CS Paper Radar

On testing the incentive compatibility of single-parameter allocation mechanisms

Jason Milionis, William Pires

cs.GT cs.CCcs.DSecon.TH ·submitted 2026-09-15 16:35 UTC · v1
publishedtheory

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.

Comment
42 pages, accepted at journal of Mathematics of Operations Research

Closest papers

Nearest neighbours by meaning across the whole index.

Polyhedral Methods for Cooperative Games: Small Lifts and Hard Faces

cs.GT cs.CCmath.COmath.OC ·2026-09-21 ·Michel Grabisch and. Hans Raj Tiwary
similarity 0.66
Abstract

We study the computational complexity of fundamental algorithmic problems -- membership testing, separation, valid-inequality testing, and linear optimization -- over polytopes and cones arising from cooperative games (also known as pseudo-Boolean functions). A central obstacle in the study of such problems is that a general cooperative game on $n$ players requires $2^n$ values, so the input size is $2^n$ for a game with $n$ players, making these computational tasks theoretically trivial. Restricting to $k$-additive games reduces the input size to $O(n^k)$, making such games a natural target for meaningful questions about the existence of efficient algorithms. On the positive side, we give an explicit extended formulation of size $O(n^k)$ for the core of $k$-additive $k$-monotone games, allowing all four problems to be solved by a single polynomial-size linear program -- in particular, circumventing the ellipsoid method that is needed when building from earlier tractability results of Deng and Papadimitriou, or of Edmonds. For the cone of $k$-additive $(k{-}1)$-monotone games, we give a complete characterization of its extreme rays and derive the same $O(n^k)$ bound on extension complexity, yielding a geometry-based proof and generalization of a result of Billionnet and Minoux. On the negative side, we show that for $l \leq k-2$ the cone of $k$-additive $l$-monotone games is computationally intractable: membership testing is not in NP (unless NP\,=\,coNP), valid-inequality testing is NP-complete, and extension complexity is at least $1.5^n$. Our hardness results yield, as a special case, a result of Crama and of Gallo and Simone. Furthermore, our hardness results also explain the lack of any good characterization of the extreme rays of the cone of $k$-additive $(k{-}2)$-monotone games.

0.27

Revisiting EFX and fPO Allocations for Binary Chores

cs.GT ·2026-09-12 ·Zehan Lin, Xiaowei Wu, Shengwei Zhou
similarity 0.66
Abstract · 28 pages, no figure

We study fair and efficient allocations of indivisible chores under binary additive costs, with a focus on unequal entitlements and best-of-both-worlds guarantees. While binary valuations have been extensively studied for goods, their chore counterpart remains much less understood. A notable exception is due to Tao et al. (TCS 2025), who established that EFX and fPO are compatible for binary chores with equal entitlements. We revisit binary chores under unequal entitlements and establish the computation of allocations that satisfy WEFX and fPO. Our key technical contribution is a new lexicographic potential function tailored to chores: any allocation minimizing this potential ensures both WEFX and fPO. This potential further guides a polynomial-time local-search algorithm for computing allocations with such fairness and efficiency guarantees. For best-of-both-worlds guarantees, we show that unequal entitlements create a sharp obstruction: even with two agents and identical binary additive costs, no lottery can simultaneously satisfy ex-ante WEF and ex-post WEF1. In contrast, for equal entitlements, we construct in polynomial time a lottery that is ex-ante EF and fPO, while every realization is both EFX and fPO.

0.41

When Maximum Nash Welfare Becomes Strongly Fair: Bi-valued Goods

cs.GT ·2026-09-09 ·Zehan Lin, Xiaowei Wu, Shengwei Zhou
similarity 0.65
Abstract

For the fair allocation of indivisible goods, the milestone work of Caragiannis et al. (2019) revolutionized the understanding of Maximum Nash Welfare (MNW) allocations by revealing their "unreasonable" ability to balance fairness (EF1) and efficiency (PO) for general additive functions. Subsequent work established that MNW allocations simultaneously satisfy EFX and GMMS (and consequently MMS and PMMS) for binary instances (Amanatidis et al. 2021 and Barman et al. 2018), and satisfy EFX for bi-valued instances (Amanatidis et al. 2021). In this paper, we revisit the (personalized) bi-valued instances and provide a tight characterization of the approximation guarantees of MNW allocations with respect to EFX, PMMS, and GMMS, showing that these guarantees are significantly stronger than what is known for general valuations. Furthermore, we demonstrate that even for the slightly more general setting of tri-valued instances, the fairness guarantees of MNW deteriorate significantly, which establishes a sharp boundary on the instances for which MNW allocations are strongly fair.

0.18

Equilibria of Round-Robin: Computational Hardness and Fairness for Few Subadditive Agents

cs.GT cs.CCcs.DS ·2026-09-16 ·Paul W. Goldberg, Alexandros Hollender, Giannis Tyrovolas
theory similarity 0.64
Abstract

The round-robin procedure is a simple and well-studied fair division mechanism where agents pick goods in turns. Motivated by draft mechanisms in sports leagues, we investigate strategic behaviour in online round-robin for subadditive agents. This gives rise to an extensive-form game, and we study the computational problem of computing a subgame perfect Nash equilibrium (SPNE). We show that for just two submodular agents, computing an SPNE is $\mathsf{PSPACE}$-hard. Even for the class of $\mathit{OXS}$ utilities, which are a special case of submodular utilities, computing an SPNE remains $\mathsf{NP}$-hard for a small number of agents. We complement our computational results with normative results. We show that for just three additive agents, there exist instances where every equilibrium violates EF1. This separates the online and the direct revelation games. On the positive side, we show that for additive agents every equilibrium allocation is proportional up to one good (PROP1) and for two additive agents it is also EF1. Finally, by showing that round-robin is bossy at equilibrium, we prove that the number of equilibrium allocations can be exponential even if agents have lexicographic preferences.

