file.pdf (293.2 kB)
Download file

Learning Cooperative Games

Download (293.2 kB)
journal contribution
posted on 01.01.2015, 00:00 authored by Maria-Florina Balcan, Ariel D. Procaccia, Yair Zick

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




Usage metrics