Group strategyproofness (GSP), also called coalitional strategyproofness, is a property of mechanisms and voting rules in social choice theory and mechanism design. A mechanism is group-strategyproof if no coalition of agents can all gain by jointly misreporting their private information: there is no group of agents and no joint deviation from truthful reporting that makes at least one member of the group strictly better off without making any other member of the group worse off. It is a strengthening of ordinary strategyproofness (also called individual strategyproofness, or SP), which only requires that no single agent can gain by misreporting. It also strengthens Pareto efficiency, which only requires that the set of all agents cannot gain by misreporting.

Group strategyproofness is desirable because individual strategyproofness alone does not protect a mechanism against coordinated behaviour. Even when no agent can profit by lying on their own, a group of agents who communicate and coordinate may be able to manipulate the outcome to their mutual advantage. Mechanisms that are merely individually strategyproof can therefore be vulnerable in settings where collusion is plausible, while group-strategyproof mechanisms are robust to such joint deviations.

Because every individual is a coalition of size one, group strategyproofness implies individual strategyproofness, but the converse does not hold in general. A central theme in the literature is identifying the conditions—on the domain of admissible preferences, or on the mechanism itself—under which the two properties coincide.

Formal definition

Let N = { 1 , … , n } {\displaystyle N=\{1,\ldots ,n\}} be a set of agents, let A {\displaystyle A} be a set of possible outcomes (or alternatives), and let each agent i {\displaystyle i} have a preference P i {\displaystyle P_{i}} drawn from an admissible domain of preferences. A mechanism (or social choice function) is a map f {\displaystyle f} that assigns to every profile of reported preferences ( P 1 , … , P n ) {\displaystyle (P_{1},\ldots ,P_{n})} an outcome f ( P 1 , … , P n ) ∈ A {\displaystyle f(P_{1},\ldots ,P_{n})\in A}.

A mechanism f {\displaystyle f} is individually strategyproof if for every agent i {\displaystyle i}, every profile ( P 1 , … , P n ) {\displaystyle (P_{1},\ldots ,P_{n})}, and every alternative report P i ′ {\displaystyle P_{i}'}, agent i {\displaystyle i} does not strictly prefer the outcome obtained by reporting P i ′ {\displaystyle P_{i}'} to the outcome obtained by reporting truthfully (holding the reports of the other agents fixed).

