Better Strategyproof Mechanisms without Payments or Prior - An Analytic Approach

Yun Kuen Cheung

Abstract

This research advances the design of strategyproof (SP) mechanisms for resource allocation in environments where monetary incentives are prohibited. By transitioning from traditional numerical methods to a rigorous analytic framework, this work derives new mechanisms that achieve superior social welfare. Key contributions include a 0.67776-competitive mechanism for multiple items—breaking the long-standing 2/3 performance barrier—and a 5/6-competitive mechanism for the two-item case.

Introduction

In mechanism design, the objective is often to distribute scarce resources, such as computing power or medical placements, to maximize "social welfare" (the aggregate utility of all participants). The gold standard for such systems is strategyproofness: a property ensuring that no participant can gain an advantage by misrepresenting their true preferences.

While strategyproofness is relatively straightforward to achieve when payments are allowed, many critical real-world scenarios—including kidney exchanges, school choice, and internal corporate resource sharing—disallow monetary transfers. In these "non-monetary" settings, and without prior knowledge of agent preferences, designers struggle to maintain efficiency. Efficiency is typically measured by the competitive ratio, defined as the social welfare produced by the SP mechanism divided by the welfare of the optimal (but non-SP) allocation. This paper seeks to establish new upper limits for this ratio and design concrete mechanisms that approach these theoretical ceilings.

Methodology

Departing from the "guess-and-check" or heavy Linear Programming (LP) methods prevalent in prior literature, this work adopts an analytic approach to mechanism design:

  1. Analytic Sufficient Conditions: The paper introduces Theorem 3, which provides mathematical conditions based on the partial derivatives of allocation functions. This allows for the direct derivation of mechanisms rather than mere verification of existing ones.
  2. High-Resolution Linear Programming: By pruning redundant constraints from previous LP formulations, the author solved the allocation problem with significantly higher resolution (N=400 vs. N=50), resulting in tighter, more accurate upper bounds.
  3. Partial Allocation (PA) Averaging: For multi-item scenarios, the author employs a weighted average of existing Partial Allocation mechanisms. This technique "smooths" worst-case performance scenarios to improve the overall competitive ratio.
  4. Dynamic-Increasing-Price (DIP) Mechanisms: The paper proposes a new class of mechanisms where agents "purchase" items using virtual currency. Crucially, the prices an agent encounters are determined solely by the preferences of other agents. This ensures the agent remains a "price-taker," removing any incentive to lie about their utility.

Key Insights

The "Holding Back" Paradox

A counter-intuitive finding of this research is that partial mechanisms—those that intentionally withhold a fraction of the resources—can be more competitive than full mechanisms. By strategically "burning" a small portion of the items, the designer can more effectively disincentivize strategic manipulation, ultimately leading to a higher guaranteed social welfare in the worst case.

Virtual Markets as a Shield

The DIP mechanism effectively transforms the resource allocation problem into a Fisher market. By decoupling an agent's reported preferences from the prices they face, the mechanism captures the efficiency of market equilibria while strictly enforcing strategyproofness.

Results and Performance

The analytic framework yielded several state-of-the-art results in competitive ratios:

  • Breaking the 2/3 Barrier: For the general multi-item case, the paper introduces a mechanism that is 0.67776-competitive, surpassing the previous state-of-the-art limit of 2/3 (≈0.666).
  • Two-Item Optimality: The author derived a full mechanism for the two-item case that is 5/6-competitive (≈0.833). The author conjectures this is the theoretical optimum for full mechanisms in this setting.
  • Refined Upper Bounds: The research improved the known upper bounds on competitiveness to approximately 0.841 for full mechanisms and 0.8644 for partial mechanisms.
  • Human-Verifiable Proofs: The paper provides a compact mathematical proof for an upper bound of 0.9523. This represents a significant step toward moving away from "black-box" computer-generated proofs toward human-understandable logic.

Limitations and Future Directions

Despite these advancements, a gap remains between the best-known mechanism (0.833) and the best-known upper bound (0.841) for the two-item case. Additionally, while DIP mechanisms are theoretically robust, ensuring their feasibility (preventing over-allocation) becomes computationally complex as the number of items ($m$) increases. Finally, while the analytic derivations are highly detailed for the two-agent case, extending these specific mathematical proofs to $n$ agents remains a primary challenge for future research in the field.

Summary updated

BibTeX
@inproceedings{cheung2016better,
  author = {Yun Kuen Cheung},
  title = {{Better Strategyproof Mechanisms without Payments or Prior - An Analytic Approach}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure