Fairness Math

Fair Division of Goods: The Impossibility of Perfect Fairness

October 7th, 2022

Part 1: Mathematical foundations of fair division and why indivisible goods make perfect fairness provably impossible, forcing fundamental trade-offs between competing criteria.

Maya, Jordan, and Sam inherit their parents’ estate. The assets include the family home (appraised at $450,000), a modest investment portfolio ($180,000), the parents’ car ($25,000), and various personal items: furniture, artwork, photo albums, the grandfather’s watch collection, their mother’s piano. Total value: roughly $700,000.

Maya, the eldest, has two young children and lives three hours away in a cramped apartment. She dreams of moving back to raise her kids in the family home. Jordan, a musician, doesn’t need the house but deeply values the piano because their mother taught them to play on it. Sam, the youngest, is a graduate student drowning in debt; they need liquidity above all else.

The lawyer suggests the obvious solution: sell everything, split the proceeds three ways, each sibling gets $233,333. Perfectly equal. Perfectly fair.

Except Maya starts crying. Jordan looks devastated. Sam seems satisfied, but guilty about it.

This is where most discussions of fairness end and most implementations of “fair division” begin. We recognize that equal splits of monetary value don’t capture what people actually care about. But here’s the uncomfortable truth that drives everything in this post: there is no single, mathematically correct definition of “fair.”

Let me show you why intuitive solutions fail by working through three attempts:

Attempt 1: Equal Value
Split everything by market value: $233,333 each. Maya gets the house but must compensate her siblings $216,667 in cash which she doesn’t have. Jordan gets the piano (worth $8,000) plus $225,333 in other assets. Sam gets $233,333 in liquid assets.

Problem: Maya can’t afford to keep the house without taking on debt, effectively forcing her to sell the one thing she values most. This allocation is envy-free (no sibling prefers another’s bundle to their own) but it fails basic feasibility.

Attempt 2: Divide by Preference
Maya gets the house, Jordan gets the piano plus some investments, Sam gets the most liquid assets. We try to balance by valuation. But Maya receives $450,000 in value while Jordan and Sam each receive $125,000.

Problem: Jordan and Sam feel shortchanged. This violates proportionality, each sibling should receive at least their “fair share” (1/3 of the total value by their own assessment). Jordan might not envy Maya’s specific bundle (Jordan doesn’t want the house), but Jordan believes they deserved more overall.

Attempt 3: Hybrid Approach
Maya gets the house but we insist she compensate her siblings partially, say $50,000 each. Jordan gets the piano plus investments worth $75,000. Sam gets liquid assets totaling $75,000 plus $50,000 from Maya.

Problem: Now Maya must either secure a mortgage or liquidate investments to pay her siblings, and we’re back to questioning whether she can keep the house. Meanwhile, we’ve created a solution that satisfies no one completely: Maya feels burdened, Jordan feels undervalued (the house is worth so much more!), and Sam feels guilty about Maya’s burden but also uncertain if $125,000 is really “fair.”

The issue isn’t that these siblings are being unreasonable. The issue is that we’re trying to simultaneously satisfy multiple, mathematically incompatible fairness criteria. We want:

Envy-freeness: No sibling wishes they had received another’s bundle
Proportionality: Each sibling receives at least 1/n of the value (by their own assessment)
Efficiency: No allocation exists that would make everyone better off
Feasibility: No sibling must pay money they don’t have

With divisible goods (think: splitting a cake), we can often satisfy all these criteria. But with indivisible goods like a house, a piano, or a car, perfect fairness becomes provably impossible in many cases. And this is just the beginning of the complexity. Consider what else we must grapple with:

The mathematical challenge: Multiple valid definitions of “fair” exist, and they often conflict. An allocation can be envy-free but not proportional, proportional but not efficient, efficient but not envy-free. We must choose which notion matters most.

The computational challenge: Even when we agree on what “fair” means, finding such allocations can be NP-hard. As the number of agents or items grows, exact solutions become infeasible to compute in reasonable time.

The philosophical challenge: Should we maximize total happiness (utilitarian), protect the worst-off agent (Rawlsian), or ensure equal treatment regardless of outcome (egalitarian)? Different ethical frameworks lead to different algorithms.

The strategic challenge: If agents know the allocation mechanism, they may misreport their true preferences to get better outcomes. We need mechanisms that incentivize honesty.

The practical challenge: Can items be shared or must they remain whole? Can agents make monetary transfers? What if preferences are uncertain or change over time? Real-world constraints limit which theoretical solutions we can actually implement.

But here’s what makes this field compelling: we can make progress. We can:

Quantify different notions of fairness mathematically
Design algorithms with provable guarantees
Understand trade-offs between fairness, efficiency, and computational complexity
Make informed choices about which approach fits which context

This is the first post in a four-part series on fair division of indivisible goods. In this series, we’ll solve the sibling problem with increasing sophistication, building from theoretical foundations to practical algorithms to philosophical considerations. Each post combines three perspectives:

Theory: Formal definitions, theorems, and complexity results
Practice: Working code implementing algorithms
Philosophy: The normative assumptions underlying each approach

The Series Structure

Part 1 (this post): Foundations and Divisible Goods
We’ll establish the mathematical foundations of fair division, like how to represent preferences, what fairness criteria mean formally, and why indivisibility creates impossibility results. Then we’ll explore cake-cutting: the elegant theory of fairly dividing continuous resources. While our siblings face indivisible items, studying the divisible case reveals what’s possible when constraints are removed and provides algorithmic intuition for discrete problems. We’ll learn about query complexity, protocol design, and the fundamental trade-offs between fairness and computational efficiency.

Part 2: The Indivisibility Challenge
We’ll confront the harsh reality: with discrete items, perfect fairness often becomes impossible. We’ll introduce relaxed fairness notions like EF1 (envy-free up to one good), MMS (maximin share), and others that approximate perfection while remaining achievable. Simple algorithms like round-robin will surprise us with strong guarantees. We’ll explore the computational complexity wall: which problems are tractable and which are NP-hard, and when to accept approximations.

Part 3: Optimizing for Social Welfare
Sometimes fairness isn’t enough. We also want efficiency. We’ll explore social welfare functions (utilitarian, egalitarian, Nash) that optimize for collective good rather than individual satisfaction. When should we sacrifice some fairness for greater total value? How do different ethical frameworks lead to different welfare measures? We’ll implement algorithms that balance fairness constraints with welfare maximization.

Part 4: Sophisticated Mechanisms and Synthesis
We’ll examine state-of-the-art approaches: matching algorithms for heterogeneous agents, mechanisms that allow monetary transfers, and methods for handling both divisible and indivisible components. Then we’ll synthesize everything into a practical decision framework: given your problem’s characteristics, which fairness notion should you target, and which algorithm should you use? We’ll apply our full toolkit to finally resolve the sibling case with multiple approaches, examining which fits their values best.

What You’ll Gain from This Series

By the end, you’ll be able to:

Use fairpyx fair division algorithms and understand their guarantees
Evaluate computational feasibility: when are exact solutions tractable versus when must you approximate?
Exercise judgment about fairness: recognize that “fairness” isn’t a single destination but a landscape of competing values
Choose appropriate tools: match algorithms to problem characteristics and stakeholder priorities
Navigate trade-offs: balance fairness, efficiency, and computational complexity

You’ll see that being a good fair division architect means understanding not just how algorithms work, but when to use them and why they embody certain values over others.

This first post lays the groundwork. We start by answering a deceptively simple question: how do we even quantify something as subjective as what a person values? From there, we’ll build the formal machinery needed for everything that follows, specifically valuation functions, fairness criteria, and the mathematical structures that make some problems solvable and others provably impossible.

FOUNDATIONS: Quantifying the Subjective🔗

Before we can compute fair allocations, we need to answer several foundational questions that have occupied researchers since the field’s inception: How do we represent what people value? What does it mean for an allocation to be “fair”? What types of problems can we solve, and what mathematical structures make problems tractable versus intractable? These questions determine which algorithms we can design, which guarantees we can provide, and which impossibilities we must accept.

This section builds the formal machinery needed for everything that follows. We’ll define the fair division problem precisely, explore the landscape of valuation functions, formalize our key fairness criteria, and understand why the discrete nature of goods creates fundamental barriers. By the end, you’ll have the conceptual toolkit to understand both what’s possible and what’s provably impossible in fair division.

The Fair Division Problem: Formal Setup🔗

Let’s begin with a precise mathematical model that captures the essence of fair division.

The Components

A fair division instance consists of:

A set of agents $N = {1, 2, \ldots, n}$ who will receive allocations. In our sibling case, N = {Maya, Jordan, Sam} with $n = 3$.
A set of items $M = {g_1, g_2, \ldots, g_m}$ to be divided. These could be divisible (like cake) or indivisible (like houses). For the siblings, $ m $ = {house, investments, car, piano, furniture, artwork, photos, watches} with \(m = 8).
Valuation functions $v_i: 2^M \to \mathbb{R}_+$ for each agent $ i $, mapping subsets of items to non-negative real numbers. The notation $2^M$ denotes the power set which is the set of all possible subsets of $M$, including the empty set $\emptyset$ and $M$ itself.