A mechanism f {\displaystyle f} is group-strategyproof (GSP) if there is no coalition S ⊆ N {\displaystyle S\subseteq N} and no joint deviation ( P i ′ ) i ∈ S {\displaystyle (P_{i}')_{i\in S}} such that, when the members of S {\displaystyle S} jointly switch from their true preferences to their deviating reports (holding the reports of agents outside S {\displaystyle S} fixed), every member of S {\displaystyle S} is at least as well off and at least one member of S {\displaystyle S} is strictly better off. This is the most common formulation, sometimes called the strong form of group strategyproofness.

A weaker condition called weak group-strategyproof (WGSP) requires only immunity to deviations in which every member of the coalition is made strictly better off. The strong form implies the weak form. The distinction is important: the weak form is equivalent to individual strategyproofness under quite general conditions, whereas the strong form is strictly more demanding and may require additional structure—such as a non-bossiness condition—to coincide with individual strategyproofness.

Examples

Group-strategyproof mechanisms

1. Serial dictatorship mechanisms, in which agents take turns choosing their most preferred still-available outcome, are GSP: because an agent's choice is unaffected by the choices of agents who come later, no coalition can engineer a deviation that strictly benefits one member without harming another.

2. When agents have single-peaked preferences, the median voting rule, as well as all generalized median voter schemes, are GSP: no coalition of agents can jointly shift the median in a direction that benefits all of them without harming at least one member.

3. The deferred acceptance algorithm for stable matching is weakly GSP for the proposing side (for the other side it is not even SP).

4. The Top trading cycles algorithm for housing markets, which computes the unique core (game theory) allocation, is weakly GSP.

5. In the context of budget-proposal aggregation, when agents have Leontief utilities, the Nash welfare rule (maximizing the product of utilities) is GSP.

6. Barberà, Berga and Moreno showed that a common structural argument establishes GSP for solutions to matching, division, cost sharing, house allocation and auction problems, unifying many previously separate results under a single framework based on connectedness of the preference domain. The same authors also characterized GSP social choice functions whose range consists of two alternatives over arbitrary domains.

Mechanisms that are strategyproof but not group-strategyproof

The gap between individual and group strategyproofness is real: there exist mechanisms that are individually strategyproof but not group-strategyproof.

1. The Vickrey auction is SP, but it is not GSP. The two agents with the highest values can manipulate by having the second-highest value agent report a lower value. This will not harm the manipulator, but help the winner (at the expense of the auctioneer). The same The Japanese auction (ascending auction) is even obviously strategyproof, but not GSP, due to the same reason.

2. Voting by committees,[clarification needed] on the domain of separable preferences over a hypercube of alternatives, the setting characterized by Barberà, Sonnenschein and Zhou. Many rules in this class are SP but admit profitable joint deviations by coalitions. The reason is that separable preferences over several binary issues are not "tightly enough" linked across agents: a coalition whose members have correlated stakes across different issues can trade support—each member conceding on issues they care little about in exchange for a favourable outcome on issues they care about—producing a joint deviation that benefits all of them, even though no member could gain by deviating alone.

When does SP imply GSP?

A strand of research asks when individual SP is already sufficient to guarantee GSP, so that the two coincide.

Le Breton and Zaporozhets introduced a sufficient condition based on the richness of the preference domain. Roughly, a domain is rich if it contains "enough" preferences, connected to one another by small local changes, so that any change of preference can be decomposed into elementary steps to which the strategyproofness condition can be applied. On a rich domain, every individually strategyproof rule (satisfying mild regularity conditions) is GSP. The authors illustrate the result with the problem of allocating a fixed budget among several pure public goods.

Barberà, Berga and Moreno generalized this with a weaker and more precise condition called sequential inclusion. For a fixed preference profile and an ordered pair of alternatives y , z {\displaystyle y,z}, consider the set of agents who strictly prefer y {\displaystyle y} to z {\displaystyle z}, and define a binary relation on this set by comparing agents' lower contour sets: agent i {\displaystyle i} precedes agent j {\displaystyle j} when the set of alternatives i {\displaystyle i} ranks at or below z {\displaystyle z} is contained in the set of alternatives j {\displaystyle j} ranks at or below y {\displaystyle y}. The profile satisfies sequential inclusion if, for every pair of alternatives, this relation is complete and acyclic. A domain satisfies the condition if every profile does. On such a domain, individual and group strategyproofness coincide. The condition can fail in two ways: by incompleteness (two agents whose lower contour sets are not nested in either direction) or by cyclicity (a cycle in the relation). Both authors prove that richness in the sense of Le Breton and Zaporozhets is a special case, so the sequential-inclusion framework subsumes the earlier result.

Where the condition holds

When there are at most three alternatives, every profile automatically satisfies sequential inclusion, so SP implies GSP with no further domain restriction; the property can only fail once there are four or more alternatives.

The condition also holds on the domain of single-peaked preferences: for any pair of alternatives, ordering the agents by the position of their peaks makes the relevant lower contour sets nest cleanly, so the comparison relation is complete and acyclic. This explains why the median rule and the generalized median voter schemes, which are SP on the single-peaked domain, are automatically GSP there. A further useful feature of the (direct) condition is that it is inherited by subdomains: if it holds on a domain, it holds on every subdomain.

A subtler case is the domain of lexicographically separable preferences: it is too large to satisfy the direct form of the condition but small enough to satisfy an indirect version, so the SP rules on it turn out to be GSP after all.

Where the condition fails

The two failure modes can be illustrated with small concrete profiles, following Barberà, Berga and Moreno.

Failure by incompleteness. Let the alternatives be { x , y , z , w } {\displaystyle \{x,y,z,w\}} and consider two agents with the preference orderings (listed best to worst)

agent 1: x ≻ y ≻ z ≻ w {\displaystyle x\succ y\succ z\succ w},

agent 2: w ≻ y ≻ z ≻ x {\displaystyle w\succ y\succ z\succ x}.

Take the ordered pair y , z {\displaystyle y,z}. Both agents strictly prefer y {\displaystyle y} to z {\displaystyle z}, so both belong to the relevant set. The lower contour set of z {\displaystyle z} for agent 1 is { z , w } {\displaystyle \{z,w\}}, while the lower contour set of y {\displaystyle y} for agent 2 is { y , z , x } {\displaystyle \{y,z,x\}}; since w {\displaystyle w} belongs to the former but not the latter, agent 1 does not precede agent 2. Symmetrically, the lower contour set of z {\displaystyle z} for agent 2 is { z , x } {\displaystyle \{z,x\}} and the lower contour set of y {\displaystyle y} for agent 1 is { y , z , w } {\displaystyle \{y,z,w\}}; since x {\displaystyle x} belongs to the former but not the latter, agent 2 does not precede agent 1. The two agents are therefore incomparable, the relation is incomplete, and sequential inclusion fails. (At least four alternatives are needed to construct such a failure.)

Failure by cyclicity. Let the alternatives be { x , y , z , w , t } {\displaystyle \{x,y,z,w,t\}} and consider three agents with the orderings

agent 1: x ≻ y ≻ w ≻ z ≻ t {\displaystyle x\succ y\succ w\succ z\succ t},

agent 2: w ≻ y ≻ t ≻ z ≻ x {\displaystyle w\succ y\succ t\succ z\succ x},

agent 3: t ≻ y ≻ x ≻ z ≻ w {\displaystyle t\succ y\succ x\succ z\succ w}.

For the ordered pair y , z {\displaystyle y,z}, all three agents strictly prefer y {\displaystyle y} to z {\displaystyle z}. Comparing lower contour sets pairwise yields that agent 1 precedes agent 2, agent 2 precedes agent 3, and agent 3 precedes agent 1. The relation is thus complete but contains a cycle, so sequential inclusion again fails. When the comparison relation cycles in this way there is no consistent order in which a coalition's joint deviation can be unwound into individual deviations, which is exactly where a strategyproof but group-manipulable rule can exist.

The condition fails on the domain of separable preferences over a hypercube, consistent with the existence of SP but group-manipulable voting-by-committees rules described above.[clarification needed]

It also fails for natural multidimensional domains. A concrete and important example is the domain in which the outcomes form a simplex (for instance the set of probability distributions or budget shares that sum to one), each agent's preference is determined by an ideal point or "peak" in the simplex, and utility decreases with the Euclidean distance from the peak. This is the multidimensional analogue of single-peakedness, but once the simplex has dimension two or more (a triangle or larger) sequential inclusion is violated. The reason is geometric: an agent's lower contour set is a Euclidean ball centred at the agent's peak, and containment between balls with different centres is a genuinely partial relation. It is straightforward to place the peaks of two agents so that neither agent's lower contour set is contained in the other's, which makes the comparison relation incomplete; three suitably placed peaks can instead produce a cycle. The same multidimensional obstruction underlies the broader fact that on such domains there is a tension between strategyproofness, efficiency and the constraint that outcomes remain on the simplex.[clarification needed]

This connects to the structural theory of strategyproof rules on multidimensional domains. Border and Jordan showed that on separable multidimensional domains a rule is strategyproof essentially if and only if it decomposes into independent one-dimensional rules, each a generalized median. Such decomposable rules are group-strategyproof, but the decomposition requires the range to be a product (box-shaped) set, a requirement the simplex does not meet because its coordinates are constrained to sum to one. Nehring and Puppe placed these results in a common framework: they showed that strategyproof rules on generalized single-peaked domains are exactly "voting by issues" satisfying an "Intersection Property", and that the domains admitting the richest class of well-behaved (non-dictatorial, anonymous, neutral) strategyproof rules are precisely the median spaces—spaces in which every triple of elements has a median element lying between each pair. A simplex under the Euclidean metric is not a median space, which gives a unified explanation for the failure of the various positive results on that domain.

See also