Quantifying Approximate Strategyproofness

Strategyproofness is an appealing property for real world mechanisms
to enjoy, for well understood reasons such as robustness, simplicity
and fairness. But in many domains (e.g., combinatorial auctions,
course allocation, combinatorial exchanges, matching, etc.) this is a
requirement that seems to come at an unreasonable cost. In the search
for "maximally strategyproof" mechanisms that simultaneously satisfy
other desirable properties, I will first review existing approaches
for reasoning about the approximate strategyproofness of mechanisms. I
introduce an approach based on "reference mechanisms." The idea is to
quantify the strategyproofness of a mechanism through a comparison of
the payoff distribution, given truthful reports, against that of a
strategyproof reference mechanism that solves a relaxation of the
problem. This appeals to the intuitions of the decision problem facing
an agent in a Bayesian game. The results are demonstrated in the
setting of combinatorial exchanges, where the metric isolates the
successful performance of a mechanism that seeks to leave as many
agents as possible with zero ex post regret from truthful bidding.
This is part of a broader agenda of heuristic mechanism design, that
also serves to motivate the need for continued research into methods
for solving for Bayesian Nash equilibrium of combinatorial mechanisms.

Joint work with Ben Lubin.

See: "quantifying the Strategyproofness of Mechanisms via Metrics on
Payoff Distributions" , Benjamin Lubin and David C. Parkes, In the 25th
Conference on Uncertainty in Artificial Intelligence, 2009.
http://www.eecs.harvard.edu/econcs/pubs/lubin_UAI09.pdf