# Approval compatible voting rules

Zoi Terzopoulou, Jérôme Lang, William Zwicker

► To cite this version:

Zoi Terzopoulou, Jérôme Lang, William Zwicker. Approval compatible voting rules. Social Choice and Welfare, 2025, 10.1007/s00355-025-01588-9. hal-05393305

HAL Id: hal-05393305

https://hal.science/hal-05393305v1

Submitted on 4 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Approval Compatible Voting Rules

Zoi Terzopoulou¹, Jérôme Lang² and William S. Zwicker³

¹GATE, Université Jean-Monnet, Saint-Etienne, France.

²LAMSADE, Université Paris-Dauphine, Paris, France.

³Union College, NY, USA, and Murat Sertel Center for
Advanced Economic Studies, Bilgi University, Istanbul, Turkey.

Contributing authors: zoi.terzopoulou@cnrs.fr;
lang@lamsade.dauphine.fr; zwickerw@union.edu;

Abstract

Suppose voters are asked to submit approval ballots for a certain set of alternatives, with approval voting applied to determine a winning alternative. The same voters are then asked to report rankings over these alternatives, and some voting rule intended for ranked ballots is applied. If voters are sincere, can an approval winner possibly win this second election? Can an approval loser lose that election, or all approval co-winners be co-winners of the election? These questions give rise to three notions of approval compatibility for voting rules: positive, negative, and uniform positive approval compatibility (PAC, NAC, and UPAC). We find that NAC is a very weak notion and UPAC is a very strong one. Moreover, PAC, a stronger variant of it called OPAC, and a weaker variant of UPAC called FUPAC divide usual voting rules into four families: Condorcet-consistent rules satisfy all of them; K-approval rules for $K \ge 2$ satisfy none; plurality, plurality with runoff and STV satisfy OPAC but fail FUPAC; and Borda satisfies FUPAC and PAC but fails OPAC.

**Keywords:** social choice, voting, approval voting, rankings

# 1 Introduction

Consider a standard voting setting: A winner needs to be determined amongst a set of alternatives, by aggregating the ballots that are submitted by a group of voters. The aggregation is achieved through a (single-winner) voting rule.
## 2 *Approval Compatible Voting Rules*

However, the choice of the voting rule may change dramatically the output of the election. This is already the case when comparing two rules with a common input format. For instance, it is known that if we focus on voting rules that take rankings as input, various rules will give different outcomes (Taylor, 1995; Ratliff, 2001; Klamler, 2005).<fnref n="1" />

Now, comparing rules with different input formats is a more intricate question: How can we compare the outcomes given that the rules never take the same input? We investigate this question by focusing on the two most common input formats: *rankings* and *approvals*.<fnref n="2" /> The prominent rule in which each voter submits an approval ballot (a set of approved alternatives, with remaining alternatives disapproved) is of course *approval voting*, selecting as winners those alternatives that have received the most approvals from the voters (Brams and Fishburn, 1983). Approval voting is put in use by a number of committees and institutions worldwide, including the United Nations and the Society for Social Choice and Welfare.<fnref n="3" />

Although a ranking and an approval set express different types of information, they are correlated. Brams and Fishburn (1983) suggest that if a sincere voter is asked to report an approval ballot instead of a ranking ballot, she will construct a *compatible* approval set by fixing a certain alternative as a threshold, approving it along with all alternatives ranked above it, and disapproving all alternatives below it. Suppose, instead, that we start with the approval ballot of a sincere voter. Reasonably, her ranking ballot will then rank all approved alternatives above all disapproved ones—this is what we call a *compatible* ranking.

Thus, there are two symmetric ways of comparing the outcome under a given ranking-based voting rule to the outcome under approval voting:

* Given ranking ballots, we can ask which alternatives can possibly be approval winners if voters report compatible approval ballots.

* Given approval ballots, we can ask which alternatives can possibly be winners under the ranking-based rule if voters report compatible ranking ballots.

The first direction has been explored by Regenwetter and Grofman (1998), Regenwetter and Tsetlin (2004), and Barrot et al (2013), while some results of Saari yield contributions to this direction.<fnref n="4" /> Regenwetter and Grofman assume that each voter has a fixed ranking of the alternatives and use a probabilistic model to choose as an approval ballot a subset of alternatives at the top of

<footnote n="1">¹Note though that probabilistic studies based on real data (e.g., data from the elections of the American Psychological Association analysed by Regenwetter et al (2007) and data from an online survey analysed by Darmann et al (2019)) and as well as artificial data (Popov et al, 2014) suggest that the disagreement of voting rules is not very common in practice.</footnote>

<footnote n="2">²See also the work of Endriss et al (2009), who put forward a framework where the ballots have a different format than the underlying preferences of the voters.</footnote>

<footnote n="3">³Other single-winner rules with approval ballots as input have been considered as well (Alcalde-Unzu and Vorsatz, 2009; Laslier, 2012; Procaccia and Shah, 2015; Allouche et al, 2022).</footnote>

<footnote n="4">⁴For example Saari (2010) shows that for three alternatives, given a ranking profile and any scoring rule, there exists a compatible approval profile for which the *ranking* by approval score agrees with the ranking by the scores of the scoring rule applied to the ranking profile.</footnote>
that ranking. They provide a formula to calculate ranking winners (specifically under the Borda rule) from approval ballots. In an experiment based on an election of the Mathematical Association of America, they also show that the collective rankings of the alternatives induced by approval and by Borda scores tend to coincide, although theoretically they need not.

The work of Regenwetter and Tsetlin (2004) also hinges on the probabilistic model by Regenwetter and Grofman, and shows that the total approval scores of the alternatives can be approximated by the scores of a ranking-based positional scoring rule—moreover, if all sizes of approval ballots are equally frequent, then an approximation of the approval scores is achieved by the Borda rule (an analogous result was obtained by Gehrlein (1981), for rankings that follow the impartial culture distribution). Barrot et al (2013) assumed that the ranking ballots of the voters over alternatives are known, and address (mostly from a computational perspective) the question of which alternatives are approval (co)-winners in some compatible approval profile.

The second direction is the one we study here. Given sincere voters for whom we only know their approval ballots, multiple rankings can be compatible Which alternatives could possibly be the winners if we applied a certain ranking-based voting rule – in particular, which from among the approval winners? We might hope that approval winner(s) would be amongst the winners of our favourite ranking-based rule, were ranking ballots to be reported instead. Interestingly, this is not such a trivial property; some simple ranking-based rules violate it.

Note that our study is complementary to foundational questions about the nature of approval preferences, of ranking preferences, and of how they compare—we do not provide answers to those questions. Further, our contribution does not rely on the answers. Rather, it is enough to take an agnostic or neutral position on the matter of what preferences consist of. Preferences are complex, with multiple aspects, and are unlikely to be fully plumbed by using any known ballot form to elicit voter responses. Nonetheless we do have elections, some with ballots that are approval sets, and others with rankings. Moreover, the assumption that sincere voters would rank all approved candidates over all disapproved candidates seems to be consistent with any reasonable assumption about the nature of the preferences that lie behind voters’ choices of approval and ranking ballots.

More concretely, we evaluate the approval compatibility of voting rules according to several compatibility notions. These are divided between *positive* compatibility notions, which, informally, say that approval co-winners are also winners in a compatible ranking election under that rule; and negative notions, which say that approval losers are also losers in a compatible ranking election.

We study approval compatibility for a number of well-established voting rules taking rankings as input: the plurality and the Borda rules, K-approval rules, Single Transferable Vote (STV), and Condorcet-consistent rules. It turns out that negative compatibility properties are weak enough to be satisfied by most of these rules. Among positive properties, three are key: *positive approval*
## 4 Approval Compatible Voting Rules

compatibility (PAC), satisfied by rule $r$ if each approval co-winner can also be made a winner in a compatible ranking election under $r$; the stronger notion of obvious positive approval compatibility (OPAC), satisfied by $r$ if each approval co-winner can also be made a winner under $r$ in an obvious way by ranking it first whenever a voter approves it, and rank it higher than any other non-approved alternative whenever a voter does not approve it; and finally, fractional uniform positive approval compatibility (FUPAC), satisfied if all approval co-winners are simultaneously co-winners under $r$ in some ranking election that is compatible with some multiple of the original approval profile.

Although we consider other properties, these three suffice to cluster ranking rules in four groups: Condorcet-consistent rules satisfies all of them; plurality and its sequential variants—plurality with runoff and STV—satisfy OPAC (and PAC) but not FUPAC; Borda satisfies PAC and FUPAC, but not OPAC; finally, $K$-approval for $K \ge 2$ satisfies none.

This paper proceeds as follows. In Section 2 we present our basic framework, define voting with ranking ballots and with approval ballots, and formally introduce all our notions of approval compatibility. In Section 3 we state and prove our results with respect to the approval compatibility of ranking-based rules, and in Section 4 we conclude.

# 2 Model

In this section we present our formal model together with the necessary notation and terminology.

## 2.1 Preliminaries

Consider a finite group of voters $N$, with $|N| = n \ge 1$. Given a finite set of alternatives $X$, with $|X| = m \ge 3$, an approval ballot of a voter $i \in N$ is a subset $A_i \subseteq X$, denoting those alternatives that she approves. An approval profile is a vector $\mathbf{A} = \langle A_1, \dots, A_n \rangle$ of approval ballots for all voters in the group $N$. For our technical proofs, the following definitions will be handy:

* $A(x^+y^+) = \{i \in N \mid x, y \in A_i\}$;

* $A(x^+y^-) = \{i \in N \mid x \in A_i, y \notin A_i\}$;

* $A(x^-y^+) = \{i \in N \mid y \in A_i, x \notin A_i\}$;

* $A(x^-y^-) = \{i \in N \mid x, y \notin A_i\}$.

The set $\text{App}(\mathbf{A}) \subseteq X$ contains exactly those alternatives that receive the most approval votes in the profile $\mathbf{A}$, i.e., the winners of classical approval voting. Writing $\text{App}_{\mathbf{A}}(x) = |\{i \in N \mid x \in A_i\}|$, we have the following:

$$ \text{App}(\mathbf{A}) = \underset{x \in X}{\operatorname{argmax}} \text{App}_{\mathbf{A}}(x) $$

Note the following elementary lemma:
**Lemma 1** If a is an approval winner for A, then for any $x \in X$, $|A(a^+x^-)| \ge |A(a^-x^+)|$, with equality if and only if x is an approval winner too.

*Proof* App<sub>A</sub>(a) = |A(a<sup>+</sup>x<sup>-</sup>)| + |A(a<sup>+</sup>x<sup>+</sup>)| and App<sub>A</sub>(x) = |A(a<sup>-</sup>x<sup>+</sup>)| + |A(a<sup>+</sup>x<sup>+</sup>)|. Since a is an approval winner, App<sub>A</sub>(a) = |A(a<sup>+</sup>x<sup>-</sup>)| + |A(a<sup>+</sup>x<sup>+</sup>)| ≥ App<sub>A</sub>(x) = |A(a<sup>-</sup>x<sup>+</sup>)| + |A(a<sup>+</sup>x<sup>+</sup>)|, therefore, |A(a<sup>+</sup>x<sup>-</sup>)| ≥ |A(a<sup>-</sup>x<sup>+</sup>)|. If |A(a<sup>+</sup>x<sup>-</sup>)| = |A(a<sup>-</sup>x<sup>+</sup>)| then App<sub>A</sub>(x) = App<sub>A</sub>(a): x is an approval winner too. □

Approval voting is homogeneous, in the sense that replicating each ballot in a profile an equal number of times will not affect the approval winners. Formally, for any positive integer $k$ and any approval profile with $n$ voters $A = (A_1, \dots, A_n)$, $kA$ denotes the approval profile with $kn$ voters, composed of $k$ copies of $A_i$ for each $i \in N$. For every profile $A$, we have the following:

$$ \mathrm{App}(A) = \mathrm{App}(kA), \text{ for every positive integer } k $$

Next, we denote a ranking over all alternatives in $X$ as $x_1x_2\dots x_m$; a corresponding ranking ballot $V_i$ of voter $i$ captures that alternative $x_1$ is ranked first by that voter, $x_2$ is ranked second, and so on, with $x_m$ being the least preferred. If alternative $x$ appears before alternative $y$ in a ranking $V$, we write $(x, y) \in V$. A ranking profile is a collection $V = (V_1, \dots, V_n)$ of rankings over $X$, for all voters in $N$.

We say that $A$ and $V$ are compatible (denoted by $V \sim A$) if there exist $n$ integers $k_1, \dots, k_n$ such that $A_i$ is the set of the top $k_i$ alternatives in $V_i$, for all $i$. Intuitively, each $V_i$ can be thought of as a ranking ballot that a sincere voter with approval ballot $A_i$ may possibly report in a ranking election: one for which all approved alternatives are ranked above the others.

