Fair Division under objective entitlements
A group of people has to divide a set of m objects (or tasks).
Objects are indivisible (so each object has to go to one agent in full), and all objects are to be assigned.
Monetary transfers between agents, or lotteries (“tossing a coin”), are not allowed.
Agents have different valuations for the objects, and agent’s utility of a bundle is the sum of valuations of objects in it. Agents are also endowed with exogenous share sizes: each agent i has to get exactly qi objects, with sum of qi equal to m.
We are looking for ways to use heterogeneity of preferences to produce a “good”, namely “efficient” and “fair”, assignment.
Possible examples include:
--Workers dividing tasks (instructors distributing teaching load for the semester, nurses distributing hospital shifts, etc.), when workers have different contractual obligations (different numbers of classes they have to teach, different number of hours they have to work per week,…)
--Managers assembling teams from the group of workers (who are regarded as objects here), where teams are to be of pre-determined different sizes
--Agents with tasks of different size allocating between themselves processing time slots of the unique task processing server (i.e., when one repair or cleaning team needs to serve a bunch different units of different size)
The first question here is how to define “fairness” or “efficiency”.
There are two problems with traditional fairness notions of “proportionality” (or “fair share”) and “envy-freeness”:
(1) They are impossible to reach due to indivisibilities (think about agents sharing one diamond and many rocks: everyone who did not get the diamond will envy diamond owner and will think they did not get their fair share). This issue is usually addressed in discrete fair division literature by looking at approximate fairness “up to one object”.
We have to amend it, due to the assumption of fixed share sizes qi, so we talk about fairness “up to exchange of two objects”.
(2) They lose meaning when agents are to get shares of different sizes qi. We thus propose to consider fairness “on average”: agent i gets fair share if average value of her objects is at least as good as the average of the total set, and she does not envy another agent if her average value is at least as good as the average in that other agent bundle (according to agent I’s tastes).
Next, what should we demand in terms of “efficiency”? Full efficiency (Pareto optimality) is both very difficult to reach if we combine it with fairness requirements, and demands the mechanism designer to collect too much information from agents in order to implement. Even if preferences are additive, one will need to know cardinal valuations of agents for all objects.
We discuss full efficiency property, and present existence results for some particular cases.
Next to it, we consider the setting with ordinal input, where agents only submit their ordinal rankings of individual objects. Here, one can only guarantee “Ordinal Efficiency”, which is weaker than full Pareto. One however can talk about ordinal variants of fairness properties, which are stronger then cardinal ones.
We show the existence of an allocation rule, which satisfies Ordinal Efficiency, Ordinal Proportionality up to one object exchange, and Ordinal Envy-Freeness up to one object exchange. It is proven by demonstrating that an appropriate generalization of Round Robin rule (gRR) always exists for the case of different entitlements qi, and satisfies a plethora of attractive normative properties.