Fact-checked by Grok 2 weeks ago

Strategyproofness

Strategyproofness is a core property in mechanism design requiring that a mechanism's rules render truthful reporting of an agent's private valuations or preferences a weakly dominant strategy, irrespective of others' reports, such that no agent can strictly improve their utility by submitting a false report.^[1] This condition, formally expressed as v_i(Outcome(v_i,v_{-i})) + Payment_i(v_i,v_{-i}) \geq v_i(Outcome(v_i',v_{-i})) + Payment_i(v_i',v_{-i}) for all agents i, valuations v_i, v_i', and others' reports v_{-i}, ensures robustness against strategic manipulation and aligns individual incentives with efficient or desirable collective outcomes.^[2] In social choice settings, the Gibbard-Satterthwaite theorem proves that no non-dictatorial voting rule over three or more alternatives can be strategyproof while satisfying Pareto optimality and surjectivity (ability to select any alternative as winner), underscoring inherent manipulability in aggregating ordinal preferences.^[3] Despite such impossibilities on unrestricted domains, strategyproof mechanisms are attainable via randomization, restricted preference domains, or additional instruments like payments, with practical implementations in Vickrey-Clarke-Groves auctions for truthful bidding in procurement and resource allocation, and in serial dictatorship for assignment problems.^[4] These designs prioritize causal incentive alignment over full efficiency, revealing trade-offs where empirical violations of strategyproofness in real-world systems often stem from bounded rationality or incomplete information rather than pure strategic deviation.^[5]

Core Concepts and Definitions

Formal Definition of Strategyproofness

In mechanism design, strategyproofness, also known as dominant-strategy incentive compatibility, requires that truth-telling constitutes a weakly dominant strategy for every participant in a direct revelation mechanism, irrespective of others' reports.^[6]^[7] This property ensures no agent can strictly increase their utility by misreporting their private valuation, given quasilinear preferences where utility decomposes into valuation of the selected outcome minus any payment (or plus net transfer received).^[4] Formally, let there be n agents indexed by i = 1, \dots, n, an outcome space X, and for each agent i, a private valuation function v_i: X \to \mathbb{R}_+ drawn from a type space V_i. A direct mechanism specifies an outcome rule \text{Outcome}: V \to X, where V = V_1 \times \cdots \times V_n, and payment rules p_i: V \to \mathbb{R} for each i, yielding quasilinear utility u_i(v_i, v) = v_i(\text{Outcome}(v)) + p_i(v).^[8] The mechanism is strategyproof if, for all i, all true v_i \in V_i, all deviations v_i' \in V_i, and all v_{-i} \in V_{-i}, This inequality holds with weak preference (\geq), allowing indifference but prohibiting strict gain from deviation.^[9]^[10] In non-quasilinear settings, such as pure social choice without transfers, strategyproofness adapts to ordinal or cardinal preferences over outcomes alone, requiring truthful reporting to maximize the probability or expected utility of preferred outcomes without side payments.^[6] The definition assumes complete information revelation in direct mechanisms; indirect mechanisms inherit the property via the revelation principle, which equates strategyproof implementability to direct strategyproofness under dominant strategies.^[4]

Distinction from Incentive Compatibility and Truthfulness

Strategyproofness, equivalently termed dominant-strategy incentive compatibility (DSIC), mandates that for each agent i, reporting their true type v_i maximizes their expected utility regardless of the reports submitted by other agents, formalized as u_i(v_i, v_{-i}) \geq u_i(v_i', v_{-i}) for all v_i, v_i', v_{-i}, where u_i denotes agent i's utility from outcome and payments.^[11] This dominant-strategy property ensures robustness against unilateral deviations without requiring coordination or probabilistic beliefs about others' behavior.^[12] Incentive compatibility, by contrast, encompasses weaker equilibrium concepts such as Bayesian incentive compatibility (BIC), under which truthful reporting forms a Bayesian Nash equilibrium: agents optimize expected utility conditional on their prior beliefs about others' types and assuming others adhere to equilibrium strategies.^[11] BIC relies on common priors over type distributions and rational expectations, permitting mechanisms where deviations could profit if others deviate or beliefs are misspecified, whereas DSIC precludes such vulnerabilities ex post.^[13] For instance, the first-price auction exemplifies BIC but violates DSIC, as bidders shade bids below true values under equilibrium play.^[11] Truthfulness aligns precisely with strategyproofness in direct revelation mechanisms, denoting the incentive for agents to disclose private valuations veraciously as a dominant strategy, thereby eliminating strategic misrepresentation in type reporting.^[14] While terminology occasionally overlaps—some contexts apply "incentive compatible" broadly to DSIC—the distinction underscores strategyproofness's stricter guarantee of individual optimality independent of strategic interdependence.^[15] This hierarchy implies DSIC mechanisms satisfy BIC (under independent private values), but the converse fails generally, motivating preference for strategyproof designs in settings demanding ex post robustness, such as public good provision or auctions with uncertain participant strategies.^[16]

Historical Foundations

The concept of strategyproofness, ensuring that individuals have no incentive to misrepresent their preferences in collective decision-making, emerged from social choice theory's examination of voting systems and preference aggregation. Social choice theory, formalized in the mid-20th century, built on earlier probabilistic and positional voting methods proposed by figures such as Marquis de Condorcet in the 1780s and Jean-Charles de Borda around 1770, who recognized practical vulnerabilities to tactical voting but lacked game-theoretic analysis. Kenneth Arrow's 1951 impossibility theorem demonstrated that no non-dictatorial social welfare function could satisfy unanimity, independence of irrelevant alternatives, and Pareto efficiency over unrestricted ordinal preferences, implicitly highlighting tensions with strategic behavior, though Arrow focused on sincere aggregation rather than dominant strategies. Explicit attention to manipulability as a strategic deviation gained traction in the 1960s through game-theoretic modeling of voting. In their 1961 paper "Stability in Voting," Michael Dummett and Robin Farquharson framed voting as an n-person non-cooperative game under majority rule with ordinal preferences, introducing a stability condition weaker than full strategyproofness—requiring that sincere voting equilibria resist unilateral deviations under certain preference restrictions. They conjectured that no voting procedure satisfying basic fairness properties, such as non-dictatorship and onto coverage of outcomes, could be fully stable against manipulation in general preference profiles, anticipating later impossibility results.^[17] Farquharson advanced this framework in his 1969 monograph Theory of Voting, treating voting procedures as extensive-form games where voters sequentially or simultaneously submit ordinal rankings, and analyzing equilibria via backward induction to reveal "sophisticated" strategic voting—iterative best responses anticipating others' manipulations. This work formalized non-manipulability as resistance to profitable deviations in such games, distinguishing it from Arrowian sincerity assumptions, and identified limited domains (e.g., single-peaked preferences) where strategyproof rules like the median voter exist, influencing subsequent characterizations. These contributions shifted social choice from axiomatic non-strategic aggregation toward incentive-compatible mechanisms, setting the stage for rigorous proofs of general impossibilities.^[18]

Gibbard-Satterthwaite Theorem

The Gibbard–Satterthwaite theorem establishes that no non-dictatorial social choice function can be strategyproof when there are at least three alternatives and voters possess unrestricted strict linear preferences over those alternatives. Formally, consider a set of voters N with |N| \geq 1 and a set of alternatives A with |A| \geq 3. A social choice function f maps profiles of strict total orders on A to elements of A. The function is strategyproof if, for every voter i \in N, every profile of preferences R = (R_i, R_{-i}), and every alternative preference R_i' for i, the outcome f(R) is at least as preferred as f(R_i', R_{-i}) under R_i. It is onto if every alternative in A is selected for some preference profile, and non-dictatorial if no single voter i has their most preferred alternative chosen by f for every profile. The theorem proves that no such f satisfying all three properties exists.^[19] The result was independently proven by Allan Gibbard in a 1973 article demonstrating that any manipulable voting scheme with at least three outcomes admits individual strategic manipulation under unrestricted preferences, implying the dictatorial characterization. Mark Satterthwaite arrived at the same conclusion in 1975, linking strategyproofness to Arrow's impossibility conditions and showing that strategyproof voting procedures correspond to dictatorial social welfare functions when onto. These proofs built on earlier conjectures, such as those by Duncan Black and Peter Fishburn, but provided the general impossibility for ordinal voting mechanisms without interpersonal utility comparisons.^[20]^[21] Proofs of the theorem typically proceed by contradiction, assuming a strategyproof, onto, non-dictatorial f. One identifies a pivotal voter r whose reported preference can determine the outcome between any two alternatives a, b \in A by varying profiles where others unanimously prefer one over the other. Strategyproofness then forces f to select r's top-ranked alternative in unanimous profiles, extending to dictatorship via onto coverage: for any profile, construct deviations showing r's preference dictates the result without profitable manipulation. This holds under unanimity (implied by onto for strict preferences), as violating it would allow manipulation. Simpler variants, such as Benoît's 2000 proof, emphasize the pivotal role and leverage strategyproofness to equate the function to the dictator's choice across profiles.^[19] The theorem underscores inherent trade-offs in voting design, explaining manipulability in deterministic ordinal mechanisms but exempting cases with two alternatives (where median or majority rules are strategyproof) or restricted domains. It applies strictly to non-probabilistic rules; randomized variants may evade full impossibility but introduce other incentive issues. Empirical voting analyses, such as coalitional manipulation studies, align with its predictions, showing even prominent rules like plurality or Borda susceptible to individual strategy in multi-candidate settings.^[19]

Impossibility Results and Trade-offs

General Impossibility in Unrestricted Domains

In settings with an unrestricted domain of preferences—where each of the n \geq 2 agents may hold any strict ordering over a finite set of at least three alternatives X—no non-dictatorial social choice function that is onto (i.e., selects every alternative x \in X as the outcome for at least one preference profile) can be strategyproof.^[22]^[19] This result holds for direct mechanisms without side payments, revealing that truthful reporting cannot be a dominant strategy unless one agent's preferences unilaterally determine the outcome regardless of others' reports. The theorem's proof typically proceeds by contradiction: assuming a non-dictatorial, onto, strategyproof function f, there exists an agent i whose report influences the outcome between some pair of alternatives, allowing construction of a preference profile where i can manipulate by misreporting to pivot the result in their favor without violating strategyproofness for others, leading to a decisiveness cycle that contradicts onto-ness or non-dictatorship.^[19]^[24] Unrestricted domains exacerbate this vulnerability because arbitrary preferences permit such manipulations; for instance, with |X| = 3 (say alternatives a, b, c), profiles can be arranged where unanimous preference for a over b coexists with manipulations shifting from c to a.^[25] This impossibility underscores the tension in collective decision-making without structural constraints on preferences, implying that strategyproofness demands either dictatorship (violating fairness) or domain restrictions (e.g., single-peaked preferences) to enable non-trivial mechanisms.^[22] Extensions to set-valued outcomes or hyperfunctions yield analogous dictatorial characterizations, confirming the robustness of the result across generalized social choice settings.^[26]

Conflicts with Efficiency and Other Desirable Properties

In settings without monetary transfers, strategyproofness frequently conflicts with Pareto efficiency and properties like equal treatment or surjectivity. The Gibbard-Satterthwaite theorem establishes that non-dictatorial strategyproof social choice functions cannot be surjective over unrestricted preference domains with at least three alternatives, limiting their ability to select all Pareto-efficient outcomes that might be demanded by diverse preferences.^[27] Dictatorial rules, while strategyproof and satisfying weak Pareto optimality (as the dictator's preference aligns with unanimous improvements), fail anonymity and equal treatment, as only one agent's ranking determines the outcome regardless of collective welfare considerations.^[28] In probabilistic mechanisms for random assignment or object allocation, stronger incompatibilities arise. Strategyproofness cannot coexist with ex ante Pareto efficiency and equal treatment of equals when assigning indivisible goods without money, as proven by Zhou (1990); any such mechanism must resort to random dictatorships, which dilute efficiency by ignoring aggregate preferences.^[29] Similar trade-offs appear in matching domains with indifferences, where strategyproofness for one side (e.g., students in school choice) precludes Pareto improvements or stability, as observed in the New York City high school matching redesign, where no mechanism fully satisfies strategyproofness, stability, and efficiency simultaneously.^[30] With monetary transfers in quasilinear environments, strategyproofness aligns with efficiency via mechanisms like Vickrey-Clarke-Groves (VCG), which maximize social surplus but violate budget balance by generating deficits or surpluses.^[31] The Green–Laffont impossibility theorem demonstrates that no mechanism can achieve dominant-strategy strategyproofness, Pareto efficiency (or VCG efficiency), and weak budget balance simultaneously for public decisions with at least two agents and non-trivial type spaces, as transfers required for truth-telling disrupt fiscal neutrality.^[31] This forces designers to relax one property, such as accepting deficits in efficient auctions or sacrificing efficiency for balanced mechanisms like fixed-price sales. Strategyproofness also clashes with individual rationality in fractional or probabilistic allocations. For fractional matching problems, no rule satisfies strategyproofness, ex post Pareto efficiency, and ex ante individual rationality, as agents could gain by misreporting to access better lotteries despite participation constraints.^[29] In cost-sharing or assembly problems, strategyproof, efficient, and budget-balanced mechanisms often fail ex post individual rationality, requiring subsidies or inefficiencies to ensure voluntary compliance.^[32] These conflicts underscore the need for domain-specific relaxations, such as approximate strategyproofness, to approximate multiple desiderata.^[33]

Characterizations and Structural Results

Gibbard's Characterization via Outcome Functions

In 1977, Allan Gibbard provided a structural characterization of strategyproof randomized social decision schemes (SDS), which map profiles of voters' strict ordinal preferences over a finite set of alternatives to probability distributions (lotteries) over those alternatives.^[34] A randomized SDS is strategyproof if, for every voter, truthful reporting maximizes their expected utility, where utilities are any von Neumann-Morgenstern representation consistent with their ordinal preference (i.e., higher-ranked alternatives yield strictly higher utility). Gibbard demonstrated that every such strategyproof SDS is a convex combination (probabilistic mixture) of deterministic unilateral schemes and duple schemes.^[34] ^[35] Unilateral schemes are those in which the outcome lottery depends solely on the preference ordering of a single designated voter (a "dictator"), with the probabilities assigned to alternatives fixed independently of other voters' reports; variations across the dictator's possible preferences yield the overall randomization.^[34] This structure ensures strategyproofness because non-dictators have no influence, eliminating incentives to manipulate, while the dictator's best response is always truthful under the assumed utility representations. Duple schemes, by contrast, fix two alternatives a and b, assigning positive probability only to these (or deterministic outcomes thereof) unless overridden by unanimity; specifically, the probability of a (or b) adjusts based solely on whether all voters unanimously rank one above the other relative to the pair, with intermediate unanimous subsets yielding fixed probabilities independent of detailed preference profiles beyond the a-b comparison.^[34] This limits manipulability by restricting outcomes to binary lotteries that respect unanimous consensus without allowing finer strategic deviations to shift probabilities in a beneficial direction for any single voter. The outcome function in a strategyproof SDS under Gibbard's characterization thus decomposes into these atomic components, implying that non-trivial strategyproof randomization cannot escape dictatorial elements or pairwise fixed lotteries without violating incentive compatibility. For instance, if a strategyproof SDS is also onto (every alternative receives positive probability for some preference profile) and satisfies Pareto optimality (no alternative Pareto-dominates the chosen lottery), it must reduce to a random dictatorship—a uniform mixture over unilateral schemes for each voter.^[34] ^[36] This result underscores the limited scope for non-dictatorial strategyproof mechanisms even in randomized settings, extending the deterministic impossibility of the Gibbard-Satterthwaite theorem while highlighting the role of outcome functions in enforcing truthfulness through restricted dependence on reported preferences. Empirical applications in voting theory confirm that real-world randomized rules deviating from these forms often admit manipulable equilibria, as deviations can exploit the expanded outcome space.^[37]

Mechanisms in Single-Parameter Settings

In single-parameter settings of mechanism design, each agent i reports a private scalar parameter v_i \in \mathbb{R}_+, representing their valuation for a share of the outcome, with quasilinear utility u_i(\mathbf{v}) = v_i \cdot x_i(\mathbf{v}) - p_i(\mathbf{v}), where \mathbf{v} = (v_i, \mathbf{v}_{-i}), x_i(\mathbf{v}) \in [0,1] denotes the expected allocation (e.g., probability of receiving the good or fraction allocated), and p_i(\mathbf{v}) is the expected payment extracted from agent i. A direct mechanism (\mathbf{x}(\mathbf{v}), \mathbf{p}(\mathbf{v})) is strategyproof if, for every i, \mathbf{v}_{-i}, and v_i, v_i', reporting truthfully yields at least as high utility as misreporting: v_i x_i(v_i, \mathbf{v}_{-i}) - p_i(v_i, \mathbf{v}_{-i}) \geq v_i x_i(v_i', \mathbf{v}_{-i}) - p_i(v_i', \mathbf{v}_{-i}).^[14] This formulation assumes normalization where agents with v_i = 0 receive zero utility, individual rationality, and no positive transfers among agents. Strategyproof mechanisms in these domains are fully characterized: the allocation rule x_i must be monotone non-decreasing in v_i for each fixed \mathbf{v}_{-i}—that is, higher reported valuations cannot decrease an agent's allocation probability—and payments must satisfy the formula p_i(v_i, \mathbf{v}_{-i}) = v_i x_i(v_i, \mathbf{v}_{-i}) - \int_0^{v_i} x_i(t, \mathbf{v}_{-i}) \, dt. This payment rule, derived from the envelope theorem applied to the indirect utility function, ensures that the marginal benefit of misreporting is zero under monotonicity, preventing profitable deviations. The result holds for Bayesian incentive compatibility in dominant strategies and extends to settings with combinatorial constraints on allocations, such as knapsack or scheduling problems where v_i scales a base cost or size parameter.^[38]^[14] This characterization facilitates mechanism design by decoupling allocation from payments: designers select any feasible monotone allocation (e.g., via greedy algorithms respecting supply constraints) and compute payments post-hoc to enforce truthfulness. For instance, in unlimited-supply digital goods auctions, posting a fixed price yields monotonicity (buy if v_i \geq price), with zero payments for non-buyers and price payments for buyers matching the integral. In single-item auctions, allocating to the highest bidder (monotone) and charging the second-highest bid (equivalent to the critical value where allocation changes) produces the Vickrey mechanism, which is strategyproof and individually rational. Violations of monotonicity, such as non-monotone rules in multi-unit settings, fail strategyproofness even with adjusted payments, as shown in analyses of combinatorial auctions.^[14]^[39] Extensions to multi-agent problems with single parameters, like digital spectrum allocation or cloud resource provisioning, leverage this framework for truthful implementations, often approximating optimal welfare or revenue under monotonicity constraints. Empirical implementations, such as Google's sponsored search auctions circa 2002, adapted these principles for single-parameter bids scaled by click-through rates, ensuring dominant-strategy truthfulness amid real-time bidding.^[14]

Examples in Specific Domains

Network Routing and Resource Allocation

In communication networks, particularly mobile ad hoc networks (MANETs) and wireless selfish environments, nodes often act strategically by misreporting link costs, capacities, or forwarding willingness to minimize their own energy expenditure or maximize utility, potentially degrading overall network performance. Strategyproof routing mechanisms mitigate this by incentivizing truthful reporting through payments or penalties, typically drawing on the Vickrey-Clarke-Groves (VCG) framework, which ensures dominant-strategy truthfulness by charging agents the externality they impose on others.^[40]^[41] A canonical application is the Ad hoc-VCG protocol, proposed by Anderegg and Eidenbenz in 2003, which adapts VCG for unicast routing in MANETs with selfish nodes. In this reactive protocol, upon a source node's session request, intermediate nodes report private transmission costs; the mechanism computes the shortest-path tree based on these reports, routes packets along it, and compensates forwarding nodes via VCG payments equal to the cost difference between the chosen path and the lowest-cost alternative excluding that node. This structure guarantees strategyproofness, as any deviation in cost reporting cannot increase a node's net utility (valuation minus payment), while approximating system-optimal routing under truthful behavior; simulations indicate it reduces overhead compared to non-truthful protocols like AODV by enforcing participation incentives.^[40]^[42] Extensions to multicast routing in selfish wireless networks, such as the mechanisms developed by Wang, Li, and Sheng in 2004, extend truthful incentives to tree-based structures without full VCG reliance to curb payment inflation. These protocols select a minimum spanning tree or shortest-path tree from reported costs, applying adjusted second-price auctions per edge to ensure nodes reveal true costs, achieving constant-factor approximations to optimal multicast cost (e.g., within 2 of optimum in dense networks) while maintaining individual rationality and budget balance approximations; empirical evaluations on random graphs show they outperform VCG in payment efficiency by up to 50% in high-density scenarios.^[43]^[44] For resource allocation, such as bandwidth or spectrum in capacitated networks, strategyproofness manifests in auction-based protocols where users bid on link capacities or channels. In cognitive radio networks, for instance, hierarchical auctions like TERA (2015) allocate spectrum and relays truthfully by decomposing the problem into winner-determination via VCG sub-auctions, ensuring no profitable misreporting of valuation vectors and achieving near-optimal social welfare (within 1-1/e of optimum for submodular valuations); this addresses multi-dimensional types inherent in network demands, though at the expense of increased computational complexity for NP-hard winner selection.^[45] In bus-interconnected distributed systems, strategyproof scheduling for divisible loads (e.g., Grosu and Buyya, 2008) uses greedy allocation with critical-price payments, where tasks report sizes and machines report speeds, yielding truthful equilibria that minimize makespan while providing dominant-strategy incentives verified via submodularity of allocation rules.^[46] Challenges persist in distributed implementations, as VCG requires global cost revelation, leading to communication overhead scaling with network diameter; Nisan and Ronen (1999) highlighted this in their foundational algorithmic mechanism design model, where edge agents in general graphs yield truthful VCG solutions for shortest-path routing but with approximation gaps (e.g., no truthful mechanism beats 3/2-factor for certain cost functions without randomization).^[41] Trade-offs with efficiency are evident: while pure strategyproofness enforces truthfulness, it often sacrifices budget balance or requires subsidies, prompting frugal variants that bound payments to O(log n) times true costs in tree networks.^[47] In practice, these mechanisms underpin incentive-compatible protocols in emerging domains like IoT edge computing, where truthful ascending-price auctions allocate heterogeneous resources (e.g., CPU, bandwidth) with revenue guarantees under lowest-revenue limits.^[48]

Matching Markets and School Choice

In two-sided matching markets, such as the stable marriage problem, the Gale-Shapley deferred acceptance algorithm produces a stable matching that is strategyproof for the proposing side, meaning proposers have no incentive to misrepresent their preferences to obtain a better outcome.^[49] When men propose, the resulting man-optimal stable matching ensures that no man can benefit by lying about his preferences, as any deviation would lead to a matching that is either unstable or worse for him under his true preferences.^[49] This property holds because the algorithm's deferred acceptance process guarantees that proposers receive their optimal stable outcome, eliminating profitable manipulations.^[50] School choice mechanisms extend this framework to one-sided preferences with capacities and priorities on the school side, treating schools as non-responsive (fixed capacities) and students as having strict preferences.^[50] The student-proposing deferred acceptance mechanism, analogous to Gale-Shapley, assigns students to schools in a stable manner and is strategyproof for students: no student can secure a strictly preferred school by misreporting preferences, as the algorithm respects priorities and true rankings in a way that blocks beneficial deviations.^[51] This strategyproofness was key in reforms, such as Boston's 2005 switch from the manipulable Boston mechanism to deferred acceptance, reducing observed gaming where students ranked safer but less preferred schools higher to avoid rejection from top choices.^[52]^[53] In contrast, the Boston (immediate acceptance) mechanism processes student rankings round-by-round, assigning to top choices with available capacity, but it is highly manipulable: students can improve outcomes by truncating lists or ranking non-top schools strategically, as empirical data from pre-reform Boston showed widespread non-truthful reporting.^[54]^[52] Strategyproofness in school choice often trades off with efficiency; deferred acceptance may Pareto-dominate the Boston mechanism in stability but not always in student welfare, as measured in simulations and field data from districts like New York City post-2003 adoption.^[55] Alternative mechanisms like top trading cycles, strategyproof in house allocation settings, have been proposed for school choice but may violate stability under priorities.^[56]

Randomized and Probabilistic Mechanisms

Truthfulness in Expectation

In randomized mechanisms, truthfulness in expectation—also termed truthful in expectation (TIE) or ex-ante incentive compatibility—stipulates that each agent maximizes their expected utility by reporting their true type, where the expectation is taken over the mechanism's internal randomness conditional on the reported type profile.^[57] Formally, for agent i with true valuation v_i and others' reports v_{-i}, the mechanism satisfies \mathbb{E}[v_i(\text{Outcome}(v_i, v_{-i})) + p_i(v_i, v_{-i})] \geq \mathbb{E}[v_i(\text{Outcome}(v_i', v_{-i})) + p_i(v_i', v_{-i})] for all deviations v_i', ensuring no profitable deviation in expectation even if agents are risk-neutral.^[58] This contrasts with deterministic strategyproofness, which demands truth-telling for every possible outcome without randomness.^[59] Unlike ex-post incentive compatibility (or universal truthfulness), which requires the inequality to hold for every realization of the randomness—effectively distributing over deterministic strategyproof mechanisms—truthfulness in expectation permits correlations across outcomes that enhance efficiency but may expose agents to variance in utility.^[59] Ex-post variants guarantee robustness against deviations post-randomization, but they often yield worse approximations; for instance, in combinatorial auctions, ex-post truthful mechanisms struggle with constant-factor guarantees, whereas expectation-based ones achieve near-optimal performance.^[60] This relaxation proves valuable in settings where full strategyproofness is impossible, as randomization averages out incentives without requiring monotonicity in every sample path.^[61] Design techniques for such mechanisms often leverage convex programs or maximal-in-distributional-range (MIDR) representations, where the allocation distribution over outcomes is optimized subject to incentive and feasibility constraints, paired with expected payments derived from marginal contributions.^[62] For example, in scheduling unrelated machines, randomized rounding of linear programs yields truthful-in-expectation mechanisms with constant-factor approximations to the optimum, outperforming deterministic counterparts.^[61] Empirical and theoretical analyses indicate that while agents may occasionally regret truth-telling ex post due to realized outcomes, risk-neutrality assumptions align expected utilities with dominant strategies, though risk aversion can undermine this without additional safeguards.^[63] In practice, these mechanisms appear in auction formats like multi-unit sales, where they balance truth-inducement with revenue, as validated in simulations of spectrum allocation.^[64]

Truthfulness with High Probability

A randomized mechanism satisfies truthfulness with high probability (for parameter \epsilon > 0) if, for every agent i, true valuation v_i, any misreport v_i', and valuations of others v_{-i}, the probability over the mechanism's internal randomness that agent i's realized utility from truthful reporting exceeds or equals the realized utility from misreporting is at least $1 - \epsilon: \Pr\left[ v_i\left(Outcome(v_i, v_{-i})\right) + Payment_i(v_i, v_{-i}) \geq v_i\left(Outcome(v_i', v_{-i})\right) + Payment_i(v_i', v_{-i}) \right] \geq 1 - \epsilon.^[65]^[66] This condition holds separately for each possible deviation, ensuring that successful manipulation occurs only with probability at most \epsilon.^[67] Unlike truthfulness in expectation, which requires only that the expected utility from truth-telling dominates any deviation (\mathbb{E}[u_i(v_i, v_{-i})] \geq \mathbb{E}[u_i(v_i', v_{-i})]), truthfulness with high probability bounds the likelihood of regret rather than its average magnitude.^[68] These properties are orthogonal: a mechanism truthful in expectation may permit large regret with small probability (if compensated by gains elsewhere), while one truthful with high probability may violate expectation if regret, though rare, is sufficiently severe.^[67] For instance, in single-parameter combinatorial auctions, a randomized VCG variant achieves truthfulness in expectation but allows manipulation succeeding with constant probability, whereas a random-sampling auction can yield truthfulness with high probability (e.g., \epsilon = 1/n for n agents) using non-monotonic allocation rules, though it fails expectation.^[67] This notion aligns with ex-post incentive compatibility in the limit as \epsilon \to 0, but for fixed \epsilon > 0, it enables approximations in hard domains like multi-unit auctions or combinatorial settings where deterministic strategyproof mechanisms yield poor welfare guarantees.^[69] In differential privacy-based mechanisms, noise addition enforces truthfulness with high probability by making deviations statistically indistinguishable from truth-telling outcomes, with \epsilon tunable via privacy parameters; for example, in exponential mechanism designs, the probability of beneficial lying decays exponentially in the deviation's "distance."^[65] Empirical regret is thus controlled: an agent's worst-case expected loss from truth-telling is at most \epsilon times the maximum possible utility gain from lying.^[66] Applications include collusion-resistant settings, where high-probability variants approximate optimal revenue (e.g., within factors of 2-4 for digital goods auctions) while limiting coalition benefits to probability \epsilon.^[69] It also supports peer-prediction tasks with multiple signals, where informed truthfulness (conditioning on observed outcomes) converges to high-probability guarantees as the number of tasks increases, with rates O(1/\sqrt{T}) for T tasks under sub-Gaussian assumptions.^[70] However, achieving it often requires stronger assumptions, such as limited agent types or single-parameter domains, and may sacrifice monotonicity or efficiency compared to expectation-based relaxations.^[67]

