Kemeny-based criteria Strategyproof and efficient preference aggregation with Games and Economic Behavior

Contents lists available atScienceDirect

Games

and

Economic

Behavior

www.elsevier.com/locate/geb

Note

Strategyproof

and

efficient

preference

aggregation

with

Kemeny-based

criteria

Stergios Athanasoglou

1

IEFE,EconomicsDepartment,BocconiUniversity,Italy

a

r

t

i

c

l

e

i

n

f

o

a

b

s

t

r

a

c

t

Articlehistory:

Received24October2014 Availableonline17December2015

JELclassification: D71 C70 Keywords: Aggregationrule Strategyproofness Efficiency Kemenydistance

Supposeagroup of agents submitstrict linearorderings over aset of alternatives.An aggregationruleisafunctionmappingthisinformationintoauniquesocialordering.In arecent paper, Bossert and Sprumont (2014) introduced betweenness-basednotions of efficiency and strategyproofnessfor aggregation rulesand identifiedthree broadclasses of rules whichsatisfy them. The current paper suggests that such betweenness-based requirements may at times be too weak and introduces stronger concepts based on Kemeny distances,namely K -efficiency and K -strategyproofness. When there are three alternatives,all Condorcet–Kemenyrules are both K -efficient and K -strategyprooffor a largesubdomainofprofiles.Moreover,allstatus-quorulesare K -strategyproof,thoughnot K -efficient. Whenthe number ofalternativesexceedsthree none oftherulesdiscussed byBossertandSprumontsatisfies K -strategyproofness,whilejustCondorcet–Kemenyrules satisfyK -efficiency.TheexistenceofanondictatorialandontoK -strategyproofruleisan openquestion.

©2015ElsevierInc.All rights reserved.

1. Introduction

Suppose agroupofagentssubmitstrictlinearorderings(i.e.,complete,transitive,andanti-symmetric binaryrelations) over asetofalternatives.Anaggregationrule (alsoknownasanArroviansocialwelfarefunction)isafunctionmappingthis informationintoasingle“social”ordering,thatismeanttorepresentthegroup’saggregatepreferences.2

In contrastto other settingsof socialchoice (like, say,that ofselecting asingle winning alternativeon thebasis ofa set oforderings),strategic issueshave notbeen theobjectof extensivestudyinthe contextof aggregationrules.This is primarily becauseithasnotbeenclearhowtomodelindividualpreferencesoverorderingsofalternatives.Forinstance,if therearefouralternatives

{

a

,

b

,

c

,

d

}

andanagenthastheorderingabcd,3itisnotimmediatelyclearwhether,onthebasis of her ordering, sheprefers theoutcome acdb tobcda. As aresult, we cannot assesswhether thisagent wouldwish to somehowmisreportherpreferencesinordertochangeanaggregationrule’soutcomefromacdb tobcda.

One way ofdealing withthis issueis through a notion ofbetweenness discussed inGrandmont (1978). An ordering

R is said tobe between twoorderings R1 and R2,ifandonlyifit agreeswithboth R1 and R2 wheneverthelatter two agree. For instance,abcd isbetween adcb and bcad:the latter two orderings only agree on ordered pair

(

a

,

d

)

andthis

E-mailaddress:[email protected].

1 _{Iwouldliketothanktwoanonymousrefereesforinsightfulcommentsandusefulsuggestions.Theresearchleadingtotheseresultshasreceived}

fundingfromERCgrantNo.336703–projectRISICO.

2 _{Sincethispaperexclusivelydealswithstrictlinearorderings,fromnowonIusethesimplerterm“orderings”todenote“strictlinearorderings”.} 3 _{Here,asintherestofthepaper,orderingsaredenotedbystringsofalternatives,whereanalternative’spositioninthestringcorrespondstoitsrank.}

binary comparisonis respected inabcd.Inrecent works, Sato (2015)andBossert andSprumont (2014) usedthisnotion ofbetweenness toaddressstrategyproofnessinpreferenceaggregation.Intheirframeworks,aruleisdeemedstrategyproof if misreporting one’s ordering cannot lead to a new social ordering that is between that under truthful reporting and theagent’sownpreferences.Thispropertyamounts torequiringthatthe“truthful” socialorderingnot beunambiguously dominatedbythatproducedundermisreporting.Thisisaratherweakmeasureofnon-manipulabilityandIwillhenceforth refertoitasweakstrategypoofness.4BossertandSprumont (2014)employedsimilarbetweenness-basedreasoningtodefine an efficiencycriterion fororderings, whichIrefer toasweakefficiency.Intheirmodel,arulesatisfiesweakefficiencyifit alwaysgivesrisetoanorderingsuchthatthereexistsnootherthatunambiguouslydominatesitforallagents.

Sato (2015)demonstratedthat weakstrategyproofnesscombinedwithanaxiom ofso-calledboundedresponse leadsto a numberofimpossibility results.In hisframework, a ruleis saidto satisfy boundedresponse iftwo preferenceprofiles differingalongasinglebinary comparisonforasingleagentyieldapairofsocialorderingsdifferinginatmostonebinary comparison.Whileintuitiveasatechnicalcontinuitycheck,boundedresponseseemstolackastrongnormativejustification andisnotsatisfiedbymanycompellingrules.Incontrast,BossertandSprumont (2014)showedthat, absentSato’sstrong axiomofboundedresponse,arichsetofpossibilityresultsemerge.Theyrigorouslyanalyzedthreeweaklyefficientclasses ofruleswhichareconsistentwithweakstrategyproofness:monotonicmajorityalterationrules,status-quorules,andrules generalizingtheCondorcet–Kemenyrule (Kemeny,1959).

However, while weak strategyproofness allows for novel theoretical insights, I argue that it may set too high a bar formanipulability.Todemonstratehow itmayneedtobestrengthened,IexaminetheCondorcet–Kemenyrule andshow how itcan lead to situationsin which misreportingone’s preferences seemsto representa compelling course ofaction. Motivatedbythis“failure”oftheCondorcet–Kemenyrule,Isuggestthatitmaybeofinteresttoexamineastrongernotion of strategyproofness that is based on Kemeny (or Kendall-

τ

) distances, a commonly-used metric of the space of linear orderings (Kemeny, 1959; Kemeny and Snell,1962; Bogart, 1973). A related examination of the efficiency properties of status-quorulesindicatesthatweakefficiencymayalsoneedtobestrengthenedinananalogousKemeny-likefashion.

