2015/07/08 by Dimitris Fotakis, Fotakis, Dimitris, Christos Tzamos +2
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Voting Systems #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.1507.02301
openalex publication_date 2015/07/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce a general approach based on selective verification and obtain approximate mechanisms without money for maximizing the social welfare in the general domain of utilitarian voting. Having a good allocation in mind, a mechanism with verification selects few critical agents and detects, using a verification oracle, whether they have reported truthfully. If yes, the mechanism produces the desired allocation. Otherwise, the mechanism ignores any misreports and proceeds with the remaining agents. We obtain randomized truthful (or almost truthful) mechanisms without money that verify only O(ln m / ε) agents, where m is the number of outcomes, independently of the total number of agents, and are (1-ε)-approximate for the social welfare. We also show that any truthful mechanism with a constant approximation ratio needs to verify Ω(log m) agents. A remarkable property of our mechanisms is robustness, namely that their outcome depends only on the reports of the truthful agents.