We study the fair division of a continuous resource, such as a land-estate or a time-interval, among pre-specified groups of agents, such as families. Each family is given a piece of the resource and this piece is used simultaneously by all family members, while different members may have different value functions. Three ways to assess the fairness of such a division are examined. (a) *Average fairness* means that each family's share is fair according to the "family value function", defined as the arithmetic mean of the value functions of the family members. (b) *Unanimous fairness* means that all members in all families feel that their family received a fair share according to their personal value function. (c) *Democratic fairness* means that in each family, at least half the members feel that their family's share is fair. We compare these criteria based on the number of connected components in the resulting division, and based on their compatibility with Pareto-efficiency.
The notion of fairness between groups has been studied empirically in the context of the well-known . In the standard version of this game, an individual agent (the ) suggests a division of a sum of money to another individual (the ), which can either approve or reject it. In the group version, either the proposer or the responder or both are groups of agents. The groups have to decide together what division to propose and whether to accept a proposed division. Experiments by @cite_15 @cite_6 show that, in general, groups tend to act more rationally by proposing and accepting divisions which are less fair. @cite_8 studies the effect of different group-decision rules while @cite_9 uses a threshold decision rule which is a generalized version of our majority rule (an allocation is accepted if at least @math agents in the responder group vote to accept it). These studies are only tangentially relevant to the present paper, since they deal with a much simpler division problem in which the divided good is (money) rather than heterogeneous (cake land).
@cite_9 @cite_15 @cite_6 @cite_8
2971548201 2555059222 2909121337 2963668580
Abstract We study the problem of fairly allocating indivisible goods to groups of agents. Agents in the same group share the same set of goods even though they may have different preferences. Previous work has focused on unanimous fairness, in which all agents in each group must agree that their group's share is fair. Under this strict requirement, fair allocations exist only for small groups. We introduce the concept of democratic fairness, which aims to satisfy a certain fraction of the agents in each group. This concept is better suited to large groups such as cities or countries. We present protocols for democratic fair allocation among two or more arbitrarily large groups of agents with monotonic, additive, or binary valuations. For two groups with arbitrary monotonic valuations, we give an efficient protocol that guarantees envy-freeness up to one good for at least 1 2 of the agents in each group, and prove that the 1 2 fraction is optimal. We also present other protocols that make weaker fairness guarantees to more agents in each group, or to more groups. Our protocols combine techniques from different fields, including combinatorial game theory, cake cutting, and voting. We study cake cutting on a graph, where agents can only evaluate their shares relative to their neighbors. This is an extension of the classical problem of fair division to incorporate the notion of social comparison from the social sciences. We say an allocation is locally envy-free if no agent envies a neighbor's allocation, and locally proportional if each agent values its own allocation as much as the average value of its neighbors' allocations. We generalize the classical Cut and Choose" protocol for two agents to this setting, by fully characterizing the set of graphs for which an oblivious single-cutter protocol can give locally envy-free (thus also locally-proportional) allocations. We study the price of envy-freeness , which compares the total value of an optimal allocation with that of an optimal, locally envy-free allocation. Surprisingly, a lower bound of @math on the price of envy-freeness for global allocations also holds for local envy-freeness in any connected graph, so sparse graphs do not provide more flexibility asymptotically with respect to the quality of envy-free allocations. Two food banks catering to populations of different sizes with different needs must divide among themselves a donation of food items. What constitutes a "fair" allocation of the items among them? Competitive equilibrium from equal incomes (CEEI) is a classic solution to the problem of fair and efficient allocation of goods among equally entitled agents [Foley 1967, Varian 1974]. Every agent (foodbank) receives an equal endowment of artificial currency with which to "purchase" bundles of goods (food items). Prices for the goods are set high enough such that the agents can simultaneously get their favorite within-budget bundle, and low enough such that all goods are allocated (no waste). A CEEI satisfies mathematical notions of fairness like fair-share, and also has built-in transparency -- prices can be published so the agents can verify they're being treated equally. However, a CEEI is not guaranteed to exist when the items are indivisible. We study competitive equilibrium from generic incomes (CEGI), which is based on the idea of slightly perturbed endowments, and enjoys similar fairness, efficiency and transparency properties as CEEI. We show that when the two agents have almost equal endowments and additive preferences for the items, a CEGI always exists. We then consider agents who are a priori non-equal (like different-sized foodbanks); we formulate a new notion of fair allocation among non-equals satisfied by CEGI, and show existence in cases of interest (like when the agents have identical preferences). Experiments on simulated and Spliddit data (a popular fair division website) indicate more general existence. Our results open opportunities for future research on fairness through generic endowments, and on fair treatment of non-equals. Single minded agents have strict preferences, in which a bundle is acceptable only if it meets a certain demand. Such preferences arise naturally in scenarios such as allocating computational resources among users, where the goal is to fairly serve as many requests as possible. In this paper we study the fair division problem for such agents, which is complex due to discontinuity and complementarities of preferences. Our solution concept--the competitive allocation from equal incomes (CAEI)--is inspired from market equilibria and implements fair outcomes through a pricing mechanism. We study existence and computation of CAEI for multiple divisible goods, discrete goods, and cake cutting. Our solution is useful more generally, when the players have a target set of goods, and very small positive values for any bundle other than their target set.