This chapter focuses on forming coalitions analysis, based on the realm of cooperative game theory. The cooperative game states the situation that there are a number of agents with their own utility. Each agent can work their own to earn a certain amount of money. But also they can work with others, by cooperating, to generate some surplus income, over and above the amount that could be earned by individuals. Agents can form as a team to obtain a certain utility, which can be shared among coalition members. The game itself is completely silent about how this utility should be distributed among coalition members. In addition, the agreement of how to divide the ‘pay-check’ is done by coalition members.
Three key issues have been raised: coalition structure generation, solving the optimisation problem of each coalition to maximise social welfare, and how to divide the value of the solution for each coalition as fair as possible.
Some representative solutions have been reviewed for each key issue. However, this is NP-Hard problem as the complexity is exponential in the number of agents. It is likely impossible to give an optimal solution if the number of agents is high volume.
Thinking: just a simple real scenario can raise lots of key issuesL.
There are a number of papers written in the group on this topic - make sure you have a look at them at some point - most of them are on Nick Jennings' publications page. Otherwise, look at the work of Tuomas Sandholm as well. Go and talk to George Chalkiadakis (in the bay next to yours) or Talal Rahwan and Tomasz Michalak to get some ideas on what is going on in the field. I have also written some papers on this topic so check my publications list.
ReplyDelete