betaFeedback

WorksEconomics, Econometrics and Finance

Obvious group manipulations in voting

Abstract

We study obvious group manipulation in voting and characterize it as manipulation identifiable from a coalition's option sets alone. Our analysis focuses on two overlapping classes: tops-only rules and rules satisfying the majority criterion, including all Condorcet-consistent rules. On the universal domain with at least three alternatives, a tops-only rule is not obviously manipulable by groups (NOMG) if and only if it is dictatorial. For rules satisfying the majority criterion, NOMG is impossible when n,m≥3n,m\geq3, except with four voters and three alternatives. We quantify the coalition sizes behind these restrictions, obtaining sharp bounds for efficient tops-only rules and an exact threshold for majority-criterion rules with odd electorates. In the exceptional configuration, we characterize an interval of NOMG scoring rules containing Borda, which is also Condorcet consistent there. We further characterize NOMG with two alternatives and apply our tops-only characterization to generalized median voter schemes and voting by committees.

JEL classification: D71, D82.

Introduction

The Gibbard–Satterthwaite theorem ([21, 34]) makes manipulation unavoidable for every onto and non-dictatorial voting rule on the universal domain when there are at least three alternatives. It does not distinguish between a deviation that is easy to recognize and one whose success depends on fine information about the other voters. The notion of obvious manipulation, introduced by Troyan and Morrill [37], makes this distinction by comparing the best and the worst outcomes that a report can generate. It has been used to discriminate among manipulable voting rules [1, 7]: many familiar rules are manipulable, but not obviously so.

This paper asks what changes when manipulation is coordinated by a coalition. Coalitions matter because many rules that pass the individual test owe their good behavior to the fact that a single voter has little influence. The information a coalition needs in order to recognize a profitable deviation is of the same kind as for an individual: it must know which outcomes its joint report can produce, not how the outsiders will vote.

Given a coalition, its members’ true preferences, and a misreport, we compare the set of outcomes left open by truthful reporting with the set left open by the misreport. The misreport is an obvious group manipulation if either some outcome left open by truthful reporting is ranked by every member below every outcome left open by the misreport, or some outcome left open by the misreport is ranked by every member above every outcome left open by truthful reporting. For a single voter this is the notion of Troyan and Morrill [37], and for the grand coalition it is an ordinary group manipulation. A rule is not obviously manipulable by groups (NOMG) if no coalition has an obvious group manipulation.

We first give an informational foundation for this definition: with at least three alternatives, obvious group manipulations are exactly the misreports that remain group manipulations under every voting rule generating the same option sets for the coalition (Proposition 1). This is the coalitional counterpart of the characterization in Troyan and Morrill [37]; Doi et al. [19] independently introduced the same notion and obtained this result in a general mechanism-design framework. The result explains why the definition captures deviations whose profitability can be recognized from option sets alone: for each rule consistent with this information, the deviation benefits every coalition member at some outsider profile, although that profile may differ across rules. Conversely, whenever a deviation is not obvious, there is a rule with the same option sets under which it never benefits all coalition members. Thus, the definition has a precise informational interpretation beyond its formal extension of the individual notion.

Within the universe of voting rules, we focus on two prominent classes that capture different aspects of collective choice. Tops-only rules restrict the preference information used by the rule: voters’ favorite alternatives suffice to determine the outcome. This class includes plurality, generalized median voter schemes, and voting by committees. Its importance also stems from the connection between informational simplicity and incentives: Chatterji and Sen [13] study domains on which strategy-proofness and unanimity imply the tops-only property. Rules satisfying the majority criterion instead restrict the response to concentrated support: an alternative ranked first by a strict majority must be selected, while lower ranks may otherwise affect the outcome. This class includes every Condorcet-consistent rule. The broader axiomatic case for majority-based aggregation is developed by Dasgupta and Maskin [15, 16], who study the robustness and characterization of majority rule across preference domains.

These classes provide complementary perspectives on coalitional manipulation: one concerns which preference information a rule uses, and the other concerns the power of a strict majority. They overlap—plurality belongs to both—and neither contains the other. Their comparison therefore lets us examine how obvious group manipulation arises under two distinct restrictions, and how each restriction shapes the protection available against coalitions of different sizes.

Our remaining contributions establish both the restrictions imposed by coalitional obviousness and the possibilities for protection against it. With two alternatives, we characterize NOMG and show that it can be strictly weaker than strategy-proofness. With at least three alternatives, we characterize immunity for tops-only rules and show that full immunity within this class implies dictatorship. Beyond tops-only rules, we establish an impossibility for rules satisfying the majority criterion. We then compare the coalition sizes behind these restrictions, obtaining sharp bounds for efficient tops-only rules and an exact threshold for rules satisfying the majority criterion with odd electorates. An exceptional family of scoring rules provides a positive result, for which we characterize NOMG exactly. Finally, we apply the tops-only characterization to two familiar families of rules, identifying the parameters that provide the greatest protection against obvious group manipulation.

We first consider the case of two alternatives. The only coalitions that can gain unanimously are those whose members agree on their preferred alternative. An efficient rule is NOMG precisely when every proper coalition that can force an alternative can do so by voting unanimously for it (Proposition 2). This condition is much weaker than strategy-proofness: parity rules satisfy it. Thus, with two alternatives, immunity to obvious group manipulation allows for a broader class of rules than strategy-proofness.

With at least three alternatives, we begin with tops-only rules. For every coalition, we characterize when a tops-only rule leaves it without an obvious group manipulation (Theorem 1). For efficient rules the characterization is a single condition, extending the individual veto condition of Arribillaga and Bonifacio [1] to coalitions: if a coalition can veto an alternative with some report, it vetoes it with every report at which none of its members ranks that alternative first.

A tops-only rule is NOMG if and only if it is group strategy-proof (Theorem 2). The Gibbard–Satterthwaite theorem then implies that only dictatorships qualify. For tops-only rules, therefore, the weak informational requirement of obviousness has exactly the same bite as full group strategy-proofness. The proof shows that the supporters of a winning alternative always include a coalition that can force it; a coalition whose members all prefer a different outcome is disjoint from it and therefore leaves the winner in place.

We then extend the analysis beyond tops-only rules. Every rule satisfying the majority criterion, and hence every Condorcet-consistent rule, is obviously manipulable by groups whenever n,m≥3n,m \ge3 and (n,m)≠(4,3)(n,m) \ne(4,3) (Theorem 3). Thus, allowing a rule to use information beyond voters’ top alternatives does not restore compatibility between NOMG and the majority criterion, except possibly in a single configuration of electorate and alternative-set sizes.

We next determine how large coalitions must be for these restrictions to become binding. We say that a rule is kk-NOMG if no coalition with at most kk members has an obvious group manipulation. The grand coalition contributes only efficiency: a rule is NOMG if and only if it is efficient and no proper coalition has an obvious group manipulation. For efficient tops-only rules, immunity to coalitions of up to n−1n-1 voters implies dictatorship (Proposition 4), and this bound is sharp: for every n≥3n \ge3, the rule at which a designated voter decides unless all other voters agree on a different alternative is efficient, non-dictatorial, and immune to coalitions of up to n−2n-2 voters. Thus, the impossibility of full immunity is compatible with protection against all but the largest coalitions. Without efficiency, even immunity to all proper coalitions is compatible with non-dictatorial rules.

For rules satisfying the majority criterion, and hence for Condorcet-consistent rules, every coalition smaller than half the electorate is protected, whereas some minimal strict majority has an obvious group manipulation whenever n,m≥3n,m \ge3 and (n,m)≠(4,3)(n,m) \ne(4,3) (Proposition 5). Thus, for odd nn, the smallest manipulating coalition has exactly (n+1)/2(n+1)/2 members; for even nn, its size is either n/2n/2 or n/2+1n/2+1. For plurality, which is both tops-only and satisfies the majority criterion, the smallest such coalition has ⌈n/2⌉\lceil n/2\rceil members (Proposition 6).

The configuration excluded from the majority results yields a positive result. When (n,m)=(4,3)(n,m)=(4,3), the scoring rule with vector (1,t,0)(1,t,0) is NOMG if and only if 12≤t<23\frac{1}{2}\le t<\frac{2}{3} (Theorem 4). This interval contains Borda’s rule and consists of rules satisfying the majority criterion. Borda’s rule is even Condorcet consistent in this electorate (Corollary 1). These rules show that full immunity to obvious group manipulation can coexist with anonymity, efficiency, and majority responsiveness on the universal domain. They also establish that the tops-only restriction is essential for our dictatorship result and that the exception in the majority impossibility theorem is substantive.

Finally, we apply the tops-only characterization to two classes of rules that are strategy-proof on restricted domains: generalized median voter schemes, strategy-proof on single-peaked preferences (Moulin [26]), and voting by committees, strategy-proof on separable preferences (Barberà et al. [12]). On the universal domain, only their dictatorial members are NOMG, so the question is against which coalition sizes the others are protected. A generalized median voter scheme is kk-NOMG if and only if two conditions on its fixed ballots hold for every coalition with at most kk members: such a coalition can veto at most the two extreme alternatives, and it cannot exclude both of them by splitting its reports between them (Theorem 5). Among non-dictatorial generalized median voter schemes, the largest coalition size that can be protected is the largest integer strictly below n/2n/2 when m≥4m\ge4, and strictly below 2n/32n/3 when m=3m=3; anonymous median voter schemes attain both bounds (Proposition 7). A voting by committees is kk-NOMG if and only if no coalition with at most kk members can force an object into or out of the outcome (Theorem 6), which requires k<n/2k<n/2; among voting by quota, simple majority on each object gives the greatest protection (Corollary 2). For k=1k=1, these characterizations recover the corresponding results for individual obvious manipulation.

Related literature. Obvious manipulations were introduced by Troyan and Morrill [37], who show that a manipulation is obvious exactly when it can be recognized as profitable by a cognitively limited agent in the sense of Li [25], and who use the notion to classify non-strategy-proof mechanisms in school choice, auctions, and bilateral trade. In voting, Aziz and Lam [7] identify classes of rules that are obviously manipulable, and Arribillaga and Bonifacio [1] characterize the tops-only rules without obvious manipulations and apply the characterization to generalized median voter schemes and voting by committees; our results for coalitions of size one are theirs. Outside voting, non-obvious manipulability has been studied in cake-cutting ([30]), the allocation of indivisible goods ([32]), assignment problems (Troyan [36]), allotment and division problems ([2 b,c]), two-sided matching ([6]), and budget-feasible mechanism design ([17]).

Our paper is closely related to two contemporaneous contributions, Doi et al. [19] and Demoor et al. [18], which study the role of groups in non-obvious manipulability in Shapley–Scarf housing markets. These contributions and ours pursue a common research agenda through independently developed approaches. Both papers cite an earlier version of our project,3 and their connections with the present paper concern both the definition of group extensions and their implications for mechanism design.

The connection with Doi et al. [19] is particularly close: they independently introduce the same notion of obvious group manipulation studied here. They call the resulting property NOGM and show that, together with individual rationality and pair efficiency, it characterizes the top trading cycles mechanism. Their formulation uses Pareto-undominated best and worst outcomes; under our assumption of strict preferences over alternatives, the two formulations coincide (Remark 1). They also establish a characterization of obvious group manipulations in a general mechanism-design framework that, when specialized to our voting setting, implies our independently obtained Proposition 1 and also covers the case of two alternatives.

Demoor et al. [18] pursue a different extension. Agents are partitioned into exogenously given groups, and each agent knows the reports of the other members of her group but not those of outsiders. Deviations remain individual: groups determine the information available to a deviating agent, whereas in our framework they identify the agents who can coordinate their reports and evaluate a deviation jointly. Their approach therefore explores the informational role of groups, while ours studies coordinated manipulation.

A common motivation underlies these contemporaneous developments: individual non-obvious manipulability may impose only weak restrictions on mechanisms. Both papers start from this observation in housing markets. Its counterpart in voting, where many manipulable rules admit no obvious individual manipulation, motivates the present paper. The three contributions thus investigate complementary ways of incorporating groups into the analysis of obvious manipulations, through richer information or coordinated deviations, and examine the resulting restrictions in different economic environments.

On the universal domain, strategy-proofness and group strategy-proofness both reduce to dictatorship when there are at least three alternatives. On restricted domains they need not coincide, and Le Breton and Zaporozhets [23] and Barberà et al. [9] give conditions on the domain under which they do. The vulnerability of voting rules to coalitions has also been measured by the frequency of profiles at which some coalition can manipulate ([24]) and by the size of the coalitions needed to manipulate ([31, 35]). Kondratev and Nesterov [22] measure the smallest share of the voters that can guarantee the election of one of its most preferred candidates, or veto its least preferred ones, whatever the other voters do. Our thresholds answer a different question: the smallest size at which some coalition has an obvious manipulation somewhere on the domain.

Finally, manipulation under limited information about the other voters has been modeled by specifying the set of profiles that a manipulator considers possible. Conitzer et al. [14] ask whether some vote does at least as well as the truthful one at each such profile and strictly better at some profile, and Reijngoud and En driss [33] and Endriss et al. [20] study how voters respond to poll information and to other forms of partial information. Earlier, Moulin [27] and Barberà and Dutta [10] studied voters who evaluate their strategies by the worst outcomes that they can lead to. Here a coalition knows nothing about the outsiders’ votes, but it knows the range of each of its reports.

Organization. § 2 introduces the model and group strategy-proofness. § 3 defines obvious group manipulations and establishes their informational foundation. § 4 treats the case of two alternatives. § 5 develops the impossibility results for tops-only rules and rules satisfying the majority criterion, and then compares the coalition sizes needed for obvious manipulation. § 6 studies the exceptional case of four voters and three alternatives. § 7 applies the tops-only characterization to generalized median voter schemes and voting by committees. § 8 concludes. Appendix § 9 contains the proof of Theorem 4.

Preliminaries

Let N={1,…,n}N = \{1, \ldots, n\} be the set of voters and let A\mathcal{A} be the set of alternatives, with ∣A∣=m|\mathcal{A}| = m and n,m≥2n,m \ge2. Each voter ii has a preference PiP_i in the set P\mathcal{P} of all strict linear orders on A\mathcal{A}. We write xPiyx P_i y if ii prefers xx to yy, and t(Pi)t(P_i) for her most preferred alternative, her top. A profile is P=(Pi)i∈NP = (P_i)_{i\in N}. For a nonempty coalition C⊆NC \subseteq N, we write PC=(Pi)i∈CP_C = (P_i)_{i\in C}, P−C=PN∖CP_{-C} = P_{N\setminus C} and P=(PC,P−C)P = (P_C,P_{-C}); the voters in N∖CN \setminus C are the outsiders. A coalition is proper if it is nonempty and different from NN.

A voting rule f:PN→Af : \mathcal{P}^{N} \to\mathcal{A} selects an alternative at each profile. Throughout, rules are onto. A rule is efficient if there are no profile PP and alternative xx such that xPif(P)x P_i f(P) for every i∈Ni \in N. It is dictatorial if there is a voter dd such that f(P)=t(Pd)f(P) = t(P_d) for every PP.

Voter ii can manipulate ff at PP if some report Pi′P_i' gives f(Pi′,P−i)Pif(P)f(P_i',P_{-i}) P_i f(P). A rule is strategy-proof if no voter can manipulate it at any profile. The classical extension allows a coalition to choose its reports jointly. A report PC′∈PCP_C' \in\mathcal{P}^{C} is a group manipulation for CC at PP if

f(PC′,P−C)Pif(P)for every i∈C.f(P_C',P_{-C}) P_i f(P) \qquad\text{for every } i \in C.

Every member must gain, although some members may keep their truthful ballots: a coalition commits to a joint report, and a member’s commitment to her truthful ballot is part of that report. A rule is group strategy-proof if it admits no group manipulation.

Group strategy-proofness implies strategy-proofness. Whether strategy-proofness already protects against coalitions depends on the preference domain. On the domain of single-peaked preferences, for instance, strategy-proofness implies group strategy-proofness, and Le Breton and Zaporozhets [23] and Barberà et al. [9] give conditions on the domain under which the two requirements coincide. On the universal domain considered here, the Gibbard–Satterthwaite theorem leaves only dictatorships once there are at least three alternatives [21, 34], and every dictatorship is group strategy-proof: a coalition that changes the outcome must include the dictator, who already obtains her top.

For non-dictatorial rules, the question is then which opportunities to manipulate can be recognized. Troyan and Morrill [37] propose non-obvious manipulability: a voter must be unable to improve either her worst possible outcome or her best possible outcome by misreporting. We ask the corresponding question for a group. If its members know one another’s preferences but do not know how the outsiders will vote, when can they recognize a joint deviation from which all of them gain?

Obvious group manipulations

The option set of a report PCP_C of a nonempty coalition CC is the set of outcomes that remain possible once the coalition submits that report:

Of(PC)={f(PC,P−C):P−C∈PN\C}.O^{f}(P_C)=\{f(P_C,P_{-C}):P_{-C}\in\mathcal{P}^{N\backslash C}\}.

We write O(PC)O(P_C) when the rule is understood. For a single voter this is the usual option set Of(Pi)O^{f}(P_i); for the grand coalition it is the singleton {f(P)}\{f(P)\}. A report PCP_C vetoes xx if x∉O(PC)x\notin O(P_C), and it forces xx if O(PC)={x}O(P_C)=\{x\}; a coalition can veto (can force) xx if one of its reports does.

Compare the option sets of the truthful report and of a deviation. The deviation is recognizably profitable if it eliminates an outcome that all members rank below every outcome that is still possible, or if it makes attainable an outcome that all members rank above every outcome that is possible under truthful reporting.

Definition 1. Let C⊆NC\subseteq N be nonempty, let PC∈PCP_C\in\mathcal{P}^{C} be the true preferences of its members, let PC′∈PCP'_C\in\mathcal{P}^{C} be a report, and write T=O(PC)T=O(P_C) and F=O(PC′)F=O(P'_C). The report PC′P'_C is an obvious group manipulation for CC at PCP_C if at least one of the following holds:

(W) there is x∈Tx\in T such that yPixyP_i x for every y∈Fy\in F and every i∈Ci\in C;

(B) there is y∈Fy\in F such that yPixyP_i x for every x∈Tx\in T and every i∈Ci\in C.

A rule is not obviously manipulable by groups (NOMG) if no coalition has an obvious group manipulation, and obviously manipulable by groups (OMG) otherwise.

Condition (W) says that some outcome that the coalition may obtain by telling the truth is unanimously worse than anything it may obtain by misreporting; condition (B) says that some outcome that it may obtain by misreporting is unanimously better than anything it may obtain by telling the truth. The definition only uses the two option sets and the members’ preferences. As discussed in the Introduction, it coincides with the definition of Doi et al. [19], as clarified in the following remark.

Remark 1 (Two formulations). Doi et al. [19] state the definition differently. For a set of outcomes OO, let BC(O)B_C(O) be the set of elements of OO that are not Pareto dominated, for the members of CC, by another element of OO, and let WC(O)W_C(O) be the set of elements of OO that do not Pareto dominate another element of OO. In their definition, PC′P'_C is an obvious group manipulation at PCP_C if some element of BC(F)B_C(F) Pareto dominates every element of BC(T)B_C(T), or some element of WC(T)W_C(T) is Pareto dominated by every element of WC(F)W_C(F). Such a formulation is needed when members can be indifferent between distinct outcomes, as in allocation problems, where an agent only cares about her own assignment. Here preferences over outcomes are strict, so yy Pareto dominates x≠yx\ne y for CC if and only if yPixyP_i x for every i∈Ci\in C. This relation is transitive, and therefore every element of a finite set OO is equal to, or dominated by, an element of BC(O)B_C(O), and is equal to, or dominates, an element of WC(O)W_C(O). It follows that their two conditions are equivalent to (B) and (W), respectively. For instance, if y∈Fy\in F dominates every element of TT, then so does an element of BC(F)B_C(F) that is equal to or dominates yy; conversely, if y∈BC(F)y\in B_C(F) dominates every element of BC(T)B_C(T), then it dominates every element of TT, so that (B) holds with yy. The argument for (W) is symmetric. Hence NOMG is the property that Doi et al. [19] call NOGM, specialized to voting.

At the two extremes of coalition size the conditions take a familiar form. For a single voter they compare the worst and the best elements of the two option sets; for the grand coalition each report determines one outcome.4

Lemma 1. Let CC, PCP_C, PC′P'_C, TT and FF be as in Definition 1.

(i) If PC′P'_C is an obvious group manipulation for CC at PCP_C, then there is P−CP_{-C} such that PC′P'_C is a group manipulation for CC at (PC,P−C)(P_C,P_{-C}). Hence every group strategy-proof rule is NOMG.

(ii) For C={i}C=\{i\}, Pi′P'_i is an obvious group manipulation at PiP_i if and only if either the worst element of FF is preferred to the worst element of TT, or the best element of FF is preferred to the best element of TT, where worst and best refer to PiP_i. Thus the absence of obvious manipulations by single voters is non-obvious manipulability in the sense of Troyan and Morrill [37].

(iii) For C=NC=N, PN′P'_N is an obvious group manipulation at PP if and only if it is a group manipulation at PP. Consequently, the grand coalition has no obvious group manipulation if and only if the rule is efficient, and a rule is NOMG if and only if it is efficient and no proper coalition has an obvious group manipulation.

Proof. (i) If (W) holds with xx, choose P−CP_{-C} with f(PC,P−C)=xf(P_C,P_{-C})=x; then f(PC′,P−C)∈Ff(P'_C,P_{-C})\in F is strictly preferred to xx by every member. If (B) holds with yy, choose P−CP_{-C} with f(PC′,P−C)=yf(P'_C,P_{-C})=y; then f(PC,P−C)∈Tf(P_C,P_{-C})\in T is strictly worse than yy for every member.

(ii) If some x∈Tx\in T satisfies (W), then so does the worst element of TT. Hence (W) holds if and only if every element of FF, that is, the worst element of FF, is preferred to the worst element of TT. In the same way, (B) holds if and only if the best element of FF is preferred to the best element of TT.

(iii) For C=NC=N both option sets are singletons, and (W) and (B) both say that f(P′)Pif(P)f(P') P_i f(P) for every ii. If ff is not efficient, say xPif(P)x P_i f(P) for every ii, then since ff is onto there is P′P' with f(P′)=xf(P')=x, a group manipulation by NN. Conversely, a group manipulation by NN exhibits a violation of efficiency.

These properties connect the definition with individual non-obvious manipulability and group strategy-proofness. We next establish its informational foundation. In Troyan and Morrill [37], an agent who cannot reason contingently about the reports of others evaluates a report through the best and worst outcomes it may produce. Our coalition faces the same limitation with respect to outsiders, while its members know each other’s preferences and can commit to a joint report, as in the definition of group strategy-proofness. The comparison must therefore be decisive for the coalition as a whole: either a truthful outcome is unanimously worse than every possible outcome of the deviation, or an outcome of the deviation is unanimously better than every possible truthful outcome.

Knowing these option sets does not reveal how the outcomes of two reports are paired at the same outsider profile. To make this precise, say that rules ff and gg are CC-indistinguishable if Of(PC)=Og(PC)O^f(P_C)=O^g(P_C) for every PC∈PCP_C\in\mathcal{P}^C. Such rules have the same range, the union of the option sets of CC, so that gg is onto whenever ff is.

The next result shows that the definition captures exactly those deviations that the coalition can identify as group manipulations from this information alone: a misreport is an obvious group manipulation if and only if it remains a group manipulation under every CC-indistinguishable voting rule. It thus extends to coalitions the characterization of obvious manipulations in Troyan and Morrill [37].5

Proposition 1. Let m≥3m \ge3, let C⊆NC \subseteq N be nonempty and let PC,PC′∈PCP_C, P'_C \in\mathcal{P}^C. Then PC′P'_C is an obvious group manipulation for CC at PCP_C under ff if and only if, for every rule gg that is CC-indistinguishable from ff, there is an outsider profile Q−C∈PN\CQ_{-C} \in\mathcal{P}^{N\backslash C} such that

g(PC′,Q−C) Pi g(PC,Q−C)for every i∈C.g(P'_C,Q_{-C})\ P_i\ g(P_C,Q_{-C}) \qquad\text{for every } i \in C.

Proof. Write T=Of(PC)T = O^f(P_C) and F=Of(PC′)F = O^f(P'_C). If C=NC = N, the only NN-indistinguishable rule is ff itself and both statements say that every member prefers f(P′)f(P') to f(P)f(P) (Lemma 1). Assume C≠NC \ne N.

Only if. Let gg be CC-indistinguishable from ff. If (W) holds with x∈T=Og(PC)x \in T = O^g(P_C), choose Q−CQ_{-C} with g(PC,Q−C)=xg(P_C,Q_{-C}) = x; then g(PC′,Q−C)∈Fg(P'_C,Q_{-C}) \in F is unanimously preferred to xx. If (B) holds with y∈F=Og(PC′)y \in F = O^g(P'_C), choose Q−CQ_{-C} with g(PC′,Q−C)=yg(P'_C,Q_{-C}) = y; then g(PC,Q−C)∈Tg(P_C,Q_{-C}) \in T is unanimously worse than yy.

If. Suppose neither (W) nor (B) holds. If PC′=PCP'_C = P_C, take g=fg = f. Otherwise, call a pair (x,y)∈T×F(x,y) \in T \times F improving if yPixy P_i x for every i∈Ci \in C. Since (W) fails, for every x∈Tx \in T there is φ(x)∈F\varphi(x) \in F such that (x,φ(x))(x,\varphi(x)) is not improving; since (B) fails, for every y∈Fy \in F there is ψ(y)∈T\psi(y) \in T such that (ψ(y),y)(\psi(y),y) is not improving. Since m≥3m \ge3, the number of outsider profiles is (m!)∣N\C∣≥m!≥2m≥∣T∣+∣F∣(m!)^{|N\backslash C|} \ge m! \ge2m \ge|T| + |F|. Choose distinct outsider profiles QxQ^x (x∈T)(x \in T) and Q^y\widehat{Q}^y (y∈F)(y \in F), and define gg by

g(PC,Qx)=x,g(PC′,Qx)=φ(x),g(PC,Q^y)=ψ(y),g(PC′,Q^y)=y,g(P_C,Q^x) = x,\quad g(P'_C,Q^x) = \varphi(x),\quad g(P_C,\widehat{Q}^y) = \psi(y),\quad g(P'_C,\widehat{Q}^y) = y,

by g(PC,Q)=x0g(P_C,Q) = x_0 and g(PC′,Q)=φ(x0)g(P'_C,Q) = \varphi(x_0) at every remaining outsider profile QQ, for a fixed x0∈Tx_0 \in T, and by g=fg = f at all profiles at which CC reports neither PCP_C nor PC′P'_C. Then Og(PC)=TO^g(P_C) = T, Og(PC′)=FO^g(P'_C) = F, and all other option sets of CC are unchanged, so gg is CC-indistinguishable from ff. By construction, no outsider profile yields an improving pair. □

The outsider profile at which the coalition gains may depend on the rule, but for each rule the same profile must work for every member. Conversely, if a deviation is not obvious, some CC-indistinguishable rule makes it unprofitable for the coalition at every outsider profile. Option sets alone therefore suffice to identify exactly the obvious group manipulations.

Two alternatives

Let A={a,b}\mathcal{A} = \{a,b\}. A vote for aa represents the preference aPiba P_i b, and aCa^C denotes the report of coalition CC at which every member votes for aa. With two alternatives, a rule is efficient if and only if it selects aa whenever all voters vote for aa, for each a∈Aa \in\mathcal{A}.

Proposition 2. Let m=2m = 2 and let CC be a nonempty coalition. Then CC has no obvious group manipulation if and only if, for each alternative aa:

(i) if some report of CC forces aa, then aCa^{C} forces aa; and

(ii) a∈O(aC)a \in\mathrm{O}(a^{C}).

In particular, a rule is NOMG if and only if it is efficient and every proper coalition that can force an alternative can force it by voting unanimously for it.

Proof. If two members of CC disagree, neither outcome is strictly better than the other for every member, so neither (W) nor (B) can hold. Suppose that all members prefer aa to the other alternative, bb, write T=O(aC)T = \mathrm{O}(a^{C}), and let FF be the option set of a report of CC. Condition (W) holds if and only if b∈Tb \in T and F={a}F = \{a\}; ruling this out for every report gives (i). Condition (B) holds if and only if T={b}T = \{b\} and a∈Fa \in F. Since the rule is onto, some report of CC leaves aa open, so ruling (B) out for every report gives (ii). For the last statement, NOMG implies efficiency by Lemma 1(iii). Conversely, let the rule be efficient. Letting all outsiders vote for aa shows that (ii) holds for every coalition, and (i) holds for C=NC = N because aNa^{N} forces aa. Hence the rule is NOMG if and only if (i) holds for every proper coalition.

Condition (i) says that the power to force an alternative never requires a coalition to split its votes. It is much weaker than strategy-proofness.

Example 1 (Parity rules). Let A={x,y}\mathcal{A} = \{x,y\}, let n≥3n \ge3 be odd, and let ff select yy if and only if an odd number of voters vote for yy. For every proper coalition CC and every report of CC, a single outsider can change the parity, so every option set of CC is A\mathcal{A} and CC forces nothing. Since nn is odd, ff selects yy when all voters vote for yy and xx when all voters vote for xx, so ff is efficient. By Proposition 2, ff is NOMG. It is not strategy-proof: if voter ii, who prefers yy, and exactly one other voter vote for yy, the outcome is xx, and if ii switches to xx the outcome becomes yy.

Conversely, efficiency alone leaves open the possibility that a coalition can force its preferred alternative only by splitting its votes.

Example 2 (Efficiency is not enough). Let n=3n = 3 and A={x,y}\mathcal{A} = \{x,y\}, and let ff select yy if voter 1 votes for yy and voter 2 votes for xx, and the alternative for which voter 3 votes otherwise. This rule is efficient. The coalition C={1,2}C = \{1,2\} forces yy with the report at which voter 1 votes for yy and voter 2 votes for xx, but O(yC)=A\mathrm{O}(y^{C}) = \mathcal{A} because voter 3 decides, so (i) fails. Concretely, let voters 1 and 2 prefer yy. If voter 2 switches to xx while voter 1 keeps her vote, the outcome is yy whatever voter 3 does. Since xx belongs to the truthful option set and both members prefer yy, the only element of the deviating option set, this is an obvious group manipulation of type (W).

Impossibility results and coalition size

We study two overlapping classes of voting rules. Tops-onliness restricts the information used to choose an outcome, whereas the majority criterion guarantees that a strict majority can impose its common top alternative. Thus, the two classes capture distinct aspects of collective choice rather than partitioning the set of voting rules. We first establish the restrictions that NOMG imposes within each class and then compare the coalition sizes responsible for them. Throughout, preferences range over the universal domain.

Tops-only rules

The characterization below holds for every m≥2m \ge2. For the equivalence with group strategy-proofness and the dictatorship result, we assume m≥3m \ge3.

A rule is tops-only if f(P)=f(P′)f(P) = f(P') whenever t(Pi)=t(Pi′)t(P_i) = t(P'_i) for every i∈Ni \in N. Tops-only rules include plurality, generalized median voter schemes and voting by committees; on many domains, strategy-proofness and unanimity imply tops-onliness [13]. For a tops-only rule we use the same symbol for the induced map f:AN→Af : A^N \to A; thus f(t)f(t) is the outcome when the vector of reported tops is t=(t1,…,tn)t = (t_1, \ldots, t_n), and O(rC)O(r_C) is the option set of a vector of tops rC∈ACr_C \in A^C. For tC∈ACt_C \in A^C let τ(tC)={ti:i∈C}\tau(t_C) = \{t_i : i \in C\} be the set of reported tops, for x∈Ax \in A let Sx(t)={i∈N:ti=x}S_x(t) = \{i \in N : t_i = x\} be the xx-support of tt, and let xCx^C denote the report of CC at which every member reports xx. A tops-only rule is efficient if and only if f(t)∈τ(t)f(t) \in\tau(t) for every tt: if the outcome is a reported top it cannot be Pareto dominated, and if f(t)f(t) is not a reported top, there are preferences with the reported tops at which every voter ranks some reported top zz above f(t)f(t).

For a tops-only rule, the option sets of a coalition depend only on the tops that it reports, while the lower ranks of its members’ true preferences are free. We can therefore test whether a coalition has an obvious group manipulation using only reported tops and option sets.

Lemma 2. Let ff be tops-only and let C⊆NC \subseteq N be nonempty. The coalition CC has an obvious group manipulation, for some true preferences of its members, if and only if there are tC,rC∈ACt_C,r_C \in A^C such that

(W′) some x∈O(tC)∖O(rC)x \in O(t_C) \setminus O(r_C) satisfies x∉τ(tC)x \notin\tau(t_C); or

(B′) O(tC)∩τ(tC)=∅O(t_C) \cap\tau(t_C) = \varnothing and O(rC)⊈O(tC)O(r_C) \not\subseteq O(t_C).

Proof. Let tCt_C be the tops of the true preferences, rCr_C the tops of the report, T=O(tC)T = O(t_C) and F=O(rC)F = O(r_C). If (W) holds with xx, then x∉Fx \notin F, and xx is not a member’s top because every member ranks the elements of FF above it; this is (W′). Conversely, given (W′), let every member rank her top first and xx last; then every element of FF is above xx for every member. If (B) holds with yy, then y∉Ty \notin T, and no member’s top is in TT, since otherwise yy would have to be ranked above that member’s top; this is (B′). Conversely, given (B′) and y∈F∖Ty \in F \setminus T, let every member rank her top first, yy next (if it is different from her top), and the elements of TT below; since no top lies in TT, (B) holds.

Definition 2. Let ff be tops-only. A nonempty coalition CC satisfies the conditional veto if, whenever some report of CC vetoes an alternative xx, every report tCt_C with x∉τ(tC)x \notin\tau(t_C) vetoes xx.

The conditional veto is exactly what prevents (W′). To prevent (B′), a report must leave open at least one of the tops that it contains.

Theorem 1. Let ff be tops-only and let CC be a nonempty coalition. Then CC has no obvious group manipulation if and only if

(i) CC satisfies the conditional veto; and

(ii) every report of CC leaves open the top of at least one of its members: O(tC)∩τ(tC)≠∅O(t_C) \cap\tau(t_C) \ne\varnothing for every tC∈ACt_C \in A^C.

If ff is efficient, then (ii) holds for every coalition and (i) holds for the grand coalition. Hence an efficient tops-only rule is NOMG if and only if every proper coalition satisfies the conditional veto.

Proof. By Lemma 2, CC has no obvious group manipulation if and only if (W′) and (B′) fail for all tC,rCt_C,r_C. The failure of (W′) for all tC,rCt_C,r_C is the conditional veto. For (B′), note that the union of the option sets of CC is AA, because ff is onto. If O(tC)O(t_C) contains none of the tops in tCt_C, choose y∈τ(tC)y \in\tau(t_C) and a report rCr_C with y∈O(rC)y \in O(r_C); then y∉O(tC)y \notin O(t_C), so (B′) holds. Conversely, if (ii) holds, then (B′) fails for every pair of reports.

Let ff be efficient, so that f(t)∈τ(t)f(t) \in\tau(t) for every tt. For a proper coalition CC and a report tCt_C, let the outsiders report the top of some member of CC; the outcome lies in τ(tC)\tau(t_C), so (ii) holds. For C=NC=N, O(t)={f(t)}⊆τ(t)O(t)=\{f(t)\}\subseteq\tau(t), so (ii) holds and no alternative outside τ(t)\tau(t) is left open, which gives (i). The last statement follows from Lemma 1(iii).

For a single voter, (i) implies (ii). Indeed, if reporting xx vetoed xx, then by the conditional veto every report of that voter would veto xx, which contradicts ontoness. For C={i}C=\{i\}, Theorem 1 is therefore the characterization of Arribillaga and Bonifacio [1]: a tops-only rule has no obvious individual manipulation if and only if, whenever a voter can veto an alternative, she vetoes it with every preference that does not have that alternative on top.

Applying the characterization to all coalitions has a strong implication. If a tops-only rule protects every coalition, then the voters who support the winner at any given profile include a group that can secure that outcome by itself.

Theorem 2. Let m≥3m \ge3 and let ff be an onto tops-only rule. The following are equivalent:

(i) ff is NOMG;

(ii) ff is efficient and every proper coalition satisfies the conditional veto;

(iii) ff is group strategy-proof;

(iv) ff is dictatorial.

Proof. (i)⟺\Longleftrightarrow(ii). NOMG implies efficiency by Lemma 1(iii), and for efficient rules the equivalence is the last statement of Theorem 1.

(ii)⟹\Longrightarrow(iii). We proceed in four steps.

Step 1: winning supports contain kernels. Let f(t)=af(t)=a. Among the profiles of tops at which aa is selected and whose aa-support is contained in Sa(t)S_a(t), choose one, t∗t^*, whose aa-support KK is minimal with respect to inclusion; KK is nonempty by efficiency. We claim that

f(aK,r−K)=afor every r−K with a∉τ(r−K).(1)f(a^K,r_{-K})=a \qquad\text{for every }r_{-K}\text{ with }a\notin\tau(r_{-K}). \tag*{(1)}

If K=NK=N, the claim is that aa is selected when all voters report aa, which holds by efficiency. Otherwise, C=N∖KC=N\setminus K is a proper coalition whose report at t∗t^* avoids aa and leaves aa open. By the conditional veto, no report of CC vetoes aa. Let rCr_C avoid aa and choose rKr_K such that f(rK,rC)=af(r_K,r_C)=a. The aa-support of (rK,rC)(r_K,r_C) is contained in K⊆Sa(t)K\subseteq S_a(t), so by minimality it equals KK; that is, rK=aKr_K=a^K.

Step 2: winning supports of different alternatives intersect. Let f(t)=xf(t)=x and f(t′)=zf(t')=z with x≠zx\ne z, and suppose that Sx(t)S_x(t) and Sz(t′)S_z(t') are disjoint. Let K⊆Sx(t)K\subseteq S_x(t) and L⊆Sz(t′)L\subseteq S_z(t') be given by Step 1, and choose c∈A∖{x,z}c\in A\setminus\{x,z\}, which is possible because m≥3m\ge3. Consider the profile at which the members of KK report xx, the members of LL report zz, and every other voter reports cc. The voters outside KK avoid xx, so the outcome is xx by (1); the voters outside LL avoid zz, so the outcome is zz; a contradiction. Step 3: kernels force their alternative. Let f(t)=af(\mathbf{t})=a and let KK be given by Step 1. We claim that f(aK,r−K)=af(a^{K},\mathbf{r}_{-K})=a for every r−K\mathbf{r}_{-K}. If K=NK=N there is nothing to prove. Otherwise, suppose that z=f(aK,r−K)≠a\mathbf{z}=f(a^{K},\mathbf{r}_{-K})\ne a for some r−K\mathbf{r}_{-K}. The zz-support of (aK,r−K)(a^{K},\mathbf{r}_{-K}) is contained in N∖KN\setminus K, whereas for any r−K′\mathbf{r}'_{-K} that avoids aa, the alternative aa is selected at (aK,r−K′)(a^{K},\mathbf{r}'_{-K}) with aa-support KK. This contradicts Step 2.

Step 4. Suppose that a coalition CC has a group manipulation at a profile with tops t\mathbf{t}, which changes the outcome from a=f(t)a=f(\mathbf{t}) to some yy. Every member strictly prefers yy to aa, so no member has top aa; that is, C∩Sa(t)=∅C\cap S_a(\mathbf{t})=\varnothing. Let K⊆Sa(t)K\subseteq S_a(\mathbf{t}) be given by Step 1. The members of KK keep reporting aa after the deviation, so by Step 3 the outcome is still aa, a contradiction.

(iii)⟹\Longrightarrow(iv). A group strategy-proof rule is strategy-proof. Since ff is onto and m≥3m\ge3, the Gibbard–Satterthwaite theorem implies that ff is dictatorial.

(iv)⟹\Longrightarrow(i). A dictatorial rule is group strategy-proof, and group strategy-proof rules are NOMG by Lemma 1(i). □

Theorem 2 says that, for tops-only rules, restricting coalitions to the deviations that they can recognize from option sets does not enlarge the set of admissible rules beyond the group strategy-proof ones. The third alternative is essential: with two alternatives every rule is tops-only, and the parity rules of Example 1 (in § 4) are NOMG but not strategy-proof. The contrast with the individual case is also sharp. Fix a status quo s∈As\in\mathcal{A} and let f(t)=af(\mathbf{t})=a if every voter reports aa, and f(t)=sf(\mathbf{t})=s otherwise. This rule is onto, tops-only and non-dictatorial. A voter who reports aa has option set {a,s}\{a,s\}, which contains her reported top. She can veto every alternative other than ss, and every report that does not have such an alternative on top vetoes it. By Theorem 1, the rule has no obvious individual manipulation. It is OMG because it is not efficient (Lemma 1(iii)).

Rules satisfying the majority criterion

We now allow voting rules to depend on the entire rankings. The next impossibility follows from the majority criterion and therefore applies, in particular, to Condorcet-consistent rules.

A rule satisfies the majority criterion if it selects xx whenever more than n/2n/2 voters rank xx first; a coalition with more than n/2n/2 members can then force any alternative by ranking it first, even under a rule that uses the entire rankings. A rule is Condorcet consistent if it selects the Condorcet winner whenever one exists; an alternative ranked first by more than n/2n/2 voters is a Condorcet winner, so Condorcet consistency implies the majority criterion. Dasgupta and Maskin [15, 16] single out majority rules by its performance on restricted domains; in the second paper the axioms include a strategy-proofness requirement that covers manipulations by coalitions. On the universal domain, the majority criterion alone creates obvious group manipulations: if the members of a majority all prefer some alternative to the alternative that is selected, the selected alternative itself is a witness for condition (W).

The construction below is related to the argument of Nakamura [29] for the emptiness of the core of a simple game with ordinal preferences. A cycle suffices if each alternative in the cycle can be replaced by a coalition that prefers, and can force, another alternative.

Proposition 3. Let m≥3m\ge3, let a,b,ca,b,c be distinct alternatives, and suppose that NN can be partitioned into nonempty sets C1,C2,C3C_1,C_2,C_3 such that every union of two of them can force each of a,ba,b and cc. Then ff is OMG.

Proof. Consider the profile PP at which the members of C1C_1, C2C_2 and C3C_3 rank a,b,ca,b,c in the orders abcabc, bcabca and cabcab, respectively, and all other alternatives below these three in a common order. Let v=f(P)v=f(P). If v∉{a,b,c}v\notin\{a,b,c\}, every voter ranks aa above vv, and C1∪C2C_1\cup C_2 can force aa while v∈O(PC1∪C2)v\in O(P_{C_1\cup C_2}), so (W) holds with vv. If v=av=a, every member of C2∪C3C_2\cup C_3 ranks cc above aa; if v=bv=b, every member of C1∪C3C_1\cup C_3 ranks aa above bb; if v=cv=c, every member of C1∪C2C_1\cup C_2 ranks bb above cc. In each case that union can force the alternative that it prefers, and (W) holds with vv.

Theorem 3. Let n,m≥3n,m\ge3 with (n,m)≠(4,3)(n,m)\ne(4,3). Every rule satisfying the majority criterion is OMG. In particular, every Condorcet-consistent rule is OMG.

Proof. If n≠4n\ne4, partition NN into three nonempty sets of sizes as equal as possible; each has fewer than n/2n/2 members (this fails only for n=4n=4), so the union of any two has more than n/2n/2 members and Proposition 3 applies. If n=4n=4, then m≥4m\ge4; consider the profile

abcd,bcda,cdab,dabc,\begin{array}{cccc} abcd, & bcda, & cdab, & dabc, \end{array}

with all other alternatives below these four in a common order. Each v∈{a,b,c,d}v\in\{a,b,c,d\} is ranked below its cyclic predecessor by three voters, and any alternative outside {a,b,c,d}\{a,b,c,d\} is ranked below aa by all four. Three voters can force the alternative that they prefer by ranking it first, so (W) holds with the alternative vv selected at this profile.

Thresholds on the number of alternatives also appear in other impossibility results for Condorcet-consistent rules: Moulin [28] shows that every such rule generates the no-show paradox when there are four or more alternatives. Here the only exception is a single electorate.

How large must coalitions be?

The preceding results impose two restrictions on full immunity: tops-only rules must be dictatorial when m≥3m\ge3, while rules satisfying the majority criterion cannot be NOMG when n,m≥3n,m\ge3 and (n,m)≠(4,3)(n,m)\ne(4,3). We now ask how large a coalition must be before an obvious manipulation becomes possible. This question applies to both classes. For k∈{1,…,n}k\in\{1,\ldots,n\}, a rule is kk-NOMG if no coalition with at most kk members has an obvious group manipulation. Let K(f)K(f) denote the largest such kk, with K(f)=0K(f)=0 if some single voter has an obvious manipulation. Thus K(f)=nK(f)=n if and only if ff is NOMG, and otherwise K(f)+1K(f)+1 is the size of the smallest coalitions that can manipulate obviously. By Theorem 1, an efficient tops-only rule is kk-NOMG if and only if every proper coalition with at most kk members satisfies the conditional veto.

By Lemma 1(iii), the grand coalition enters NOMG only through efficiency, so for an efficient tops-only rule immunity to coalitions of up to n−1n-1 voters already implies dictatorship. The next proposition shows that neither efficiency nor the coalitions with n−1n-1 members can be dispensed with. For n≥3n\ge3 and d∈Nd\in N, the override rule fdf^d selects yy if at least n−1n-1 voters report yy, and selects tdt_d otherwise. Since n−1>n/2n-1>n/2, at most one alternative is reported by n−1n-1 voters, so fdf^d is well defined: voter dd decides unless all other voters agree on a different alternative. Now assign the values 0,…,m−10,\ldots,m-1 to the mm different tops. The cyclic rule selects ∑i∈Nti\sum_{i\in N}t_i modulo mm.

Proposition 4. Let m≥3m\ge3.

  1. Every efficient, tops-only, (n−1)(n-1)-NOMG rule is dictatorial.

(ii) For every n≥3n \ge3 and d∈Nd \in N, the override rule fdf^d is efficient, tops-only, non-dictatorial and (n−2)(n-2)-NOMG.

(iii) For every n≥2n \ge2, the cyclic rule is tops-only, non-dictatorial and (n−1)(n-1)-NOMG.

Consequently, for efficient tops-only rules, kk-NOMG implies dictatorship if and only if k≥n−1k \ge n-1, and for tops-only rules in general if and only if k=nk=n.

Proof. (i) By Lemma 1(iii) the rule is NOMG; apply Theorem 2.

(ii) The outcome is always a reported top, so fdf^d is efficient. It is not dictatorial. Voter dd is not a dictator: if all voters other than dd report y≠tdy \ne t_d, the outcome is yy. A voter j≠dj \ne d is not a dictator either: fix an alternative aa and a voter l∈{d,j}l \in\{d,j\}, let jj and ll report two different alternatives other than aa, and let all other voters report aa; no alternative is reported by n−1n-1 voters, so the outcome is td=a≠tjt_d=a \ne t_j. By Theorem 1, it remains to check the conditional veto for every coalition CC with c=∣C∣≤n−2c=|C| \le n-2 members. There are n−c≥2n-c \ge2 outsiders. For rC∈ACr_C \in A^C and y∈Ay \in A, let #rC(y)\#_{r_C}(y) be the number of members of CC who report yy.

If d∉Cd \notin C, let all outsiders, among them dd, report xx. Every y≠xy \ne x is reported by at most c≤n−2c \le n-2 voters, so the outcome is xx. Hence O(rC)=AO(r_C)=A for every rCr_C, and CC vetoes nothing.

If d∈Cd \in C and dd reports aa, then

O(rC)={a}∪{y≠a:#rC(y)≥c−1}.O(r_C)=\{a\}\cup\{y\ne a:\#_{r_C}(y)\ge c-1\}.

Indeed, if all outsiders report aa, no y≠ay \ne a is reported by more than c−1≤n−3c-1 \le n-3 voters, so the outcome is aa; and y≠ay \ne a can be selected only if it is reported by n−1n-1 voters, which the outsiders can achieve if and only if #rC(y)+(n−c)≥n−1\#_{r_C}(y)+(n-c)\ge n-1. If c=1c=1, then O(rC)=AO(r_C)=A for every report and CC vetoes nothing. If c≥2c\ge2 and x∉τ(tC)x\notin\tau(t_C), then x≠tdx\ne t_d and #tC(x)=0<c−1\#_{t_C}(x)=0<c-1, so tCt_C vetoes xx. In both cases the conditional veto holds.

(iii) The rule is onto and tops-only. It is not dictatorial: for every voter ii, if some other voter reports 11 and all remaining voters report 00, the outcome is ti+1t_i+1 modulo mm, which differs from tit_i. If CC is a proper coalition and j∉Cj\notin C, then for every report of the other voters, jj can choose tjt_j so that the sum takes any prescribed value modulo mm. Hence every option set of CC equals AA, so CC satisfies both conditions of Theorem 1.

For the last statement, combine (i)–(iii) with the fact that kk-NOMG implies k′k'-NOMG for k′≤kk'\le k, and with Theorem 2 for k=nk=n.

The override rule shows where the proof of Theorem 2 needs large coalitions. Let the members of C=N∖{d}C=N\setminus\{d\} have true tops split between two alternatives bb and b′b', and let a∉{b,b′}a\notin\{b,b'\}. Truthful reporting leaves aa open, because voter dd may report aa, whereas the report bCb^C forces bb; if all members rank aa last, this is an obvious group manipulation of type (W). Thus K(fd)=n−2K(f^d)=n-2. The cyclic rule has K(f)=n−1K(f)=n-1; by part (i), it is not efficient.

For rules satisfying the majority criterion, the relevant threshold is instead determined by majority size. Coalitions with fewer than half of the voters cannot restrict their option sets, since the outsiders can force any alternative. Conversely, the profiles used in Theorem 3 allow a minimal strict majority to manipulate obviously.

Proposition 5. Let n,m≥3n,m\ge3 with (n,m)≠(4,3)(n,m)\ne(4,3), and let ff satisfy the majority criterion. Then no coalition with fewer than n/2n/2 members has an obvious group manipulation, and some coalition with exactly ⌊n/2⌋+1\lfloor n/2\rfloor+1 members has an obvious group manipulation of type (W). Consequently,

K(f)=n−12if n is odd,n2−1≤K(f)≤n2if n is even.K(f)=\frac{n-1}{2}\quad\text{if }n\text{ is odd},\qquad\frac{n}{2}-1\le K(f)\le\frac{n}{2}\quad\text{if }n\text{ is even}.

In particular, these conclusions hold for every Condorcet-consistent rule.

Proof. Let CC satisfy ∣C∣<n/2|C| < n/2. For every report PCP_C and every x∈Ax \in\mathcal{A}, the outsiders can rank xx first. Since they form a strict majority, the outcome is xx. Thus Of(PC)=AO^f(P_C) = \mathcal{A} for every report, which rules out both (W) and (B).

For the upper bound, write q=⌊n/2⌋+1q = \lfloor n/2 \rfloor+ 1. The construction in the proof of Theorem 3 provides a profile PP, an alternative yy, and a strict majority DD such that yPif(P)y P_i f(P) for every i∈Di \in D. Indeed, when n≠4n \ne4, use the three blocks in that proof: if the selected alternative belongs to the cycle, the union of the two blocks that prefer its cyclic predecessor is such a majority; if it lies outside the cycle, all voters prefer aa to it. When n=4n = 4 and m≥4m \ge4, the four-cycle construction gives three voters who prefer the predecessor of the selected alternative, or all four voters prefer aa if the outcome lies outside the cycle.

Choose C⊆DC \subseteq D with ∣C∣=q|C| = q and let PC′P'_C be any report at which every member ranks yy first. The original outsider profile gives f(P)∈Of(PC)f(P) \in O^f(P_C), whereas the majority criterion gives Of(PC′)={y}O^f(P'_C) = \{y\}. Since every member of CC strictly prefers yy to f(P)f(P), condition (W) holds. The bounds on K(f)K(f) follow, and coincide when nn is odd. Condorcet consistency implies the majority criterion, so the same conclusions apply. □

For odd electorates, all rules satisfying the majority criterion therefore have exactly the same protection threshold, regardless of how they use the lower ranks. For even electorates, the only unresolved size is n/2n/2: the proposition does not determine whether coalitions of that size can manipulate a given rule. The exception (n,m)=(4,3)(n,m) = (4,3) is essential, as the next section shows by exhibiting Condorcet-consistent Borda with K(f)=nK(f) = n.

Plurality belongs to both classes considered here: it is tops-only and satisfies the majority criterion. Its exact threshold provides a useful comparison with the preceding bounds.

Under plurality, what matters is how the size of the coalition compares with the number of outsiders. Let fpf^p select, among the alternatives reported as top by the largest number of voters, the highest one in a fixed strict priority ▹\triangleright over A\mathcal{A}.

Proposition 6. Let m≥3m \ge3. Plurality is kk-NOMG if and only if k<n/2k < n/2; that is, K(fp)=⌈n/2⌉−1K(f^p) = \lceil n/2 \rceil- 1. Coalitions of fewer than half of the voters have no obvious group manipulation, and some coalition with ⌈n/2⌉\lceil n/2 \rceil members has one.

Proof. Plurality is tops-only and efficient. Label the alternatives so that a1▹a2▹a3▹⋯a_1 \triangleright a_2 \triangleright a_3 \triangleright\cdots.

If ∣C∣=c<n/2|C| = c < n/2, the outsiders outnumber the members of CC; if they all report xx, then xx has more reports than any other alternative and wins. Hence every option set of CC is A\mathcal{A}, CC vetoes nothing, and by Theorem 1 it has no obvious group manipulation.

Let c=⌈n/2⌉c = \lceil n/2 \rceil, which is at most n−1n - 1 because n≥2n \ge2, and let CC be a coalition with cc members. We exhibit a violation of the conditional veto.

If nn is even, c=n/2c = n/2 equals the number of outsiders. Let every member report a3a_3. If all outsiders report a2a_2, then a2a_2 and a3a_3 tie with cc reports each and a2a_2 wins, so a2∈O(a3C)a_2 \in O(a_3^C). If instead every member reports a1a_1, then a1a_1 has cc reports and no other alternative has more, so a1a_1 wins every tie: O(a1C)={a1}O(a_1^C) = \{a_1\}, which vetoes a2a_2 although a2∉τ(a3C)a_2 \notin\tau(a_3^C).

If nn is odd, c=(n+1)/2≥2c = (n+1)/2 \ge2 and there are c−1c-1 outsiders. Let ⌈c/2⌉\lceil c/2 \rceil members report a2a_2 and ⌊c/2⌋\lfloor c/2 \rfloor members report a3a_3. If all outsiders report a1a_1, then a1a_1 has c−1≥⌈c/2⌉c-1 \ge\lceil c/2 \rceil reports and wins every tie, so a1a_1 belongs to the option set of this report, although no member reports it. If every member reports a2a_2, then a2a_2 has cc reports, more than any other alternative can obtain, so the option set is {a2}\{a_2\}, which vetoes a1a_1. □ Plurality and the override rule show how differently rules can behave in the same electorate. Plurality loses its protection as soon as a coalition can match the outsiders’ voting strength, whereas the override rule, which concentrates power in one voter, protects against every coalition that leaves at least two voters outside.

A possibility result beyond tops-only rules

The exception in Theorem 3 and Proposition 5 admits rules that are immune to obvious manipulations by every coalition. With four voters and three alternatives, the partition into three blocks leaves one pair of blocks without a strict majority, and there is no fourth alternative for the longer cycle. Now we show that an entire family of scoring rules (Young, [38]) satisfying the majority criterion is NOMG. A scoring rule with vector s=(s1,s2,s3)s=(s_1,s_2,s_3), where s1≥s2≥s3s_1 \ge s_2 \ge s_3 and s1>s3s_1 > s_3, awards sjs_j points to an alternative for each voter who ranks it in position jj, and selects, among the alternatives with the highest total score, the highest one in a fixed strict priority ▹\triangleright. Since a positive affine transformation of ss does not change the rule, we normalize s=(1,t,0)s=(1,t,0) with t∈[0,1]t \in[0,1]; plurality is t=0t=0 and Borda’s rule is t=12t=\frac{1}{2}. These rules are onto, even for t=1t=1: to elect xx, let all voters rank it first and split their second positions equally between the other two alternatives. The result below holds for every priority.

Theorem 4. Let n=4n=4 and m=3m=3. The scoring rule with vector (1,t,0)(1,t,0) is NOMG if and only if 12≤t<23\frac{1}{2} \le t < \frac{2}{3}, that is, if and only if 2s2≥s1+s32s_2 \ge s_1+s_3 and 3s2<2s1+s33s_2 < 2s_1+s_3.

The proof is in Appendix § 9. For t<12t < \frac{1}{2}, two voters with a common bottom alternative can remove it from their option set by agreeing on their top; for 23≤t<1\frac{2}{3} \le t < 1, three voters with a common preference can remove their second-ranked alternative by having one of them demote it; and for t=1t=1 the rule is not efficient. Every rule in the interval satisfies the majority criterion: if three voters rank xx first, xx gets at least 3 points and every other alternative at most 3t+1<33t+1<3. Hence the exception in Theorem 3 cannot be removed.

Corollary 1. With four voters and three alternatives, Borda’s rule is Condorcet consistent and NOMG.

Proof. Borda’s rule is NOMG by Theorem 4 with t=12t=\frac{1}{2}. For Condorcet consistency, use the equivalent vector (2,1,0)(2,1,0): the score of an alternative is the sum, over the other two alternatives, of the numbers of voters who prefer it to that alternative. A Condorcet winner is preferred to each other alternative by at least three voters, so its score is at least 6. Any other alternative is preferred to the Condorcet winner by at most one voter and to the third alternative by at most four, so its score is at most 5. □

Applications of the tops-only characterization

Having established the general coalition-size bounds and the exceptional possibility result, we now return to the tops-only characterization in Theorem 1 to determine the protection against smaller coalitions offered by two familiar families: generalized median voter schemes and voting by committees. These rules are strategy-proof on their respective restricted domains (see Barberà, [8], for a survey). Here we evaluate them on the universal domain and ask how large a coalition must be to manipulate them obviously, and how a rule should be chosen to protect against coalitions up to a given size. Although only their dictatorial members are NOMG by Theorem 2, the characterization allows us to determine exactly which non-dictatorial members are protected against coalitions of a given size. Option sets are always computed on the universal domain P\mathcal{P}; the restricted domains only motivate the classes.

Median and generalized median voter schemes

Let A={a,a+1,…,b}\mathcal{A} = \{a, a+1,\ldots,b\} be a set of consecutive integers, so that b=a+m−1b = a + m - 1, and let m≥3m \ge3. For x,y∈Ax,y \in\mathcal{A} write [x,y]={z∈A:x≤z≤y}[x,y] = \{z \in\mathcal{A}: x \le z \le y\}. Given n−1n-1 fixed ballots α1≤⋯≤αn−1\alpha_1 \le\cdots\le\alpha_{n-1} in A\mathcal{A}, the median voter scheme fαf^{\alpha} selects the median of the fixed ballots and the nn reported tops,

fα(t)=med⁡{t1,…,tn,α1,…,αn−1},f^{\alpha}(\mathbf{t}) = \operatorname{med}\{t_1,\ldots,t_n,\alpha_1,\ldots,\alpha_{n-1}\},

and we set α0=a\alpha_0 = a and αn=b\alpha_n = b. For odd nn, placing half of the fixed ballots at each extreme alternative gives the median of the voters’ tops.

The option sets of a median voter scheme are obtained by counting. Fix a proper coalition CC with cc members and a report tC\mathbf{t}_C, pool the cc reported tops with the n−1n-1 fixed ballots, and order this list as z1≤⋯≤zn+c−1z_1 \le\cdots\le z_{n+c-1}. Then

O(tC)=[zc,zn].(2)O(\mathbf{t}_C) = [z_c,z_n]. \tag*{(2)}

Indeed, the outcome is the nnth smallest of 2n−12n-1 numbers; it equals zcz_c if all outsiders report aa and znz_n if all outsiders report bb, and it is nondecreasing in the outsiders’ reports. If all outsiders report an alternative x∈[zc,zn]x \in[z_c,z_n], then at least nn of the 2n−12n-1 numbers are at most xx and at least nn of them are at least xx, so the outcome is xx. In particular, if rr members report bb and the other s=c−rs = c-r members report aa, then

O(tC)=[αr,αn−s],(3)O(\mathbf{t}_C) = [\alpha_r,\alpha_{n-s}], \tag*{(3)}

because the pooled list consists of ss copies of aa, the fixed ballots, and rr copies of bb.

Proposition 7. Let m≥3m \ge3 and let fαf^{\alpha} be a median voter scheme. Let LL be the number of fixed ballots that are at most a+1a+1, let HH be the number of fixed ballots that are at least b−1b-1, and let EE be the number of fixed ballots that belong to {a,b}\{a,b\}. Then

K(fα)=min⁡{L,H,E+1}.\mathrm{K}(f^{\alpha}) = \min\{L,H,E+1\}.

Equivalently, for k∈{1,…,n−1}k \in\{1,\ldots,n-1\}, fαf^{\alpha} is kk-NOMG if and only if αk≤a+1\alpha_k \le a+1, αn−k≥b−1\alpha_{n-k} \ge b-1, and at least k−1k-1 fixed ballots belong to {a,b}\{a,b\}. Moreover, for k≥1k \ge1 there is a median voter scheme with K(fα)=k\mathrm{K}(f^{\alpha}) = k if and only if k<n/2k < n/2 when m≥4m \ge4, and if and only if k<2n/3k < 2n/3 when m=3m=3.

Proof. A median voter scheme is anonymous and onto, hence not dictatorial, so K(fα)≤n−1\mathrm{K}(f^{\alpha}) \le n-1 by Theorem 2. Let qaq_a and qbq_b be the numbers of fixed ballots equal to aa and to bb, so that E=qa+qbE = q_a + q_b, and let CC be a coalition with c≤n−1c \le n-1 members. By Theorem 1, CC has no obvious group manipulation if and only if it satisfies the conditional veto and every report of CC leaves open one of its tops.

Step 1: if c≤min⁡{L,H}c \le\min\{L,H\}, then CC satisfies the conditional veto. By (2), the lower endpoint of an option set is largest at the report bC\mathbf{b}^C, where it equals αc≤a+1\alpha_c \le a+1 by (3), and the upper endpoint is smallest at the report aC\mathbf{a}^C, where it equals αn−c≥b−1\alpha_{n-c} \ge b-1. Hence every option set of CC contains [a+1,b−1][a+1,b-1], and only aa and bb can be vetoed. By (2), aa belongs to an option set if and only if the pooled list contains at least cc copies of aa. Thus, if CC can veto aa, then qa<cq_a < c, and every report in which no member reports aa vetoes aa. The argument for bb is the same, counting from the other end of the list.

Step 2: if c=min⁡{L,H}+1c = \min\{L,H\} + 1, then CC violates the conditional veto. Reversing the order of the alternatives if necessary, let L=c−1L = c - 1, so that αc>a+1\alpha_c > a + 1 and H≥c−1H \ge c - 1. The report bCb^C vetoes a+1a + 1, because the lower endpoint of its option set is αc\alpha_c. If c=1c = 1, the report aCa^C has option set [a,αn−1][a,\alpha_{n-1}], which contains a+1a + 1 because αn−1≥α1>a+1\alpha_{n-1} \ge\alpha_1 > a + 1. If c≥2c \ge2, let one member report bb and the other c−1c - 1 members report aa. By (3), the option set is [α1,αn−c+1][\alpha_1,\alpha_{n-c+1}], which contains a+1a + 1: α1≤a+1\alpha_1 \le a + 1 because L≥1L \ge1, and αn−c+1≥b−1≥a+1\alpha_{n-c+1} \ge b - 1 \ge a + 1 because H≥c−1H \ge c - 1. In both cases a report in which no member reports a+1a + 1 leaves a+1a + 1 open.

Step 3: some report of a coalition with cc members leaves open none of its tops only if c≥E+2c \ge E + 2, and such a report exists if c=E+2c = E + 2. Suppose that O(tC)=[zc,zn]O(t_C) = [z_c,z_n] contains no top of tCt_C, and let ss members have a top below zcz_c and r=c−sr = c - s members a top above znz_n. Both numbers are positive: at least cc entries of the pooled list are at most the largest reported top, so zcz_c does not exceed it, and at least cc entries are at least the smallest reported top, so znz_n is not below it. Fewer than cc entries of the pooled list are strictly below zcz_c; since zc>az_c > a, these entries include the ss low tops and the qaq_a fixed ballots equal to aa, so s+qa<cs + q_a < c, that is, r>qar > q_a. Symmetrically, fewer than cc entries are strictly above znz_n, so r+qb<cr + q_b < c, that is, s>qbs > q_b. Hence c=r+s≥E+2c = r + s \ge E + 2. Conversely, if c=E+2c = E + 2, let qa+1q_a + 1 members report bb and qb+1q_b + 1 members report aa. By (3), the option set is [αqa+1,αn−qb−1][\alpha_{q_a+1},\alpha_{n-q_b-1}], which contains neither aa nor bb.

By Steps 1–3, for k≤n−1k \le n - 1 the rule is kk-NOMG if and only if k≤min⁡{L,H}k \le\min\{L,H\} and k≤E+1k \le E + 1. Since L≤n−1L \le n - 1, this gives K(fα)=min⁡{L,H,E+1}K(f^\alpha) = \min\{L,H,E + 1\}. The three inequalities in the statement express L≥kL \ge k, H≥kH \ge k and E≥k−1E \ge k - 1.

It remains to determine the attainable thresholds. If m≥4m \ge4, no fixed ballot is counted by both LL and HH, so K(fα)=kK(f^\alpha) = k requires $2k \le L + H \le n - 1.Conversely,if$2k≤n−1. Conversely, if \$2k \le n - 1, place kk fixed ballots at aa and the other n−1−kn - 1 - k at bb; then L=k≤HL = k \le H and E+1=nE + 1 = n. If m=3m = 3, the fixed ballots equal to a+1=b−1a + 1 = b - 1 are counted by both LL and HH, so L+H=2(n−1)−EL + H = 2(n - 1) - E, and L,H≥kL,H \ge k together with E≥k−1E \ge k - 1 imply 3k≤2n−13k \le2n - 1. Conversely, the previous construction works if 2k≤n−12k \le n - 1; if n/2≤k<2n/3n/2 \le k < 2n/3, place n−kn - k fixed ballots at each of aa and bb and the remaining 2k−n+12k - n + 1 at a+1a + 1. Then L=H=kL = H = k and E=2(n−1−k)≥k−1E = 2(n - 1 - k) \ge k - 1.

For example, if all fixed ballots are extreme alternatives, then K(fα)=min⁡{qa,qb}K(f^\alpha) = \min\{q_a,q_b\}, where qaq_a and qbq_b are the numbers of fixed ballots at aa and at bb. Balancing the two numbers gives the largest protection within this class: for odd nn, the median of the tops has K(fα)=(n−1)/2K(f^\alpha) = (n - 1)/2, exactly as plurality (Proposition 6). Placing every fixed ballot at aa gives the rule that selects the smallest reported top, for which K(fα)=0K(f^\alpha) = 0. The third term matters only for coalitions with at least two members: with three alternatives and n≥3n \ge3, the median voter scheme with all fixed ballots equal to a+1a + 1 has L=H=n−1L = H = n - 1 and E=0E = 0, so that single voters are protected, while two voters whose tops are the two extreme alternatives obtain a+1a + 1 whatever the outsiders do, and their truthful report leaves open neither of their tops.

Median voter schemes only count how many voters report a top below a given alternative. Generalized median voter schemes allow the identities of these voters to matter. A monotonic family of fixed ballots is a collection β=(βS)S⊆N\beta= (\beta_S)_{S \subseteq N} of elements of AA such that βN=a\beta_N = a, β∅=b\beta_\varnothing= b, and βQ≤βS\beta_Q \le\beta_S whenever S⊆QS \subseteq Q. The generalized median voter scheme fβf^\beta is the tops-only rule

fβ(t)=min⁡S⊆Nmax⁡{max⁡j∈Stj,βS}.f^\beta(\mathbf{t}) = \min_{S \subseteq N} \max\left\{\max_{j \in S} t_j,\beta_S\right\}.

where the term for S=∅S = \varnothing is β∅=b\beta_{\varnothing} = b. A preference PiP_i is single-peaked if x<y≤t(Pi)x < y \leq t(P_i) or t(Pi)≤y<xt(P_i) \leq y < x implies yPixy P_i x. On the domain of single-peaked preferences, the onto, tops-only and strategy-proof rules are exactly the generalized median voter schemes, and the anonymous ones among them are exactly the median voter schemes [26]; see also Barberà et al. [11]. For t∈AN\mathbf{t} \in A^N and x∈Ax \in A let Lx(t)={i∈N:ti≤x}L_x(\mathbf{t}) = \{i \in N : t_i \leq x\}. If a coalition CC is the union of disjoint sets AA and BB, one of which may be empty, (aA,bB)(a^A,b^B) denotes the report of CC at which the members of AA report aa and the members of BB report bb.

Lemma 3. Let f=fβf = f^\beta be a generalized median voter scheme.

(i) For every t∈AN\mathbf{t} \in A^N and x∈Ax \in A, f(t)≤xf(\mathbf{t}) \leq x if and only if βLx(t)≤x\beta_{L_x(\mathbf{t})} \leq x. Consequently, ff is nondecreasing in each top, min⁡i∈Nti≤f(t)≤max⁡i∈Nti\min_{i\in N} t_i \leq f(\mathbf{t}) \leq\max_{i\in N} t_i, and ff is onto.

(ii) Let CC be a proper coalition, let tC∈AC\mathbf{t}_C \in A^C, and write ℓ(tC)=f(tC,aN∖C)\ell(\mathbf{t}_C) = f(\mathbf{t}_C,a^{N\setminus C}) and u(tC)=f(tC,bN∖C)u(\mathbf{t}_C) = f(\mathbf{t}_C,b^{N\setminus C}). Then O(tC)=[ℓ(tC),u(tC)]O(\mathbf{t}_C) = [\ell(\mathbf{t}_C),u(\mathbf{t}_C)], and every xx in this interval is the outcome when all outsiders report xx. Moreover, ℓ\ell and uu are nondecreasing in tC\mathbf{t}_C, u(tC)≥min⁡i∈Ctiu(\mathbf{t}_C) \geq\min_{i\in C} t_i and ℓ(tC)≤max⁡i∈Cti\ell(\mathbf{t}_C) \leq\max_{i\in C} t_i.

(iii) Let a proper coalition CC be the union of disjoint sets AA and BB, one of which may be empty. Then O(aA,bB)=[βN∖B,βA]O(a^A,b^B) = [\beta_{N\setminus B},\beta_A]. In particular, O(aC)=[a,βC]O(a^C) = [a,\beta_C] and O(bC)=[βN∖C,b]O(b^C) = [\beta_{N\setminus C},b], and CC can veto xx if and only if x>βCx > \beta_C or x<βN∖Cx < \beta_{N\setminus C}.

Proof. (i) The term for SS is at most xx if and only if S⊆Lx(t)S \subseteq L_x(\mathbf{t}) and βS≤x\beta_S \leq x (for S=∅S = \varnothing the first condition is vacuous). If βLx(t)≤x\beta_{L_x(\mathbf{t})} \leq x, the term for S=Lx(t)S = L_x(\mathbf{t}) is at most xx. Conversely, if the term for some SS is at most xx, then S⊆Lx(t)S \subseteq L_x(\mathbf{t}) and, by monotonicity, βLx(t)≤βS≤x\beta_{L_x(\mathbf{t})} \leq\beta_S \leq x. Raising a top weakly shrinks every Lx(t)L_x(\mathbf{t}) and therefore weakly raises every βLx(t)\beta_{L_x(\mathbf{t})}, so ff is nondecreasing in each top. For x=max⁡itix = \max_i t_i we have Lx(t)=NL_x(\mathbf{t}) = N and βN=a≤x\beta_N = a \leq x, so f(t)≤max⁡itif(\mathbf{t}) \leq\max_i t_i; for x<min⁡itix < \min_i t_i we have Lx(t)=∅L_x(\mathbf{t}) = \varnothing and β∅=b>x\beta_{\varnothing} = b > x, so f(t)>xf(\mathbf{t}) > x. In particular f(xN)=xf(x^N) = x for every x∈Ax \in A.

(ii) By monotonicity every element of O(tC)O(\mathbf{t}_C) lies in [ℓ(tC),u(tC)][\ell(\mathbf{t}_C),u(\mathbf{t}_C)]. Conversely, let ℓ(tC)≤x≤u(tC)\ell(\mathbf{t}_C) \leq x \leq u(\mathbf{t}_C) and let t′=(tC,xN∖C)\mathbf{t}' = (\mathbf{t}_C,x^{N\setminus C}). Since Lx(t′)=Lx(tC,aN∖C)L_x(\mathbf{t}') = L_x(\mathbf{t}_C,a^{N\setminus C}) and f(tC,aN∖C)≤xf(\mathbf{t}_C,a^{N\setminus C}) \leq x, part (i) gives f(t′)≤xf(\mathbf{t}') \leq x. For y<xy < x we have Ly(t′)={i∈C:ti≤y}=Ly(tC,bN∖C)L_y(\mathbf{t}') = \{i \in C : t_i \leq y\} = L_y(\mathbf{t}_C,b^{N\setminus C}), and f(tC,bN∖C)=u(tC)>yf(\mathbf{t}_C,b^{N\setminus C}) = u(\mathbf{t}_C) > y, so part (i) gives f(t′)>yf(\mathbf{t}') > y. Hence f(t′)=xf(\mathbf{t}') = x. The monotonicity of ℓ\ell and uu and the two bounds follow from part (i), applied to (tC,aN∖C)(\mathbf{t}_C,a^{N\setminus C}) and (tC,bN∖C)(\mathbf{t}_C,b^{N\setminus C}).

(iii) At a profile at which the voters in a set DD report aa and all other voters report bb, we have Ly=DL_y = D for every yy with a≤y<ba \leq y < b, so by part (i) the outcome is βD\beta_D. Applying this with all outsiders at aa and with all outsiders at bb gives ℓ(aA,bB)=βN∖B\ell(a^A,b^B) = \beta_{N\setminus B} and u(aA,bB)=βAu(a^A,b^B) = \beta_A, and the formula follows from part (ii). Taking B=∅B = \varnothing and A=∅A = \varnothing gives O(aC)O(a^C) and O(bC)O(b^C). By part (ii), u(rC)≥u(aC)=βCu(\mathbf{r}_C) \geq u(a^C) = \beta_C and ℓ(rC)≤ℓ(bC)=βN∖C\ell(\mathbf{r}_C) \leq\ell(b^C) = \beta_{N\setminus C} for every rC\mathbf{r}_C. Hence xx belongs to every option set of CC if βN∖C≤x≤βC\beta_{N\setminus C} \leq x \leq\beta_C, while aCa^C vetoes every x>βCx > \beta_C and bCb^C vetoes every x<βN∖Cx < \beta_{N\setminus C}.

A median voter scheme is the generalized median voter scheme with βS=αn−∣S∣\beta_S = \alpha_{n-|S|}, which is a monotonic family of fixed ballots because α0=a\alpha_0 = a and αn=b\alpha_n = b. Indeed, the median is at most xx if and only if at least n−∣Lx(t)∣n - |L_x(\mathbf{t})| fixed ballots are at most xx, that is, if and only if αn−∣Lx(t)∣≤x\alpha_{n-|L_x(\mathbf{t})|} \leq x, which by Lemma 3(i) is the condition for fβ(t)≤xf^\beta(\mathbf{t}) \leq x.

Theorem 5. Let m≥3m \geq3, let fβf^\beta be a non-dictatorial generalized median voter scheme, and let k∈{1,…,n−1}k \in\{1,\ldots,n-1\}. Then fβf^\beta is kk-NOMG if and only if every coalition CC with 1≤∣C∣≤k1 \leq|C| \leq k satisfies

(i) βN∖C≤a+1\beta_{N\setminus C} \le a + 1 and βC≥b−1\beta_C \ge b - 1; and

(ii) for every partition of CC into nonempty sets AA and BB, βN∖B=a\beta_{N\setminus B} = a or βA=b\beta_A = b.

Consequently, K(fβ)K(f^\beta) is one less than the size of the smallest nonempty coalitions that fail (i) or (ii).

By Lemma 3(iii), condition (i) says that the coalition can veto at most the two extreme alternatives, and condition (ii) says that when the coalition splits its reports between the two extreme alternatives, at least one of them remains in its option set. The grand coalition fails (i), so the last statement is meaningful.

Proof. Throughout, CC is a nonempty coalition with at most k≤n−1k \le n - 1 members, so that CC is proper and Lemma 3 applies. By Theorem 1, fβf^\beta is kk-NOMG if and only if every such coalition satisfies the conditional veto and every report of such a coalition leaves open one of its tops. By Lemma 3(iii), condition (i) holds for CC if and only if CC cannot veto any alternative in [a+1,b−1][a + 1, b - 1].

Necessity of (i). Let fβf^\beta be kk-NOMG, suppose that (i) fails for some coalition with at most kk members, and let CC be such a coalition that is minimal with respect to inclusion. Let x∈[a+1,b−1]x \in[a + 1, b - 1] be an alternative that CC can veto. Suppose first that CC has at least two members, and split it into two nonempty sets AA and BB. By minimality, (i) holds for AA and for BB, so βN∖B≤a+1\beta_{N\setminus B} \le a + 1 and βA≥b−1\beta_A \ge b - 1, and the option set O(aA,bB)=[βN∖B,βA]O(a^A,b^B) = [\beta_{N\setminus B},\beta_A] contains xx. Since x∉{a,b}=τ(aA,bB)x \notin\{a,b\} = \tau(a^A,b^B), this contradicts the conditional veto.

Hence C={i}C = \{i\} for some voter ii. Suppose first that βC≤b−2\beta_C \le b - 2. The report aCa^C vetoes b−1b - 1, so by the conditional veto the report bCb^C vetoes b−1b - 1 as well; since O(bC)=[βN∖C,b]O(b^C) = [\beta_{N\setminus C},b], this means that βN∖C=b\beta_{N\setminus C} = b. Then bCb^C vetoes a+1a + 1, so the report aCa^C must veto a+1a + 1; since O(aC)=[a,βC]O(a^C) = [a,\beta_C], this means that βC=a\beta_C = a. If instead βN∖C≥a+2\beta_{N\setminus C} \ge a + 2, the same two implications, in the reverse order, give first βC=a\beta_C = a and then βN∖C=b\beta_{N\setminus C} = b. In both cases β{i}=a\beta_{\{i\}} = a and βN∖{i}=b\beta_{N\setminus\{i\}} = b, so by monotonicity βS=a\beta_S = a whenever i∈Si \in S and βS=b\beta_S = b whenever i∉Si \notin S. By Lemma 3(i), fβ(t)≤xf^\beta(t) \le x if and only if ti≤xt_i \le x, for every tt and xx. Hence fβ(t)=tif^\beta(t) = t_i for every tt, and fβf^\beta is dictatorial, a contradiction.

Necessity of (ii). Let fβf^\beta be kk-NOMG and let CC be partitioned into nonempty sets AA and BB. The report (aA,bB)(a^A,b^B) must leave open one of its tops, so [βN∖B,βA][\beta_{N\setminus B},\beta_A] contains aa or bb; that is, βN∖B=a\beta_{N\setminus B} = a or βA=b\beta_A = b.

Sufficiency. Suppose that (i) and (ii) hold for every coalition with at most kk members, and fix such a coalition CC.

By (i), CC can veto at most aa and bb. If CC can veto bb, then βC<b\beta_C < b by Lemma 3(iii). At any profile at which no member of CC reports bb, we have C⊆Lb−1C \subseteq L_{b-1} and therefore βLb−1≤βC≤b−1\beta_{L_{b-1}} \le\beta_C \le b - 1, so the outcome is at most b−1b - 1 by Lemma 3(i). Thus every report of CC that avoids bb vetoes bb. If CC can veto aa, then βN∖C>a\beta_{N\setminus C} > a. At any profile at which no member of CC reports aa, we have La=N∖CL_a = N \setminus C and therefore βLa≥βN∖C>a\beta_{L_a} \ge\beta_{N\setminus C} > a, so the outcome is above aa. Thus every report of CC that avoids aa vetoes aa. Hence CC satisfies the conditional veto.

Finally, suppose that some option set O(tC)=[ℓ,u]O(t_C) = [\ell,u] contains no top of tCt_C. By Lemma 3(ii), uu is at least the smallest top of tCt_C and ℓ\ell is at most the largest one, so the sets A={i∈C:ti<ℓ}A = \{i \in C : t_i < \ell\} and B={i∈C:ti>u}B = \{i \in C : t_i > u\} are nonempty, and they partition CC. At the profile (tC,bN∖C)(t_C,b^{N\setminus C}), whose outcome is u<bu < b, we have Lu=AL_u = A, so Lemma 3(i) gives βA≤u<b\beta_A \le u < b. At the profile (tC,aN∖C)(t_C,a^{N\setminus C}), whose outcome is ℓ>a\ell> a, we have Lℓ−1=N∖BL_{\ell-1} = N \setminus B, so Lemma 3(i) gives βN∖B>ℓ−1≥a\beta_{N\setminus B} > \ell- 1 \ge a. This contradicts (ii). Hence every report of CC leaves open one of its tops.

The last statement follows because K(fβ)≤n−1K(f^\beta) \le n - 1 by Theorem 2.

For a median voter scheme, where βS=αn−∣S∣\beta_S=\alpha_{n-|S|}, conditions (i) and (ii) for all coalitions with at most kk members are the three inequalities of Proposition 7. Allowing the fixed ballots to depend on the identities of the voters does not increase the largest attainable threshold: if a non-dictatorial generalized median voter scheme is kk-NOMG, then k<n/2k<n/2 when m≥4m\geq4, and k<2n/3k<2n/3 when m=3m=3. Indeed, let m≥4m\geq4 and suppose that n−k≤kn-k\leq k. Choose DD with ∣D∣=n−k|D|=n-k; both DD and N∖DN\setminus D are nonempty and have at most kk members. Condition (i) for N∖DN\setminus D gives βD≤a+1\beta_D\leq a+1, and condition (i) for DD gives βD≥b−1\beta_D\geq b-1, so m=b−a+1≤3m=b-a+1\leq3, a contradiction. Let m=3m=3, so that a+1=b−1a+1=b-1, and suppose that 3k≥2n3k\geq2n. Then 2(n−k)≤k2(n-k)\leq k, so there are disjoint coalitions AA and BB with ∣A∣=∣B∣=n−k≥1|A|=|B|=n-k\geq1, and C=A∪BC=A\cup B has at most kk members. The coalitions N∖AN\setminus A and N∖BN\setminus B have kk members each, so condition (i) gives βA≤a+1<b\beta_A\leq a+1<b and βN∖B≥b−1>a\beta_{N\setminus B}\geq b-1>a, and (ii) fails for CC, a contradiction. By Proposition 7, both bounds are attained by median voter schemes.

Voting by committees

Let Ω\Omega be a finite set of objects with ∣Ω∣≥2|\Omega|\geq2 (one object is the case of two alternatives of § 4), and let A=2ΩA=2^\Omega, so that m≥4m\geq4 and each top tit_i is a set of objects. A committee for ω∈Ω\omega\in\Omega is a nonempty family Wω\mathcal{W}_\omega of nonempty coalitions, the winning coalitions for ω\omega, such that M∈WωM\in\mathcal{W}_\omega and M⊆M′M\subseteq M' imply M′∈WωM'\in\mathcal{W}_\omega. Given W=(Wω)ω∈Ω\mathcal{W}=(\mathcal{W}_\omega)_{\omega\in\Omega}, voting by committees is the tops-only rule

fW(t)={ω∈Ω:{i∈N:ω∈ti}∈Wω}.f^{\mathcal{W}}(\mathbf{t})=\{\omega\in\Omega:\{i\in N:\omega\in t_i\}\in\mathcal{W}_\omega\}.

It is onto: since N∈WωN\in\mathcal{W}_\omega and ∅∉Wω\varnothing\notin\mathcal{W}_\omega, fW(xN)=xf^{\mathcal{W}}(x^N)=x for every xx. Voting by quota is the case Wω={M⊆N:∣M∣≥qω}\mathcal{W}_\omega=\{M\subseteq N:|M|\geq q_\omega\} with 1≤qω≤n1\leq q_\omega\leq n for every ω\omega, and we write fqf^q. A preference PiP_i is separable if, for every y⊆Ωy\subseteq\Omega and ω∉y\omega\notin y, y∪{ω}Piyy\cup\{\omega\}P_i y if and only if ω∈t(Pi)\omega\in t(P_i). Barberà et al. [12] show that, on the domain of separable preferences, the onto strategy-proof rules are exactly the voting by committees, and the anonymous ones among them are exactly the voting by quota.

We say that a coalition CC can force ω\omega in if C∈WωC\in\mathcal{W}_\omega, and that it can force ω\omega out if N∖C∉WωN\setminus C\notin\mathcal{W}_\omega. By monotonicity of the committee, if CC can force ω\omega in (out), then ω\omega belongs (does not belong) to the outcome whenever all members of CC include ω\omega in (exclude ω\omega from) their tops, whatever the outsiders report.

Theorem 6. Let ∣Ω∣≥2|\Omega|\geq2, let fWf^{\mathcal{W}} be a non-dictatorial voting by committees, and let k∈{1,…,n−1}k\in\{1,\ldots,n-1\}. Then fWf^{\mathcal{W}} is kk-NOMG if and only if no coalition with at most kk members can force an object in or out. Consequently,

K(fW)=min⁡ω∈Ωmin⁡{∣C∣:C∈Wω or N∖C∉Wω}−1,K(f^{\mathcal{W}})=\min_{\omega\in\Omega}\min\{|C|:C\in\mathcal{W}_\omega\text{ or }N\setminus C\notin\mathcal{W}_\omega\}-1,

and K(fW)<n/2K(f^{\mathcal{W}})<n/2.

Proof. Sufficiency. Suppose that no coalition with at most kk members can force an object in or out, and let CC be such a coalition and tCt_C one of its reports. If all outsiders report a set of objects yy, the outcome is yy: every ω∈y\omega\in y is supported by a coalition that contains N∖CN\setminus C, which is winning for ω\omega, and every ω∉y\omega\notin y is supported by a subset of CC, which is not. Hence every option set of CC is AA, and CC has no obvious group manipulation.

Necessity. Let fWf^{\mathcal{W}} be kk-NOMG, suppose that some coalition with at most kk members can force an object in or out, and let CC be such a coalition that is minimal with respect to inclusion. We first show that CC can force every object in and out. Suppose that CC can impose a decision on an object ω\omega: all sets of objects with the opposite decision on ω\omega are then vetoed by the same report of CC. Let yy be one of these sets, let η≠ω\eta\ne\omega be another object, and let xx be the set obtained from yy by reversing the decision on η\eta only. Since y∉τ(xC)y \notin\tau(x^{C}), the conditional veto requires the report xCx^{C} to veto yy. If all outsiders report yy, all voters agree on every object other than η\eta, and the outcome agrees with them on these objects. Since the outcome is not yy, the decision on η\eta is the one supported by the members of CC, against all outsiders. Choosing yy with η∈y\eta\in y shows that CC can force η\eta out, and choosing yy with η∉y\eta\notin y shows that CC can force η\eta in. Applying the same argument with the roles of η\eta and ω\omega exchanged shows that CC can force ω\omega in and out as well.

If C={i}C = \{i\}, then for every object the winning coalitions are exactly the coalitions that contain ii, so fW(t)=tif^{W}(t) = t_i for every tt, and fWf^{W} is dictatorial, a contradiction. Otherwise, split CC into two nonempty sets, fix two different objects, and consider the report at which the members of one set report the first object alone and the members of the other set report the second object alone. If all outsiders report the empty set, each of the two objects is supported by a nonempty proper subset of CC, which by minimality is not winning, and no other object is supported by any voter. Hence the empty set belongs to the option set of this report, although no member reports it; but CC can veto the empty set, because it can force an object in. This contradicts the conditional veto.

The threshold. The formula for K(fW)K(f^{W}) restates the equivalence, because K(fW)≤n−1K(f^{W}) \le n - 1 by Theorem 2. For the bound, take a coalition with ⌊n/2⌋\lfloor n/2 \rfloor members and an object ω\omega. If the coalition is winning for ω\omega, it can force ω\omega in; otherwise its complement, which has ⌈n/2⌉\lceil n/2 \rceil members, can force ω\omega out. Hence some coalition with at most ⌈n/2⌉\lceil n/2 \rceil members can force an object in or out, and K(fW)≤⌈n/2⌉−1<n/2K(f^{W}) \le\lceil n/2 \rceil- 1 < n/2.

Corollary 2. Let ∣Ω∣≥2|\Omega| \ge2 and let fqf^{q} be a voting by quota. Then

K(fq)=min⁡ω∈Ωmin⁡{qω−1,n−qω}.K(f^{q}) = \min_{\omega\in\Omega}\min\{q_{\omega} - 1, n - q_{\omega}\}.

Equivalently, for k∈{1,…,n−1}k \in\{1,\ldots,n-1\}, fqf^{q} is kk-NOMG if and only if k+1≤qω≤n−kk + 1 \le q_{\omega} \le n - k for every ω∈Ω\omega\in\Omega.

Proof. Voting by quota is anonymous and onto, hence not dictatorial. The smallest coalitions that can force ω\omega in have qωq_{\omega} members, and the smallest coalitions that can force ω\omega out have n−qω+1n - q_{\omega} + 1 members. Apply Theorem 6.

The object with the lowest threshold determines the protection of the whole rule. A unanimity quota on a single object, qω=nq_{\omega} = n, already gives K(fq)=0K(f^{q}) = 0. If every quota is ⌈2n/3⌉\lceil2n/3 \rceil, then K(fq)=⌊n/3⌋K(f^{q}) = \lfloor n/3 \rfloor. By Theorem 6, no non-dictatorial voting by committees protects coalitions with more than h=⌈n/2⌉−1h = \lceil n/2 \rceil- 1 members, and by Corollary 2 the voting by quota that attain hh are precisely those with h+1≤qω≤n−hh + 1 \le q_{\omega} \le n - h for every object. Thus an odd electorate has a unique optimal quota for each object, the simple majority quota (n+1)/2(n + 1)/2, while an even electorate admits either of the two quotas n/2n/2 and n/2+1n/2 + 1, independently across objects.

Remark 2. For k=1k = 1, the results of this section are those obtained by Arribillaga and Bonifacio [1] for individual manipulations. Proposition 7 gives α1∈{a,a+1}\alpha_1 \in\{a,a+1\} and αn−1∈{b−1,b}\alpha_{n-1} \in\{b-1,b\}; Theorem 5 gives βN∖{i}∈{a,a+1}\beta_{N\setminus\{i\}} \in\{a,a+1\} and β{i}∈{b−1,b}\beta_{\{i\}} \in\{b-1,b\} for every ii; Corollary 2 gives 2≤qω≤n−12 \le q_{\omega} \le n-1; and Theorem 6 says that, for every object, no voter belongs to all winning coalitions and no voter is a winning coalition by herself. The coalitional conditions are more demanding in two ways. Conditions on single voters become conditions on all coalitions with at most kk members, and, for generalized median voter schemes, condition (ii) of Theorem 5 appears, which has no counterpart for individuals.

Concluding remarks

The informational characterization in Proposition 1 gives a precise basis for studying obvious group manipulations: they are exactly the deviations identifiable as group manipulations from option sets alone. The results that follow show both the restrictions imposed by this requirement and the scope for protection against it, depending on the rules, the domain, and the size of the coalition.

For tops-only rules with at least three alternatives, immunity to obvious group manipulations has the same bite as group strategy-proofness (Theorem 2). Doi et al. [19] find a similar pattern in housing markets, where the same notion, together with individual rationality and pair efficiency, singles out the top trading cycles mechanism, which is group strategy-proof. The coincidence is not general: there are NOMG rules that are not strategy-proof, namely the parity rules of Example 1 and, by the Gibbard–Satterthwaite theorem, the scoring rules of Theorem 4. Identifying the classes of rules and the environments in which the two requirements coincide is a natural question.

The coalition-size results also distinguish the two classes. Efficient, non-dictatorial tops-only rules can protect all coalitions of up to n−2n - 2 voters, whereas under the majority criterion a minimal strict majority already suffices for an obvious manipulation, outside the exceptional configuration. For odd electorates the latter threshold is exact for every such rule. For even electorates, determining which rules also protect coalitions of exactly n/2n/2 voters remains a question for further research, both within the majority class and within its Condorcet-consistent subclass.

The results for tops-only rules use the richness of the universal domain at two points: to choose the lower ranks of the members of a coalition in Lemma 2, and to find a third alternative in the proof of Theorem 2. On restricted domains, such as the domain of single-peaked preferences, where non-dictatorial group strategy-proof rules exist, NOMG and (group) strategy-proofness are not equivalent, as the following example shows.

Example 3. Let A={a,b,c}\mathcal{A} = \{a,b,c\}, let n≥3n \ge3 be odd, and restrict preferences to the domain of single-peaked preferences with respect to the axis a<b<ca < b < c: true preferences, reports and option sets are all taken within this domain. Consider the tops-only rule that selects cc if all voters rank cc first, aa if an odd number rank aa first, and bb otherwise. This rule is anonymous and, on this domain, efficient. For every nonempty proper coalition CC,

Of(PC)={{a,b,c},if all members of C rank c first,{a,b},otherwise.O^{f}(P_C) = \begin{cases} \{a,b,c\}, & \text{if all members of } C \text{ rank } c \text{ first},\\ \{a,b\}, & \text{otherwise.} \end{cases}

Since aa and bb remain attainable after every report, neither can witness a worst-case obvious manipulation; cc cannot do so either, since it is attainable truthfully only when all members rank it first. A best-case obvious manipulation would require making cc attainable when some member prefers aa or bb to it, which also fails. Efficiency handles the grand coalition, so the

rule is NOMG. However, if two voters have the preference a b ca\ b\ c and all others have b a cb\ a\ c, the outcome is bb, and either of the first two voters can obtain aa by reporting b a cb\ a\ c. Thus, the rule is not strategy-proof. On the universal domain the same rule is not efficient: if two voters have the preference a c ba\ c\ b and all others have c a bc\ a\ b, it selects bb, which every voter ranks below aa. This is why the example does not contradict Theorem 2.

§ 7 takes the complementary view: it keeps the universal domain and asks how much protection survives for rules that are strategy-proof on single-peaked or on separable preferences. With at least four alternatives, no non-dictatorial rule in these classes is protected against coalitions with half of the voters, while the best of them are protected against all smaller coalitions.

Beyond tops-only rules, Subsection 5.2 and § 6 establish, respectively, the incompatibility of NOMG with the majority criterion for n,m≥3n,m \ge3 and (n,m)≠(4,3)(n,m) \ne(4,3), and the existence of anonymous NOMG scoring rules in the exceptional configuration. Borda’s rule also shows that NOMG and Condorcet consistency can coexist there.

A characterization of the NOMG scoring rules for arbitrary numbers of voters and alternatives is left for future work.

Proof of Theorem 4

Throughout, n=4n=4, m=3m=3, s=(1,t,0)s=(1,t,0), and Sc⁡(x)\operatorname{Sc}(x) denotes the total score of xx. For a coalition CC with c=∣C∣c=|C| members and a report PCP_C, σ(x)\sigma(x) denotes the score that xx receives from the members of CC, and r=4−cr=4-c is the number of outsiders. We use three observations.

(a) Exclusion. If σ(y)−σ(x)>r\sigma(y)-\sigma(x)>r for some yy, then x∉O(PC)x\notin O(P_C), since each outsider gives xx at most 1 point more than yy.

(b) Large coalitions. If c⋅min⁡{t,1−t}>rc\cdot\min\{t,1-t\}>r, then CC has no group manipulation. Indeed, if the outcome changes from x=f(P)x=f(P) to yy with yPixy\mathrel{P_i}x for every i∈Ci\in C, then at PP each member gives yy at least min⁡{t,1−t}\min\{t,1-t\} more than xx, so the members give yy more than rr points more than xx, while the outsiders give xx at most rr more than yy; hence Sc⁡(y)>Sc⁡(x)\operatorname{Sc}(y)>\operatorname{Sc}(x) at PP, contradicting f(P)=xf(P)=x.

(c) Raising the target. If xx wins at some outsider profile, it still wins after every outsider moves xx to the top of her ranking: the score of xx weakly increases, every other score weakly decreases, and the ties won by xx are still won. So, when checking whether x∈O(PC)x\in O(P_C), we may assume that all outsiders rank xx first.

Lemma 4. If t<34t<\frac{3}{4}, every option set of a single voter is A\mathcal{A}.

Proof. Let the voter report p1p2p3p_1p_2p_3, in this order. If all three outsiders report p1p2p3p_1p_2p_3, the scores of (p1,p2,p3)(p_1,p_2,p_3) are (4,4t,0)(4,4t,0); if all report p2p3p1p_2p_3p_1, they are (1,3+t,3t)(1,3+t,3t); if all report p3p2p1p_3p_2p_1, they are (1,4t,3)(1,4t,3). The respective alternatives win strictly (the last one because t<34t<\frac{3}{4}).

Lemma 5. Let c=2c=2 and 12≤t<23\frac{1}{2}\leq t<\frac{2}{3}.

(i) If the two members rank different alternatives last, then O(PC)=AO(P_C)=\mathcal{A}.

(ii) If both members rank uu last, then O(PC)=A∖{u}O(P_C)=\mathcal{A}\setminus\{u\} when t>12t>\frac{1}{2} or uu is not ▹\triangleright-maximal, and O(PC)=AO(P_C)=\mathcal{A} otherwise.

In particular, every option set of a two-voter coalition contains both members’ tops and at least two alternatives, and an alternative can be missing only if both members rank it last and, when t=12t=\frac{1}{2}, it is not ▹\triangleright-maximal.

Proof. Let xx be an alternative that at least one member does not rank last, so that σ(x)≥t\sigma(x)\geq t, and let both outsiders rank xx first, which gives Sc⁡(x)≥2+t\operatorname{Sc}(x)\geq2+t. If neither of the other two alternatives receives 2 points from the members, each of them receives at most 1+t1+t; if the outsiders rank one of them second each, both end with at most 1+2t<2+t1+2t<2+t. If one of them, say pp, receives 2 points from the members, both members rank pp first; the remaining alternative qq then receives at most tt points from the members, because at least one member ranks xx second. If both outsiders rank qq second, the scores of pp and qq are at most 2 and 3t3t, both below 2+t2+t. Hence x∈O(PC)x\in O(P_C). This proves (i) and shows that, in (ii), the two alternatives other than uu belong to O(PC)O(P_C).

It remains to consider uu in case (ii). Since both members rank uu last, Sc⁡(u)≤2\operatorname{Sc}(u)\leq2, while the three scores add up to 4(1+t)4(1+t). If t>12t>\frac{1}{2}, the scores of the other two alternatives add up to more than 4, so one of them exceeds 2 and uu is not selected. If t=12t=\frac{1}{2}, the three scores add up to 6, so uu can be selected only if all three scores equal 2, and then only if uu is ▹\triangleright-maximal. Such a tie can be obtained. Let pp and qq be the other two alternatives. If both members rank pp first, let both outsiders report uqpu q p; if the members rank pp and qq first, respectively, let the outsiders report upqu p q and uqpu q p.

Proof of Theorem 4. The case t<12t < \frac{1}{2}. Label the alternatives so that ww is ▹\triangleright-minimal and let p,qp, q be the others. Let C={1,2}C = \{1, 2\}, let voter 1 have the preference pqwp q w and voter 2 the preference qpwq p w, so that σ=(1+t,1+t,0)\sigma= (1 + t, 1 + t, 0) on (p,q,w)(p, q, w). If the outsiders report wpqw p q and wqpw q p, the scores are (1+2t,1+2t,2)(1 + 2t, 1 + 2t, 2) and ww wins, because t<12t < \frac{1}{2}; so w∈O(PC)w \in O(P_C). Let both members report pqwp q w, so that σ=(2,2t,0)\sigma= (2, 2t, 0). By (c), ww can win only if both outsiders rank it first, which gives ww the score 2 and (p,q)(p, q) the scores (2,4t)(2, 4t), (2+t,3t)(2 + t, 3t) or (2+2t,2t)(2 + 2t, 2t). In each case pp has at least 2 points, and pp wins a tie with ww because ww is ▹\triangleright-minimal. Hence ww is not in the option set of the new report, and (W) holds with ww, which both members rank last.

The case 23≤t<1\frac{2}{3} \le t < 1. Label the alternatives p1,p2,p3p_1, p_2, p_3 with p2▹p1p_2 \triangleright p_1, and let the members of C={1,2,3}C = \{1, 2, 3\} have the common preference p1p2p3p_1 p_2 p_3, so that σ=(3,3t,0)\sigma= (3, 3t, 0). If the outsider reports p2p3p1p_2 p_3 p_1, the scores are (3,3t+1,t)(3, 3t + 1, t) and p2p_2 wins (by priority when t=23t = \frac{2}{3}), so p2∈O(PC)p_2 \in O(P_C). Let one member report p1p3p2p_1 p_3 p_2 while the others keep their ballots; then σ=(3,2t,t)\sigma= (3, 2t, t), and since 3−2t>13 - 2t > 1 and 3−t>13 - t > 1, (a) gives the option set {p1}\{p_1\}. Condition (W) holds with p2p_2.

The case t=1t = 1. Let xx be ▹\triangleright-maximal. If every voter ranks some y≠xy \ne x first and xx second, then xx and yy tie with score 4 and xx is selected, although every voter prefers yy. The rule is not efficient, hence OMG by Lemma 1(iii).

The case 12≤t<23\frac{1}{2} \le t < \frac{2}{3}. For c=1c = 1, all option sets equal A\mathcal{A} (Lemma 4), so neither (W) nor (B) can hold. For c∈{3,4}c \in\{3, 4\}, (b) with min⁡{t,1−t}=1−t\min\{t, 1 - t\} = 1 - t shows that there is no group manipulation, because 3(1−t)>13(1 - t) > 1; by Lemma 1(i) there is no obvious group manipulation either. Let c=2c = 2, with truthful option set TT and deviating option set FF. By Lemma 5, TT contains both members’ tops, so (B) cannot hold: no alternative is ranked by a member above her own top. Suppose that (W) holds with x∈Tx \in T. Then x∉Fx \notin F, and both remaining alternatives belong to FF, because by Lemma 5 an option set of a two-voter coalition misses at most one alternative. Since every element of FF is ranked above xx by both members, both members rank xx last. As x∈Tx \in T, Lemma 5(ii), applied to the truthful report, gives t=12t = \frac{1}{2} and xx ▹\triangleright-maximal. But then, by Lemma 5, no report of the coalition has an option set that misses xx, contradicting x∉Fx \notin F. Hence there is no obvious group manipulation.

References

  1. [1]Arribillaga, R. P. and Bonifacio, A. G. (2024). Obvious manipulations of tops-only voting rules. Games and Economic Behavior, 143:12–24.arxiv.org/abs/2210.11627
  2. [2]Arribillaga, R. P. and Bonifacio, A. G. (2025a). Non-obvious manipulability in division problems with general preferences. arXiv preprint arXiv:2512.15024.arxiv.org/abs/2512.15024
  3. [5]Arribillaga, R. P., Bonifacio, A. G., and Fioravanti, F. (2026). Obvious manipulations by groups. Unpublished manuscript.
  4. [6]Arribillaga, R. P. and Pepa Risma, E. (2025). Obvious manipulations in matching with and without contracts. Games and Economic Behavior, 151:70–81.
  5. [7]Aziz, H. and Lam, A. (2021). Obvious manipulability of voting rules. In Algorithmic Decision Theory (ADT 2021), volume 13023 of Lecture Notes in Computer Science, pages 179–193. Springer.DOI
  6. [8]Barberà, S. (2011). Strategyproof social choice. In Arrow, K. J., Sen, A., and Suzumura, K., editors, Handbook of Social Choice and Welfare, volume 2, pages 731–831. Elsevier.DOI
  7. [9]Barberà, S., Berga, D., and Moreno, B. (2010). Individual versus group strategy-proofness: When do they coincide? Journal of Economic Theory, 145(5):1648–1674.
  8. [10]Barberà, S. and Dutta, B. (1982). Implementability via protective equilibria. Journal of Mathematical Economics, 10(1):49–65.DOI
  9. [11]Barberà, S., Gul, F., and Stacchetti, E. (1993). Generalized median voter schemes and committees. Journal of Economic Theory, 61(2):262–289.
  10. [12]Barberà, S., Sonnenschein, H., and Zhou, L. (1991). Voting by committees. Econometrica, 59(3):595–609.
  11. [13]Chatterji, S. and Sen, A. (2011). Tops-only domains. Economic Theory, 46(2):255–282.
  12. [14]Conitzer, V., Walsh, T., and Xia, L. (2011). Dominating manipulations in voting with partial information. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 25, pages 638–643.arxiv.org/abs/1106.5448
  13. [15]Dasgupta, P. and Maskin, E. (2008). On the robustness of majority rule. Journal of the European Economic Association, 6(5):949–973.
  14. [16]Dasgupta, P. and Maskin, E. (2020). Strategy-proofness, independence of irrelevant alternatives, and majority rule. American Economic Review: Insights, 2(4):459–474.DOI
  15. [17]de Keijzer, B., Schäfer, G., Tsikiridis, A., and Ventre, C. (2026). Breaking barriers, finding boundaries: Not obviously manipulable budget-feasible mechanism design. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 40, pages 16803–16811.
  16. [18]Demoor, L., Jané-Ballarín, M., Nunn, P., Pramanik, S., Pré votat, A., and Yokoo, M. (2026). Non-obvious manipulability with groups in Shapley–Scarf housing markets. arXiv preprint arXiv:2608.15631.
  17. [19]Doi, R., Ikeda, K., and Nakamura, K. (2026). Obvious group manipulations and top trading cycles. arXiv preprint arXiv:2611.13469.arxiv.org/abs/2611.13469
  18. [20]Endriss, U., Obraztsova, S., Polukarov, M., and Rosenschein, J. S. (2016). Strategic voting with incomplete information. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI 2016), pages 236–241.
  19. [21]Gibbard, A. (1973). Manipulation of voting schemes: A general result. Econometrica, 41(4):587–601.DOI
  20. [22]Kondratev, A. Y. and Nesterov, A. S. (2020). Measuring majority power and veto power of voting rules. Public Choice, 183(1–2):187–210.DOI
  21. [23]Le Breton, M. and Zaporozhets, V. (2009). On the equivalence of coalitional and individual strategy-proofness properties. Social Choice and Welfare, 33(2):287–309.
  22. [24]Lepelley, D. and Mbih, B. (1987). The proportion of coalitionally unstable situations under the plurality rule. Economics Letters, 24(4):311–315.
  23. [25]Li, S. (2017). Obviously strategy-proof mechanisms. American Economic Review, 107(11):3257–3287.
  24. [26]Moulin, H. (1980). On strategy-proofness and single peakedness. Public Choice, 35(4):437–455.DOI
  25. [27]Moulin, H. (1981). Prudence versus sophistication in voting strategy. Journal of Economic Theory, 24(3):398–412.
  26. [28]Moulin, H. (1988). Condorcet’s principle implies the no show paradox. Journal of Economic Theory, 45(1):53–64.DOI
  27. [29]Nakamura, K. (1979). The vetoers in a simple game with ordinal preferences. International Journal of Game Theory, 8(1):55–61.DOI
  28. [30]Ortega, J. and Segal-Halevi, E. (2022). Obvious manipulations in cake-cutting. Social Choice and Welfare, 59(4):969–988.
  29. [31]Pritchard, G. and Wilson, M. C. (2007). Exact results on manipulability of positional voting rules. Social Choice and Welfare, 29(3):487–513.
  30. [32]Psomas, A. and Verma, P. (2022). Fair and efficient allocations without obvious manipulations. In Advances in Neural Information Processing Systems 35 (NeurIPS 2022).arxiv.org/abs/2206.11143
  31. [33]Reijngoud, A. and Endriss, U. (2012). Voter response to iterated poll information. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2012), pages 635–644.
  32. [34]Satterthwaite, M. A. (1975). Strategy-proofness and Arrow’s conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, 10(2):187–217.DOI
  33. [35]Slinko, A. (2004). How large should a coalition be to manipulate an election? Mathematical Social Sciences, 47(3):289–293.DOI
  34. [36]Troyan, P. (2024). (Non-)obvious manipulability of rank-minimizing mechanisms. Journal of Mathematical Economics, 113:103015.
  35. [37]Troyan, P. and Morrill, T. (2020). Obvious manipulations. Journal of Economic Theory, 185:104970.
  36. [38]Young, H. P. (1975). Social choice scoring functions. SIAM Journal on Applied Mathematics, 28(4):824–838.DOI

Paper details

vlnc:W_qe9euxf2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Economics, Econometrics and Finance

Not recorded for this paper

View statement
Looking for related papers…
Contents