Metraipolis › archive › dc_c1f78076f4bd
On testing the incentive compatibility of single-parameter allocation mechanisms — arXiv:2609.17406
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.17406
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-15T19:31:08.793Z
- SHA-256 of the archived text
d14b56a3d18132eace1db008640db617d00ccadb37ada250fba38441fa31dada- Stable URL of this page
https://metraipolis.com/documento/dc_c1f78076f4bd
How to cite
On testing the incentive compatibility of single-parameter allocation mechanisms — arXiv:2609.17406 — arXiv (en), https://arxiv.org/abs/2609.17406 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c1f78076f4bd (Metraipolis archive dc_c1f78076f4bd, sha256 d14b56a3d18132eace1db008640db617d00ccadb37ada250fba38441fa31dada)
BibTeX
@misc{dcc1f78076f4bd,
title = {On testing the incentive compatibility of single-parameter allocation mechanisms — arXiv:2609.17406},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.17406},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c1f78076f4bd; sha256 d14b56a3d18132eace1db008640db617d00ccadb37ada250fba38441fa31dada},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.17406. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\epsilon$-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/\epsilon)$-query algorithm to test whether a function (representing n-player allocation mechanisms) is coordinate-wise monotone versus $\epsilon$-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{\Omega}(n/\epsilon)$ queries to test whether it is $\epsilon$-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.
Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-16 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Theoretical Economics (econ.TH).
Pagina del lavoro: https://arxiv.org/abs/2609.17406 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T18:39:23.384Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-16?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).