Fairness Properties Framework
Mathematical foundations and comparative analysis of fairness criteria in algorithmic resource allocation
Overview
Fair division algorithms are evaluated against rigorous mathematical criteria that formalize our intuitive notions of fairness. This framework provides the theoretical foundation for comparing algorithms and understanding the trade-offs between different fairness guarantees.
Each property represents a different way to answer the fundamental question: "What makes a division fair?" Some properties focus on individual satisfaction, others on relative comparisons, and still others on strategic considerations.
Core Fairness Properties
Proportionality
Intuition: Each player receives at least their "fair share" according to their own valuation.
Formal Definition: For $n$ players, player $i$ receives at least $\frac{1}{n}$ of their subjective valuation:
$$v_i(\text{piece}_i) \geq \frac{v_i(\text{total})}{n}$$Why This Matters: Proportionality ensures no player leaves feeling they received less than their "due." It's often considered the minimum acceptable fairness criterion.
Limitations: Players might still prefer others' allocations even when receiving proportional shares. A player could receive exactly $\frac{1}{n}$ while another receives $\frac{n-1}{n}$.
Algorithm Examples: Divide-and-Choose, Steinhaus Lone-Divider, Banach-Knaster
Envy-Freeness
Intuition: No player would prefer to trade their allocation for someone else's.
Formal Definition: For all players $i$ and $j$:
$$v_i(\text{piece}_i) \geq v_i(\text{piece}_j)$$Relationship to Proportionality: Envy-freeness implies proportionality. If player $i$ doesn't envy anyone, and there are $n$ players total, then $v_i(\text{piece}_i) \geq v_i(\text{piece}_j)$ for all $j$. Since the pieces partition the whole cake: $\sum_{j=1}^n v_i(\text{piece}_j) = v_i(\text{total})$. Therefore: $n \cdot v_i(\text{piece}_i) \geq \sum_{j=1}^n v_i(\text{piece}_j) = v_i(\text{total})$, which gives us $v_i(\text{piece}_i) \geq \frac{v_i(\text{total})}{n}$.
Converse Not True: Proportionality doesn't imply envy-freeness. Consider: Player 1 values pieces A and B equally at 50 each, receives A. Player 2 receives piece B but Player 1 values B at 60 and A at 40. Player 1 is proportional (≥50) but envious.
Algorithm Examples: Divide-and-Choose, Austin's Moving Knife, Selfridge-Conway
Equitability
Intuition: All players are equally satisfied with their allocations.
Formal Definition: All players value their received pieces equally:
$$v_1(\text{piece}_1) = v_2(\text{piece}_2) = \cdots = v_n(\text{piece}_n)$$Philosophical Challenge: Equitability requires comparing utility across different people, which raises deep questions about interpersonal utility comparison. Can we meaningfully say that Alice's satisfaction of "75 points" equals Bob's satisfaction of "75 points"?
Practical Implementation: Most algorithms assume utilities are measured on comparable scales (e.g., both players' total valuations sum to 100), making equitability operationally meaningful.
Relationship to Other Properties: Equitability neither implies nor is implied by envy-freeness. Players can be equally satisfied but still envy each other if they value others' pieces higher than their own.
Algorithm Examples: Austin's Moving Knife, Adjusted Winner
Strategy-Proofness
Intuition: Players cannot benefit by misrepresenting their true preferences.
Formal Definition: Truth-telling is a dominant strategy. For any player $i$, any false valuation $v_i'$, and any valuations $v_{-i}$ of other players:
$$u_i(\text{outcome}(v_i, v_{-i})) \geq u_i(\text{outcome}(v_i', v_{-i}))$$Implementation Challenge: Many fairness properties become much harder to achieve when players might lie about their preferences. Strategy-proofness ensures the algorithm works correctly even with strategic players.
Revelation Principle: For any mechanism, there exists an equivalent strategy-proof mechanism that yields the same outcomes. This justifies focusing on strategy-proof algorithms.
Example of Non-Strategy-Proof Mechanism: "Highest bidder wins" auction isn't strategy-proof because players benefit from underbidding. In contrast, second-price auctions are strategy-proof.
Algorithm Examples: Austin's Moving Knife
Exactness
Intuition: The division achieves perfect mathematical equality rather than just inequality bounds.
Formal Definition: Players receive exactly their proportional share:
$$v_i(\text{piece}_i) = \frac{v_i(\text{total})}{n} \text{ for all players } i$$Discrete vs. Continuous: Exact divisions typically require continuous procedures. Discrete algorithms can only approximate exactness to within their precision limits.
Existence Theory: The Intermediate Value Theorem guarantees that exact divisions exist for continuous valuation functions. For any player's continuous valuation $v_i$ on interval $[0,1]$, there exists a cut position $x^*$ such that $v_i([0,x^*]) = \frac{v_i([0,1])}{2}$.
Computational Complexity: Exact algorithms often require infinite precision, making them theoretically elegant but practically challenging to implement.
Algorithm Examples: Austin's Moving Knife, Continuous Moving Knife procedures
Pareto Efficiency
Intuition: No alternative allocation could make someone better off without making someone else worse off.
Formal Definition: An allocation is Pareto efficient if there exists no other allocation where:
$$v_i(\text{piece}_i') \geq v_i(\text{piece}_i) \text{ for all } i \text{ and } v_j(\text{piece}_j') > v_j(\text{piece}_j) \text{ for some } j$$Tension with Other Properties: Pareto efficiency can conflict with fairness properties. The allocation "Player 1 gets everything" is Pareto efficient but violates proportionality and envy-freeness.
Implementation Difficulty: Many simple fair division algorithms are not Pareto efficient. For example, Divide-and-Choose might create allocations where both players could be made better off through trades.
Social Choice Implications: The Second Fundamental Theorem of Welfare Economics suggests that any Pareto efficient allocation can be achieved through market mechanisms, but this requires initial endowments and may not preserve fairness.
Note: Most classical fair division algorithms do not guarantee Pareto efficiency, representing an important area for algorithmic improvement.
Property Relationships
Hierarchy of Fairness
Understanding how these properties relate helps in algorithm design and evaluation:
Envy-Free ⟹ Proportional
Every envy-free allocation is proportional, but proportional allocations may still have envy.
Exact ⟹ Proportional
Exact equality automatically satisfies proportionality requirements.
Equitable ⊄ Envy-Free
Players can be equally satisfied but still prefer others' allocations.
Strategy-Proof ⊥ Others
Strategy-proofness is largely independent of outcome-based fairness properties.
Interactive Exploration
Use our algorithm simulator to explore how different procedures achieve these fairness properties:
Proportionality Testing
Create scenarios where players have very different valuations and observe how algorithms ensure each receives ≥1/n share.
Try with Steinhaus →Envy Analysis
Design preference patterns that might create envy and see how envy-free algorithms prevent it.
Try with Divide-and-Choose →Exactness vs. Approximation
Compare discrete and continuous procedures to understand the precision trade-offs.
Try Austin's Procedure →