Abstract
In many real-world resource allocation scenarios, an agent's utility depends not only on the item they receive but also on the other agents with whom they share it. This paper formalizes this through the "Dorm Sharing Model," where students are assigned to rooms with specific capacities. We investigate the existence and computational complexity of fair assignments in the presence of these externalities. Our findings show that while determining the existence of a perfectly Envy-Free (EF) assignment is NP-complete, a relaxed notion—Pareto Envy-Freeness (PEF)—is guaranteed to exist and can be found in polynomial time when room capacity is limited to two. However, this guarantee fails for capacities of three or more, establishing a fundamental complexity threshold in social resource sharing.
1. Introduction
Traditional fair division theory typically operates under the assumption of "no externalities," meaning an agent's preference over a bundle is independent of the allocations of others. However, in environments like college dormitories, project teams, or shared workspaces, the social context is inseparable from the physical resource. A student's satisfaction depends on both the room's amenities (internal value) and their roommates (external value). This paper addresses the "dormmate problem": how to partition $n$ students into $m$ rooms such that the resulting assignment is fair, stable, and computationally feasible.
2. The Dorm Sharing Model
The authors define a model where each student $i$ has preferences over a set of dorms $D$ and a set of potential roommates. Preferences are modeled as dichotomous regarding roommates—students are either "friends" or "not friends." The utility of an assignment for student $i$ is thus a combination of the room's quality and the composition of their roommate group.
The gold standard for fairness in such settings is Envy-Freeness (EF). An assignment is envy-free if no student $i$ would prefer to swap their room and roommate set with those of another student $j$. However, the dual-dimensionality of preferences (rooms and people) makes EF notoriously difficult to satisfy.
3. Computational Hardness
The research first establishes that finding an EF assignment is computationally intractable. By reducing the problem from the CLIQUE problem, the authors prove that deciding whether an envy-free assignment exists is NP-complete, even in highly restricted scenarios with only two resources. This suggests that seeking perfect envy-freeness is impractical for large-scale institutional housing where social externalities are present.
4. Pareto Envy-Freeness and the "Power of Two"
To circumvent the impossibility results, the authors propose a relaxation: Pareto Envy-Freeness (PEF). In a PEF assignment, student $i$ envies student $j$ only if $j$ has both a strictly better room and a strictly better set of roommates. If student $i$ prefers their own room but likes $j$'s roommates more (or vice versa), they are not considered to be in a state of "actionable" envy.
A central contribution of the paper is the discovery of a sharp phase transition at room capacity $c=2$:
- The Case for Doubles ($c=2$): The authors prove that a PEF assignment is guaranteed to exist when every room is a double. They provide a constructive algorithm with a complexity of $O(n^3)$. This algorithm leverages the Gallai-Edmonds Decomposition and Hall’s Marriage Theorem to match friends into "bad" rooms and individuals into "good" rooms in a way that balances internal and external utilities.
- The Impossibility for Triples ($c \ge 3$): The guarantee vanishes as soon as capacity increases. The authors provide counterexamples (such as a 9-agent, 3-dorm instance) where no PEF assignment exists. This indicates that as social groups grow beyond pairs, the interdependencies become too complex to ensure even relaxed fairness.
5. Utility Guarantees and Welfare
Beyond social stability, the paper examines individual welfare. They define a proportionality threshold ($\Delta_i$), representing the expected utility a student would receive under a random assignment. The authors prove that any EF assignment (when one exists) guarantees each agent at least $(1 - 1/n)$ of this proportional share. This result bridges the gap between fairness (the absence of envy) and efficiency (ensuring a baseline level of individual happiness).
6. Conclusion and Future Directions
This work identifies the capacity of two as a critical threshold for guaranteed fairness in the presence of externalities. While the $c=2$ case is efficiently solvable using combinatorial optimization, the impossibility results for $c \ge 3$ highlight the inherent difficulty of group-based resource sharing.
Future research may explore non-binary preferences, such as weighted friendships, or investigate conditions under which "Strong Pareto Envy-Freeness" (sPEF) might be achievable. Additionally, extending this model to multi-resource demand—where agents require both a room and a specific workspace—remains an open challenge for the field of fair division.
Summary updated