Abstract
Strategyproofness (SP) is a cornerstone of mechanism design, ensuring that participants' dominant strategy is to report their true valuations. However, in complex environments such as Combinatorial Exchanges (CEs), achieving perfect SP while maintaining budget balance and high efficiency is mathematically impossible. This paper proposes a novel metric for "approximate strategyproofness" based on the Kullback-Leibler (KL) distance between a candidate mechanism's payoff distribution and a theoretical SP ideal, such as the VCG mechanism. Our results demonstrate that this distributional metric is a superior predictor of agent behavior and market efficiency compared to traditional regret-based metrics.
Introduction
In mechanism design, the "gold standard" is strategyproofness: a system where every participant's best move is to tell the truth, regardless of others' actions. In scenarios like Combinatorial Exchanges—where multiple buyers and sellers trade bundles of goods—perfect SP is often unattainable. Consequently, researchers design "approximately strategyproof" mechanisms.
The challenge lies in measuring "approximation." The standard metric, "regret" (the maximum utility gain from lying), often fails to predict actual cheating. If the opportunity to profit from a lie is rare, agents may remain truthful despite high potential regret. We propose a holistic metric that captures the "incentive landscape" by analyzing payoff distributions.
Methods: The KL-Distance Metric
We introduce a metric based on normalized KL-divergence to quantify how closely a mechanism's incentives align with an SP ideal.
- Reference Mechanism: We utilize a known SP mechanism, typically VCG, as a benchmark. While VCG may be impractical due to deficits, its payoff distribution represents the SP ideal.
- Payoff Distribution: We analyze the distribution of payoffs (utilities or discounts) agents receive under truthful reporting.
- The Metric: We calculate the KL-divergence between the payoff distribution of a candidate mechanism and the reference mechanism. A smaller distance indicates a closer match to the SP ideal.
To validate this metric, we employ Restricted Bayes-Nash Equilibrium (RBNE) analysis. We simulate agents who "shave" their bids (reporting a fraction of true value) to find stable points where no agent benefits from further deviation. Evaluations were conducted using three generators: Decay, Uniform, and a new "Super" generator featuring super-additive valuations common in logistics and spectrum auctions.
Key Results and Insights
Our analysis reveals that the "shape" of payoffs is more critical than the "worst-case" temptation to lie.
The Superiority of the "Small" Rule
Among candidate rules, the "Small" rule—which prioritizes surplus for agents who would receive small discounts under VCG—performed best. As shown in the CDF comparison, the Small rule most closely mimics the VCG payoff distribution.
Failure of Regret-Based Metrics
Traditional regret metrics ($L_1, L_2, L_\infty$ norms) showed no statistically significant correlation with agent behavior. For instance, the "Threshold" rule, designed to minimize maximum regret, led to more aggressive bid-shaving and lower efficiency (81-90%) in "Super" scenarios compared to the Small rule, which maintained nearly 100% efficiency.
Statistical Significance
The KL-distance metric demonstrated significant correlation with both allocative efficiency ($\rho \approx -0.38$) and the degree of bid-shaving ($\rho \approx 0.38$). This suggests that matching the overall truthful distribution is a more reliable guide for mechanism designers than minimizing isolated instances of high regret.
Discussion and Future Work
The KL-metric offers a practical tool for market designers. By observing bids in a non-SP mechanism, designers can predict which alternative rule would encourage the most truthful behavior in subsequent rounds.
However, limitations remain. The metric depends on the existence of a suitable reference mechanism. Furthermore, our equilibrium analysis focused on simple bid-shaving; future work should explore more complex, non-linear misreporting strategies. Ultimately, this metric could move beyond selection and be used to generate new payment rules by explicitly optimizing for a low KL-distance to the VCG ideal.
Summary updated