Thus,inmy framework,preferences overthespaceoforderings aremodeledvia Kemeny distances.Foranagent with ordering R,anordering R isstrictlypreferredto R ifandonlyitsKemenydistancefromR isstrictly smaller.Usingthis notionofpreferencesoverorderings,aruleissaidtobe K -strategyproof ifbymisreportingherpreferredorderinganagent cannot obtainanoutcome thatiscloser–intheKemeny sense –tohertrueordering. Usingthesamelogic,Bossert and Sprumont’s weakefficiencyrequirementcan be strengthenedvia theconcept of K -efficiency: anordering is K -efficient if there does not exist another ordering implying weakly smaller Kemeny distances for all agents, andstrictly smaller for some.AnancillarypropertyofK -efficiencyisthatitimplieslocalunanimity,wherethelatterensuresthatifthereexistsan alternativea thatallagentsprefertob,thenthesocialorderingshouldalsoranka aboveb.Bycontrast,localunanimityis logicallyunrelatedtoBossertandSprumont’sweakernotionofefficiency.

ThisKemeny-inspiredwayofmodelingagentpreferencesoverorderings,aswellasits effectonstrategicbehavior,was first studied by Bossert and Storcken (1992). Theyestablished impossibility results for rules satisfying an independence condition (extrema independence) andthe muchstronger property of K -coalitional-strategyproofness, whichrequires that nocoalitionofagentscanprofitablyjointlymisrepresentits preferences.Morerecently,othershavealsousedtheKemeny distanceasawaytomodelpreferencesover orderings (Baldiga,forthcoming; LaffondandLaine,2000; Laine etal., 2015; BaldigaandGreen,2013).Finally,astheproposedKemeny-basedmodeladmitsagraph-theoreticformulation,priorrelevant workcanalsobefoundintheliteratureondistance-basedpreferencesandstrategyprooflocation(Moulin,1980; Demange, 1982; Barberaetal.,1993; SchummerandVohra,2002).

Having introduced these Kemeny-based notions of efficiency and strategyproofness,the naturalnext question to ask is whether we can find any nontrivial rules that satisfy them. In the case of three alternatives, the answer is by and largeaffirmative:allCondorcet–Kemenyrules areboth K -strategyproofandK -efficientonalargesubdomainofpreference profiles. Moreover, status-quo rules, though not K -efficient, are K -strategyproofon the entireprofile domain.In marked contrast,whentherearefourormorealternativesthesepositiveresultsvanish.Indeed,allthreeclassesofrulesstudiedby BossertandSprumontviolateK -strategyproofnessandjustCondorcet–Kemenyrules satisfy K -efficiency.Theexistenceofa nondictatorialandonto(andthusnontrivial)K -strategyproofruleisanopenquestionworthyoffurtherstudy.

2. Modeldescription

Inwhatfollows,IadoptthenotationofBossertandSprumont (2014).Let A beafinitesetcontainingm

≥

3 alternatives. Let

N

denote the set of natural numbers, and let

N

denote the set of all finite nonempty subsets of

N

. Each N

∈

N

representsagroupofagents.

Agentssubmitstrictlinearorderings5overalternativesinA (i.e.,complete,transitive,andantisymmetricbinaryrelations) andthe set ofsuch preferences is denoted by

R

.Given N

∈

N

, the setof possiblepreference profiles forthat group is

given by

R

N. An aggregationrule is a function that assigns to each preference profile an ordering, i.e., it is a function

f

:



_N∈N

R

N

_→

_R

_.6

Let usnow introduce anotion ofbetweenness fororderings dueto Grandmont (1978).Forany R

,

R

,

R

∈

R

,we say that R isbetween R and R,andwriteR

∈ [

R

,

R

]

,ifandonlyifR

∩

R

⊆

R.Thatis,ordering R agreeswithboth R and Rwheneverthelattertwoagree.

Bossert andSprumont (2014)define theprudentextension ofanordering R

∈

R

asthebinary relationR overorderings givenby

RR R

⇔

R

∈ [

R

,

R

],

for all R

,

R

∈

R

.

Hence,foranagentholdingtheordering R,R isatleastasgoodasRifandonlyifRisbetweenR andR.Therelation

R isastrictquasi-ordering(i.e.,areflexive,transitive,andantisymmetricbinaryrelation)thatisnotcomplete.

Thus, givenan agent i’s statedordering Ri

∈

R

andtwo orderings R

=

R,the expression RRiR impliesthat R is

unambiguouslydominatedby Rforagent i.Tobesure,suchunambiguousdominancewillholdonlyforarestrictedsetof pairs oforderings,whichisresponsibleforRi’sgeneric incompleteness.Itnaturally leadstotheconceptsofefficiencyand

strategyproofnessemployedbyBossertandSprumont (2014),towhichIaddthequalifier“weak”.

Weakefficiency. TheredonotexistN

∈

N

, RN

∈

R

N,andR

∈

R

suchthatR

∈ [

Ri

,

f

(

RN

)

]

foralli

∈

N and R

=

f

(

RN

)

. Weakstrategyproofness. There donotexist N

∈

N

, RN

∈

R

N

_,

_i

_∈

_{N and R}

i

∈

R

such that f

(

Ri

,

RN\{i}

)

∈ [

Ri

,

f

(

RN

)

]

and f

(

R_i

,

RN_\{i}

)

=

f

(

RN

)

.

Weakefficiencysetsforthaminimalstandardofefficiency,imposingthattherenotexistanorderingthatunambiguously dominatestheselectedoneforallagents.Similarly,weakstrategyproofnessrequiresthat,bymisreportingone’sordering,it shouldnotbepossibleforanagenttoobtainasocialorderingthatunambiguouslydominates(withrespecttothatagent’s trueordering)thatundertruthfulreporting.

An additional property that Bossert and Sprumont discussis that of localunanimity,which is relevant forpreference profilesinwhichthereisunanimousagreementovercertainbinarycomparisons.

Localunanimity. ForallN

∈

N ,

RN

∈

R

N _wehave



i∈NRi

⊆

f

(

RN

)

.

Bossert andSprumont identified three broadclassesof rules that satisfy weakefficiency andweakstrategyproofness: (i) Condorcet–Kemenyrules andtheirsuitablegeneralizations;(ii)monotonicmajorityalterationrules;and(iii)status-quo rules.Theyalsoprovidednovelcharacterizationofrules(ii)and(iii).Finally,BossertandSprumontdemonstratedthatthe well-knownBordaandCopelandrulesfailtosatisfyweakstrategyproofness,andarethusextremelyvulnerabletostrategic manipulation.

