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