Abstract | ||
---|---|---|
This paper explores a PAC (probably approximately correct) learning model in cooperative games. Specifically, we are given m random samples of coalitions and their values, taken from some unknown cooperative game; can we predict the values of unseen coalitions? We study the PAC learnability of several well-known classes of cooperative games, such as network flow games, threshold task games, and induced subgraph games. We also establish a novel connection between PAC learnability and core stability: for games that are efficiently learnable, it is possible to find payoff divisions that are likely to be stable using a polynomial number of samples. |
Year | Venue | Field |
---|---|---|
2015 | IJCAI | Flow network,Probably approximately correct learning,Polynomial,Induced subgraph,Artificial intelligence,Learnability,Mathematics,Stochastic game |
DocType | Volume | Citations |
Journal | abs/1505.00039 | 5 |
PageRank | References | Authors |
0.45 | 28 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Maria-Florina Balcan | 1 | 1445 | 105.01 |
Ariel D. Procaccia | 2 | 1875 | 148.20 |
Yair Zick | 3 | 143 | 22.98 |