arXiv preprint ·
On testing the incentive compatibility of single-parameter allocation mechanisms
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
This paper is the first work at the intersection of game theory and property testing, giving algorithms and lower bounds for efficiently testing whether an allocation mechanism is incentive compatible (IC). We propose distinguishing whether a mechanism is $ε$-far from being IC, i.e., when it observes many monotonicity "violations." Conceptually, inspired by the literature on Boolean function monotonicity testing, we construct a tester for discrete single-parameter allocation rules. Technically, our work is the first to consider monotonicity testing of vector-valued functions on the hypergrid. We give a $\tilde{O}(n/ε)$-query algorithm to test whether a function (representing n-player allocation mechanisms) is coordinate-wise monotone versus $ε$-far from it. We also show a matching lower bound: the class of coordinate-wise monotone vector-valued functions on a Boolean hypercube or hypergrid requires $\tildeΩ(n/ε)$ queries to test whether it is $ε$-far from monotonicity, and this holds even if the tester is two-sided and allowed to make adaptive queries. Finally, we extend our upper bound to and give a tester of the same query complexity for pricing functions of allocation mechanisms. This requires overcoming the technical challenge that the path in function space to the closest IC mechanism may involve interdependent changes to both the price and the allocation rule.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computer Science & Game Theory
Equilibrium prices under hidden Markov fundamentals
Delegating Authorization to Misaligned Agents: Coalitional Alignment and Safe Control
Multi-Dimensional Matching
Approximating Optimal Welfare in Complementary Allocation under Decentralized Information
Can Labor Markets Function in the Age of AI? The Evaluation Bottleneck in Hiring
Get the few papers worth your time in Computer Science & Game Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.