An Axiomatic Characterization of Split Cycle Yifeng Ding Wesley H. Holliday and Eric Pacuit Peking University yf.dingpku.edu.cn

2025-04-30 0 0 746.75KB 40 页 10玖币

侵权投诉

An Axiomatic Characterization of Split Cycle

Yifeng Ding∗, Wesley H. Holliday†, and Eric Pacuit‡

∗Peking University (yf.ding@pku.edu.cn)

†University of California, Berkeley (wesholliday@berkeley.edu)

‡University of Maryland (epacuit@umd.edu)

Forthcoming in Social Choice and Welfare.

Abstract

A number of rules for resolving majority cycles in elections have been proposed in the literature.

Recently, Holliday and Pacuit (Journal of Theoretical Politics 33 (2021) 475-524) axiomatically charac-

terized the class of rules reﬁned by one such cycle-resolving rule, dubbed Split Cycle: in each majority

cycle, discard the majority preferences with the smallest majority margin. They showed that any rule

satisfying ﬁve standard axioms plus a weakening of Arrow’s Independence of Irrelevant Alternatives (IIA),

called Coherent IIA, is reﬁned by Split Cycle. In this paper, we go further and show that Split Cycle is

the only rule satisfying the axioms of Holliday and Pacuit together with two additional axioms, which

characterize the class of rules that reﬁne Split Cycle: Coherent Defeat and Positive Involvement in De-

feat. Coherent Defeat states that any majority preference not occurring in a cycle is retained, while

Positive Involvement in Defeat is closely related to the well-known axiom of Positive Involvement (as

in J. P´erez, Social Choice and Welfare 18 (2001) 601-616). We characterize Split Cycle not only as a

collective choice rule but also as a social choice correspondence, over both proﬁles of linear ballots and

proﬁles of ballots allowing ties.

Contents

1 Introduction 2

2 Preliminaries 6

2.1 VCCRs and VSCCs ......................................... 6

2.2 Split Cycle .............................................. 7

3 Axioms on VCCRs 9

3.1 Standard axioms ........................................... 9

3.2 Coherent IIA ............................................. 9

3.3 Coherent Defeat ........................................... 11

3.4 Positive Involvement in Defeat ................................... 13

4 Characterization of the Split Cycle VCCR 17

arXiv:2210.12503v3 [econ.TH] 28 Jun 2024

5 Axioms on VSCCs 19

5.1 Standard axioms ........................................... 19

5.2 Coherent IIA ............................................. 20

5.3 Coherent Defeat ........................................... 21

5.4 Tolerant Positive Involvement .................................... 21

6 Characterization of the Split Cycle VSCC 23

7 Ballots with Ties 26

8 The Necessity of Three Special Axioms 31

8.1 Coherent IIA ............................................. 32

8.2 Positive Involvement in Defeat and Tolerant Positive Involvement ................ 33

8.3 Coherent Defeat ........................................... 35

9 Conclusion 36

1 Introduction

The possibility of cycles in the majority relation of an election—wherein for candidates c1, . . . , cn, a majority

of voters prefer c1to c2, a majority prefer c2to c3, and so on, while a majority prefer cnto c1—has been taken

to show that “majority rule is fatally ﬂawed by an internal inconsistency” (Wolﬀ 1970, p. 59). Yet voting

theorists have studied many collective choice rules based on pairwise majority comparisons of candidates

designed to resolve majority cycles. These collective choice rules output a binary relation between candidates,

which we will call the relation of defeat, that is guaranteed to be free of cycles. One prominent family of such

rules resolves cycles by paying attention to the size of majority victories, e.g., as measured by the majority

margin between candidates xand y, deﬁned as the number of voters who prefer xto yminus the number

who prefer yto x. Examples include the Ranked Pairs (Tideman 1987,Zavist and Tideman 1989), River

(Heitzig 2004b), Beat Path (Schulze 2011,2022), Kemeny (Kemeny 1959),1Weighted Covering (Dutta and

Laslier 1999,P´erez-Fern´andez and De Baets 2018), and Split Cycle (Holliday and Pacuit 2021a,2023a) rules.

