Introduction
In mechanism design, strategyproofness (SP) is the ideal property ensuring that agents' best interest is to report their true values. However, SP is often mathematically incompatible with other critical goals like budget balance or computational tractability. When SP is unattainable, designers must settle for "approximately strategyproof" mechanisms.
Traditionally, this approximation is measured by regret—the maximum utility an agent could gain by misreporting. However, regret is a worst-case metric that often fails to reflect average-case behavior. This paper introduces a novel metric to quantify strategyproofness by measuring the normalized Kullback-Leibler (KL) distance between the payoff distributions of a candidate mechanism and a strategyproof reference mechanism, such as Vickrey-Clarke-Groves (VCG).
Methodology: The Distributional Approach
The core idea is that the overall "shape" of incentives across the population is a better predictor of equilibrium behavior than the single worst-case scenario. The authors propose a three-step process:
- Reference Mechanism: Identify a strategyproof mechanism (e.g., VCG) that solves a relaxed version of the problem.
- Payoff Distribution: Model the distribution of utilities agents receive under the candidate mechanism assuming truthful reporting.
- KL-Distance: Quantify how much the candidate's payoff distribution deviates from the reference's.
Case Study: Combinatorial Exchanges
The authors validated this metric using Combinatorial Exchanges (CEs), evaluating several payment rules including "Small," "Large," and "Threshold." The "Small" rule prioritizes giving surplus to agents who would have received the smallest payoffs under VCG.
As shown in the cumulative distribution function (CDF) plot above, the "Small" rule mimics the VCG payoff distribution far more effectively than other rules. Interestingly, the "Threshold" rule—designed specifically to minimize maximal regret—shows a much larger distributional gap.
The Regret Paradox
A key insight of the study is that minimizing regret does not necessarily lead to better equilibrium performance. While the "Threshold" rule succeeds in lowering the peak incentive to lie, it performs significantly worse in actual equilibrium than the "Small" rule.
The figure above illustrates this paradox. Although the "Threshold" rule has a lower peak profit increase (lower regret), the "Small" rule's closer adherence to the VCG distribution (as seen in the previous figure) results in higher efficiency and more truthful behavior in practice. The authors attribute this to a "risk vs. reward" balance: the "Small" rule leaves many agents with negligible gains from lying, while those with larger potential gains face a high risk of failing to trade if they shave their bids too much.
Results and Implications
The KL-distance metric showed a significant correlation with both equilibrium efficiency and the degree of bid-shaving, whereas traditional regret metrics ($L_1, L_2, L_\infty$) did not. In complex scenarios, the "Small" rule achieved near-perfect efficiency, outperforming the regret-minimizing "Threshold" rule by over 10%.
These findings suggest that mechanism designers should prioritize the average shape of incentives over worst-case metrics. The authors propose that this KL-distance metric can be integrated into automated mechanism design to create more robust, efficient systems in the real world.
Summary updated