Relaxations and Practical Approximations

Approximate Strategyproofness

A mechanism exhibits approximate strategyproofness, or ε-strategyproofness, if the utility loss from truthful reporting compared to the best possible misreport is bounded by a small ε > 0, formally satisfying u_i(M(v_i, v_{-i}), v_i) \geq u_i(M(v_i', v_{-i}), v_i) - \varepsilon for all agents i, true valuations v_i, misreports v_i', and others' reports v_{-i}, where ε may be additive, multiplicative relative to utility bounds, or scaled by problem parameters like agent budgets.^[33] This relaxation permits minor incentives for deviation while preserving near-dominant truth-telling, contrasting exact strategyproofness where ε = 0 ensures no gain from lying under any circumstances.^[1] The concept addresses limitations of exact strategyproof mechanisms, which frequently yield poor performance guarantees—such as constant-factor losses in social welfare—for complex optimization problems like combinatorial auctions or facility location, due to computational constraints or structural impossibilities without payments.^[71] By tolerating bounded manipulation incentives, designers can achieve better approximation ratios to optimal outcomes; for instance, in one-dimensional facility location, randomized mechanisms attain (1 + √2)/2-approximate social cost while being approximately strategyproof.^[72] Empirical deployments in resource allocation prioritize such trade-offs, as small ε values render deviations practically negligible for risk-averse agents or under repeated interactions.^[73] Key results include constant-factor approximate strategyproof mechanisms for settings like additively separable group activity selection, where exact versions fail to scale, and hybrid facility problems yielding 3-approximate deterministic or better randomized variants.^[73]^[74] In two-sided matching markets, low-correlation assumptions enable ε-strategyproofness by expanding participant pools, bounding regret from misreporting to o(1) as market size grows.^[75] These bounds hold under quasilinear utilities, with ε often independent of instance size, facilitating tractable algorithms via rounding or greedy methods while critiquing overly rigid exact incentive constraints in non-monetary environments.^[76]

Obviously Strategyproof Mechanisms

A mechanism is obviously strategy-proof (OSP) if truthful reporting constitutes an obviously dominant strategy for every agent in the associated extensive-form game representation.^[77] Obvious dominance requires that, at every decision node where an agent moves, the truthful action yields a payoff at least as high as any deviation across all possible continuations of the game, irrespective of opponents' strategies or information sets; this contrasts with standard dominance, which allows contingency on beliefs about others' play.^[77] Formally, for agent i with type v_i, strategy \sigma_i(v_i) (truth-telling) obviously dominates \sigma_i'(v_i) if, for every possible history leading to i's move and every pair of outcomes reachable under \sigma_i(v_i) versus \sigma_i'(v_i), the utility from truth exceeds or equals that from deviation in the worse-case pairing.^[78] OSP strengthens standard strategyproofness (SP), as obvious dominance implies weak dominance, ensuring OSP mechanisms are SP but not conversely; for instance, the Vickrey-Clarke-Groves (VCG) mechanism is SP yet fails OSP because deviations can appear beneficial without full foresight of others' reports.^[79] In contrast, the English (ascending) auction is OSP, as bidders can observe competitors dropping out, making exit at true valuation obviously optimal without needing to predict sealed bids.^[77] Experimental evidence supports OSP's behavioral robustness: in laboratory settings comparing OSP and SP mechanisms implementing identical rules, subjects adhered to truth-telling at rates 15-20% higher under OSP designs, attributed to reduced cognitive demands on strategic foresight.^[78] Characterizations of OSP mechanisms emphasize simplicity in extensive forms: every OSP game is equivalent to a "pruned" version where irrelevant branches are eliminated, and OSP can be verified algorithmically via dominance solvability in reduced game trees.^[77] In restricted domains like single-peaked preferences, OSP and onto social choice functions coincide with median-voter rules, mirroring SP outcomes but with added obviousness.^[80] For randomized mechanisms, OSP requires truth to obviously dominate in expectation across lotteries, though randomization often sacrifices OSP for efficiency; recent analyses show optimal OSP auctions in multi-unit settings yield revenues 10-15% below VCG but enhance participation.^[81] Stable matching mechanisms, such as deferred acceptance, fail OSP for at least one market side, as proposers may misreport to manipulate visible queues without anticipating full responses.^[82] OSP addresses practical limitations of SP by mitigating bounded rationality, where agents deviate due to incomplete strategic reasoning; this has implications for policy design, prioritizing mechanisms verifiable by non-experts over those reliant on equilibrium sophistication.^[77] However, OSP's stricter criterion excludes many efficient SP mechanisms, prompting trade-offs in approximation guarantees.^[83]

Strategyproofness in the Large

A mechanism satisfies strategyproofness in the large (SP-L) if, in environments with a continuum of agents, no agent can gain a positive amount by misreporting their type when others report truthfully, where gains are measured relative to the agent's negligible measure in the population.^[84] This criterion formalizes approximate incentive compatibility asymptotically, requiring that the indirect utility from truth-telling equals or exceeds that from any deviation in the limit of large agent populations, often verified through finite-n approximations where manipulation gains are o(1/n).^[85] SP-L applies to symmetric, anonymous mechanisms in settings like double auctions or matching markets, contrasting with exact strategyproofness by permitting vanishingly small incentives to deviate as scale increases, rather than prohibiting any profitable manipulation regardless of population size.^[86] Key characterizations of SP-L mechanisms emphasize local incentive constraints at the margin. In bilateral trade models, SP-L holds if and only if the mechanism implements no-trade outcomes when buyer and seller types coincide, preventing profitable infinitesimal deviations.^[84] For double auctions with unit demand, uniform-price mechanisms satisfy SP-L, as shading bids yields negligible gains in large markets due to price stability, whereas discriminatory pricing (e.g., pay-your-bid) fails because agents can profitably underbid by an amount independent of market size.^[87] These results extend impossibility theorems: while exact strategyproofness often precludes efficient trade by Myerson-Satterthwaite, SP-L permits approximately efficient mechanisms like k-double auctions for large k, where truth-telling approximates optimality.^[84] SP-L addresses practical limitations of exact strategyproofness in scalable designs, such as spectrum auctions or financial exchanges with millions of participants, where enforcing dominant-strategy truthfulness sacrifices efficiency or revenue.^[85] Azevedo and Budish argue that violations of SP-L are avoidable design flaws, as they allow persistent manipulation gains that accumulate across agents, leading to welfare losses of order 1 rather than vanishing; for instance, empirical analysis of Treasury auctions favors uniform pricing for its SP-L properties over alternatives prone to shading.^[84] In course allocation, mechanisms like immediate-acceptance fail SP-L due to profitable report ordering, but random serial dictatorship approximates it, supporting its use in large universities.^[85] Recent extensions using distributional mechanism design confirm SP-L's robustness for anonymous large-scale settings, emphasizing private-value environments where type distributions ensure asymptotic truthfulness.^[88]

False-Name-Proofness

False-name-proofness is a property of mechanisms that prevents agents from improving their utility by submitting reports or bids under multiple pseudonymous identities, rather than truthfully participating under a single identity.^[89] Formally, for any agent i with true valuation v_i, the mechanism ensures that the utility from truthful single-identity bidding equals or exceeds the utility from any strategy involving multiple identifiers, holding others' reports fixed.^[90] This condition subsumes strategyproofness, as misreporting under one identity represents a degenerate case of false-name manipulation where all pseudonyms submit identical valuations.^[91] False-name-proofness addresses vulnerabilities in environments where identity creation is cheap, such as internet-based auctions or decentralized voting, where agents might otherwise deploy "shill" bids to influence allocations or payments.^[92] The property gained prominence in combinatorial auction design, where bidders can partition bids across false identities to evade critical pricing or alter winner determination.^[93] For example, in the Vickrey-Clarke-Groves (VCG) mechanism, a bidder might split a high-value package bid into lower-value components under separate names to reduce their payment while securing the items, as the VCG payment depends on externalities computed over distinct bids.^[89] To achieve false-name-proofness, mechanisms like the Iterative Generalized VCG (IGVCG) protocol enforce a "partition decision" rule, evaluating bids as if merged across potential pseudonyms and only accepting non-substitutable partitions, thereby neutralizing manipulation incentives.^[93] Similarly, the Partition-Based Voluntary Contribution (PBVC) mechanism, analyzed in 2000, guarantees false-name-proofness alongside individual rationality but at the expense of computational tractability for large item sets.^[92] In voting contexts, false-name-proofness deters "vote multiplicity" attacks, where an agent submits extra votes under false names to sway outcomes, assuming zero or low verification costs.^[94] For binary choice voting with costly participation, optimal false-name-proof rules, such as plurality with abstention thresholds, balance efficiency and robustness by making additional votes unprofitable, though they may favor majority preferences less aggressively than standard rules.^[90] Under separable preferences, false-name-proof voting rules coincide with strategyproof ones only in restricted domains; otherwise, they require additional constraints like anonymity or coalitional stability.^[95] Extensions to social networks model agents controlling multiple vertices, where false-name-proof mechanisms prevent utility gains from fabricating network ties.^[96] False-name-proof mechanisms often trade off social welfare for robustness; for instance, in cloud resource auctions, the FAITH protocol achieves both truthfulness and false-name-proofness via greedy allocation and critical pricing, but yields lower revenue than VCG in high-competition settings.^[97] In team-hiring auctions, where agents own complementary resources, no truthful false-name-proof mechanism Pareto-dominates anonymous bidding, highlighting implementation challenges.^[98] Recent approaches, including deep learning-based designs, approximate false-name-proofness in complex environments but lack theoretical guarantees against adversarial manipulations.^[99] Overall, the property assumes costless identity forgery and no collusion, limiting applicability where verification (e.g., via biometrics) is feasible.^[100]

Group Strategyproofness

Group strategyproofness, also known as group incentive compatibility, requires that no coalition of agents can jointly deviate from truth-telling by misreporting their private information in a way that strictly benefits every member of the coalition, while leaving others unaffected or worse off.^[101] ^[102] This property strengthens individual strategyproofness by addressing collusive manipulations, ensuring robustness against coordinated deviations in settings like voting, allocation, and cost-sharing.^[103] Formally, for a mechanism with outcome function f and agent utilities u_i, a deviation by coalition S via misreports v_S' must not satisfy u_i(f(v_i, v_{-i}), v_i) \leq u_i(f(v_i', v_{-i}), v_i) for all i \in S with strict inequality for at least one i \in S.^[104] Group strategyproof mechanisms necessarily satisfy individual strategyproofness, but the reverse does not hold, as many individually incentive-compatible rules remain vulnerable to group deviations.^[105] In voting environments with single-peaked preferences, group strategyproofness restricts mechanisms to median-based rules or dictatorships, often yielding probabilistic generalizations like random dictatorships for broader domains.^[106] For example, the uniform random dictatorship—selecting an agent at random to dictate the outcome—is group strategyproof on unrestricted preference domains, as no coalition can guarantee improvement over the ex-ante expected utility without risking worse outcomes for some members.^[107] In matching and assignment problems, such as school choice or kidney exchange, group strategyproofness conflicts with stability and fairness; the deferred acceptance algorithm, while individually strategyproof, permits group manipulations where coalitions jointly misreport priorities to secure better joint allocations.^[108] ^[109] Recent analyses in two-sided matching markets show that no non-dictatorial stable mechanism is group strategyproof when both sides have private preferences, highlighting a tension with efficiency.^[105] Cost-sharing mechanisms provide another domain where group strategyproofness is achievable via cross-monotonic schemes, which ensure that expanding the set of serviced agents does not increase per-agent costs; such schemes yield \gamma-budget-balanced group strategyproof rules for network design problems like Steiner forests.^[102] ^[110] In multi-unit auctions, the minimum-price Walrasian equilibrium (MWEP) mechanism satisfies weak group strategyproofness, preventing coalitions from bidding to alter prices in their collective favor without individual losses.^[2] However, strong variants—requiring no beneficial deviation even under indifferences or robust to preference perturbations—often lead to impossibilities; for instance, no Pareto-efficient multi-winner voting rule under approval ballots is strongly group strategyproof.^[111] These limitations underscore that group strategyproofness prioritizes collusion resistance over other desiderata like efficiency, frequently restricting viable mechanisms to trivial or random forms in complex environments.^[112]