For instance, according to Split Cycle,2majority cycles are resolved as follows:

1. For each majority cycle, identify the pairwise majority victories with the smallest margin in that cycle.

2. A candidate adefeats a candidate baccording to Split Cycle if and only if ahas a pairwise majority

victory over bthat was not identiﬁed in step 1.

In other words, a majority victory of avs. bcounts as a defeat of bif and only if in each majority cycle in

which that majority victory appears, it does not have the smallest margin in the cycle. The resulting defeat

relation contains no cycles. See Figure 1for an example.

Faced with such a rule for resolving cycles, the question becomes: why this rule and not something

else? The question can be partially answered by identifying axioms that distinguish between known rules.

1Though Kemeny is not usually deﬁned in terms of pairwise margins of victory, it can be so deﬁned as shown in Fischer et al.

2016, p. 87. Another rule usually deﬁned in terms of individual preferences but also deﬁnable in terms of pairwise margins is

the Borda count (see Zwicker 2016, p. 28).

2Eppley’s (2000) “Beatpath Criterion Method” can be deﬁned in the same way but using winning votes instead of margins

as the measure of strength of majority preference. This distinction does not matter for our axiomatization in the context of

linear ballots, but it does matter for our axiomatization in the context of ballots allowing ties (see Section 7).

a c

D D

Figure 1: A margin graph (left) with three cycles: (a, d, b, a), (a, d, c, a), and (a, d, b, c, a). Deleting the

weakest edge in each cycle (namely (b, a) in the ﬁrst, (c, a) in the second, and (b, c) in the third) results in

the Split Cycle defeat graph (right).

A deeper answer comes from a complete axiomatic characterization of a rule as the unique rule satisfying

some list of natural axioms. For example, such axiomatic characterizations exist for the collective choice

rules that rank candidates by Copeland score (Rubinstein 1980) and Borda scores (Nitzan and Rubinstein

1981,Mihara 2017).3

Recently Holliday and Pacuit (2021a) have characterized the class of rules reﬁned by the Split Cycle

rule4using six axioms, ﬁve of which are standard (see Section 3.1 below) and the sixth of which is a

weakening of Arrow’s (1963) axiom of Independence of Irrelevant Alternatives (IIA). They call their new

axiom Coherent IIA. Recall that IIA states that for any two proﬁles Pand P′of voter preferences, if Pand

P′are the same with respect to how each voter ranks xvs. y, then if xdefeats yin P,xmust also defeat y

in P′. The motivation for weakening IIA to Coherent IIA can be seen in a simple example from Holliday and

Pacuit 2021a. In the proﬁle Pin Figure 2, displayed alongside its corresponding margin graph, arguably any

sensible collective choice rule should judge that candidate adefeats candidate b. However, in the proﬁle P′in

Figure 2, no sensible collective choice rule—technically, no collective choice rule that is anonymous, neutral,

and guarantees that some undefeated candidate exists—can judge that adefeats b, despite astill beating b

head-to-head by a margin of n. This is a counterexample to IIA as a normative requirement. Holliday and

Pacuit argue that the “Fallacy of IIA” is to ignore how the context of a full election can force us to suspend

judgment on some relations of defeat that we could coherently accept in a diﬀerent context.

n n n

a b c

b a a

c c ba c

n n

P′

n n n

a b c

bca

ca b a c

n n

Figure 2: Proﬁles (left) and their margin graphs (right) illustrating the “Fallacy of IIA.”

3A conjectured axiomatization of Ranked Pairs can be found in Tideman 1987.

4To say that a rule is reﬁned by Split Cycle means that if a candidate xdefeats a candidate yaccording to the rule, then x

also defeats yaccording to Split Cycle.

In the context of a majority cycle in which xis majority preferred to y, the electorate is incoherent with

respect to xand yin the sense that while there is an argument that xshould defeat y, in virtue of the

majority preference for xover y, there is also an opposing argument that xshould not defeat y, in virtue

of the path of majority preferences from yto x; e.g., yis majority preferred to z, who is majority preferred

