Fair Room Allocation with Majority Voting and Random Serial Dictatorship

Setting

Let there be a finite set of agents $N = \{1, 2, \dots, n\}$ and two rooms $A$ and $B$.

Each agent $i \in N$ has a strict preference over the two rooms:

$$A \succ_i B \quad \text{or} \quad B \succ_i A.$$

A majority vote determines the selected room:

$$R^* \in \{A, B\}.$$

Define:

• The majority group:

$$M = \{ i \in N : R^* \text{ is agent } i\text{'s preferred room} \}$$

• The minority (losers) group:

$$L = N \setminus M.$$

After selecting $R^*$, agents are assigned positions within the room using Random Serial Dictatorship (RSD):

• A permutation of agents is drawn uniformly at random.
• Agents pick positions sequentially.

We compare two policies:

1. Standard RSD: random permutation over all agents.
2. Losers-first RSD: first randomly permute $L$, then randomly permute $M$, and concatenate.

---

Objective

We study whether the losers-first policy improves fairness.

---

Definition (Ex Post Envy)

An allocation is envy-free ex post if no agent prefers another agent's assignment over their own.

Since positions within a room are heterogeneous (e.g., size, lighting), we assume:

• Each agent has a strict preference ordering over positions in $R^*$.

---

Theorem

Under the losers-first RSD policy, every agent in the minority group $L$ weakly improves their expected allocation (in stochastic dominance terms) compared to standard RSD.

---

Proof

Fix an agent $i \in L$.

Step 1: Position in the Order

• Under standard RSD, agent $i$'s position is uniformly distributed over $\{1, \dots, n\}$.
• Under losers-first RSD, agent $i$'s position is uniformly distributed over $\{1, \dots, |L|\}$.

Thus, for any $k \le |L|$:

$$\mathbb{P}(\text{position of } i \le k \text{ under losers-first}) = \frac{k}{|L|}$$ $$\mathbb{P}(\text{position of } i \le k \text{ under standard}) = \frac{k}{n}$$

Since $|L| \le n$, we have:

$$\frac{k}{|L|} \ge \frac{k}{n}.$$

Thus, agent $i$ is stochastically earlier in the order under losers-first RSD.

---

Step 2: Monotonicity of Preferences

Under serial dictatorship:

• Earlier positions yield weakly better outcomes (since more choices remain).

Thus, if one distribution over positions first-order stochastically dominates another, then the induced allocation distribution also stochastically dominates.

---

Step 3: Conclusion

Therefore, the allocation distribution for agent $i \in L$ under losers-first RSD first-order stochastically dominates their allocation under standard RSD.

$$\Rightarrow \text{Every minority agent is weakly better off in expectation.}$$

---

Corollary

The losers-first mechanism reduces ex ante unfairness toward the minority group.

---

Limitation (Critical)

This mechanism is not Pareto optimal in general.

Counterexample Sketch

• Suppose some majority agents have extremely strong preferences over top positions.
• Prioritizing all minority agents may force large welfare losses for the majority that exceed gains for the minority.

Thus:

• Losers-first improves fairness (compensation),
• but may reduce total welfare (efficiency).

---

Strategic Considerations

The mechanism is not strategy-proof.

Agents may:

• Misreport preferences in the voting stage to end up in the minority group and gain priority.

---

Conclusion

• Losers-first RSD provides a fairness correction by compensating agents whose preferred room was not chosen.
• It guarantees stochastic dominance improvements for minority agents.
• However, it is not globally optimal:
  • It may reduce efficiency,
  • It introduces incentives for manipulation.

---

Interpretation

The rule is best viewed as a fairness heuristic, not an optimal mechanism:

• Good if your goal is perceived fairness and morale,
• Not ideal if your goal is strategy-proofness or total welfare maximization.