The Goal

We seek an allocation $A = (A_1, A_2, \ldots, A_n)$ that partitions the items among agents. For indivisible goods, this means:

Each item goes to exactly one agent: $A_i \cap A_j = \emptyset$ for (i \neq j\) (disjoint bundles)
Every item is allocated: $\bigcup_i A_i = M$ (complete allocation)
Each $A_i \subseteq M$ is agent $ i $’s bundle

For divisible goods, we allow fractional allocations where each item g is divided with agent $ i $ receiving share $\alpha_{i,g} \in [0,1]$ such that (\sum_i \alpha_{i,g} = 1\) for each item $ g $.

Why This Formalization Matters

This abstract setup unifies many concrete problems:

Inheritance division: Agents are heirs, items are estate assets, valuations reflect personal attachment and utility
Computational resource allocation: Agents are jobs, items are time-slices or machines, valuations reflect priority and deadlines
Course assignment: Agents are students, items are course seats, valuations reflect academic interests and degree requirements
Divorce settlements: Agents are spouses, items are marital property, valuations reflect need and sentimental value

By abstracting to this mathematical model, we develop algorithms and theorems that apply across all these domains. The formalization lets us reason precisely about what’s possible and what’s not.

Goods, Chores, and Mixed Manna🔗

Our siblings are dividing goods, items that agents want to receive. But fair division theory also considers chores, tasks that agents want to avoid, and mixed manna where some items are goods to some agents and chores to others.

Goods have the property that $v_i(S) \geq 0$ for all bundles S, and typically $v_i(S \cup {g}) \geq v_i(S)$ (adding an item doesn’t hurt, by monotonicity). Examples: inheritance assets, desirable tasks, resources. The siblings’ estate consists entirely of goods, so each item has non-negative value to everyone.

Chores have $v_i(S) \leq 0$ (negative utility), and $v_i(S \cup {g}) \leq v_i(S)$ (adding a chore makes things worse). Examples: household duties, unpleasant tasks, burdens. If the estate included debts or maintenance obligations, these would be chores.

Mixed manna allows items to be goods to some agents and chores to others. Example: A family pet is a valued good to the sibling who loves animals, but a chore (daily care burden) to the sibling who doesn’t want pets.

Why the distinction matters:

The type of items fundamentally changes what fairness criteria make sense and what’s computationally feasible. For goods:

Proportionality requires $v_i(A_i) \geq v_i(M)/n$: each agent gets at least their fair share of positive value
Pareto optimality means no reallocation can improve someone without hurting others
Many algorithms achieve strong guarantees efficiently

For chores:

Proportionality requires $v_i(A_i) \leq v_i(M)/n$: each agent receives at most their fair share of negative value (you’re not overburdened)
The direction of envy reverses: you envy someone if they have fewer chores than you
Some problems that are polynomial for goods become harder for chores

For mixed manna:

Fairness criteria must carefully handle items that are positive to some, negative to others
Impossibility results become stronger so fewer guarantees are achievable
Some algorithms that work for goods or chores separately fail for mixed manna

Throughout this post, we focus primarily on goods because that’s what the sibling case involves, but we’ll note when results differ for chores or mixed manna. The distinction reflects deep mathematical differences in problem structure.

Valuation Functions: The Language of Preference🔗

A valuation function is a mathematical representation of an agent’s preferences over bundles of items. For an agent $ i $ and a set of items $ S $, we write $v_i(S)$ to denote how much agent $i $ values receiving bundle $S $. The valuation is typically expressed in some abstract utility units, though we can think of them as dollars for intuition.

Essential Properties

We require valuation functions to satisfy certain basic axioms:

Normalization: An empty bundle has zero value: $v_i(\emptyset) = 0$. This gives us a baseline for comparison: receiving nothing is worth nothing. Without this, utility comparisons become meaningless (is a bundle worth 100 utils good if the empty bundle is worth -1000?).

Monotonicity (for goods): More items are weakly better: if $S \subseteq T$, then $v_i(S) \leq v_i(T)$. Adding items to a bundle doesn’t decrease its value. This captures the idea that goods are desirable. You can always discard unwanted items (free disposal), so receiving extra items can’t hurt you.

Mathematically, this implies:

$v_i(S \cup {g}) \geq v_i(S)$ for any item g and bundle S
$v_i(S \cup T) \geq \max{v_i(S), v_i(T)}$ for any bundles S and T

The monotonicity assumption simplifies analysis enormously. When it fails (as with chores or mixed manna), we need different mathematical machinery.

The Valuation Hierarchy: From Simple to Complex

