In mechanism design, strategyproofness is the gold standard. A mechanism is strategyproof if no agent can ever benefit by misrepresenting their true preferences. It provides a clean, predictable environment where truth-telling is a dominant strategy.
However, this ideal frequently collides with an mathematical wall. In many multi-agent settings, strict strategyproofness is fundamentally incompatible with other essential goals, such as Pareto efficiency or fairness. For instance, Brandl et al. utilized automated SMT solvers to definitively prove that efficiency and strategyproofness cannot coexist in randomized voting systems under standard neutrality assumptions.
Faced with this impossibility, researchers have shifted from treating strategyproofness as an all-or-nothing property to treating it as a continuous, relaxable design space. By breaking strategyproofness down into its constituent mathematical axioms or restricting the environments in which it must hold, it becomes possible to design mechanisms that are practically immune to manipulation while achieving near-optimal social welfare.
Decomposing Strategyproofness
To relax a property gracefully, one must first understand its internal machinery. In one-sided matching and assignment problems, Mennle et al. and Seuken et al. established that full strategyproofness can be cleanly decomposed into three independent structural axioms:
- Swap Monotonicity: If an agent swaps the ranking of two adjacent items in their preference list (moving item $A$ above item $B$), the probability of being assigned the elevated item $A$ must not decrease.
- Upper Invariance: If an agent alters their preferences only among items ranked below a certain item $A$, the probability of receiving item $A$ (and any item ranked above it) must remain completely unchanged.
- Lower Invariance: If an agent alters their preferences only among items ranked above a certain item $B$, the relative probabilities of receiving the items ranked below $B$ must remain unchanged.
Historically, mechanism designers treated these requirements as a single monolithic block. However, Mennle et al. demonstrated that dropping just one of these components—lower invariance—while strictly maintaining swap monotonicity and upper invariance, yields a powerful, relaxed incentive property known as partial strategyproofness.
Why Dropping Lower Invariance Works
Why does dropping lower invariance unlock better mechanisms without collapsing into rampant manipulability?
Lower invariance forces a mechanism to ignore how an agent rearranges their top-tier choices when calculating the relative assignment probabilities of their bottom-tier choices. By discarding this constraint, the mechanism gains the flexibility to dynamically adjust "tail" probabilities to maximize overall social efficiency.
The cost of this flexibility is that an agent could theoretically manipulate the mechanism. However, because upper invariance and swap monotonicity are preserved, such a manipulation can only alter the probabilities of lower-ranked items. If the agent cares significantly more about securing their top choices than distinguishing between their safety options—a condition formalized by the authors as Uniformly Relatively Bounded Indifference (URBI)—the potential gains from manipulating the tail probabilities are completely eclipsed by the risk of losing a top choice. Truth-telling remains the dominant strategy for all practical purposes.
Alternative Paradigms of Relaxation
Beyond axiomatic decomposition, other branches of social choice relax strategyproofness by bounding the incentives, the information, or the utility profiles of the participating agents.
1. Restricting the Utility Space
Standard strategyproofness requires an ordinal mechanism to be immune to manipulation for every conceivable cardinal utility function consistent with a voter's ordinal ranking. Lederer introduced $U$-strategyproofness, which requires immunity to manipulation only for a predefined, realistic subset of utility functions ($U$). This allows designers to bypass impossibility results by ignoring pathological utility profiles that rarely occur in the real world.
Similarly, Brandt et al. analyzed weak strategyproofness in randomized social choice. While strong strategyproofness dictates that no misrepresentation can yield an outcome that is even partially better (in expectation) for any consistent utility function, weak strategyproofness merely requires that a voter cannot strictly improve their expected outcome. The authors proved that a broad class of voting rules—score-based Social Decision Schemes (SDSs)—are universally weakly strategyproof, providing a rich repository of fair and efficient rules once the strictness requirement is softened.
2. Bounding the Gains ($\epsilon$-Strategyproofness)
Another natural relaxation is to allow for a tiny, bounded incentive to lie. Bhaskar et al. demonstrated that while strictly truthful cardinal voting mechanisms suffer from high social welfare distortion, relaxing the requirement to approximate truthfulness ($\epsilon$-strategyproofness) drastically reduces this distortion.
In a similar vein, Lee showed that by shifting the goal of tournament voting rules from finding the exact winner to finding an approximate winner, one can simultaneously achieve computational efficiency, privacy, and $\epsilon$-strategyproofness, making large-scale crowdsourcing viable.
3. Cognitive and Informational Barriers
Rather than modifying the utility math, some relaxations exploit the cognitive limits of the agents. Flammini et al. investigated non-obvious manipulability within hedonic games. Under this framework, an agent is assumed to deviate from the truth only if the lie guarantees a strictly better outcome in either the absolute best-case or worst-case scenario. If a mechanism ensures that the benefits of lying are highly contingent on other players' hidden actions, the manipulation is "not obvious," and boundedly rational agents will default to truth-telling.
In settings with excludable goods, Aziz et al. proposed Excludable Strategyproofness (EXSP). Here, the mechanism penalizes misrepresentation by withholding outcomes that agents falsely claim to dislike, leveraging the physical constraints of the environment to enforce honesty.
Summary of the Landscape
The evolution of this research direction demonstrates that strategyproofness is not a fragile, binary property. As pioneered in deterministic settings by foundational concepts like weak monotonicity (Bikhchandani et al.), the modern toolkit treats incentive compatibility as a modular optimization problem. Whether by dropping lower invariance to protect top choices, bounding utility domains, or allowing an $\epsilon$-tolerance of manipulation, relaxing strategyproofness provides the mathematical elasticity needed to build efficient, fair, and practical real-world systems.
Key Foundational Work
Relaxing strategyproofness in one-sided matching (2014) — contributed 3 concept elements to this direction.
An Axiomatic Approach to Characterizing and Relaxing Strategyproofness of One-sided Matching Mechanisms (2014) — contributed 2 concept elements to this direction.
Weak Monotonicity Characterizes Deterministic Dominant-Strategy Implementation (2006) — contributed 1 concept elements to this direction.