11 Multiagent Systems

The third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including full text).

11.5 Group Decision Making

Often groups of people have to make decisions about what the group will do. It may seem that voting is a good way to determine what a group wants, and when there is a clear most-preferred choice, it is. However, there are major problems with voting when there is not a clear preferred choice, as shown in the following example.

Example 11.17.

Consider a purchasing agent that has to decide on a holiday destination for a group of people, based on their preference. Suppose there are three people, Alice, Bob and Cory, and three destinations, X, Y, and Z. Suppose the agents have the following preferences, where ≻ means strictly prefers:

  • •

    Alice: X≻Y≻Z

  • •

    Bob: Y≻Z≻X

  • •

    Cory: Z≻X≻Y

Given these preferences, in a pairwise vote, X≻Y because two out of the three prefer X to Y. Similarly, in the voting, Y≻Z and Z≻X. Thus, the preferences obtained by voting are not transitive. This example is known as the Condorcet paradox. Indeed, it is not clear what a group outcome should be in this case, because it is symmetric between the outcomes.

A social preference function gives a preference relation for a group. We would like a social preference function to depend on the preferences of the individuals in the group. It may seem that the Condorcet paradox is a problem unique to pairwise voting; however, the following result due to Arrow [1963] shows that such paradoxes occur with any social preference function.

Proposition 11.1 (Arrow’s impossibility theorem).

If there are three or more outcomes, the following properties cannot simultaneously hold for any social preference function:

  • •

    The social preference function is complete and transitive.

  • •

    Every individual preference that is complete and transitive is allowed.

  • •

    If every individual prefers outcome o1 to o2, the group prefers o1 to o2.

  • •

    The group preference between outcomes o1 and o2 depends only on the individual preferences on o1 and o2 and not on the individual preferences on other outcomes.

  • •

    No individual gets to unilaterally decide the outcome (nondictatorship).

When building an agent that takes the individual preferences and gives a social preference, you should be aware that you cannot have all of these intuitive and desirable properties. Rather than giving a group preference that has undesirable properties, it may be better to point out to the individuals how their preferences cannot be reconciled.