TofixideasandaidthereaderinunderstandingthecontributionofBossertandSprumont (2014),weprovidedefinitions oftheaforementionedrules(i)–(ii)–(iii).

(i) Condorcet–Kemenyrules. Originating in the writings of the Marquis de Condorcet, these rules were formalized by

Kemeny (1959) andaxiomatized by Young andLevenglick (1978) and Young (1988). Giventwo orderings R

,

R

∈

R

, definetheirdisagreementset,denotedbyD

(

R

,

R

)

,

D

(

R

,

R

)

= (

R

\

R

)

∪ (

R

\

R

),

whichincludesallbinarycomparisonsonwhichR andRdisagree.TheKemenydistance (or,alternatively,Kendall-

τ

distance) betweenR and R,denotedby

δ(

R

,

R

)

,isdefinedas

δ(

R

,

R

)

= |

D

(

R

,

R

)

|.

Let



beastrictorderingon

R

.Forall N

∈

N

andRN

∈

R

N,let K

(

RN

)

=

arg min

R∈R



i∈N

δ(

R

,

Ri

).

(1)

The



-Condorcet–Kemenyrule is defined asthe aggregation rule which assigns to each N

∈

N

and RN

∈

R

N _{the strict}

ordering belonging to K

(

RN

)

ranked firstaccording to



. Bossert andSprumont also considered generalizedversions of Condorcet–Kemeny rules,in whichdisagreements over binary comparisons are givenarbitrarypositive weights that may varyacrossagents,andshowedthattheytoosatisfyweakstrategyproofness.

6 _{UnlikeBossertandSprumont (2014)whoallowforrulesproducingweakorderings(complete,reflexive,transitivebinaryrelations)andthenconsider}

(ii) Monotonicmajorityalterationrules. Given N

∈

N

andRN

∈

R

N,themajorityrelation M

(

RN

)

on A is acompleteand

antisymmetricbinaryrelationdefinedby

a M

(

RN

)

b

⇔ |{

i

∈

N

:

aRib

}| ≥ |{

i

∈

N

:

bRia

}| ,

forall

(

a

,

b

)

∈

A

×

A. Clearly,themajorityrelation canfail tobe transitiveandthusmaynot always leadtoan ordering. Amonotonicmajorityalterationrule alters themajorityrelationtoobtainatransitive relation(andthusaunique ordering) in a way that is agreement-monotonic (for detailed definitions see Section 4 in Bossert andSprumont, 2014). Two such agreement-monotonic alterations are (a) lexicographicalterations in which intransitivities are addressedin a step-by-step manneraccordingtoanexogenousstrictorderingoversetsofpairsofalternatives(seeExample3inBossertandSprumont, 2014)and(b)Slateralterations inwhichintransitivitiesareaddressedbychoosingtheorderingthathasthesmallestKemeny distancefromthemajorityrelation,wheretiesarebrokenaccordingtoanexogenousstrictorderingover

R

(seeExample 4inBossertandSprumont,2014).

(iii) Status-quorules. Status-quorulesaredesignedtoimproveuponanexogenouslygivenordering,whichinturnismeant torepresentastatus-quosolution.Beforeprovidingaformaldefinition,afewadditionalconceptsneedtobeintroduced. Given R0

_∈

_R

_{andits prudent extension R}0_{,Guilbaud andRosenstiehl (1963)proved that}