**Example 1** For an approval ballot $A = \{x_1, x_2\}$ with $X = \{x_1, x_2, x_3, x_4\}$, the four ranking ballots compatible with $A$ are $V'_i = x_1x_2x_3x_4$, $V''_i = x_2x_1x_3x_4$, $V'''_i = x_1x_2x_4x_3$, and $V''''_i = x_2x_1x_4x_3$. △

In determining winners for an election with ranking ballots, we allow our voting rule $r$ to be irresolute: $r$ is a function that maps any given profile $V$ to some non-empty subset of $X$. We start by recalling positional scoring rules, which assign points to alternatives depending on their positions in a voter's rankings, and elect those alternatives with the largest total score across all voters. Formally, a positional scoring rule $r_s$ is induced by a positional scoring vector $s = (s_1, s_2, \dots, s_m)$ with $s_k \ge s_{k+1}$ for all $k \in \{1, \dots, m\}$, and $s_1 > s_m$. When voter $i$ ranks alternative $x$ in the $j^{th}$ position, score $s(V_i, x) = s_j$ is assigned to it. We write $s_V(x_i) = \sum_{j \in N} s(V_i, x)$ (simplified by $s(x)$ when the profile to which we refer is clear) for the total score $x$ receives in $V$. Given a
6 *Approval Compatible Voting Rules*

ranking profile $\mathbf{V}$, we have the following definition:

$$
r_s(\mathbf{V}) = \underset{x \in X}{\operatorname{argmax}} s_{\mathbf{V}}(x)
$$

Note that a scoring vector $s = (s_1, s_2, \dots, s_m)$ induces the same rule as any affine transformation of it $s' = (s'_1, s'_2, \dots, s'_m)$ such that $s'_j = \alpha s_j + \beta$ with $\alpha > 0, \beta \in \mathbb{R}$ for all $j \in \{1, \dots, m\}$. For reasons of simplicity, we will often use the normalised version of a scoring vector with $s_1 = 1$ and $s_m = 0$.

The most famous positional scoring rule for voting with ranking ballots probably is the *Borda rule* (de Borda, 1784), induced by the scoring vector $(m-1, m-2, \dots, 0)$. We write $B_{\mathbf{V}}(x)$ (or $B(x)$ when it is clear to which profile we refer) for the Borda score of the alternative $x$ in the profile $\mathbf{V}$. Similarly, $B_{V_i}(x)$ is the Borda score assigned to $x$ only by ranking $V_i$. The *k-approval rules* also are popular positional scoring rules, with the following scoring vectors:

$$
s^{k-approval} = (\underbrace{1, \dots, 1}_{k}, \underbrace{0, \dots, 0}_{m-k}), \text{ for } 1 \le k \le m
$$

For $k = 1$, the corresponding approval rule is known as the *plurality rule*, while for $k = m - 1$ the corresponding approval rule is called the *antiplurality rule*.

Positional scoring rules are often contrasted with *Condorcet-consistent*
rules. To define this concept, let us say that alternative *x* is *preferred by a
majority* to alternative *y* in the profile **V**, writing *x* ><sub>**V**</sub><sup>*maj*</sup> *y*, if strictly more
voters rank *x* above *y* than *y* above *x*. We also write *maj*(*x*, *y*) = |{*i* ∈ *N* | (*x*, *y*) ∈ *V*<sub>i</sub>}| − |{*i* ∈ *N* | (*y*, *x*) ∈ *V*<sub>i</sub>}| for the *majority margin* of *x* over *y* in
the profile **V** = ⟨*V*<sub>1</sub>, ..., *V*<sub>n</sub>⟩.

We call an alternative *x* the *Condorcet winner* of a profile **V** if for every
other alternative *y* ≠ *x* it holds that *x* ><sub>**V**</sub><sup>*maj*</sup> *y*. A *Condorcet-consistent*
rule guarantees that if alternative *x* is the *Condorcet winner* of a profile **V**,
then this will be the only elected alternative. The *Copeland rule* and the
*maximin rule*, which we present below, are specific *Condorcet-consistent rules*.

We define the Copeland score of an alternative *x* in a profile **V** as follows:

$$
\text{Copeland}(x) = |\{y \in X \mid x >_{V}^{maj} y\}| - |\{y \in X \mid y >_{V}^{maj} x\}|
$$

Then, the winners of the Copeland rule are those alternatives in $X$ with the highest Copeland score. The *maximin rule* on the other hand, elects those alternatives that maximise the minimum majority margin against all other alternatives, i.e., the alternatives in the following set:

$$
\operatorname{argmax}_{x \in X} \min_{y \in X \setminus \{x\}} \operatorname{maj}(x, y)
$$

Lastly, two voting rules that are often used in political elections are *Sin-
gle Transferable Vote* (STV) and *plurality with runoff* (Hare, 1859). Here
we explain the irresolute, parallel universe tie-breaking version of these rules
(Conitzer et al, 2009). STV proceeds in multiple rounds. In every round, the alternative ranked first by the smallest number of voters is eliminated (if there is more than one such alternative, each of them is eliminated in a different parallel universe), leaving each voter's ranking shorter by one. Every alternative that survives after $m-1$ rounds in at least one parallel universe is declared a winner. Plurality with runoff proceeds in two rounds. In the first round, the two alternatives ranked first by the largest number of voters are selected for the second round, where the winning alternative is chosen by the majority rule (if more than two alternatives are ranked first by the same, largest number of voters in the first round, then a different pair passes to the second round in each parallel universe).<fnref n="5" />

## 2.2 Definitions of Approval Compatibility

In this section we introduce different notions of approval compatibility, starting from the *positive* ones, which concern approval winners, and continuing with the *negative* ones, which focus on approval losers.

If the goal is to make *one* approval winner be the winner in some compatible ranking profile, then the notion that needs to be satisfied is what we call *positive approval compatibility*. If instead we want to make *all* approval winners simultaneously be the winners in some compatible ranking profile, then we need to check the notion of *uniform positive approval compatibility*. The latter will be found to be the most demanding notion from those we consider.

Note that there is an obvious way to promote an approval winner $x$ to make it win a ranking election, while preserving compatibility between approval and ranking profiles: rank $x$ first whenever a voter approves it, and rank $x$ higher than all other non-approved alternatives otherwise. We allow the way other approved (respectively, disapproved) alternatives are ranked among themselves to vary freely. If every such construction leads to an approval winner being a winner of a ranking-based rule, we say that the rule satisfies *obvious positive approval compatibility*.

Formally, given $x \in X$, we call $V = \{V_1, ..., V_n\} \sim A$ a *standardised ranking profile* for $x$ based on the approval profile $A = \{A_1, ..., A_n\}$ if the following two conditions hold:

1. For every voter $i$ such that $x \in A_i$, $x$ is ranked first in $V_i$.

2. For every voter $j$ such that $x \notin A_i$, $x$ is ranked in position $|A_j| + 1$ in $V_i$, right below all alternatives of $A_j$.

For example, if $X = \{a, b, c, d, e\}$ and $A = \{\{a, b\}, \{b, c\}, \{d, e\}\}$ then $\langle bacde, bcade, debca \rangle$ and $\langle baedc, bcead, edbac \rangle$ are standardised for $b$. If every such construction guarantees that the selected approval winner will be the winner of the corresponding ranking election, *obvious positive approval compatibility* holds.

<footnote n="5">⁵In reality, according to plurality with runoff and also to STV, an alternative ranked first by a majority of voters in the first round would win, with no need to proceed to a second round.</footnote>
8 *Approval Compatible Voting Rules*

**Definition 1** *The rule r satisfies:*

*   **positive approval compatibility (PAC)** if for every approval profile **A** and $x \in App(\mathbf{A})$ there exists a ranking profile **V** ~ **A** such that $x \in r(\mathbf{V})$;

*   **uniform positive approval compatibility (UPAC)** if for every approval profile **A** there exists a ranking profile **V** ~ **A** such that $App(\mathbf{A}) \subseteq r(\mathbf{V})$;

*   **obvious positive approval compatibility (OPAC)** if for every approval profile **A**, $x \in App(\mathbf{A})$, and standardised ranking profile $\mathbf{V}_x \sim \mathbf{A}$ it holds that $x \in r(\mathbf{V}_x)$.

Let us get accustomed to the above notions via Examples 2, 3 and 4, in all of which we take $X = \{x_1, x_2, x_3\}$.

**Example 2** Consider the positional scoring rule with scoring vector (1, 2/3, 0), and the following profile, in which all alternatives $x_1, x_2$, and $x_3$ are approval winners:

$$ \mathbf{A} = \langle \{x_1\}, \{x_2, x_3\} \rangle $$

In every compatible ranking profile, alternative $x_1$ will receive exactly 1 point in total: the first voter will rank it in the first position of her ranking and the second voter will rank it in the last position. Now, alternatives $x_2$ and $x_3$ will receive at least 2/3 points each by the second voter. But one of them has to also be ranked second by the first voter, which will result in at least 4/3 > 1 points in total. This means that the two voters have no way to make the approval winner $x_1$ win under a compatible ranking profile, and hence that PAC is violated. Note that this example strongly depends on the specific scoring vector we chose. $\Delta$

**Example 3** Consider the plurality rule, and the following approval profile, in which $x_1$ and $x_2$ are the approval winners:

$$ \mathbf{A} = \langle \{x_1, x_2\}, \{x_2\}, \{x_1, x_3\} \rangle $$

Suppose we want to make the approval winner $x_1$ win under a compatible ranking profile. Then everyone who approved $x_1$ (i.e., the first and the third voters) can place it on top of their rankings, giving it two plurality points. The remaining positions of the rankings can be completed arbitrarily. As no other alternative can receive more than one plurality point, $x_1$ will be a plurality winner. This is the idea behind OPAC for Plurality: any standardised ranking profile for $x_1$ can be used for $x_1$ to win the Plurality election (see Theorem 1 for the general result). $\Delta$

**Example 4** Consider the plurality rule, and take the simple 1-voter profile, where all alternatives are approval winners:

$$ \mathbf{A} = \langle \{x_1, x_2, x_3\} \rangle $$

Clearly, it is impossible for the voter to provide a compatible ranking profile where all approval winners will be plurality winners: any such profile will only have one winner. This indicates that the plurality rule violates UPAC. This argument shows in Section 3 that every rule satisfying the axiom of faithfulness violates UPAC. $\Delta$
Certain violations of positive approval compatibility arise from numerical indivisibilities that could be avoided if we were allowed, for example, to replace a single approval ballot by a half-ballot of one compatible ranking and a second half-ballot with a different compatible ranking. To avoid formal reference to fractional ballots, we instead circumvent such violations by allowing replacement of the given approval profile with a suitable *multiple* of that profile. The equivalence relies on the homogeneity property of approval voting. Formally, under any homogeneous rule the election outcome will not change if we repeat each ballot *k* times; loosely speaking, such rules pay attention only to the fraction of the total electorate (rather than to the absolute number of voters) reporting each ballot. For example, we will see in Section 3 that although the Borda rule violates UPAC, it satisfies FUPAC, the weaker, fractional version. If a rule fails approval compatibility even when such multiples are allowed, this indicates a more fundamental failure.

**Definition 2** *The rule* *r* *satisfies*:

• **fractional positive approval compatibility (FPAC)** if for every approval profile **A** and $x \in App(\mathbf{A})$ there exists a positive integer *k* and a ranking profile **V** ~ *k***A** such that $x \in r(\mathbf{V})$;

• **fractional uniform positive approval compatibility (FUPAC)** if for every approval profile **A** there exists a positive integer *k* and a ranking profile **V** ~ *k***A** such that $App(\mathbf{A}) \subseteq r(\mathbf{V})$.

We next consider analogous notions of negative approval compatibility, which ensure that an approval loser (or multiple losers) will not win under a ranking rule. While *negative approval compatibility* is satisfied if each approval loser can also be forced to lose in a compatible ranking election, *uniform negative approval compatibility* ensures that all approval losers will simultaneously be losing under the ranking-based rule (equivalently, no approval loser will be amongst the winners of the ranking election).

**Definition 3** *The rule* *r* *satisfies*:

• **negative approval compatibility (NAC)** if for every approval profile **A** and *x* ∉ App(**A**) there exists a ranking profile **V** ~ **A** such that *x* ∉ r(**V**);

• **uniform negative approval compatibility (UNAC)** if for every approval profile **A** there exists a ranking profile **V** ~ **A** such that r(**V**) ⊆ App(**A**).

**Definition 4** *The rule* *r* *satisfies*:

• **fractional negative approval compatibility (FNAC)** if for every approval profile **A** and *x* ∉ App(**A**) there exists a positive integer *k* and a ranking profile **V** ~ *k***A** such that *x* ∉ r(**V**);
10 *Approval Compatible Voting Rules*

• *fractional uniform negative approval compatibility (FUNAC) if for*
every approval profile **A** there exists a positive integer *k* and a ranking
profile **V** ~ *k***A** such that *r(**V**)* ⊆ App(**A**).

So far, we have examined positive and negative notions of approval compat-
ibility separately, as targeting different attributes of the voting rule in question.
Consider, however, the “non-unanimous loser” voting rule *r* that elects as a
co-winner every alternative not ranked last by all voters. This rule clearly sat-
isfies UPAC, our strongest positive approval compatibility property. However,
by choosing winners so indiscriminately it often also forces approval losers to
win ranking elections, violating NAC. Such examples suggest that when a rule
satisfies *either* positive or negative approval compatibility, we should be wary—
this satisfaction may be due to some extreme behavior. Only the satisfaction
of both properties together should carry a positive normative message.

With this idea in mind, we define one last notion, which separates winners
from losers; it requires that the election of an approval winner never forces the
rule to simultaneously elect some approval loser: *cautious approval compatibil-
ity* demands that any single approval winner can be made a co-winner of the
ranking election without also electing any approval losers.

**Definition 5** The rule *r* satisfies:

• *cautious approval compatibility (CAC) if for every approval profile* **A**
*and* *x* ∈ App(**A**) *there exists a ranking profile* **V** ~ **A** *such that* x ∈ r(**V**)
*and* r(**V**) ⊆ App(**A**);

• *obvious cautious approval compatibility (OCAC) if for every approval profile* **A**, *x* ∈ App(**A**), *and standardised ranking profile* **V**<sub>*x*</sub> ~ **A** *it holds* that *x* ∈ r(**V**<sub>*x*</sub>) *and* r(**V**<sub>*x*</sub>) ⊆ App(**A**).

Figure 1 depicts the logical relations between our notions of approval compatibility. Of course, other notions of approval compatibility could be considered, but at least some of these alternatives lead nowhere. For example, we will say that a voting rule *r* satisfies *perfect approval compatibility* if it is possible to make any approval winner a ranking winner, and impossible to make any approval loser a ranking winner. Equivalently, it satisfies *PAC* and for all profiles **A** and **V** ~ **A** we have that *r(V)* ⊆ App(**A**). This is a stronger notion than cautious approval compatibility. In fact, it is far too strong—no voting rule *r* satisfies it.

To see this, consider two approval profiles **A** = ⟨{*x*}, {*x*, *y*}⟩ and **A'** = ⟨{*x*, *y*}, {*y*}⟩. Let **V** be a ranking on *X* with *x* on top, then *y*, and all other alternatives ranked below in an arbitrary way; let **V'** be a ranking on *X* with *y* on top, then *x*, and all other alternatives ranked below in an arbitrary way. Consider the ranking profile **V** = ⟨**V**, **V'**⟩. For *r* to be perfectly approval compatible, only alternative *x* can win on **V**, since **V** ~ **A** and *x* is the only
<figure><img src="image_2.png" /><figcaption>**Fig. 1:** Logical relations between different notions of approval compatibility. An arrow points from the logically stronger to the logically weaker notion.</figcaption></figure>

<table><caption>**Table 1:** Summary of results. “✓” indicates satisfaction and “✗” indicates violation of the given property. K-approval refers to $K \ge 2$.</caption><thead><tr><th></th><th>OCAC</th><th>OPAC</th><th>CAC</th><th>PAC</th><th>FPAC</th><th>UPAC</th><th>FUPAC</th><th>NAC</th><th>FNAC</th><th>UNAC</th><th>FUNAC</th></tr></thead><tbody><tr><td>Plurality</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>K-approval</td><td>✗</td><td>✗</td><td>✗</td><td>✗</td><td>✗</td><td>✗</td><td>✗</td><td>✗</td><td>✓</td><td>✓</td><td>✗</td><td>✗</td></tr><tr><td>Borda</td><td>✗</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>STV</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>Plur. runoff</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>Cond.-cons.</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr></tbody></table>

approval winner on App($A$). But also, only $y$ can win on $V$, since $V \sim A'$ and $y$ is the only approval winner on App($A'$). This is impossible.

We make no claim that all potential additions to our list of approval compatibility notions can be dismissed as quickly as perfect approval compatibility; other attractive properties may well exist. Indeed it was a challenge for us to select, from a great variety of possible variants, those most interesting and central. Yet we believe that the notions explored in this paper provide a good starting point.

# 3 Results

Here we present our results on the satisfaction of different notions of approval compatibility by various voting rules, with Table 1 providing a summary.

The results carry several key messages. First, compatibility properties can be clustered in three groups: those that are very easy to satisfy, those that are
12 *Approval Compatible Voting Rules*

extremely strong and tend to exclude all rules, and those that are in between.<fnref n="6" />
The first group contains negative approval compatibility (NAC) and fractional
negative approval compatibility (FNAC); they are satisfied by all the rules we
considered. The second group contains uniform positive approval compatibility
(UPAC); it is satisfied by none of the rules we considered. All other properties
are in the third group and are more interesting: they are of mild strength,
being satisfied by some certain common voting rules and violated by others. We
also notice that positive approval-compatibility properties are globally more
interesting, since most negative properties seem to be easy to satisfy.

Second, and perhaps even more interestingly, the voting rules them-
selves can be clustered into several groups, according to the properties of
the third group they satisfy. We can distinguish four families of rules. The
*Condorcet family* contains all Condorcet-consistent rules, which satisfy all
middle-strength axioms. The *plurality family* contains plurality and its sequen-
tial variants (plurality with runoff, STV), which satisfy all the middle-strength
axioms except fractional uniform positive approval compatibility (FUPAC). A
third group contains only Borda, which satisfies FUPAC (unlike rules of the
plurality family) but violates obvious positive approval compatibility (OPAC)
and obvious cautious approval compatibility (OCAC) (also unlike rules of the
plurality family). The last group contains *K*-approval for all $K \ge 2$ (includ-
ing antiplurality), but also some positional scoring rules that are closer to
antiplurality than to plurality.

Note that the class of positional scoring rules has been seen as rather
homogeneous when it comes to the more classical voting axioms: all such
rules satisfy reinforcement, participation, and monotonicity, while violating
Condorcet-consistency and clone-proofness. Yet rules within this class exhibit
a wide range of behaviour when it comes to approval compatibility, with plural-
ity satisfying almost all such properties, and *K*-approval for $K \ge 2$ satisfying
almost none. Indeed, the clustering now runs transversal to the family, with
plurality lumped together with both STV and plurality with runoff.

**3.1 Positive Approval Compatibility**

We first focus on PAC and FPAC. We show that the plurality rule and the
Borda rule, as well as STV, plurality with runoff, and all Condorcet-consistent
rules, satisfy both these notions, while *K*-approval rules for *K* ≥ 2 do not
satisfy either.<fnref n="7" /> The latter observation follows from a necessary condition we
provide for FPAC. Notably, plurality, STV, plurality with runoff, and all
Condorcet-consistent rules also satisfy the stronger notion of OPAC, but the
Borda rule and all other *K*-approval rules violate it.

<footnote n="6">⁶Such trichotomies are classical in social choice. See in particular Zwicker (2016) for a similar classification of classical axioms for voting rules.</footnote>

<footnote n="7">⁷A reasonable conjecture here would be that what distinguishes positional scoring rules that satisfy PAC from those that do not is the Pareto condition: Borda and plurality are Pareto-efficient, while *K*-approval rules for *K* ≥ 2 are not. However, there are positional scoring rules, like the one with scoring vector (6, 5, 1, 0) when *m* = 4, that are Pareto-efficient yet violate PAC.</footnote>
**Theorem 1** *The following two statements hold:*

(a) *The plurality rule satisfies OCAC (thus also CAC, OPAC, PAC and FPAC).*

(b) *Any positional scoring rule other than plurality violates OPAC (thus also OCAC).*

*Proof* For (a), consider an approval profile **A** and an alternative *x* ∈ X such that *x* ∈ App(**A**). Suppose that *x* is approved by *k* voters in **A**, and that all these voters rank her first in a standardised profile **V***<sub>*x*</sub> ∼ **A**. Clearly no alternative can have more than *k* first positions in **V***<sub>*x*</sub>, and every alternative *y* ∉ App(**A**) will have strictly fewer than *k* first positions in **V***<sub>*x*</sub>. This means that *x* will be amongst the plurality winners and no approval loser will be a plurality winner. So OCAC holds for plurality.

For (b), let $s = (s_1, \dots, s_m)$ be a scoring vector with $s_2 > s_m$. Take the approval profile $\mathbf{A} = \langle\{a\}, \{x_2, \dots, x_m\}\rangle$ and the following standardised ranking profile for $a$: $V_a = \langle ax_1 \cdots x_{m-1}, x_1x_2 \cdots x_{m-1}a \rangle \sim \mathbf{A}$. Alternative $a$ is an approval winner in $\mathbf{A}$, but $x$ is the unique $F_s$ winner in $V_a$. This means that $F_s$ fails OPAC. $\square$

Theorem 1 tells that the plurality rule is the only scoring rule that satisfies OPAC. However, the Borda rule is a rather special case; while it fails OPAC and OCAC, it satisfies their weaker cousins PAC and CAC. We show this by constructing a particular type of standardised ranking profile. Observe that if there is a profile **V** ~ **A** for which *x* is a Borda winner, then there is a standardised profile **V'* ~ **A** for which *x* is a Borda winner: moving *x* in each **V***<sub>*j*</sub> to the top position (if *x* ∈ **A***<sub>*j*</sub>) or to the position |**A***<sub>*j*</sub>| + 1 (if *x* ∉ **A***<sub>*j*</sub>), leaving unchanged the relative position of other alternatives, can only increase the score of *x* and decrease the score of other alternatives.

**Theorem 2** *The Borda rule satisfies CAC (and thus also PAC and FPAC).*

*Proof* Consider an approval profile **A** for a set *X* containing *m* alternatives, and let *a* ∈ App(**A**) be an approval winner. We will show that there exists a compatible (and standardised) ranking profile **V** where *a* is a Borda winner, and every alternative *x* ∉ App(**A**) is a Borda loser. Given any set *S* ⊆ *X* of alternatives with *a* ∈ *S*, we define the approval profile **A**<sub>S</sub> = ⟨*A*₁ ∩ *S*, ..., *A*<sub>*n*</sub> ∩ *S*⟩ to be the restriction of **A** to *S*. Note that because *a* ∈ *S*, it is true that App(**A**<sub>S</sub>) = App(**A**) ∩ *S*. We will show, by induction on the number of alternatives in *S*, that for each such set *S* there exists a standardised ranking profile **V** ~ **A**<sub>S</sub> satisfying that *a* is a Borda winner, and that for every alternative *x* ∈ *S*, if *x* ∉ App(**A**) then *x* is a Borda loser. Taking *S* = *X* then completes the proof.

First, suppose that |S| = 2, so that for some alternative x ∈ X, we have that A_i ⊆ {a, x} for all voters i ∈ N. Let V ~ AS be a standardised ranking profile with respect to a. Since a is an approval winner, by Lemma 1, |A(a^+x^-)| ≥ |A(a^-x^+)|, with equality if and only if x is an approval winner too. Now, V ~ AS contains |A(x^+a^-)| votes of the form {x, a} and at least |A(a^+x^-)| votes of the form {a, x}. Therefore, a is a Borda winner in V, and x can only be a Borda winner in V if it is an approval co-winner in AS. See Figure 4 for an example.
14 *Approval Compatible Voting Rules*

<table><caption>**Fig. 2:** Treatment of *a* and of *x* by an individual voter *i*.</caption><thead><tr><th><i>i</i></th><th><i>A</i>(<i>x</i><sup>+</sup><i>a</i><sup>-</sup>)</th><th><i>A</i>(<i>x</i><sup>+</sup><i>a</i><sup>+</sup>)</th><th><i>A</i>(<i>x</i><sup>-</sup><i>a</i><sup>-</sup>)</th><th><i>A</i>(<i>x</i><sup>-</sup><i>a</i><sup>+</sup>)</th></tr></thead><tbody><tr><td>rank of <i>a</i></td><td><i>α</i><sub><i>i</i></sub> + 2</td><td>1</td><td><i>α</i><sub><i>i</i></sub> + 1</td><td>1</td></tr><tr><td>rank of <i>x</i></td><td><i>α</i><sub><i>i</i></sub> + 1</td><td>2</td><td><i>α</i><sub><i>i</i></sub> + 2</td><td><i>α</i><sub><i>i</i></sub> + 1 (<b>≥</b> 2)</td></tr><tr><td><i>B</i><sub><i>V</i><sub><i>i</i></sub></sub>(<i>a</i>) &minus; <i>B</i><sub><i>V</i><sub><i>i</i></sub></sub>(<i>x</i>)</td><td>&minus;1</td><td>1</td><td>1</td><td><i>α</i><sub><i>i</i></sub> (<b>≥</b> 1)</td></tr></tbody></table>

Next, assume that our hypothesis holds for each set $S \subset X$ with $|S| = k < m$. For our induction step, take any $S' \subset X$ with $|S'| = k + 1 \le m$. Then $S' = S \cup \{x\}$ for some $S \subset X$ with $|S| = k$ and some $x \in X \setminus S$. Using the standardised profile $V$ that the inductive hypothesis provides for $S$, we can construct a new standardised profile $V' \sim AS'$, ensuring that the relative order of all alternatives in $S$ remains the same between $V_i$ and $V'_i$, for every $i \in N$. We also construct $V'$ so that the following two conditions hold:

1. For every $i \in A(x^+a^-)$, we rank $x$ as low as possible in $V_i$, without violating approval compatibility.

2. For every $i \in N \setminus A(x^+a^-)$, we rank $x$ as high as possible in $V_i$, without violating approval compatibility or the definition of a standardised profile.

An example of the above construction can be found in Figure 4.

Let $\alpha_i = |A_i \cap S|$. If $\alpha_i = 0$, then $A_i \cap S = \emptyset$. Because $a \in S$, we necessarily have $a \notin A_i$, which implies that $i \notin A(x^-a^+)$. For each $i \in A(x^-a^+)$ we have $\alpha_i \ge 1$. The table in Figure 2 indicates the rank of $a$ and $x$ in the four types of votes of $V'$, as well as the differences in contributions of voter $i$ to the Borda scores of $a$ and $x$.

Assume $x$ is an approval loser in $AS'$. As $a$ is an approval winner, we know (Lemma 1) that $|A(x^-a^+)| > |A(x^+a^-)|$. Then by the construction of $V'$:

$$ \frac{\sum_{i \in A(x^+a^-) \cup A(x^-a^+)} B_{V'_i}(a) - B_{V'_i}(x)}{\left( \sum_{i \in A(x^-a^+)} \alpha_i \right) - |A(x^+a^-)|} \geq |A(x^-a^+)| - |A(x^+a^-)| > 0 $$

In addition, the following clearly holds since our ranking profile is standardised:

$$ \sum_{i \in A(x^+a^+) \cup A(x^-a^-)} B_{V'_i}(a) - B_{V'_i}(x) > 0 $$

So, we have that $\sum_{i \in N} B_{V'_i}(a) - B_{V'_i}(x) = \sum_{i \in A(x^+a^-) \cup A(x^-a^+)} B_{V'_i}(a) - B_{V'_i}(x) + \sum_{i \in A(x^+a^+) \cup A(x^-a^-)} B_{V'_i}(a) - B_{V'_i}(x) > 0$. This means that $x$ will be a Borda loser in $V'$. If we instead assume $x$ is an approval co-winner in $AS'$, the above inequality may be weak, implying that $x$ may be a Borda winner in $V'$, together with $a$.

It remains to prove that $a$'s Borda score in $V'$ is greater than the Borda score of each other alternative $y \in S \setminus \{a\}$ (or equal to that score, in case $y$ is an approval co-winner in $AS'$). For what remains, let us focus on the case of $y$ being an approval loser, since the other one is analogous.

We now consider the evolution of the Borda scores of $a$ and $y$ in $V'_i$ and $V_i$, depending of the type of voter $i$. We write $x_1 \succ_i x_2$ to denote that alternative $x_1$ is ranked above alternative $x_2$ by voter $i$ in $V'$:
• if $i \in A(a^+y^-)$, then $a \triangleright_i x \triangleright_i y$.

• If $i \in A(a^-x^+y^+)$, then $y \triangleright_i x \triangleright a$.

• If $i \in A(a^-x^-y^+)$, then $y \triangleright a \triangleright x$.

• If $i \in A(a^+y^+)$, then $a \triangleright y \triangleright x$.

• If $i \in A(a^-y^-x^+)$, then $x \triangleright a \triangleright y$.

• If $i \in A(a^-y^-x^-)$, then $a \triangleright x \triangleright y$.

Now, in moving from $\mathbf{V}$ to $\mathbf{V}'$ the contribution of voter $i$ to the difference between the Borda scores of $a$ and $y$ is unchanged if $x$ is either above both $a$ and $y$ or below both $a$ and $y$; increases by one unit if $x$ is below $a$ and above $y$; and decreases by one unit if $x$ is below $y$ and above $a$, as summarised on Figure 3, where (*) means $(B_{V_i'}(a) - B_{V_i'}(y)) - (B_{V_i}(a) - B_{V_i}(y))$.

<table><caption>Fig. 3: Evolution of the difference between the Borda scores of $a$ and $x$</caption><thead><tr><th>i</th><th>A(a<sup>+</sup>y<sup>-</sup>)</th><th>A(a<sup>-</sup>x<sup>+</sup>y<sup>+</sup>)</th><th>A(a<sup>-</sup>x<sup>-</sup>y<sup>+</sup>)</th><th>A(a<sup>+</sup>y<sup>+</sup>)</th><th>A(a<sup>-</sup>y<sup>-</sup>x<sup>+</sup>)</th><th>A(a<sup>-</sup>y<sup>-</sup>x<sup>-</sup>)</th></tr></thead><tbody><tr><td>(*)</td><td>a &rarr; x &rarr; y</td><td>y &rarr; x &rarr; a</td><td>y &rarr; a &rarr; x</td><td>a &rarr; y &rarr; x</td><td>x &rarr; a &rarr; y</td><td>a &rarr; x &rarr; y</td></tr></tbody><tfoot><tr><td></td><td>+1</td><td>-1</td><td>0</td><td>0</td><td>0</td><td>+1</td></tr></tfoot></table>

Therefore, by our construction, when moving from $\mathbf{V}$ to $\mathbf{V}'$, the following hold with respect to the changes that occur in the difference of $a$'s and $y$'s Borda scores:

$$ \sum_{i \in A(a^+ y^-)} B_{V_i}(a) - B_{V_i}(y) = \left( \sum_{i \in A(a^+ y^-)} B_{V_i'}(a) - B_{V_i'}(y) \right) - |A(a^+ y^-)| \quad (1) $$

$$ \sum_{i \in A(a^- y^+)} B_{V_i}(a) - B_{V_i}(y) \le \left( \sum_{i \in A(a^- y^+)} B_{V_i'}(a) - B_{V_i'}(y) \right) + |A(a^- y^+)| \quad (2) $$

$$ \sum_{i \in A(a^+ y^+)} B_{V_i}(a) - B_{V_i}(y) = \sum_{i \in A(a^+ y^+)} B_{V_i'}(a) - B_{V_i'}(y) \quad (3) $$

$$ \sum_{i \in A(a^- y^-)} B_{V_i}(a) - B_{V_i}(y) \le \sum_{i \in A(a^- y^-)} B_{V_i'}(a) - B_{V_i'}(y) \quad (4) $$

Combining the equations and inequalities (1) to (4), we get:

$$ \sum_{i \in N} B_{V_i}(a) - B_{V_i}(y) \le \left( \sum_{i \in N} B_{V_i'}(a) - B_{V_i'}(y) \right) - |A(a^+ y^-)| + |A(a^- y^+)| \quad (5) $$

Recall that $|A(a^-y^+)| < |A(a^+y^-)|$ because $a$ is an approval winner and $y$ is an approval loser. Then, inequality (5) implies that:

$$ \sum_{i \in N} B_{V_i}(a) - B_{V_i}(y) < \sum_{i \in N} B_{V_i'}(a) - B_{V_i'}(y) $$

By our induction hypothesis, we have that $0 < \sum_{i \in N} B_{V_i}(a) - B_{V_i}(y)$ because $a$ is a Borda winner and $y$ a Borda loser in $\mathbf{V}$. This means that $0 < \sum_{i \in N} B_{V_i'}(a) - B_{V_i'}(y)$, and our proof is concluded. $\square$
16 *Approval Compatible Voting Rules*

<figure><img src="image_3.png" /><figcaption>(a) Step 1: Profile $\mathbf{A_S}$ with $S = \{a, x_1\}$.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>(b) Step 2: Profile $\mathbf{A_S}$ with $S = \{a, x_1, x_2\}$.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>(c) Step 3: Profile $\mathbf{A_S}$ with $S = X = \{a, x_1, x_2, x_3\}$.</figcaption></figure>

**Fig. 4:** Construction of a standardised ranking profile $V \sim \mathbf{A} = \langle\{a\}, \{a, x_1\}, \{x_1, x_2\}, \{x_3\}\rangle$, in which alternative $a$ is a Borda winner. The alternatives that are shaded in the approval profile of each step are not considered, and the alternatives within the grey box in a ranking are those that are approved in the corresponding approval ballot.

Turning for a moment to some of our other rules, proving that OCAC holds is much easier (see the proof of Proposition 1 in the Appendix).

**Proposition 1** *STV, plurality with runoff, and all Condorcet-consistent rules (when n is odd) satisfy OCAC (and thus also PAC and FPAC).*<fnref n="8" />

<footnote n="8">⁸For an even number of voters, we need a condition slightly stronger to Condorcet consistency to ensure that an approval winner will always be elected. We call an alternative $x$ weak Condorcet winner if it is preferred over every other alternative by at least half of the voters. As opposed to a Condorcet winner that—if existing—is unique, there may be multiple weak Condorcet winners in a ranking profile. Let us call a voting rule weakly Condorcet-consistent if it elects all weak</footnote>
Proof First, we consider STV. Take an arbitrary approval profile **A**, an approval winner $a \in \text{App}(\mathbf{A})$, and a standardised ranking profile $V_a \sim \mathbf{A}$ for $a$. Because $a \in \text{App}(\mathbf{A})$, the approval ballots that contain $a$ but not $x$ are at least as many as the approval ballots that contain $x$ but not $a$:

$$A(x^-a^+) \geq A(x^+a^-) \quad (1)$$

We prove by induction that at each round $j$ of the STV elimination procedure, there is a parallel universe in which $a$ has not been eliminated. At round 1, because $a$ is an approval winner and $V_a$ is standardised, $a$ has a maximal plurality score in $V_a$, therefore there is a universe in which $a$ survives to round 2. Assume that there is a universe in which $a$ survives until round $j$. Because $V_a$ is standardised for $a$, its restriction $V_a^j$ to the remaining candidates at step $j$ is standardised for $a$ too. Take any alternative $x \neq a$ that has survived until round $j$ in this universe. $V_a^j$ being standardised for $a$, together with (1), implies that $x$ will appear in the first position at most $A(x^+a^-) \leq A(x^-a^+)$ times in $V_a^j$, while $a$ will appear in the first position at least $A(x^-a^+) \times A(x^+a^-)$ times in $V_a^j$. Therefore, there is at least one universe in which $a$ will survive to round $j+1$, which proves the induction step. Taking $j = m-1$, we get that there is a universe in which $a$ is the STV winner. In addition, the only possibility for $x \neq a$ to be another STV winner in $V_a$ is if $A(x^-a^+) = A(x^+a^-)$ and $A(x^+a^+) = A(x^-a^-) = 0$, implying that $x$ is also an approval winner of **A**.

Second, for plurality with runoff, the reasoning is analogous to STV. The plurality points of $a$ in both rounds are at least $A(x^-a^+)$, and the plurality points of $x$ in both rounds are at most $A(x^+a^-) \leq A(x^-a^+)$. So alternative $a$ must be a winner. In addition, the only possibility for the alternative $x \neq a$ to be another winner in $V$ is if $A(x^-a^+) = A(x^+a^-)$ and $A(x^+a^+) = A(x^-a^-) = 0$, implying that $x$ is also an approval winner of **A**.

Finally, consider an odd number of voters $n$ and an approval profile $\mathbf{A} = (A_1, \dots, A_n)$ and $x \in \text{App}(\mathbf{A})$. We will show that $x$ is the Condorcet winner in any standardised ranking profile $V = (V_1, \dots, V_n) \sim \mathbf{A}$. Thus, all Condorcet-consistent rules will elect $x$ as the single winner in $V$, implying that OCAC holds. We construct $V$ to be standardised by having each voter $i$ who approves $x$ in $\mathbf{A}$ rank $x$ first, and each voter $i$ who does not approve $x$ in $\mathbf{A}$ rank $x$ in position $|A_i| + 1$. To see that $x$ is a Condorcet winner in $V$, consider an arbitrary alternative $y \neq x$. Since $x$ is an approval winner, we know that $A(x^+y^-) \geq A(x^-y^+)$. Now, the number of voters ranking $x$ above $y$ in $V$ is $N(x, y) = A(x^+y^+) + A(x^+y^-) + A(x^-y^-)$, and $n - N(x, y) = A(x^-y^+) \leq A(x^+y^-) \leq N(x, y)$, which, because $n$ is odd, implies that $N(x, y) > \frac{n}{2}$, and we are done. $\square$

Before continuing to uniform notions of approval compatibility, it remains to see if positional scoring rules satisfy the weakest notion of FPAC. For that, Lemma 2 gives a necessary condition.<fnref n="9" /> Intuitively, this condition focuses on special profiles where an approval winner $x$ only appears in singleton approval ballots, while other alternatives are approved together in large ballots (hence forcing $x$ to be ranked below all of them in the compatible rankings). Then, it states that the average score of all alternatives should not exceed the score of $x$; otherwise, one of the alternatives besides $x$ will win.

<footnote>Condorcet winners, whenever there are some. The fact that all weakly Condorcet-consistent rules satisfy OCAC (and thus also PAC and FPAC) for even $n$ is proven similarly to the odd case.</footnote>

<footnote n="9">⁹We conjecture that this condition is also sufficient.</footnote>
18 Approval Compatible Voting Rules

For example, take $|X| = \{x_1, x_2, x_3\}$ and consider the following approval profile $\mathbf{A}$, where $x_3$ is the only approval winner:

$$ \mathbf{A} = \langle \{x_3\}, \{x_3\}, \{x_3\}, \{x_1, x_2\}, \{x_1, x_2\} \rangle $$

For any positive integer $k$ and profile $\mathbf{V} \sim k\mathbf{A}$, the antiplurality score of $x_3$ is exactly $3k$, while the sum of the antiplurality scores of all alternatives is $10k$. Since $3k < \frac{10k}{3}$, at least one alternative amongst $x_1$ and $x_2$ must have an antiplurality score larger than that of $x_3$, thus FPAC is violated.

**Lemma 2** Let $r_s$ be the positional scoring rule defined by the scoring vector $s = (s_1, \dots, s_m)$. The following is a necessary condition for $r_s$ to satisfy FPAC (and thus also a necessary condition to satisfy PAC):

$$ \frac{1}{m}(s_1 + \dots + s_m) \le \frac{\ell s_1 + (m-1)s_{\ell+1}}{\ell + m - 1}, \quad \text{for all } \ell \in \{2, \dots, m-1\} $$

*Proof* Suppose that the condition of the statement is violated for a given $\ell \in \{2, \dots, m-1\}$. We will show that $r_s$ violates FPAC by constructing a suitable counterexample. Consider an approval profile $\mathbf{A}$ with $\ell + m - 1$ voters, where each of the $\ell$ voters only approve $x_m$ and each of the remaining $m-1$ voters circularly approve $\ell$ alternatives from the set $X \setminus \{x_m\}$, as follows:

$$ \underbrace{\langle \{x_m\}, \dots, \{x_m\} \rangle}_{\ell} \underbrace{\overbrace{\{x_1, x_2, \dots, x_\ell\}}^{\ell}, \overbrace{\{x_2, x_3, \dots, x_{\ell+1}\}}^{\ell}, \dots, \overbrace{\{x_{m-1}, x_1, \dots, x_{\ell-1}\}}^{\ell}}^{m-1} $$

All alternatives in $X$ are approval co-winners of $\mathbf{A}$, with approval score $\ell$. In particular, $x_m \in \text{App}(\mathbf{A})$, with $\text{App}_{\mathbf{A}}(x_m) = \ell$. But for every ranking profile $\mathbf{V} \sim k\mathbf{A}$, for some positive integer $k$, we know that $x_m$ can get score at most $s(x_m) = k(\ell s_1 + (m-1)s_{\ell+1})$, while the sum of the scores of all alternatives is $\sum_{x \in X} s(x) = k(\ell + m - 1)(s_1 + \dots + s_m) > \ell s_1 + (m-1)s_{\ell+1}$ from the violation of our condition, it follows that at least one alternative amongst $x_1, \dots, x_{m-1}$ must have a larger score than $x_m$ in $\mathbf{V}$, implying that $x_m$ cannot be made a winner under the given positional scoring rule. $\square$

To exemplify the necessary condition for FPAC above, let us look at the special case with three alternatives. For $m = 3$ and normalising the scoring vector to $s = (1, s_2, 0)$, the characterisation condition states that $\frac{1}{3}(1+s_2) \le \frac{2}{4}$, or equivalently that $s_2 \le \frac{1}{2}$. This is in agreement with Example 2 in the Introduction, demonstrating that for such scoring vectors with $s_2 > \frac{1}{2}$, PAC is violated.

Lemma 2 implies Proposition 2, stating that FPAC is not satisfied by any $K$-approval rule (except for the plurality rule that we already saw satisfies

PAC). Indeed, if we consider the scoring vector $s = (\overbrace{1, \dots, 1}^{K}, \overbrace{0, \dots, 0}^{m-K}, \overbrace{0}^{\ell})$ for $K \ge 2$ and let $\ell = K$ in the inequality of Lemma 2, we get $\frac{1}{m}K > \frac{K}{m+K-1}$, meaning that FPAC is violated.
**Proposition 2** For any $K \ge 2$, the K-approval rule violates FPAC (and thus also PAC and CAC).

## 3.2 Uniform Positive Approval Compatibility

After having looked at notions of positive approval compatibility that refer to a single approval winner at a time, we continue with uniform ones that examine all approval winners simultaneously, i.e., UPAC and FUPAC. Although the former notion is extremely demanding, we find that the latter is satisfied by the Borda rule as well as Copeland and maximin.

Recall Example 3, where the plurality rule was found to violate UPAC. We will use the same argument to show that many more rules also fail to satisfy this property. A voting rule is called *faithful* if whenever applied to an 1-voter profile, it selects as winner the voter's top alternative and only that (Young, 1974). For example, the plurality rule and the Borda rule are faithful, while K-approval rules for $K \ge 2$ are not.

**Proposition 3** All faithful rules violate UPAC.

*Proof* Let $n = 1$, and consider the approval profile $\mathbf{A}$ where the unique voter approves all alternatives. We have that $\text{App}(\mathbf{A}) = X$ but for every $\mathbf{V} \sim \mathbf{A}$ (that is, for every $\mathbf{V}$) we have $|r(\mathbf{V})| = 1$, and therefore we cannot have $\text{App}(\mathbf{A}) = r(\mathbf{V})$.<fnref n="10" /> □

Note that the argument employed in Proposition 3 relies on the fact that there is a single ranking from which the voting rule should determine a winner. If we are allowed to take multiple copies of the ballots (aiming for the satisfaction of the fractional version of UPAC), perhaps there is a hope for a positive result. This intuition is verified for the Borda rule (specifically, by taking just a double copy of the approval profile), but is falsified for all K-approval rules, and in particular for plurality. We will prove the latter by also providing a necessary condition.

**Lemma 3** Let $r_s$ be the positional scoring rule defined by the scoring vector $s = (s_1, \dots, s_m)$. The following is a necessary condition for $r_s$ to satisfy FUPAC (and thus also to satisfy UPAC):

$$ \frac{s_1 + s_m}{2} = \frac{s_2 + \dots + s_{m-1}}{m-2} $$

*Proof* Take $r_s$ to be the positional scoring rule defined by the scoring vector $s = (s_1, \dots, s_m)$, and suppose that $r_s$ satisfies FUPAC. Then, consider the 2-voter profile $\mathbf{A}$ as follows, where $\text{App}(\mathbf{A}) = X$:

$$ \mathbf{A} = \{\{x_1, x_2, \dots, x_{m-1}\}, \{x_m\}\} $$

<footnote n="10">¹⁰With at least three alternatives, a similar argument works without needing the sole voter to approve all alternatives.</footnote>
20 Approval Compatible Voting Rules

Since $r_s$ satisfies FUPAC, there is a ranking profile $\mathbf{V} \sim k\mathbf{A}$ for some positive integer $k$, such that $r_s(\mathbf{V}) = X$. Then, the sum of the scores of the first $m-1$ alternatives in $\mathbf{V}$ is the following:

$$ \sum_{j \in \{1, \dots, m-1\}} s(\mathbf{V}, x_j) = k(s_1 + 2s_2 + 2s_3 + \dots + 2s_{m-1} + s_m) $$

Also, the score of $s_m$ is $s(\mathbf{V}, x_m) = k(s_1 + s_m)$. But as all alternatives are winners in $\mathbf{V}$, we know that all their scores must be equal, which means that:

$$ \begin{align*} k(s_1 + 2s_2 + 2s_3 + \dots + 2s_{m-1} + s_m) &= (m-1)k(s_1 + s_m) \\ \Rightarrow \quad k(2s_2 + 2s_3 + \dots + 2s_{m-1}) &= (m-2)k(s_1 + s_m) \\ \Rightarrow \quad \frac{s_2 + s_3 + \dots + s_{m-1}}{m-2} &= \frac{s_1 + s_m}{2} \end{align*} $$

Therefore, we have obtained our necessary condition for FUPAC. $\square$

<figure><img src="image_6.png" /></figure>

**Theorem 3** The following two statements hold:

(a) All K-approval rules violate FUPAC (thus also UPAC).

(b) The Borda rule satisfies FUPAC.

*Proof* For (a), since the plurality rule violates the necessary condition of Lemma 3, it violates FUPAC. For any $K \ge 2$, it follows from Proposition 2 that the K-approval rule violates FPAC (hence violates FUPAC too).

For (b), let $r$ be the Borda rule. Given an approval profile $\mathbf{A}$, we construct a ranking profile $\mathbf{V} = \langle \mathbf{V}^1, \mathbf{V}^2 \rangle \sim 2\mathbf{A}$ such that $r(\mathbf{V}) = \text{App}(\mathbf{A})$, as follows. We first fix the lexicographical ordering of the alternatives in $X: x_1, x_2, \dots, x_m$. Then for ever voter $i$, $V_i^1$ ranks the alternatives of $A_i$ in the lexicographical order at the top, followed by the alternatives of $X \setminus A_i$ in the lexicographical order below; $V_i^2$ ranks the alternatives of $A_i$ in the reverse lexicographical order at the top, followed by the alternatives of $X \setminus A_i$ in the reverse lexicographical order below.

We claim that the Borda score $B_{\mathbf{V}}(x)$ of every alternative $x$ in $\mathbf{V}$ arises from its approval score $\text{App}_{\mathbf{A}}(x)$ in $\mathbf{A}$ via the positive affine transformation:

$$ B_{\mathbf{V}}(x) = \delta \text{App}_{\mathbf{A}}(x) + \gamma $$

where $\delta, \gamma \in \mathbb{R}$ are specified below. We next prove our claim. Recall that $m(x, y) = |\{i \in N | (x, y) \in V_i\}| - |\{i \in N | (y, x) \in V_i\}|$ and that $\sum_{y \in X} m(x, y) = \beta_{\mathbf{V}}^{\text{sym}}(x)$ is the symmetric Borda score of alternative $x$ (obtained via the vector of symmetric Borda scores $(m-1, m-3, m-5, \dots, -(m-1))$, which is equivalent to the more standard one $(m-1, m-2, \dots, 1, 0)$). For our profile $\mathbf{V}$ above, we have that:

$$ m(x, y) = 2(\text{App}_{\mathbf{A}}(x) - \text{App}_{\mathbf{A}}(y)) $$

Therefore, it follows that:

$$ \beta_{\mathbf{V}}^{\text{sym}}(x) = 2 \sum_{y \in X} \text{App}_{\mathbf{A}}(x) - \text{App}_{\mathbf{A}}(y) = 2m \text{App}_{\mathbf{A}}(x) - 2 \sum_{y \in X} \text{App}_{\mathbf{A}}(y) $$

This completes the proof of our claim, taking $\delta = 2m$ and $\gamma = -2 \sum_{y \in X} \text{App}_{\mathbf{A}}(y)$.

Finally, from our claim it follows that the Borda winners that maximise $B_{\mathbf{V}}(x)$ coincide with the approval winners that maximise $\text{App}_{\mathbf{A}}(x)$, and we are done. $\square$
Note that Lemma 3 implies that when $m = 3$, the Borda rule is the only positional scoring rule that potentially satisfies FUPAC. Theorem 3 then confirms that this is indeed the case. A natural question is whether this extends to $m > 3$. So far we don't have an answer, but we believe that the answer is negative.<fnref n="11" />

As we see in the next proposition, moving away from positional scoring rules brings mixed news in terms of FUPAC.

**Proposition 4** STV and plurality with runoff violate FUPAC (and thus also UPAC). All weakly Condorcet-consistent rules satisfy FUPAC.

*Proof* Let $m = 3$ and consider the following approval profile, where all three alternatives $x_1, x_2, x_3$ are approval co-winners:

$$ \langle \{x_1\}, \{x_2, x_3\} \rangle $$

For every ranking profile $V \sim kA$, alternative $x_1$ will be placed on the first position $k$ times, but one of the alternatives $x_2$ and $x_3$ will necessarily be placed on the first position fewer than $k$ times and will be eliminated in the first round of STV. This means that not all approval winners can be made STV co-winners. For $m = 3$, STV and plurality with runoff coincide, and the counterexample works for the latter too.

Continuing to Copeland and maximin, let us fix a lexicographical ordering over the set of alternatives: $x_1, x_2, ..., x_m$. Consider $App(\mathbf{A})$, the set of approval co-winners of a profile $\mathbf{A}$. Take a compatible ranking profile $V = \langle V_1, V_2, ..., V_m \rangle \sim \mathbf{A}$ such in every $V_i$, the alternatives in $A_i$ are ranked according to the lexicographical ordering and above all alternatives in $X \setminus A_i$, which are also ranked according to the lexicographical ordering. Take another compatible ranking profile $V' = \langle V'_1, V'_2, ..., V'_m \rangle \sim \mathbf{A}$ such in every $V'_i$, the alternatives in $A_i$ are ranked according to the reverse lexicographical ordering and above all alternatives in $X \setminus A_i$, which are also ranked according to the reverse lexicographical ordering.

Then, for each pair of alternatives $x, y \in App(\mathbf{A})$, $x$ is ranked equally many times above and below $y$ in the joint profile $V'' = \langle V, V' \rangle$. The same holds for each pair of alternatives in $X \setminus App(\mathbf{A})$. Moreover, for each $x \in App(\mathbf{A})$ and $z \in X \setminus App(\mathbf{A})$, we know as in the proof of Proposition 1 that $x$ is ranked above $z$ in strictly more than $n$ (out of the total $2n$) rankings of $V''$. This means that the approval winners of $\mathbf{A}$ will be exactly the weak Condorcet winners of $V''$, and FUPAC will hold for every weakly Condorcet-consistent rule. $\square$

## 3.3 Negative Approval Compatibility

We have seen so far that satisfying positive notions of approval compatibility is not a trivial task for many voting rules: K-approval rules (except for the plurality rule) fail all such notions we examined, and all our rules fail the uniform notion. On the contrary, we now focus on negative notions of approval

<footnote n="11">¹¹For $m = 4$, we have shown that the following conditions on the scoring weights are necessary for a scoring rule to satisfy FUPAC: $s_1 - s_2 = s_3 - s_4 > 0$ and $s_2 - s_3 = r(s_1 - s_2)$ for some rational number $r$ with $0 \le r \le 4$. In particular, the scoring rule associated with scoring vector $(2, 1, 1, 0)$ satisfies this condition and we strongly believe it satisfies FUPAC, but we don't have a full proof.</footnote>
22 *Approval Compatible Voting Rules*

compatibility, asking for a voting rule to guarantee that approval losers will
not be elected. We will see that this is a much weaker requirement.

Let us start with defining a weak normative principle, satisfied by most
known voting rules. We will then show that this principle implies NAC (so
also FNAC).

**Definition 6** *Given two alternatives x, y ∈ X, we say that x overwhelms y at the ranking profile V if at least one of the following two conditions holds:*

1. x Pareto dominates y at V ;

2. more than half the ballots at V rank x first and y last.

The overwhelmed losers property (aka OWL) then says that if some alterna-
tive x overwhelms an alternative y at profile V and also at profile V', then y
is not a winner of the joint profile ⟨V, V'⟩.

**Lemma 4** If a voting rule satisfies OWL, then it also satisfies NAC.

*Proof* Consider an approval profile **A** and two alternatives x, y such that x ∈ App(**A**)
and y / ∈ App(**A**). Then, we can construct a ranking profile **V** ∼ **A** as follows:

* Every voter *i* with *y* ∈ *A*<sub>*i*</sub> and *x* /∈ *A*<sub>*i*</sub> ranks *y* last amongst all her approved alternatives and ranks *x* first amongst all her non-approved alternatives. Say we have α ⊆ *N* such voters.

* Every voter *i* with *x* ∈ *A*<sub>*i*</sub> and *y* /∈ *A*<sub>*i*</sub> ranks *x* first amongst all her approved alternatives and ranks *y* last amongst all her non-approved alternatives. Say we have *β* ⊆ *N* such voters.

* Every voter *i* with *x*, *y* ∈ *A*<sub>*i*</sub> ranks *x* first and *y* last amongst all her approved alternatives. Say we have *γ* ⊆ *N* such voters.

* Every voter *i* with *x*, *y* /∈ *A*<sub>*i*</sub> ranks *x* first and *y* last amongst all her non-approved alternatives. Say we have *δ* ⊆ *N* such voters.

Because $x \in \text{App}(\mathbf{A})$ and $y \notin \text{App}(\mathbf{A})$, we know that $|\beta| > |\alpha|$. Then the profile $\mathbf{V}$ can be decomposed into two profiles $\mathbf{V}'$ (with the voters from $\gamma \cup \delta$) and $\mathbf{V}''$ (with the voters from $\alpha \cup \beta$), in both of which $x$ overwhelms $y$. Thus $y \notin r(\mathbf{V})$ holds for any rule $r$ satisfying OWL. $\square$

Although OWL has some flavour of “negative reinforcement”, it does not imply
such a property, which is too strong to be reasonable. For if *y* loses both at
profile **V** and at profile **V'**, then it may happen that it barely loses to some
alternative *z* in **V** and it barely loses to some alternative *w* in **V'*. Now if *z*
does very poorly at **V'** and *w* does very poorly at **V**, it's quite plausible that
*y* should win at ⟨**V**, **V'**⟩.

But how compelling is OWL? Note also that each of the following two
strictly weaker properties is in fact quite compelling:
1. If some $x$ Pareto dominates $y$ at $V$, then $y$ is not a winner at $V$.

2. If a majority of voters rank some $x$ at the top and some $y$ at the bottom at $V'$, then $y$ is not a winner at $V'$.

It is difficult to identify plausible voting rules that fail either one of these two weaker properties, although K-approval rules for $K \ge 2$ do not satisfy the Pareto condition. Note that positional scoring rules with scoring vector $(s_1, ..., s_m)$ such that $s_1 > s_2 > ... > s_m$ satisfy OWL.

Let us next confirm what we already claimed: that many common voting rules satisfy OWL, and therefore NAC and FNAC. Specifically, this holds for STV, plurality with runoff, the Copeland rule, the maximin rule. Note however that from Proposition 1 we already know that all Condorcet-consistent rules satisfy NAC (which is implied by OCAC).

**Proposition 5** All positional scoring rules satisfying $s_1 > s_2 > ... > s_m$, STV, plurality with runoff, the Copeland rule, and the maximin rule satisfy NAC (and thus also FNAC).

*Proof* For STV, plurality with runoff, the Copeland rule, and the maximin rule, we will show that OWL holds. Then, Lemma 4 implies that NAC holds too. Consider an alternative $y$ that is overwhelmed by an alternative $x$ in both ranking profiles $V$ and $V'$. For STV, $y$ will be eliminated before $x$ in $\langle V, V' \rangle$ (unless no voter ranks $x$ or $y$ first, in which case $y$ is eliminated before any $z$ who is ranked first by at least one voter) and cannot be a winner. Similarly for plurality with runoff, $y$ cannot win since it loses from $x$ in a majority competition. The Copeland score of alternative $y$ will also be smaller than that of $x$ in $\langle V, V' \rangle$, ensuring that $y$ cannot win. Similarly, a scoring rule with scoring vector $(s_1, ..., s_m)$ such that $s_1 > s_2 > ... > s_m$ will give a smaller score to $y$ than to $x$. For the maximin rule, the argument goes as follows: If $x$ Pareto dominates $y$ on the entire profile $V$ (with $V'$ empty) then $y$'s margin over $x$ achieves the minimum possible value of $-m$, and so $y$ cannot be a maximin winner. If not (so that there is a nonempty $V'$ part in which a majority of the voters rank $x$ on top and $y$ on bottom), then $x$'s majority margin over any alternative $z$ is strictly greater than $y$'s majority margin over $z$. As $x$'s majority margin over $y$ is greater than $y$'s over $x$, $x$ has a larger maximin score than $y$.

Arbitrary positional scoring rules need not satisfy OWL, so we provide a direct proof for NAC. Take a scoring rule with associated scoring vector $(s_1, ..., s_m)$. Consider an approval profile $A$ with $x_1 \in \text{App}(A)$ and $x_2 \notin \text{App}(A)$. Construct a ranking profile $V \sim A$ as follows: All voters who approve $x_1$ in $A$ rank $x_1$ first (let this set of voters be $X_1$). All voters who do not approve $x_2$ in $A$ rank $x_2$ last (let this set of voters be $N \setminus X_2$). Voters otherwise rank alternatives arbitrarily, subject to $V \sim A$. Since $|X_1| > |X_2|$ and $s_1 > s_m$, we have that $s_V(x_1) \ge s_1|X_1| + s_m|(N \setminus X_1)| > s_1|X_2| + s_m|N \setminus X_2| \ge s_V(x_2)$, which guarantees that $x_2$ will not win in $V$. $\square$

## 3.4 Uniform Negative Approval Compatibility

In this section we examine UNAC and FUNAC, requiring that a voting rule can ensure that no approval loser will win in a ranking election. As was the
24 Approval Compatible Voting Rules

case for PAC and FPAC, we find that the plurality rule, the Borda rule, all Condorcet-consistent rules, STV, and plurality with runoff satisfy both these notions, while K-approval rules for $K \ge 2$ violate both. This is not surprising, since we know that the satisfaction of the positive notions for these rules was due to the satisfaction of CAC, which also implies UNAC. Part (a) of Theorem 4 then follows from Theorems 1 and 2, and Proposition 1.

**Theorem 4** The following two statements hold:

(a) The Borda rule, the plurality rule, STV, plurality with runoff, and all Condorcet-consistent rules (for an odd number of voters) satisfy UNAC (and thus also FUNAC).

(b) For all $K \ge 2$, K-approval violates FUNAC (and thus also UNAC).

*Proof* For (b), fix a set of alternatives $X = \{x_1, \dots, x_m\}$ and a K-approval rule for some $K \ge 2$. Take two approval profiles $A'$ and $A''$ as follows:

$$A' = \langle \{x_1, x_2, \dots, x_K\}, \{x_2, x_3, \dots, x_{K+1}\}, \dots, \{x_{m-1}, x_1, \dots, x_{K-1}\} \rangle \\ A'' = \langle \{x_m\} \rangle$$

That is, in the profile $A'$ each of the alternatives $x_1, \dots, x_{m-1}$ receives K approval points, and in the profile $A''$ the alternative $x_m$ receives 1 approval point.

Now take two numbers $\alpha, \beta \in \mathbb{N}$ such that $\beta = \alpha K + 1$ and $\beta(K-1) \ge m-1$ (such numbers always exist, for example by taking a large enough even number $\alpha$ and a corresponding large enough number $\beta$), and consider the following profile:

$$A = \underbrace{\langle A', \dots, A' \rangle}_{\alpha}, \underbrace{\langle A'', \dots, A'' \rangle}_{\beta}$$

In the profile $A$ each of the alternatives $x_1, \dots, x_{m-1}$ receives $\text{App}_A(x_1) = \alpha K$ approvals, and the alternative $x_m$ receives $\text{App}_A(x_m) = \beta = \text{App}_A(x_1)+1$ approvals (so $x_m$ is the single approval winner).

Then, in every ranking profile $V \sim kA$, the alternative $x_m$ will get at most $k\text{App}_A(x_m)$ points by the K-approval rule, since only the voters in $kA''$ can rank it in one of the top K positions. The alternatives $x_1, \dots, x_{m-1}$ will all get at least $k\text{App}_A(x_1)$ points by the remaining voters. Since $k\text{App}_A(x_m) - k\text{App}_A(x_1) = k$, if any alternative from the first $m-1$ ones gets at least $k$ more points by the K-approval rule in $V$, it will be a (co-)winner in $V$. Note that this will necessarily happen, because there are $k\beta(K-1) \ge k(m-1)$ available points to be given from the voters in $kA''$, which must be shared among $m-1$ alternatives. $\square$

Having presented all our formal results, we are ready to conclude.

## 4 Conclusion

Social choice theorists stand within a long tradition of comparing different voting rules. What are their similarities and differences? Will the same electorate yield similar outcomes for different rules? Here we have considered a special case of the latter question: given an electorate who have cast approval ballots
and determined an approval winner, is it possible for the same electorate to
obtain the same winner(s) by using a voting rule that instead uses ranked bal-
lots? An immediate issue is what “same electorate” means under a change of
ballot format. We have chosen to require only that a voter who has approved a
set A of alternatives in the first (approval) ballot must, in the ranking election
that follows, rank all members of A above all non-members. Arguably, this
interpretation better represents a “possibly same electorate,” but it is difficult
to imagine natural alternatives.

We find that the answer varies considerably, depending on both the version
of *approval compatibility* property at hand, and on the particular voting rule
for ranked ballots. However, some broad patterns emerge. Some properties,
such as requiring the exact same set of co-winners from the second election,
are too strong to be satisfied universally (that is, for all approval profiles)
by any ranking rule. Others, such as requiring any single approval loser to
lose the ranking election, are so weak that they are satisfied by quite a broad
variety of ranking rules. An intermediate set of properties, such as requiring
any single approval winner to be a winner of the ranking election, but without
also electing any approval losers, are of intermediate strength, and differentiate
in interesting ways among voting rules. For example, this particular property is
satisfied by all Condorcet consistent rules, STV, Borda, and Plurality voting,
but not by K-approval. Other variants are satisfied by Condorcet consistent
rules and Borda, but not by STV, plurality or K-approval. Borda, in particular,
seems to play an important role as an edge case.

While we have laid the ground for exploring the relations between approval-
based and ranking-based elections, we certainly have not answered all relevant
questions. For instance, we have provided necessary but not sufficient condi-
tions for positional scoring rules to satisfy the “fractional” version of uniform
positive approval compatibility, and have only partially linked approval
compatibility with other known axiomatic properties of voting rules (e.g., faith-
fulness). Also, our results are limited to a specific collection of voting rules for
ranked ballots, and to a single rule – approval voting – for approval ballots.
We leave these matters for future research. A possibly more important limita-
tion of the current study is that it represents a “worst case” analysis, in the
sense that a rule that violates some approval compatibility property for even a
single approval profile is lumped together with another that might violate that
property most of the time. A particularly interesting follow-up, then, would
consider a probabilistic counterpart to the questions we ask here: given a joint
probability distribution over approval profiles and compatible ordinal profiles,
and an ordinal voting rule *r*, how likely is it that the approval winner(s) of the
approval profile coincide with the *r* winner(s) of the ranking profile?

Acknowledgements

We thank Antoinette Baujard, Jean-François Laslier, and Remzi Sanver for
helpful discussions about the meaning of approval preferences and ballots.
References

Alcalde-Unzu J, Vorsatz M (2009) Size approval voting. Journal of Economic Theory 144(3):1187-1210

Allouche T, Lang J, Yger F (2022) Truth-tracking via approval voting: Size matters. In: Proceedings of AAAI-2022

Barrot N, Gourvès L, Lang J, et al (2013) Possible winners in approval voting. In: Proceedings of the 3rd International Conference on Algorithmic Decision Theory (ADT)

de Borda JC (1784) *Memoire sur les elections au scrutin*. Histoire de l'Academie Royale des Sciences

Brams S, Fishburn P (1983) Approval Voting. Birkhäuser. Basel

Conitzer V, Rognlie M, Xia L (2009) Preference functions that score rankings and maximum likelihood estimation. In: Boutilier C (ed) IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11-17, 2009, pp 109-115

Darmann A, Grundner J, Klamler C (2019) Evaluative voting or classical voting rules: Does it make a difference? Empirical evidence for consensus among voting rules. European Journal of Political Economy 59:345-353

Endriss U, Pini MS, Rossi F, et al (2009) Preference aggregation over restricted ballot languages: Sincerity and strategy-proofness. In: Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI)

Gehrlein WV (1981) Borda efficiency of constant scoring rules with large electorates. RAIRO-Operations Research 15(3):287-296

Hare T (1859) Treatise on the Election of Representatives, Parliamentary and Municipal. London: Longman, Green, Reader, and Dye

Klamler C (2005) Borda and Condorcet: Some distance results. Theory and Decision 59(2):97-109

Laslier JF (2012) And the loser is... plurality voting. In: Felsenthal DS, Machover M (eds) Electoral systems. Paradoxes, Assumptions, and Procedures. Springer, p 327-351

Popov SV, Popova A, Regenwetter M (2014) Consensus in organizations: Hunting for the social choice conundrum in APA elections. Decision 1(2):123

Procaccia AD, Shah N (2015) Is approval voting optimal given approval votes? In: Proceedings of the 29th Conference on Neural Information Processing
Systems (NIPS)

Ratliff TC (2001) A comparison of dodgson’s method and kemeny’s rule. Social Choice and Welfare 18(1):79–89

Regenwetter M, Grofman B (1998) Choosing subsets: A size-independent probabilistic model and the quest for a social welfare ordering. Social Choice and Welfare 15(3):423–443

Regenwetter M, Tsetlin I (2004) Approval voting and positional voting methods: Inference, relationship, examples. Social Choice and Welfare 22(3):539–566

Regenwetter M, Kim A, Kantor A, et al (2007) The unexpected empirical consensus among consensus methods. Psychological Science 18(7):629–635

Saari DG (2010) Systematic analysis of multiple voting rules. Social Choice and Welfare 34(2):217–247

Taylor AD (1995) Mathematics and Politics. Springer, New York

Young HP (1974) An axiomatization of Borda's rule. Journal of Economic Theory 9(1):43–52

Zwicker WS (2016) Introduction to the theory of voting. In: Brandt F, Conitzer V, Endriss U, et al (eds) Handbook of Computational Social Choice. Cambridge University Press