research-article

A Learning Framework for Distribution-Based Game-Theoretic Solution Concepts

Authors:

Yair ZickAuthors Info & Claims

EC '20: Proceedings of the 21st ACM Conference on Economics and Computation

Pages 355 - 377

https://doi.org/10.1145/3391403.3399509

Published: 13 July 2020 Publication History

Abstract

The past few years have seen several works exploring learning economic solutions from data; these include optimal auction design, function optimization, stable payoffs in cooperative games and more. In this work, we provide a unified learning-theoretic methodology for modeling such problems, and establish tools for determining whether a given solution concept can be efficiently learned from data. Our learning theoretic framework generalizes a notion of function space dimension --- the graph dimension --- adapting it to the solution concept learning domain. We identify sufficient conditions for efficient solution learnability, and show that results in existing works can be immediately derived using our methodology. Finally, we apply our methods in other economic domains, yielding learning variants of competitive equilibria and Condorcet winners.

References

[1]

M. Anthony and P. Bartlett. 1999. Neural Network Learning: Theoretical Foundations. Cambridge University Press.

[2]

Y. Bachrach, E. Elkind, E. Malizia, R. Meir, D. Pasechnik, J. S. Rosenschein, J. Rothe, and M. Zuckerman. 2018. Bounds on the Cost of Stabilizing a Cooperative Game. Journal of Artificial Intelligence Research, Vol. 63 (2018), 987--1023.

Digital Library

[3]

M.F. Balcan, A.D. Procaccia, and Y. Zick. 2015a. Learning cooperative games. In Proc. of the 24th IJCAI. 475--481.

[4]

M.F. Balcan, T. Sandholm, and E. Vitercik. 2016. Sample Complexity of Automated Mechanism Design. In Proc. of the 29th NIPS. 2083--2091.

[5]

M. F. Balcan, T. Dick, R. Noothigattu, and A. D. Procaccia. 2018a. Envy-Free Classification. CoRR, Vol. abs/1809.08700 (2018). arxiv: 1809.08700

[6]

M. F. Balcan and N. Harvey. 2011. Learning Submodular Functions. In Proc. of the 43rd STOC. 793--802.

[7]

M. F. Balcan, A. D. Procaccia, and Y. Zick. 2015b. Learning Cooperative Games. CoRR, Vol. abs/1505.00039 (2015).

[8]

M. F. Balcan, T. Sandholm, and E. Vitercik. 2018b. A General Theory of Sample Complexity for Multi-Item Profit Maximization. In Proc. of the 19th EC. 173--174.

[9]

E. Balkanski, A. Rubinstein, and Y. Singer. 2016. The Power of Optimization from Samples. In Proc. of the 29th NIPS. 4017--4025.

[10]

E. Balkanski, A. Rubinstein, and Y. Singer. 2017a. The limitations of optimization from samples. In Proc. of the 49th STOC. 1016--1027.

[11]

E. Balkanski and Y. Singer. 2017. The sample complexity of optimizing a convex function. In Proc. of the 30th COLT. 275--301.

[12]

E. Balkanski, U. Syed, and S. Vassilvitskii. 2017b. Statistical Cost Sharing. In Proc. of the 30th NIPS. 6222--6231.

[13]

A. Bhattacharyya and P. Dey. 2015. Sample Complexity for Winner Prediction in Elections. In Proc. of the 14th AAMAS. 1421--1431.

[14]

F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A.D. Procaccia (Eds.). 2016. Handbook of Computational Social Choice. Cambridge University Press.

[15]

G. Brero, B. Lubin, and S. Seuken. 2018. Combinatorial Auctions via Machine Learning-based Preference Elicitation. In Proc. of the 27th IJCAI. 128--136.

[16]

E. Budish. 2011. The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. Journal of Political Economy, Vol. 119, 6 (2011), 1061--1103.

[17]

R. Cole and T. Roughgarden. 2014. The sample complexity of revenue maximization. In Proc. of the 46th STOC. 243--252.

[18]

L. J. Cromme and I. Diener. 1991. Fixed Point Theorems For Discontinuous Mappings. Mathematical Programming, Vol. 51 (1991), 257--267. Issue 1--3.

Digital Library

[19]

A. Daniely, S. Sabato, S. Ben-David, and S. Shalev-Shwartz. 2011. Multiclass Learnability and the ERM principle. Journal of Machine Learning Research, Vol. 16 (2011), 2377--2404.

[20]

N. Devanur, Z. Huang, and C. Psomas. 2016. The Sample Complexity of Auctions with Side Information. In Proc. of the 48th STOC. 426--439.

[21]

E. Elkind, M. Lackner, and D. Peters. 2017. Structured Preferences. In Trends in Computational Social Choice, U. Endriss (Ed.). AI Access, Chapter 10.

[22]

F. Gul and E. Stacchetti. 1999. Walrasian equilibrium with gross substitutes. Journal of Economic theory, Vol. 87, 1 (1999), 95--124.

[23]

Jason S Hartford, James R Wright, and Kevin Leyton-Brown. 2016. Deep Learning for Predicting Human Strategic Behavior. In Proc. of the 29th NIPS. 2424--2432.

[24]

A. Hassidim and Y. Singer. 2017. Submodular Optimization under Noise. In Proc. of the 30th COLT. 1069--1122.

[25]

A. Igarashi and E. Elkind. 2016. Hedonic Games with Graph-restricted Communication. In Proc. of the 15th AAMAS. 242--250.

[26]

A. Igarashi, J. Sliwinski, and Y. Zick. 2019. Forming Probably Stable Communities with Limited Interactions. In Proc. of the 33rd AAAI. 2053--2060.

[27]