_(R,

_R0

₎

_{is alattice so that} every collection

{

R1

,

R2

,

. . . ,

RT

}

⊆

2R hasaunique minimalcommonupperbound, i.e., aunique ordering R

∈

R

such that

R R0Rt

,

for all t

∈ {

1,2, . . . ,T

},

(2)

and



RR0Rt

,

for all t

∈ {

1,2, . . . ,T

}



⇒

RR0R

.

(3)

Therule f is astatus-quo rule associatedwithordering R0

∈

R

if, forall N

∈

N

andRN

∈

R

N, f

(

RN

)

equals theunique

orderingsatisfyingEqs.(2)–(3)foralltheorderingsin RN.Wedenotesucharule f bySQR0.

Status-quo rules admit concise reformulations via Kemeny distances. For any two orderings R

,

R

∈

R

we have (seeBossertandStorcken,1992):

RR0R

⇔

R

∈ [

R0

,

R

] ⇔

R

∈ {

R

∈

R

: δ(

R0

,

R

)

+ δ(

R

,

R

)

= δ(

R0

,

R

)

}.

(4)

Now,Eqs.(2)–(4)implythatthestatus-quoruleassociatedwithR0_{canberewrittenas:} SQR0

(

RN

)

=

arg max

R∈i∈N[Ri,R0]

δ(

R0

,

R

).

(5)

Finally,usingEqs.(4)–(5)wefurtherobtain:

SQR0

(

RN

)

=

arg max R∈i∈N[Ri,R0]

δ(

R0

,

R

)

=

arg max R∈i∈N[Ri,R0]

δ(

Ri

,

R0

)

− δ(

R

,

Ri

),

∀

i

∈

N

=

arg max R∈i∈N[Ri,R0]

δ(

R

,

Ri

),

∀

i

∈

N

.

(6)

2.1. Thelimitationsofbetweenness-basedconcepts

Whilethe introductionofweak strategyproofnessisa conceptualbreakthrough thatleads tonovel insights,it is intu-itivelyclearthatitmaysometimesplacetoohighabarformanipulability.Asitisbasedontheprudentextensionofagents’ orderings(anincompleterelation)itwillfrequentlynottakeastandonthedesirabilityofmisreportinginordertoobtain one ordering over another. Similar problems persist withregard to weak efficiency andthe desirability of one ordering versusanother.

Thefollowingtwoexamplesillustratethesepotentiallimitationsofweakstrategyproofnessandefficiency.

Example1(Thelimitationsofweakstrategyproofness).Suppose A

= {

a

,

b

,

c

,

d

,

e

,

f

}

andN

= {

1

,

2

,

3

,

4

,

5

,

6

,

7

}

andwehavethe followingpreferenceprofileRN appearinginTable 1:

Consider now the Condorcet–Kemenyrule with a randomly assignedordering



on

R

.Let usdenotethis ruleby g.

Doingsomealgebra,we have K

(

RN

)

=

c f bdae sothat g

(

RN

)

=

c f bdae.7 Letusidentifythepairsofalternativesonwhich R1andg

(

RN

)

disagree:

Table 1

Limitationsofweakstrategyproofness.

i Ri 1 bf deca 2 bdae f c 3 f bdaec 4 cbdae f 5 dc f eab 6 ce f bda 7 aec f bd Table 2

Limitationsofweakefficiency(boxesdrawattentiontokeypairs ofalternatives). i Ri 1 a2a1 a3. . .am−1am 2 a1 a3a2 a4. . .am−1am . . . . . . m−2 a1a2a3. . .am−3 am−1am−2 am m−1 a1a2a3. . .am−3am−2 amam−1 D

(

R1

,

g

(

RN

))

= {(

b

,

c

), (

d

,

c

), (

e

,

c

), (

f

,

c

), (

b

,

f

), (

e

,

a

)

}.

Hence,weseethatthesocialorderingplacesalternativec first,whichhoweverisagent1’ssecond-to-lastrankedalternative. Moreover, it reverses the order of pairs

(

b

,

f

)

and

(

e

,

a

)

. In total, the ordering g

(

RN

)

disagrees with R1 on sixbinary comparisons.

Suppose now that voter 1 misreports her preferences by stating R₁

=

af bedc. Then, algebraic calculations yield

K

(

R₁

,

RN

N\{1}

)

=

f bdaec

=

g

(

R1

,

RNN\{1}

)

.Asaresult,thepairsonwhichR1 andg

(

R1

,

RN\{1}

)

disagreeare: D

(

R1

,

g

(

R1

,

RN\{1}

))

= {(

c

,

a

), (

b

,

f

), (

e

,

a

)

}.

Ihavehighlightedinbold thecommonelements ofthetwodisagreementsets.Comparedtotruthfulreporting,thesocial ordering undermisreportingstill clasheswith1’s preferencesregardingpairs

(

b

,

f

)

and

(

e

,

a

)

.However, byrankingc last

instead offirst,it hasreplacedthe previous disagreementover pairs

(

b

,

c

),

(

d

,

c

),

(

e

,

c

),

(

f

,

c

)

,witha single disagreement over

(

c

,

a

)

,i.e.,theorderofhertwoleast-preferredalternatives.

Clearly, g

(

R₁

,

RN\{1}

)

∈ [

/

R1

,

g

(

RN

)

]

, so that misreportingdoes not unambiguously dominate truthfulness for agent 1.

However,itisplausiblethatagent1willpreferasocialorderingwhichresultsinthree,asopposedtosix,disagreeingpairs ofalternatives.

Example2(Thelimitationsofweakefficiency).Suppose A

= {

a1

,

a2

,

. . . ,

am

}

form

≥

3,N

= {

1

,

2

,

. . . ,

m

−

1

}

,andwehavethe preferenceprofilelistedinTable 2.8

Let R0

=

amam₋1

...

a2a1 andconsider the associated status-quo rule SQR

0

. For all i

∈

N we have

[

Ri

,

R0

]

= {

R

∈

R

:

(

ai+1

,

ai

)

∈

R

}

.Thus, it is easy to seethat



i∈N

[

Ri

,

R0

]

=

R0,so that SQR

0

(

RN

)

=

R0.As the rulesatisfies weak efficiency,

we are not surprised to find that



i∈N



Ri

,

SQR 0

(

RN

)



=

SQR0

(

RN

)

implying that the ordering SQR

0

(

RN

)

is undominated.

However, note that we have

δ



Ri

,

SQR 0

(

RN

)

=

m 2



−

1 for all i

∈

N, sothat withregard toevery agent’spreferences Ri

thechosenorderingdisagreesonallbinarycomparisonsbutone.Moreover,observethatwehave



i∈N

Ri

= {(

ak

,

al

)

:

k

,

l

∈

N

,

l

>

k

+

1

}



R0

=

SQR0

(

RN

)

.Indeed,



i∈N

Ri

∩

R0

= ∅

.Evidently,theruleSQR0

(

RN

)

violateslocalunanimityinasignificant way.

Now,considertheorderingR

=

a1a2

...

am−1am,i.e.,theexactoppositeof R0.Herewehave

δ(

Ri

,

R

)

=

1 foralli

∈

N,so

that Rdiffersalongasinglebinarycomparisonwithregardtoall Ri.Thisorderingrespectslocalunanimityandseemslike asignificantlymoreappealingoutcomeforallagentsinN,especiallyformediumorrelativelyhighvaluesofm.

3. Alternativeconceptsofefficiencyandstrategyproofness

Examples1 and2highlighttheweaknessofbetweenness-basedefficiencyandnon-manipulabilitycriteria.Theyfurther suggestthat aproblematic featureofsuchcriterialiesintheir insensitivityto theconsiderationofall binarycomparisons when deciding betweenorderings, not just thoserelated to unambiguous dominance.Using Kemeny distances,one may strengthenBossertandSprumont’sconceptsofstrategyproofnessandefficiencyinamannerthataddressestheseconcerns.

K -strategyproofness. Theredonotexist N

∈

N

,RN

∈

R

N

,

i

∈

N andR_i

∈

R

suchthat

δ(

f

(

R_i

,

RN\{i}

),

Ri

)

< δ(

f

(

RN

),

Ri

)

.

K -efficiency. There donot exist N

∈

N

, RN

∈

R

N,and R

∈

R

such that

δ(

R

,

Ri

)

≤ δ(

f

(

RN

),

Ri

)

for all i

∈

N andthere

existsatleastone j

∈

N suchthat

δ(

R

,

Rj

)

< δ(

f

(

RN

),

Rj

)

.

Example 1showsthat theCondorcet–Kemenyrule failsK -strategyproofness ina significantwaysince

δ(

f

(

R₁

,

RN\{1}

),

Ri

)

=

3

<

6

= δ(

f

(

RN

),

R1

)

. Similarly, Example2demonstrates how status-quo rulescan resultin outcomesthat are ex-tremelyK -inefficient.

ThefollowingpropositionscollectafewstraightforwardimplicationsofK -efficiencyandK -strategyproofness.

Proposition1.IfarulesatisfiesK -efficiencythenitsatisfiesweakefficiency.

Proof. Suppose rule f does not satisfy weak efficiency. Then there exists RN

∈

R

N _{and R}

_∈

_R

_{such that R}

₌

_f

₍

_R N

)

and R

∈ [

Ri

,

f

(

RN

)

]

