Timezone: »

 
Poster
Welfare Guarantees from Data
Darrell Hoy · Denis Nekipelov · Vasilis Syrgkanis

Tue Dec 05 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #225
in Posters Tue »

Analysis of efficiency of outcomes in game theoretic settings has been a main item of study at the intersection of economics and computer science. The notion of the price of anarchy takes a worst-case stance to efficiency analysis, considering instance independent guarantees of efficiency. We propose a data-dependent analog of the price of anarchy that refines this worst-case assuming access to samples of strategic behavior. We focus on auction settings, where the latter is non-trivial due to the private information held by participants. Our approach to bounding the efficiency from data is robust to statistical errors and mis-specification. Unlike traditional econometrics, which seek to learn the private information of players from observed behavior and then analyze properties of the outcome, we directly quantify the inefficiency without going through the private information. We apply our approach to datasets from a sponsored search auction system and find empirical results that are a significant improvement over bounds from worst-case analysis.

Keywords: Learning Theory · Game Theory and Computational Economics
[ Paper] 

Author Information

Darrell Hoy (Tremor Technologies)
Denis Nekipelov (University of Virginia)
Vasilis Syrgkanis (Microsoft Research)

More from the Same Authors