Valuation functions come in different flavors, arranged in a hierarchy of increasing generality:

Additive valuations (also called linear or modular) are the simplest and most common model. The value of a bundle is the sum of the values of individual items:

\[v_i(S) = \sum_{g \in S} v_i(\{g\})\]

Each item contributes independently to total value. Maya might value the house at $450,000, the car at $25,000, and the piano at $5,000. If she receives {house, car}, her total value is $450,000 + $25,000 = $475,000.

Key property: No complementarities (items aren’t worth more together) and no substitutabilities (items aren’t worth less together). The value of receiving both A and B equals the value of A plus the value of B.

Why additive matters: Many algorithms work efficiently only for additive valuations. The linearity enables optimization techniques (linear programming, greedy algorithms) that fail for more general valuations. Computation that takes polynomial time for additive valuations might become NP-hard for non-additive valuations.

Unit-demand valuations: Agent values only their most-valued item in a bundle:

\[v_i(S) = \max_{g \in S} v_i(\{g\})\]

This captures “I only need one car. The second car adds no value.” Real estate investors might have unit-demand valuations: they want the single best property, and additional properties add little value if they can only manage one.

Unit-demand is more restrictive than additive (every unit-demand function is additive with at most one positive-value item), but it’s computationally convenient for auction design and matching problems.

Submodular valuations capture diminishing marginal returns. The marginal value of adding an item to a bundle decreases as the bundle grows:

\[v_i(S \cup \{g\}) - v_i(S) \geq v_i(T \cup \{g\}) - v_i(T) \text{ for all } S \subseteq T\]

The incremental benefit of item g is higher when added to small bundle S than when added to larger bundle T ⊇ S.

Example: Sam might value the first $100,000 in liquid assets highly (pays off urgent debt), the next $100,000 moderately (emergency fund), and additional amounts with decreasing urgency. The tenth investment account adds less value than the first. Submodularity models satiation and substitution effects.

Why submodular matters: Many natural valuations are submodular. Budget valuations (you have a budget for different categories, subject to diminishing returns) are submodular. Influence in networks (adding one more friend helps less if you already have many friends) is submodular. Algorithmically, submodular functions have special structure that enables approximation algorithms.

Subadditive valuations: A weaker property than submodularity:

\[v_i(S \cup T) \leq v_i(S) + v_i(T) \text{ for all bundles } S, T\]

The value of a combined bundle is at most the sum of the values of the parts. This rules out strong complementarities (where items together are worth more than their sum) but allows substitution effects.

Supermodular valuations (also called superadditive) capture complementarities. It is opposite of submodular:

\[v_i(S \cup \{g\}) - v_i(S) \leq v_i(T \cup \{g\}) - v_i(T) \text{ for all } S \subseteq T\]

Adding item g is more valuable when you already have many items (because they complement each other).

Example: Jordan might value the piano at $80,000 and the sheet music at $1,000 separately, but together they’re worth $100,000 because the combination unlocks Jordan’s ability to play professionally. The piano without music, or music without piano, provides limited value; together they create synergy.

Supermodular valuations are harder algorithmically than submodular. Many problems that are tractable for submodular become intractable for supermodular.

General valuations (also called arbitrary valuations) place no restrictions beyond monotonicity and normalization. An agent can have any preferences whatsoever, including complex patterns of complementarities, substitutabilities, and non-linearities.

This is the most realistic model but also the most computationally challenging. Real human preferences exhibit all sorts of structure. When an algorithm works for general valuations, it’s robust. When it requires special structure (like additivity), we must check whether that assumption holds.

The Hierarchy:

Unit-demand ⊂ Additive ⊂ Submodular ⊂ Subadditive ⊂ General

Each class is strictly more general than the previous. An additive valuation is submodular, but not all submodular functions are additive. This hierarchy matters because:

Algorithms often make assumptions about valuation structure
Computational complexity varies dramatically across the hierarchy
Impossibility results may hold for general but not additive valuations

Representation and Elicitation

How do we actually specify valuation functions in practice?

For additive valuations, we only need $ m $ numbers, the value of each individual item. For our siblings with 8 items, that’s 8 values per sibling, or 24 numbers total. Concise and easy to elicit: “Maya, how much is the house worth to you?”

For general valuations, we might need to specify values for all 2^m possible subsets. For 8 items, that’s 256 possible bundles. For 20 items, it’s over 1 million bundles. This is completely infeasible to elicit as human agents cannot possibly specify their value for every bundle.

This creates the elicitation bottleneck: Algorithms that require knowing the full valuation function (all 2^m values) are impractical beyond tiny instances. We need algorithms that query the valuation function strategically, asking only for values of specific bundles that matter for the allocation decision.

