Algorithmic game theory and econometrics

Abstract

The traditional econometrics approach for inferring properties of strategic interactions that are not fully observable in the data, heavily relies on the assumption that the observed strategic behavior has settled at an equilibrium. This assumption is not robust in complex economic environments such as online markets where players are typically unaware of all the parameters of the game in which they are participating, but rather only learn their utility after taking an action. Behavioral models from online learning theory have recently emerged as an attractive alternative to the equilibrium assumption and have been extensively analyzed from a theoretical standpoint in the algorithmic game theory literature over the past decade. In this letter we survey two recent works, [Nekipelov et al. 2015, Hoy et al. 2015], in which we take a learning agent approach to econometrics, i.e. infer properties of the game, such as private valuations or efficiency of observed allocation, by only assuming that the observed repeated behavior is the outcome of a no-regret learning algorithm, rather than a static equilibrium. In both works we apply our methods to datasets from Microsoft's sponsored search auction system.

References

1. Athey, S. and Nekipelov, D. 2010. A structural model of sponsored search advertising auctions. In Sixth ad auctions workshop.
2. Bajari, P., Hong, H., and Nekipelov, D. 2013. Game theory and econometrics: a survey of some recent results. Advances in Economics and Econometrics 3.
3. Blum, A., Hajiaghayi, M., Ligett, K., and Roth, A. 2008. Regret minimization and the price of total anarchy. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing. STOC '08. ACM, New York, NY, USA, 373--382.
4. Foster, D. P. and Vohra, R. V. 1997. Calibrated learning and correlated equilibrium. Games and Economic Behavior 21, 12, 40--55.
5. Freund, Y. and Schapire, R. E. 1999. Adaptive game playing using multiplicative weights. Games and Economic Behavior 29, 1, 79--103.
6. Hartline, J., Hoy, D., and Taggart, S. 2014. Price of Anarchy for Auction Revenue. In ACM Conference on Economics and Computation. ACM Press, New York, New York, USA, 693--710.
7. Hoy, D., Nekipelov, D., and Syrgkanis, V. 2015. Robust data-driven efficiency guarantees in auctions. 1st Workshop on Algorithmic Game Theory and Data Science and CoRR abs/1505.00437.
8. Nekipelov, D., Syrgkanis, V., and Tardos, E. 2015. Econometrics for learning agents. In Proceedings of the 16th ACM Conference on Economics and Computation. EC'15.
9. Roughgarden, T. 2009. Intrinsic robustness of the price of anarchy. In Proceedings of the 41st annual ACM symposium on Theory of computing. STOC '09. ACM, New York, NY, USA, 513--522.
10. Syrgkanis, V. and Tardos, E. 2013. Composable and efficient mechanisms. In Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing. STOC '13. ACM, New York, NY, USA, 211--220.

Index Terms

• Applied computing

  • Electronic commerce

  • Law, social and behavioral sciences

    • Economics

• Theory of computation

  • Design and analysis of algorithms

    • Online algorithms

      • Online learning algorithms

  • Models of computation

    • Interactive computation

  • Theory and algorithms for application domains

    • Machine learning theory

      • Online learning theory