Cooperation in competition: efficiently representing and reasoning about coalitional games
Cooperation is a central topic in multiagent systems research. In typical scenarios, agents, with only limited information and capabilities, must cooperate with others to achieve their goals. However, as agents are often only interested in their own welfare, cooperation takes place only if they gain by doing so. How benefits are divided, therefore, plays a crucial role in determining the success of partnerships. In my thesis, I study the problem of payoff division using coalitional game theory. This theory examines how to divide payoffs among agents so as to achieve fairness and stability. My contributions include both computational and conceptual advances of the theory. From a computational standpoint, I investigate how to efficiently find "good" division of payoffs. From a conceptual standpoint, I study how to extend the theory to capture characteristics of realistic multiagent systems. First, I propose two new schemes for representing coalitional games marginal contribution nets and multi attribute representation. I show that these schemes generalize past approaches, and reduce the space required to represent coalitional games by significant amounts. Further, they confer concomitant savings in computation by exploiting the structure exposed by these schemes, I develop algorithms that efficiently find fair and stable payoff divisions in these games. Second, I examine how to model updates and uncertainties in coalitional games. Both concepts are important for modeling multiagent systems in practice. For updates, I study how to efficiently update payoff divisions to maintain fairness or stability as the underlying game evolves. For uncertainties, I introduce Bayesian coalitional games which extend classical coalitional game theory to account for imperfect information, and I generalize the stability criterion of the core to the new setting.