The query complexity of fair division - The number of questions we mut ak agents becomes a crucial computational measure, as we’ll see in Part II when we study cake-cutting.

For our analysis, we’ll primarily work with additive valuations because:

They’re expressive enough to capture different preferences (Maya values house more, Jordan values photos more)
They’re structured enough to enable efficient algorithms
They’re feasible to elicit (ask about individual items, not exponentially many bundles)
They’re a realistic approximation for many real-world problems

When we need more generality, we’ll be explicit about it.

Modeling the Siblings' Preferences🔗

[Keep the existing content about modeling Maya, Jordan, and Sam’s valuations - it’s already good]

The Core Fairness Criteria: Formal Definitions🔗

Now that we can represent preferences mathematically, we can formalize what it means for an allocation to be “fair.” Fair division theory has developed several criteria, each capturing different intuitions about fairness. Understanding these criteria (and the relationships between them) is essential for choosing appropriate algorithms and interpreting results.

Envy-Freeness: Preferring Your Own Bundle🔗

Intuition: Envy-freeness captures a fundamental notion of fairness: no agent should wish they had received someone else’s allocation instead of their own. If Maya looks at Jordan’s bundle and thinks “I wish I had that instead,” she experiences envy. An allocation is envy-free if no such feelings arise for any agent.

Why is this compelling? Envy-freeness respects each agent’s subjective preferences while creating a kind of social stability. If no one envies anyone else, there’s no grounds for complaint based on “you got something better than me.” It’s a relative fairness criterion for comparing your bundle to others’ bundles, not to some absolute standard.

Formal Definition: An allocation A = (A₁, A₂, …, Aₙ) is envy-free (EF) if for all agents i and j:

\[v_i(A_i) \geq v_i(A_j)\]

Agent i values their own bundle Aᵢ at least as much as they value agent j’s bundle Aⱼ, according to i’s own valuation function.

Note several key aspects of this definition:

Subjectivity: We use vᵢ for both sides, so agent i’s own valuation determines whether they envy. We don’t ask “is Maya’s bundle objectively better than Jordan’s?” We ask “does Maya prefer Jordan’s bundle to her own, by Maya’s assessment?”

All pairs: The condition must hold for every pair of agents i and j. There are n(n-1) such ordered pairs. For three siblings, that’s 6 comparisons we must verify. As n grows, the number of constraints grows quadratically, having computational implications.

Weakness of envy: The inequality is weak (≥, not >). Agents are allowed to be indifferent between bundles. If Maya values her bundle at $450k and also values Jordan’s bundle at $450k, she’s envy-free despite the exact tie.

[Continue with existing example and analysis…]

[Keep existing content but add this formal context at the beginning:]

Formal Definition: An allocation A = (A₁, A₂, …, Aₙ) is proportional (PROP) if for all agents i:

\[v_i(A_i) \geq v_i(M) / n\]

where $ m $ is the set of all items and n is the number of agents. Agent i receives a bundle they value at least as much as 1/n of the total value of all items.

The proportionality criterion embodies a principle of equal shares for equal entitlement. If you’re one of n equally deserving agents, you deserve at least 1/n of the value.

Key properties of proportionality:

Absolute standard: Unlike envy-freeness, proportionality doesn’t compare your bundle to others’. It compares your bundle to the total pool of items. You might receive much less than another agent (by your valuation) yet still satisfy proportionality.

Individual sovereignty: Your proportionality guarantee doesn’t depend on what others receive. Even if every other agent receives nothing, if you receive 1/n of total value, proportionality is satisfied for you.

Normalization dependence: The criterion crucially depends on how we normalize valuations. We’ve set vᵢ(M) = 700,000 for all siblings, making their fair shares comparable. But if we used different scales (Maya values total at 1, Jordan values total at 100), proportionality would mean different things.

This normalization implicitly makes an interpersonal utility comparison: one unit of Maya’s utility equals one unit of Jordan’s utility. This is a strong assumption that some philosophers reject, but it’s necessary to define proportionality across agents.

[Continue with existing example and analysis…]

The Relationship Between Fairness Criteria🔗

How do envy-freeness and proportionality relate? Neither implies the other in general, but there are important connections.

Theorem (Folklore): For goods with non-atomic valuations (where no single item is valued by any agent), envy-freeness implies proportionality.

Proof sketch: Suppose allocation A is envy-free. Consider agent i. Since i doesn’t envy anyone, we have:

\[v_i(A_i) \geq v_i(A_j) \text{ for all } j\]

Summing over all agents $ j $:

\[n \cdot v_i(A_i) \geq \sum_j v_i(A_j)\]

Since the allocation is complete (every item allocated) and disjoint (no item shared):

\[\sum_j v_i(A_j) = v_i(M)\]

(by additivity of valuations over disjoint sets)

Therefore:

\[v_i(A_i) \geq v_i(M) / n\]

So agent i satisfies proportionality.

This shows that envy-freeness is a stronger condition than proportionality (when valuations are non-atomic). If you achieve envy-freeness, you get proportionality “for free.”

However, the reverse doesn’t hold: proportional allocations can harbor envy. You might receive your fair share while still preferring someone else’s bundle.

For divisible goods: The Dubins-Spanier theorem (1961) proves that envy-free allocations always exist and can be both envy-free and Pareto optimal simultaneously. Proportionality is automatically satisfied.

For indivisible goods: Both criteria can fail simultaneously, as we’ll see next.

Pareto Optimality: No Wasted Value🔗

A third crucial criterion is efficiency: ensuring the allocation doesn’t waste value through poor matching.

Formal Definition: An allocation A is Pareto optimal (or Pareto efficient) if there exists no other allocation A’ such that:

$v_i(A’_i) \geq v_i(A_i)$ for all agents i (no one is worse off)
$v_j(A’_j) > v_j(A_j)$ for at least one agent j (someone is strictly better off)

In other words, you cannot reallocate items to make at least one person better off without making anyone worse off.

Why Pareto optimality matters:

Waste avoidance: A Pareto suboptimal allocation leaves value on the table. If we can make Maya better off without hurting Jordan or Sam, why wouldn’t we? Pareto improvements are “free money” so everyone consents to them.

Consensus criterion: All reasonable normative frameworks (utilitarian, egalitarian, libertarian) agree that Pareto improvements should be implemented. Unlike fairness criteria that involve trade-offs, Pareto dominance is unambiguous.

Incentive compatibility: In Pareto optimal allocations, agents cannot all benefit from trading after the fact. If the initial allocation were Pareto suboptimal, agents would have incentive to negotiate trades, undermining the mechanism.

Example of Pareto suboptimality: Suppose we allocate:

Maya receives: {piano, artwork} → value to Maya: $15,000
Jordan receives: {house, car} → value to Jordan: $160,000
Sam receives: {investments, watches, furniture, photos} → value to Sam: $571,000

Now consider swapping the piano and artwork (which Maya has) for the photos (which Sam has):

Maya receives: {photos} → value to Maya: $8,000 (worse by $7,000)
Jordan receives: {house, car} → value to Jordan: $160,000 (unchanged)
Sam receives: {investments, watches, furniture, piano, artwork} → value to Sam: $571,000 - $15,000 + $2,000 + $5,000 = $563,000 (worse by $8,000)

Wait, this makes everyone worse off. Let me try a proper example:

Suppose:

Maya receives: {piano} → value to Maya: $5,000
Jordan receives: {house} → value to Jordan: $150,000
Sam receives: {everything else} → value to Sam: $570,000

But Jordan values the piano at $120,000 and Maya values the house at $450,000. If we swap:

Maya receives: {house} → value to Maya: $450,000 (better by $445,000)
Jordan receives: {piano} → value to Jordan: $120,000 (worse by $30,000)
Sam receives: {everything else} → value to Sam: $570,000 (unchanged)

This is still not a Pareto improvement because Jordan is worse off.

For a true Pareto improvement: If Maya has {artwork, photos} worth $18,000 to her but Jordan values the photos at $200,000, while Jordan has {furniture} worth $5,000 to Jordan but Maya values it at $20,000, then swapping photos for furniture:

Maya: $18,000 - $8,000 + $20,000 = $30,000 (better by $12,000)
Jordan: $5,000 - $5,000 + $200,000 = $200,000 (better by $195,000)

Both benefit! The original allocation was Pareto suboptimal.

Tension with fairness: Pareto optimality and fairness can conflict. An allocation might be envy-free but Pareto suboptimal (wastes value). Or it might be Pareto optimal but not envy-free (efficiently matches items but creates envy).

Ideally, we want allocations that are both fair (EF and PROP) and efficient (Pareto optimal). For divisible goods, this is always achievable (Dubins-Spanier, 1961). For indivisible goods, we often must compromise.

The Impossibility of Achieving Both: A Formal Result🔗

[Keep the existing content about impossibility but add this formal framing:]

We now arrive at the first major impossibility result: with indivisible items, we cannot always guarantee both envy-freeness and proportionality simultaneously.

Theorem (Folklore): There exist fair division instances with indivisible goods where no allocation is both envy-free and proportional.