forall i

∈

N. Notehowever,that, foranyi

∈

N, if R

=

f

(

RN

)

and R

∈ [

Ri

,

f

(

RN

)

]

then D

(

Ri

,

R

)

⊂

D

(

Ri

,

f

(

RN

))

.Hencewewillhave

δ(

Ri

,

R

)

< δ(

Ri

,

f

(

RN

))

foralli

∈

N,thusviolating K -efficiency.

2

Bossert andSprumont showed that weak efficiency is logically unrelated to local unanimity. This does not hold for

K -efficiency.

Proposition2.IfarulesatisfiesK -efficiencythenitsatisfieslocalunanimity.

Proof. Follows by the proof of a stronger version of its contrapositive outlined in Remark 5 in Bossert and Sprumont (2014).

2

It shouldbe notedthat theopposite directionofProposition 2doesnot hold. Forinstance,consider N

= {

1

,

2

,

3

}

and

R1

=

bcad

,

R2

=

abcd

,

R3

=

badc. Since we have

δ(

R1

,

R2

)

= δ(

R1

,

R3

)

= δ(

R2

,

R3

)

=

2, theset of K -efficientorderings is easily seentobe

{

R1

,

R2

,

R3

,

bacd

}

.Meanwhile,we have



i∈N

Ri

= {(

b

,

c

),

(

b

,

d

),

(

a

,

d

)

}

sothat thesetoflocallyunanimous

rankings is

{

R1

,

R2

,

R3

,

bacd

,

abdc

}

.Thus, ifa rule f sets f

(

RN

)

=

abdc it willviolate K -efficiency withoutviolatinglocal unanimity.

Proposition3.IfarulesatisfiesK -strategyproofnessthenitsatisfiesweakstrategyproofness. Proof. IdenticaltoProposition 1.

2

4. Mainresults

HavinglaidouttheconceptsofK -efficiencyandK -strategyproofnessintheprevioussection,canwefindanynontrivial (i.e.,non-dictatorial andonto) rule thatsatisfies them? Anaturalwayto startthisinquiry isby drawing onthe workof

BossertandSprumont (2014)andexaminingthethreebroadclassesofrulesthatthey provedsatisfyweak strategyproof-ness.

Wedistinguishbetweentwocasesregardingthenumberofalternatives:m

=

3 andm

>

3.As wewillseeshortly,this distinctionturnsouttobeimportant.

4.1. Thecasem

=

3

ThefollowingTheoremestablishesthatallCondorcet–Kemenyrules areK -strategyproofwhenthenumberofalternatives isthreeandwearedealingwitharestricteddomainofprofilesthatprecludestheexistenceofelectoratesthatareperfectly splitwithrespecttoall binarycomparisonsofalternatives.Formally,thisprofilesubdomainisdenotedby

K

andsatisfies

K

=



RN

∈

R

N

:

N

∈

N

and

∃(

a

,

b

)

∈

A

×

A s.t.

|{

i

∈

N

:

aRib

}| > |{

i

∈

N

:

bRia

}|

Table 3

NoCondorcet–Kemenyor Slaterrule isK -strategyproofwhenm>3. i Ri 1 dcba 2 dacb 3 bdac 4 cbda 5 abcd

Theorem1.Considertherestricteddomainofprofiles

K

.Onthisdomain,allCondorcet–Kemenyrules satisfyK-strategyproofness whenm

=

3.Inparticular,thisimpliesthatallCondorcet–Kemenyrules areK -strategyproofwhenm

=

3 and

|

N

|

isodd.

Proof. SeeAppendixA.1.

2

The intuition behind the proof of Theorem 1 is straightforward. Recall that all Condorcet–Kemeny rules are weakly strategyproof (Bossert andSprumont, 2014). When thereare justthree alternatives thisimpliesthat K -strategyproofness

can be violated only if there exists an agent for which (i) the social ordering undertruthfulness results in exactly two disagreeing binary comparisons and; (ii) the ordering obtained when this agent misreports his preferences is its exact opposite. Byfirstprinciplesthisisshowntobeimpossible,unlessthetruthfulormisreportingpreferenceprofiledoesnot belongin

K

[meaningthatallorderingshaveidenticalKemenyscoresasperEq.(1)].9

SinceCondorcet–Kemenyrules arebydefinitionK -efficient,acorollarytoTheorem 1isthat,intherestricteddomain

K

, thereexistsaK -efficientandK -strategyproofrulewhenm

=

3.

Ontheotherhand,Theorem 2establishesthatallstatus-quoruleswillsatisfy K -strategyproofnesswhenm

=

3 without theneedforanydomainrestrictions.However,thisgaininnon-manipulabilitycomesatasignificantcosttoefficiency.

Theorem2.Whenm

=

3 allstatus-quorulessatisfyK -strategyproofness.Conversely,nonesatisfylocalunanimityandthusalso K -efficiency.

Proof. SeeAppendixA.1.

2

The proof ofTheorem 2 is simple.The K -strategyproofness of status-quo rules is established by recalling their weak strategyproofness(BossertandSprumont,2014) andenumeratingallsixpossiblechoicesforthestatus-quoordering. Con-versely,theviolationoflocalunanimitycanbeeasilyseenbyreferringtoExample2form

=

3.

4.2. Thecasem

>

3

Incontrasttothecaseofthreealternatives,whenm

>

3 allpositiveresultsonK -strategyproofnessquicklyvanish.

Proposition4.NoCondorcet–Kemeny,Slatermajority-alteration,orstatus-quorulesatisfiesK-strategyproofnessform

>

3.

Proof. Let g beaCondorcet–Kemenyrule withanyordering



.Suppose A

= {

a

,

b

,

c

,

d

}

andN

= {

1

,

2

,

3

,

4

,

5

}

andwehave thepreferenceprofile RN showninTable 3.

Here, it iseasy to verifythat K

(

RN

)

=

bdac, so g

(

RN

)

=

bdac. Consider now voter 1.We have

δ(

R1

,

g

(

RN

))

=

3. Sup-pose now that voter 1 changes her preferences to R₁

=

cdba, by simply flippingthe positions of adjacent alternatives c

and d.Then,wemayverifythat K

(

R₁

,

RN_\{1}

)

=

cbda,sog

(

R₁

,

RN_\{1}

)

=

cbda,leadingto

δ(

R1

,

g

(

R1

,

RN\{1}

))

=

2.Thus,all



-Condorcet–Kemenyrules willfail K -strategyproofness.

Let us now turn to Slaterrules. Computing the majority relations corresponding to profiles RN and

(

R₁

,

RN_\{1}

)

, we obtain: M

(

RN

)

= {(

a

,

c

),

(

b

,

a

),

(

b

,

d

),

(

c

,

b

),

(

d

,

a

),

(

d

,

c

)

}

and M

(

R₁

,

RN\{1}

)

= (

M

(

RN

)

\ {(

d

,

c

)

}) ∪ {(

c

,

d

)

}

. Using them it is easy to see that every Slater majority-alteration rule f , regardless of its ordering



, will also yield f

(

RN

)

=

bdac and

f

(

R₁

,

RN\{1}

)

=

cbda andthusalsofail K -strategyproofness.10

Finally,we addressstatus-quorules.Consider theprofileofExample 2andthecorresponding status-quoruleSQR0 _for R0

₌

_a

mam−1

...

a2a1.RecallthatSQR

0

(

RN

)

=

R0.Focusonagent1andsupposeshesubmitsorderingR1

=

a1amam−1

. . .

a3a2 insteadofhertruthfulpreferences R1

=

a2a1a3

...

am−1am.Thenwehave

9 _{NotethatSlaterandlexicographicalterationrules,beingbasedonthemajorityrelation,willencountersimilarproblemsforprofilesR}

N∈ K/ as delin-eatedintheproofofTheorem 1.

Table 4

SlaterrulesviolateK -efficiency.

i Ri i Ri 1 dcab 5 cdab 2 abcd 6 cdab 3 abcd 7 dbca 4 abcd 8 bdac

⎛

⎝



i∈N\{1}



Ri

,

R0



⎞

⎠ ∩ [

R₁

,

R0

] =

R0

∪ {

R∗_j

:

j

=

1,2, . . . ,m

−

1

},

where(boldfontsplacedforemphasis):

R∗₁

=

a1amam−1

. . .

a2

=

R1

R∗_j

=

amam−1

. . .

am−j+2a1am−j+1

. . .

a4a3a2

,

j

=

2,3, . . . ,m

−

1. Then,applyingEq.(5)toprofile

(

R₁

,

RN\{1}

)

obtains

SQR0

(

R₁

,

RN\{1}

)

=

R₁

.

Whenm

>

3 thisviolates K -strategyproofnesssince,

δ(

R1

,

SQR

0

(

RN

))

=

m 2



−

1

> δ(

R1

,

SQR 0

(

R₁

,

RN\{1}

))

=

m 2



− (

m

−

2

)

, form

>

3.

Now takean arbitraryordering R

˜

0 andconstructaprofile R by

˜

takingtheoneinTable 2 andrelabelingam₋k+1

← ˜

ak fork

=

1

,

2

,

. . . ,

m.Anidenticalargumenttotheaboveshowsthatthemisreport R

˜

₁

= ˜

ama

˜

1a

˜

2

. . .

am

˜

−2am

˜

−1 isprofitablefor agent1whenm

>

3.Thisestablishesthatnostatus-quorulecanbe K -strategyproofwhenm

>

3.

2

BossertandSprumont (2014)showedthat Slatermajority-alterationrulesare weaklyefficientaswell aslocally unani-mous.However,thefollowingpropositiondemonstratesthattheyfailtobe K -efficientwhenm

>

3.

Proposition5.NoSlatermajority-alterationruleisK -efficientform

>

3.

Proof. Let h be a Slater majority-alterationrule withan ordering



to be specified shortly.Suppose A

= {

a

,

b

,

c

,

d

}

and

N

= {

1

,

2

,

3

,

4

,

5

,

6

,

7

,

8

}

andwehavethepreferenceprofileRN showninTable 4.

There are 4 orderings that are minimal with respect to total Kemeny distance from the majority relation M

(

RN

)

=

{(

a

,

b

),

(

a

,

c

),

(

b

,

c

),

(

b

,

d

),

(

c

,

a

),

(

c

,

d

),

(

d

,

a

),

(

d

,

b

)

}

,namely R

=

abcd, R

=

bcda, R

=

cdab and R

=

dabc. Letussuppose



is such that R is ranked first. Then, h

(

RN

)

=

R

=

bcda. However, it is easy to see that

δ(

Ri

,

R

)

= δ(

Ri

,

R

)

forall i

∈

N

\ {

1

}

and

δ(

R1

,

R

)

=

2

<

4

= δ(

R1

,

R

)

,implyingthatallsuch



-Slaterrulesarenot K -efficient.

Nowtakea



-Slaterrule,callitagainh,suchthatanarbitraryorderingon A,a1a2a3a4,isrankedfirstin



.Constructa profile RN

˜

bytakingtheoneappearinginTable 4andrelabelingb

←

a1,c

←

a2,d

←

a3 anda

←

a4.Repeatingtheabove argumentweseethath

( ˜

RN

)

=

a1a2a3a4 whichis K -dominatedbyorderinga3a4a1a2.

Sincetheorderinga1a2a3a4 isarbitrary,theaboveestablishesthatall



-Slaterrulesfail K -efficiencyform

>

3.

2

Remark1.Letusnowaddress thepropertiesoflexicographicmajority-alterationrules. Theresultswe obtainare qualita-tivelysimilartothoseabove.Withregardtostrategyproofness,considertheprofileofTable 3andthesamemisreportasin theproofofProposition 4.Definerule f asalexicographicmajority-alterationrulewithanordering



overpairsof alterna-tivessuchthat

{

c

,

d

}

 {

a

,

d

}

 {

a

,

c

}

 {

b

,

d

}

 {

b

,

c

}

 {

a

,

b

}

.Afewstraightforwardcalculationsshowthat f

(

RN

)

=

bdac and f

(

R₁

,

RN\{1}

)

=

cbda,andthus f willalsofail K -strategyproofness.Meanwhile,asregardsefficiency,BossertandSprumont (2014) show thatwhenm

>

3 thereexist lexicographicmajoritymonotonic rules thatfail localunanimity(see Remark 3 inBossertandSprumont,2014)andthusbyProposition 2 also K -efficiency.Isuspect thatboth oftheabove negative re-sultscanbeextendedtoall lexicographicmajority-alterationrulesbyajudiciousrelabelingofalternativesandsubsequent considerationofthetransformedprofiles,inmuchthesamewayastheproofsofPropositions 4 and 5.Theargumentwould likelybemoreelaboratethough,sincethereare

m₂



!

orderingsofpairsofalternatives.Inanyevent,theaboveremarksshow thatlexicographicalterationrulesfallpreytoviolationsofbothstrengthenednotionsofefficiencyandstrategyproofness.

Remark2.AninterestingcandidateforaK -efficientandK -strategyproofruleisthefollowingfamilyofrules,whichIdenote asRawlsian.GivenN

∈

N

, RN

∈

R

N andR

∈

R

,considerthe

|

N

|

-dimensionalvector

δ

∗

(

R

,

RN

)

=

δ

1

(

R

,

RN

), δ

2

(

R

,

RN

), . . . , δ

|N|

(

R

,

RN

)



,

whose elements are equal to the elements of set

{δ(

R

,

Ri

)

:

i

∈

N

}

listed in decreasing order. That is,

δ

1

(

R

,

RN

)

is the

maximumvalueof

δ(

R

,

Ri

)

pickoneatrandom).Then,

δ

2

(

R

,

RN

)

isthemaximumoftheremaining

δ(

R

,

Ri

)

’sexcludingthat

ofagent i1,anditcorrespondstosomeagent i2

∈

N

\ {

i1}(similarly,iftherearetwoormoreagentsbelongingto N

\ {

i1} thatattainthemaximumvalueoftheremaining

δ(

R

,

Ri

)

’s,pickoneatrandom).Usingsimilarrecursivelogicwecandefine allother

δ

k

(

R

,

RN

)

andikupuntilk

= |

N

|

.

Let



denoteastrictorderingontheelementsof

R

.ForN

∈

N

andRN

∈

R

N,define Rw

(

RN

)

=

arg minlex

R∈R

δ

∗

₍

_R

_,

_R

N

).

(7)

Thatis,Rw

(

RN

)

denotesthesetoforderingsthatarethelexicographic-minimizersofthevector-valuedfunction

δ

∗

(

·,

RN

)

:

R

→ 

|N|_{. The}



_{Rawlsianrule is the aggregation rule which assigns to each N}

_∈

_N

_{and RN}

_∈

_R

N _{the strict ordering}

belongingtoRw

(

RN

)

rankedfirstaccordingto



.

Consistent to Rawls’ principlesof justice, Rawlsian rules search for an ordering that minimizesthe discontent of the worst-off agents in N. Ifthere areseveral such orderings, thenthey focus on minimizing thediscontent ofthe (weakly) secondworst-off,andsoon.Thisattentionontheleastfortunateagentsisindicativeofacertainsortoffairness.

Clearly, all



-Rawlsianrules are K -efficient.However, their desirablefairnessandefficiencypropertiescomeatahigh price, asthefollowingexampleshowsthat noRawlsianrulecan everbeweakly strategyproof,evenwhen m

=

3.Towit, let g beaRawlsian rulewithanyordering



.Suppose A

= {

a

,

b

,

c

}

andN

= {

1

,

2

,

3

}

andconsidertheprofile RN,where

R1

=

R2

=

bca and R3

=

abc. It is clear that there is justone ordering that attains the arg minlex of Eq. (7)applied to profile RN,namelybac,so Rw

(

RN

)

=

g

(

RN

)

=

bac.Suppose nowthatagent 1changes her preferencesto R1

=

cba.Then, afew briefcalculationsestablishthatRw

((

RN_\{1}

,

R₁

))

=

bca

=

g

((

RN_\{1}

,

R₁

))

.Thus,weakstrategyproofnessisviolatedno matterhowtheordering



ischosen.

2

4.3. RelationtoBossertandStorcken(1992)

As mentioned in the introduction, Bossert andStorcken (1992) were the first to consider Kemeny-based concepts of strategyproofnessforaggregationrules.Theiranalysisemployedastrongerversionofnon-manipulability, K -coalitional strat-egyproofness,whichextends K -strategyproofnesstostrategicbehaviorinvolvingcoalitionsofagents.Moreover,Bossertand Storckenintroducedtwoversions(oneweak,onestrong)ofanindependenceconditionknownasextremaindependence. Ex-tremaindependenceanditsweakcounterpartaretechnicalrequirementsthatensurerobustnesstospecialkindsofchanges in extremepreferences.(Itisstraightforwardto seethatstatus-quo rulessatisfy extrema independencewhile monotonic-majority-alterationandCondorcet–Kemenyrules violatethestrongversionwhilesatisfyingtheweak.)

Whenm

>

3,BossertandStorckenshowedthatextremaindependenceisincompatiblewithK -coalitional strategyproof-ness,unlesswearewillingtoentertaintrivialrules.Theorem 3summarizesthisresult.

Theorem3.(SeeBossertandStorcken,1992.)Supposem

>

3.ThereexistsnoontorulesatisfyingK -coalitionalstrategyproofnessand extremaindependence.If

|

N

|

iseven,thereexistsnoontorulesatisfyingK -coalitionalstrategyproofnessandweakextrema indepen-dence.

Bossert andStorcken’simpossibility resultis clearly relevantto theinquiry ofthispaper.For example,itimpliesthat alltherulesexaminedbyBossertandSprumont (2014)donotsatisfy K -coalitionalstrategyproofness.Yet,therelevanceof

Theorem 3toourcontextistemperedbythefactthat K -coalitionalstrategyproofnessisaverysignificantstrengtheningof

K -strategyproofness.Insistingon itwouldnullifyeventhe fewpossibilityresultsthiswork hasbeenableto establish.In particular,whenm

=

3 allstatus-quorulesandallCondorcet–Kemenyrules (evenwhen,inthecaseofthelatter,

|

N

|

isodd andthereforethedomainrestriction

K

ofTheorem 1isautomaticallysatisfied)willfailK -coalitionalstrategyproofness(see inAppendixA.2).

5. Conclusion

This paper has been concerned with Arrovianpreference aggregation. In this setting strategic behavior had not, un-til the recent works of Bossert and Sprumont (2014) and Sato (2015), been the object of much systematic study. But whiletheintroductionofbetweenness-basednotionsofefficiencyandstrategyproofnessbytheseauthorswasaconceptual breakthroughleadingtointerestingtheory,wehavedemonstratedthattheymayattimesleadtounsatisfyingconclusions. This in turn prompted the introduction of stronger requirements based on Kemeny distances, namely K -efficiency and

K -strategyproofness,andthesearchforrulesthatmaysatisfythem.

