Problem 217 - An Introduction to Game Theory

Question

A committee has three members; there are five alternatives. One member prefers \(x\) to \(y\) to \(v\) to \(w\) to \(z\), another prefers \(z\) to \(x\) to \(v\) to \(w\) to \(y\), and the third prefers \(y\) to \(z\) to \(w\) to \(v\) to \(x\). Find the top cycle set, and for each alternative \(a\) in the set design a binary agenda for which \(a\) is the outcome of sophisticated voting. Convince yourself that for no binary agenda is the outcome of sophisticated voting outside the top cycle set.

Step-by-Step Solution

Answer

The top cycle set includes all alternatives that cannot be beaten by those outside the set. For each alternative in this set, structure pairwise comparisons to ensure it remains the final choice.

Step 1: Identify Preferences

List out the preferences of each committee member: - Member 1's order: \(x \to y \to v \to w \to z\) - Member 2's order: \(z \to x \to v \to w \to y\) - Member 3's order: \(y \to z \to w \to v \to x\)

Step 2: Determine Pairwise Comparisons

Compare each pair of alternatives and determine which ones are preferred more often. For example, compare \(x\) and \(y\): - In comparison \(x \text{ vs } y\): - Member 1 prefers \(x\) - Member 2 prefers \(y\) - Member 3 prefers \(y\) - Thus, \(y\) wins against \(x\)

Step 3: Construct a Dominance Graph

Create a directed graph where an arrow from one alternative to another signifies that the first is preferred over the second. For example, since \(y\) is preferred over \(x\) by majority, draw an arrow from \(y\) to \(x\). Repeat for all pairs.

Step 4: Identify the Top Cycle Set

The top cycle set includes all alternatives such that each alternative in the set is not beaten by any alternative outside the set. From the dominance graph, identify a set of nodes that form a cycle, indicating mutual dominance.

Step 5: Design Binary Agendas

For each alternative in the top cycle set, design a binary agenda (a sequence of pairwise comparisons) such that the alternative is the outcome. For example, structure the agenda so that alternative \(a\) is never eliminated in the comparison process.

Step 6: Confirm No Outsider Outcomes

Ensure that for no binary agenda, the outcome is an alternative outside the top cycle set, confirming that the top cycle set is comprehensive.

Key Concepts

top cycle set

The top cycle set is a critical concept in voting theory that refers to a set of alternatives each of which ‘defeats’ the others in a pairwise comparison. Let’s break this down. Imagine a committee voting on different choices. If Alternative A is preferred over Alternative B by a majority and Alternative B is preferred over Alternative C, then A is in the top cycle set if C is also defeated by A or connected in a cycle. Essentially, the top cycle set captures the most preferred elements when faced with binary choices against each other. In our example, we compared each alternative like this, and found a loop of preferences that ensures all are mutually dominant.

sophisticated voting

Sophisticated voting is a type of strategic voting where voters consider the likely outcomes of their votes rather than just their direct preferences. Voters anticipate how others will vote and might vote in a non-obvious way to ensure the best outcome aligned with their preferences occurs. In our committee example, even if a member prefers Alternative X, they might vote for Alternative Y if they think Y has a better chance of winning in subsequent rounds. This way, sophisticated voting models a more strategic approach to decision-making, aiming to influence the final outcome to be as favorable as possible relative to each voter’s preference.

binary agenda

A binary agenda structures the voting process into a series of pairwise comparisons between two alternatives at a time. Think of it like a knockout tournament where at each stage, one option is eliminated based on majority preference. To create a binary agenda where a specific alternative wins, we carefully arrange the sequence of comparisons to favor that result. In our committee example, we designed agendas such that each top cycle set alternative emerges as the winner. This planning involves ensuring that the alternative we want to win isn't pitted against a stronger opponent too early in the sequence. By organizing the comparisons wisely, sophisticated voting drives the desired alternative to victory.

pairwise comparison

Pairwise comparison is a straightforward method of voting where two alternatives are compared, and the one preferred by the majority moves on. In this method, every possible pair of alternatives is considered to see which is more popular. In the context of our committee example, each member’s order of preferences is crucial. We list out all pairs like (x vs. y) and determine the majority preference for each pair. This process helps us build a comprehensive picture of how each alternative stacks up against the others, spotlighting which options have the most overall support.

dominance graph

A dominance graph visually represents the preferences among alternatives using directed edges (arrows) to show which option is preferred over another. Each alternative is a node, and an arrow from one node to another indicates dominance. By examining this graph, you can see at a glance which alternatives are more favored. In our example, after conducting pairwise comparisons, we drew arrows to create the graph. This visual aid makes it easier to identify the top cycle set, showing which options prevail in direct comparisons and highlighting any cycles of mutual dominance among the alternatives.