Proof by example: Consider two agents, Alice and Bob, dividing two items: a diamond and a pebble. Both have identical valuations:

Diamond: 100
Pebble: 0
Total value to each: 100

Any allocation must assign the diamond to one agent. Without loss of generality, suppose Alice receives the diamond.

Envy-freeness check:

Alice values her bundle (diamond) at 100, Bob’s bundle (pebble) at 0 → no envy
Bob values his bundle (pebble) at 0, Alice’s bundle (diamond) at 100 → Bob envies Alice

Failed envy-freeness.

Proportionality check:

Fair share for each agent: 100/2 = 50
Alice receives 100 ≥ 50 ✓
Bob receives 0 < 50 ✗

Failed proportionality.

By symmetry, giving the diamond to Bob instead just swaps who fails the criteria.

This captures a fundamental barrier: when a single item is worth more than 1/n of the total value to an agent, and multiple agents want it, we cannot guarantee proportionality. When agents have identical or highly similar preferences for items, we cannot guarantee envy-freeness.

Corollary: For indivisible goods, we cannot always achieve:

Envy-freeness + Proportionality
Envy-freeness + Completeness (allocating all items)
Proportionality + Pareto optimality (in all cases)

These impossibilities motivate the relaxed fairness notions we’ll study in Part II: EF1, MMS, and others that weaken the criteria just enough to make guarantees possible.

First Attempt: A Naive Split🔗

Let’s try to allocate the estate using our intuition, aiming for something reasonable if not perfect:

Allocation 1: Priority to Strongest Preferences

Maya receives: {house, car, furniture} → value to Maya: $495,000
Jordan receives: {piano, artwork, photos} → value to Jordan: $350,000
Sam receives: {investments, watches} → value to Sam: $550,000

Analysis:

Proportionality: All siblings exceed $233,333 ✓
Envy-freeness:
- Maya values Jordan’s bundle at $23,000 (no envy)
- Maya values Sam’s bundle at $182,000 (no envy)
- Jordan values Maya’s bundle at $170,000 (no envy)
- Jordan values Sam’s bundle at $185,000 (no envy)
- Sam values Maya’s bundle at $128,000 (no envy)
- Sam values Jordan’s bundle at $22,000 (no envy)

Success! This allocation satisfies both criteria. But we achieved this through careful matching of items to preferences. Notice what we did:

Gave Maya the house (her highest value item)
Gave Jordan the photos (their highest value item) and piano (second highest)
Gave Sam the watches (their highest value item) and investments (second highest)

This worked because of fortunate complementarity: each sibling’s highest-valued items were different. The house was uniquely valuable to Maya, the photos to Jordan, the watches to Sam. This is not always the case.

Allocation 2: What if we prioritize monetary value?

Maya receives: {house} → value to Maya: $450,000
Jordan receives: {investments} → value to Jordan: $180,000
Sam receives: {car, piano, furniture, artwork, photos, watches} → value to Sam: $300,000

Analysis:

Proportionality: Jordan receives $180,000 < $233,333 ✗

This “fair by market value” allocation fails proportionality for Jordan because Jordan’s subjective valuation of the investments is just their face value, whereas Jordan’s most valued items (photos, piano) went elsewhere.

These attempts reveal the challenge: we need systematic methods that consider all agents’ valuations simultaneously, guarantee fairness properties when possible, and handle cases when guarantees are impossible. We need algorithms with provable bounds.

In the next post, we’ll start with the theoretically elegant case: what happens when items are perfectly divisible, like cutting a cake?

CONCLUSION: From Foundations to Algorithm🔗

We’ve built the conceptual foundations needed for computational fair division:

The formal model: Agents with valuation functions over bundles of items, seeking allocations that partition items among agents. This abstraction unifies inheritance division, resource allocation, and countless other problems.

The valuation landscape: From simple additive functions (values sum independently) to complex general valuations (arbitrary preference structures). The choice of valuation model determines which algorithms work and how efficiently.

The fairness criteria: Envy-freeness (relative satisfaction, as in you don’t prefer others’ bundles) and proportionality (absolute satisfaction, as in you receive your fair share). These capture different moral intuitions and have different mathematical properties.

The impossibility barrier: With indivisible goods, perfect fairness is often unattainable. No allocation may satisfy both envy-freeness and proportionality. This forces us to compromise by relaxing fairness notions or by restricting to special cases.

The efficiency dimension: Pareto optimality ensures we don’t waste value. Ideally, allocations are both fair and efficient, but these goals sometimes conflict.

