Asymptotically Optimal Public Project Redistribution without Bounded Precision: A Complex-Analytic Proof

概要

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.

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
Asymptotically Optimal Public Project Redistribution without Bounded Precision: A Complex-Analytic Proof

# 概要
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…

# 原典
https://arxiv.org/abs/2610.10995

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。