Summary
Figuring out if a system that decides how to give out resources is fair can be very complicated. This paper looks at ways to quickly check if these systems follow certain fairness rules called incentive compatibility, which means no one benefits from lying. The authors develop a method to test if the system is close to fair or far from it, by looking for specific patterns that show unfairness. They also prove that their method is about as efficient as possible and extend it to pricing parts of these systems. This helps in understanding and verifying fairness in complex allocation setups without having to check everything in detail.
What this means in practice
- •For mechanism designers: Check allocation rules efficiently to ensure players have no reason to lie about their preferences before deploying mechanisms.
- •For auction platform engineers: Quickly test and validate pricing functions in allocation auctions to avoid incentive problems during runtime.
A theory result. No direct application yet.
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.