Preserving Condorcet Winners under Strategic Manipulation
Condorcet extensions — or Condorcet-consistent voting rules — have long held a prominent place in social choice theory. A Condorcet extension will return the Condorcet winner as the unique winner whenever such an alternative exists. However, this definition does not take into account possible strategic behaviour by the voters. A profile where all agents vote truthfully may have a Condorcet winner, but this alternative may not end up in the set of winners if agents are acting strategically. We examine how such strategic behaviour affects Condorcet consistency. This post is based on a joint paper with Ulle Endriss.
Definitions
I’ll first explain some concepts that may be familiar to those who work in (computational) social choice. If you fall into that category, you may want to skim this section and hop back in when there’s a bolded term you don’t recognise 😉
Our setting is voting: we have a set of alternatives, and a set of agents who each rank all the alternatives. A collection of these individual rankings is called a preference profile. What we study are voting rules — or social choice functions (SCFs)— which are functions that take as input a preference profile and output a set of winners. I will refer to some specific SCFs by name, and I’ll link to their definitions, but won’t get into that here. If you know them, great. If you don’t, it won’t affect your understanding very much.
A Condorcet winner is an alternative that beats every other alternative in a pairwise majority contest. The orange is a Condorcet winner in the image above. Condorcet winners are not guaranteed to exists, but A SCF that always returns a Condorcet winner when it does exists, is called a Condorcet extension. A SCF is resolute if it always returns a single winner, and irresolute if not.
- A SCF is weakly resolute if it sometimes returns a single winner even if there is not Condorcet winner.
- One SCF is a coarsening of another if the former always returns a superset of what the latter returns.
We study SCFs that are equivalent to tournament solutions. Strictly speaking tournament solutions map a directed graph to a subset of its vertices, but for the purposes of this blog post, let’s blur the lines a little. So let’s say that tournament solutions are in essence social choice functions that only need the majority graph, or the majority relation as input.
We also need to define agents’ preferences over sets of winners, as the rules we study are irresolute. Some of our results hold for any (reasonable) way of defining these preferences. For those results that are relative to a specific type of preference we speak only about Gärdenfors preferences.
What We Do
The main idea in our paper is the notion of a robust Condorcet extension. I like to think of it as follows: Suppose if our agents’ submit their true preferences that there will exist a Condorcet winner. A Condorcet extension guarantees that if the truthful rankings are submitted, the SCF will return the Condorcet winner as the only winning alternative. A robust Condorcet extension guarantees that the truthful rankings are submitted when there is a Condorcet winner — and will of course then return the Condorcet winner as the only winning alternative.
We find that no tournament-solution is robust under all preferences. We also find that weakly resolute rules fail robustness (for all preferences), and they are the only rules that do so.
The latter result tells us that weakly resolute rules — such as the well-known Copeland and Slater SCFs — cannot be robust under any preference. But of course, we can also read it in a positive light, any rule that is not weakly resolute will be robust for some preference. Now we only need to find those that are robust for some reasonable preference.
We show that if a Condorcet-consistent SCF is robust under Gärdenfors preferences, then all Condorcet-consistent coarsenings of it are as well. The minimal extending set is one example of a tournament solution that is robust under Gärdenfors preferences.
We can combine the above to show robustness for several well-known coarsenings of the minimal extending set — the Banks set and Top Cycle, for example, are both coarsenings of the minimal extending set.
To summarise: The number of winners returned by a SCF matters. Even weakly resolute rules fail robustness for all preferences, so robust rules will always return at least one tie (unless a Condorcet winner exists). But on the positive side, all rules that fail weak resoluteness will be robust for some preference, and we’ve seen that if we can show robustness for a relatively “decisive’’ SCF, we can extend the result to its coarsenings ☀️