to x. One natural measure of the degree of this incoherence is the strength of the opposing argument, which

is some monotonic function of the margins of the relevant majority preferences; e.g., the larger the margin

of yover zor of zover x, the more incoherent with the majority preference for xover y—and the smaller

those margins, the less incoherent with the majority preference for xover y. On this view, the following is

suﬃcient for P′to be no more incoherent than Pwith respect to xand y: the margin graph of P′is obtained

from that of Pby deleting or reducing the margins on zero or more edges not connecting xand yor by

deleting zero or more candidates other than xand y. Adopting this view about incoherence, Holliday and

Pacuit accept the core intuition behind IIA whenever contextual incoherence does not interfere, leading to

their axiom of Coherent IIA, which can be stated informally as follows:

•Coherent IIA (informally): if Pand P′are the same with respect to how each voter ranks xvs. y,

xdefeats yin P, and P′is not more incoherent than Pwith respect to xand y, then xmust also defeat

yin P′.

Holliday and Pacuit then prove that Split Cycle is the most resolute collective choice rule5satisfying the ﬁve

standard axioms plus Coherent IIA. Here “most resolute” means that for any other rule fthat satisﬁes the

six axioms, if xdefeats yaccording to f, then xdefeats yaccording to Split Cycle.

Holliday and Pacuit’s theorem may be viewed as characterizing Split Cycle as the unique collective choice

rule satisfying their six axioms plus a seventh axiom stating that the rule should be the most resolute rule

satisfying the ﬁrst six axioms. In a sense, however, this characterization using the notion of resoluteness is

only half of a characterization of Split Cycle.6We would like axioms on a collective choice rule such that

for any rule fsatisfying the axioms, xdefeats yaccording to fif and only if xdefeats yaccording to Split

Cycle. Such an axiomatic characterization is the main result of the present paper.

Our new characterization of Split Cycle involves two natural axioms, which we prove are satisﬁed by

exactly the collective choice rules that reﬁne Split Cycle:

•Coherent Defeat: if a majority of voters prefer xto y, and there is no majority cycle involving xand

y, then xdefeats y.

•Positive Involvement in Defeat: if ydoes not defeat xin proﬁle P, and P′is obtained from Pby

adding one new voter who ranks xabove y, then ystill does not defeat xin P′.

Coherent Defeat is a point of common ground between Split Cycle, Ranked Pairs, Beat Path, and GOCHA

(Schwartz 1986): in the absence of cyclic incoherence, majority preference is suﬃcient for defeat. We will

discuss other ways of motivating Coherent Defeat below, drawing on Heitzig 2002.7The intuition behind

Positive Involvement in Defeat, a variable-electorate axiom, is similar to the intuition behind ﬁxed-electorate

monotonicity axioms for collective choice rules, as stated in Blair and Pollak 1982: “additional support for a

5Technically, they characterize Split Cycle as what they call a variable-election collective choice rule, whose domain contains

proﬁles with diﬀerent sets of candidates and voters (see Section 2.1 below). Until the end of this section, we use ‘collective

choice rule’ to refer to the variable-election variety.

6As Holliday and Pacuit (2021a, p. 501) write, “A natural next step would be to obtain another axiomatic characterization

of Split Cycle as the only VCCR satisfying some axioms without reference to resoluteness.”

7Heitzig’s (2004a) deﬁnition of an “immune” candidate is the same as that of a Split Cycle winner if we replace “stronger”

with “at least as strong” in his deﬁnition.

(pairwise) winning alternative leaves it winning” (p. 935). Perhaps surprisingly, many collective choice rules

violate Positive Involvement in Defeat, including Ranked Pairs, River, Beat Path, and Covering (see Duggan

2013 for many versions) viewed as collective choice rules. As we will explain, the name is borrowed from

the related axiom of “Positive Involvement” for functions that output winners instead of a defeat relation

(see Saari 1995,P´erez 2001,Holliday and Pacuit 2021b). Our main result in this paper is that Split Cycle

is the unique collective choice rule satisfying the ﬁve standard axioms, Coherent IIA, Coherent Defeat, and

