A fair payoff distribution for myopic rational agents

ABSTRACT

We consider the case of self-interested agents that are willing to form coalitions for increasing their individual rewards. We assume that each agent knows its individual payoff when a coalition structure (CS) is formed. We consider a CS to be stable if no individual agent has an incentive to change coalition from this CS. When no stable CSs exist, rational agents will be changing coalitions forever. When stable CSs exist, they may not be unique, and choosing one over the other may 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 propose 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 space of coalition structures for selecting the initial CS. To compute this expected utility, we model the coalition formation process by a Markov chain. We recommend that agents share the utility from a social welfare maximizing CS proportionally to the expected utility they would receive if all agents acted in a myopic rational fashion. This scheme guarantees that agents receive at least as much as their expected utility from myopic behavior, which ensures sufficient incentives for the agents to use our proposed payoff distribution.

REFERENCES

• 1: J. Alcalde and A. Romero-Medina. Coalition formation and stability. Soc Choice Welfare, 27(2):365--375, 2006.
• 2: S. Banerjee, H. Konishi, and T. Sönmez. Core in a simple coalition formation game. Soc Choice Welfare, 18(1):135--153, 2001.
• 3: A. Bogomolnaia and M. O. Jackson. The stability of hedonic coalition structures. Game Econ Behav, 38(2):201--230, 2002.
• 4: D. Ray and R. Vohra. A theory of endogenous coalition structures. Game Econ Behav, 26(2):286--336, 1999.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

Additional Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES

General Terms:
Algorithms, Economics, Theory

Keywords:
Markov chain, coalition structure, fairness, payoff distribution