These foundations reveal both the promise and the challenge of fair division. The promise: we can formalize subjective notions of fairness, prove theorems about when fair allocations exist, and design algorithms that find them. The challenge: the discrete, indivisible nature of many real-world goods creates fundamental barriers that no clever algorithm can overcome.

But here’s the key insight that will guide everything that follows: the impossibilities depend crucially on indivisibility. If we could divide items arbitrarily those impossibility results vanish. For example, if the family home could be cut like a cake into fractional pieces without destroying value. With perfect divisibility, elegant existence theorems guarantee that envy-free, proportional, and Pareto optimal allocations always exist.

This observation motivates the next phase of our journey: studying the divisible case as a theoretical foundation before returning to confront the harsh realities of indivisibility.

In Part II, we’ll explore cake-cutting, which is the theory of fairly dividing continuous, heterogeneous resources among agents with different preferences. You might wonder: why study an idealized model when our siblings face discrete, indivisible items? Three reasons:

1. Theoretical insight: Cake-cutting reveals what’s possible when indivisibility constraints are removed. Understanding the best-case scenario helps us appreciate what we sacrifice when items must remain whole. The impossibility results for discrete goods become meaningful only when contrasted with the possibility results for continuous goods.

2. Algorithmic inspiration: Many algorithms for indivisible goods are discrete adaptations of continuous protocols. Round-robin allocation mimics sequential cutting. Envy cycle elimination generalizes continuous reallocation. Understanding the continuous case provides intuition for the discrete variants.

3. Practical application: Some resources genuinely are divisible, like time-sharing of computational resources, allocation of continuous budgets, division of land parcels (within legal constraints). For these problems, cake-cutting applies directly. Even for indivisible goods, continuous models sometimes provide useful approximations when items are numerous and granular.

Moreover, cake-cutting introduces concepts that will prove essential throughout:

Query complexity: How much information must we elicit from agents?
Protocol design: How does the structure of the allocation procedure affect fairness and incentives?
Computational efficiency: What’s the trade-off between fairness guarantees and computational cost?
Strategic behavior: When can agents manipulate outcomes by misreporting preferences?

These questions apply equally to divisible and indivisible goods, but they’re easier to analyze in the continuous setting where mathematical tools from analysis and topology apply cleanly.

So as you begin Part II, suspend disbelief about perfect divisibility. Let yourself explore the elegant mathematics of cake-cutting, understanding that the insights we gain will prove invaluable when we return to the messy reality of indivisible goods.

Fair Division of Goods: The Impossibility of Perfect Fairness

FOUNDATIONS: Quantifying the Subjective🔗

The Fair Division Problem: Formal Setup🔗

Goods, Chores, and Mixed Manna🔗

Valuation Functions: The Language of Preference🔗

Modeling the Siblings' Preferences🔗

The Core Fairness Criteria: Formal Definitions🔗

Envy-Freeness: Preferring Your Own Bundle🔗

The Relationship Between Fairness Criteria🔗

Pareto Optimality: No Wasted Value🔗

The Impossibility of Achieving Both: A Formal Result🔗

First Attempt: A Naive Split🔗

CONCLUSION: From Foundations to Algorithm🔗

Further Reading🔗

Foundational Textbooks🔗

Classic Papers: Foundations🔗

Modern Surveys and Syntheses🔗

Computational Complexity Results🔗

Approximation Algorithms and Relaxations🔗

Philosophical Foundations🔗

Applications and Real-World Systems🔗

Online Resources and Tools🔗

Courses and Lecture Notes🔗

How to Use These Resources🔗

Fair Division of Goods: The Impossibility of Perfect Fairness

FOUNDATIONS: Quantifying the Subjective🔗

The Fair Division Problem: Formal Setup🔗

Goods, Chores, and Mixed Manna🔗

Valuation Functions: The Language of Preference🔗

Modeling the Siblings' Preferences🔗

The Core Fairness Criteria: Formal Definitions🔗

Envy-Freeness: Preferring Your Own Bundle🔗

Proportionality: Receiving Your Fair Share🔗

The Relationship Between Fairness Criteria🔗

Pareto Optimality: No Wasted Value🔗

The Impossibility of Achieving Both: A Formal Result🔗

First Attempt: A Naive Split🔗

CONCLUSION: From Foundations to Algorithm🔗

Further Reading🔗

Foundational Textbooks🔗

Classic Papers: Foundations🔗

Modern Surveys and Syntheses🔗

Computational Complexity Results🔗

Approximation Algorithms and Relaxations🔗

Philosophical Foundations🔗

Applications and Real-World Systems🔗

Online Resources and Tools🔗

Courses and Lecture Notes🔗

How to Use These Resources🔗