When dividing resources—whether they are indivisible items like houses, continuous goods like a cake, or public funds in a city budget—the ideal mechanism should be both fair and truthful. A mechanism is truthful (or strategyproof) if participants have no incentive to misrepresent their preferences to secure a better outcome.
However, a fundamental tension exists between these two goals. When mechanisms cannot use monetary payments to balance incentives, enforcing absolute truthfulness severely degrades the fairness of the final allocation.
Why Truthfulness Breeds Rigidity
The core reason truthfulness and fairness clash lies in the mathematical constraints that strategyproofness imposes on a mechanism's design. To ensure that an agent can never benefit from lying, the mechanism must become highly rigid, preventing it from dynamically adapting to complex reported preferences to ensure equity.
In Truthful Allocation Mechanisms Without Payments: Characterization and Implications on Fairness, George Christodoulou 0001 et al. provide a complete mathematical characterization of all truthful two-player allocation mechanisms without payments. They demonstrate that every such mechanism is merely a hybrid of two simple, rigid strategies: picking from a predefined menu or swapping items. Because of this rigid structure, standard fairness criteria like envy-freeness or even relaxed criteria like envy-free up to one item (EF1) become impossible to satisfy.
This rigidity frequently forces mechanisms into extreme, unequal outcomes. As noted by Vasilis Gkatzelis et al. in Getting More by Knowing Less: Bayesian Incentive Compatible Mechanisms for Fair Division, requiring dominant strategy incentive compatibility—where truth-telling must be optimal regardless of other agents' actions—restricts mechanism design to trivial or inherently unfair outcomes such as serial dictatorship.
Consequently, the "price of honesty" is steep. Georgios Amanatidis et al. show in On Truthful Mechanisms for Maximin Share Allocations that requiring truthfulness introduces a substantial performance gap, halving the maximum achievable maximin share fairness guarantee in simple two-player scenarios. Ilan Reuven Cohen et al. in Plant-and-Steal: Truthful Fair Allocations via Predictions similarly emphasize that enforcing incentive compatibility forces mechanisms to accept extremely low fairness guarantees, occasionally resulting in scenarios where one agent receives nearly all items while others receive almost nothing.
Manifestations Across Allocation Domains
This fundamental incompatibility manifests across several distinct resource allocation problems:
- Cake Cutting: Even when algorithms achieve computational efficiency, they remain vulnerable to manipulation. In How to Cut a Cake Before the Party Ends, David Kurokawa et al. present the first bounded, polynomial-time envy-free algorithm for agents with piecewise linear preferences, but show that such bounded envy-free algorithms are inherently susceptible to strategic manipulation.
- House Allocation and Welfare Maximization: Optimizing for alternative social goals often breaks truthfulness. Yan Hao Ling et al. demonstrate in Envy-Free House Allocation with Minimum Subsidy that mechanisms designed to minimize the total subsidy cost of achieving envy-freeness fail to be strategyproof. Similarly, Xiaoxi Guo et al. in First-Choice Maximality Meets Ex-ante and Ex-post Fairness prove that prioritizing first-choice maximality (maximizing the number of agents who receive their top-ranked items) alongside basic fairness and Pareto efficiency inevitably creates incentives for agents to misreport their preferences.
- Participatory Budgeting: When aggregating public project proposals, a natural fairness goal is proportionality. However, Rupert Freeman et al. in Truthful Aggregation of Budget Proposals note that a general notion of proportionality allowing voters to submit non-uniform distributions is incompatible with incentive compatibility. George Christodoulou et al. expand on this in Truthful aggregation of budget proposals with proportionality guarantees, proving that perfect proportionality is mathematically incompatible with truthfulness, meaning any strategyproof mechanism must necessarily deviate from an ideal proportional distribution of funds.
Bypassing the Impossibility
To circumvent the severe fairness degradation imposed by strict truthfulness, researchers have introduced two primary paradigms: relaxing the informational assumptions of truthfulness or incorporating external predictions.
Relaxing the Incentive Standard
Instead of requiring bulletproof honesty under all circumstances, the authors of Getting More by Knowing Less: Bayesian Incentive Compatible Mechanisms for Fair Division relax the requirement to Bayesian Incentive Compatibility (BIC). By assuming agents have only partial information about each other's preferences rather than complete information, the authors successfully design mechanisms for both indivisible goods and cake-cutting that achieve fairness and efficiency levels previously proven impossible under dominant-strategy constraints.
Learning-Augmented Mechanisms
Alternatively, mechanisms can leverage machine learning predictions about agent preferences to bypass rigid structural limitations. In Plant-and-Steal: Truthful Fair Allocations via Predictions, Ilan Reuven Cohen et al. introduce the Plant-and-Steal framework. This approach utilizes preference predictions to achieve a 2-approximation of a fair share when predictions are accurate, while maintaining a robust safety net (robustness) to protect agents if the predictions fail, successfully bridging the performance gap between honest and truthful fair division.
Key Foundational Work
How to Cut a Cake Before the Party Ends (2013) — contributed 2 concept elements to this direction.
On Truthful Mechanisms for Maximin Share Allocations (2016) — contributed 1 concept elements to this direction.