An Asymptotically Optimal VCG Redistribution Mechanism for the Public Project Problem
An Asymptotically Optimal VCG Redistribution Mechanism for the Public Project Problem
Mingyu Guo
Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 315-321.
https://doi.org/10.24963/ijcai.2019/45
We study the classic public project problem, where a group of agents need to decide whether or not to build a non-excludable public project. We focus on efficient, strategy-proof, and weakly budget-balanced mechanisms (VCG redistribution mechanisms). Our aim is to maximize the worst-case efficiency ratio --- the worst-case ratio between the achieved total utility and the first-best maximum total utility. Previous studies have identified the optimal mechanism for 3 agents. It was also conjectured that the worst-case efficiency ratio approaches 1 asymptotically as the number of agents approaches infinity. Unfortunately, no optimal mechanisms have been identified for cases with more than 3 agents. We propose an asymptotically optimal mechanism, which achieves a worst-case efficiency ratio of 1, under a minor technical assumption: we assume the agents' valuations are rational numbers with bounded denominators. We also show that if the agents' valuations are drawn from identical and independent distributions, our mechanism's efficiency ratio equals 1 with probability approaching 1 asymptotically. Our results significantly improve on previous results. The best previously known asymptotic worst-case efficiency ratio is 0.102. For non-asymptotic cases, our mechanisms also achieve better ratios than all previous results.
Keywords:
Agent-based and Multi-agent Systems: Algorithmic Game Theory
Agent-based and Multi-agent Systems: Economic Paradigms, Auctions and Market-Based Systems