Real-World Applications and Empirical Insights

Auction Design and Spectrum Allocation

Spectrum auctions allocate licenses for radio frequencies, essential for wireless communications, to the highest-value users via competitive bidding managed by regulators such as the U.S. Federal Communications Commission (FCC). Authorized by the Omnibus Budget Reconciliation Act of 1993, the FCC has conducted over 100 such auctions since 1994, raising more than $233 billion in gross bids by January 2025.^[113] These mechanisms prioritize efficiency in assigning indivisible, complementary spectrum blocks while addressing bidders' incentives to misrepresent valuations, as strategic lying could lead to suboptimal allocations and revenue losses.^[114] The Vickrey-Clarke-Groves (VCG) mechanism serves as the theoretical benchmark for strategyproof spectrum auctions, guaranteeing truthful bidding as a dominant strategy through payments that internalize externalities, thereby maximizing total social welfare.^[115] However, VCG's requirement to evaluate all possible bidder packages renders it computationally infeasible for real-world spectrum auctions, where thousands of licenses exhibit complementarities and the winner determination problem is NP-hard.^[116] This impracticality stems from exponential growth in computational demands, prompting reliance on heuristic formats that trade exact strategyproofness for scalability. In practice, the FCC employs the simultaneous multiple round auction (SMRA), designed by Paul Milgrom, Robert Wilson, and others, which runs parallel ascending auctions for multiple licenses over discrete rounds with activity rules to curb speculation and collusion.^[117] SMRA reveals price trajectories dynamically, enabling bidders to pivot toward valued packages, but lacks full strategyproofness, as participants can engage in demand reduction—underbidding on substitutes to suppress prices on complements—or tacit signaling.^[118] Empirical evaluations of FCC Auctions 1 through 6 (1994–1996) reveal allocative efficiencies exceeding 95% relative to theoretical maxima, with scant evidence of systematic profitable deviations, attributable to intense competition and transparency mitigating manipulation gains.^[114] Advanced designs, such as the clock-proxy auction used in the FCC's 2016–2017 Incentive Auction (Auctions 1000, 1001, 1002), approximate strategyproofness by eliciting proxy bids upfront for automated bidding in descending (for broadcasters relinquishing spectrum) and ascending phases, reclaiming 70 MHz for broadband while generating $19.8 billion.^[119] These formats align with "strategyproofness in the large," where truthful reporting approximates optimality in competitive settings, as manipulation profits diminish with bidder numbers and license granularity; simulations and historical data confirm bounded strategic losses, often under 5–10%, validating causal links between design features like parallelism and empirical efficiency over rigid theoretical incentives.^[87]^[120]

