Electrical Engineering and Computer Science

AI Seminar

Quantifying Approximate Strategyproofness

David C. Parkes

Harvard University
Friday, December 04, 2009
3:30pm - 5:00pm
3725 Beyster Bldg. (Stained Glass Conference Room)

Add to Google Calendar

About the Event

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

Additional Information

Sponsor(s): Special AI Seminar

Open to: Public