Group strategyproofness

Uses your system voice; voice and rate in settings.

Snapshot

≈ 5 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.…

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. Let N = \{1, \ldots, n\} be a set of agents, let A be a set of possible outcomes (or alternatives), and let each agent i have a preference P_i drawn from an admissible domain of preferences. A mechanism (or social choice function) is a map f that assigns to every profile of reported preferences (P_1, \ldots, P_n) an outcome f(P_1, \ldots, P_n) \in A . A mechanism f is individually strategyproof if for every agent i , every profile (P_1, \ldots, P_n) , and every alternative report P_i' , agent i does not strictly prefer the outcome obtained by reporting P_i' to the outcome obtained by reporting truthfully (holding the reports of the other agents fixed). A mechanism f is group-strategyproof (GSP) if there is no coalition S \subseteq N and no joint deviation (P_i')_{i \in S} such that, when the members of S jointly switch from their true preferences to their deviating reports (holding the reports of agents outside S fixed), every member of S is at least as well off and at least one member of 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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1378638407 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001378638407 · captured 1791191033.0 · version history

Cite this page as: encyclopegia.org, “Group strategyproofness”, snapshot enwiki-001378638407. https://encyclopegia.org/a/group-strategyproofness

Sources cited in this revision

3 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.