Agents & Rooms
Total Rent$20
Agents
Alice
Bob
Charlie
Dana
Rooms
R1
$
R2
$
R3
$
R4
$
Sum: $20
V-Matrix (Valuations)
| R1 | R2 | R3 | R4 | |
|---|---|---|---|---|
| Alice | ||||
| Bob | ||||
| Charlie | ||||
| Dana |
vij = Agent i's value for Room j
U-Matrix (Utilities)
| R1 | R2 | R3 | R4 | |
|---|---|---|---|---|
| Alice | -3 | -3 | -3 | 3 |
| Bob | 0 | 5 | 1 | -4 |
| Charlie | 2 | 3 | -1 | 4 |
| Dana | 1 | -3 | 4 | 4 |
uij = vij − rj
Assign all agents to rooms
Each agent must be assigned to exactly one room.
How It Works
Problem: n agents share n rooms and must divide a total rent R.
Goal: Find an assignment σ and rents r₁,...,rₙ (summing to R) such that no agent envies another—i.e., each agent's utility for their own room is at least as high as for any other room.
Utility: uij = vij − rj (value minus rent).
Envy-Free: Agent i is envy-free if ui,σ(i) ≥ uij for all j.