Public project payments optimized without number restrictions
Asymptotically Optimal Public Project Redistribution without Bounded Precision: A Complex-Analytic Proof
Computer Science and Game Theory
Summary
When a group of people decides whether to fund a public project, it’s important to design rules that share costs fairly without losing money. Previous methods worked well only when everyone’s contributions were simple fractions with limited size. The authors show a way to handle any real-number contributions, keeping the system fair and efficient as the group grows larger. They use a clever math technique called complex analysis to prove their method works better than past approaches.
What this means in practice
- •For market platform designers: Design payment rules for public goods that maximize efficiency without assuming simple value reporting formats.
- •For auction engineers: Build more accurate redistribution mechanisms for group decisions with continuous or complex preference reports.
A theory result. No direct application yet.
Authors
Mingyu Guo
Abstract
We study worst-case VCG redistribution mechanism design for the public project problem, where n agents decide whether to build a non-excludable public project and the designer chooses a Groves term that returns as much of the VCG payment as possible without running a deficit. The objective is the worst-case efficiency ratio, the worst-case ratio between the agents' total utility and the first-best total utility. Prior work showed that this ratio can approach 1 as n grows only under a bounded precision assumption, that all types are rational numbers with a common bounded denominator. The assumption is stronger than it looks: it confines the difficult profiles to those in which all but a bounded number of agents report zero, and an agent who reports zero knows the total exactly. Without it, the best known guarantee tends to 1/2. We remove the assumption. We construct a deterministic, anonymous, strategy-proof, and non-deficit mechanism for arbitrary real types in [0,1] whose worst-case efficiency ratio is 1-O(1/log log n). The construction estimates the shortfall of the reported total below the project cost by filling in each agent's missing report with a resampled one, then estimates the error of that estimate, then the error of the error, and so on. After m rounds the aggregate error is at most 1/Hm mean reports, where Hm is the mth harmonic number. The proof of this bound is the heart of the paper and, unusually for a result about payments, uses complex analysis: a trigonometric representation of the shortfall function together with the Poisson-Jensen inequality for bounded analytic functions in the upper half plane.