Positive Involvement in Defeat. The proof uses the well-known concept of minimal cuts in graph theory.

So far we have discussed Split Cycle as a collective choice rule that outputs for a given proﬁle a binary

relation of defeat on the set of candidates—or more precisely, what we call a variable-election collective choice

rule (VCCR), whose domain includes proﬁles with diﬀerent set of candidates and voters. In this paper, we

also characterize the associated variable-election social choice correspondence (VSCC) that outputs for a

given proﬁle the set of undefeated candidates. This involves a translation from VSCCs to VCCRs which

induces a translation in the reverse direction from IIA (resp. Coherent IIA) for VCCRs to IIA (resp. Coherent

IIA) for VSCCs. The additional axioms of Coherent Defeat and Positive Involvement in Defeat also have

natural analogues for VSCCs. Interestingly, the VSCC analogue of the VCCR axiom of Positive Involvement

in Defeat, which we call Tolerant Positive Involvement, strengthens the axiom of Positive Involvement from

the prior literature mentioned above. We prove that the Split Cycle VSCC is the unique VSCC satisfying

ﬁve standard axioms, Coherent IIA, Coherent Defeat, and Tolerant Positive Involvement.

The use in our axiomatizations of Coherent IIA, on the one hand, and variants of Positive Involvement,

on the other, nicely matches the two main normative points made about the Split Cycle VSCC in Holliday

and Pacuit 2023a, which stresses Split Cycle’s ability to handle both (i) the “Problem of Spoilers” and (ii)

the “Strong No Show Paradox” (P´erez 2001). Problem (i) is a variable-candidate problem, wherein adding a

new candidate to an election who loses overall and loses head-to-head to a candidate xcauses xto go from

winning to losing, while (ii) is a variable-voter problem, wherein adding new voters to an election who rank a

candidate xin ﬁrst place causes xto go from winning to losing. In essence, Coherent IIA is a strengthening

(assuming other uncontroversial axioms) of anti-spoiler axioms that mitigate (i), while Tolerant Positive

Involvement is a strengthening of the Positive Involvement axiom that prevents (ii).

The rest of the paper is organized as follows. In Section 2, we formally deﬁne VCCRs and VSCCs

in general and the Split Cycle VCCR and VSCC in particular. In Section 3, we review the axioms from

Holliday and Pacuit 2021a (Sections 3.1-3.2) and discuss in more depth the additional axioms of Coherent

Defeat (Section 3.3) and Positive Involvement in Defeat (Section 3.4). Using these axioms, we prove our

characterization result for the Split Cycle VCCR in Section 4. We then turn to the Split Cycle VSCC. In

Section 5, we deﬁne analogues for VSCCs of the axioms for VCCRs in Section 3. Using these analogous

axioms, we prove our characterization result for the Split Cycle VSCC in Section 6. In Section 7, we

adapt our characterization results to the setting in which ties are permitted in voters’ ballots. In Section 8,

we show that the three special axioms—Coherent IIA, Positive Involvement in Defeat (or Tolerant Positive

Involvement for VSCCs), and Coherent Defeat—are all necessary in our axiomatization. Finally, we conclude

with some suggestions for related axiomatization problems in voting theory in Section 9.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

AnAxiomaticCharacterizationofSplitCycleYifengDing∗,WesleyH.Holliday†,andEricPacuit‡∗PekingUniversity(yf.ding@pku.edu.cn)†UniversityofCalifornia,Berkeley(wesholliday@berkeley.edu)‡UniversityofMaryland(epacuit@umd.edu)ForthcominginSocialChoiceandWelfare.AbstractAnumberofrulesforresolvingmajoritycycles...

展开>> 收起<<

An Axiomatic Characterization of Split Cycle Yifeng Ding Wesley H. Holliday and Eric Pacuit Peking University yf.dingpku.edu.cn.pdf

共40页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

An Axiomatic Characterization of Split Cycle Yifeng Ding Wesley H. Holliday and Eric Pacuit Peking University yf.dingpku.edu.cn

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: