Games and Economic Behavior 144 (2024) 203β224
Available online 1 February 2024
0899-8256/Β© 2024 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license
(http://creativecommons.org/licenses/by/4.0/).
Contents lists available at ScienceDirect
Games and Economic Behavior
journal homepage: www.elsevier.com/locate/geb
Impartial selection with additive guarantees via iterated deletion
Javier Cembrano a, Felix Fischer b, David Hannonb, Max Klimma,β
aInstitut fΓΌr Mathematik, Technische UniversitΓ€t Berlin, Germany
bSchool of Mathematical Sciences, Queen Mary University of London, UK
A R T I C L E I N F O A B S T R A C T
Keywords:
Voting
Impartial selection
Additive approximation
Impartial selection is the selection of an individual from a group based on nominations by other
members of the group, in such a way that individuals cannot inο¬uence their own chance of
selection. For this problem, we give a deterministic mechanism with an additive performance
guarantee of π(π(1+π
)β2)in a setting with πindividuals where each individual casts π(ππ
)
nominations, where π
β[0, 1]. This bound is π(βπ)for π
=0and π(π)for π
=1. The latter is
trivial, as even a mechanism that never selects provides an additive guarantee of π β1. We show,
however, that it is also best possible: for every deterministic impartial mechanism there exists a
situation in which some individual is nominated by every other individual and the mechanism
either does not select or selects an individual not nominated by anyone.
1. Introduction
Many important decisions are made by groups of people who select one member of the group based on nominations from within
the group. In fact, such a procedure is applied in a wide range of settings such as the papal conclaves (Mackenzie, 2020), the national
captainβs votes for the best FIFA Womenβs and Menβs Players Awards, or the voting for spokespersons of committees or student
representatives. A common feature of these situations is that there is at least a partial overlap between the set of voters and the
set of candidates. This overlap may be a source of incentive issues as candidates who have a reasonable chance of winning may be
motivated not to reveal their true opinion on who should win in order to increase their own chance of winning. Incentive issues of
this kind were ο¬rst studied in a systematic way by Holzman and Moulin (2013)and Alon et al. (2011), who formalized the problem
in terms of a directed graph in which vertices correspond to voters and a directed edge from one voter to another indicates that the
former nominates the latter. A (deterministic) selection mechanism then takes such a nomination graph as input and returns either
one of its vertices or no vertex. In order to allow voters to express their true opinions about other voters without having to worry
about their own chance of selection, an important property of a selection mechanism is its impartiality: a mechanism is impartial if,
for all nomination graphs, a change of the outgoing edges of some vertex π£does not change whether π£is selected or not. It is easy
to see that a mechanism that selects a vertex with maximum indegree and breaks ties in some consistent way is not impartial: if ties
are broken in favor of greater index, for example, a vertex with maximum indegree that currently nominates another vertex with
maximum indegree but greater index has an incentive to instead nominate a diο¬erent vertex.
Holzman and Moulin have shown that impartial mechanisms are in fact much more limited even in a setting where each voter
casts exactly one vote, i.e., where each vertex has outdegree one: for every impartial mechanism that selects a vertex in every
* Corresponding author at: Max Klimm, TU Berlin, Institut fΓΌr Mathematik, MA 5-2, StraΓe des 17. Juni 136, 10623 Berlin, Germany.
E-mail addresses: [emailΒ protected] (J. Cembrano),
https://doi.org/10.1016/j.geb.2024.01.008
Received 27 December 2022
Games and Economic Behavior 144 (2024) 203β224
204
J. Cembrano, F. Fischer, D. Hannon et al.
nomination graph, there exists a graph where the mechanism selects a vertex with indegree zero or a graph where it fails to select
a vertex with indegree π β1, where πis the number of voters. This shows in particular that the best multiplicative approximation
guarantee for impartial mechanisms, i.e., the worst case over all nomination graphs of the ratio between the maximum indegree
and the indegree of the selected vertex is at least π β1. On the other hand, a multiplicative guarantee of π β1 is easy to obtain
by always following the outgoing edge of a ο¬xed vertex. As multiplicative guarantees do not allow for a meaningful distinction
among deterministic impartial mechanisms, Caragiannis et al. (2022, 2023) proposed to instead consider an additive guarantee,
i.e., the worst case over all nomination graphs of the diο¬erence between the maximum indegree and the indegree of the selected
vertex. An adaptation provided by Mackenzie (2020)of a mechanism due to Holzman and Moulin achieves an additive guarantee
of βπβ2β.1Caragiannis et al. (2022)further proposed a randomized mechanism with an additive guarantee of π(βπ). It remained
open, however, whether there exists a deterministic mechanism with a sublinear additive guarantee.
The setting studied by Holzman and Moulin, where each vertex has outdegree one, is commonly referred to as the plurality setting.
The impossibility results of Holzman and Moulin regarding multiplicative guarantees carry over to the more general approval setting,
where outdegrees can be arbitrary, but here even less is known about possible additive guarantees. While Caragiannis et al. (2022)
have shown that deterministic impartial mechanisms cannot provide a better additive guarantee than 3, no mechanism is known that
improves on the trivial guarantee of π β1achieved by selecting a ο¬xed vertex. Caragiannis et al. also gave a randomized mechanism
for the approval setting with an additive guarantee of Ξ(π2β3 ln1β3 π).
1.1. Our contribution
We develop a new deterministic mechanism for impartial selection that is parameterized by a pair of thresholds on the indegrees
of vertices in the graph. The mechanism seeks to select a vertex with large indegree, and to achieve impartiality it iteratively deletes
outgoing edges from vertices in decreasing order of their indegrees, until only the outgoing edges of vertices with indegrees below
the lower threshold remain. It then selects a vertex with maximum remaining indegree if that indegree is above the higher threshold,
and otherwise does not select. Any ties are broken according to a ο¬xed ordering of the vertices. We give a suο¬cient condition for
choices of thresholds that guarantee impartiality. The iterative nature of the deletions requires a fairly intricate analysis but is key to
achieving impartiality. The additive guarantee is then obtained for a good choice of thresholds, and the worst case is the one where
the mechanism does not select.
For instances with πvertices and maximum outdegree at most π(ππ
), where π
β[0, 1], the mechanism provides an additive
guarantee of π(π
1+π
2). This is the ο¬rst sublinear bound for a deterministic mechanism and any π
β[0, 1], and is sublinear for all
π
β[0, 1). For settings with constant maximum outdegree, which includes the setting of Holzman and Moulin where all outdegrees
are equal to one, our bound matches the best known bound of π(βπ)for randomized mechanisms and outdegree one, due to
Caragiannis et al. (2022).
When the maximum outdegree is unbounded, the bound becomes π(π). This is of course trivial, as even a mechanism that never
selects a vertex provides an additive guarantee of π β1. For a setting without abstentions, i.e., with minimum outdegree one, the
guarantee can be improved slightly to π β2by following the outgoing edge of a ο¬xed vertex. We show that both of these bounds
are best possible by giving matching lower bounds. This improves on the only lower bound known prior to our work, again due
to Caragiannis et al., which is equal to 3and applies to the setting with abstentions and mechanisms that select a vertex for every
graph.
Just like the lower bounds regarding multiplicative guarantees for plurality, our lower bounds for approval are obtained through
an axiomatic impossibility result. Holzman and Moulin have shown that in the case of plurality, impartiality is incompatible with
positive and negative unanimity. Here, positive unanimity requires that a vertex with the maximum possible indegree of π β1must
be selected, and negative unanimity that a vertex with indegree zero cannot be selected.2We show that in the case of approval
this impossibility can be strengthened even further: call a selection mechanism weakly unanimous if it selects a vertex with positive
indegree whenever there exists a vertex with the maximum possible indegree of π β1; then weak unanimity and impartiality are
incompatible, even if we are not always required to select.
This result is obtained by analyzing the behavior of impartial mechanisms on a restricted class of graphs with a high degree of
symmetry among vertices. Like Holzman and Moulin, we can assume that isomorphic vertices are selected with equal probabilities
by a randomized relaxation of a mechanism. A suitable class of graphs for our purposes are those generated by partial orders on the
set of ordered partitions. Our result is then obtained by combining counting results for ordered partitions and an argument similar
to Farkasβ Lemma.
1.2. Related work
Impartiality as a formal property of social and economic mechanisms was ο¬rst considered by De Clippel et al. (2008)for the
distribution of a divisible commodity among a set of individuals according to the individualsβ subjective claims. Holzman and Moulin
(2013)and Alon et al. (2011)studied impartial selection in two diο¬erent settings, plurality and approval, and established strong
1The mechanism does not always select a vertex, but we will see that for our purposes there is little diο¬erence between mechanisms that do and do not always
select.
2This result is formulated for mechanisms that always select a vertex, but not selecting a vertex clearly does not improve the situation.
Games and Economic Behavior 144 (2024) 203β224
205
J. Cembrano, F. Fischer, D. Hannon et al.
impossibility results regarding the ability of deterministic mechanisms to approximate the maximum indegree in a multiplicative
sense. Alon et al. (2011)also proposed randomized mechanisms for the selection of one or more vertices. Fischer and Klimm (2015)
then obtained a randomized mechanism with the best possible multiplicative guarantee of 2for the selection of a single vertex in
the approval setting, and Bjelde et al. (2017)gave improved deterministic and randomized mechanisms for the selection of more
than one vertex. Niemeyer and Preusser (2023)studied strategyproof mechanisms for the selection of a single individual under more
general preferences.
Starting from the observation that impossibility results for randomized mechanisms in particular are obtained from graphs with
very small indegrees, Bousquet et al. (2014) developed a randomized mechanism that is optimal in the large-indegree limit, i.e.,
that chooses a vertex with indegree arbitrarily close to the maximum indegree as the latter goes to inο¬nity. Caragiannis et al.
(2022, 2023)used the same observation as motivation to study mechanisms with additive rather than multiplicative guarantees.
They developed new mechanisms that achieve such guarantees, established a relatively small but nontrivial lower bound of 3for
deterministic mechanisms in the approval setting, and gave improved deterministic mechanisms for a setting with prior information.
The axiomatic study of Holzman and Moulin has been reο¬ned and extended in a number of ways, for example with a focus on
symmetric mechanisms (Mackenzie, 2015) and to the selection of more than one vertex (Tamura and Ohseto, 2014). Mackenzie
(2020)provided a detailed axiomatic analysis of mechanisms used in the papal conclave and showed that impartial mechanisms
satisfying natural symmetry and anonymity axioms are exactly those that select a vertex whose indegree exceeds a supermajority
threshold. Various selection mechanisms have also been proposed that are tailored to applications like peer review and exploit the
particular preference and information structures of those applications (Kurokawa et al., 2015; Xu et al., 2019; Aziz et al., 2019;
Mattei et al., 2021). Impartial mechanisms have ο¬nally been considered for other objectives, speciο¬cally for the maximization of
progeny (Babichenko et al., 2020; Zhang et al., 2021) and for rank aggregation (Kahng et al., 2018). For an overview of mechanisms
for peer selection and evaluation, the reader is referred to the survey of Olckers and Walsh (2022).
The proof of our impossibility result uses a class of graphs constructed from ordered partitions of the set of vertices. The class has
been studied previously (e.g., Insko et al., 2017; Diagana and MaΓ―ga, 2017), and some of its known properties including its lattice
structure and the number of graphs isomorphic to each graph within the class are relevant to us.
2. Preliminaries
For π ββ, let ξ³π={(π,πΈ)βΆπ={1,2,β¦,π},πΈ β(πΓπ)⧡βπ£βπ{(π£, π£)}}be the set of directed graphs with πvertices and no
loops. Let ξ³ =βπββξ³π. For πΊ=(π, πΈ) βξ³and π£ βπ, let π+(π£, πΊ) ={π’ βπβΆ(π£, π’) βπΈ}be the out-neighborhood and πβ(π£, πΊ) =
{π’ βπβΆ(π’, π£) βπΈ}the in-neighborhood of π£in πΊ. Let πΏ+(π£, πΊ) =|π+(π£, πΊ)|and πΏβ(π£, πΊ) =|πβ(π£, πΊ)|denote the outdegree and
indegree of π£in πΊ,
πΏβ
π(π£, πΊ)=|{π’βπβΆ(π’, π£)βπΈ}|
the indegree of π£from a particular subset πβπof the vertices, and Ξ(πΊ) =max
π£βππΏβ(π£, πΊ)the maximum indegree of any vertex
in πΊ. When the graph is clear from the context, we will sometimes drop πΊfrom the notation and write π+(π£), πβ(π£), πΏ+(π£), πΏβ(π£),
πΏβ
π(π£), and Ξ. For π, π ββ, let ξ³+
π={(π, πΈ) βξ³πβΆπΏ+(π£) β₯1for every π£ βπ}be the set of graphs in ξ³πwhere all outdegrees are
strictly positive,
ξ³π(π)={(π,πΈ)βξ³πβΆπΏ+(π£)β€πfor every π£βπ}
the set of graphs in ξ³πwhere outdegrees are at most π, and ξ³+
π(π) =ξ³+
πβ©ξ³π(π)for the set of graphs satisfying both conditions. Let
ξ³+=βπββξ³+
π, ξ³(π) =βπββξ³π(π), and ξ³+(π) =βπββξ³+
π(π).
A (deterministic) selection mechanism is then given by a family of functions πβΆξ³πβ2πthat maps each graph to a subset of its
vertices, where we require throughout that |π(πΊ)| β€1for all πΊβξ³. By slightly abusing notation, we will use πto refer to both the
mechanism and to individual functions from the family. Mechanism πis impartial on ξ³β²βξ³if on this set of graphs the outgoing
edges of a vertex have no inο¬uence on its selection, i.e., if for every pair of graphs πΊ=(π, πΈ)and πΊβ²=(π, πΈβ²)in ξ³β²and every
π£ βπ, π(πΊ) β©{π£} =π(πΊβ²) β©{π£}whenever πΈβ§΅({π£} Γπ) =πΈβ²β§΅({π£} Γπ). Mechanism πis πΌ-additive on ξ³β²βξ³, for πΌβ₯0, if for
every graph in ξ³β²the indegree of the choice of πdiο¬ers from the maximum indegree by at most πΌ, i.e., if
sup
πΊβξ³β²{Ξ(πΊ)βπΏβ(π(πΊ),πΊ)}β€πΌ,
where for πβπwe let πΏβ(π, πΊ) =βπ£βππΏβ(π£, πΊ)denote the sum of the indegrees of the vertices in π.
3. Iterated deletion of nominations
When outdegrees are at most one, the following simple mechanism is βπβ2β-additive: if there is a vertex with indegree at least
βπβ2β +1, select it; otherwise, do not select. This mechanism is a slight modiο¬cation of a mechanism Holzman and Moulin (2013)
called majority with default and corresponds to the supermajority rule of Mackenzie (2020)with threshold βπβ2β +1. As there can be
at most one vertex with degree βπβ2β +1or more and a vertex cannot inο¬uence its own indegree, the mechanism is clearly impartial.
We will borrow from this mechanism the idea of imposing a threshold on the minimum indegree a vertex needs to be selected, but
will seek to lower the threshold in order to achieve a better additive guarantee and also to relax the constraint on the maximum
Games and Economic Behavior 144 (2024) 203β224
206
J. Cembrano, F. Fischer, D. Hannon et al.
Algorithm 1: Twin threshold mechanism with thresholds πand π‘.
Input: Digraph πΊ=(π, πΈ) βξ³π.
Output: Set πβπof selected vertices with |π| β€1.
Initialize π β0and πβΞ;
π·πββ
; // vertices with deleted outgoing edges in iteration πor before
ξ
πΏπ(π£) βπΏβ(π£)for all π£ βπ; // indegree of π£omitting edges deleted up to π
while πβ₯π‘do
if {π’ βπ⧡π·πβΆξ
πΏπ(π’) =π} =β
then
update πβπβ1and continue
end
π£ βmax{π’ βπ⧡π·πβΆξ
πΏπ(π’) =π};
update
ξ
πΏπ+1(π’) βξ
πΏπ(π’) β1for all π’ βπ+(π£); // delete outgoing edges of π£
update
ξ
πΏπ+1(π’) βξ
πΏπ(π’)for all π’ βπ⧡π+(π£);
update π·π+1 βπ·πβͺ{π£}and π βπ +1;
end
πΌβπ;
ξ
Ξβmaxπ£βπξ
πΏπΌ(π£);
if ξ
Ξβ₯πthen
return πβ{max{π£ βπβΆξ
πΏπΌ(π£) =ξ
Ξ}}
end
return πββ
outdegree. Of course, lower thresholds and larger outdegrees both mean that more and more vertices become eligible for selection,
and we will no longer get impartiality for free.
As a ο¬rst step, it is instructive to again consider the outdegree-one case but to use a lower threshold of π‘ =βπβ3β +1. This choice
of threshold implies that there can be at most two vertices with indegrees equal to or higher than the threshold. Analogously to the
supermajority rule, the general idea is that only vertices with indegree at least π‘are eligible for selection. In cases where there is only
one such vertex impartiality would follow by a similar argument as for the supermajority rule, so the critical case is when there are
two vertices π’and π£with indegree at least π‘. If π’is selected, πΏβ(π’) =π‘, and (π£, π’) βπΈ, then π£could remove the edge (π£, π’), cause π’to
drop below the threshold, and leave π£as the only vertex eligible for selection. To prevent impartiality from being compromised in
this case, it makes sense to introduce another threshold π=π‘ +1 =βπβ3β +2in the understanding that only vertices with indegree
at least πare eligible for selection, but the outgoing edges of all vertices with indegree at least π‘ =βπβ3β +1will automatically be
ignored. It turns out that in order to actually achieve impartiality, the outgoing edges of the vertices with indegree at least π‘must
be removed in decreasing order of indegrees, breaking ties according to some ο¬xed ordering of the vertices. In the end we select
the vertex with maximum indegree among those with indegree at least π, breaking ties as before, and call the resulting mechanism
two contenders (TC). It is not too diο¬cult to convince ourselves that the mechanism is indeed impartial.3Indeed, if πΏβ(π’) β₯πand
πΏβ(π£) β₯π, neither π’nor π£can inο¬uence whether the respective other vertex ends up with an indegree of at least π‘ =πβ1; the
outgoing edges of both π’and π£will be removed, and neither π’nor π£can inο¬uence which of the two vertices is selected. If πΏβ(π’) β₯π
and πΏβ(π£) =π‘, only π’is eligible for selection; the outgoing edge of π’, which has the highest indegree, is removed ο¬rst, so π’cannot
inο¬uence whether π£will have indegree at least π‘and thus whether a potential edge (π£, π’)is removed or not. All other cases are either
analogous or lead to no vertex being selected, and impartiality follows.
It is natural to ask whether the threshold can be lowered further while maintaining impartiality, and whether guarantees can be
obtained in a similar fashion for graphs with larger outdegrees. The answer to the ο¬rst question is not obvious, as the number of
graphs that need to be considered to establish impartiality grows very quickly in the number of vertices eligible for selection. The
obvious generalization of the mechanism with threshold βπβ2β +1to a setting with outdegrees at most π, of selecting the unique
vertex with indegree at least βππβ2β +1if it exists and not selecting otherwise, is impartial and βππβ2β-additive, but this guarantee
is trivial when π β₯2.
Our main result answers both questions in the aο¬rmative. It applies to settings with outdegree at most π =π(ππ
)for π
β[0, 1]
and provides a nontrivial guarantee when π
β[0, 1). When πis constant the guarantee is π(βπ), which matches the best guarantee
known for randomized mechanisms and outdegree one (Caragiannis et al., 2022).
Theorem 1. For every π ββ, π
β[0, 1], and π =π(ππ
), there exists an impartial and π(π
1+π
2)-additive mechanism on ξ³π(π). Speciο¬cally,
for every π ββ, there exists an impartial and
β7.25π-additive mechanism on ξ³π(1).
The result is achieved by a mechanism of a family we call twin threshold mechanisms and describe formally in Algorithm 1. Each
of these mechanisms iteratively deletes the outgoing edges from vertices with indegree above a ο¬rst threshold π‘from the highest to
the lowest indegree and, in the end, selects the vertex with maximum remaining indegree as long as that indegree is above a second,
higher threshold π. The parameters π‘and πcharacterize a speciο¬c mechanism of this family and will be chosen in order to achieve
impartiality and obtain the desired bounds. Throughout the mechanism ties are broken as before, in favor of greater index.
3This will follow as a special case from a more general result in Lemma 3, but we ο¬nd it insightful to give the informal argument here.
Games and Economic Behavior 144 (2024) 203β224
207
J. Cembrano, F. Fischer, D. Hannon et al.
π23451020501005001000
SR 112251025 50250500
TC 23335818 35168335
TTβ11225816 23 56 81
(π‘, π )(2,2) (2,2) (3,3) (3,3) (4,5) (7,8) (7,11) (13,18) (28,41) (36,56)
LB 112233 3 3 3 3
Fig. 1. Values of πΌπ, for certain values of π, such that the supermajority rule with threshold βπβ2β +1(SR), the two contenders mechanism (TC), and an optimal twin
threshold mechanism (TTβ) are πΌπ-additive on ξ³π(1), together with a lower bound (LB) on πΌπfor any impartial πΌπ-additive mechanism. Each bound for TTβin the
table is accompanied by values of the thresholds π‘and πthat achieve the bound, which may not be the unique such values.
For any choice of the maximum outdegree πand the threshold parameters πand π‘, the twin threshold mechanism with thresholds
πand π‘achieves its worst additive performance guarantee in cases where it does not select, and this guarantee can be obtained in
a straightforward way by bounding the maximum indegree. The proof of impartiality, on the other hand, uses a relatively subtle
argument to show that for certain values of πand π‘, a vertex above the higher threshold πcannot inο¬uence whether another vertex
ends up above or below the lower threshold π‘when edges have been deleted. Vertices above πthen have no inο¬uence on the set of
edges taken into account for selection, and since these are the only vertices that can potentially be selected impartiality follows.
For the outdegree-one case and speciο¬c values of π, we can optimize over π‘and πin order to obtain the best guarantee; bounds for
an optimal twin threshold mechanism and selected values of πare shown in Fig. 1, alongside bounds for the supermajority rule with
threshold βπβ2β +1, corresponding to a twin threshold mechanism with π=π‘ =βπβ2β +1, the two contenders mechanism, corre-
sponding to a twin threshold mechanism with π=π‘ +1 =βπβ3β +2, and lower bounds for any impartial mechanism. It is interesting
to note at this point that the supermajority rule with threshold βπβ2β +1possesses natural symmetry properties (Mackenzie, 2020),
and that the optimal twin threshold mechanism does not possess these properties due to its use of tie-breaking and its distinction
among edges depending on their origin. The improved additive guarantee provided by the optimal twin threshold mechanism and
shown in the ο¬gure thus comes at the expense of a certain amount of fairness among vertices.
A twin threshold mechanism maintains a set π·πof vertices whose outgoing edges have been deleted up to iteration π, and indegrees
ξ
πΏπ(π£)where all edges deleted up to iteration πare not counted. After the iterations during which outgoing edges are deleted, we add
an artiο¬cial ο¬nal iteration during which no edges are deleted; this iteration counter is denoted by πΌ. In order to prove Theorem 1,
we will compare runs of the mechanism with ο¬xed thresholds for diο¬erent graphs, and denote by
ξ
πΏπ(π£, πΊ), π·π(πΊ), and πΌ(πΊ)the
respective values of
ξ
πΏπ(π£), π·π, and πΌwhen the mechanism is invoked with input graph πΊ. We use πto denote the indicator function
for logical propositions, i.e., π(π) =1when proposition πis true and π(π) =0otherwise. For a graph πΊand a vertex π£in πΊwhose
outgoing edges are deleted by the mechanism, we use πβ(π£, πΊ)to denote the iteration in which this deletion takes place, such that
π·πβ(π£,πΊ)+1(πΊ) ⧡π·πβ(π£,πΊ)(πΊ) ={π£}. We use the convention that πβ(π£, πΊ) =πΌ(πΊ)if π£ βπ·πΌ(πΊ)(πΊ)to extend the function to all vertices. For
a graph πΊand vertex π£, we write πΏβ(π£, πΊ)= ξ
πΏπβ(π£,πΊ)(π£, πΊ)for the indegree of π£, not taking into account any incoming edges deleted
previously, at the last moment before the outgoing edges of π£are deleted. When the graph πΊis clear from the context, we again drop
πΊfrom the notation. It is clear from the deο¬nition of the mechanism that for any graph πΊ=(π, πΈ)and vertex π£ βπ·πΌ(πΊ)(πΊ),
πΏβ(π£, πΊ)βπΏβ(π£, πΊ)=|{π’βπβ(π£, πΊ)βΆπβ(π’, πΊ)<π
β(π£, πΊ)}|.(1)
When comparing tuples of the form (πΏβ(π£), π£), we use βͺ―and βΊto denote lexicographic order and strict lexicographic order. These
comparisons are relevant to our analysis because they determine the order in which edges are deleted. Speciο¬cally, for any graph
πΊ=(π, πΈ)and vertices π’, π£ βπ·πΌ(πΊ)(πΊ),
πβ(π’, πΊ)<π
β(π£, πΊ)if and only if (πΏβ(π’, πΊ),π’)β»(πΏβ(π£, πΊ),π£).(2)
Fig. 2shows an example of the edge deletion process over four iterations of Algorithm 1. Observe that for πβ{1, 2}, (πΏβ(π£), π£) β»
(πΏβ(π’π), π’π)but (πΏβ(π£), π£) βΊ(πΏβ(π’π), π’π). This is caused by a drop in the indegree of π£over the course of the algorithm, and this drop
occurs before the algorithm considers possible outgoing edges of π£for deletion. For our analysis, it will be important to bound how
much the indegree of a vertex π£can drop before π£loses its outgoing edges. The following lemma, which we prove in Appendix A,
characterizes this quantity in terms of the indegrees of the in-neighbors of π£.
Games and Economic Behavior 144 (2024) 203β224
208
J. Cembrano, F. Fischer, D. Hannon et al.
Fig. 2. Illustration of the edge deletion process in Algorithm 1. Here and in other ο¬gures, we arrange the vertices above π‘vertically according to their indegree, with
larger indegrees above, and horizontally according to their index, with greater indices to the left. Vertices below π‘, as well as edges with one or both endpoints below
π‘, are omitted for simplicity.
Fig. 3. Illustration of Lemma 1for π =3. If the indegree of π£drops as shown by the dashed arrow, there must be a vertex with an edge to π£in π΄, another vertex with
an edge to π£in π΄ βͺπ΅, and a third vertex with an edge to π£in π΄ βͺπ΅βͺπΆ. Note that this exact condition is satisο¬ed for the example of Fig. 2.
Lemma 1. Let πΊ=(π, πΈ) βξ³π, π£ βπand (π, π§) ββ2such that
(πΏβ(π£),π£)β»(π,π§)βͺ°(πΏβ(π£),π£).
Let π =πΏβ(π£) βπ+π(π£ >π§). Then there exist vertices π’0, β¦ , π’πβ1 such that for each πβ{0, 1, β¦ , π β1}, (π’π, π£) βπΈand (πΏβ(π’π), π’π) β»
(πΏβ(π£) βπ, π£). Moreover, if (π, π§) =(πΏβ(π£), π£), then for every vertex π’ βπβ(π£) ⧡{π’0, β¦ , π’πβ1}, (πΏβ(π’), π’) βΊ(πΏβ(π£), π£).
If we take (π, π§) =(πΏβ(π£), π£), the lemma implies that for any vertex π£ βπ·πΌ,
πΏβ(π£)βπΏβ(π£)=|{π’βπβ(π£)βΆ(πΏβ(π’),π’)β»(πΏβ(π£)+1,π£)}|.(3)
In other words, if the indegree of a vertex π£drops from πΏβ(π£)to πΏβ(π£) =πΏβ(π£) βπbefore the outgoing edges of π£are deleted, there
must be πvertices with edges to π£that satisfy the following property: at least one of them, π’0, must have indegree high enough for its
outgoing edges to be deleted before those of π£, i.e., (πΏβ(π’0), π’0) β»(πΏβ(π£), π£); another vertex, π’1, must have indegree high enough for
its outgoing edges to be deleted before those of π£after its indegree is reduced by one, i.e., (πΏβ(π’1), π’1) β»(πΏβ(π£) β1, π£); and so forth, up
to π’πβ1 with (πΏβ(π’πβ1), π’πβ1) β»(πΏβ(π£) β(π β1), π£) =(πΏβ(π£) +1, π£). The other vertices π’with edges to π£must satisfy (πΏβ(π’), π’) βΊ(πΏβ(π£), π£).
This is illustrated in Fig. 3for the case where the indegree of π£drops by π =3. When (π, π§) β»(πΏβ(π£), π£)it is enough to carry out the
analysis for the ο¬rst π =πΏβ(π£) βπ+π(π£ >π§)vertices π’0, β¦ , π’πβ1.
To establish impartiality of the twin threshold mechanism with certain thresholds, we need to compare runs of the mechanism
on graphs that diο¬er in the outgoing edges of a single vertex. Intuitively, a change in the outgoing edges will make a diο¬erence to
the outcome of the mechanism only if it aο¬ects the position of some other vertex relative to the lower threshold π‘at the time that
vertex is considered: If at that time the vertex is above the threshold its outgoing edges are deleted, otherwise the edges remain
and are used in the decision of which vertex to select. We are thus interested in pairs of graphs πΊ1and πΊ2that diο¬er only in the
outgoing edges of a vertex ξ‘π£, and which contain a second vertex π£ β ξ‘π£ such that πΏβ(π£, πΊ1) >πΏ
β(π£, πΊ2). Using Lemma 1, we can derive
conditions in terms of the indegrees of the in-neighbors of π£under which this can happen. Moreover, we can show that one of two
additional conditions must be satisο¬ed: either (i) ξ‘π£ has an edge to π£in πΊ1, or (ii) there exists a vertex π’0with an edge to π£in both
πΊ1and πΊ2such that πΏβ(π’0, πΊ1) <πΏ
β(π’0, πΊ2). We obtain the following lemma.
Lemma 2. Let πΊ1=(π, πΈ1), πΊ2=(π, πΈ2) βξ³π, π£, ξ‘π£ βπwith π£ β ξ‘π£ be such that πΈ1⧡({ ξ‘π£} Γπ) =πΈ2⧡({ ξ‘π£} Γπ), πΏβ(π£, πΊ1) >πΏ
β(π£, πΊ2),
and πΏβ(π£, πΊ1) β₯π‘. Consider (π, π§) ββ2such that (πΏβ(π£, πΊ1), π£) β»(π, π§) βͺ°(πΏβ(π£, πΊ2), π£), and let π =πΏβ(π£, πΊ1) βπ+π(π£ >π§). Then, there
exist vertices π’0, β¦ , π’πβ1 such that, for every πβ{1, β¦ , π β1},
(π’π,π£)βπΈ1β©πΈ2,(πΏβ(π’π,πΊ
2),π’
π)β»(πΏβ(π£, πΊ1)βπ,π£),(πΏβ(π’π,πΊ
1),π’
π)βΊ(πΏβ(π£, πΊ1),π£),
and one of the following holds:
(i) (π’0, π£) βπΈ1⧡πΈ2and if (πΏβ(π£, πΊ1), π£) βΊ(πΏβ(ξ‘π£, πΊ1), ξ‘π£), taking ξ‘π =πΏβ(ξ‘π£, πΊ1) βπΏβ(π£, πΊ1) +π(ξ‘π£>π£)we have that there are vertices
ξ‘π’0, β¦ , ξ‘π’ξ‘πβ1, none of them equal to ξ‘π£, such that (πΏβ(ξ‘π’π, πΊ1), ξ‘π’π) β»(πΏβ(ξ‘π£, πΊ1) βπ, ξ‘π£)for every πβ{0, β¦ , ξ‘π β1}; or
(ii) (πΏβ(π’0, πΊ2), π’0) β»β― β»(πΏβ(π’πβ1, πΊ2), π’πβ1), (π’0, π£) βπΈ1β©πΈ2, and (πΏβ(π’0, πΊ2), π’0) β»(πΏβ(π£, πΊ1), π£) β»(πΏβ(π’0, πΊ1), π’0).
Games and Economic Behavior 144 (2024) 203β224
209
J. Cembrano, F. Fischer, D. Hannon et al.
We prove Lemma 2in Appendix B, but provide some intuition for its correctness here. Assume that the indegree of a vertex π£
drops from πΏβ(π£)to πΏβ(π£) =πΏβ(π£) βπbefore its outgoing edges are deleted. Then, by Lemma 1, there must be πin-neighbors of π£
whose indegrees are at least πΏβ(π£) +1when their outgoing edges are deleted. Thus, when π£, πΊ1, and πΊ2are as in the statement of
Lemma 2, and deο¬ning π1=πΏβ(π£, πΊ1) βπΏβ(π£, πΊ1)and π2=πΏβ(π£, πΊ2) βπΏβ(π£, πΊ2), then π1in-neighbors of π£must have indegree at least
πΏβ(π£, πΊ1) +1in πΊ1upon deletion of their outgoing edges, and π2in-neighbors of π£must have indegree at least πΏβ(π£, πΊ2) +1in πΊ2
upon deletion of their outgoing edges. There are then two possible reasons for the diο¬erence between πΏβ(π£, πΊ1)and πΏβ(π£, πΊ2). The
ο¬rst, which can only occur when π1=π2, is given in Condition (i) of the lemma: ξ‘π£ has an edge to π£in πΊ1but not in πΊ2, while all the
other indegrees remain the same. However, for this diο¬erence to have an impact, the outgoing edges of ξ‘π£ must be deleted after those
of π£, and Lemma 1implies the existence of in-neighbors of ξ‘π£ with indegrees as shown. The other reason, which can happen when
π1=π2and necessarily happens otherwise, is that some in-neighbor π’0of π£in both πΊ1and πΊ2loses its outgoing edges after π£when
the input to the mechanism is πΊ1, but before π£when the input is πΊ2. This must happen due to a change in the indegree of π’0at the
time its outgoing edges are deleted, i.e.,
(πΏβ(π’0,πΊ
2),π’
0)β»(πΏβ(π£, πΊ1),π£)β»(πΏβ(π’0,πΊ
1),π’
0).
This is captured in Condition (ii). In both cases, Lemma 1implies the existence of πΏβ(π£, πΊ1) βπΏβ(π£, πΊ2) β1further in-neighbors of π£
in both graphs, denoted as π’1, β¦ , π’πβ1, which lose their outgoing edges after π£in πΊ1but before π£in πΊ2. When (π, π§) β»(πΏβ(π£, πΊ2), π£),
it again suο¬ces to carry out the analysis for a smaller subset of the vertices with edges to π£.
Lemma 2implies that whenever πΊ1and πΊ2diο¬er only in the outgoing edges of a single vertex ξ‘π£, and π£is a diο¬erent vertex with
πΏβ(π£, πΊ1) >πΏ
β(π£, πΊ2), then either (i) ξ‘π£ has an edge to π£in πΊ1, or (ii) there exists a vertex π’0with πΏβ(π’0, πΊ1) <πΏ
β(π’0, πΊ2). The fact that
this relationship is the opposite of that for π£naturally suggests an iterative analysis, where the roles of πΊ1and πΊ2are exchanged in
each iteration as long as Condition (ii) holds. Such an analysis leads to the following lemma, which establishes a suο¬cient condition
for impartiality in terms of π,π‘, and π. Impartiality for a particular choice of πand π‘that guarantees the bound of Theorem 1can
then be obtained in a straightforward way.
Lemma 3. For every π, π ββwith π β€π β1, the twin threshold mechanism with thresholds πand π‘such that
1
2(π2+π+3π‘βπ‘2)βmin{πβπ‘, π}>ππ
is impartial on ξ³π(π).
Proof. Let πbe the selection mechanism given by the twin threshold mechanism with thresholds πand π‘. We suppose that π
is not impartial and we want to see that the inequality in the statement of the lemma is thus violated. Speciο¬cally, let π ββ,
πΊ=(π, πΈ), πΊβ²=(π, πΈβ²) βξ³π, and ξ‘π£ βπbe such that πΈβ§΅({ ξ‘π£} Γπ) =πΈβ²β§΅({ ξ‘π£} Γπ)and ξ‘π£ βπ(πΊ) β΅π(πΊβ²), i.e., ξ‘π£ is selected only
for one of these graphs. In particular, πΏβ(ξ‘π£, πΊ) =πΏβ(ξ‘π£, πΊβ²) β₯π. For ξ‘π£ to be selected only for one of the graphs, there has to be a
vertex π£ βπ⧡{ξ‘π£}whose outgoing edges are deleted when the mechanism runs with input πΊbut not when it runs with input πΊβ², or
vice versa. Suppose w.l.o.g. that the former holds, so denoting π£0=π£we have that πΏβ(π£0, πΊ) >π‘ β1 β₯πΏβ(π£0, πΊβ²). From Lemma 2with
π£ =π£0, πΊ1=πΊ, πΊ2=πΊβ², and (π, π§) =(π‘ β1, π£0), we have that there are π0=πΏβ(π£0, πΊ) β(π‘ β1)vertices π’0
0, β¦ , π’0
π0β1 for which (π’0
π, π£0) β
πΈβ©πΈβ², (πΏβ(π’0
π, πΊβ²), π’0
π) β»(πΏβ(π£0, πΊ) βπ, π£0), (πΏβ(π’0
π, πΊ), π’0
π) βΊ(πΏβ(π£0, πΊ), π£0)for every πβ{1, β¦ , π0β1}, and one of the conditions in
the lemma holds. If Condition (i) holds, we denote π =0. Otherwise, we have that (πΏβ(π’0
0, πΊβ²), π’0
0) β»(πΏβ(π£0, πΊ), π£0) β»(πΏβ(π’0
0, πΊ), π’0
0),
thus we can deο¬ne π£1=π’0
0and apply Lemma 2with π£ =π£1, πΊ1=πΊβ², πΊ2=πΊ, and (π, π§) =(πΏβ(π£0, πΊ), π£0).
The argument can be repeated until Condition (i) holds at some iteration, which we denote π. This necessarily happens because
πis ο¬nite, and we denote as πΊββ{πΊ, πΊβ²}the graph such that (ξ‘π£, π£π)is an edge of πΊβ. In particular, πΊβ=πΊif πis even and
πΊβ=πΊβ²if πis odd. For every iteration πβ{1, β¦ , π β1}the following holds: There is a vertex π£π=π’πβ1
0and a strictly positive
value ππ=πΏβ(π£π, πΊ) βπΏβ(π£πβ1, πΊβ²) +π(π£π>π£
πβ1)(if πis even) or ππ=πΏβ(π£π, πΊβ²) βπΏβ(π£πβ1, πΊ) +π(π£π>π£
πβ1)(if πis odd) such that
there are vertices π’π
0, β¦ , π’π
ππβ1 such that for each πβ{1, β¦ , ππβ1},
(π’π
π,π£
π)βπΈβ©πΈβ²,(πΏβ(π’π
π,πΊβ²),π’
π
π)β»(πΏβ(π£π,πΊ)βπ,π£π),(πΏβ(π’π
π,πΊ),π’
π
π)βΊ(πΏβ(π£π,πΊ),π£
π)(4)
if πis even, and
(π’π
π,π£
π)βπΈβ©πΈβ²,(πΏβ(π’π
π,πΊ),π’
π
π)β»(πΏβ(π£π,πΊβ²)βπ,π£π),(πΏβ(π’π
π,πΊβ²),π’
π
π)βΊ(πΏβ(π£π,πΊβ²),π£
π)(5)
if πis odd. Furthermore, we claim that for every π, πβ²β{0, β¦ , π β1} and every πβ{0, β¦ , ππβ1}, πβ²β{0, β¦ , ππβ²β1} with
(π, π) β (πβ², πβ²)it holds π’π
πβ π’πβ²
πβ². This is straightforward if π=πβ², so we only need to show it when πβ πβ². In order to see this, we
actually show the following properties, that directly imply the previous one:
(πΏβ(π’π
π,πΊβ²),π’
π
π)β»(πΏβ(π’πβ²
πβ²,πΊβ²),π’
πβ²
πβ²)for every πβ{2,β¦,π}even,πβ²β{0,β¦,πβ1},
πβ{0,β¦,π
πβ1},πβ²β{0,β¦,π
πβ²β1}.(6)
(πΏβ(π’π
π,πΊ),π’
π
π)β»(πΏβ(π’πβ²
πβ²,πΊ),π’
πβ²
πβ²)for every πβ{1,β¦,π}odd,πβ²β{0,β¦,πβ1},
πβ{0,β¦,π
πβ1},πβ²β{0,β¦,π
πβ²β1}.(7)
Games and Economic Behavior 144 (2024) 203β224
210
J. Cembrano, F. Fischer, D. Hannon et al.
We prove this by induction over π, distinguishing whether this is an even or odd value. Let ο¬rst πβ{2, β¦ , π}be an even value and
note that
(πΏβ(π’π
π,πΊβ²),π’
π
π)β»(πΏβ(π£π,πΊ)βπ,π£π)β»(πΏβ(π£πβ1,πΊβ²),π£
πβ1)for every πβ{0,β¦,π
πβ1},
where the ο¬rst inequality follows from (4)and the second one from the deο¬nition of ππ. By (5)and the fact that πβ1 β π, we have
that (πΏβ(π£πβ1, πΊβ²), π£πβ1) β»(πΏβ(π’πβ1
πβ², πΊβ²), π’πβ1
πβ²)for each πβ²β{0, β¦ , ππβ1 β1}, and from Condition (ii) of Lemma 2we also have that
(πΏβ(π£πβ1, πΊβ²), π£πβ1) =(πΏβ(π’πβ2
0, πΊβ²), π’πβ2
0) β»(πΏβ(π’πβ2
πβ², πΊβ²), π’πβ2
πβ²)for each πβ²β{1, β¦ , ππβ2 β1}. Therefore, we conclude that for every
even πwe have both
(πΏβ(π’π
π,πΊβ²),π’
π
π)β»(πΏβ(π’πβ1
πβ²,πΊβ²),π’
πβ1
πβ²)for every πβ²β{0,β¦,π
πβ1 β1},
and
(πΏβ(π’π
π,πΊβ²),π’
π
π)β»(πΏβ(π’πβ2
πβ²,πΊβ²),π’
πβ2
πβ²)for every πβ²β{0,β¦,π
πβ2 β1}.
This proves the claim for the base case π=2, and also implies that if it holds for every even πβ€ξ
πwhere
ξ
πβ₯2is even, then it holds
for
ξ
π+2as well. For odd values of π, the claim follows from an analogous argument where the roles of πΊand πΊβ²are exchanged,
with the only diο¬erence that for the base case π=1, πβ²=πβ1is the only possibility.
For the last step π=π, if πΏβ(π£π, πΊβ) <πΏ
β(ξ‘π£, πΊ), taking ξ‘π =πΏβ(ξ‘π£, πΊ) βπΏβ(π£π, πΊβ) +π(ξ‘π£>π£
π)we have that Lemma 2guarantees
the existence of vertices ξ‘π’0, β¦ , ξ‘π’ξ‘πβ1, none of them equal to ξ‘π£, such that for each πβ{0, β¦ , ξ‘π β1},
(ξ‘π’π,ξ‘π£)βπΈβ©πΈβ²,(πΏβ(ξ‘π’π,πΊβ),ξ‘π’π)β»(πΏβ(ξ‘π£, πΊ)βπ, ξ‘π£).(8)
Furthermore, we claim for every πβ{0, β¦ , π β1}, πβ{0, β¦ , ππβ1}, and πβ²β{0, β¦ , ξ‘π β1}that π’π
πβ ξ‘π’πβ². In order to see this, we
observe that (8)and the deο¬nition of ξ‘π imply that for every πβ{0, β¦ , ξ‘π β1}and every πβ²β{1, β¦ , ππβ1},
(πΏβ(ξ‘π’π,πΊβ),ξ‘π’π)β»(πΏβ(π£π,πΊβ),π£
π)=(πΏβ(π’πβ1
0,πΊβ),π’
πβ1
0)β»(πΏβ(π’πβ1
πβ²,πΊβ),π’
πβ1
πβ²),
where the last inequality follows from Condition (ii) of Lemma 2. Therefore, by (7), if πis even, then for every πβ{0, β¦ , π β1},
πβ{0, β¦ , ππβ1}, and πβ²β{0, β¦ , ξ‘π β1},
(πΏβ(ξ‘π’πβ²,πΊ),ξ‘π’πβ²)=(πΏβ(ξ‘π’πβ²,πΊβ),ξ‘π’πβ²)β»(πΏβ(π’π
π,πΊ),π’
π
π).
Similarly, if πis odd, (6)implies for every πβ{0, β¦ , π β1}, πβ{0, β¦ , ππβ1}, and πβ²β{0, β¦ , ξ‘π β1}that
(πΏβ(ξ‘π’πβ²,πΊβ²),ξ‘π’πβ²)=(πΏβ(ξ‘π’πβ²,πΊβ),ξ‘π’πβ²)β»(πΏβ(π’π
π,πΊβ²),π’
π
π).
This concludes the proof of the claim.
In the following, we will establish a lower bound on the sum of the indegrees of the vertices in graph πΊ. We start by observing
that, for any subset of vertices πβπ⧡{π£0}, deο¬ning πΊπ£β{πΊ, πΊβ²}arbitrarily for each π£ βπwe have
β
π£βπ⧡{π£0}
πΏβ(π£, πΊ)β₯max{β
π£βπ
(πΏβ(π£, πΊπ£)β1)+1,β
π£βπ
πΏβ(π£, πΊπ£)βπ}.(9)
To see this ο¬x πand {πΊπ£}π£βπas described, and note that since πΊand πΊβ²only diο¬er in the outgoing edges of ξ‘π£, it holds that
β
π£βπ
πΏβ(π£, πΊπ£)β β
π£βπ⧡{π£0}
πΏβ(π£, πΊ)β€β
π£βπ
πΏβ(π£, πΊπ£)ββ
π£βπ
πΏβ(π£, πΊ)β€π.
Moreover, we know that πΏβ(ξ‘π£, πΊ) =πΏβ(ξ‘π£, πΊξ‘π£) β₯πβ₯1, and for every π£ βπthat πΏβ(π£, πΊ) β₯πΏβ(π£, πΊπ£) β1. If ξ‘π£ βπ, this yields
β
π£βπ⧡{π£0}
πΏβ(π£, πΊ)β₯πΏβ(ξ‘π£, πΊ ξ‘π£)+ β
π£βπ⧡{ξ‘π£}
(πΏβ(π£, πΊπ£)β1)=β
π£βπ
(πΏβ(π£, πΊπ£)β1)+1.
On the other hand, if ξ‘π£ βπ, we have
β
π£βπ⧡{π£0}
πΏβ(π£, πΊ)β₯πΏβ(ξ‘π£, πΊ)+β
π£βπ
(πΏβ(π£, πΊπ£)β1)β₯β
π£βπ
(πΏβ(π£, πΊπ£)β1)+1.
This concludes the proof of (9).
We now claim that if πΏβ(π£π, πΊβ) β₯πΏβ(ξ‘π£, πΊ), then
β
π£βπ⧡{π£0}
πΏβ(π£, πΊ)+πΏβ(π£0,πΊ)
Games and Economic Behavior 144 (2024) 203β224
211
J. Cembrano, F. Fischer, D. Hannon et al.
β₯maxβ§
βͺ
β¨
βͺ
β©β
π<π even
ππβ1
β
π=0
(πΏβ(π’π
π,πΊβ²)β1)+ β
π<π odd
ππβ1
β
π=0
(πΏβ(π’π
π,πΊ)β1)+1,
β
π<π even
ππβ1
β
π=0
πΏβ(π’π
π,πΊβ²)+ β
π<π odd
ππβ1
β
π=0
πΏβ(π’π
π,πΊ)βπβ«
βͺ
β¬
βͺ
β
+πΏβ(π£0,πΊ)
β₯maxβ§
βͺ
β¨
βͺ
β©β
π<π even
ππβ1
β
π=0
(πΏβ(π£π,πΊ)βπβ1)+ β
π<π odd
ππβ1
β
π=0
(πΏβ(π£π,πΊβ²)βπβ1)+1,
β
π<π even
ππβ1
β
π=0
(πΏβ(π£π,πΊ)βπ)+ β
π<π odd
ππβ1
β
π=0
(πΏβ(π£π,πΊβ²)βπ)βπβ«
βͺ
β¬
βͺ
β
+πΏβ(π£0,πΊ)
β₯max{πΏβ(π£π,πΊβ)βπ‘
β
π=0
(πΏβ(π£π,πΊβ)βπβ1)+1,
πΏβ(π£π,πΊβ)βπ‘
β
π=0
(πΏβ(π£π,πΊβ)βπ)βπ}+π‘
=
πΏβ(π£π,πΊβ)
β
π=π‘
πβmin{πΏβ(π£π,πΊβ)βπ‘, π}+π‘
β₯
π
β
π=π‘
πβmin{πβπ‘, π}+π‘=1
2(π2+π+3π‘βπ‘2)βmin{πβπ‘, π}.
Indeed, the ο¬rst inequality follows from (9) applied to π={π’π
πβΆπβ{0, β¦ , π β1}, πβ{0, β¦ , ππβ1}}, and the facts that π£0β π’π
π
for any πβ{0, β¦ , π β1} and πβ{0, β¦ , ππβ1} and that π’π
πβ π’πβ²
πβ²whenever (π, π) β (πβ², πβ²). The second inequality uses that
πΏβ(π£,
ξ£
πΊ) β€πΏβ(π£,
ξ£
πΊ)for every
ξ£
πΊ=( ξ£
π,
ξ£
πΈ) βξ³and π£ βξ£
π, as well as (4) and (5). The third inequality uses that πΏβ(π£0, πΊ) β₯π‘and that,
by Lemma 2, πΏβ(π£π, πΊ) β₯πΏβ(π’π
0, πΊ) =πΏβ(π£π+1, πΊβ²) βππ+1 if πis even, and πΏβ(π£π, πΊβ²) β₯πΏβ(π’π
0, πΊβ²) =πΏβ(π£π+1, πΊ) βππ+1 if πis odd. The
ο¬rst equality follows from rearranging terms, the equality from simple computations, and the ο¬nal inequality by observing that the
expression is increasing in πΏβ(π£π, πΊβ)and this value is bounded from below by πΏβ(ξ‘π£, πΊ) β₯π.
On the other hand, if πΏβ(π£π, πΊβ) <πΏ
β(ξ‘π£, πΊ), then the ο¬nal inequality does not hold. We can, however, use (8)to conclude that
β
π£βπ⧡{π£0}
πΏβ(π£, πΊ)+πΏβ(π£0,πΊ)
β₯maxβ§
βͺ
β¨
βͺ
β©β
π<π even
ππβ1
β
π=0
(πΏβ(π’π
π,πΊβ²)β1)+ β
π<π odd
ππβ1
β
π=0
(πΏβ(π’π
π,πΊ)β1)+
ξ‘πβ1
β
π=0
(πΏβ(ξ‘π’π,πΊβ)β1)+1,
β
π<π even
ππβ1
β
π=0
πΏβ(π’π
π,πΊβ²)+ β
π<π odd
ππβ1
β
π=0
πΏβ(π’π
π,πΊ)+
ξ‘πβ1
β
π=0
πΏβ(ξ‘π’π,πΊβ)βπβ«
βͺ
β¬
βͺ
β
+πΏβ(π£0,πΊ)
β₯max{πΏβ(π£π,πΊβ)βπ‘
β
π=0
(πΏβ(π£π,πΊβ)βπβ1)+
ξ‘πβ1
β
π=0
(πΏβ(ξ‘π£, πΊ)βπβ1)+1,
πΏβ(π£π,πΊβ)βπ‘
β
π=0
(πΏβ(π£π,πΊβ)βπ)+
ξ‘πβ1
β
π=0
(πΏβ(ξ‘π£, πΊ)βπ)βπ}+πΏβ(π£0,πΊ)
β₯max{πΏβ(ξ‘π£,πΊ)
β
π=π‘
(πβ1)+1,
πΏβ(ξ‘π£,πΊ)
β
π=π‘
πβπ}+π‘
=
πΏβ(ξ‘π£,πΊ)
β
π=π‘
πβmin{πΏβ(ξ‘π£, πΊ)βπ‘, π}+π‘
β₯
π
β
π=π‘
πβmin{πβπ‘, π}+π‘=1
2(π2+π+3π‘βπ‘2)βmin{πβπ‘, π}.
Games and Economic Behavior 144 (2024) 203β224
212
J. Cembrano, F. Fischer, D. Hannon et al.
Fig. 4. By changing its outgoing edge, ξ‘π£ is able to aο¬ect whether it is selected by the mechanism or not. Lemma 3gives a condition over π, π‘, and πsuch that this
cannot happen. In this example, the sum of the indegrees of the vertices of πΊ1that are shown in the ο¬gure is 5(π‘ +1), so we need that 5(π‘ +1) β€ππ. On the other
hand, when π=π‘ +2Lemma 3states that impartiality is guaranteed as long as 4π‘ +3 >ππ +min{π, 2}. The graphs of this example clearly violate this condition.
Indeed, the ο¬rst inequality follows from (9) applied to π={π’π
πβΆπβ{0, β¦ , π β1}, πβ{0, β¦ , ππβ1}} βͺ{ξ‘π’πβΆπβ{0, β¦ , ξ‘π β1}},
and the facts that π£0β π’π
πfor any πβ{0, β¦ , π β1}and πβ{0, β¦ , ππβ1}, that π’π
πβ π’πβ²
πβ²whenever (π, π) β (πβ², πβ²), and that π’π
πβ ξ‘π’πβ²
for every πβ{0, β¦ , π β1}, πβ{0, β¦ , ππβ1}, and πβ²β{0, β¦ , ξ‘π β1}. The second inequality follows analogously to the previous
sequence of inequalities but also uses (8)to bound πΏβ(ξ‘π’π, πΊβ). The other inequalities follow analogously to before, with the exception
that for the last inequality we now use that the expression is increasing in πΏβ(ξ‘π£, πΊ), which is again bounded from below by π.
Since the sum of the indegrees in a graph is at most the maximum number ππ of edges, we conclude in any of the previous cases
that
1
2(π2+π+3π‘βπ‘2)βmin{πβπ‘, π}β€ππ. β‘
Fig. 4illustrates this result by showing a situation where the outgoing edge of a vertex ξ‘π£ with πΏβ(ξ‘π£, πΊ1) =πΏβ(ξ‘π£, πΊ2) =πdetermines
whether πΏβ(π£) β₯π‘for another vertex π£, and thus whether ξ‘π£ itself is selected or not. Note that in the example there exist vertices π€π
such that πΏβ(π€π, πΊ) β₯π‘ +πfor every πβ{0, β¦ , πβπ‘}and some πΊβ{πΊ1, πΊ2}.
It is worth noting that Lemma 3implies the impartiality of both the supermajority rule with threshold βπβ2β +1and the two
contenders mechanism. When taking a single threshold π=π‘, the suο¬cient condition for impartiality becomes π>ππβ2, which
is clearly satisο¬ed when π =1and π=βπβ2β +1as in the supermajority rule with threshold βπβ2β +1. When taking thresholds
that diο¬er by 1, π=π‘ +1, the suο¬cient condition for impartiality becomes π>ππβ3 +1, which is clearly satisο¬ed when π =1
and π=βπβ3β +2as in the two contenders mechanism. We will now prove Theorem 1by using this same condition to guarantee
impartiality, but choosing the thresholds in such a way that the additive deviation is as small as possible.
Proof of Theorem 1.Let π ββ+, πΊβξ³π(π)and π
, π>0such that π β€πππ
. Let πbe the selection mechanism given by the twin
threshold mechanism with thresholds π=ββ8ππ
1+π
2β +1and π‘ =ββππ
1+π
2β. Since π(π +1) β€ππ1+π
+πππ
β€2ππ1+π
, we have from
Lemma 3that a suο¬cient condition for impartiality is that
1
2(π2+π+3π‘βπ‘2)>2ππ1+π
.
Replacing πand π‘yields
1
2(π2+π+3π‘βπ‘2)>1
2(8ππ1+π
+β8ππ
1+π
2+3
βππ
1+π
2βββππ
1+π
2β2)>2ππ1+π
,
where we used that πππ
>1and thus ββππ
1+π
2β2<4ππ1+π
. We conclude that the mechanism is impartial for these values of πand π‘.
In order to obtain the additive bound, ο¬rst consider a graph πΊ=(π, πΈ)such that πreturns the empty set when run with this
graph as input. Let π£βbe such that πΏβ(π£β) =Ξ(πΊ)and note that necessarily
ξ
πΏπΌ(π£β) β€πβ1. Since there are at most βππβπ‘βvertices
with indegree π‘or higher, a maximum of βππβπ‘β β1 in-neighbors of π£βhas their outgoing edges deleted during the algorithm.
Therefore, we conclude that Ξ(πΊ) β€π+βππβπ‘β β2.
Games and Economic Behavior 144 (2024) 203β224
213
J. Cembrano, F. Fischer, D. Hannon et al.
Consider now πΊ=(π, πΈ)such that the mechanism returns a set {π£}, and let π£βbe such that πΏβ(π£β) =Ξ(πΊ). Once again, a
maximum of βππβπ‘β β1in-neighbors of π£βhas their outgoing edges deleted during the algorithm. Using the fact that
ξ
πΏπΌ(π£β) β€ξ
πΏπΌ(π£)
since π£is selected, we conclude that
Ξ(πΊ)βπΏβ(π£)β€(πΏβ(π£)+βππ
π‘ββ1
)βπΏβ(π£)=βππ
π‘ββ1.
Since the value obtained in the former case is greater than or equal to the one obtained in the latter for any values of πand π‘, we
have that πis πΌ-additive for πΌ=π+βππβπ‘β β2. Therefore, for the speciο¬ed values of πand π‘and given the upper bound on π, πis
πΌ-additive for
πΌ=ββ8ππ
1+π
2β+1+β’β’β’β’β£
ππ1+π
ββππ
1+π
2ββ₯β₯β₯β₯β¦
β2β€(β8+1)
βππ
1+π
2=π(π
1+π
2).
We conclude that πis π(π
1+π
2)-additive.
When π =1, a more detailed analysis yields the bound of
β7.25π. First observe that in this case, by Lemma 3, impartiality holds
whenever
1
2(π2+π+3π‘βπ‘2)β(π+1)>0
and thus when
π2+πβ(π‘2β3π‘+2π+2)>0.
The left-hand side is equal to zero if and only if
π=β1 Β± β4(π‘2β3π‘+2π+2)+1
2=Β±
βπ‘2β3π‘+2π+9
4β1
2,
and since πhas to be non-negative impartiality holds if
π>
βπ‘2β3π‘+2π+9
4β1
2.
This is trivially satisο¬ed if we take
π‘=β1.23βπβ,π=βββ1.23βπβ2β3β1.23βπβ+2π+9
4+1
2β.
As before, the twin threshold mechanism with thresholds πand π‘is πΌ-additive for any πΌβ₯πΌ(π) βΆ= π+βπβπ‘β β2. In order to obtain
an upper bound on πΌ(π), we start by bounding πfrom above:
πβ€β(1.23βπ+1)
2β3(1.23βπ+1)+2π+9
4+1
2
=β3.5129πβ1.23βπ+1
4+1
2,
where the ο¬rst inequality holds because π2β3πis increasing for π β₯3β2. Then,
πΌ(π)=π+βπβπ‘ββ2 β€β3.5129πβ1.23βπ+1
4+1
2+βπ
β1.23βπβββ2
β€β3.5129πβ1.23βπ+1
4+βπ
1.23 β3
2=βΆ β(π).
Let π(π) βΆ= β7.25πββ(π). Then, by the previous inequality,
π(1) = β7.25 β β3.5129 β 1.23 + 1
4β1
1.23 +3
2
=β7.25 β β2.5329 β 1
1.23 +3
2β1.79 >0.
Moreover,
πβ²(π)=β7.25
2βπ
β7.0258βπβ1.23
2βπβ14.0516πβ4.92βπ+1
β1
2.46βπ
Games and Economic Behavior 144 (2024) 203β224
214
J. Cembrano, F. Fischer, D. Hannon et al.
=
(2.46β7.25 β 2)β14.0516πβ4.92βπ+1β17.283468βπ+3.0258
4.92βπβ14.0516πβ4.92βπ+1
,
β₯
(2.46β7.25 β 2)β14.05πβ4.92βπ+1β17.3βπ+3
4.92βπβ14.0516πβ4.92βπ+1
,
=
45(2.46β7.25 β 2)β14.05πβ4.92βπ+ 1 β 778.5βπ+ 135
221.4βπβ14.0516πβ4.92βπ+1
,
which is non-negative when π β₯1.
To see this, note that the denominator of the last expression is positive and that 45(2.46β7.25 β 2) >208, so that πβ²(π) β₯0if
208β14.05πβ4.92βπ+1β₯778.5βπβ 135,
i.e., if
1796.95πβ 2663.88βπ+ 25039 β₯0.
This inequality indeed holds for every π β₯1. This is immediate for π β{1, 2, 3}. For π β₯4we have that π β₯2βπ, and thus the
expression on the left is greater than or equal to 930.02βπ+ 25039, which is clearly non-negative. We conclude that π(π) β₯0for
every π ββand thus πΌ(π) β€β(π) β€β7.25πfor every π β₯1, so πis
β7.25π-additive. β‘
Recalling Fig. 1, we note that for small values of π, the guarantee given by the optimal twin threshold mechanism is much smaller
than β7.25π, and that the bound becomes signiο¬cantly better than those given by the other mechanisms as πgrows. Closing the
gap between the lower bound of Theorem 4and the upper bound given by the optimal twin threshold mechanism is left as our main
open question.
4. A tight impossibility result for approval
So far, we have developed a new mechanism for impartial selection and have established an additive performance guarantee for
the mechanism relative to the maximum outdegree in the graph. We will now take a closer look at the case where the maximum
outdegree is unbounded, i.e., at the approval setting.
When applied to the approval setting, Theorem 1provides a performance guarantee of π(π). As the maximum indegree in a graph
with πvertices is π β1, this bound is trivially achieved by any impartial mechanism including the mechanism that never selects.
Caragiannis et al. (2022)have used a careful case analysis to show that deterministic impartial mechanisms cannot be better than
3-additive. We show that the trivial upper bound of π β1is in fact tight for all π, which means that the mechanism that never selects
provides the best possible additive performance guarantee among all deterministic impartial mechanisms. Our result is in fact more
general and again holds relative to the maximum outdegree π.
Theorem 2. Let π ββand π β€π β1. Let πbe an impartial deterministic selection mechanism such that πis πΌ-additive on ξ³π(π). Then
πΌβ₯π. In particular, if πis πΌ-additive on ξ³π, then πΌβ₯π β1.
In the practically relevant case where individuals are not allowed to abstain and the minimum outdegree is therefore at least 1,
a small improvement can be obtained by selecting a vertex with an incoming edge from a ο¬xed vertex, and again breaking ties by a
ο¬xed ordering of the vertices. The selected vertex then has indegree at least 1, which for the approval setting implies (π β2)-additivity.
This guarantee is again best possible.
Theorem 3. Let π ββand π β€π β1. Let πbe an impartial deterministic selection mechanism such that πis πΌ-additive on ξ³+
π(π). Then
πΌβ₯π β1. In particular, if πis πΌ-additive on ξ³+
π, then πΌβ₯π β2.
To prove both theorems we study the performance of impartial, but not necessarily deterministic, selection mechanisms on a
particular class of graphs which in the case of πvertices we denote by ξ³π
π. For each π ββ, a graph πΊ=(π, πΈ) βξ³πbelongs to ξ³π
π
if and only if there exists an π-partition of πfor some π β₯1, which we denote by (π1, β¦ , ππ), such that (i) π’ <π£for every π’ βππ,
and π£ βππwith π <π, and (ii) πΈ={(π’, π£) βππΓππβΆπ, πβ{1, β¦ , π}, π β€π, π’ β π£}. In other words, ξ³π
πcontains all graphs obtained by
taking an ordered partition of a set of πunlabeled vertices and adding edges from each vertex to all other vertices in the same part
and in greater parts. We will not be interested in isomorphic graphs within the class and thus only consider partitions of the vertices
in increasing order. A graph in ξ³π
πis thus characterized by the partition (π1, β¦ , ππ), or by the tuple (π 1, β¦ , π π)where π π=|ππ|for
Games and Economic Behavior 144 (2024) 203β224
215
J. Cembrano, F. Fischer, D. Hannon et al.
π (πΊ)
ππΊ
(1,1)
2
(2)
1
(1,1,1)
6
(1,2)
3
(2,1)
3
(3)
1
Fig. 5. Graphs in ξ³π
2and ξ³π
3.
each π β{1, β¦ , π}. For a given graph πΊβξ³π
π, we denote the former by π(πΊ), the latter by π (πΊ), and the length of π (πΊ)by π(πΊ).
Finally, for πΊβξ³π
π, let ππΊbe the number of graphs with πvertices isomorphic to πΊ, i.e.,
ππΊ=π!
βπ(πΊ)
π=1 (π (πΊ))π!
.
Fig. 5shows the graphs in ξ³π
2and ξ³π
3, along with their tuple representation π (πΊ)and associated values ππΊ. The sums, for π ββ, of
the values ππΊfor all graphs πΊβξ³π
πare known as Fubini numbers and count the number of weak orders on an π-element set. The
following lemma establishes a property of Fubini numbers that is readily appreciated for the cases shown in Fig. 5but in fact holds
for all π. The property was known previously (Diagana and MaΓ―ga, 2017), but we provide an alternative proof in Appendix Cfor the
sake of completeness.
Lemma 4. For every π ββ, π β₯1,
βπΊβξ³π
πππΊis an odd number.
For every pair of graphs πΊ, πΊβ²βξ³π
πand πβ{2, β¦ , π(πΊ)}, we say that there is a π-transition from πΊto πΊβ²if π(πΊ) =π(πΊβ²) +1,
(π (πΊ))π=1, and
(π (πΊβ²))π=β§
βͺ
β¨
βͺ
β©
(π (πΊ))πif πβ€πβ2,
(π (πΊ))π+1 if π=πβ1,
(π (πΊ))π+1 if πβ₯π.
Intuitively, a π-transition can be obtained by changing the outgoing edges of the single vertex in the set (π(πΊ))π, including not only
edges to vertices in βπ(πΊ)
π=π(π(πΊ))πbut also to vertices in (π(πΊ))πβ1. When the value of πis not relevant in a particular context, we
simply say that there is a transition from πΊto πΊβ²if there exists some πβ{2, β¦ , π(πΊ)} such that there is a π-transition from πΊto
πΊβ². Observe that for every pair of graphs πΊ, πΊβ²βξ³π
πthere is at most one πβ{2, β¦ , π(πΊ)} such that there is a π-transition from πΊto
πΊβ², and that if there is a transition from πΊto πΊβ², there cannot be a transition from πΊβ²to πΊ. This kind of relation between ordered
partitions has been exploited by Insko et al. (2017)for studying an expansion of the determinant, giving rise to a partial order on ξ³π
π.
In our context, it turns out to be relevant because whenever there is a π-transition from πΊto πΊβ², any impartial mechanism either
selects the vertex in (π(πΊ))πboth in πΊand πΊβ², or in none of them.
In the case of plurality, impartiality was shown by Holzman and Moulin (2013)to be incompatible with two further axioms:
positive unanimity, which requires for all πΊ=(π, πΈ) βξ³(1) that π£ βπ(πΊ)if πΏβ(π£) =|π| β1; and negative unanimity, which requires
for all πΊ=(π, πΈ) βξ³(1) that π£ βπ(πΊ)if πΏβ(π£) =0. This result holds even on a restricted class of graphs, consisting of a single
cycle and additional vertices with edges onto that cycle, and has immediate and very strong implications on the best multiplicative
approximation guarantee that an impartial mechanism can achieve. For additive performance guarantees, however, the incompat-
ibility of impartiality with the other two axioms implies only a lower bound of 2. We will see in the following that on the class
ξ³π
π, impartiality is incompatible with a single axiom that weakens positive and negative unanimity. Strong lower bounds regarding
additive performance guarantees for approval then follow immediately.
The class ξ³π
πis very diο¬erent, and has to be very diο¬erent, from the class of graphs used by Holzman and Moulin, and will
ultimately require a new analysis. We can, however, follow the approach of Holzman and Moulin to consider randomized mechanisms
rather than deterministic ones, which allows us without loss of generality to restrict attention to mechanisms that treat vertices
symmetrically. A randomized selection mechanism for ξ³is given by a family of functions πβΆξ³πβ[0, 1]πthat maps each graph to
a probability distribution on the set of its vertices, such that βπ
π=1 (π(πΊ))πβ€1for every graph πΊβξ³π. Analogously to the case
of deterministic mechanisms, we say that a randomized selection mechanism πis impartial on ξ³β²βξ³if for every pair of graphs
πΊ=(π, πΈ)and πΊβ²=(π, πΈβ²)in ξ³β²and every π£ βπ, (π(πΊ))π£=(π(πΊβ²))π£whenever πΈβ§΅({π£} Γπ) =πΈβ²β§΅({π£} Γπ). We say that a
randomized selection mechanism πsatisο¬es weak unanimity on ξ³πif for every πΊ=(π, πΈ) βξ³πsuch that πΏβ(π£) =π β1 for some
π£ βπ,
β
π’βπβΆπΏβ(π’)β₯1
(π(πΊ))π’β₯1.
Games and Economic Behavior 144 (2024) 203β224
216
J. Cembrano, F. Fischer, D. Hannon et al.
2
3
2
2
4
3
2
3
2
3
2
2
(1,1) (2)
(1,2)
(2,1)
(1,1,1)
(3)
(1,1,1,1)
(1,3)
(2,2)
(3,1)
(1,1,2)
(1,2,1)
(2,1,1)
(4)
Fig. 6. Directed versions of ξ΄2, ξ΄3, and ξ΄4. For π β{2, 3, 4}, each graph πΊβξ³π
πis represented by the tuple π (πΊ)and each edge (πΊ, πΊβ²)labeled with πββrepresents
a π-transition from πΊto πΊβ².
In other words, weak unanimity requires that a vertex with positive indegree is chosen with probability 1whenever there exists a
vertex with indegree π β1. We ο¬nally say that a randomized mechanism πis symmetric if it is invariant with respect to renaming of
the vertices, i.e., if for every πΊ=(π, πΈ) βξ³, every π£ βπand every permutation π=(π1, β¦ , π|π|)of π, (π(πΊπ))ππ£=(π(πΊ))π£, where
πΊπ=(π, πΈπ)with πΈπ={(ππ’, ππ£) βΆ(π’, π£) βπΈ}. For a given randomized mechanism π, we denote by πsthe mechanism obtained by
applying a random permutation πto the vertices of the input graph, invoking π, and permuting the result by the inverse of π. Thus,
for all π ββ, πΊβξ³π, and π£ βπ,
(πs(πΊ))π£=1
π!β
πβξΏπ
(π(πΊπ))ππ£,
where ξΏπis the set of all permutations π=(π1, β¦ , ππ)of a set of πelements.
The following lemma, which we prove in Appendix D, establishes that πsis symmetric for every randomized mechanism πand
inherits impartiality and weak unanimity from π. The lemma is a straightforward variant of a result of Holzman and Moulin and will
allow us to restrict attention to symmetric randomized mechanisms.
Lemma 5. Let πbe a randomized selection mechanism that is impartial and weakly unanimous on ξ³π. Then, πsis symmetric, impartial, and
weakly unanimous on ξ³π.
We are now ready to state our axiomatic impossibility result, which can be seen as a stronger version of that of Holzman and
Moulin for the case of unbounded outdegree. Both lower bounds follow easily from this result.
Lemma 6. For every π ββ, π β₯2, there exists no randomized selection mechanism πsatisfying impartiality and weak unanimity on ξ³π
π.
Proof. Let π ββ, π β₯2and suppose that there exists a randomized selection mechanism πsatisfying impartiality and weak una-
nimity on ξ³π. Since we can assume symmetry due to Lemma 5, for each graph πΊβξ³π
πwe have that for every π β{1, β¦ , π(πΊ)} and
every π’, π£ β(π(πΊ))π, (π(πΊ))π’=(π(πΊ))π£, and thus we denote this value simply as (π(πΊ))π. We consider for the proof an undirected
graph ξ΄π=(ξ³π
π, ξ²), such that for every pair of graphs πΊ, πΊβ²βξ³π
πwe have that {πΊ, πΊβ²} βξ²if and only if there is a transition from
πΊto πΊβ²or from πΊβ²to πΊ. By deο¬nition of a transition, for each {πΊ, πΊβ²} βξ²we have |π(πΊ) βπ(πΊβ²)| =1. Therefore, ξ΄πis bipartite
with partition (πΏπ, π
π)where πΏπ={πΊβξ³π
πβΆπ(πΊ)is even}and π
π={πΊβξ³π
πβΆπ(πΊ)is odd}. Fig. 6depicts the graphs ξ΄2, ξ΄3, and
ξ΄4. For each graph πΊβξ³π
π, we deο¬ne π(πΊ) =2if (π (πΊ))1=1and π(πΊ) =1otherwise.
Let πΊ=(π, πΈ)and πΊβ²=(π, πΈβ²)be two graphs in ξ³π
πsuch that there is a π-transition from πΊto πΊβ²for some πβ{2, β¦ , π(πΊ)}.
Denoting by π£the unique vertex in (π(πΊ))π, which is also in π(πΊβ²)πβ1, we have that πΈβ§΅({π£} Γπ) =πΈβ²β§΅({π£} Γπ), and since πis
impartial, (π(πΊ))π=(π(πΊβ²))πβ1. Therefore,
ππΊβ²β
(π (πΊβ²))πβ1 β
(π(πΊβ²))πβ1 =π!
βπ(πΊβ²)
π=1 (π (πΊβ²))π!
(π (πΊβ²))πβ1(π(πΊβ²))πβ1
=π!
((π (πΊβ²))πβ1 β1)!βπβ{1,β¦,π(πΊβ²)}⧡{πβ1} (π (πΊβ²))π!(π(πΊβ²))πβ1
=π!
((π (πΊ))πβ1)! βπβ{1,β¦,π(πΊ)}⧡{πβ1,π}(π (πΊ))π!(π(πΊ))π
=π!
βπβ{1,β¦,π(πΊ)} (π (πΊ))π!(π (πΊ))πβ
(π(πΊ))π
Games and Economic Behavior 144 (2024) 203β224
217
J. Cembrano, F. Fischer, D. Hannon et al.
Algorithm 2: Selection mechanism πbased on ππ.
Input: Digraph πΊ=(π, πΈ) βξ³π+1, mechanism ππand integer π β₯π +1.
Output: Set πof selected vertices with |π| β€1.
Let π»=(πβͺπβ², πΈ), where πβ²=βπβπβ1
π=1 {π’π};
Return ππ(π»)
=ππΊβ
(π (πΊ))πβ
(π(πΊ))π.
The ο¬rst two and last two equalities are obtained by replacing known expressions and simple calculations. The third equality comes
from the fact that (π (πΊβ²))π=(π (πΊ))πfor every π β€πβ2, (π (πΊβ²))πβ1 =(π (πΊ))πβ1 +1, and (π (πΊβ²))π=(π (πΊ))π+1 for every π β₯π. Moreover,
observe that for each πΊβξ³π
πand for each πβ{π(πΊ), β¦ , π(πΊ)}, there exists exactly one πΊβ²βξ³π
πsuch that there is a π-transition from
πΊto πΊβ²(if (π (πΊ))π=1) or a (π+1)-transition from πΊβ²to πΊ(if (π (πΊ))πβ₯2). Therefore,
β
πΊβπΏπ
π(πΊ)
β
π=π(πΊ)
ππΊβ
(π (πΊ))πβ
(π(πΊ))π=β
πΊβπ
π
π(πΊ)
β
π=π(πΊ)
ππΊβ
(π (πΊ))πβ
(π(πΊ))π.(10)
We now derive two important sets of inequalities. From the fact that πis a selection mechanism, for each πΊβξ³π
πwe have that
π(πΊ)
β
π=π(πΊ)
(π (πΊ))πβ
(π(πΊ))πβ€1,(11)
where replacing 1 by π(πΊ)on the left-hand side is possible since it can only make the sum smaller and thus keeps the inequality. On
the other hand, from the fact that πsatisο¬es weak unanimity, for each πΊβξ³π
πwe have that
β
π(πΊ)
β
π=π(πΊ)
(π (πΊ))πβ
(π(πΊ))πβ€β1,(12)
where we can omit the term for π =1on the left-hand side whenever (π (πΊ))1=1, because the vertex in (π(πΊ))1has indegree 0 in
such case.
In order to cancel out the left-hand sides of the previous inequalities, we assign a sign to each part of the bipartition of ξ΄π.
Let sign(πΏπ), sign(π
π) β{β1, 1} with sign(πΏπ) β
sign(π
π) =β1, and let sign(πΊ) =sign(πΏπ)for each πΊβπΏπand sign(πΊ) =sign(π
π)
for each πΊβπ
π. Summing up the inequalities (11)multiplied by ππΊfor every πΊβξ³π
πwith sign(πΊ) =1and the inequalities (12)
multiplied by ππΊfor every πΊβξ³π
πwith sign(πΊ) =β1, we obtain
β
πΊβξ³π
π
π(πΊ)
β
π=π(πΊ)
sign(πΊ)β
ππΊβ
(π (πΊ))πβ
(π(πΊ))πβ€β
πΊβξ³π
π
sign(πΊ)β
ππΊ.
By expression (10)the left-hand side is equal to 0. However, we know from Lemma 4that
βπΊβξ³π
πππΊis odd, so the right-hand side
cannot be equal to 0. For one of the two possible choices of sign(πΏπ)and sign(π
π)the right-hand side is negative, and we obtain
a contradiction. We conclude that a randomized selection mechanism πsatisfying impartiality and weak unanimity on ξ³πcannot
exist. β‘
As an illustration, the counterexamples constructed for π =3and π =4are shown in Fig. 7.
We are now ready to prove Theorems 2and 3. In order to be able to apply Lemma 6to deterministic mechanisms, we need a
simple deο¬nition. For a given deterministic selection mechanism πβΆξ³πβ2π, let πrand βΆξ³πβ[0, 1]πbe the randomized selection
mechanism such that (πrand(πΊ))π£=1if π£ βπ(πΊ)and (πrand(πΊ))π£=0otherwise. It is then easy to see that whenever πis impartial,
πrand is impartial as well.
Proof of Theorem 2.The result is straightforward when π =1. Let π β₯2and π β€π β1, and suppose that there is an impartial
deterministic selection mechanism ππwith
Ξ(πΊ)βπΏβ(ππ(πΊ),πΊ)β€πβ1
for every πΊβξ³π(π). We deο¬ne the deterministic selection mechanism πbased on ππas speciο¬ed in Algorithm 2. This mechanism
receives a graph πΊ=(π, πΈ)in ξ³π+1 and adds new vertices, if necessary to complete πvertices. These vertices are isolated, in the
sense that the set of edges in this new graph π»remains the same. For every input graph πΊ, the graph constructed belongs to ξ³π(π),
so the mechanism ο¬nally applies ππ. We claim that πrand is impartial and weakly unanimous on ξ³π
π+1. To see that πrand is weakly
unanimous, observe that
πΏβ(π£, π»)=πΏβ(π£, πΊ)for every π£βπ, and πΏβ(π£, π»)=0for every π£βπ.
Games and Economic Behavior 144 (2024) 203β224
218
J. Cembrano, F. Fischer, D. Hannon et al.
Fig. 7. Counterexamples for the existence of a randomized selection mechanism satisfying impartiality and weak unanimity for π =3and for π =4. The graphs are
depicted with the impartial probabilities assigned to each vertex with indegree at least one. The inequalities included below each of them are obtained from imposing
either that the probabilities sum up to at most 1βsince at most one vertex is to be selectedβor sum up to at least 1βdue to weak unanimity. The values in parentheses
show that the inequalities written for each set of graphs constitute an infeasible system because if one multiplies the corresponding inequality by them and sums the
resulting inequalities, the contradiction 0 β€β1 is achieved.
Algorithm 3: Selection mechanism πbased on π+
π.
Input: Digraph πΊ=(π, πΈ) βξ³π, mechanism π+
πand integer π β₯π +1.
Output: Set πof selected vertices with |π| β€1.
Let π»=(πβͺπβ², πΉ), where πβ²=βπβπ
π=1 {π’π}and πΉ=πΈβͺ(πβ²Γπ) βͺ({π£ βπβΆπΏ+(π£, πΊ) =0} Γ{π’1});
Return π+
π(π»)
For each πΊβξ³π
π+1, we have that Ξ(πΊ) =πand thus Ξ(π») =π. From the fact that ππis (π β1)-additive on ξ³π(π), we conclude that
πreturns a vertex π£βof π»with πΏβ(π£β, π») β₯π β(π β1) =1. This implies, in the ο¬rst place, that π£ββπ, thus πis indeed a selection
mechanism on ξ³π
π+1. Furthermore, we have πΏβ(π£β, πΊ) β₯1, thus
β
π£βπΊβΆπΏβ(π£)β₯1
(πrand(πΊ))π£=1,
i.e., πrand is weakly unanimous on ξ³π
π+1. Impartiality of πrand is straightforward since ππis impartial and the set of edges is not
modiο¬ed in the mechanism. This contradicts Lemma 6, so we conclude that mechanism ππcannot exist. β‘
Proof of Theorem 3.The result is straightforward when π β{1, 2}. Let π β₯3and π β€π β1, and suppose that there is an impartial
deterministic selection mechanism π+
πwith
Ξ(πΊ)βπΏβ(π+
π(πΊ),πΊ)β€πβ2
for every πΊβξ³+
π(π). We deο¬ne the deterministic selection mechanism πbased on π+
πas speciο¬ed in Algorithm 3. This mechanism
requires a graph πΊin ξ³πand adds new vertices πβ²={π’1, β¦ , π’πβπ}, as well as edges from each of these vertices to every vertex of πΊ,
and edges from every vertex of πΊwith outdegree zero to π’1. We ο¬rst claim that for every input graph πΊ, the graph π»constructed
in the mechanism belongs to ξ³+
π(π). Indeed, since πΊβξ³πevery vertex π£ βπsatisο¬es πΏ+(π£, πΊ) β€π β1. Moreover, an outgoing edge
to π’1is added for every π£with πΏ+(π£, πΊ) =0, thus 1 β€πΏβ(π£, π») β€π β1for each π£ βπ. On the other hand, each node in πβ²has
outdegree π. Therefore, the mechanism is well deο¬ned, in the sense that in its last step it applies π+
πto a graph in ξ³+
π(π). We claim
that πrand is impartial and weakly unanimous on ξ³π
π, which is a clear contradiction to Lemma 6and thus implies that mechanism π+
π
cannot exist. We prove the claim in what follows.
Games and Economic Behavior 144 (2024) 203β224
219
J. Cembrano, F. Fischer, D. Hannon et al.
For each πΊ=(π, πΈ) βξ³π
π, the set {π£ βπβΆπΏ+(π£) =0}is equal to (π(πΊ))π(πΊ)if (π (πΊ))π(πΊ)=1, or to the empty set, otherwise.
Therefore, for π’1, β¦ , π’πβπand π»as deο¬ned in the mechanism we have that πΏβ(π’1, π») β€1, πΏβ(π’π, π») =0for every πβ{2, β¦ , π βπ},
and πΏβ(π£, π») =πΏβ(π£, πΊ) +π βπfor every π£ βπ. Since Ξ(πΊ) =π β1from the deο¬nition of the set ξ³π
π, we have that Ξ(π») =π β1.
Using that π+
πis (π β2)-additive on ξ³+
π(π), we conclude that πreturns a vertex π£ββπβͺπβ²with πΏβ(π£β, π») β₯π β1 β(π β2) =
π βπ +1 β₯2. This implies, in the ο¬rst place, that π£ββπ, thus πis indeed a selection mechanism on ξ³π
π. Furthermore, we have
πΏβ(π£β, πΊ) =πΏβ(π£β, π») β(π βπ) β₯1, thus
β
π£βπΊβΆπΏβ(π£)β₯1
(πrand(πΊ))π£=1,
i.e., πrand is weakly unanimous on ξ³π
π.
To see that πis impartial on ξ³π
π, let πΊ=(π, πΈ), πΊβ²=(π, πΈβ²) βξ³π
πand ξ‘π£ βπbe such that πΈβ§΅({ ξ‘π£} Γπ) =πΈβ²β§΅({ ξ‘π£} Γπ).
Denoting πΉand πΉβ²the edges of the graphs deο¬ned in the mechanism πwhen run with input πΊand πΊβ², respectively, it is enough to
show that πΉβ§΅({ ξ‘π£} Γ(πβͺπβ²)) =πΉβ²β§΅({ ξ‘π£} Γ(πβͺπβ²)), because this would imply
π(πΊ)β©{ξ‘π£}=π+
π(πβͺπβ²,πΉ)β©{ξ‘π£}=π+
π(πβͺπβ²,πΉβ²)β©{ξ‘π£}=π(πΊβ²)β©{ξ‘π£}
where the second equality holds since π+
πis impartial on ξ³+
π(π)by hypothesis. Indeed,
πΉβ§΅({ ξ‘π£}Γ(πβͺπβ²)) = (πΈβͺ(πβ²Γπ)
βͺ({π£βπβΆπΏ+(π£, πΊ)=0}Γ{π’1})) ⧡({ ξ‘π£}Γ(πβͺπβ²))
=πΈβ§΅({ ξ‘π£}Γπ)βͺ(πβ²Γπ)
βͺ({π£βπ⧡{ξ‘π£}βΆπΏ+(π£, πΊ)=0}Γ{π’1})
=πΈβ²β§΅({ ξ‘π£}Γπ)βͺ(πβ²Γπ)
βͺ({π£βπ⧡{ξ‘π£}βΆπΏ+(π£, πΊβ²)=0}Γ{π’1})
=(πΈβ²βͺ(πβ²Γπ)
βͺ({π£βπβΆπΏ+(π£, πΊβ²)=0}Γ{π’1})) ⧡({ ξ‘π£}Γ(πβͺπβ²))
=πΉβ²β§΅({ ξ‘π£}Γ(πβͺπβ²)),
where the third equality uses the fact that the outgoing edges of every vertex in (πβͺπβ²) ⧡{ξ‘π£}are the same in πΊand πΊβ². This
implies that πrand is impartial as well, concluding the proof of the claim and the proof of the theorem. β‘
Theorems 2and 3provide tight bounds for the approval setting but have very weak implications for plurality. We end with small
but nontrivial lower bounds for the latter.
Theorem 4. Let π ββand let πbe an impartial deterministic selection mechanism such that πis πΌ-additive on ξ³π(1). Then, πΌβ₯πΌπ, where
πΌπ=β§
βͺ
β¨
βͺ
β©
1if πβ{2,3},
2if 4β€πβ€9,
3if πβ₯10.
Proof. Denote π1={2, 3}, π2={4, 5, β¦ , 9}, and π3={10, 11, β¦} for simplicity. The graphs in Fig. 8, Fig. 9, and Fig. 10 show the
probabilities that impartial randomized selection mechanisms on ξ³π(1) assign to each vertex for π βπ1, π2, and π3, respectively.
Vertices not shown in the ο¬gures have no incident edges. The inequalities below each graph πΊβξ³π(1) are obtained either from (i)
imposing that the corresponding mechanism on this set selects with probability 1a vertex with indegree at least Ξ(πΊ), Ξ(πΊ) β1, or
Ξ(πΊ) β2for πin π1, π2, or π3, respectively, or (ii) the fact that the probabilities assigned to the vertices of a single graph add up to at
most one. The values in parentheses show that the inequalities written for each set of graphs constitute an infeasible system because
if one multiplies the corresponding inequality by them and sums the resulting inequalities, the contradiction 0 β€β1 is achieved.
Deο¬ning πΌπas in the statement of the theorem, this shows that for π ββand for every randomized mechanism ββΆξ³πβββ [0, 1]π, there
exists πΊ=(π, πΈ) βξ³π(1) such that
β
π£βπβΆπΏβ(π£)β₯Ξβ(πΌπβ1)
(β(πΊ))π£<1.
Suppose now for contradiction that there exists π ββand πΌβ€πΌπβ1 such that there is an impartial deterministic selection
mechanism πwhich is πΌ-additive on ξ³π(1). It is clear that πrand is also impartial and, moreover, for every graph πΊ=(π, πΈ) βξ³π(1)
with Ξ(πΊ) β₯πΌπ,
Games and Economic Behavior 144 (2024) 203β224
220
J. Cembrano, F. Fischer, D. Hannon et al.
Fig. 8. Proof of impossibility of the existence of an impartial randomized selection mechanism selecting vertices with indegree Ξ(πΊ)for each graph πΊβξ³π(1) and
π β{2, 3}. Scaling and summing the inequalities leads to 0 β€β1, a contradiction.
Fig. 9. Proof of impossibility of the existence of an impartial randomized selection mechanism selecting vertices with indegree at least Ξ(πΊ) β1 for each graph
πΊβξ³π(1) and 4 β€π β€9. Scaling and summing the inequalities leads to 0 β€β1, a contradiction.
β
π£βπβΆπΏβ(π£)β₯Ξβ(πΌπβ1)
(πrand(πΊ))π£=1,
since π(πΊ) =π£βwith πΏβ(π£β) β₯Ξ β(πΌπβ1). But this contradicts the non-existence of such impartial randomized selection mechanisms.
We conclude that for every π ββ, if πis an impartial deterministic selection mechanism which is πΌ-additive on ξ³π(1), then πΌβ₯
πΌπ.β‘
It is worth noting that these bounds apply to the setting without abstentions as well, with the only diο¬erence that any deterministic
selection mechanism is impartial and 0-additive on ξ³+
2(1), thus the lower bound of 1 does not hold for π =2.
Declaration of competing interest
The authors declare that they have no known competing ο¬nancial interests or personal relationships that could have appeared to
inο¬uence the work reported in this paper.
Data availability
No data was used for the research described in the article.
Acknowledgments
We are grateful to the anonymous referees for their careful reading of the manuscript and their detailed comments. Funded by the
Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under project number 431465007 and by the Engineering
and Physical Sciences Research Council under grant EP/T015187/1.
Appendix A. Proof of Lemma 1
Let πΊand π£be as deο¬ned in the statement of the lemma. We prove the existence of vertices as claimed by induction over π. For
the base case, suppose that for every π’ βπβ(π£)it holds (πΏβ(π’), π’) βΊ(πΏβ(π£), π£). From the deο¬nition of the mechanism we thus have
that πβ(π’) >π
β(π£)for every π’ βπβ(π£)and therefore πΏβ(π£) =πΏβ(π£), which contradicts the hypothesis of the lemma.
Now, let πβ²β{0, β¦ , π β2}and assume that for every πβ{0, β¦ , πβ²}there is a vertex π’πsuch that (π’π, π£) βπΈand (πΏβ(π’π), π’π) β»
(πΏβ(π£) βπ, π£). Suppose that for every vertex π’ βπβ(π£) ⧡{π’1, β¦ , π’πβ²}it holds (πΏβ(π’), π’) βΊ(πΏβ(π£) β(πβ²+1), π£). The expression πΏβ(π£) β
(πβ²+1)is exactly the indegree of π£after deleting the incoming edges from π’0, β¦ , π’πβ², thus from the deο¬nition of the mechanism we
have that πβ(π’) >π
β(π£)for every π’ βπβ(π£) ⧡{π’0, β¦ , π’πβ²}. This yields
πΏβ(π£)β₯πΏβ(π£)β(πβ²+1)β₯πΏβ(π£)β(πβ1),
implying π β₯πΏβ(π£) βπΏβ(π£) +1. In the case π£ >π§, this is equivalent to πβ€πΏβ(π£), but these two inequalities contradict (π, π§) βͺ°(πΏβ(π£), π£).
If π£ <π§, on the other hand, it is equivalent to πβ€πΏβ(π£) β1, which is again a contradiction. This concludes the existence of vertices
π’0, β¦ , π’πβ1 as in the statement of the lemma.
Games and Economic Behavior 144 (2024) 203β224
221
J. Cembrano, F. Fischer, D. Hannon et al.
Fig. 10. Proof of impossibility of the existence of an impartial randomized selection mechanism selecting vertices with indegree at least Ξ(πΊ) β2 for each graph
πΊβξ³π(1) and π β₯10. Scaling and summing the inequalities leads to 0 β€β1, a contradiction.
To prove the last claim, we ο¬x (π, π§) =(πΏβ(π£), π£). We know that taking π =πΏβ(π£) βπΏβ(π£)there are vertices such that for each
πβ{0, 1, β¦ , π β1}, (π’π, π£) βπΈand (πΏβ(π’π), π’π) β»(πΏβ(π£) βπ, π£). Suppose that there is a vertex π’ βπβ(π£) ⧡{π’0, β¦ , π’πβ1}with (πΏβ(π’), π’) β»
(πΏβ(π£), π£). It is clear that
|{π’βπβ(π£)βΆ(πΏβ(π’),π’)β»(πΏβ(π£),π£)}|β₯π+1,
thus by expressions (1) and (2)we conclude that πΏβ(π£) βπΏβ(π£) β₯π +1, which is a contradiction.
Appendix B. Proof of Lemma 2
Since πΈ1⧡({π’} Γπ) =πΈ2⧡({π’} Γπ), it is clear that
πΏβ(π£, πΊ2)β₯πΏβ(π£, πΊ1)β1=π+π+(πΏβ(π£, πΊ1)βπΏβ(π£, πΊ1)) β 1 β π(π£>π§).(B.1)
In the following, we denote πβ²=π +(πΏβ(π£, πΊ1) βπΏβ(π£, πΊ1)) for ease of notation. If πΏβ(π£, πΊ2) =πΏβ(π£, πΊ1), then we have the equation
πβ²=πΏβ(π£, πΊ2) βπ+π(π£ >π§). In addition,
Games and Economic Behavior 144 (2024) 203β224
222
J. Cembrano, F. Fischer, D. Hannon et al.
Fig. B.11. Illustration of Lemma 2for the case πΏβ(π£, πΊ2) =πΏβ(π£, πΊ1) +1, shown on the left, and for the case πΏβ(π£, πΊ2) =πΏβ(π£, πΊ1), shown on the right. In contrast to
Fig. 2only the initial iteration π =0is shown, and the overall drop in the indegree of π£is illustrated by a dashed arrow. Observe that (πΏβ(π’0, πΊ2), π’0) β»(πΏβ(π£, πΊ1), π£) β»
(πΏβ(π’0, πΊ1), π’0)and (πΏβ(π’1, πΊ2), π’1) β»(πΏβ(π£, πΊ1) β1, π£), (πΏβ(π’1, πΊ1), π’1) βΊ(πΏβ(π£, πΊ1), π£).
(πΏβ(π£, πΊ2),π£)=(πΏβ(π£, πΊ1),π£)β»(π,π§)βͺ°(πΏβ(π£, πΊ2),π£),
thus from Lemma 1there are vertices π’β²
0, β¦ , π’β²
πβ²β1 such that for every πβ{0, β¦ , πβ²β1} we have that (π’β²
π, π£) βπΈ1β©πΈ2βsince
πΏβ(π£, πΊ2) =πΏβ(π£, πΊ1)we have πΈ1β©πβ(π£) =πΈ2β©πβ(π£)βand (πΏβ(π’β²
π, πΊ2), π’β²
π) β»(πΏβ(π£, πΊ2) βπ, π£). From expression (3), we know that
|{π’β{π’β²
0,β¦,π’
β²
πβ²β1}βΆ(πΏβ(π’, πΊ1),π’)β»(πΏβ(π£, πΊ1),π£)}|β€πΏβ(π£, πΊ1)βπΏβ(π£, πΊ1),
thus it is possible to take {π’0, β¦ , π’πβ1} β{π’β²
0, β¦ , π’β²
πβ²β1}with the property that the inequality (πΏβ(π’π, πΊ1), π’π) βΊ(πΏβ(π£, πΊ1), π£)also holds
for πβ{0, β¦ , π β1}. Moreover,
(πΏβ(π’π,πΊ
2),π’
π)β»(πΏβ(π£, πΊ2)βπβ((πΏβ(π£, πΊ1)βπΏβ(π£, πΊ1))),π£)=(πΏβ(π£, πΊ1)βπ,π£).(B.2)
Relabeling these vertices so that (πΏβ(π’0, πΊ2), π’0) β»β― β»(πΏβ(π’πβ1, πΊ2), π’πβ1)it is clear that the previous inequalities still hold, and in
particular
(πΏβ(π’0,πΊ
2),π’
0)β»(πΏβ(π£, πΊ1),π£)β»(πΏβ(π’0,πΊ
1),π’
0).
We conclude that Condition (ii) holds.
Similarly, if πΏβ(π£, πΊ2) =πΏβ(π£, πΊ1) +1, then πβ²+1 =πΏβ(π£, πΊ2) βπ+π(π£ >π§). As before, (πΏβ(π£, πΊ2), π£) β»(π, π§) βͺ°(πΏβ(π£, πΊ2), π£), thus
from Lemma 1there are vertices π’β²
0, β¦ , π’β²
πβ²such that for every πβ{0, β¦ , πβ²}we have that (π’β²
π, π£) βπΈ2and
(πΏβ(π’β²
π,πΊ
2),π’
β²
π)β»(πΏβ(π£, πΊ2)βπ,π£).
But |(πΈ2β©πβ(π£)) ⧡(πΈ1β©πβ(π£))| =1, thus at least πβ²of these vertices π’β²
πare such that (π’β²
π, π£) βπΈ1β©πΈ2. As before, from expression (3)
we conclude that it is possible to take {π’0, β¦ , π’πβ1} β{π’β²
0, β¦ , π’β²
πβ²}such that (π’π, π£) βπΈ1β©πΈ2and (πΏβ(π’π, πΊ1), π’π) βΊ(πΏβ(π£, πΊ1), π£)for
every πβ{0, β¦ , π β1}. Since expression (B.2)still holds, relabeling the vertices such that (πΏβ(π’0, πΊ2), π’0) β»β― β»(πΏβ(π’πβ1, πΊ2), π’πβ1)
we conclude the lemma with Condition (ii) as well. An example for each of the cases addressed so far is included in Fig. B.11.
In what follows, we suppose that the ο¬rst inequality in Condition (B.1)is an equality, so (ξ‘π£, π£) βπΈ1⧡πΈ2and (πΈ2β©πβ(π£)) β
(πΈ1β©πβ(π£)). In this case, πβ²β1 =πΏβ(π£, πΊ2) βπ+π(π£ >π§). Suppose ο¬rst that (πΏβ(π£, πΊ1) β1, π£) β»(π, π§), thus
(πΏβ(π£, πΊ2),π£)=(πΏβ(π£, πΊ1)β1,π£)β»(π,π§)βͺ°(πΏβ(π£, πΊ2),π£).
In this case, from Lemma 1there are vertices π’β²
0, β¦ , π’β²
πβ²β2 such that for all πβ{0, β¦ , πβ²β2} we have that (π’β²
π, π£) βπΈ1β©πΈ2and
(πΏβ(π’β²
π, πΊ2), π’β²
π) β»(πΏβ(π£, πΊ2) βπ, π£). If (πΏβ(ξ‘π£, πΊ1), ξ‘π£) β»(πΏβ(π£, πΊ1), π£), from expression (3)we have that
|{π’β{π’β²
0,β¦,π’
β²
πβ²β2}βΆ(πΏβ(π’, πΊ1),π’)β»(πΏβ(π£, πΊ1),π£)}|β€πΏβ(π£, πΊ1)βπΏβ(π£, πΊ1)β1.
Therefore, we conclude once again that it is possible to take {π’0, β¦ , π’πβ1} β{π’β²
0, β¦ , π’β²
πβ²β2}such that (πΏβ(π’π, πΊ1), π’π) βΊ(πΏβ(π£, πΊ1), π£)
for every πβ{0, β¦ , π β1}. We also have that
(πΏβ(π’π,πΊ
2),π’
π)β»(πΏβ(π£, πΊ2)βπβ(πΏβ(π£, πΊ1)βπΏβ(π£, πΊ1)β1),π£)=(πΏβ(π£, πΊ1)βπ,π£),
so after relabeling the vertices with (πΏβ(π’0, πΊ2), π’0) β»β― β»(πΏβ(π’πβ1, πΊ2), π’πβ1)Condition (ii) follows again. On the other hand, if
(πΏβ(ξ‘π£, πΊ1), ξ‘π£) βΊ(πΏβ(π£, πΊ1), π£), from expression (3)
|{π’β{π’β²
0,β¦,π’
β²
πβ²β2}βΆ(πΏβ(π’, πΊ1),π’)β»(πΏβ(π£, πΊ1),π£)}|β€πΏβ(π£, πΊ1)βπΏβ(π£, πΊ1).
Thus, it is possible to take {π’1, β¦ , π’πβ1} β{π’β²
0, β¦ , π’β²
πβ²β2}such that both (πΏβ(π’π, πΊ2), π’π) β»(πΏβ(π£, πΊ1) βπ, π£)and (πΏβ(π’π, πΊ1), π’π) βΊ
(πΏβ(π£, πΊ1), π£)hold for every πβ{1, β¦ , π β1}. In addition, whenever (πΏβ(π£, πΊ1), π£) βΊ(πΏβ(ξ‘π£, πΊ1), ξ‘π£)we know from Lemma 1that,
taking ξ‘πβ²=πΏβ(ξ‘π£, πΊ1) βπΏβ(ξ‘π£, πΊ1) +π(ξ‘π£>π£), there exist vertices ξ‘π’0, β¦ , ξ‘π’ξ‘πβ²β1, diο¬erent than ξ‘π£, such that for every πβ{0, β¦ , ξ‘πβ²β1}
it holds (ξ‘π’π, ξ‘π£) βπΈand (πΏβ(ξ‘π’π, πΊ1), ξ‘π’π) β»(πΏβ(ξ‘π£, πΊ1) βπ, ξ‘π£). Taking the ο¬rst ξ‘π =ξ‘πβ²β(πΏβ(π£, πΊ1) βπΏβ(ξ‘π£, πΊ1)) such vertices and π’0=ξ‘π£,
Condition (i) follows.
Finally, if πΏβ(π£, πΊ2) =πΏβ(π£, πΊ1) β1 and (πΏβ(π£, πΊ1) β1, π£) βΊ(π, π§), we obtain from the inequality (π, π§) βΊ(πΏβ(π£, πΊ1), π£)that
πΏβ(π£, πΊ1) =πΏβ(π£, πΊ1)and π =1. Therefore, we must have (πΏβ(ξ‘π£, πΊ1), ξ‘π£) βΊ(πΏβ(π£, πΊ1), π£), and the same analysis above leads to the
existence of vertices ξ‘π’0, β¦ , ξ‘π’ξ‘πβ1, diο¬erent than ξ‘π£, such that for every πβ{0, β¦ , ξ‘π β1} it holds (ξ‘π’π, ξ‘π£) βπΈand (πΏβ(ξ‘π’π, πΊ1), ξ‘π’π) β»
(πΏβ(ξ‘π£, πΊ1) βπ, ξ‘π£). Condition (i) follows in this case as well. An example is shown in Fig. B.12.
Games and Economic Behavior 144 (2024) 203β224
223
J. Cembrano, F. Fischer, D. Hannon et al.
Fig. B.12. Illustration of Lemma 2for the case where πΏβ(π£, πΊ2) =πΏβ(π£, πΊ1) β1with (πΏβ(π£, πΊ1), π£) βΊ(πΏβ(ξ‘π£, πΊ1), ξ‘π£). Only the initial iteration π =0is shown, and the
overall drop in the indegree of ξ‘π£ is illustrated by a dashed arrow. Observe that (πΏβ(ξ‘π’π, πΊ1), ξ‘π’π) β»(πΏβ(ξ‘π£, πΊ1) βπ, ξ‘π£)for πβ{0, 1}.
Appendix C. Proof of Lemma 4
Let ξ³β²
π={πΊβξ³π
πβΆ(π (πΊ))π=(π (πΊ))π(πΊ)+1βπfor every π β{1, β¦ , π(πΊ)}} be the set of graphs πΊβξ³π
πsuch that the tuple π (πΊ)is
symmetric. From the deο¬nition of ξ³π
π, it is clear that for every graph πΊwith a non-symmetric tuple π (πΊ), i.e., for every graph
πΊβξ³π
π⧡ξ³β²
π, there exists a unique π»βξ³π
π⧡(ξ³β²
πβͺ{πΊ}) such that π(πΊ) =π(π») =βΆ πand (π (πΊ))π=(π (π»))π+1βπfor every π β{1, β¦ , π}.
Moreover, ππΊ=ππ»for such a pair of graphs. This implies that
β
πΊβξ³π
π⧡ξ³β²
π
ππΊ
is even. In what follows we show how to conclude the lemma using the following claim: for every πΊβξ³β²
πwith π(πΊ) β₯2, ππΊis even.
Observe that
β
πΊβξ³π
π
ππΊ=β
πΊβξ³π
π⧡ξ³β²
π
ππΊ+β
πΊβξ³β²
πβΆπ(πΊ)β₯2
ππΊ+β
πΊβξ³β²
πβΆπ(πΊ)=1
ππΊ.
If the claim is true, we have that the ο¬rst two sums on the right-hand side are even. The third sum only contains one term, namely
ππΊfor the complete graph πΊ, for which π (πΊ) =(π)and thus ππΊ=π!βπ! =1. Therefore,
βπΊβξ³π
πππΊis the sum of an even term plus 1,
and we conclude the result.
We now prove the claim. Let πΊβξ³β²
πwith π(πΊ) β₯2. The multiplicity of the prime factor 2 in the numerator of ππΊ, due to Legendreβs
formula, is simply
β
β
π=1 βπ
2πβ,
while its multiplicity in the denominator is
π(πΊ)
β
π=1
β
β
π=1 β(π (πΊ))π
2πβ.
Therefore, we need to prove that this last term is strictly lower than the former. It is easy to see that for every πββ, πβ₯1we have
βπ(πΊ)
π=1 β(π (πΊ))π
2πββ€βπ
2πβ, since without the ο¬oor functions we would have the equality, and the fractional parts of the terms (π (πΊ))πβ2π
must add up βwhen summing over πβ to at least the fractional part of πβ2π. We now show that there exists some πβ²for which this
inequality is strict, by distinguishing two cases. If (π (πΊ))πβ€πβ2 for every π β{1, β¦ , π(πΊ)}, we let πβ²ββsuch that 2πβ²β€π <2πβ²+1,
and then the following holds:
π(πΊ)
β
π=1 β(π (πΊ))π
2πβ²ββ€
π(πΊ)
β
π=1 βπβ2
2πβ²β=
π(πΊ)
β
π=1 βπ
2πβ²+1 β=0<1=βπ
2πβ²β.
On the other hand, if (π (πΊ))πβ²>πβ2 for some πβ²β{1, β¦ , π(πΊ)}, from the symmetry of π (πΊ)we have that π(πΊ)is odd and, moreover,
πβ²=(π(πΊ) +1)β2. We now deο¬ne πβ²ββsuch that 2πβ²β€π β(π (πΊ))πβ²<2πβ²+1, which implies (π (πΊ))πβ€πβ(π (πΊ))πβ²
2<2πβ²for every π β πβ².
Therefore, the following holds:
π(πΊ)
β
π=1 β(π (πΊ))π
2πβ²β=β(π (πΊ))πβ²
2πβ²ββ€βπβ2
πβ²
2πβ²β=βπ
2πβ²β1
β<βπ
2πβ²β.
In either case, we obtain that
π(πΊ)
β
π=1
β
β
π=1 β(π (πΊ))π
2πβ<
β
β
π=1 βπ
2πβ,
and thus ππΊis even, which concludes the proof of the claim and the proof of the lemma.
Games and Economic Behavior 144 (2024) 203β224
224
J. Cembrano, F. Fischer, D. Hannon et al.
Appendix D. Proof of Lemma 5
To see that πsis impartial, let πΊ=(π, πΈ), πΊβ²=(π, πΈβ²) βξ³πand π£ βπsuch that πΈβ§΅({π£} Γπ) =πΈβ²β§΅({π£} Γπ). Since πis
impartial,
(πs(πΊ))π£=1
π!β
πβξΏπ
(π(πΊπ))ππ£=1
π!β
πβξΏπ
(π(πΊβ²
π))ππ£=(πs(πΊβ²))π£,
and thus πsis impartial.
To prove that πssatisο¬es weak unanimity, let πΊ=(π, πΈ) βξ³πand π£ βπwith πΏβ(π£) =π β1. Since πsatisο¬es weak unanimity,
β
π’βπβΆπΏβ(π’)β₯1
(πs(πΊ))π’=β
π’βπβΆπΏβ(π’)β₯1
1
π!β
πβξΏπ
(π(πΊπ))ππ’=1
π!β
πβξΏπβ
π’βπβΆπΏβ(π’)β₯1
(π(πΊπ))ππ’
β₯1
π!β
πβξΏπ
1=1.
This concludes the proof of the lemma.
References
Alon, N., Fischer, F., Procaccia, A., Tennenholtz, M., 2011. Sum of us: strategyproof selection from the selectors. In: Proceedings of the 13th Conference on Theoretical
Aspects of Rationality and Knowledge, pp. 101β110.
Aziz, H., Lev, O., Mattei, N., Rosenschein, J.S., Walsh, T., 2019. Strategyproof peer selection using randomization, partitioning, and apportionment. Artif. Intell. 275,
295β309.
Babichenko, Y., Dean, O., Tennenholtz, M., 2020. Incentive-compatible selection mechanisms for forests. In: Proceedings of the 21st ACM Conference on Economics
and Computation, pp. 111β131.
Bjelde, A., Fischer, F., Klimm, M., 2017. Impartial selection and the power of up to two choices. ACM Trans. Econ. Comput. 5, 1β20.
Bousquet, N., Norin, S., Vetta, A., 2014. A near-optimal mechanism for impartial selection. In: Proceedings of the 10th International Conference on Web and Internet
Economics. Springer, pp. 133β146.
Caragiannis, I., Christodoulou, G., Protopapas, N., 2022. Impartial selection with additive approximation guarantees. Theory Comput. Syst. 66, 721β742.
Caragiannis, I., Christodoulou, G., Protopapas, N., 2023. Impartial selection with prior information. In: Proceedings of the ACM Web Conference, pp. 3614β3624.
De Clippel, G., Moulin, H., Tideman, N., 2008. Impartial division of a dollar. J. Econ. Theory 139, 176β191.
Diagana, T., MaΓ―ga, H., 2017. Some new identities and congruences for Fubini numbers. J. Number Theory 173, 547β569.
Fischer, F., Klimm, M., 2015. Optimal impartial selection. SIAM J. Comput. 44, 1263β1285.
Holzman, R., Moulin, H., 2013. Impartial nominations for a prize. Econometrica 81, 173β196.
Insko, E., Johnson, K., Sullivan, S., 2017. An ordered partition expansion of the determinant. Integers 17, A36.
Kahng, A., Kotturi, Y., Kulkarni, C., Kurokawa, D., Procaccia, A.D., 2018. Ranking wily people who rank each other. In: Proceedings of the 32nd AAAI Conference on
Artiο¬cial Intelligence.
Kurokawa, D., Lev, O., Morgenstern, J., Procaccia, A.D., 2015. Impartial peer review. In: Proceedings of the 24th International Joint Conference on Artiο¬cial Intelli-
gence.
Mackenzie, A., 2015. Symmetry and impartial lotteries. Games Econ. Behav. 94, 15β28.
Mackenzie, A., 2020. An axiomatic analysis of the papal conclave. Econ. Theory 69, 713β743.
Mattei, N., Turrini, P., Zhydkov PeerNomination, S., 2021. Relaxing exactness for increased accuracy in peer selection. In: Proceedings of the 29th International Joint
Conferences on Artiο¬cial Intelligence, pp. 393β399.
Niemeyer, A., Preusser, J., 2023. Simple allocation with correlated types. Working Paper.
Olckers, M., Walsh, T., 2022. Manipulation and peer mechanisms: a survey. arXiv preprint. arXiv :2210 .01984.
Tamura, S., Ohseto, S., 2014. Impartial nomination correspondences. Soc. Choice Welf. 43, 47β54.
Xu, Y., Zhao, H., Shi, X., Shah, N.B., 2019. On strategyproof conference peer review. In: Proceedings of the 28th International Joint Conference on Artiο¬cial Intelligence,
pp. 616β622.
Zhang, X., Zhang, Y., Zhao, D., 2021. Incentive compatible mechanism for inο¬uential agent selection. In: Proceedings of the 14th International Symposium on
Algorithmic Game Theory. Springer, pp. 79β93.
