Compensation Design paper proves optimal 2x price of anarchy for decentralized contributions

A new paper on arXiv (2607.14438) tackles a fundamental challenge for decentralized platforms: how to design payment rules that incentivize high-quality contributions when a budget-constrained principal has a monotone submodular value function. The authors—Ioannis Anagnostides, Kshipra Bhawalkar, Christopher Liaw, Aranyak Mehta, Renato Paes Leme, Yifeng Teng, Grigoris Velegkas, and Weiqiang Zheng—introduce 'compensation design.' They show that a simple, cost-oblivious, anonymous marginal-contribution payment rule guarantees pure Nash equilibria always exist and achieve a price of anarchy (PoA) of at most 2+o_λ(1) in the large-market regime (λ→0, where each individual cost is at most a λ fraction of budget). This factor of 2 is provably unavoidable among deterministic cost-oblivious rules.

Surprisingly, a payment rule based on the Shapley value may admit no pure Nash equilibria, despite its popularity in cooperative game theory. The paper also proves that computing a pure Nash equilibrium is PLS-complete, motivating the study of coarse correlated equilibria, which also achieve the 2+o(1) PoA bound—even under the Shapley value rule. Extensions show that for (monotone) XOS valuations, no oracle-efficient payment rule can achieve a PoA of O(n^{1/2 - ε}), and for submodular non-monotone valuations, natural rules fail entirely. Finally, for combinatorial action sets, the authors provide randomized payment rules with logarithmic PoA guarantees for subadditive values, with matching lower bounds.