Abstract
We study a fair resource sharing problem, where a set of resources are to be shared among a set of agents. Each agent demands one resource and each resource can serve a limited number of agents. An agent cares about what resource they get as well as the externalities imposed by their mates, whom they share the same resource with. Apparently, the strong notion of envy-freeness, where no agent envies another for their resource or mates, cannot always be achieved and we show that even to decide the existence of such a strongly envy-free assignment is an intractable problem. Thus, a more interesting question is whether (and in what situations) a relaxed notion of envy-freeness, the Pareto envy-freeness, can be achieved: an agent $i$ envies another agent $j$ only when $i$ envies both the resource and the mates of $j$. In particular, we are interested in a dorm assignment problem, where students are to be assigned to dorms with the same capacity and they have dichotomous preference over their dorm-mates. We show that when the capacity of the dorms is 2, a Pareto envy-free assignment always exists and we present a polynomial-time algorithm to compute such an assignment; nevertheless, the result fails to hold immediately when the capacities increase to 3, in which case even Pareto envy-freeness cannot be guaranteed. In addition to the existential results, we also investigate the implications of envy-freeness on proportionality in our model and show that envy-freeness in general implies approximations of proportionality.
Introduction
In traditional fair division problems—such as cake cutting or rent division—an agent's utility is typically assumed to depend solely on the bundle they receive. However, many real-world allocations involve significant externalities. In a college dorm assignment, for instance, a student’s satisfaction is derived not only from the physical quality of the room but also from the social compatibility of their roommates.
This paper formalizes the "Dorm Sharing Model," where agents have preferences over both resources and the "mates" with whom they share those resources. Because social preferences introduce significant combinatorial complexity, standard fairness notions like Envy-Freeness (EF)—where no agent prefers another's total bundle over their own—are often impossible to satisfy. Furthermore, determining if an EF assignment even exists is computationally intractable (NP-hard).
Defining Pareto Envy-Freeness (PEF)
To address the limitations of strict envy-freeness, we propose a relaxation called Pareto Envy-Freeness (PEF). Under this definition, an agent $i$ is said to "Pareto-envy" agent $j$ only if $j$ possesses both a superior resource and a superior set of roommates. If agent $i$ prefers $j$’s room but prefers their own roommates (or vice versa), the assignment is considered PEF. This definition acknowledges the trade-offs inherent in shared resource environments: a less desirable room may be compensated for by a better social arrangement.
The Algorithmic Solution for Capacity 2
The technical core of our research focuses on the case where each resource has a capacity of $c=2$. We demonstrate that a PEF assignment always exists in this scenario and can be computed in $O(n^3)$ time. The proposed algorithm leverages advanced tools from matching theory, specifically:
- Gallai-Edmonds Decomposition and Tutte Sets: These are used to analyze the social "friendship graph" and identify components where agents can be perfectly matched with friends.
- Hall’s Marriage Theorem: This ensures that agents who cannot be matched with a friend are compensated with their most preferred available rooms.
By balancing social utility (mates) and physical utility (rooms), the algorithm ensures that no agent is left in a position where they envy both the room and the roommate of another.
The Impossibility Zone: $c \ge 3$
A striking finding of this study is the sensitivity of fairness to resource capacity. While a PEF assignment is guaranteed for two-person rooms, this guarantee vanishes as soon as capacity increases to three. In environments with 3-person suites or larger, the combinatorial possibilities for dissatisfaction explode. We provide specific counter-examples (e.g., a 10-agent graph) where no PEF assignment exists, proving that the "Capacity 2" case is a unique sweet spot for guaranteed fairness.
Complexity and Proportionality
Beyond existence results, we explore the broader implications of these fairness notions:
- NP-Hardness: We show that deciding if a standard EF assignment exists is NP-complete, even with only two resources. Furthermore, if room capacities are non-uniform (e.g., a mix of singles and doubles), finding a PEF assignment becomes NP-hard.
- Proportionality Guarantees: We investigate how envy-freeness relates to proportionality—the idea that every agent should receive a fair share of total utility. We prove that any EF assignment (when one exists) provides each agent with at least $(1 - 1/n)$ of their proportional share, establishing a strong link between these two fairness benchmarks.
Conclusion
This work highlights the critical role of externalities in resource allocation. While the introduction of social preferences makes fair division significantly more difficult, Pareto Envy-Freeness offers a tractable middle ground for small-capacity resources. Future research will focus on addressing dichotomous preferences (moving beyond simple friend/non-friend binary values) and exploring "Approximate PEF" for larger resource capacities where exact fairness cannot be guaranteed.
Summary updated