0.19

Balanced Fair Division for Three Agents under General Valuations and Laminar Constraints

cs.GT ·2026-08-10 ·Max Dupré la Tour
theory similarity 0.63
Abstract

We study fair allocations of indivisible items under general set valuations. We prove that every instance with three agents and arbitrary real-valued valuations admits a balanced allocation that is envy-free up to one good and one chore (EF$1^c_g$). This directly implies balanced EF$1$ when each valuation is either monotone nondecreasing or monotone nonincreasing. We also show that balanced EF$1$ cannot be guaranteed without monotonicity: there exists an instance with three agents, nine items, and identical nonmonotone valuations that admits no balanced EF$1$ allocation. We then consider a common laminar matroid constraint. Whenever a complete feasible allocation exists, we prove that there is a complete feasible allocation that is balanced and envy-free up to two goods and two chores (EF$2^c_g$) for arbitrary valuations. The allocation can additionally be chosen so that the numbers of items from every laminar set assigned to the three agents differ by at most two. Most proofs in this paper were obtained using GPT-5.6. We subsequently verified the proofs for correctness and refined their exposition and arguments, also with the aid of GPT-5.6.

0.04

Exact Hill Shares Are Simultaneous Guarantees

cs.GT ·2026-09-18 ·Bo Li, Hanyu Li, Chenghua Liu
benchmarktheory similarity 0.63
Abstract

Fair division of indivisible bads seeks allocations that guarantee every agent a bundle whose cost is no larger than a meaningful fairness benchmark. The canonical minimax share has widely been used; unfortunately, it is not a simultaneous guarantee. Hill (Ann. Probab., 1987) initiated a complementary approach in which the share depends only on the number of agents and the largest possible single-item value. Li et al. (ACM Trans. Econ. Comput., 2024) gave the exact Hill formula and proved that its monotone closure is a simultaneous guarantee. The closure treats the largest-item cost only as an upper bound and can be strictly larger than the share conditioned on the \emph{actual} largest item. They asked whether this smaller exact share is itself simultaneously guaranteed for three or more agents. We resolve this open question affirmatively. For any number of agents and arbitrary heterogeneous largest-item costs, there is one allocation that satisfies every agent's exact Hill's share. We further provide a polynomial-time algorithm computes such an allocation. Our algorithm combines an ordered moving knife with a tail-domination invariant, and a one-sided trimmed subset-sum routine for the two-agent endpoint without computing an exact minimax partition.

0.16

Best-of-Both-Worlds Fair Division via Subsidies

cs.GT ·2026-10-10 ·Surya Panchapakesan, Rohit Vaish
theory similarity 0.63
Abstract · 16 pages in main body, 1 page appendix

We study the relationship between fair division with $\textit{subsidies}$ and $\textit{best-of-both-worlds}$ (BoBW) fairness for indivisible items. We prove a general reduction of BoBW existence to envy-freeability. Specifically, for any scale-free ex-post property $P$ (e.g., EF1, EFX, PO) and any scale-free valuation class $\mathcal{V}$ (e.g, additive, submodular, subadditive, monotone), if every instance in $\mathcal{V}$ admits a $P$-allocation that can be made envy-free using subsidies, then every such instance admits an ex-ante envy-free lottery supported on $P$-allocations. The proof uses linear programming duality. As applications, the reduction gives alternative proofs of BoBW existence results for additive goods, chores, and mixtures of goods and chores. The converse of our general reduction holds for two agents but fails for three: We provide a four-good counterexample with monotone submodular valuations where an ex-ante envy-free and ex-post EF1 lottery exists, but no allocation is simultaneously EF1 and envy-freeable. For lexicographic valuations, we prove simultaneous EFX, Pareto optimality, and envy-freeability (and hence BoBW guarantees for EFX+PO) for three agents, and show that even EFX and envy-freeability can be incompatible for four agents.

0.16

Simultaneous Envy and Equitability Guarantees

cs.GT cs.AIecon.TH ·2026-08-26 ·Hadi Hosseini, Shraddha Pathak, Lirong Xia, Chengkai Zhang
similarity 0.63
Abstract · 43 pages

Recent work in fair division has focused on either simultaneously satisfying closely related fairness notions or achieving a single notion across the ex-ante and ex-post worlds. We study the compatibility of two fundamentally different fairness notions: envy-freeness and equitability. For indivisible goods-only and chores-only settings, we study the existence and complexity of simultaneously satisfying their relaxations, revealing sharp contrasts between the two settings. For normalized binary goods, we give a polynomial-time algorithm for computing an EF1+EQ1 allocation with at most seven agents, but also construct a normalized instance with a larger number of agents for which no such allocation exists. In sharp contrast, binary chores admit the stronger EFX+EQX guarantee for any number of agents, even without normalization. We further initiate the study of cross-notion ex-ante and ex-post guarantees, asking whether randomized allocations can provide ex-ante guarantees for one notion while preserving ex-post guarantees for another.

0.41