Learning to identify winning coalitions in the PAC model
Ariel D. Procaccia, Jeffrey S. Rosenschein · 2006
We consider PAC learning of simple cooperative games, in which the coalitions are partitioned into "winning" and "losing" coalitions. We analyze the complexity of learning a suitable concept class via its Vapnik-Chervonenkis (VC) dimension, and provide an algorithm that learns this class. Furthermore, we study constrained simple games; we demonstrate that the VC dimension can be dramatically reduced when one allows only a single minimum winning coalition (even more so when this coalition has cardinality 1), whereas other interesting constraints do not significantly lower the dimension.