Peer Selection and Crowdsourcing

Peer selection refers to mechanisms in which a group of agents each submit a contribution, such as a research proposal or project, and provide evaluations of others' contributions, with the goal of selecting a subset of high-quality contributions for funding, publication, or implementation. In this setting, strategyproofness ensures that no agent can increase the probability of their own contribution being selected by misreporting evaluations of others, thereby incentivizing truthful feedback despite potential conflicts of interest.^[121] Such mechanisms are particularly relevant in crowdsourcing platforms where decentralized evaluation is used to identify top performers, as strategic manipulation—such as underrating competitors—could otherwise skew outcomes.^[122] A prominent class of strategyproof peer selection mechanisms relies on partitioning agents into disjoint groups randomly or systematically, then applying impartial selection rules within each partition to allocate spots proportionally to reported scores. For instance, the Dollar Partition mechanism divides agents into partitions and assigns "dollars" representing selection slots, ensuring that truthful reporting maximizes an agent's expected utility under cardinal or ordinal evaluation models.^[121] This approach achieves strategyproofness by making manipulation incentives symmetric across partitions, preventing any single agent from predictably altering the aggregate selection probabilities in their favor.^[123] Extensions incorporate randomization to enhance proportionality and robustness against correlated valuations, where agents' preferences over contributions may align due to shared expertise.^[122] In conference peer review, strategyproof partitioning generalizes to handle reviewer expertise and load balancing, treating reviews as inputs to select papers while protecting against strategic boosting or sabotage. These mechanisms satisfy monotonicity—improving an agent's true evaluation of another does not decrease their own selection odds—and outperform non-strategyproof baselines like greedy selection in theoretical worst-case analyses.^[124] For crowdsourcing applications, such as worker selection in platforms like academic grant allocation or open-source contributions, strategyproof designs mitigate collusion risks by limiting review scopes and using anonymous aggregation, though they trade off some efficiency for incentive compatibility.^[125] Empirical evaluations on synthetic datasets with varying quality distributions and correlation structures demonstrate that strategyproof mechanisms like Dollar Partition select contributions with higher average quality scores—up to 15-20% improvement over impartial but non-monotonic alternatives—while maintaining low variance in selection probabilities across agents.^[126] Real-world adaptations, such as PeerNomination for conflict-aware review graphs, further validate these in sparse networks where each agent reviews only a subset, showing strategyproofness holds under bounded review capacities without empirical evidence of widespread manipulation in controlled simulations.^[127] However, practical deployments reveal challenges in cardinal vs. ordinal scoring, where assuming truthful intensities may overestimate robustness if agents strategically abstain or collude in unobserved ways.^[122]

