- A fair payoff distribution for myopic rational agents
- 2nd International Workshop on Computational Social Choice (COMSOC-2008), Liverpool, UK
- Book/source title
- Proceedings of the 2nd International Workshop on Computational Social Choice (COMSOC-2008)
- Pages (from-to)
- University of Liverpool, Department of Computer Science
- Document type
- Conference contribution
- Interfacultary Research Institutes
- Institute for Logic, Language and Computation (ILLC)
We consider the case of self-interested agents that are willing to form coalitions for increasing their individual rewards. We assume that each agent gets an individual payoff which depends on the coalition structure (CS) formed. We consider a CS to be stable if no individual agent has an incentive to change coalition from this CS. Stability is a desirable property of a CS: if agents form a stable CS, they do not spend further time and effort in selecting or changing CSs. When no stable CSs exist, rational agents will be changing coalitions forever unless some agents accept suboptimal results. When stable CSs exist, they may not be unique, and choosing one over the other will give an unfair advantage to some agents. In addition, it may not be possible to reach a stable CS from any CS using a sequence of myopic rational actions. We provide a payoff distribution scheme that is based on the expected utility of a rational myopic agent (an agent that changes coalitions to maximize immediate reward) given a probability distribution over the initial CS. To compute this expected utility, we model the coalition formation problem with a Markov chain. Agents share the utility from a social welfare maximizing CS proportionally to the expected utility of the agents, which guarantees that agents receive at least as much as their expected utility from myopic behavior. This ensures sufficient incentives for the agents to use our protocol.
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.