Letusbrieflyrecapthepaper’smainresults.Whentherearethreealternatives,allCondorcet–Kemenyrules (which are generically K -efficient) are K -strategyproofina restricted,butstillquite broad,profiledomain.Conversely, allstatus-quo rulesare K -strategyproof,butfaillocalunanimityandthereforealsoK -efficiency.

These positive results regarding K -strategyproofness vanish when m

>

3, as all three classes of rules considered by

Table 5

Rulesandtheirpropertiesform>3.Simple“yes”and“no”entriesmeanthattheresultholdsforallmembersoftherespectiveclass.Anasteriskindicates thattheresulthasbeenestablishedforsome,butnotnecessarilyall,membersoftherespectiveclass.

Cond.–Kem. Status quo Slater alteration Lex. alteration Rawlsian

Weak efficiency yes yes yes yes yes

Weak strategyproofness yes yes yes yes no

Local unanimity yes no yes no* yes

K -efficiency yes no no no* yes

K -strategyproofness no no no no* no

When m

=

3,the existence of a non-dictatorial, K -efficient (oreven locally unanimous), and K -strategyproof ruleon theunrestricteddomainofprofilesisanopen question.Similarly,whenm

>

3 theexistenceofanon-dictatorial andonto

K -strategyproof rule remains unsettled. Addressing these questions in a definitive manner is a topic worthy of further research.

Whilewedonotknowtheanswertotheabovequestions,thefactthatallweaklystrategyproofclassesofrulesexamined byBossert andSprumonthavenot beensuccessfulsuggeststhatmilderstrengtheningsofweakstrategyproofnessmaybe neededtoachievegeneralpossibilityresults.Whattheseadjustedrequirementsmaylooklikeisnotclear.

Appendix A

A.1. Proofsnotappearinginmaintext

Theorem1. Supposeg isaCondorcet–Kemenyrule withordering



.LetA

= {

a

,

b

,

c

},

N

∈

N

andRN

∈

R

N_{.Suppose,without}

loss ofgenerality, that voter i’s preferencesare givenby Ri

=

abc andthat there exists R_i

∈

R

such that

δ(

Ri

,

g

(

RN

))

>

δ(

Ri

,

g

(

R_i

,

RN\{i}

))

.Wedistinguishbetween4cases:

(i)

δ(

Ri

,

g

(

RN

))

=

0.Butsince0

≤ δ(

Ri

,

R

)

forall R

∈

R

,weimmediatelyreachacontradiction.

(ii)

δ(

Ri

,

g

(

RN

))

=

1.Then,wemusthave

δ(

Ri

,

g

(

Ri

,

RN\{i}

))

=

0.Hence, Ri

=

g

(

R_i

,

RN_\{i}

)

.Thisimpliesthatrule g isnot weaklystrategyproofwhichcontradictsProposition5inBossertandSprumont (2014).

(iii)

δ(

Ri

,

g

(

RN

))

=

3. Then,we musthave

δ(

Ri

,

g

(

R_i

,

RN\{i}

))

<

3. Let Ri

˜

denotethe orderingwhich isexactlythe oppo-siteof Ri (which reverses the direction of all binary comparisons). Then, it must be the casethat g

(

RN

)

= ˜

Ri and g

(

R_i

,

RN\{i}

)

= ˜

Ri.Thisagaincontradictstheweakstrategyproofnessofg.

(iv)

δ(

Ri

,

g

(

RN

))

=

2.Thisistheonlynontrivialcaseandweaddressitinwhatfollows.

Toviolate K -strategyproofnesswemusthave

δ(

Ri

,

g

(

Ri

,

RN\{i}

))

<

2.Suppose,first,that

δ(

Ri

,

g

(

Ri

,

RN\{i}

))

=

0.

Repeat-ingtheargumentofcase(ii),wearriveatacontradiction.

Thus, we must have

δ(

Ri

,

g

(

R_i

,

RN_\{i}

))

=

1.Now,

δ(

Ri

,

g

(

RN

))

=

2 implies that we must have either g

(

RN

)

=

cab or g

(

RN

)

=

bca. Supposethat g

(

RN

)

=

cab (theproof forcase g

(

RN

)

=

bca is similar). Then,to avoidviolating weak

strate-gyproofnesswemusthave g

(

R_i

,

RN_\{i}

)

=

bac.IwillarguehowthiscannothappenunlessRN

∈

/

K

or

(

R_i

,

RN\{i}

)

∈

/

K

. Givenprofile RN,definethe3

×

3 matrix E,where Exy denotesthenumberofagentsrankingalternativex over y.For

all pairs

(

x

,

y

)

∈

A

×

A such that x

=

y wemust have Exy

+

Eyx

= |

N

|

(the diagonalelements of E are definedtoequal

0).Hence,matrix E tabulatestheresultsofallhead-to-headcontestsbetweenalternativesundertruthfulpreferences.Now, denoteby Ethealteredmatrixw.r.t.toE,inwhichagenti misreportshertruepreferences Ri

=

abc bysubmittingR_i

=

Ri. Wehavethefollowingfivepossibilities:

(I) R_i

=

bac,implyingE_ab

=

Eab

−

1,E_ca

=

Eca

,

E_cb

=

Ecb.

(II) R_i

=

bca,implyingE_ab

=

Eab

−

1,Eca

=

Eca

+

1

,

E_cb

=

Ecb.

(III) R_i

=

acb,implyingE_ab

=

Eab,Eca

=

Eca

,

Ecb

=

Ecb

+

1.

(IV) R_i

=

cba,implying E_ab

=

Eab

−

1,E_ca

=

Eca

+

1

,

E_cb

=

Ecb

+

1. (V) R_i

=

cab,implyingE_ab

=

Eab,Eca

=

Eca

+

1

,

Ecb

=

Ecb

+

1.

Now,since g

(

RN

)

=

cab and g

(

R_i

,

RN\{i}

)

=

bac,itmustbethecasethat:

Eca

+

Ecb

+

Eab

≥

Eac

+

Ebc

+

Eba (8)

E_ca

+

E_cb

+

E_ab

≤

E_ac

+

E_bc

+

E_ba

.

(9)

Givenagent i’sfivepossiblemodificationstomatrixE listedabove,theonlywaythatEqs.(8)–(9)donotleadtoa contra-dictionisifeithercase(I)or(II)applies.11Ifcase(II)appliesthenwemusthaveEca

+

Ecb

+

Eab

=

Eca

+

Ecb

+

Eabinturn