References

[1]
Relaxing strategyproofness for the random assignment problem
A mechanism is strategyproof if truthtelling is a dominant strategy equilibrium. Participating in a strategyproof mechanism is simple for the agents because it ...
[2]
Strategy-proof multi-object mechanism design: Ex-post revenue ...
We show that at each preference profile, the MWEP mechanism generates more revenue for the seller than any desirable mechanism satisfying no subsidy.
[3]
The Gibbard–Satterthwaite theorem: a simple proof - ScienceDirect
It is strategyproof if it is a dominant strategy for an individual with any permissible ranking to truthfully report her preferences. Theorem Gibbard– ...
[4]
[PDF] Chapter 2 Classic Mechanism Design - Duke Computer Science
In addition to providing a robust solution concept, strategy-proofness removes game-theoretic complexity from each individ- ual agent's decision problem; an ...
[5]
[PDF] Robust group strategy-proofness - Theoretical Economics
Strategy-proofness (SP) is a sought-after property in social choice functions be- cause it ensures that agents have no incentive to misrepresent their private ...
[6]
[PDF] 4 Strategy Proofness - Stanford University
If truth telling is a dominant strategy then we can say a voting mechanism is strategy proof. We may equivalently describe strategy proof voting mechanisms as ...
[7]
[PDF] Economics, AI, and Optimization Lecture Note 3 - Columbia University
Jan 25, 2022 · Saying that an auction (or more generally a mechanism) is “truthful” or “strategyproof” typically means that it is DSIC. DSIC auctions are very ...
[8]
[TeX] https://dash.harvard.edu/bitstreams/f2caf941-5664-...
By definition, this means ... \begin{definition}[Dominant Strategy Incentive Compatibility] A mechanism is dominant strategy incentive compatible ... strategyproof.
[9]
[PDF] Artificial Intelligence Methods for Social Good Lecture 2-4
May 8, 2018 · equilibrium: Dominant Strategy Incentive Compatible. (DSIC), Strategyproof, Truthful. ▻ If everyone telling the truth is a Bayes-Nash ...
[10]
[PDF] Truthful and Fair Resource Allocation - Harvard DASH
≥0 is dominant strategy incentive compatible. (DSIC) if each agent maximizes ... strategyproof mechanism (gw,pw). In particular, for each agent i, the ...
[11]
[PDF] Incentive Compatibility and Revelation Theorem - Game Theory lab
Definition 2 (Dominant Strategy Incentive Compatibility (DSIC)) A social choice function ... Example 2 (Bayesian Incentive Compatibility of First Price ...
[12]
[PDF] Mechanism Theory - Stanford University
θi, d, t) = xi(θ). This contradicts dominant strategy incentive compatibility ... and Bayesian incentive compatibility for a wide range of distributions over ...
[13]
[PDF] Frontiers in Mechanism Design Lecture #12: Bayesian Incentive ...
Feb 19, 2014 · This lecture intro- duces the more traditional notion of Bayesian incentive-compatibility. The idea is that a player acts to maximize its ...<|control11|><|separator|>
[14]
[PDF] Truthful Mechanisms for One-Parameter Agents - UPenn CIS
Mechanisms that do this are called strategyproof or truthful. Because of some stifling negative results that apply when the agents' preferences can be ...
[15]
[PDF] Very easy games: Obviously Strategyproof Mechanisms - ETH Zürich
Remark 1. Note that strategyproof and truthful are synonymous. Truthful means that truth-telling is a dominant strategy. 4 Interns-Hospitals Matching.
[16]
[PDF] On the Equivalence of Bayesian and Dominant Strategy ...
in private value settings is equivalent to dominant strategy incentive compatibility ... of Bayesian incentive compatibility as Proposition A2 in Appendix ...
[17]
Stability in Voting - jstor
29, 1 (January 1961). STABILITY IN VOTINGI. BY MICHAEL DUMMETT AND ROBIN FARQUHARSON. Voting is presented as an n-person majority game, in which preferences.
[18]
Theory of Voting. Robin Farquharson. Yale University Press, New ...
eLetters are not edited, proofread, or indexed, but they are screened. eLetters should provide substantive and scholarly commentary on the article. Neither ...Missing: strategyproofness | Show results with:strategyproofness
[19]
[PDF] The Gibbard–Satterthwaite theorem: a simple proof
Strategy proofness and pivotal voters: A direct proof of the Gibbard–Sattherthwaite theorem. International. Economic Review 24, 413–418. Geanakoplos, J., 1996.<|separator|>
[20]
[PDF] E CO NOMET RI C A - Rohit Vaish
MANIPULATION OF VOTING SCHEMES: A GENERAL RESULT. BY ALLAN GIBBARD. It has been conjectured that no system of voting can preclude strategic voting-the.
[21]
[PDF] Rohit Vaish - Strategy-Proofness and Arrow's Conditions: Existence ...
SATTERTHWAITE, “The Existence of a Strategy Proof Voting Procedure: A Topic in Social Choice Theory,” Ph.D. Dissertation, University of Wisconsin,. Madison ...
[22]
[PDF] impossibility of strategy-proof mechanisms - Princeton University
It states that a strategy-proof mechanism ƒ on an unrestricted space of admissible preferences is dictatorial whenever. #Af ≥ 3. This result reveals the ...
[23]
https://faculty.las.%5Billinois
[24]
[PDF] The Proof of the Gibbard-Satterthwaite Theorem Revisited
The Gibbard-Satterthwaite theorem: A strategy-proof voting rule that is onto is dictatorial if the number of objects is at least three. 3 Some useful lemmas.Missing: statement | Show results with:statement
[25]
[PDF] Gibbard-Satterthwaite Theorem - Stanford University
Everyone prefers A to B, so the social welfare function should not have B as a winner in order to satisfy Pareto optimality. Unanimity doesn't apply in this ...
[26]
[PDF] A General Impossibility Result on Strategy-Proof Social Choice ...
A social choice hyperfunction picks a non-empty set of alternatives at each ad- missible preference profile over sets of alternatives.
[27]
Strategyproof social choice when preferences and outcomes may ...
The Gibbard-Satterthwaite theorem implies that all anonymous, Pareto-optimal, and single-valued social choice functions can be strategically manipulated.
[28]
[PDF] On the Tradeoff between Efficiency and Strategyproofness
Efficiency and Strategyproofness. Arguably one of the most fundamental axioms in microeconomic theory is Pareto-efficiency. An alternative Pareto-dominates ...<|separator|>
[29]
The impossibility of strategy-proof, Pareto efficient, and individually ...
For the probabilistic allocation of objects without money, strategy-proofness is incompatible with Pareto efficiency and equal treatment of equals (Zhou, 1990).
[30]
[PDF] Strategy-proofness versus Efficiency in Matching with Indifferences
Since no stable mechanism is strategy-proof for schools, but there are strategy-proof and stable mechanisms for students, there is no way to completely satisfy ...
[31]
[PDF] Vickrey-Clarke-Groves Mechanisms - Game Theory lab
The precise statement is given in the form of the following theorem. Theorem 4 (Green–Laffont Impossibility Theorem) Suppose for each agent i ∈ N that F =.
[32]
[PDF] Strategyproof and Budget Balanced Mechanisms for Assembly
It is easy to see that no strategyproof mechanism satisfying budget balance and ex post individual rationality can be efficient by comparing the efficient ...
[33]
[PDF] Approximate strategyproofness - David C. Parkes
The design of randomized mechanisms with a parameter that makes a tradeoff between the probability that an agent has non-zero regret and economic and ...
[34]
Manipulation of Schemes that Mix Voting with Chance
Apr 1, 1977 · A decision scheme makes the probabilities of alternatives depend on individual strong orderings of them. It is strategy-proof if it ...Missing: characterization | Show results with:characterization
[35]
Manipulation of Schemes that Mix Voting with Chance - jstor
Any strategy-proof decision scheme, it is shown, is a probability mixture of schemes each of which is unilateral or duple. If it guarantees Pareto optimal ...
[36]
An extreme point characterization of random strategy-proof social ...
According to the Gibbard–Satterthwaite Theorem (Gibbard, 1973, Satterthwaite, 1975), a deterministic social choice function satisfying unanimity is strategy- ...Missing: via | Show results with:via<|separator|>
[37]
[PDF] Approximately Strategy-Proof Voting - Cornell: Computer Science
The classic Gibbard-Satterthwaite Theorem estab- lishes that only dictatorial voting rules are strategy- proof; under any other voting rule, players have an.
[38]
[PDF] CSC304 Lecture 12
Myerson's Lemma: For a single-parameter environment, a mechanism is strategyproof if and only if for all i. 1. xi is monotone non-decreasing in vi.
[39]
[PDF] Algorithmic Game Theory Introduction to Mechanism Design for ...
How do we even define this mathematically? An attempt: Definition: A mechanism is called truthful (or strategyproof, or incentive compatible) if for every ...
[40]
Ad hoc-VCG: a truthful and cost-efficient routing protocol for mobile ...
We introduce a game-theoretic setting for routing in a mobile ad hoc network that consists of greedy, selfish agents who accept payments for forwarding data ...
[41]
[PDF] Algorithmic Mechanism Design - Computer Science
An exposition of applying several classic notions from mechanism design in our model appears in Nisan (1999). 2.
[42]
[PDF] Ad hoc-VCG: a truthful and cost-efficient routing protocol for ...
Ad hoc-VCG is proposed, a reactive routing protocol that achieves the design objectives of truthfulness and cost-efficiency and guarantees that routing is ...
[43]
[PDF] Truthful Multicast in Selfish Wireless Networks - Temple CIS
To the best of our knowledge, our proto- cols are the first truthful mechanisms that do not reply on VCG mechanisms for routing in selfish networks. We study ...
[44]
[PDF] Truthful Multicast Routing in Selfish Wireless Networks
In summary, we want to design strategy-proof multicast proto- cols for a selfish wireless network with the following properties. 1) Incentive Compatibility (IC) ...<|separator|>
[45]
Truthful Auction for Resource Allocation in Cooperative Cognitive ...
We model the problem of joint spectrum allocation and relay allocation as a hierarchical auction and propose TERA, which is the first Truthful auction mechanism ...
[46]
[PDF] Strategyproof Mechanisms for Scheduling Divisible Loads in Bus ...
We develop strategyproof mechanisms for three classes of distributed systems interconnected by a bus network. The strategyproof mechanisms provide incentives to.
[47]
[PDF] Beyond VCG: Frugality of Truthful Mechanisms
The VCG mechanism is truthful, and hence the winning set is in fact a cheapest feasible solution with re- spect to the true cost. However, the payments made by ...
[48]
A resource competition-based truthful mechanism for IoV edge ...
Jan 8, 2024 · In IoV edge computing resource allocation mechanism with a lowest revenue limit (IoV-RAM-LRL) section, we propose a truthful ascending-price ...
[49]
[PDF] Strategic Aspects of Stable Matching Markets: A Survey - IJCAI
Gale and Shapley [1962] showed that given any preference profile ≻, the matching computed by the DA algorithm, denoted by DA(≻), is stable, and men- optimal as ...
[50]
[PDF] Matching Markets: Theory and Practice - Duke People
Theorem 2.9 (Theorem 1 in Gale and Shapley 1962): The college-proposing de- ferred acceptance algorithm gives a stable matching for each college admissions.
[51]
Strategy-Proofness Makes the Difference: Deferred-Acceptance with ...
Jul 14, 2014 · Once we add strategy-proofness to these properties, DA-mechanisms are the only ones surviving. In market design problems that are based on weak ...
[52]
Manipulability in school choice - ScienceDirect.com
In 2005, the Boston School Committee replaced its school choice mechanism known as the Boston mechanism (BOS) with a deferred acceptance mechanism (DA). A ...
[53]
[PDF] The “Boston” School-Choice Mechanism
Jan 27, 2010 · The Boston mechanism is a popular student-placement mechanism in school-choice pro- grams around the world. We provide two characterizations ...
[54]
[PDF] Games of School Choice under the Boston Mechanism
The Boston Mechanism: For each school a strict priority ordering of students is determined, each student submits a preference ranking of the schools, and the ...
[55]
The cost of strategy-proofness in school choice - ScienceDirect.com
The second mechanism of interest is student-proposing deferred acceptance (DA). It works as follows: 1. All unmatched students apply to their most preferred ...
[56]
[PDF] Changing the Boston School Choice Mechanism - Duke People
May 18, 2006 · Many properties of TTC carry over to school choice including Pareto efficiency (Shapley and Scarf 1974) and strategy-proofness (Roth 1982b).
[57]
[PDF] On the Power of Randomization in Algorithmic Mechanism Design
Truthfulness in Expectation: A mechanism is truthful in expectation if a bidder always maxi- mizes his expected profit by bidding truthfully. The ...
[58]
[PDF] Truthful and Near-Optimal Mechanism Design via Linear Programming
Our mechanisms yield truthfulness in expectation as an ex-post Nash equilibrium, which means the following: for any player i, and any type profile v−i ∈ V ...
[59]
[PDF] Verifiably Truthful Mechanisms
truthfulness in expectation and universal truthfulness. In our context, truthfulness in expectation means that an agent cannot decrease its expected ...
[60]
Limitations of Randomized Mechanisms for Combinatorial Auctions
Recently, a randomized mechanism has been discovered for combinatorial auctions that is truthful in expectation and guarantees a (1-1/e)-approximation to the ...
[61]
[PDF] Randomized Truthful Mechanisms for Scheduling Unrelated Machines
The weaker version is truthful in expectation, which only requires that for each player, reporting his/her true type will maximize his/her own expected utility.
[62]
[PDF] A Truthful-in-expectation Mechanism for the Generalized ...
MIDR or maximal-in- distributional-range is the only known general approach for designing randomized truthful mechanisms. An MIDR algorithm fixes a set of ...
[63]
Truthfulness in advertising? Approximation mechanisms for ...
Oct 16, 2018 · The results highlight model assumptions allowing for truthfulness-in-expectation. Abstract. Quasilinear utility functions are a standard ...
[64]
On the Power of Randomization in Algorithmic Mechanism Design
We leverage the FPTAS to show for the first time that truthful in expectation polynomial-time mechanisms are provably stronger than polynomial-time universally ...<|separator|>
[65]
[PDF] Mechanism Design via Differential Privacy - Kunal Talwar
In the mechanism design context, this corresponds to truthfulness with high probability [3]: starting from the vector of private values, for most tosses of ...
[66]
[PDF] MECHANISMS FOR DISCRETE OPTIMIZATION WITH RATIONAL ...
Truthfulness with high probability. Suppose that an agent might sometimes benefit by lying, but only with small probability. Formally, suppose that for each.
[67]
[PDF] An Approximate Truthful Mechanism for Combinatorial Auctions with ...
In Section 4.1 we show another method, which at- tains strong truthfulness with high probability (but not in expectation), using a simpler (non-monotone) ...
[68]
An Approximate Truthful Mechanism for Combinatorial Auctions with ...
We discuss two orthogonal notions of truthfulness for a randomized mechanism---truthfulness with high probability and in expectation---and give a mechanism that ...
[69]
[PDF] Collusion-Resistant Mechanisms for Single-Parameter Agents
We have shown that if we relax t-truthfulness and consider t-truthfulness with high probability, mech- anisms for approximating both profit maximization and.
[70]
[PDF] Informed Truthfulness in Multi-Task Peer Prediction - Arpit Agarwal
provide a convergence rate analysis for -informed truthfulness with high probability. We believe that these are the first results on strong or informed ...
[71]
Approximate mechanism design without money - ACM Digital Library
We establish tight upper and lower bounds for the approximation ratio given by strategyproof mechanisms without payments, with respect to both deterministic ...
[72]
[PDF] Approximately Optimal Mechanisms for Strategyproof Facility Location
2-approximate strategyproof mechanism for this objective function, and provide a randomized. (1 +. √. 2)/2-approximate strategyproof mechanism. Feldman and ...
[73]
[PDF] Approximate Strategyproof Mechanisms for the Additively Separable ...
We investigate strategyproof mechanisms in the. Group Activity Selection Problem with the addi- tively separable property. Namely, agents have.
[74]
[1412.3414] Strategyproof Mechanisms for One-Dimensional Hybrid ...
Dec 10, 2014 · For the maxisum objective, in the deterministic setting, we provide a best-possible 3- approximate strategyproof mechanism; in the randomized ...
[75]
[PDF] Approximate Strategyproofness in Large, Two-Sided Matching Markets
Nov 29, 2022 · This allows market designers with a knowledge of low correlation to expand the market to secure approximate strategy proof- ness. As for the ...<|separator|>
[76]
[PDF] Approximately Strategy-proof Mechanisms for (Constrained) Facility ...
Mechanism design. 1. INTRODUCTION. Mechanism design deals with the design of protocols to elicit individual preferences while achieving some social ob ...<|separator|>
[77]
Obviously Strategy-Proof Mechanisms
A mechanism is obviously strategy-proof (OSP) if it has an equilibrium in obviously dominant strategies. This has a behavioral interpretation.
[78]
Obviously Strategy-Proof Mechanisms by Shengwu Li :: SSRN
Feb 6, 2015 · A mechanism is obviously strategy-proof (OSP) if it has an equilibrium in obviously dominant strategies. This has a behavioral interpretation.
[79]
Obviously Strategy-Proof Mechanisms - jstor
(vii) g is an outcome function. It associates each terminal history with an ... "Obviously Strategyproof Implementation of Allocation Mechanisms." http ...
[80]
On obvious strategy-proofness and single-peakedness - ScienceDirect
The purpose of this paper is to identify the class of all obviously strategy-proof and onto social choice functions on the domain of single-peaked preferences.
[81]
On the Power of Randomization for Obviously Strategy-Proof ... - arXiv
Feb 16, 2025 · We investigate the problem of designing randomized obviously strategy-proof (OSP) mechanisms in several canonical auction settings.
[82]
[PDF] Stable matching mechanisms are not obviously strategy-proof
This paper shows that no stable matching mechanism is obviously strategy-proof for any side of the market, especially for men, for general preferences.
[83]
An Algorithmic Theory of Simplicity in Mechanism Design - arXiv
Mar 13, 2024 · This paper introduces a new concept interpolating between OSP and SOSP mechanisms, and provides an algorithmic characterization for single- ...Missing: SP | Show results with:SP
[84]
Strategy-proofness in the Large | The Review of Economic Studies
Aug 7, 2018 · Together, these results suggest that using a mechanism that is manipulable in the large is a preventable design mistake. Whether SP-L can ...
[85]
Strategy-proofness in the Large | NBER
Sep 8, 2017 · We propose a criterion of approximate incentive compatibility, strategy-proofness in the large (SP-L), and argue that it is a useful second-best to exact ...
[86]
[PDF] Strategy-proofness in the Large - Eduardo Azevedo's
Sep 2, 2016 · Together, these results suggest that using a mechanism that is manipulable in the large is a preventable design mistake. Whether SP-L can ...
[87]
[PDF] Strategyproofness in the Large as a Desideratum for Market Design
We propose a criterion of approximate incentive compatibility, strategy-proofness in the large. (SP-L), and argue that it is a useful second-best to exact ...<|separator|>
[88]
Large Strategy-Proof Mechanisms
Jul 20, 2024 · We introduce a distributional approach to mechanism design that proves to be useful for the analysis of large anonymous mechanisms in a private ...
[89]
[PDF] Using Mechanism Design to Prevent False-Name Manipulations
A mecha- nism is said to be false-name-proof if no agent ever bene- fits from using multiple identifiers. The typical formal def- inition also implies strategy- ...
[90]
[PDF] False-Name-Proof Voting with Costs over Two Alternatives
A mechanism is false-name-proof if no agent ever benefits from participating more than once. Unfortunately, the design of false-name-proof mechanisms has been ...
[91]
[PDF] False-name-proof Mechanism Design without Money - IFAAMAS
ABSTRACT. Mechanism design studies how to design mechanisms that result in good outcomes even when agents strategically re- port their preferences.
[92]
[PDF] False-name-Proof Combinatorial Auction Mechanisms ... - DROPS
The goal is to design a false-name-proof mechanism, i.e., a mechanism in which using false names is useless, thus bidders voluntary refrain from using false ...
[93]
[PDF] Characterization of Strategy/False-name Proof Combinatorial ... - IJCAI
We say a protocol is false-name-proof if, for each bidder, declaring his/her true evaluation values using a single iden- tifier (although the bidder can use ...
[94]
[PDF] Optimal False-Name-Proof Voting Rules with Costly Voting
A voting rule is false-name-proof if no agent ever benefits from casting additional votes. Previous work has shown that all false-name-proof voting rules are ...
[95]
False-name-proof and strategy-proof voting rules under separable ...
Jan 25, 2024 · A voting rule where voters cannot benefit by voting several times is usually known in the literature as false-name-proof (see (Yokoo et al., ...
[96]
[PDF] False-Name-Proofness in Social Networks - Nicole Immorlica
In mechanism design, the goal is to create rules for making a decision based on the preferences of multiple parties (agents), while taking into account that ...
[97]
False-Name-Proof Auctions for Cloud Resource Allocation
To tackle this issue, we propose FAITH, a new False-name-proof Auction for virtual machine instance allocation, that is proven both strategy-proof and false- ...
[98]
[1106.2378] False-name-proof Mechanisms for Hiring a Team - arXiv
Jun 13, 2011 · Our goal is to design auctions that are truthful and false-name-proof, meaning that it is in the agents' best interest to reveal ownership ...
[99]
[PDF] Deep False-name-proof Auction Mechanisms
Mechanism design, a subfield of microeconomic theory and game theory, focuses on designing mechanisms that result in desirable outcomes even if the agents act.
[100]
Limited verification of identities to induce false-name-proofness
One way to address this is to design false-name-proof mechanisms, which choose the outcome in such a way that agents have no incentive to use more than one ...<|separator|>
[101]
Group Strategyproofness in Mechanism Design - Emergent Mind
Sep 6, 2025 · Group strategyproofness is defined as a property where no coalition can misreport their private information to ensure that all members are ...
[102]
[PDF] Contents 1 Group-strategyproof mechanism and cost-sharing schemes
Group-strategyproofnes: Informally this means that it is beneficial for players to be truthful even when collusion with other players is allowed. More formally ...
[103]
[PDF] Individual versus group strategy proofness: when do they coincide?
Feb 4, 2009 · Abstract: A social choice function is group strategy-proof on a domain if no group of agents can manipulate its final outcome to their own ...<|separator|>
[104]
[PDF] Characterization of Group-Strategyproof Mechanisms for Facility ...
Definition 2.1 (Strategyproofness). A mechanism is strategyproof if and only if no agent can. gain from misreporting the location, that is, for all x ∈ R.
[105]
[PDF] Equivalence between individual and group strategy-proofness ...
Nov 11, 2024 · Strategy-proofness means no individual can manipulate, while group strategy-proofness means no group can. For stable matching, they are ...
[106]
Group strategy-proof probabilistic voting with single-peaked ...
Several authors have examined group strategy-proof rules in the random assignment and matching models. ... BadeS. Fairness and group-strategyproofness clash in ...
[107]
[PDF] Group-Strategyproof Irresolute Social Choice Functions - IJCAI
Clearly, weak R-group-strategyproofness and. R-group-strategyproofness coincide when voters have strict preferences. Strategyproofness has been shown to be ...
[108]
Fairness and group-strategyproofness clash in assignment problems
It is group-strategyproof if no group ever gains by lying about the group's preferences. Group-strategyproofness strengthens strategyproofness which only ...
[109]
When are efficient and fair assignment mechanisms group strategy ...
Well-known examples include school choice, house allocation, and kidney exchange. An ideal allocation mechanism should be efficient, fair and non-manipulable.
[110]
[PDF] On Budget-Balanced Group-Strategyproof Cost-Sharing Mechanisms
This raises the question of whether all “natural” problems have budget-balanced group-strategyproof mechanisms.
[111]
An impossibility result for strongly group-strategyproof multi-winner ...
Feb 13, 2024 · As a corollary, our result also yields an incompatibility between Pareto-efficiency and strong group-strategyproofness under the approval voting ...
[112]
[PDF] An Impossibility Result for Strongly Group-Strategyproof Multi ...
As a corollary, our result also yields an incompatibility between Pareto-efficiency and strong group-strategyproofness under the approval voting format.<|control11|><|separator|>
[113]
Congress Must Use 2025 to Restore FCC Auction Authority and ...
Jan 14, 2025 · Since acquiring its auction authority in 1993, the FCC has held over 100 auctions that have generated more than $233 billion. With politicians ...<|separator|>
[114]
[PDF] The FCC Spectrum Auctions: An Early Assessment - Peter Cramton
Abstract. This paper analyzes six spectrum auctions conducted by the Federal Communications. Commission (FCC) from July 1994 to May 1996.
[115]
Strategy-Proof Spectrum Allocation Among Multiple Operators in ...
The classical Vickrey-Clarke-Groves (VCG) approach provides the framework for a strategy-proof and social welfare maximizing auction.<|separator|>
[116]
[PDF] Combinatorial Auctions - Brown Computer Science
Recall the VCG mechanism, which generalizes the second-price. (Vickrey) auction to the multi-parameter setting. This mechanism suffers from several anomalies, ...
[117]
[PDF] Putting Auction Theory to Work: The Simultaneous Ascending Auction
In the spectrum auctions, the percentage has usually been 5 percent or 10 per- cent (and in recent auctions has been dependent on the level of bidding in the.
[118]
[PDF] Fourier Analysis-based Iterative Combinatorial Auctions - IJCAI
And in fact, no ICA de- ployed in practice is strategyproof – including the famous. SMRA and CCA auctions used to conduct spectrum auctions. Instead, auction ...
[119]
[PDF] The Clock-Proxy Auction: A Practical Combinatorial Auction Design
The ascending proxy auction is a particular package bidding procedure with desirable properties (see Ausubel and Milgrom 2002, Chapter 3). The bidders report ...
[120]
[PDF] 3. Market design, economic efficiency, and game theory for spectrum ...
This year's Laureates, Paul Milgrom and Robert Wilson, have studied how auctions work. They have also used their insights to design new auction formats for ...
[121]
Strategyproof Peer Selection: Mechanisms, Analyses, and ...
Feb 21, 2016 · We study an important crowdsourcing setting where agents evaluate one another and, based on these evaluations, a subset of agents are selected.
[122]
Strategyproof Peer Selection using Randomization, Partitioning, and ...
Apr 13, 2016 · We make three fundamental contributions to the study of peer selection, a specific type of group decision-making problem, studied in computer science, ...
[123]
Strategyproof peer selection using randomization, partitioning, and ...
We propose a novel mechanism that is strategyproof, ie, agents cannot benefit by reporting insincere valuations.
[124]
[PDF] On Strategyproof Conference Peer Review - IJCAI
Based on their work, Aziz et al. [2016] then propose an improved mechanism for peer selection which is strategyproof and satisfies a natural monotonicity ...<|separator|>
[125]
Strategyproof Peer Selection | Request PDF - ResearchGate
We make three fundamental contributions to the study of peer selection, a specific type of group decision-making problem, studied in computer science, economics ...
[126]
[PDF] Strategyproof Peer Selection: Mechanisms, Analyses, and ...
Dec 28, 2020 · The main challenge in the peer selection problem is to propose strategyproof (also called impartial) mechanisms in which agents cannot increase ...
[127]
PeerNomination: A novel peer selection algorithm to handle ...
We present PeerNomination, an impartial (or strategyproof) peer selection method for scenarios where n agents review and are each reviewed by m others, with the ...