3 December 2010, Computational Social Choice Seminar, Stéphane Airiau
The two main questions in coalition games are 1) what coalitions should form and 2) how to distribute the value of each coalition between its members. When a game is not superadditive, other coalition structures (CSs) may be more attractive than the grand coalition. For example, if the agents care about the total payoff generated by the entire society, CSs that maximize utilitarian social welfare are of interest. The search for such optimal CSs has been a very active area of research. Stability concepts have been defined for games with coalition structure, under the assumption that the agents agree first on a CS, and then the members of each coalition decide on how to share the value of their coalition. An agent can refer to the values of coalitions with agents outside of its current coalition to argue for a larger share of the coalition payoff. To use this approach, one can find the CS s* with optimal value and use one of these stability concepts for the game with s*. However, it may not be fair for some agents to form s* e.g., for those that form a singleton coalition and cannot benefit from collaboration with other agents. We explore the possibility of allowing side-payments across coalitions to improve the stability of an optimal CS. We adapt existing stability concepts and prove that some of them are non-empty under our proposed scheme.