Agents & Rooms
Total Rent$20
Agents
Alice
Bob
Charlie
Dana
Rooms
R1
$
R2
$
R3
$
R4
$
Sum: $20
V-Matrix (Valuations)
R1R2R3R4
Alice
Bob
Charlie
Dana

vij = Agent i's value for Room j

U-Matrix (Utilities)
R1R2R3R4
Alice
1
4
-4
-4
Bob
-1
3
3
4
Charlie
5
-2
-1
3
Dana
-1
5
0
-2

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.