M.J. Kearns and U.V. Vazirani. 1994. An introduction to computational learning theory. MIT press.

[28]

Nicholas Mattei and Toby Walsh. 2013. PrefLib: A Library of Preference Data http://preflib.org. In Proc. of the 3rd ADT (Lecture Notes in Artificial Intelligence). Springer.

[29]

J. Morgenstern and T. Roughgarden. 2015. On the Pseudo-Dimension of Nearly Optimal Auctions. In Proc. of the 28th NIPS. 136--144.

[30]

J. Morgenstern and T. Roughgarden. 2016. Learning Simple Auctions. In Proc.of the 29th COLT. 1298--1318.

[31]

B. K. Natarajan. 1989. On learning sets and functions. Machine Learning, Vol. 4, 1 (1989), 67--97.

Digital Library

[32]

N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani (Eds.). 2007. Algorithmic Game Theory. Cambridge University Press.

[33]

A. Othman, C. Papadimitriou, and A. Rubinstein. 2014. The complexity of fairness through equilibrium. In Proc.of the 15th EC. 209--226.

[34]

N. Rosenfeld, E. Balkanski, A. Globerson, and Y. Singer. 2018. Learning to Optimize Combinatorial Functions. In Proc.of the 35th ICML. 4374--4383.

[35]

S. Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan. 2010. Learnability, Stability and Uniform Convergence. Journal of Machine Learning Research, Vol. 11 (2010), 2635--2670.

Digital Library

[36]

J. Sliwinski and Y. Zick. 2017. Learning Hedonic Games. In Proc. of the 26th IJCAI. 2730--2736.

[37]

V. Syrgkanis. 2017. A Sample Complexity Measure with Applications to Learning Optimal Auctions. In Proc. of the 30th NIPS. 5352--5359.

[38]

V.N. Vapnik and A. Ya. Chervonenkis. 1971. On the Uniform Convergence of Relative Frequencies of Events to their Probabilities. Theory of Probability and its Applications, Vol. 16, 2 (1971), 264--280.

[39]

H. Zhang and V. Conitzer. 2019. A PAC Framework for Aggregating Agents' Judgments. In Proc. of the 33rd AAAI. 2237--2244.

Cited By

Xia L(2022)Group decision making under uncertain preferences: powered by AI, empowered by AIAnnals of the New York Academy of Sciences10.1111/nyas.147341511:1(22-39)Online publication date: 4-Feb-2022
https://doi.org/10.1111/nyas.14734
Lev OLu WTsang AZick YDignum FLomuscio AEndriss UNowé A(2021)Learning Cooperative Solution Concepts from Voting Behavior: A Case Study on the Israeli KnessetProceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3463952.3464163(1572-1574)Online publication date: 3-May-2021
https://dl.acm.org/doi/10.5555/3463952.3464163
Lev OPatel NViswanathan VZick YDignum FLomuscio AEndriss UNowé A(2021)The Price is (Probably) Right: Learning Market Equilibria from SamplesProceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3463952.3464043(755-763)Online publication date: 3-May-2021
https://dl.acm.org/doi/10.5555/3463952.3464043

Index Terms

A Learning Framework for Distribution-Based Game-Theoretic Solution Concepts
1. Theory of computation
  1. Theory and algorithms for application domains
    1. Algorithmic game theory and mechanism design
    2. Machine learning theory

Recommendations

A Learning Framework for Distribution-Based Game-Theoretic Solution Concepts
The past few years have seen several works exploring learning economic solutions from data, including optimal auction design, function optimization, stable payoffs in cooperative games, and more. In this work, we provide a unified learning-theoretic ...
Computing Dominance-Based Solution Concepts

Two common criticisms of Nash equilibrium are its dependence on very demanding epistemic assumptions and its computational intractability. We study the computational properties of less demanding set-valued solution concepts that are based on varying ...
Computing dominance-based solution concepts
EC '12: Proceedings of the 13th ACM Conference on Electronic Commerce

Two common criticisms of Nash equilibrium are its dependence on very demanding epistemic assumptions and its computational intractability. We study the computational properties of less demanding set-valued solution concepts that are based on varying ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EC '20: Proceedings of the 21st ACM Conference on Economics and Computation

July 2020

937 pages

ISBN:9781450379755

DOI:10.1145/3391403

General Chairs:
Péter Biró
Hungarian Academy of Sciences
,
Jason Hartline
Northwestern University
,
Program Chairs:
Michael Ostrovsky
Stanford University
,
Ariel Procaccia
Harvard University

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGecom: Special Interest Group on Economics and Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 July 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Research Foundation Singapore

Conference

EC '20

Sponsor:

SIGecom

EC '20: The 21st ACM Conference on Economics and Computation

July 13 - 17, 2020

Virtual Event, Hungary

Acceptance Rates

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
118
Total Downloads

Downloads (Last 12 months)13
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Xia L(2022)Group decision making under uncertain preferences: powered by AI, empowered by AIAnnals of the New York Academy of Sciences10.1111/nyas.147341511:1(22-39)Online publication date: 4-Feb-2022
https://doi.org/10.1111/nyas.14734
Lev OLu WTsang AZick YDignum FLomuscio AEndriss UNowé A(2021)Learning Cooperative Solution Concepts from Voting Behavior: A Case Study on the Israeli KnessetProceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3463952.3464163(1572-1574)Online publication date: 3-May-2021
https://dl.acm.org/doi/10.5555/3463952.3464163
Lev OPatel NViswanathan VZick YDignum FLomuscio AEndriss UNowé A(2021)The Price is (Probably) Right: Learning Market Equilibria from SamplesProceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3463952.3464043(755-763)Online publication date: 3-May-2021
https://dl.acm.org/doi/10.5555/3463952.3464043

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents