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 , 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 and (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 -NOMG if no coalition with at most 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 voters implies dictatorship (Proposition 4), and this bound is sharp: for every , 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 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 and (Proposition 5). Thus, for odd , the smallest manipulating coalition has exactly members; for even , its size is either or . For plurality, which is both tops-only and satisfies the majority criterion, the smallest such coalition has members (Proposition 6).
The configuration excluded from the majority results yields a positive result. When , the scoring rule with vector is NOMG if and only if (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 -NOMG if and only if two conditions on its fixed ballots hold for every coalition with at most 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 when , and strictly below when ; anonymous median voter schemes attain both bounds (Proposition 7). A voting by committees is -NOMG if and only if no coalition with at most members can force an object into or out of the outcome (Theorem 6), which requires ; among voting by quota, simple majority on each object gives the greatest protection (Corollary 2). For , 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 be the set of voters and let be the set of alternatives, with and . Each voter has a preference in the set of all strict linear orders on . We write if prefers to , and for her most preferred alternative, her top. A profile is . For a nonempty coalition , we write , and ; the voters in are the outsiders. A coalition is proper if it is nonempty and different from .
A voting rule selects an alternative at each profile. Throughout, rules are onto. A rule is efficient if there are no profile and alternative such that for every . It is dictatorial if there is a voter such that for every .
Voter can manipulate at if some report gives . 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 is a group manipulation for at if
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 of a nonempty coalition is the set of outcomes that remain possible once the coalition submits that report:
We write when the rule is understood. For a single voter this is the usual option set ; for the grand coalition it is the singleton . A report vetoes if , and it forces if ; a coalition can veto (can force) 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 be nonempty, let be the true preferences of its members, let be a report, and write and . The report is an obvious group manipulation for at if at least one of the following holds:
(W) there is such that for every and every ;
(B) there is such that for every and every .
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 , let be the set of elements of that are not Pareto dominated, for the members of , by another element of , and let be the set of elements of that do not Pareto dominate another element of . In their definition, is an obvious group manipulation at if some element of Pareto dominates every element of , or some element of is Pareto dominated by every element of . 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 Pareto dominates for if and only if for every . This relation is transitive, and therefore every element of a finite set is equal to, or dominated by, an element of , and is equal to, or dominates, an element of . It follows that their two conditions are equivalent to (B) and (W), respectively. For instance, if dominates every element of , then so does an element of that is equal to or dominates ; conversely, if dominates every element of , then it dominates every element of , so that (B) holds with . 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 , , , and be as in Definition 1.
(i) If is an obvious group manipulation for at , then there is such that is a group manipulation for at . Hence every group strategy-proof rule is NOMG.
(ii) For , is an obvious group manipulation at if and only if either the worst element of is preferred to the worst element of , or the best element of is preferred to the best element of , where worst and best refer to . Thus the absence of obvious manipulations by single voters is non-obvious manipulability in the sense of Troyan and Morrill [37].
(iii) For , is an obvious group manipulation at if and only if it is a group manipulation at . 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 , choose with ; then is strictly preferred to by every member. If (B) holds with , choose with ; then is strictly worse than for every member.
(ii) If some satisfies (W), then so does the worst element of . Hence (W) holds if and only if every element of , that is, the worst element of , is preferred to the worst element of . In the same way, (B) holds if and only if the best element of is preferred to the best element of .
(iii) For both option sets are singletons, and (W) and (B) both say that for every . If is not efficient, say for every , then since is onto there is with , a group manipulation by . Conversely, a group manipulation by 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 and are -indistinguishable if for every . Such rules have the same range, the union of the option sets of , so that is onto whenever 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 -indistinguishable voting rule. It thus extends to coalitions the characterization of obvious manipulations in Troyan and Morrill [37].5
Proposition 1. Let , let be nonempty and let . Then is an obvious group manipulation for at under if and only if, for every rule that is -indistinguishable from , there is an outsider profile such that
Proof. Write and . If , the only -indistinguishable rule is itself and both statements say that every member prefers to (Lemma 1). Assume .
Only if. Let be -indistinguishable from . If (W) holds with , choose with ; then is unanimously preferred to . If (B) holds with , choose with ; then is unanimously worse than .
If. Suppose neither (W) nor (B) holds. If , take . Otherwise, call a pair improving if for every . Since (W) fails, for every there is such that is not improving; since (B) fails, for every there is such that is not improving. Since , the number of outsider profiles is . Choose distinct outsider profiles and , and define by
by and at every remaining outsider profile , for a fixed , and by at all profiles at which reports neither nor . Then , , and all other option sets of are unchanged, so is -indistinguishable from . 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 -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 vote for represents the preference , and denotes the report of coalition at which every member votes for . With two alternatives, a rule is efficient if and only if it selects whenever all voters vote for , for each .
Proposition 2. Let and let be a nonempty coalition. Then has no obvious group manipulation if and only if, for each alternative :
(i) if some report of forces , then forces ; and
(ii) .
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 disagree, neither outcome is strictly better than the other for every member, so neither (W) nor (B) can hold. Suppose that all members prefer to the other alternative, , write , and let be the option set of a report of . Condition (W) holds if and only if and ; ruling this out for every report gives (i). Condition (B) holds if and only if and . Since the rule is onto, some report of leaves 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 shows that (ii) holds for every coalition, and (i) holds for because forces . 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 , let be odd, and let select if and only if an odd number of voters vote for . For every proper coalition and every report of , a single outsider can change the parity, so every option set of is and forces nothing. Since is odd, selects when all voters vote for and when all voters vote for , so is efficient. By Proposition 2, is NOMG. It is not strategy-proof: if voter , who prefers , and exactly one other voter vote for , the outcome is , and if switches to the outcome becomes .
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 and , and let select if voter 1 votes for and voter 2 votes for , and the alternative for which voter 3 votes otherwise. This rule is efficient. The coalition forces with the report at which voter 1 votes for and voter 2 votes for , but because voter 3 decides, so (i) fails. Concretely, let voters 1 and 2 prefer . If voter 2 switches to while voter 1 keeps her vote, the outcome is whatever voter 3 does. Since belongs to the truthful option set and both members prefer , 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 . For the equivalence with group strategy-proofness and the dictatorship result, we assume .
A rule is tops-only if whenever for every . 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 ; thus is the outcome when the vector of reported tops is , and is the option set of a vector of tops . For let be the set of reported tops, for let be the -support of , and let denote the report of at which every member reports . A tops-only rule is efficient if and only if for every : if the outcome is a reported top it cannot be Pareto dominated, and if is not a reported top, there are preferences with the reported tops at which every voter ranks some reported top above .
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 be tops-only and let be nonempty. The coalition has an obvious group manipulation, for some true preferences of its members, if and only if there are such that
(W′) some satisfies ; or
(B′) and .
Proof. Let be the tops of the true preferences, the tops of the report, and . If (W) holds with , then , and is not a member’s top because every member ranks the elements of above it; this is (W′). Conversely, given (W′), let every member rank her top first and last; then every element of is above for every member. If (B) holds with , then , and no member’s top is in , since otherwise would have to be ranked above that member’s top; this is (B′). Conversely, given (B′) and , let every member rank her top first, next (if it is different from her top), and the elements of below; since no top lies in , (B) holds.
Definition 2. Let be tops-only. A nonempty coalition satisfies the conditional veto if, whenever some report of vetoes an alternative , every report with vetoes .
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 be tops-only and let be a nonempty coalition. Then has no obvious group manipulation if and only if
(i) satisfies the conditional veto; and
(ii) every report of leaves open the top of at least one of its members: for every .
If 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, has no obvious group manipulation if and only if (W′) and (B′) fail for all . The failure of (W′) for all is the conditional veto. For (B′), note that the union of the option sets of is , because is onto. If contains none of the tops in , choose and a report with ; then , so (B′) holds. Conversely, if (ii) holds, then (B′) fails for every pair of reports.
Let be efficient, so that for every . For a proper coalition and a report , let the outsiders report the top of some member of ; the outcome lies in , so (ii) holds. For , , so (ii) holds and no alternative outside is left open, which gives (i). The last statement follows from Lemma 1(iii).
For a single voter, (i) implies (ii). Indeed, if reporting vetoed , then by the conditional veto every report of that voter would veto , which contradicts ontoness. For , 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 and let be an onto tops-only rule. The following are equivalent:
(i) is NOMG;
(ii) is efficient and every proper coalition satisfies the conditional veto;
(iii) is group strategy-proof;
(iv) is dictatorial.
Proof. (i)(ii). NOMG implies efficiency by Lemma 1(iii), and for efficient rules the equivalence is the last statement of Theorem 1.
(ii)(iii). We proceed in four steps.
Step 1: winning supports contain kernels. Let . Among the profiles of tops at which is selected and whose -support is contained in , choose one, , whose -support is minimal with respect to inclusion; is nonempty by efficiency. We claim that
If , the claim is that is selected when all voters report , which holds by efficiency. Otherwise, is a proper coalition whose report at avoids and leaves open. By the conditional veto, no report of vetoes . Let avoid and choose such that . The -support of is contained in , so by minimality it equals ; that is, .
Step 2: winning supports of different alternatives intersect. Let and with , and suppose that and are disjoint. Let and be given by Step 1, and choose , which is possible because . Consider the profile at which the members of report , the members of report , and every other voter reports . The voters outside avoid , so the outcome is by (1); the voters outside avoid , so the outcome is ; a contradiction. Step 3: kernels force their alternative. Let and let be given by Step 1. We claim that for every . If there is nothing to prove. Otherwise, suppose that for some . The -support of is contained in , whereas for any that avoids , the alternative is selected at with -support . This contradicts Step 2.
Step 4. Suppose that a coalition has a group manipulation at a profile with tops , which changes the outcome from to some . Every member strictly prefers to , so no member has top ; that is, . Let be given by Step 1. The members of keep reporting after the deviation, so by Step 3 the outcome is still , a contradiction.
(iii)(iv). A group strategy-proof rule is strategy-proof. Since is onto and , the Gibbard–Satterthwaite theorem implies that is dictatorial.
(iv)(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 and let if every voter reports , and otherwise. This rule is onto, tops-only and non-dictatorial. A voter who reports has option set , which contains her reported top. She can veto every alternative other than , 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 whenever more than voters rank first; a coalition with more than 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 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 , let be distinct alternatives, and suppose that can be partitioned into nonempty sets such that every union of two of them can force each of and . Then is OMG.
Proof. Consider the profile at which the members of , and rank in the orders , and , respectively, and all other alternatives below these three in a common order. Let . If , every voter ranks above , and can force while , so (W) holds with . If , every member of ranks above ; if , every member of ranks above ; if , every member of ranks above . In each case that union can force the alternative that it prefers, and (W) holds with .
Theorem 3. Let with . Every rule satisfying the majority criterion is OMG. In particular, every Condorcet-consistent rule is OMG.
Proof. If , partition into three nonempty sets of sizes as equal as possible; each has fewer than members (this fails only for ), so the union of any two has more than members and Proposition 3 applies. If , then ; consider the profile
with all other alternatives below these four in a common order. Each is ranked below its cyclic predecessor by three voters, and any alternative outside is ranked below by all four. Three voters can force the alternative that they prefer by ranking it first, so (W) holds with the alternative 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 , while rules satisfying the majority criterion cannot be NOMG when and . We now ask how large a coalition must be before an obvious manipulation becomes possible. This question applies to both classes. For , a rule is -NOMG if no coalition with at most members has an obvious group manipulation. Let denote the largest such , with if some single voter has an obvious manipulation. Thus if and only if is NOMG, and otherwise is the size of the smallest coalitions that can manipulate obviously. By Theorem 1, an efficient tops-only rule is -NOMG if and only if every proper coalition with at most 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 voters already implies dictatorship. The next proposition shows that neither efficiency nor the coalitions with members can be dispensed with. For and , the override rule selects if at least voters report , and selects otherwise. Since , at most one alternative is reported by voters, so is well defined: voter decides unless all other voters agree on a different alternative. Now assign the values to the different tops. The cyclic rule selects modulo .
Proposition 4. Let .
Every efficient, tops-only, -NOMG rule is dictatorial.
(ii) For every and , the override rule is efficient, tops-only, non-dictatorial and -NOMG.
(iii) For every , the cyclic rule is tops-only, non-dictatorial and -NOMG.
Consequently, for efficient tops-only rules, -NOMG implies dictatorship if and only if , and for tops-only rules in general if and only if .
Proof. (i) By Lemma 1(iii) the rule is NOMG; apply Theorem 2.
(ii) The outcome is always a reported top, so is efficient. It is not dictatorial. Voter is not a dictator: if all voters other than report , the outcome is . A voter is not a dictator either: fix an alternative and a voter , let and report two different alternatives other than , and let all other voters report ; no alternative is reported by voters, so the outcome is . By Theorem 1, it remains to check the conditional veto for every coalition with members. There are outsiders. For and , let be the number of members of who report .
If , let all outsiders, among them , report . Every is reported by at most voters, so the outcome is . Hence for every , and vetoes nothing.
If and reports , then
Indeed, if all outsiders report , no is reported by more than voters, so the outcome is ; and can be selected only if it is reported by voters, which the outsiders can achieve if and only if . If , then for every report and vetoes nothing. If and , then and , so vetoes . In both cases the conditional veto holds.
(iii) The rule is onto and tops-only. It is not dictatorial: for every voter , if some other voter reports and all remaining voters report , the outcome is modulo , which differs from . If is a proper coalition and , then for every report of the other voters, can choose so that the sum takes any prescribed value modulo . Hence every option set of equals , so satisfies both conditions of Theorem 1.
For the last statement, combine (i)–(iii) with the fact that -NOMG implies -NOMG for , and with Theorem 2 for .
The override rule shows where the proof of Theorem 2 needs large coalitions. Let the members of have true tops split between two alternatives and , and let . Truthful reporting leaves open, because voter may report , whereas the report forces ; if all members rank last, this is an obvious group manipulation of type (W). Thus . The cyclic rule has ; 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 with , and let satisfy the majority criterion. Then no coalition with fewer than members has an obvious group manipulation, and some coalition with exactly members has an obvious group manipulation of type (W). Consequently,
In particular, these conclusions hold for every Condorcet-consistent rule.
Proof. Let satisfy . For every report and every , the outsiders can rank first. Since they form a strict majority, the outcome is . Thus for every report, which rules out both (W) and (B).
For the upper bound, write . The construction in the proof of Theorem 3 provides a profile , an alternative , and a strict majority such that for every . Indeed, when , 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 to it. When and , the four-cycle construction gives three voters who prefer the predecessor of the selected alternative, or all four voters prefer if the outcome lies outside the cycle.
Choose with and let be any report at which every member ranks first. The original outsider profile gives , whereas the majority criterion gives . Since every member of strictly prefers to , condition (W) holds. The bounds on follow, and coincide when 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 : the proposition does not determine whether coalitions of that size can manipulate a given rule. The exception is essential, as the next section shows by exhibiting Condorcet-consistent Borda with .
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 select, among the alternatives reported as top by the largest number of voters, the highest one in a fixed strict priority over .
Proposition 6. Let . Plurality is -NOMG if and only if ; that is, . Coalitions of fewer than half of the voters have no obvious group manipulation, and some coalition with members has one.
Proof. Plurality is tops-only and efficient. Label the alternatives so that .
If , the outsiders outnumber the members of ; if they all report , then has more reports than any other alternative and wins. Hence every option set of is , vetoes nothing, and by Theorem 1 it has no obvious group manipulation.
Let , which is at most because , and let be a coalition with members. We exhibit a violation of the conditional veto.
If is even, equals the number of outsiders. Let every member report . If all outsiders report , then and tie with reports each and wins, so . If instead every member reports , then has reports and no other alternative has more, so wins every tie: , which vetoes although .
If is odd, and there are outsiders. Let members report and members report . If all outsiders report , then has reports and wins every tie, so belongs to the option set of this report, although no member reports it. If every member reports , then has reports, more than any other alternative can obtain, so the option set is , which vetoes . □ 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 , where and , awards points to an alternative for each voter who ranks it in position , and selects, among the alternatives with the highest total score, the highest one in a fixed strict priority . Since a positive affine transformation of does not change the rule, we normalize with ; plurality is and Borda’s rule is . These rules are onto, even for : to elect , 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 and . The scoring rule with vector is NOMG if and only if , that is, if and only if and .
The proof is in Appendix § 9. For , two voters with a common bottom alternative can remove it from their option set by agreeing on their top; for , three voters with a common preference can remove their second-ranked alternative by having one of them demote it; and for the rule is not efficient. Every rule in the interval satisfies the majority criterion: if three voters rank first, gets at least 3 points and every other alternative at most . 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 . For Condorcet consistency, use the equivalent vector : 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 ; the restricted domains only motivate the classes.
Median and generalized median voter schemes
Let be a set of consecutive integers, so that , and let . For write . Given fixed ballots in , the median voter scheme selects the median of the fixed ballots and the reported tops,
and we set and . For odd , 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 with members and a report , pool the reported tops with the fixed ballots, and order this list as . Then
Indeed, the outcome is the th smallest of numbers; it equals if all outsiders report and if all outsiders report , and it is nondecreasing in the outsiders’ reports. If all outsiders report an alternative , then at least of the numbers are at most and at least of them are at least , so the outcome is . In particular, if members report and the other members report , then
because the pooled list consists of copies of , the fixed ballots, and copies of .
Proposition 7. Let and let be a median voter scheme. Let be the number of fixed ballots that are at most , let be the number of fixed ballots that are at least , and let be the number of fixed ballots that belong to . Then
Equivalently, for , is -NOMG if and only if , , and at least fixed ballots belong to . Moreover, for there is a median voter scheme with if and only if when , and if and only if when .
Proof. A median voter scheme is anonymous and onto, hence not dictatorial, so by Theorem 2. Let and be the numbers of fixed ballots equal to and to , so that , and let be a coalition with members. By Theorem 1, has no obvious group manipulation if and only if it satisfies the conditional veto and every report of leaves open one of its tops.
Step 1: if , then satisfies the conditional veto. By (2), the lower endpoint of an option set is largest at the report , where it equals by (3), and the upper endpoint is smallest at the report , where it equals . Hence every option set of contains , and only and can be vetoed. By (2), belongs to an option set if and only if the pooled list contains at least copies of . Thus, if can veto , then , and every report in which no member reports vetoes . The argument for is the same, counting from the other end of the list.
Step 2: if , then violates the conditional veto. Reversing the order of the alternatives if necessary, let , so that and . The report vetoes , because the lower endpoint of its option set is . If , the report has option set , which contains because . If , let one member report and the other members report . By (3), the option set is , which contains : because , and because . In both cases a report in which no member reports leaves open.
Step 3: some report of a coalition with members leaves open none of its tops only if , and such a report exists if . Suppose that contains no top of , and let members have a top below and members a top above . Both numbers are positive: at least entries of the pooled list are at most the largest reported top, so does not exceed it, and at least entries are at least the smallest reported top, so is not below it. Fewer than entries of the pooled list are strictly below ; since , these entries include the low tops and the fixed ballots equal to , so , that is, . Symmetrically, fewer than entries are strictly above , so , that is, . Hence . Conversely, if , let members report and members report . By (3), the option set is , which contains neither nor .
By Steps 1–3, for the rule is -NOMG if and only if and . Since , this gives . The three inequalities in the statement express , and .
It remains to determine the attainable thresholds. If , no fixed ballot is counted by both and , so requires $2k \le L + H \le n - 1, place fixed ballots at and the other at ; then and . If , the fixed ballots equal to are counted by both and , so , and together with imply . Conversely, the previous construction works if ; if , place fixed ballots at each of and and the remaining at . Then and .
For example, if all fixed ballots are extreme alternatives, then , where and are the numbers of fixed ballots at and at . Balancing the two numbers gives the largest protection within this class: for odd , the median of the tops has , exactly as plurality (Proposition 6). Placing every fixed ballot at gives the rule that selects the smallest reported top, for which . The third term matters only for coalitions with at least two members: with three alternatives and , the median voter scheme with all fixed ballots equal to has and , so that single voters are protected, while two voters whose tops are the two extreme alternatives obtain 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 of elements of such that , , and whenever . The generalized median voter scheme is the tops-only rule
where the term for is . A preference is single-peaked if or implies . 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 and let . If a coalition is the union of disjoint sets and , one of which may be empty, denotes the report of at which the members of report and the members of report .
Lemma 3. Let be a generalized median voter scheme.
(i) For every and , if and only if . Consequently, is nondecreasing in each top, , and is onto.
(ii) Let be a proper coalition, let , and write and . Then , and every in this interval is the outcome when all outsiders report . Moreover, and are nondecreasing in , and .
(iii) Let a proper coalition be the union of disjoint sets and , one of which may be empty. Then . In particular, and , and can veto if and only if or .
Proof. (i) The term for is at most if and only if and (for the first condition is vacuous). If , the term for is at most . Conversely, if the term for some is at most , then and, by monotonicity, . Raising a top weakly shrinks every and therefore weakly raises every , so is nondecreasing in each top. For we have and , so ; for we have and , so . In particular for every .
(ii) By monotonicity every element of lies in . Conversely, let and let . Since and , part (i) gives . For we have , and , so part (i) gives . Hence . The monotonicity of and and the two bounds follow from part (i), applied to and .
(iii) At a profile at which the voters in a set report and all other voters report , we have for every with , so by part (i) the outcome is . Applying this with all outsiders at and with all outsiders at gives and , and the formula follows from part (ii). Taking and gives and . By part (ii), and for every . Hence belongs to every option set of if , while vetoes every and vetoes every .
A median voter scheme is the generalized median voter scheme with , which is a monotonic family of fixed ballots because and . Indeed, the median is at most if and only if at least fixed ballots are at most , that is, if and only if , which by Lemma 3(i) is the condition for .
Theorem 5. Let , let be a non-dictatorial generalized median voter scheme, and let . Then is -NOMG if and only if every coalition with satisfies
(i) and ; and
(ii) for every partition of into nonempty sets and , or .
Consequently, 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, is a nonempty coalition with at most members, so that is proper and Lemma 3 applies. By Theorem 1, is -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 if and only if cannot veto any alternative in .
Necessity of (i). Let be -NOMG, suppose that (i) fails for some coalition with at most members, and let be such a coalition that is minimal with respect to inclusion. Let be an alternative that can veto. Suppose first that has at least two members, and split it into two nonempty sets and . By minimality, (i) holds for and for , so and , and the option set contains . Since , this contradicts the conditional veto.
Hence for some voter . Suppose first that . The report vetoes , so by the conditional veto the report vetoes as well; since , this means that . Then vetoes , so the report must veto ; since , this means that . If instead , the same two implications, in the reverse order, give first and then . In both cases and , so by monotonicity whenever and whenever . By Lemma 3(i), if and only if , for every and . Hence for every , and is dictatorial, a contradiction.
Necessity of (ii). Let be -NOMG and let be partitioned into nonempty sets and . The report must leave open one of its tops, so contains or ; that is, or .
Sufficiency. Suppose that (i) and (ii) hold for every coalition with at most members, and fix such a coalition .
By (i), can veto at most and . If can veto , then by Lemma 3(iii). At any profile at which no member of reports , we have and therefore , so the outcome is at most by Lemma 3(i). Thus every report of that avoids vetoes . If can veto , then . At any profile at which no member of reports , we have and therefore , so the outcome is above . Thus every report of that avoids vetoes . Hence satisfies the conditional veto.
Finally, suppose that some option set contains no top of . By Lemma 3(ii), is at least the smallest top of and is at most the largest one, so the sets and are nonempty, and they partition . At the profile , whose outcome is , we have , so Lemma 3(i) gives . At the profile , whose outcome is , we have , so Lemma 3(i) gives . This contradicts (ii). Hence every report of leaves open one of its tops.
The last statement follows because by Theorem 2.
For a median voter scheme, where , conditions (i) and (ii) for all coalitions with at most 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 -NOMG, then when , and when . Indeed, let and suppose that . Choose with ; both and are nonempty and have at most members. Condition (i) for gives , and condition (i) for gives , so , a contradiction. Let , so that , and suppose that . Then , so there are disjoint coalitions and with , and has at most members. The coalitions and have members each, so condition (i) gives and , and (ii) fails for , a contradiction. By Proposition 7, both bounds are attained by median voter schemes.
Voting by committees
Let be a finite set of objects with (one object is the case of two alternatives of § 4), and let , so that and each top is a set of objects. A committee for is a nonempty family of nonempty coalitions, the winning coalitions for , such that and imply . Given , voting by committees is the tops-only rule
It is onto: since and , for every . Voting by quota is the case with for every , and we write . A preference is separable if, for every and , if and only if . 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 can force in if , and that it can force out if . By monotonicity of the committee, if can force in (out), then belongs (does not belong) to the outcome whenever all members of include in (exclude from) their tops, whatever the outsiders report.
Theorem 6. Let , let be a non-dictatorial voting by committees, and let . Then is -NOMG if and only if no coalition with at most members can force an object in or out. Consequently,
and .
Proof. Sufficiency. Suppose that no coalition with at most members can force an object in or out, and let be such a coalition and one of its reports. If all outsiders report a set of objects , the outcome is : every is supported by a coalition that contains , which is winning for , and every is supported by a subset of , which is not. Hence every option set of is , and has no obvious group manipulation.
Necessity. Let be -NOMG, suppose that some coalition with at most members can force an object in or out, and let be such a coalition that is minimal with respect to inclusion. We first show that can force every object in and out. Suppose that can impose a decision on an object : all sets of objects with the opposite decision on are then vetoed by the same report of . Let be one of these sets, let be another object, and let be the set obtained from by reversing the decision on only. Since , the conditional veto requires the report to veto . If all outsiders report , all voters agree on every object other than , and the outcome agrees with them on these objects. Since the outcome is not , the decision on is the one supported by the members of , against all outsiders. Choosing with shows that can force out, and choosing with shows that can force in. Applying the same argument with the roles of and exchanged shows that can force in and out as well.
If , then for every object the winning coalitions are exactly the coalitions that contain , so for every , and is dictatorial, a contradiction. Otherwise, split 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 , 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 can veto the empty set, because it can force an object in. This contradicts the conditional veto.
The threshold. The formula for restates the equivalence, because by Theorem 2. For the bound, take a coalition with members and an object . If the coalition is winning for , it can force in; otherwise its complement, which has members, can force out. Hence some coalition with at most members can force an object in or out, and .
Corollary 2. Let and let be a voting by quota. Then
Equivalently, for , is -NOMG if and only if for every .
Proof. Voting by quota is anonymous and onto, hence not dictatorial. The smallest coalitions that can force in have members, and the smallest coalitions that can force out have members. Apply Theorem 6.
The object with the lowest threshold determines the protection of the whole rule. A unanimity quota on a single object, , already gives . If every quota is , then . By Theorem 6, no non-dictatorial voting by committees protects coalitions with more than members, and by Corollary 2 the voting by quota that attain are precisely those with for every object. Thus an odd electorate has a unique optimal quota for each object, the simple majority quota , while an even electorate admits either of the two quotas and , independently across objects.
Remark 2. For , the results of this section are those obtained by Arribillaga and Bonifacio [1] for individual manipulations. Proposition 7 gives and ; Theorem 5 gives and for every ; Corollary 2 gives ; 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 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 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 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 , let be odd, and restrict preferences to the domain of single-peaked preferences with respect to the axis : true preferences, reports and option sets are all taken within this domain. Consider the tops-only rule that selects if all voters rank first, if an odd number rank first, and otherwise. This rule is anonymous and, on this domain, efficient. For every nonempty proper coalition ,
Since and remain attainable after every report, neither can witness a worst-case obvious manipulation; cannot do so either, since it is attainable truthfully only when all members rank it first. A best-case obvious manipulation would require making attainable when some member prefers or to it, which also fails. Efficiency handles the grand coalition, so the
rule is NOMG. However, if two voters have the preference and all others have , the outcome is , and either of the first two voters can obtain by reporting . Thus, the rule is not strategy-proof. On the universal domain the same rule is not efficient: if two voters have the preference and all others have , it selects , which every voter ranks below . 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 and , 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, , , , and denotes the total score of . For a coalition with members and a report , denotes the score that receives from the members of , and is the number of outsiders. We use three observations.
(a) Exclusion. If for some , then , since each outsider gives at most 1 point more than .
(b) Large coalitions. If , then has no group manipulation. Indeed, if the outcome changes from to with for every , then at each member gives at least more than , so the members give more than points more than , while the outsiders give at most more than ; hence at , contradicting .
(c) Raising the target. If wins at some outsider profile, it still wins after every outsider moves to the top of her ranking: the score of weakly increases, every other score weakly decreases, and the ties won by are still won. So, when checking whether , we may assume that all outsiders rank first.
Lemma 4. If , every option set of a single voter is .
Proof. Let the voter report , in this order. If all three outsiders report , the scores of are ; if all report , they are ; if all report , they are . The respective alternatives win strictly (the last one because ).
Lemma 5. Let and .
(i) If the two members rank different alternatives last, then .
(ii) If both members rank last, then when or is not -maximal, and 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 , it is not -maximal.
Proof. Let be an alternative that at least one member does not rank last, so that , and let both outsiders rank first, which gives . If neither of the other two alternatives receives 2 points from the members, each of them receives at most ; if the outsiders rank one of them second each, both end with at most . If one of them, say , receives 2 points from the members, both members rank first; the remaining alternative then receives at most points from the members, because at least one member ranks second. If both outsiders rank second, the scores of and are at most 2 and , both below . Hence . This proves (i) and shows that, in (ii), the two alternatives other than belong to .
It remains to consider in case (ii). Since both members rank last, , while the three scores add up to . If , the scores of the other two alternatives add up to more than 4, so one of them exceeds 2 and is not selected. If , the three scores add up to 6, so can be selected only if all three scores equal 2, and then only if is -maximal. Such a tie can be obtained. Let and be the other two alternatives. If both members rank first, let both outsiders report ; if the members rank and first, respectively, let the outsiders report and .
Proof of Theorem 4. The case . Label the alternatives so that is -minimal and let be the others. Let , let voter 1 have the preference and voter 2 the preference , so that on . If the outsiders report and , the scores are and wins, because ; so . Let both members report , so that . By (c), can win only if both outsiders rank it first, which gives the score 2 and the scores , or . In each case has at least 2 points, and wins a tie with because is -minimal. Hence is not in the option set of the new report, and (W) holds with , which both members rank last.
The case . Label the alternatives with , and let the members of have the common preference , so that . If the outsider reports , the scores are and wins (by priority when ), so . Let one member report while the others keep their ballots; then , and since and , (a) gives the option set . Condition (W) holds with .
The case . Let be -maximal. If every voter ranks some first and second, then and tie with score 4 and is selected, although every voter prefers . The rule is not efficient, hence OMG by Lemma 1(iii).
The case . For , all option sets equal (Lemma 4), so neither (W) nor (B) can hold. For , (b) with shows that there is no group manipulation, because ; by Lemma 1(i) there is no obvious group manipulation either. Let , with truthful option set and deviating option set . By Lemma 5, contains both members’ tops, so (B) cannot hold: no alternative is ranked by a member above her own top. Suppose that (W) holds with . Then , and both remaining alternatives belong to , because by Lemma 5 an option set of a two-voter coalition misses at most one alternative. Since every element of is ranked above by both members, both members rank last. As , Lemma 5(ii), applied to the truthful report, gives and -maximal. But then, by Lemma 5, no report of the coalition has an option set that misses , contradicting . Hence there is no obvious group manipulation.
References
- [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]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
- [5]Arribillaga, R. P., Bonifacio, A. G., and Fioravanti, F. (2026). Obvious manipulations by groups. Unpublished manuscript.
- [6]Arribillaga, R. P. and Pepa Risma, E. (2025). Obvious manipulations in matching with and without contracts. Games and Economic Behavior, 151:70–81.
- [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
- [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.
- [10]Barberà, S. and Dutta, B. (1982). Implementability via protective equilibria. Journal of Mathematical Economics, 10(1):49–65.DOI
- [11]Barberà, S., Gul, F., and Stacchetti, E. (1993). Generalized median voter schemes and committees. Journal of Economic Theory, 61(2):262–289.
- [12]Barberà, S., Sonnenschein, H., and Zhou, L. (1991). Voting by committees. Econometrica, 59(3):595–609.
- [13]Chatterji, S. and Sen, A. (2011). Tops-only domains. Economic Theory, 46(2):255–282.
- [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
- [15]Dasgupta, P. and Maskin, E. (2008). On the robustness of majority rule. Journal of the European Economic Association, 6(5):949–973.
- [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
- [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.
- [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.
- [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
- [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.
- [21]Gibbard, A. (1973). Manipulation of voting schemes: A general result. Econometrica, 41(4):587–601.DOI
- [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
- [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.
- [24]Lepelley, D. and Mbih, B. (1987). The proportion of coalitionally unstable situations under the plurality rule. Economics Letters, 24(4):311–315.
- [25]Li, S. (2017). Obviously strategy-proof mechanisms. American Economic Review, 107(11):3257–3287.
- [26]Moulin, H. (1980). On strategy-proofness and single peakedness. Public Choice, 35(4):437–455.DOI
- [27]Moulin, H. (1981). Prudence versus sophistication in voting strategy. Journal of Economic Theory, 24(3):398–412.
- [28]Moulin, H. (1988). Condorcet’s principle implies the no show paradox. Journal of Economic Theory, 45(1):53–64.DOI
- [29]Nakamura, K. (1979). The vetoers in a simple game with ordinal preferences. International Journal of Game Theory, 8(1):55–61.DOI
- [30]Ortega, J. and Segal-Halevi, E. (2022). Obvious manipulations in cake-cutting. Social Choice and Welfare, 59(4):969–988.
- [31]Pritchard, G. and Wilson, M. C. (2007). Exact results on manipulability of positional voting rules. Social Choice and Welfare, 29(3):487–513.
- [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
- [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.
- [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
- [35]Slinko, A. (2004). How large should a coalition be to manipulate an election? Mathematical Social Sciences, 47(3):289–293.DOI
- [36]Troyan, P. (2024). (Non-)obvious manipulability of rank-minimizing mechanisms. Journal of Mathematical Economics, 113:103015.
- [37]Troyan, P. and Morrill, T. (2020). Obvious manipulations. Journal of Economic Theory, 185:104970.