Fair Division Under Cardinality Constraints

The Setting

We have n agents who must share indivisible goods. The goods are grouped into categories (e.g. Paintings, Statues), and each category h has a capacity k_h: no agent may receive more than k_h goods from category h. Each agent has their own valuation for each item, and values are additive.

The goal: find an allocation that is EF1 and respects all capacities.

Algorithm 1: EF1 under Cardinality Constraints (main procedure)

Initialize σ⁰ = sorted(agents)
For each category h = 1, …, m:
    Run Greedy Round-Robin on C_h with order σ^(h-1)   ← Algorithm 2
    Build envy graph G_h (edge i → j if i prefers j's bundle)
    While G_h has a cycle (a₁ → a₂ → … → a_r → a₁):
        Rotate bundles along the cycle
        Rebuild G_h
    σ^h = topological sort of G_h     ← next picking order
Return final allocation

In plain words: for each category, agents pick greedily in turns. If any envy cycles appear, we rotate bundles along the cycle (this never hurts anyone). Once the envy graph is acyclic, we topologically sort it: agents who envy others get to pick earlier next round — balancing things out.

Algorithm 2: Greedy Round-Robin (subroutine — one category)

Input: items M in category h, picking order σ = (a₁, …, aₙ)
While M is not empty:
    For each agent aᵢ in σ:
        if M is empty: break
        let g* = the item in M that aᵢ values most
        give g* to aᵢ;  remove g* from M

In plain words: agents take turns picking, in a fixed round-robin order. On each turn, the current agent grabs the item they value most from what's still on the table.

What does it guarantee?

• EF1 (Envy-Free up to One Good) — for every pair (i, j), removing one good from j's bundle eliminates i's envy.
• Cardinality constraints — every agent gets ≤ k_h items from each category h.