Paper deep dive
Characterizing Necessary Losers to Explain Tournaments Losers
Contet Clément, Umberto Grandi, Jérôme Mengin
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study the problem of formally explaining why a candidate was not selected by a given tournament rule, by identifying sub-tournaments in which the candidate loses independently of how the rest of the tournament is completed. We define destructive minimal supports as any minimal sub-tournaments satisfying this property, which in formal explainable artificial intelligence correspond to abductive explanations for the question "Why does the loser lose the tournament?". For six common tournament solutions (maximin, uncovered set and its weighted variant, top-cycle, Copeland, and Borda) we provide characterizations of when a candidate is either a necessary loser or a possible winner, we determine the size of the smallest destructive minimal supports, complemented by polynomial-time algorithms for their computation except for the case of the Borda rule which is suspected to be NP-complete.
Tags
Links
- Source: https://arxiv.org/abs/2608.23446v1
- Canonical: https://arxiv.org/abs/2608.23446v1
Trouble viewing inline? Open PDF directly →
Full Text
101,038 characters extracted from source content.
Expand or collapse full text
Characterizing Necessary Losers to Explain Tournaments Losers Clément Contet Affiliation: Institut de Recherche en Informatique de Toulouse (IRIT) Affiliation: Université de Toulouse Umberto Grandi Affiliation: Institut de Recherche en Informatique de Toulouse (IRIT) Affiliation: Université Toulouse Capitole Jérôme Mengin Affiliation: Institut de Recherche en Informatique de Toulouse (IRIT) Affiliation: Université de Toulouse Abstract We study the problem of formally explaining why a candidate was not selected by a given tournament rule, by identifying sub-tournaments in which the candidate loses independently of how the rest of the tournament is completed. We define destructive minimal supports as any minimal sub-tournaments satisfying this property, which in formal explainable artificial intelligence correspond to abductive explanations for the question “Why does the loser lose the tournament?”. For six common tournament solutions (maximin, uncovered set and its weighted variant, top-cycle, Copeland, and Borda) we provide characterizations of when a candidate is either a necessary loser or a possible winner, we determine the size of the smallest destructive minimal supports, complemented by polynomial-time algorithms for their computation except for the case of the Borda rule which is suspected to be NP-complete. Keywords: Computational Social Choice Voting Explainability. 1 Introduction 00footnotetext: This paper is the extended version of Contet, Grandi, Mengin. Characterizing Necessary Losers to Explain Tournaments Losers. In: Proceedings of the 9th International Conference on Algorithmic Decision Theory (ADT) (2026). Why do people accept the outcome of decision making processes? If it seems natural that people follow decisions which are favorable to them, it is less clear to see why they would conform to disadvantageous outcomes. Procedural justice theory, developed in the late 1990s and early 2000s by Tyler [30, 29] and Hibbing and Theiss-Morse [21], claims that the willingness to accept and to obey the outcome of a decision making process not only depends on the outcome per se but also on the process that leads to it. If the primary influence on the individual position toward an outcome is its favorability, a process perceived with a higher procedural fairness, i.e., which treats all stakeholders fairly, increases the legitimacy and trustworthiness of the decision, the process in itself and more generally the responsible entity. This in turn leads to more acceptance and conformance with the decision. More recently, Carman [7] showed that this theory holds for participatory democracy, in particular for petitioning systems. It is important to realize that it is all about perceived fairness, as Tyler states: “When authorities are presenting their decisions to the people influenced by them, they need to make clear that they have listened to and considered the arguments made. They can do so by accounting for their decisions.” [29]. A practical example of this is the work of Suryanarayana et al. [28] establishing that providing explanations for election outcomes could increase satisfaction and acceptance of voters, especially for those with less favorable outcomes. These results as well as numerous voices in the computational social choice community [19] have called for efforts to make collective decision-making processes more accessible to a wider audience by developing tools to explain their inner workings. More generally, this movement is in line with the field of Explainable Artificial Intelligence (XAI) which aims at making algorithms more understandable to human users (see Miller [24] for an introduction). Building on previous work on transparency [11], de Fine Licht and de Fine Licht [12] and Grimmelikhuijsen [18] showed that from a social sciences perspective, the basic transparency approach consisting of simply making public all the information to enable anyone to recompute and verify algorithmic decisions is insufficient to foster trust.11 1 This body of works distinguishes between fishbowl transparency, i.e., full openness of the decision-making process, and transparency in rationale, that is public receiving dedicated information for the justification or explanation of the decision. Our notion ofexplainability is associated to the latter. For collective decisions, this implies that simply publishing the individual vote counts and the rule used may not be enough. In the computational social choice literature, multiple methods to specifically explain or justify the outcome of an election have been proposed. In a classical social choice approach, a first line of works unfolds some logical reasonings based on desirable axiomatic properties to justify the election of one alternative [2, 6, 25, 26]. A second method presents the stakeholders with manually or automatically curated statistics on the expressed preferences supporting a specific outcome [28]. Finally, a third line of work [9, 10] uses abductive reasoning to explain why an alternative is in the winning set. All approaches have their strengths and weaknesses, however, each only allows to generate explanations supporting why an alternative was selected and not why an alternative was not selected. We see this as an important drawback as procedural justice theory has shown that explanations of decisions are particularly important to maintain trust and legitimacy in the case of an adverse outcome [5, 8]. Inspired by the literature on control and bribery [14, 15] which distinguishes between constructive bribery where the goal is to change votes to make a losing candidate elected, and destructive bribery where an elected candidate becomes unelected, we introduce the notion of destructive minimal supports to answer the question “Why was this candidate not selected?” with abductive reasoning. To produce compact explanations for the election outcome, our approach uses tournaments which are a classical structure in social choice to compactly represent pairwise comparisons over a set of possible alternatives such as contending teams in sports, preferences expressed over candidates in an election or possible outcomes in a decision making problem (for an introduction see [3, 16]). Destructive minimal supports are partial sub-tournaments of the initial tournament in which the scrutinized losing candidate loses in all possible completions. That is, the candidate is a necessary loser of the sub-tournament, or, equivalently, not a possible winner. This problem can be seen as the dual of the Margin of Victory (MoV) problem [4, 13] where one is looking for minimal changes in the tournament to change the outcome of the election. More generally, this work fits in the literature on the problem of finding necessary and possible winners in election with partial information [1, 22, 23, 27, 31]. Paper structure. In Section 2, we recall classical notions on tournaments. In Section 3, we define destructive minimal supports for the losing candidate l for a tournament solution S in a tournament G as the set of inclusion minimal sub-tournaments of G where l is a necessary loser, i.e., loses in all completions of those sub-tournaments. In Section 4, we characterize partial tournaments where a specific candidate is a necessary loser, or, equivalently, not a possible winner for the following six tournament solutions : the maximin rule, the uncovered set and its weighted variant, the top-cycle, the Copeland rule, and the Borda rule. Finally, in Section 5 we study the smallest destructive minimal supports that is the destructive minimal supports comprised of the smallest amount of pairwise comparisons, we provide explicit formulas and bounds for their size, and we show how to obtain them efficiently. See Table 1 for a preview of our results. All missing proofs are available in the Appendix. Tournament Solution Necessary Loser Characterization Upper bound on SdMS size Top Cycle (TC)( ) ∃K⊆∖l∃ K \l\ s.t. K≠∅K≠ , ∀c,c′∈K×(∖K)∀ c,c ∈ K×(C K), μ(c,c′)=1μ(c,c )=1. (Theorem 4.1) ⌈m2⌉⌊m2⌋ m2 m2 (Theorem 5.1) Borda (BO)( ) ∃K⊆∖l∃ K \l\ s.t. minc∈KG′∈[G]σBO(c,G′)>maxG′∈[G]σBO(l,G′) _G ∈[G] E_c∈ K _ (c,G )> _G ∈[G] _ (l,G ). (Theorem 4.2, Schwartz [27]) n(m−1)+1n(m-1)+1 (Theorem 5.2) Copeland (CO)( ) ∃K⊆∖l∃ K \l\ s.t. minc∈KG′∈[G]σCO(c,G′)>maxG′∈[G]σCO(l,G′) _G ∈[G] E_c∈ K _ (c,G )> _G ∈[G] _ (l,G ). (Corollary of Theorem 4.2) m (Theorem 5.3) Maximin (M)( ) ∃ a tree T=(K,E)T=(K,E) s.t. K⊆∖lK \l\, ∀c,c′∈K×(∖l,c)∀ c,c ∈ K×(C \l,c\), c,c′∉E\c,c \ ∈ E ⟹μ(c,c′)>n−maxc′∈μ(c′,l) μ(c,c )>n- _c μ(c ,l). (Theorem 4.3) ⌈n+12⌉(m−2)+n+1 n+12 (m-2)+n+1 (Theorem 5.4) Weighted Uncovered Set (wUC)( ) ∃ a tree T=(K,E)T=(K,E) s.t. K⊆∖lK \l\, ∀c,c′∈K×(∖l,c)∀ c,c ∈ K×(C \l,c\), μ(c,l)≥n2μ(c,l)≥ n2, c,c′∉E⟹μ(c,c′)+μ(c′,l)≥n\c,c \ ∈ E μ(c,c )+μ(c ,l)≥ n.* (Theorem 4.4) n(m−2)+⌈n+12⌉n(m-2)+ n+12 (Theorem 5.5) Uncovered Set (UC)( ) ∃ a tree T=(K,E)T=(K,E) s.t. K⊆∖lK \l\, ∀c,c′∈K×(∖l,c)∀ c,c ∈ K×(C \l,c\), μ(c,l)=1μ(c,l)=1, c,c′∉E⟹μ(c,c′)+μ(c′,l)≥1\c,c \ ∈ E μ(c,c )+μ(c ,l)≥ 1.* (Corollary of Theorem 4.4) m−1m-1 (Corollary 1) * At least one of all the inequalities has to be strict. Table 1: Overview of our results for a tournament G=(,μ)G=(C,μ) with n voters, m candidates in C, and l the losing candidate considered. σBO(l,G) _ (l,G) and σCO(l,G) _ (l,G) are the Borda and Copeland scores of l in G. [G][G] is the set of all completions of G. All bounds are tight. 2 Preliminaries Let the number of voters n be a strictly positive integer. Aziz et al. [1] define a partial n-weighted tournament as a pair G=(,μ)G=(C,μ) where C is a nonempty finite set of candidates and μ:×→0,…,nμ:C×C→\0,…,n\ a weight function such that for all distinct x,y∈x,y , μ(x,y)+μ(y,x)≤nμ(x,y)+μ(y,x)≤ n and μ(x,x)=0μ(x,x)=0. A (complete) n-weighted tournament satisfies for all distinct x,y∈x,y , μ(x,y)+μ(y,x)=nμ(x,y)+μ(y,x)=n. Naturally, an (unweighted) tournament is a 11-weighted tournament. Example 1 aabbccddee (a) G aabbccddee225555113333333322334422224444221111 (b) GwG_w aabbccddee (c) GpG_p Figure 1: An (unweighted) tournament G (1(a)), a 5-weighted tournament GwG_w(1(b)), and an (unweighted) partial tournament GpG_p (1(c)). Throughout this paper, edges with a weight of 00 are not shown and edge labels are omitted in the unweighted case. In Figure 1(a), the edge of G between the pair of alternatives a and b shows that a is preferred to b. In Figure 1(b), the edge from a to b with a weight of 22 in GwG_w shows that a is preferred to b by 22 voters. Given a tournament G it is then possible to select a set of desirable candidates using a tournament solution S (also called tournaments rule) which is a function taking a tournament as input and returning the winners set as a non-empty subset of candidates noted S(G)S(G). We focus on the following set of classical tournament solutions. • The top cycle (TC ) is the unique minimal dominant nonempty subset of candidates of an unweighted tournament G, where a nonempty subset of candidates A⊆A is called dominant in G=(,μ)G=(C,μ) if for each candidates x∈Ax∈ A and y∈∖Ay A, μ(x,y)=1μ(x,y)=1. Alternatively, TC can also be defined as the set of candidates that can reach every other candidate via a directed path in G or, in terms of graph theory, as the unique (since G is complete) top strongly connected component of G. • The weighted uncovered set (wUC ) is the nonempty subset of candidates that are not strictly weighted covered by any other candidate in a weighted tournament G=(,μ)G=(C,μ) where a candidate x∈x is said to strictly cover another candidate y∈y if for all z∈z , μ(x,z)≥μ(y,z)μ(x,z)≥μ(y,z) and at least one inequality is strict. For unweighted tournaments, we simply talk about uncovered set (UC ). • The Borda score of a candidate c∈c in a weighted tournament G=(,μ)G=(C,μ) is σBO(c,G)=∑c′∈μ(c,c′) _ (c,G)= _c μ(c,c ). The Borda rule (BO ) selects candidates that have a maximal Borda score. • The Copeland score of a candidate c∈c in an unweighted tournament G=(,μ)G=(C,μ) is σCO(c,G)=|c′:c′∈,μ(c,c′)=1| _ (c,G)=|\c :c ,μ(c,c )=1\|. The Copeland rule (CO ) selects candidates that have a maximal Copeland score. It can be seen as the restriction of BO to unweighted tournaments. • The maximin score of a candidate c∈c in a weighted tournament G=(,μ)G=(C,μ) is σM(c,G)=minc′∈∖cμ(c,c′) _ (c,G)= _c \c\μ(c,c ). The maximin rule (M ) selects candidates that have a maximal maximin score. 3 (Smallest) Destructive Minimal Supports for Tournaments To explain why a candidate c loses a tournament G, abductive reasoning extracts a subset minimal set of features of the tournament G ensuring that the scrutinized candidate loses. We call destructive minimal supports such minimal sub-tournaments of G where c loses independently of the rest of the tournament. Given two partial tournaments G=(,μ)G=(C,μ) and G′=(,μ′)G =(C,μ ), we say that G′G is an extension of G denoted G⊆G′G G if for all distinct x,y∈x,y , μ(x,y)≤μ′(x,y)μ(x,y)≤μ (x,y). We refer to [G][G] as the set of all complete extensions of G. We introduce the notion of necessary losers to formalize this idea of a candidate losing in all completions of a partial tournament. This definition can be viewed as a parallel to the notion of necessary winners, i.e., candidates winning no matter what, and is equivalent to not being a possible winner or a candidate that can win in at least one completion (see Konczak and Lang [22]). Definition 1. Given n voters, a partial n-weighted tournament G, a tournament solution S and a candidate c∈c , c is a necessary loser for G (w.r.t S) if for every completion G′∈[G]G ∈[G] we have that c∉S(G′)c ∈ S(G ). We write c∈NLS(G)c _S(G). Example 2 Consider the partial tournament in Figure 1(c) and the Copeland rule. Since a already secured 33 wins, c and d cannot catch back as their Copeland score is respectively 11 and 00 and they can only improve it by 11 by being preferred to e. On the contrary, a can win, typically if e is never preferred. b can win if e is preferred to a and b is preferred to e. e can win as it could be a Condorcet winner for instance. Hence, c and d are the necessary Copeland-losers for G. We now define destructive minimal supports for tournaments. Definition 2. Given n voters, an n-weighted tournament G=(,μ)G=(C,μ), a tournament solution S and a losing candidate l∈∖S(G)l S(G), a destructive minimal support (dMS) for l∉S(G)l ∈ S(G) is a partial tournament G′⊆G G such that: (a) l∈NLS(G′)l _S(G ) (b) G′G is ⊆ -minimal, i.e., all partial tournaments G′⊊G′G G are such that l∉NLS(G′)l _S(G ). Example 3 aabbccddee (a) G aabbccddee (b) X aabbccddee (c) Y Figure 2: A tournament G (2(a)), and X and Y, two dMSs for d∉CO(G)d ∈ (G) (2(b)) and (2(c)). Consider the Copeland rule and the tournament G in Figure 2(a). Clearly, c∉CO(G)c ∈ (G). To produce a dMS for d∉CO(G)d ∈ (G) like X in Figure 2(b), one has to find a partial sub-tournament of G such that independently of the way it is completed, there always exists a candidate with a better Copeland score than d. In X, this is achieved by using a mix of pairwise comparisons lost by d and won by a stronger candidate a. Indeed, at best d can achieve a score of 22 while a will at least score 33. This sub-tournament is subset minimal as removing a defeat from d breaks the previous reasoning. The case of the dMS for d∉CO(G)d ∈ (G) in Figure 2(c) is similar. However, here it is sufficient to attribute 33 losses to d as it is impossible to complete the rest of the partial tournament without giving at least a score of 22 to another candidate. d loses a strict majority of its comparisons and there always exists a candidate in the tournament that wins a majority of them by the pigeonhole principle. As seen in the previous example, there can exist multiple dMSs for a given losing candidate. We focus on the simpler ones in line with Grice’s manner criterion [17] which suggests to pick the briefest explanation. To measure the dMSs size, we use total number of pairwise comparisons in the partial tournament like in Contet et al. [10] and the microbribery setting of Faliszewski et al. [15]. Definition 3. Given n voters, a partial n-weighted tournament G=(,μ)G=(C,μ), and a losing candidate l∈∖S(G)l S(G), we define the size of a dMS =(,μ)X=(C, _X) for l∉S(G)l ∈ S(G) as ||=∑(c,c′)∈2μ(c,c′)|X|= _(c,c ) ^2 _X(c,c ). X is a smallest destructive minimal support (SdMS) for l∉S(G)l ∈ S(G) if and only if for all dMSs Y for l∉S(G)l ∈ S(G), we have ||≤|||X|≤|Y|. 4 Characterizing Necessary Losers 4.1 Top Cycle The characterization of top cycle is relatively straightforward. Essentially, a candidate l can be a necessary loser if and only if there always exists a strongly connected component inaccessible from l in each completion. For it to be the case, a “one-way frontier” has to split the initial partial tournament in two. Theorem 4.1 Given a partial tournament G=(,μ)G=(C,μ), a candidate l∈l is a necessary TC -loser for G if and only if exists K⊆∖lK \l\ with K≠∅K≠ such that for each pair (c,c′)∈K×(∖K)(c,c )∈ K×(C K), μ(c,c′)=1μ(c,c )=1. 4.2 Borda Schwartz proved the characterization for Borda in the 1960s [27]. It was originally expressed with flow networks so we translate it in our framework. Theorem 4.2 Schwartz [27]. Given n voters and a partial n-weighted tournament G=(,μ)G=(C,μ) with ||=m|C|=m, a candidate l∈l is a necessary Borda loser for G if and only if exists K⊆∖lK \l\ such that minc∈KG′∈[G]σBO(c,G′)>maxG′∈[G]σBO(l,G′). _G ∈[G] E_c∈ K _ (c,G )> _G ∈[G] _ (l,G ). 4.3 Maximin and Weighted Uncovered Set In this section we provide characterizations of partial tournaments where a specific candidate l is a necessary loser for the maximin rule and the weighted uncovered set rule. We proceed by reducing the problem of determining if l is a necessary loser in a tournament G to the existence of a perfect matching in a specific bipartite graph that we call the l-deficient incidence graph of G. This approach generalizes an idea used by Aziz et al. to prove that the possible winner problem for maximin is in P (Theorem 11 in [1]). We then use Hall’s mariage theorem [20] which characterizes bipartite graphs admitting perfect matchings to characterize partial tournaments where l is a necessary loser. Let B=(X,Y,Z)B=(X,Y,Z) be a bipartite graph where X and Y are vertex sets and Z the edge set. For each subset W⊆XW X, the neighborhood of W in B, noted NB(W)N_B(W) is the subset of vertices in Y adjacent in B to vertices in W. An X-perfect matching (or simply a perfect matching) is a subset of edges M⊆ZM Z such that each vertex of X is adjacent to exactly one edge in M. We distinguish the directed edge from x to y, noted with parentheses (x,y)(x,y), from the (undirected) edge between x and y, noted with braces x,y\x,y\. Definition 4. Given a directed graph G=(V,E)G=(V,E) where V is the set of vertices, E the set of edges and a vertex v∈Vv∈ V, we call the v-deficient incidence graph of G the bipartite graph IGv=(X,Y,Z)I_G^v=(X,Y,Z) where X=V∖vX=V \v\, Y=x,y:x,y∈V2,(x,y)∈EY=\\x,y\:x,y∈ V^2,\,(x,y)∈ E\ and Z=x,x,y:x,y∈V2,(x,y)∈EZ=\\x,\x,y\\:x,y∈ V^2,\,(x,y)∈ E\, i.e., a vertex x≠vx≠ v is adjacent to an edge e in IGvI_G^v if and only if e is an edge leaving x in G. Example 4 aabbcceeddffggiihhjj (a) G aabbccddeeffgghhiia,b\a,b\a,c\a,c\b,c\b,c\d,e\d,e\e,f\e,f\e,g\e,g\h,i\h,i\i,j\i,j\ (b) IGjI_G^j Figure 3: A directed graph G (3(a)) and its j-deficient incidence graph IGjI_G^j (3(b)). Consider the graph G=(V,E)G=(V,E) in Figure 3(a). To build its j-deficient incidence graph IGj=(X,Y,Z)I_G^j=(X,Y,Z) in Figure 3(b) simply take the original set of vertices without j, X=V∖j=a,b,c,d,e,f,g,h,iX=V \j\=\a,b,c,d,e,f,g,h,i\, add each pair of vertices containing an edge in the original graph Y=x,y:x,y∈V2,(x,y)∈EY=\\x,y\:x,y∈ V^2,\,(x,y)∈ E\ and then link vertices with their out-going edges in G. We identify graphs whose deficient incidence graph has no perfect matching. Lemma 1 Given a directed graph G=(V,E)G=(V,E) where V is the set of vertices and E the set of edges, and a vertex v∈Vv∈ V, the v-deficient incidence graph of G, IGv=(X,Y,Z)I_G^v=(X,Y,Z), does not have an X-perfect matching if and only if there exists a tree T=(K,ET)T=(K,E_T) with K⊆V∖vK V \v\ such that for each pair (c,c′)∈K×V(c,c )∈ K× V with c≠c′c≠ c , if c,c′∉ET\c,c \ ∈ E_T then (c,c′)∉E(c,c ) ∈ E. Proof Given a directed graph G=(V,E)G=(V,E) where V is the set of vertices and E the set of edges, a vertex v∈Vv∈ V and the v-deficient incidence graph of G IGv=(X,Y,Z)I_G^v=(X,Y,Z). Given a subgraph S⊆GS G, let VSV_S be the set of vertices contained in S and ESE_S the set of edges. We define the undirected version of S, S~=(VS,ES~) S=(V_S, E_S) where ES~=c,c′:c,c′∈VS2,(c,c′)∈ES E_S=\\c,c \:c,c ∈ V_S^2,\,(c,c )∈ E_S\. To prove Lemma 1, we use a classical result from matching theory. Hall’s marriage theorem [20]. Let G=(X,Y,Z)G=(X,Y,Z) be a finite bipartite graph with bipartite sets X and Y and edge set Z. An X-perfect matching exists if and only if for each subset W⊆XW X, |W|≤|NG(W)||W|≤|N_G(W)|. (⟹ ) Suppose IGvI_G^v has no X-perfect matching. Then, according to Hall’s marriage theorem, there exists a subset W⊆XW X, |W|>|NIGv(W)||W|>|N_I_G^v(W)|. Given T=(W,NIGv(W))T=(W,N_I_G^v(W)), if no connected component of T is a tree then each connected component has more edges than vertices and |W|≤|NIGv(W)||W|≤|N_I_G^v(W)|. This is not the case so exists W′⊆W W such that T′=(W′,NIGv(W′))T =(W ,N_I_G^v(W )) is a tree. Since W′⊆W W, and v∉Wv ∈ W, v∉W′v ∈ W . By definition of IGvI_G^v, for each pair (c,c′)∈W′×V(c,c )∈ W × V with c≠c′c≠ c , if c,c′∉NIGv(W′)\c,c \ ∈ N_I_G^v(W ) then, since c∈W′c∈ W , (c,c′)∉E(c,c ) ∈ E. (⟸ ) Suppose there exists a tree T=(K,EK)T=(K,E_K) with K⊆V∖vK V \v\ such that for each pair (c,c′)∈K×V(c,c )∈ K× V with c≠c′c≠ c , if c,c′∉ET\c,c \ ∈ E_T then (c,c′)∉E(c,c ) ∈ E. As T is acyclic |K|=|EK~|+1|K|=| E_K|+1 and since v∉Kv ∈ K and T is connected, EK~=NIGv(K) E_K=N_I_G^v(K). Thus, |K|=NIGv(K)+1|K|=N_I_G^v(K)+1. Additionally, since v∉Sv ∈ S, K⊆XK X. Hence according to Hall’s marriage theorem, there is no X-perfect matching in IGvI_G^v. ∎ To illustrate this result we revisit the previous example to see why it does not admit an X-perfect matching. Example 5 Looking back at the previous graph G=(V,E)G=(V,E) in Figure 3(a) and its j-deficient incidence graph IGj=(X,Y,Z)I_G^j=(X,Y,Z) in Figure 3(b), by considering each connected component of G, it becomes clear that no X-perfect matching exists because of the strongly connected component d,e,f,g\d,e,f,g\ which has strictly less edges than vertices since it is a tree. Note that even if the connected component h,i,j\h,i,j\ is also a tree, j brings an additional possible edge to match without adding a vertex in the bipartite graph. Using the previous result we can show that a candidate is a necessary maximin loser if and only if there exists a specific tree in the partial tournament. Theorem 4.3 Given n voters and a partial n-weighted tournament G=(,μ)G=(C,μ), a candidate l∈l is a necessary M -loser for G if and only if there exists a tree T=(K,E)T=(K,E) with K⊆∖lK \l\ such that for each pair (c,c′)∈K×(c,c )∈ K×C with c≠c′c≠ c , if c,c′∉E\c,c \ ∈ E then μ(c,c′)>n−maxc′∈μ(c′,l)μ(c,c )>n- _c μ(c ,l). Proof Given n voters, a partial n-weighted tournament G=(,μ)G=(C,μ) with ||=m|C|=m, and a candidate l∈l . If l wins all its unspecified comparisons in G, l achieves a maximin score of t=n−maxc∈μ(c,l)t=n- _c μ(c,l). If t≥⌈n2⌉t≥ n2 , by winning all its unspecified comparisons in G, l can become a Condorcet winner and hence a maximin winner. Thus, l is not a necessary loser. And since for each c∈c , μ(c,l)≤⌈n2⌉μ(c,l)≤ n2 while t≥⌈n2⌉t≥ n2 , hence μ(c,l)≤n−maxc′∈μ(c′,l)μ(c,l)≤ n- _c μ(c ,l). Hence K⊆∖lK \l\ and there exists no candidate satisfying the condition in the theorem and thus no tree. In the rest of this proof we assume t<⌈n2⌉t< n2 . Let the graph H=(VH,EH)H=(V_H,E_H) be such that VH=V_H=C and EH=(c,c′):c,c′∈2,c≠l,c≠c′,μ(c,c′)≤tE_H=\(c,c ):c,c ^2,\,c≠ l,\,c≠ c ,\,μ(c,c )≤ t\, and IHl=(X,Y,Z)I_H^l=(X,Y,Z) be the l-deficient incidence graph of H. If c is matched with c,c′\c,c \ in IHlI_H^l, then G can be completed in G′G where μ′(c,c′)≤tμ (c,c )≤ t which ensures that the maximin score of c is less than t. Aziz et al. [1] showed that l is a not necessary loser if and only if there exists an X-perfect matching in IHlI_H^l, we prove it here for completeness. (⟹)( ) Suppose that l∉NLMM(G)l _ (G), then there exists a completion G′=(,μ′)G =(C,μ ) of G where l is a M -winner, i.e., where l has the maximal M score. Thus, in G′G , for all candidate c distinct from l, there exists c′≠c ≠ c such that μ′(c,c′)≤n−maxc′∈μ′(c′,l)≤n−maxc′∈μ(c′,l)=tμ (c,c )≤ n- _c μ (c ,l)≤ n- _c μ(c ,l)=t. Additionally, since t<⌈n2⌉t< n2 , 2t<n2t<n and c,c′∈Y\c,c \∈ Y cannot force both the maximin score of c and c′c to be below t. Hence, in IHlI_H^l, each vertex in Y can only be matched to at most one vertex of X. This results in an X-perfect matching. (⟸)( ) Suppose there exists an X-perfect matching in IHlI_H^l, then for each candidate c∈Xc∈ X, exists c′∈c such that c is matched with c,c′\c,c \. Now, let G′=(,μ′)G =(C,μ ) be a completion of G where l wins all its remaining comparisons, i.e., such that for all c∈c , μ′(l,c)=n−μ(c,l)μ (l,c)=n-μ(c,l), where μ′(c,c′)=n−maxc′∈μ(c′,l)μ (c,c )=n- _c μ(c ,l) if c,c,c′\c,\c,c \\ is part of the matching and where the rest of G is completed arbitrarily. Each candidate distinct from l has a maximin score of at most n−maxc′∈μ(c′,l)n- _c μ(c ,l) and l has a maximin score of minc′∈μ′(l,c′)=minc′∈(n−μ(c′,l))=n−maxc′∈μ(c′,l) _c μ (l,c )= _c (n-μ(c ,l))=n- _c μ(c ,l). Hence, l∈M(G′)l∈ (G ) and l∉NLMM(G)l _ (G). Applying Lemma 1, we have that l is not a necessary M -loser of G if and only if there exists a tree T=(K,ET)T=(K,E_T) with K⊆V∖vK V \v\ such that for each pair (c,c′)∈K×V(c,c )∈ K× V with c≠c′c≠ c , if c,c′∉ET\c,c \ ∈ E_T then (c,c′)∉EH(c,c ) ∈ E_H. Finally, by construction, such tree exists if and only if there exists a tree T=(K,E)T=(K,E) in G with K⊆∖lK \l\ such that for each pair (c,c′)∈K×(c,c )∈ K×C with c≠c′c≠ c , if c,c′∉E\c,c \ ∈ E then μ(c,c′)>n−maxc′∈(c′,l)μ(c,c )>n- _c (c ,l). ∎ Example 6 aabbccdd332222443311112233 (a) G aabbccdd (b) H a,b\a,b\a,c\a,c\a,d\a,d\b,c\b,c\b,d\b,d\c,d\c,d\aaddcc (c) IHbI_H^b aabbccdd332222334411441133223322 (d) G′G Figure 4: A partial 55-weighted tournament G (4(a)), its resulting H graph (see proof of Theorem 4.3 and Example 6) (4(b)), the b-deficient incidence graph of H IHbI_H^b (4(c)), and G′G , a completion of G where b is a M -winner (4(d)). Consider, in Figure 4, the partial 55-weighted tournament G. H is obtained from G by only keeping the edges with a weight smaller than t=n−maxx∈μ(x,b)=5−3=2t=n- _x μ(x,b)=5-3=2. Edges in H are edges which can potentially be used to limit the maximin score of the competitors of b. We then try to build a perfect matching in the b-deficient incidence graph of H. We show one with the thick edges. Finally, from this matching we produce G′G , a completion of G where b is a M -winner, hence not a necessary loser in G. We proceed with the same idea for the weighted uncovered set. Theorem 4.4 Given n voters and a partial n-weighted tournament G=(,μ)G=(C,μ), a candidate l∈l is a necessary wUC -loser for G if and only if there exists a tree T=(K,E)T=(K,E) with K⊆∖lK \l\ such that for each c∈Kc∈ K, μ(c,l)≥n2μ(c,l)≥ n2 and for each c′∈∖l,cc \l,c\, if c,c′∉E\c,c \ ∈ E then μ(c,c′)+μ(c′,l)≥nμ(c,c )+μ(c ,l)≥ n. Additionally, at least one of all the previous inequalities has to be strict. Besides the strict inequality constraint, the proof is similar to the proof of Theorem 4.3 with H=(VH,EH)H=(V_H,E_H) such that VH=V_H=C and EH=(c,c′):c,c′∈2,c≠l,c≠c′,μ(c,c′)<n−μ(c′,l)∪(c,l):c∈,c≠l,μ(c,l)<⌈n2⌉E_H=\(c,c ):c,c ^2,\,c≠ l,\,c≠ c ,\,μ(c,c )<n-μ(c ,l)\∪\(c,l):c ,\,c≠ l,\,μ(c,l)< n2 \. 5 Smallest Destructive Minimal Supports In this section we continue our work with the analysis of the smallest destructive minimal supports. Proofs in this section all follow the same structure. First, we show how to build small destructive minimal supports in each sub-case and then we prove they match the lower bounds, hence that they are the smallest dMSs. Top Cycle. To guarantee a necessary loser, we separate the top cycle and the loser. Such separation can only occurs between strongly connected components of a tournament. Since the order between the strongly connected components of a tournament is transitive and complete, it is linear. Additionally, to split m candidates in two groups of sizes k and m−km-k, m(m−k)m(m-k) comparisons are required. By concavity, the smallest frontier is either right after the top cycle (which is the top component) or right before the loser’s component. Theorem 5.1 Given a complete tournament G=(,μ)G=(C,μ) with ||=m|C|=m, and a losing candidate l∈∖TC(G)l (G), for each SdMS X for l∉TC(G)l ∈ (G), we have ||=mint∈α,βt(m−t)|X|= _t∈\α,β\t(m-t) where α=|TC(G)|α=| (G)| and β=|c:c∈,l can reach c in G|β=|\c:c ,l can reach c in G\|. An SdMS X can be computed in polynomial time, and ||≤⌈m2⌉⌊m2⌋|X|≤ m2 m2 . Borda. Because there always exists a candidate at the average or above, when possible, it is enough to show that the loser performs strictly below average (case i.). Else we have to present a coalition with a stronger average Borda score (case i.). The coalition of size 11, which always exists, gives the upper bound. We suspect that the decision problem of finding an SdMS for Borda is NP-complete. Theorem 5.2 Given n voters, a complete n-weighted tournament G=(,μ)G=(C,μ) with ||=m|C|=m, a losing candidate l∈∖BO(G)l (G) with Borda score σBO(l) _ (l), for each SdMS X for l∉BO(G)l ∈ (G): i. if σBO(l)≤⌊n(m−1)−12⌋ _ (l)≤ n(m-1)-12 then ||=⌈n(m−1)+12⌉|X|= n(m-1)+12 i. else ⌈n(m−1)+12⌉<||≤n(m−1)+1−maxc∈Aμ(c,l) n(m-1)+12 <|X|≤ n(m-1)+1- _c∈ Aμ(c,l) where A=c:c∈,σBO(c)>σBO(l)A=\c:c , _ (c)> _ (l)\. For each SdMS X, ||≤n(m−1)+1|X|≤ n(m-1)+1. Copeland. This result is derived from the Theorem 5.2 as Copeland agrees with Borda when n=1n=1. Except for case i., a coalition of size 11 is always optimal. Theorem 5.3 Given a complete tournament G=(,μ)G=(C,μ) with ||=m|C|=m, and a losing candidate l∈∖CO(G)l (G) with Copeland score σCO(l) _ (l), for each SdMS X for l∉CO(G)l ∈ (G): i. if σCO(l)<⌊m−12⌋ _ (l)< m-12 then ||=⌈m2⌉|X|= m2 i. else if exists c∈c such that μ(c,l)=1μ(c,l)=1 and σCO(c)>σCO(l) _ (c)> _ (l) then ||=m−1|X|=m-1 i. else ||=m|X|=m. An SdMS X can be computed in polynomial time, and ||≤m|X|≤ m. Maximin. Here, the idea is to bound the maximin score of the losing candidate by keeping comparisons where he loses against one candidate while ensuring there exists a candidate with a higher maximin score by keeping enough comparisons where he wins against each other candidate. Case i. of Theorem 5.4 is when the two sets of comparisons overlap and case i. is when they do not. An SdMS fo maximin relies on a tree (in the sense of Theorem 4.3) reduced to one candidate. Theorem 5.4 Given n voters, a complete n-weighted tournament G=(,μ)G=(C,μ) with ||=m|C|=m, and a losing candidate l∈∖M(G)l (G) with maximin score σM(l) _ (l), for each SdMS X for l∉M(G)l ∈ (G): i. if m=2m=2 then ||=⌈n+12⌉|X|= n+12 i. else if exists c∈c such that σM(c)>σM(l) _ (c)> _ (l) and μ(c,l)≥n−σM(l)μ(c,l)≥ n- _ (l), then ||=(σM(l)+1)(m−3)+n+1|X|=( _ (l)+1)(m-3)+n+1 i. else ||=(σM(l)+1)(m−2)+n+1|X|=( _ (l)+1)(m-2)+n+1 An SdMS X can be computed in polynomial time, and ||≤⌈n+12⌉(m−2)+n+1|X|≤ n+12 (m-2)+n+1. Weighted Uncovered Set. For a candidate to be a necessary loser with the weighted uncovered set, there need to exist a candidate covering him in each possible completion. We can have one specific candidate to cover the losing candidate in all completions. Concretely, with l the losing candidate and c0c_0 the “necessary” covering candidate, we ensure that for each candidate c, μ(c0,c)≥n−μ(c,l)μ(c_0,c)≥ n-μ(c,l) by fixing high enough μ(c0,c)μ(c_0,c) and μ(c,l)μ(c,l) (case i. in Theorem 5.5, dMS X in Example 7). The tree of Theorem 4.4 then contains one candidate. However, sometimes a tree with two candidates yields a smaller dMS (case i., dMS Y). aabbcc332233223322 (a) G aabbcc333322 (b) X aabbcc3333 (c) Y Figure 5: A 55-weighted tournament G (5(a)), and X and Y, two dMSs for c∉wUC(G)c ∈ (G) (5(b)) and (5(c)). Theorem 5.5 Given n voters, a complete n-weighted tournament G=(,μ)G=(C,μ) with ||=m|C|=m, a losing candidate l∈∖wUC(G)l (G), for each SdMS X for l∉wUC(G)l ∈ (G): i. if p=max∑c∈∖l,c0,c1c0,c1μ(c,l)−n(m−3)+⌊n2⌋>0p= _c_0,c_1 _c \l,c_0,c_1\μ(c,l)-n(m-3)+ n2 >0 with c0,c1∈(∖l)2c_0,c_1∈(C \l\)^2 such that c0≠c1c_0≠ c_1, for i∈0,1i∈\0,1\, μ(ci,l)≥n2μ(c_i,l)≥ n2, for all c∈∖l,c0,c1c \l,c_0,c_1\, μ(ci,c)+μ(c,l)≥nμ(c_i,c)+μ(c,l)≥ n, and at least one of the inequalities is strict, then ||=n(m−2)+⌈n+12⌉−p|X|=n(m-2)+ n+12 -p i. else ||=n(m−2)+⌈n+12⌉|X|=n(m-2)+ n+12 An SdMS X can be computed in polynomial time, and ||≤n(m−2)+⌈n+12⌉|X|≤ n(m-2)+ n+12 . We illustrate the non-trivial case i. with the following example. Example 7 Consider the 55-weighted tournament G in Figure 5(a). In the case of X in Figure 5(b), a weighted covers c across all completions. However, we can allow the covering candidate to vary dependently of the completion as in the dMS Y in Figure 5(c). If a majority of voters prefers a to b then a covers c else b covers c. Here, p=∑c∈∖l,c0,c1μ(c,l)−n(m−3)+⌊n2⌋=0+0+2p= _c \l,c_0,c_1\μ(c,l)-n(m-3)+ n2 =0+0+2. Hence Y contains 22 less comparisons than X (||=8|X|=8, ||=6|Y|=6). The analogous result for the uncovered set is simpler since the first case cannot occur as ∑c∈∖l,c0,c1μ(c,l)≤m−3 _c \l,c_0,c_1\μ(c,l)≤ m-3 and p≤0p≤ 0. Corollary 1 Given a complete tournament G=(,μ)G=(C,μ) with ||=m|C|=m, and a losing candidate l∈∖UC(G)l (G), for each SdMS X for l∉UC(G)l ∈ (G), we have ||=m−1|X|=m-1. 6 Conclusion First, in contrast with the results of Contet et al. on constructive SMSs [10], for the weighted uncovered set, smallest destructive MSs can be computed in polynomial time while the decision problem associated to finding the smallest constructive MS is NP-complete. Additionally, we do not know if computing an SdMS for Borda is in P. Furthermore, with m the number of candidate and n the number of voters, the size of the SdMSs is in (m2)O(m^2) for the top cycle rule and in (nm)O(nm) for the remaining rules. Hence, even in the less favorable instances, only a fraction of the tournament is required. For Borda in the constructive case, almost the whole tournament was necessary when all candidates are tied. In this paper, to find simple explanations, we put the emphasis on minimizing the size of the dMSs, i.e., the total number of pairwise comparisons. If the simplicity of the structure of dMSs is often correlated with a short number of pairwise comparisons, when looking specifically for the smallest dMSs, it can occur that we end up with a more complex structure. This suggests that depending on the specific application one might optimize for different metrics on dMSs. Further work is needed to investigate which explanations are preferred by users, especially empirical studies. Acknowledgments The authors thank the reviewers of ADT26 for their constructive comments and suggestions, which helped improve this paper. This work is funded by the European Union. Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. This work is supported by ERC grant 101166894 “Advancing Digital Democratic Innovation” (ADDI). References [1] H. Aziz, M. Brill, F. Fischer, P. Harrenstein, J. Lang, and H. G. Seedig (2015) Possible and necessary winners of partial tournaments. Journal of Artificial Intelligence Research 54, p. 493–534. Cited by: §1, §2, §4.3, Proof. [2] A. Boixel, U. Endriss, and R. de Haan (2022) A calculus for computing structured justifications for election outcomes. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), Cited by: §1. [3] F. Brandt, M. Brill, and P. Harrenstein (2016) Tournament solutions.. In Handbook of Computational Social Choice, F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia (Eds.), p. 57–84. Cited by: §1. [4] M. Brill, U. Schmidt-Kraepelin, and W. Suksompong (2020) Refining tournament solutions via margin of victory. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), Cited by: §1. [5] J. Brockner and B. M. Wiesenfeld (1996) An integrative framework for explaining reactions to decisions: interactive effects of outcomes and procedures.. Psychological bulletin 120 (2), p. 189. Cited by: §1. [6] O. Cailloux and U. Endriss (2016) Arguing about voting rules. In Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), Cited by: §1. [7] C. Carman (2010) The process is the reality: perceptions of procedural fairness and participatory democracy. Political Studies 58 (4), p. 731–751. Cited by: §1. [8] J. A. Colquitt and J. M. Chertkoff (2002) Explaining injustice: the interactive effect of explanation and outcome on fairness perceptions and task motivation. Journal of Management 28 (5), p. 591–610. Cited by: §1. [9] C. Contet, U. Grandi, and J. Mengin (2024) Abductive and contrastive explanations for scoring rules in voting. In Proceedings of the 27th European Conference on Artificial Intelligence (ECAI), Cited by: §1. [10] C. Contet, U. Grandi, and J. Mengin (2026) Explaining tournament solutions with minimal supports. In Proceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI), Cited by: §1, §3, §6. [11] J. De Fine Licht, D. Naurin, P. Esaiasson, and M. Gilljam (2014) When does transparency generate legitimacy? experimenting on a context-bound relationship. Governance 27 (1), p. 111–134. Cited by: §1. [12] K. de Fine Licht and J. de Fine Licht (2020) Artificial intelligence, transparency, and public decision-making: why explanations are key when trying to produce perceived legitimacy. AI & society 35 (4), p. 917–926. Cited by: §1. [13] M. Döring and J. Peters (2023) Margin of victory for weighted tournament solutions. In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), Cited by: §1. [14] E. Elkind, P. Faliszewski, and A. Slinko (2009) Swap bribery. In Proceedings of the 2nd International Symposium on Algorithmic Game Theory (SAGT), Cited by: §1. [15] P. Faliszewski, E. Hemaspaandra, L. A. Hemaspaandra, and J. Rothe (2009) Llull and copeland voting computationally resist bribery and constructive control. Journal of Artificial Intelligence Research 35, p. 275–341. Cited by: §1, §3. [16] F. Fischer, O. Hudry, and R. Niedermeier (2016) Weighted tournament solutions.. In Handbook of Computational Social Choice, F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia (Eds.), p. 85–102. Cited by: §1. [17] H. P. Grice (1975) Logic and conversation. In Speech acts, p. 41–58. Cited by: §3. [18] S. Grimmelikhuijsen (2023) Explaining why the computer says no: algorithmic transparency affects the perceived trustworthiness of automated decision-making. Public Administration Review 83 (2), p. 241–262. Cited by: §1. [19] D. Grossi, U. Hahn, M. Mäs, A. Nitsche, J. Behrens, N. Boehmer, M. Brill, U. Endriss, U. Grandi, A. Haret, J. Heitzig, N. Janssens, C. M. Jonker, M. A. Keijzer, A. Kistner, M. Lackner, A. Lieben, A. Mikhaylovskaya, P. K. Murukannaiah, C. Proietti, M. Revel, É. Rouméas, E. Shapiro, G. Sreedurga, B. Swierczek, N. Talmon, P. Turrini, Z. Terzopoulou, and F. V. D. Putte (2024) Enabling the digital democratic revival: a research program for digital democracy. External Links: 2401.16863, Link Cited by: §1. [20] P. Hall (1935) On representatives of subsets. Journal of the London Mathematical Society 1 (1), p. 26–30. Cited by: §4.3, Proof. [21] J. R. Hibbing (2001) Process preferences and american politics: what the people want government to be. American Political Science Review 95 (1), p. 145–153. Cited by: §1. [22] K. Konczak and J. Lang (2005) Voting procedures with incomplete preferences. In Proceedings of the Multidisciplinary IJCAI Workshop on Advances in Preference Handling (M-PREF), Cited by: §1, §3. [23] J. Lang (2020) Collective decision making under incomplete knowledge: possible and necessary solutions. In Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI), Cited by: §1. [24] T. Miller (2023) Explainable ai is dead, long live explainable ai! hypothesis-driven decision support using evaluative ai. In Proceedings of the 2023 ACM conference on fairness, accountability, and transparency, p. 333–342. Cited by: §1. [25] O. Nardi, A. Boixel, and U. Endriss (2022) A graph-based algorithm for the automated justification of collective decisions. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS), Cited by: §1. [26] D. Peters, A. D. Procaccia, A. Psomas, and Z. Zhou (2020) Explainable voting. Proceedings of the 33rd Advances in Neural Information Processing Systems (NeurIPS). Cited by: §1. [27] B. L. Schwartz (1966) Possible winners in partially completed tournaments. SIAM Review 8 (3), p. 302–308. Cited by: Table 1, §1, §4.2, Theorem 4.2, Proof. [28] S. A. Suryanarayana, D. Sarne, and S. Kraus (2022) Justifying social-choice mechanism outcome for improving participant satisfaction. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS), Cited by: §1, §1. [29] T. R. Tyler (2000) Social justice: outcome and procedure. International Journal of Psychology 35 (2), p. 117–125. Cited by: §1. [30] T. R. Tyler (1994) Governing amid diversity: the effect of fair decisionmaking procedures on the legitimacy of government. Law & Society Review 28 (4), p. 809–831. Cited by: §1. [31] L. Xia and V. Conitzer (2011) Determining possible and necessary winners given partial orders. Journal of Artificial Intelligence Research (JAIR) 41, p. 25–67. Cited by: §1. Appendix Appendix 0.A Proofs for Section 4 0.A.1 Proofs for Section 4.1 See 4.1 Proof Given a partial tournament G=(,μ)G=(C,μ), a candidate l∈l . (⟹ ) We proceed by contrapose. Suppose for all K⊆∖lK \l\ with K≠∅K≠ , exists a pair (c,c′)∈K×∖K(c,c )∈ K×C K, μ(c,c′)=0μ(c,c )=0. If l∈NLTC(G)l _ (G), for each completion X of G, let A=c:c∈,l cannot reach c in A_X=\c:c ,l cannot reach c in X\ be the set of candidates l cannot reach in X, A≠∅A_X≠ . Let 0=(,μ0)X_0=(C, _0) be such that 0=argmin∈[G]|A|X_0= _X∈[G]|A_X|. Since A0⊆∖lA_X_0 \l\ and A0≠∅A_X_0≠ , exists a pair (c,c′)∈A0×∖A0(c,c )∈ A_X_0×C A_X_0, μ(c,c′)=0μ(c,c )=0. Let 1=(,μ1)X_1=(C, _1) be a completion of G such that μ1(c,c′)=0 _1(c,c )=0, μ1(c′,c)=1 _1(c ,c)=1 and μ1=μ0 _1= _0 everywhere else. Clearly, for all c∈∖A0c A_X_0, c∈∖A1c A_X_1 In particular, since c′∈∖A0c A_X_0, c′∈∖A1c A_X_1, i.e. l can reach c′c in 1X_1. Additionally, μ1(c′,c)=1 _1(c ,c)=1. Hence, l can reach c, i.e., c∈∖A1c A_X_1. Hence (∖A0)⊊(∖A1)(C A_X_0) (C A_X_1) or equivalently, A1⊊A0A_X_1 A_X_0. Contradiction. Thus l∉NLTC(G)l _ (G). (⟸ ) Suppose exists K⊆∖lK \l\ with K≠∅K≠ such that for each pair (c,c′)∈K×∖K(c,c )∈ K×C K, μ(c,c′)=1μ(c,c )=1 then clearly for each completion X of G, l cannot reach candidates in K thus l∉TC()l ∈ (X) and l∈NLTC(G)l _ (G). ∎ 0.A.2 Proofs for Section 4.2 See 4.2 Proof Schwartz studied this problem from the angle of network flow theory. The result was initially stated as follows in [27]. Given a partial tournament, for any candidate l∈l and subset K⊆∖lK \l\, let N(l,K)N(l,K) be the algebraic sum of half game behind by which l trails each candidate of K, P(l)P(l) be the number of games l has still to play and P(K)P(K) be the number of games the candidates of K still have to play, omitting any in which they face one another. We have that for l to be eliminated it is necessary and sufficient that exists a subset K such that N(l,K)−kP(l)−P(K)>0.N(l,K)-kP(l)-P(K)>0. We now show how to reach the new formulation from the original one. Given n voters and a partial n-weighted tournament G=(,μ)G=(C,μ) with ||=m|C|=m, the half game behind score of a candidate c is defined as H(c)=n(m−1)+∑c′∈μ(c,c′)−∑c′∈μ(c′,c)H(c)=n(m-1)+ _c μ(c,c )- _c μ(c ,c). Each of the n(m−1)n(m-1) games that c will have to play grants by default one half game, if c wins the game then it grants a total of two half games (one half game plus one half game) and if c loses that game grants no half game at all (one half game minus one half game). Then we simply have N(l,K)=∑c∈K(H(c)−H(l))N(l,K)= _c∈ K(H(c)-H(l)). The number of game c still has to play is naturally the total number of games c has to play minus those c already played, i.e., won or lost, hence P(c)=n(m−1)−∑c′∈(μ(c,c′)+μ(c′,c))P(c)=n(m-1)- _c (μ(c,c )+μ(c ,c)). It is the same idea for P(K)P(K) but we only consider games against candidates not in K, P(K)=∑c∈K∑c′∉K(n−μ(c,c′)−μ(c′,c))P(K)= _c∈ K _c ∈ K(n-μ(c,c )-μ(c ,c)). N(l,K)−kP(l)−P(K)>0 N(l,K)-kP(l)-P(K)>0 ⇔ ∑c∈K(H(c)−H(l))−k(n(m−1)−∑c∈(μ(l,c)+μ(c,l))) _c∈ K(H(c)-H(l))-k (n(m-1)- _c (μ(l,c)+μ(c,l)) ) −∑c∈K∑c′∉K(n−μ(c,c′)−μ(c′,c))>0 - _c∈ K _c ∈ K(n-μ(c,c )-μ(c ,c))>0 ⇔ ∑c∈K(∑c′∈(μ(c,c′)−μ(c′,c))−∑c′∈(μ(l,c′)−μ(c′,l))) _c∈ K ( _c (μ(c,c )-μ(c ,c))- _c (μ(l,c )-μ(c ,l)) ) −k(n(m−1)−∑c∈(μ(l,c)+μ(c,l)))−∑c∈K∑c′∉K(n−μ(c,c′)−μ(c′,c))>0 -k (n(m-1)- _c (μ(l,c)+μ(c,l)) )- _c∈ K _c ∈ K(n-μ(c,c )-μ(c ,c))>0 ⇔ ∑c∈K∑c′∈(μ(c,c′)−μ(c′,c))−k∑c′∈(μ(l,c′)−μ(c′,l))−kn(m−1) _c∈ K _c (μ(c,c )-μ(c ,c))-k _c (μ(l,c )-μ(c ,l))-kn(m-1) −k∑c∈(μ(l,c)+μ(c,l))−∑c∈K∑c′∉K(n−μ(c,c′)−μ(c′,c))>0 -k _c (μ(l,c)+μ(c,l))- _c∈ K _c ∈ K(n-μ(c,c )-μ(c ,c))>0 ⇔ ∑c∈K∑c′∈(μ(c,c′)−μ(c′,c))+2k∑c∈μ(c,l)−kn(m−1) _c∈ K _c (μ(c,c )-μ(c ,c))+2k _c μ(c,l)-kn(m-1) −k(m−k)n+∑c∈K∑c′∉K(μ(c,c′)+μ(c′,c))>0 -k(m-k)n+ _c∈ K _c ∈ K(μ(c,c )+μ(c ,c))>0 In the first double sum, observe that if c′∈Kc ∈ K, then both c and c′c belong to K and both μ(c,c′)−μ(c′,c)μ(c,c )-μ(c ,c) and μ(c′,c)−μ(c,c′)μ(c ,c)-μ(c,c ) appear in the sum. Additionally, remember that μ(c,c)=0μ(c,c)=0 so the case where c=c′c=c can be ignored. Hence, when c′c is in K, the pairs cancel in the sum and we have: ∑c∈K∑c′∈(μ(c,c′)−μ(c′,c))+2k∑c∈μ(c,l)−nk(2m−1−k) _c∈ K _c (μ(c,c )-μ(c ,c))+2k _c μ(c,l)-nk(2m-1-k) +∑c∈K∑c′∉K(μ(c,c′)+μ(c′,c))>0 + _c∈ K _c ∈ K(μ(c,c )+μ(c ,c))>0 ⇔ ∑c∈K∑c′∉K(μ(c,c′)−μ(c′,c))+2k∑c∈μ(c,l)−nk(2m−1−k) _c∈ K _c ∈ K(μ(c,c )-μ(c ,c))+2k _c μ(c,l)-nk(2m-1-k) +∑c∈K∑c′∉K(μ(c,c′)+μ(c′,c))>0 + _c∈ K _c ∈ K(μ(c,c )+μ(c ,c))>0 ⇔ 2∑c∈K∑c′∉Kμ(c,c′)+2k∑c∈μ(c,l)−nk(2m−1−k)>0 2 _c∈ K _c ∈ Kμ(c,c )+2k _c μ(c,l)-nk(2m-1-k)>0 ⇔ ∑c∈K∑c′∉Kμ(c,c′)+k∑c∈μ(c,l)>12nk(2m−1−k) _c∈ K _c ∈ Kμ(c,c )+k _c μ(c,l)> 12nk(2m-1-k) ⇔ ∑c∈K∑c′∉Kμ(c,c′)+k∑c∈μ(c,l)>kn(m−1)−nk(k−1)2 _c∈ K _c ∈ Kμ(c,c )+k _c μ(c,l)>kn(m-1)-n k(k-1)2 Additionally, observe that since the maximum total number of pairwise comparisons a candidate can win in any completion G′∈[G]G ∈[G] is the total number of times it is compared less the number of pairwise comparisons it loses in G we have: maxG′∈[G]σBO(l,G′)=n(m−1)−∑c∈μ(c,l). _G ∈[G] _ (l,G )=n(m-1)- _c μ(c,l). Similarly, the minimum total number of pairwise comparisons a candidate can win in any completion G′∈[G]G ∈[G] is the number of comparisons it wins in G. Moreover, independently of the outcome, a comparison between to candidate in a coalition always represent both a win and a loss. Only wins from members of the coalition over non-members increase the average Borda score. Hence we have: minc∈KG′∈[G]σBO(c,G′)=nk−12+1k∑c∈K∑c′∉Kμ(c,c′). _G ∈[G] E_c∈ K _ (c,G )=n k-12+ 1k _c∈ K _c ∈ Kμ(c,c ). Finally we have: N(l,K)−kP(l)−P(K)>0⇔minc∈KG′∈[G]σBO(c,G′)>maxG′∈[G]σBO(l,G′).N(l,K)-kP(l)-P(K)>0 _G ∈[G] E_c∈ K _ (c,G )> _G ∈[G] _ (l,G ). ∎ 0.A.3 Proofs for Section 4.3 The proof of Theorem 4.4 follows a similar approach to the one of Theorem 4.3. We show that a candidate is not weighted covered by any other one if and only if there exists a perfect matching in a specific bipartite graph. Note that this is not sufficient as a weighted covered candidate can still be in the uncovered set as long as it is not strictly weighted covered. Typically, when two candidates weighted cover each other. See 4.4 Proof We proceed in a similar fashion to the proof of Theorem 4.3, we reduce the problem of determining if a candidate is weighted covered by a candidate in any completion to the problem of finding a perfect matching of a specific undirected unweighted bipartite graph. Given n voters, a partial n-weighted tournament G=(,μ)G=(C,μ) with ||=m|C|=m, and a candidate l∈l . Given a completion G′=(,μ′)G =(C,μ ) of G, l is a wUC -winner if and only if it is not strictly weighted covered that is that there is no c0∈c_0 such that μ′(c0,l)≥μ′(l,c0)μ (c_0,l)≥μ (l,c_0) and for all c∈∖l,c0c \l,c_0\ μ′(c0,c)≥μ′(l,c)μ (c_0,c)≥μ (l,c) and at least one of this inequalities is strict. We start by identifying the relaxed case where l is (simply) weighted covered in each completion G′=(,μ′)G =(C,μ ) of G, i.e., where for each candidate c∈∖lc \l\ we either have μ′(c,l)<μ′(l,c)μ (c,l)<μ (l,c) or a distinct candidate c′∈∖l,cc \l,c\ such that μ′(c,c′)<μ′(l,c′)μ (c,c )<μ (l,c ). Let the graph H=(VH,EH)H=(V_H,E_H) be such that VH=V_H=C and EH=(c,c′):∀(c,c′)∈(∖l)2,c≠c′∧μ(c,c′)<n−μ(c′,l)∪(c,l):∀c∈∖l,μ(c,l)<⌈n2⌉E_H=\(c,c ):∀(c,c )∈ (C \l\ )^2,\,c≠ c μ(c,c )<n-μ(c ,l)\∪\(c,l):∀ c \l\,\,μ(c,l)< n2 \ and IHl=(X,Y,Z)I_H^l=(X,Y,Z) be the l-deficient incidence graph of H. If c is matched with c,c′\c,c \ in IHlI_H^l then if c′=lc =l then G is completed in G′G such that μ′(l,c)≥⌈n+12⌉μ (l,c)≥ n+12 which ensures that l is strictly preferred to c else when c′≠lc ≠ l, G is completed such that μ′(l,c′)>n−μ′(c′,c)μ (l,c )>n-μ (c ,c) which ensures that l is strictly more preferred to c′c than c is preferred to c′c . In both cases, l is not weighted covered by c. We now show that l is not weighted covered by a candidate in any completion of G if and only if there exists an X-perfect matching of , i.e., a matching of cardinality |X||X| of X in IHlI_H^l. (⟹)( ) Suppose that l is a not weighted covered by a candidate in each completion of G, then there exists a completion G′=(,μ′)G =(C,μ ) of G where l is not weighted covered by any other candidate. Thus, in G′G , for all candidate c distinct from l, either μ′(l,c)≥⌈n2⌉μ (l,c)≥ n2 thus μ′(c,l)=n−μ′(l,c)≤n−μ(l,c)≤n−⌈n2⌉<⌈n2⌉μ (c,l)=n-μ (l,c)≤ n-μ(l,c)≤ n- n2 < n2 and c is matched with c,l\c,l\ in H or there exists c′∈∖l,cc \l,c\ such that μ′(l,c′)>μ′(c,c′)μ (l,c )>μ (c,c ) which gives us n−μ(l,c′)≥n−μ′(l,c′)>μ′(c,c′)≥μ(c,c′)n-μ(l,c )≥ n-μ (l,c )>μ (c,c )≥μ(c,c ) and c is matched with c,c′\c,c \ in H. Suppose c,c′\c,c \ has been matched both to c and c′c , then we have that μ′(l,c′)>μ′(c,c′)μ (l,c )>μ (c,c ) and μ′(l,c)>μ′(c′,c)μ (l,c)>μ (c ,c). Hence, μ′(l,c′)+μ′(l,c)>μ′(c,c′)+μ′(c′,c)=nμ (l,c )+μ (l,c)>μ (c,c )+μ (c ,c)=n and μ′(l,c)≥⌈n2⌉μ (l,c)≥ n2 or μ′(l,c′)≥⌈n2⌉μ (l,c )≥ n2 . Without loss of generality, suppose μ′(l,c)≥⌈n2⌉μ (l,c)≥ n2 . Then μ(c,l)≤μ′(c,l)=n−μ′(l,c)≤n−⌈n2⌉<⌈n2⌉μ(c,l)≤μ (c,l)=n-μ (l,c)≤ n- n2 < n2 . Thus c,c,l∈EH\c,\c,l\\∈ E_H which means that we can unmatch c with c,c′\c,c \ and match it with its corresponding edge shared with l. This result in a X-perfect matching in IHlI_H^l. (⟸)( ) Suppose there exists a X-perfect matching in IHlI_H^l, then for each candidate c∈Xc∈ X, exists c′∈c such that c is matched with c,c′\c,c \. Now, let G′=(,μ′)G =(C,μ ) be a completion of G where l wins all its remaining comparisons, i.e., such that for all c∈c , μ′(l,c)=n−μ(c,l)≥μ(l,c)μ (l,c)=n-μ(c,l)≥μ(l,c), and where μ′(c,c′)=μ(c,c′)μ (c,c )=μ(c,c ) if c,c,c′\c,\c,c \\ is part of the matching and where the rest of G is completed arbitrarily. For each candidate c distinct from l, if c,c,l\c,\c,l\\ is part of the matching then c,c,l∈EH\c,\c,l\\∈ E_H and μ(c,l)<⌈n2⌉μ(c,l)< n2 else else exists c′≠lc ≠ l such that c,c,c′\c,\c,c \\ is part of the matching then c,c,c′∈EH\c,\c,c \\∈ E_H and μ′(c,c′)=μ(c,c′)<μ(l,c′)≤μ′(l,c)μ (c,c )=μ(c,c )<μ(l,c )≤μ (l,c), i.e., in both case l is not weighted covered by c. Hence l is not weighted covered by any other candidate in G′G which is a completion of G. Applying Lemma 1, we have that l is a not weighted covered by a candidate in each completion G if and only if H has an acyclic connected component which does not contain l. Finally, by construction, H has an acyclic connected component which does not contain l if and only if exists a tree T=(K,E)T=(K,E) with K⊆∖lK \l\ such that for each c∈Kc∈ K, μ(c,l)≥⌈n2⌉μ(c,l)≥ n2 and for each pair (c,c′)∈K×∖l(c,c )∈ K×C \l\ with c≠c′c≠ c , if c,c′∉E\c,c \ ∈ E then μ(c,c′)+μ(c′,l)≥nμ(c,c )+μ(c ,l)≥ n. Recall that l∈NLwUC(G)l _ (G) when l is strictly weighted covered in each completion of G. Since we know when l is (simply) weighted covered in each completion of G, we now need to identify the sub-cases in which it is always strictly weighted covered. We show that it is necessary and sufficient to simply add the constraint that at least one of inequalities in the tree of the previous characterization has to be strict. Suppose that no inequality is strict. Then for each c∈Kc∈ K, μ(l,c)=n2μ(l,c)= n2. Let G′=(,μ′)G =(C,μ ) be a completion of G where l wins all its remaining comparisons, i.e., such that for all c∈c , μ′(l,c)=n−μ(c,l)≥μ(l,c)μ (l,c)=n-μ(c,l)≥μ(l,c), and where If we require at least one equality to be strict for each member of the tree, it is clear that in each completion, a member of the tree that weighted covers l also strictly weighted covers l. Given a tree T=(K,E)T=(K,E) with K⊆∖lK \l\ such that for each c∈Kc∈ K, μ(c,l)≥n2μ(c,l)≥ n2 and for each c′∈∖l,cc \l,c\, if c,c′∉E\c,c \ ∈ E then μ(c,c′)+μ(c′,l)≥nμ(c,c )+μ(c ,l)≥ n, suppose exists c0∈Kc_0∈ K such that μ(c,l)=n2μ(c,l)= n2 and for each c′∈∖l,cc \l,c\, if c,c′∉E\c,c \ ∈ E then μ(c,c′)+μ(c′,l)=nμ(c,c )+μ(c ,l)=n. Let G′=(,μ′)G =(C,μ ) be a completion of G where l wins all its remaining comparisons, i.e., such that for all c∈c , μ′(l,c)=μ(l,c)=n2μ (l,c)=μ(l,c)= n2, and where for each pair (c,c′)∈K×∖l(c,c )∈ K×C \l\ with c≠c′c≠ c , if c,c′∈E\c,c \∈ E then μ′(c,c′)=μ(c,c′)=n2μ (c,c )=μ(c,c )= n2 else μ(c,c′)=n−μ(c′,l)=n2μ(c,c )=n-μ(c ,l)= n2. It is clear that l is not strictly weighted covered by any candidate in K. Now suppose that one of the inequalities in T0=(K0,E0)T_0=(K_0,E_0) is strict. Let us assume that it is associated to candidate c0∈Kc_0∈ K. If T0T_0 only contains one vertex, then c0c_0 strictly weighted covers l. Else for l not to be weighted covered by c0c_0, G has to be extended in another partial tournament G1=(,μ1)G_1=(C, _1) where exists c1∈K0c_1∈ K_0, c1≠c0c_1≠ c_0 such that c0,c1∈E0\c_0,c_1\∈ E_0 where μ1(c0,c1)<μ1(l,c1) _1(c_0,c_1)< _1(l,c_1). Thus μ1(c1,c0)≥n−μ1(c0,c1)>n−μ1(l,c1) _1(c_1,c_0)≥ n- _1(c_0,c_1)>n- _1(l,c_1) and we have a new strict inequality μ1(c1,c0)+μ1(l,c1)>n _1(c_1,c_0)+ _1(l,c_1)>n. This means that exists T1=(K1,E1)T_1=(K_1,E_1) a sub-tree of T0T_0 with K1⊆K0∖c0K_1 K_0 \c_0\ and E1⊊E0E_1 E_0 such that for each c∈K1c∈ K_1, μ1(c,l)≥n2 _1(c,l)≥ n2 and for each c′∈∖l,c0,cc \l,c_0,c\, if c,c′∉E1\c,c \ ∈ E_1 then μ(c,c′)+μ(c′,l)≥nμ(c,c )+μ(c ,l)≥ n where exists a strict inequality. This way we build a strictly decreasing sequence of trees with at least one strict inequality. Since we are working with a finite number of candidate, we end up with a tree restricted to one vertex which strictly weighted covers l in each completion. ∎ Appendix 0.B Proofs for Section 5 See 5.1 Proof Given a directed graph G=(,μ)G=(C,μ). A subset of vertices K∈CK∈ C is a strongly connected component if: (i) for each pair (x,y)∈K2(x,y)∈ K^2 with x≠yx≠ y, there exist a path from x to y and (i) K is maximal, in the sense that no vertex can be added without violating condition (i). Given a complete tournament G=(,μ)G=(C,μ) with ||=m|C|=m, and a losing candidate l∈∖TC(G)l (G), Let =(,μ)X=(C, _X) be a dMS for l∉TC(G)l ∈ (G). Let ∼ be the equivalence relation on C defined by x∼yx y if and only if there are directed paths from x to y and y to x. The equivalence classes of ∼ are the strongly connected components of G. We define the condensation graph G~=(~,μ~) G=( C, μ), i.e., the quotient graph of G by ∼ with ~=/∼ C=C/ and for (x,y)∈~2(x,y)∈ C^2 with x≠yx≠ y, μ~(x,y)=1 μ(x,y)=1 if and only if exist (u,v)∈x×y(u,v)∈ x× y such that μ(u,v)=1μ(u,v)=1. G~ G is naturally a directed acyclic graph. However, since G is complete, G~ G is complete. Hence ≻ , the order induced by G~ G on the strongly connected components of G is total. Let p be the number of strongly connected components of G. Since l∉TC(G)l ∈ (G), l cannot reach all candidates in G and p≥2p≥ 2. Let A1,A2,…,Ap\A_1,A_2,…,A_p\ be the set of strongly connected components of G such that A1≻A2≻⋯≻ApA_1 A_2 … A_p. Let 2≤il≤p2≤ i_l≤ p be such that l∈Aill∈ A_i_l. According to Theorem 4.1, exists K⊆∖lK \l\ with K≠∅K≠ such that for each pair (c,c′)∈K×∖K(c,c )∈ K×C K, μ(c,c′)=1μ(c,c )=1. But for each strongly connected component A, either A⊆KA K or A∩K=∅A∩ K= otherwise some candidates in A could not reach other candidates in A. And for 1≤i≤p1≤ i≤ p, if Ai⊆KA_i K then for all 1≤j≤i1≤ j≤ i, Aj⊆KA_j K else there would exist (A,A′)∈A1,A2,…,Ap2(A,A )∈\A_1,A_2,…,A_p\^2 with A≻A′A A such that exists (x,y)∈A×A′(x,y)∈ A× A such that μ(y,x)=1μ(y,x)=1. Hence, the only possibilities for K are ⋃j=1iAj _j=1^iA_j with 1≤i≤il−11≤ i≤ i_l-1. Additionally, to split G between K and its complementary |K|(||−|K|)|K|(|C|-|K|) pairwise comparisons are needed. Let the function f:x↦x(m−x)f:x x(m-x) be defined on [|A1|,|⋃j=1il−1Aj|][|A_1|,| _j=1^i_l-1A_j|]. f is clearly concave and thus reaches its minimum either in x=|A1|x=|A_1| or x=|⋃j=1il−1Aj|x=| _j=1^i_l-1A_j|. Since A1=TC(G)A_1= (G), ⋃j=ilpAj=m−⋃j=1il−1Aj _j=i_l^pA_j=m- _j=1^i_l-1A_j and ⋃j=ilpAj=c:c∈,l can reach c in G _j=i_l^pA_j=\c:c ,l can reach c in G\, ||=mint∈α,βt(m−t)|X|= _t∈\α,β\t(m-t) where α=|TC(G)|α=| (G)| and β=|c:c∈,l can reach c in G|β=|\c:c ,l can reach c in G\|. If |A1|(m−|A1|)≤|⋃j=1il−1Aj|(m−|⋃j=1il−1Aj|)|A_1|(m-|A_1|)≤| _j=1^i_l-1A_j|(m-| _j=1^i_l-1A_j|) then let =(,μ)X=(C, _X) be partial sub-tournament of G such that for all (c,c′)∈A1×(∖A1)(c,c )∈ A_1×(C A_1), μ(c,c′)=1 _X(c,c )=1 and μ _X is null everywhere else. According to Theorem 4.1, l∈NLTC(G)l _ (G). Since ||=|A1|(m−|A1|)|X|=|A_1|(m-|A_1|) matches the lower bound, X is a smallest dMS for l∉TC(G)l ∈ (G). The same reasoning holds when |A1|(m−|A1|)≥|⋃j=1il−1Aj|(m−|⋃j=1il−1Aj|)|A_1|(m-|A_1|)≥| _j=1^i_l-1A_j|(m-| _j=1^i_l-1A_j|). It naturally follows from the beginning of the proof, that an SdMS can be computed in polynomial time. Additionally, by concavity and symmetry, the worst case is reached when candidates are split in two equal parts, i.e., when |TC(G)|=⌈m2⌉|TC(G)|= m2 or |TC(G)|=⌊m2⌋|TC(G)|= m2 and the losing candidate is in A2A_2. In that case, ||=⌈m2⌉⌊m2⌋|X|= m2 m2 . ∎ See 5.2 Proof We start by proving that ⌈n(m−1)+12⌉ n(m-1)+12 comparisons are enough when l has below average performances, i.e., σBO(l)≤⌊n(m−1)−12⌋ _ (l)≤ n(m-1)-12 . Given n voters, a complete n-weighted tournament G=(,μ)G=(C,μ) with ||=m|C|=m, a losing candidate l∈∖BO(G)l (G). Suppose that σBO(l,G′)≤⌊n(m−1)−12⌋ _ (l,G )≤ n(m-1)-12 , then ∑c≠lμG(c,l)=n(m−1)−σBO(l,G)≥⌈n(m−1)+12⌉ _c≠ l _G(c,l)=n(m-1)- _ (l,G)≥ n(m-1)+12 . Let ⊆GX G such that ∑c≠lμ(c,l)=⌈n(m−1)+12⌉ _c≠ l _X(c,l)= n(m-1)+12 and μ _X is null otherwise. Clearly, ||=⌈n(m−1)+12⌉|X|= n(m-1)+12 . Then for all complete tournaments G′G completing X we have σBO(l,G′)=n(m−1)−∑c≠lμG′(c,l)≤n(m−1)−∑c≠lμ(c,l)=n(m−1)−⌈n(m−1)+12⌉=⌊n(m−1)−12⌋ _ (l,G )=n(m-1)- _c≠ l _G (c,l)≤ n(m-1)- _c≠ l _X(c,l)=n(m-1)- n(m-1)+12 = n(m-1)-12 . Moreover, ∑c≠lσBO(c,G′)=nm(m−1)2−σBO(l,G′)=nm(m−1)2−⌊n(m−1)−12⌋=n(m−1)(m−1)2+⌈12⌉=n(m−1)(m−1)2+1 _c≠ l _ (c,G )=n m(m-1)2- _ (l,G )=n m(m-1)2- n(m-1)-12 =n (m-1)(m-1)2+ 12 =n (m-1)(m-1)2+1 and by the pigeonhole principle, among the m−1m-1 candidates distinct from l, there exists c0c_0 such that σBO(c0,G′)≥⌈∑c≠lσBO(c,G′)m−1⌉=⌈n(m−1)2+1m−1⌉ _ (c_0,G )≥ _c≠ l _ (c,G )m-1 = n(m-1)2+ 1m-1 . Hence, σBO(c0,G′)>σBO(l,G′) _ (c_0,G )> _ (l,G ) and l is a necessary loser for X and X contains a dMS. Let us now prove that n(m−1)+1−maxc∈Aμ(c,l)n(m-1)+1- _c∈ Aμ(c,l) comparisons are always enough. Given n voters, a complete n-weighted tournament G=(,μ)G=(C,μ) with ||=m|C|=m, a losing candidate l∈∖BO(G)l (G). Let A=c:c∈,σBO(c,G)>σBO(l,G)A=\c:c , _ (c,G)> _ (l,G)\ and c0=argmaxc∈AμG(c,l)c_0= _c∈ A _G(c,l). Then, ∑c≠c0μG(c0,c)+∑c≠lμG(c,l)=σBO(c0,G)+n(m−1)−σBO(l,G)≥σBO(l,G)+1+n(m−1)−σBO(l,G)=n(m−1)+1 _c≠ c_0 _G(c_0,c)+ _c≠ l _G(c,l)= _ (c_0,G)+n(m-1)- _ (l,G)≥ _ (l,G)+1+n(m-1)- _ (l,G)=n(m-1)+1. Let ⊆GX G be such that μ(c0,l)=μG(c0,l) _X(c_0,l)= _G(c_0,l), ∑c≠lμ(c0,c)+∑c≠lμ(c,l)=n(m−1)+1 _c≠ l _X(c_0,c)+ _c≠ l _X(c,l)=n(m-1)+1 and μ _X is null otherwise. ||=n(m−1)+1−μ(c0,l)=n(m−1)+1−maxc∈Aμ(c,l)|X|=n(m-1)+1- _X(c_0,l)=n(m-1)+1- _c∈ Aμ(c,l). Then for all complete tournaments G′G completing X we have ∑c≠lμG′(c0,c)+∑c≠lμG′(c,l)≥n(m−1)+1⟹σBO(c0,G′)+n(m−1)−σBO(l,G′)≥n(m−1)+1⟹σBO(c0,G′)>σBO(l,G′) _c≠ l _G (c_0,c)+ _c≠ l _G (c,l)≥ n(m-1)+1 _ (c_0,G )+n(m-1)- _ (l,G )≥ n(m-1)+1 _ (c_0,G )> _ (l,G ) and l is a necessary loser for X and X contains a dMS. We now move on the lower bounds. Given n voters, a complete n-weighted tournament G=(,μ)G=(C,μ) with ||=m|C|=m, a losing candidate l∈∖BO(G)l (G), let =(,μ)X=(C, _X) be a dMS for l∉BO(G)l ∈ (G). According to Theorem 4.2, exists K⊆∖lK \l\ with |K|=k|K|=k such that ∑c∈K∑c′∉Kμ(c,c′)+k∑c∈μ(c,l)>kn(m−1)−nk(k−1)2. _c∈ K _c ∈ Kμ(c,c )+k _c μ(c,l)>kn(m-1)-n k(k-1)2. We have that ||≥∑c∈K∑c′∉Kμ(c,c′)|X|≥ _c∈ K _c ∈ Kμ(c,c ) and ||≥∑c∈μ(c,l)|X|≥ _c μ(c,l). Hence, ||+k||>kn(m−1)−nk(k−1)2 |X|+k|X|>kn(m-1)-n k(k-1)2 ⇔ (k+1)||>kn(m−1)−nk(k−1)2 (k+1)|X|>kn(m-1)-n k(k-1)2 ⇔ ||>1k+1(kn(m−1)−nk(k−1)2) |X|> 1k+1 (kn(m-1)-n k(k-1)2 ) ⇔ ||>(1−1k+1)(n(m−1)−nk−12) |X|> (1- 1k+1 ) (n(m-1)-n k-12 ) ⇔ ||>(1−1k+1)(nm−nk+12) |X|> (1- 1k+1 ) (nm-n k+12 ) Let f be the function x↦(1−1x+1)(nm−nx+12)x (1- 1x+1 ) (nm-n x+12 ) defined on [1;m−1]→ℝ[1;m-1] . f is twice differentiable on its domain. f′:x↦1(x+1)2(nm−nx+12)−(1−1x+1)n2f :x 1(x+1)^2 (nm-n x+12 )- (1- 1x+1 ) n2 and f′:x↦−2(x+1)3(nm−nx+12)−1(x+1)2n2−1(x+1)2n2=−2nm(x+1)3f :x -2(x+1)^3 (nm-n x+12 )- 1(x+1)^2 n2- 1(x+1)^2 n2= -2nm(x+1)^3. f′f is clearly negative on the interval [1;m−1][1;m-1], thus f is concave and minimal at x=1x=1 or x=m−1x=m-1. f(1)=(1−11+1)(nm−n1+12)=n(m−1)2f(1)= (1- 11+1 ) (nm-n 1+12 )= n(m-1)2. f(m−1)=(1−1m−1+1)(nm−nm−1+12)=n(m−1)2f(m-1)= (1- 1m-1+1 ) (nm-n m-1+12 )= n(m-1)2. Hence, ||>n(m−1)2|X|> n(m-1)2. Since |||X| is an integer we have ||≥⌈n(m−1)+12⌉|X|≥ n(m-1)+12 . Suppose now that σBO(l)>⌊n(m−1)−12⌋ _ (l)> n(m-1)-12 . We have that ∑c∈μ(c,l)≤∑c∈μ(c,l)=n(m−1)−σBO(l)<n(m−1)−⌊n(m−1)−12⌋=⌈n(m−1)+12⌉ _c _X(c,l)≤ _c μ(c,l)=n(m-1)- _ (l)<n(m-1)- n(m-1)-12 = n(m-1)+12 . Thus, ∑c∈μ(c,l)≤⌈n(m−1)−12⌉ _c _X(c,l)≤ n(m-1)-12 , it is not possible to take K=∖lK=C \l\ anymore and ||>⌈n(m−1)+12⌉|X|> n(m-1)+12 . If we look at ∑c∈K∑c′∉Kμ(c,c′)+k∑c∈μ(c,l)>kn(m−1)−nk(k−1)2 _c∈ K _c ∈ Kμ(c,c )+k _c μ(c,l)>kn(m-1)-n k(k-1)2 it is clear that: • for c∈Kc∈ K μ(c,l)μ(c,l) contributes k+1k+1 times in the left hand • for c,c′∈K×(∖l)c,c ∈ K×(C \l\) μ(c,c′)μ(c,c ) contributes 11 • for c∉Kc ∈ K μ(c,l)μ(c,l) contributes k • for c,c′∈(∖K)×(∖l)c,c ∈(C K)×(C \l\) μ(c,c′)μ(c,c ) contributes 00. Hence, maximizing ∑c∈μ(c,l) _c μ(c,l) is never damaging to obtain smallest dMSs and we can take it to its maximal value, n(m−1)−σBO(l,G)n(m-1)- _ (l,G). We have: ∑c∈K∑c′∉Kμ(c,c′)+k∑c∈μ(c,l)>kn(m−1)−nk(k−1)2 _c∈ K _c ∈ Kμ(c,c )+k _c μ(c,l)>kn(m-1)-n k(k-1)2 ⟹ ∑c∈K∑c′∈∖(K∪l)μ(c,c′)+∑c∈Kμ(c,l)+k∑c∈μ(c,l)>kn(m−1)−nk(k−1)2 _c∈ K _c (K∪\l\)μ(c,c )+ _c∈ Kμ(c,l)+k _c μ(c,l)>kn(m-1)-n k(k-1)2 ⟹ ∑c∈K∑c′∈∖(K∪l)μ(c,c′)+∑c∈Kμ(c,l)+k(n(m−1)−σBO(l,G))>kn(m−1)−nk(k−1)2 _c∈ K _c (K∪\l\)μ(c,c )+ _c∈ Kμ(c,l)+k(n(m-1)- _ (l,G))>kn(m-1)-n k(k-1)2 ⟹ ∑c∈K∑c′∈∖(K∪l)μ(c,c′)>kσBO(l,G)−nk(k−1)2−∑c∈Kμ(c,l). _c∈ K _c (K∪\l\)μ(c,c )>k _ (l,G)-n k(k-1)2- _c∈ Kμ(c,l). With a MILP solver, we can fin K∗K^* and μ∗μ^* which minimize ∑c∈K∑c′∈∖(K∪l)μ(c,c′) _c∈ K _c (K∪\l\)μ(c,c ) while satisfying this constraint. Finally, we can take =(,μ)X=(C, _X) with ∀c∈K,c′∈∖(K∪l)∀ c∈ K,c (K∪\l\), μ(c,c′)=μ∗(c,c′) _X(c,c )=μ^*(c,c ), μ(c,l)=μ(c,l) _X(c,l)=μ(c,l) and μ _X null elsewhere. Hence, ||=∑c∈K∗∑c′∈∖(K∗∪l)μ∗(c,c′)+n(m−1)−σBO(l,G)|X|= _c∈ K^* _c (K^*∪\l\)μ^*(c,c )+n(m-1)- _ (l,G). ∎ See 5.3 See 5.4 Proof In the case m=2m=2, ensuring that a strict majority of voters prefers the other candidate to l is clearly necessary and sufficient so we move to the case where m≥3m≥ 3. We start by proving that (σM(l)+1)(m−3)+n+1( _ (l)+1)(m-3)+n+1 and (σM(l)+1)(m−2)+n+1( _ (l)+1)(m-2)+n+1 are enough depending on the cases. Given n voters, a complete n-weighted tournament G=(,μ)G=(C,μ) with ||=m|C|=m, a losing candidate l∈∖M(G)l (G). Since l∉M(G)l ∈ (G), exists c0∈∖lc_0 \l\ such that σM(c0)>σM(l,G) _ (c_0)> _ (l,G). Additionally, let c1=argmaxc≠lμ(c,l)c_1= _c≠ lμ(c,l), by definition μ(c1,l)=n−σM(l,G)μ(c_1,l)=n- _ (l,G). Let =(,μ)X=(C, _X) be a such that for all c∈∖c0c \c_0\, μ(c0,c)=σM(l,G)+1 _X(c_0,c)= _ (l,G)+1, μ(c1,l)=n−σM(l,G) _X(c_1,l)=n- _ (l,G) and the rest of μ _X is null. Then, for all completion G′G of X, σM(c0,G′)=minc≠c0μG′(c0,c)≥minc≠c0μ(c0,c)=σM(l,G)+1 _ (c_0,G )= _c≠ c_0 _G (c_0,c)≥ _c≠ c_0 _X(c_0,c)= _ (l,G)+1 and σM(l,G′)=minc≠lμG′(l,c)=n−maxc≠lμG′(c,l)≥n−maxc≠lμ(c,l)≥n−μ(c1,l)=n−(n−σM(l,G))=σM(l,G) _ (l,G )= _c≠ l _G (l,c)=n- _c≠ l _G (c,l)≥ n- _c≠ l _X(c,l)≥ n- _X(c_1,l)=n-(n- _ (l,G))= _ (l,G). Hence, σM(c0,G′)>σM(l,G′) _ (c_0,G )> _ (l,G ) and l is a necessary loser for X and X contains a dMS. If c0≠c1c_0≠ c_1, |X|=(m−1)(σM(l,G)+1)+n−σM(l,G)=(σM(l)+1)(m−2)+n+1|X|=(m-1)( _ (l,G)+1)+n- _ (l,G)=( _ (l)+1)(m-2)+n+1 and if c0=c1c_0=c_1, having μ(c0,l)=n−σM(l,G) _X(c_0,l)=n- _ (l,G) ensures that μ(c0,l)=σM(l,G)+1 _X(c_0,l)= _ (l,G)+1 (σM(l,G)≤⌊n−12⌋ _ (l,G)≤ n-12 otherwise, l is a Condorcet winner and thus a Maximin winner) so we can save σM(l,G)+1 _ (l,G)+1 comparisons and |X|=(m−2)(σM(l,G)+1)+n−σM(l,G)=(σM(l)+1)(m−3)+n+1|X|=(m-2)( _ (l,G)+1)+n- _ (l,G)=( _ (l)+1)(m-3)+n+1. We now prove the matching lower bounds. Given n voters, a complete n-weighted tournament G=(,μ)G=(C,μ) with ||=m|C|=m, a losing candidate l∈∖M(G)l (G), according to Theorem 4.3, for l to be the necessary M -loser of a partial sub-tournament G′⊆G G, G′G needs to contain two elements: • a pairwise comparison in which l is beaten to limit its maximal possible maximin score, • a set of candidates arranged in a tree where each candidate in the tree beats the non adjacent candidates in the tree with a strictly stronger weight than l’s possible maximin score. Observe that if the tree contains k≥1k≥ 1 candidates, k(m−3)+2k(m-3)+2 edges needs to have a stronger weight than l’s possible maximin score. Each time the maximal possible maximin score of l decreases by one, we can save k(m−3)+2≥1k(m-3)+2≥ 1 comparisons. Hence, to obtain the smallest dMS, we want the maximal possible maximin score of l to be as low as possible, i.e., fixed to σM(l,G) _ (l,G). Let c1=argmaxc≠lμ(c,l)c_1= _c≠ lμ(c,l), we can fix μ(c1,l)=n−σM(l,G) _X(c_1,l)=n- _ (l,G) to bound the maximal possible maximin score of l to σM(l,G) _ (l,G) using n−σM(l,G)n- _ (l,G) comparisons. Additionally, note that k(m−3)+2k(m-3)+2 increases with k so we want as few candidates in tree as possible. Since l∉M(G)l ∈ (G), exists a candidate c0≠lc_0≠ l such that σM(c0)>σM(l) _ (c_0)> _ (l). Thus, we can take the tree reduced to the single vertex c0c_0 as c0c_0 beats any other candidate with strictly more than σM(l) _ (l) comparisons. This gives us a lower bound of (m−1)(σM(l)+1)(m-1)( _ (l)+1) pairwise comparisons for this constraint. If for all c∈c such that σM(c)>σM(l) _ (c)> _ (l), μ(c,l)<n−σM(l)μ(c,l)<n- _ (l) both constraints cannot be combined and both sets of pairwise comparisons are disjoint. Hence, a lower bound of n−σM(l,G)+(m−1)(σM(l)+1)=(σM(l)+1)(m−2)+n+1n- _ (l,G)+(m-1)( _ (l)+1)=( _ (l)+1)(m-2)+n+1 corresponding to the third case of the theorem. In the other case, we can have c0=c1c_0=c_1 and by fixing μ(c1,l)=n−σM(l,G) _X(c_1,l)=n- _ (l,G), we have μ(c1,l)≥σM(l,G)+1 _X(c_1,l)≥ _ (l,G)+1 without requiring additional comparisons. This allows to save an extra σM(l,G)+1 _ (l,G)+1 which gives a final lower bound of (σM(l)+1)(m−3)+n+1( _ (l)+1)(m-3)+n+1. It naturally follows from the beginning of the proof, that an SdMS can be computed in polynomial time. Finally, since the score of a losing candidate cannot be greater than ⌊n−12⌋ n-12 otherwise, it is a Condorcet winner and thus a Maximin winner, we have that for each SdMS X for maximin, (⌊n−12⌋+1)(m−2)+n+1=⌈n+12⌉(m−2)+n+1( n-12 +1)(m-2)+n+1= n+12 (m-2)+n+1. ∎ See 5.5 Proof We first provide upper bounds on the number of pairwise comparisons required in each case by exhibiting partial sub-tournaments where l is a necessary loser in each case. Given n voters, a complete n-weighted tournament G=(,μ)G=(C,μ) with ||=m|C|=m, a losing candidate l∈∖wUC(G)l (G). We start with the second case and we show that there always exists a dMS of size n(m−2)+⌈n+12⌉n(m-2)+ n+12 . Since l is a losing candidate in G, exists c0∈∖lc_0 \l\ such that c0c_0 weighted covers l, i.e., for all candidates c∈∖c0c \c_0\, μ(c0,c)≥μ(l,c)μ(c_0,c)≥μ(l,c). Hence, for all candidates c∈∖c0,lc \c_0,l\, μ(c0,c)≥n−μ(c,l)μ(c_0,c)≥ n-μ(c,l) or equivalently, μ(c0,c)+μ(c,l)≥nμ(c_0,c)+μ(c,l)≥ n. Let ⊆GX G be a partial sub-tournament of G with =(,μ)X=(C, _X) and μ(c0,l)=⌈n2⌉ _X(c_0,l)= n2 , for all candidates c∈∖c0,lc \c_0,l\, μX(c0,c)+μ(c,l)≥n _X(c_0,c)+ _X(c,l)≥ n. For each completion =(,μ)Y=(C, _Y) of X, μ(c0,l)≥n2≥μ(l,c0) _Y(c_0,l)≥ n2≥ _Y(l,c_0). Additionally, for all candidates c∈∖c0,lc \c_0,l\, μY(c0,c)+μ(c,l)≥μX(c0,c)+μ(c,l)≥n _Y(c_0,c)+ _Y(c,l)≥ _X(c_0,c)+ _X(c,l)≥ n. Thus, for all candidates c∈∖c0,lc \c_0,l\, μY(c0,c)≥n−μ(c,l)=μ(l,c) _Y(c_0,c)≥ n- _Y(c,l)= _Y(l,c). We have that l is weighted covered by c0c_0 in Y and l∈NLwUC()l _ (X). Finally, for at least one of the inequalities to be strict we need an additional comparison if n is even and none if n is odd as μ(c0,l)≥n2 _Y(c_0,l)≥ n2 is already strict. We encode this by changing the ⌈n2⌉ n2 into ⌈n+12⌉ n+12 Since, ||=n(m−2)+⌈n+12⌉|X|=n(m-2)+ n+12 , n(m−2)+⌈n+12⌉n(m-2)+ n+12 pairwise comparisons are enough. We now move on to the first case. Suppose p=∑c∈∖l,c0,c1μ(c,l)−n(m−3)−⌊n2⌋>0p= _c \l,c_0,c_1\μ(c,l)-n(m-3)- n2 >0 where (c0,c1)∈(∖l)2(c_0,c_1)∈(C \l\)^2 maximizes ∑c∈∖l,c0,c1μ(c,l) _c \l,c_0,c_1\μ(c,l) with c0≠c1c_0≠ c_1, μ(ci,l)≥n2μ(c_i,l)≥ n2, for all c∈∖l,c0,c1c \l,c_0,c_1\, μ(ci,c)+μ(c,l)≥nμ(c_i,c)+μ(c,l)≥ n for i∈0,1i∈\0,1\ and at least one of the inequalities is strict. Let ⊆GX G be a partial sub-tournament of G with =(,μ)X=(C, _X) and μ(ci,l)=⌈n2⌉ _X(c_i,l)= n2 , for all c∈∖l,c0,c1c \l,c_0,c_1\, μ(c,l)=μ(c,l) _X(c,l)=μ(c,l) and μ(ci,c)=n−μ(c,l) _X(c_i,c)=n-μ(c,l) for i∈0,1i∈\0,1\. For each completion =(,μ)Y=(C, _Y) of X, since μ(c0,c1)+μ(c1,c0)=n _Y(c_0,c_1)+ _Y(c_1,c_0)=n, μ(c0,c1)≥⌈n2⌉ _Y(c_0,c_1)≥ n2 or μ(c1,c0)≥⌈n2⌉ _Y(c_1,c_0)≥ n2 . Without loss of generality, suppose μ(c0,c1)≥⌈n2⌉ _Y(c_0,c_1)≥ n2 . Since μ(c1,l)=⌈n2⌉ _X(c_1,l)= n2 , μ(l,c1)=n−μ(c1,l)≤n−μ(c1,l)=n−⌈n2⌉=⌊n2⌋ _Y(l,c_1)=n- _Y(c_1,l)≤ n- _X(c_1,l)=n- n2 = n2 . Hence μ(c0,c1)≥μ(l,c1) _Y(c_0,c_1)≥ _Y(l,c_1). Additionally, μ(c0,l)≥μ(c0,l)≥⌈n2⌉ _Y(c_0,l)≥ _X(c_0,l)≥ n2 and μ(l,c0)=n−μ(c0,l)≤n−⌈n2⌉≤⌊n2⌋ _Y(l,c_0)=n- _Y(c_0,l)≤ n- n2 ≤ n2 . Thus μ(c0,l)≥μ(l,c0) _Y(c_0,l)≥ _Y(l,c_0). Moreover, for all c∈∖l,c0,c1c \l,c_0,c_1\, μ(c0,c)+μ(c,l)≥μ(c0,c)+μ(c,l)=μ(c,l)+n−μ(c,l)=n _Y(c_0,c)+ _Y(c,l)≥ _X(c_0,c)+ _X(c,l)=μ(c,l)+n-μ(c,l)=n. Thus μ(c0,c)≥n−μ(c,l)=μ(l,c) _Y(c_0,c)≥ n- _Y(c,l)= _Y(l,c). Finally, 2⌈n2⌉+∑c∈∖l,c0,c1μ(c,l)+2∑c∈∖l,c0,c1(n−μ(c,l)) 2 n2 + _c \l,c_0,c_1\μ(c,l)+2 _c \l,c_0,c_1\(n-μ(c,l)) =2⌈n2⌉+2∑c∈∖l,c0,c1n−∑c∈∖l,c0,c1(μ(c,l)) =2 n2 +2 _c \l,c_0,c_1\n- _c \l,c_0,c_1\(μ(c,l)) =2⌈n2⌉+2n(m−3)−∑c∈∖l,c0,c1(μ(c,l)) =2 n2 +2n(m-3)- _c \l,c_0,c_1\(μ(c,l)) =⌈n2⌉+n(m−3)−p = n2 +n(m-3)-p Additionally, like in the previous case, for at least one of the inequalities to be strict we need an additional comparison if n is even and none if n is odd as μ(c0,l)≥n2 _Y(c_0,l)≥ n2 is already strict. We encode this by changing the ⌈n2⌉ n2 into ⌈n+12⌉ n+12 . || |X| =⌈n+12⌉+n(m−3)−p<⌈n+12⌉+n(m−3) = n+12 +n(m-3)-p< n+12 +n(m-3) Since, ||=n(m−3)+⌈n+12⌉−p|X|=n(m-3)+ n+12 -p, n(m−3)+⌈n+12⌉−pn(m-3)+ n+12 -p pairwise comparisons are enough. We now prove the matching lower bounds. Since dMSs are partial tournaments where l is a necessary loser, we use the characterization provided in Theorem 4.4 to obtain lower bounds on the riquered number of pairwise comparisons. Given n voters, a complete n-weighted tournament G=(,μ)G=(C,μ) with ||=m|C|=m, a losing candidate l∈∖wUC(G)l (G). According to Theorem 4.4, for each dMS =(,μ)X=(C, _X) for l∉wUC(G)l ∈ (G), we have that exists a tree T=(K,E)T=(K,E) with K⊆∖lK \l\ such that for each c∈Kc∈ K, μ(c,l)≥n2 _X(c,l)≥ n2 and ∀c′∈∖l∀ c \l\, ∀c∈K∀ c∈ K, if if c,c′∉E\c,c \ ∈ E then μ(c,c′)+μ(c′,l)≥n _X(c,c )+ _X(c ,l)≥ n and at least one of the inequalities is strict. In particular, ∀c′∈∖l∀ c \l\, unless ∀c∈K∀ c∈ K, c,c′∈E\c,c \∈ E, i.e, T is a star graph with center c′c , ∃c∈K∃ c∈ K such that μ(c,c′)+μ(c′,l)≥n _X(c,c )+ _X(c ,l)≥ n. Note that if |K|=1|K|=1 and we denote K=cK=\c\, then T is a star graph with center c. If |K|=2|K|=2 and K=c0,c1K=\c_0,c_1\, then T is both a star graph with center c0c_0 and a star graph with center c1c_1. If |K|≥3|K|≥ 3, there exists at most on candidate c such that T is a star graph with center c otherwise T would have a cycle. Additionally, if T is a star graph with center c, we have c∈Kc∈ K and μ(c,l)≥n2 _X(c,l)≥ n2. Hence, if |K|=1|K|=1 or |K|≥3|K|≥ 3, if T is a star graph we have m−2m-2 independent inequalities of the form μ(c,c′)+μ(c′,l)≥n _X(c,c )+ _X(c ,l)≥ n and one of the form μ(c,l)≥n2 _X(c,l)≥ n2, and at least one has to be strict thus ||≥(m−2)n+⌈n+12⌉|X|≥(m-2)n+ n+12 else we have m−1m-1 independent inequalities of the form μ(c,c′)+μ(c′,l)≥n _X(c,c )+ _X(c ,l)≥ n and ||≥(m−1)n≥(m−2)n+⌈n+12⌉|X|≥(m-1)n≥(m-2)n+ n+12 . If |K|=2|K|=2 and K=c0,c1K=\c_0,c_1\, our set of constrains is μ(ci,l)≥n2 _X(c_i,l)≥ n2 and for all c∈∖l,c0,c1c \l,c_0,c_1\, μ(ci,c)+μ(c,l)≥n _X(c_i,c)+ _X(c,l)≥ n for i∈0,1i∈\0,1\ and at least one inequality has to be strict. Since μ(c,l) _X(c,l) appears both in μ(c0,c)+μ(c,l)≥n _X(c_0,c)+ _X(c,l)≥ n and μ(c1,c)+μ(c,l)≥n _X(c_1,c)+ _X(c,l)≥ n, to obtain the smallest dMS, it is clear that we have to take its highest possible value which is μ(c,l)μ(c,l). In that case, if we ignore the strict inequality constraint, || |X| =2⌈n2⌉+∑c∈∖l,c0,c1μ(c,l)+2∑c∈∖l,c0,c1(n−μ(c,l)) =2 n2 + _c \l,c_0,c_1\μ(c,l)+2 _c \l,c_0,c_1\(n-μ(c,l)) =2⌈n2⌉+2n(m−3)−∑c∈∖l,c0,c1(μ(c,l)). =2 n2 +2n(m-3)- _c \l,c_0,c_1\(μ(c,l)). Once again, for at least one of the inequalities to be strict we need an additional comparison we change one ⌈n2⌉ n2 into ⌈n+12⌉ n+12 . If p=∑c∈∖l,c0,c1μ(c,l)−n(m−3)−⌊n2⌋>0p= _c \l,c_0,c_1\μ(c,l)-n(m-3)- n2 >0 as in the first case of the theorem then || |X| =⌈n2⌉+⌈n+12⌉+2n(m−3)−∑c∈∖l,c0,c1(μ(c,l)) = n2 + n+12 +2n(m-3)- _c \l,c_0,c_1\(μ(c,l)) =⌈n+12⌉+n(m−3)−p = n+12 +n(m-3)-p <⌈n+12⌉+n(m−2). < n+12 +n(m-2). Else taking |K|=2|K|=2 does not help to obtain smaller dMSs and we go back to the general approach with |K|=1|K|=1. It naturally follows from the beginning of the proof, that an SdMS can be computed in polynomial time. Finally, since the score of a losing candidate cannot be greater than ⌊n−12⌋ n-12 otherwise, it is a Condorcet winner and thus a Maximin winner, we have that for each SdMS X for the weighted uncovered set, ||≤n(m−2)+⌈n+12⌉|X|≤ n(m-2)+ n+12 . ∎ See 1 Proof In the unweighted case (n=1n=1), ∑c∈∖l,c0,c1μ(c,l)≤∑c∈∖l,c0,c11≤m−3 _c \l,c_0,c_1\μ(c,l)≤ _c \l,c_0,c_1\1≤ m-3. Hence, p=∑c∈∖l,c0,c1μ(c,l)−(m−3)−⌊12⌋≤0p= _c \l,c_0,c_1\μ(c,l)-(m-3)- 12 ≤ 0 and the first case of Theorem 5.5 never occurs. ∎