Two-person fair division of indivisible objects

Image taken from http://www.divorceny.com


Fair allocation of objects is one of the most pressing issues faced by society. “Fairness” is a prickly topic with people coming up with different notions of what fairness should mean. One of the most established notions of fairness is envy-freeness  which requires that no agent should prefer another agent’s allocation. EF (Envy-freeness)  by itself does not guarantee desirable allocations. For example, an allocation which leaves agents empty-handed is envy-free as well! Thus, we would like to allocate all the objects to the agents i.e., the assignment should be complete. Unfortunately, there may not exist a complete and envy-free assignment. This can illustrated by
consider the setting in which there is exactly one object. Then, any agent who does not get the object will be envious of the agent who gets the object.


In view of this predicament, in a recent issue of Notices of the AMS, Brams, Kilgour and Klamler (2014) proposed an elegant algorithm called the AL method to compute a maximal envy-free assignment for the case of two agents. The idea is that since a complete assignment of objects may not satisfy envy-freeness, we allocate a maximal set of objects while still satisfying envy-freeness. The assignment returned is also locally Pareto optimal (Pareto optimal for the set of of allocated objects). The algorithm has received interest (see e.g., here, here, and here). The version of EF they used is quite strong: it requires that for each agent i there is bijection f_i from the other agent j's allocation to i's allocation such that for each object o allocated to j, agent i prefers f_i(o) over o.

Consider for example the following preferences where 1 strictly prefer o1 over o2 over o3 over o4.

1: o1, o2, o3, o4
2: o2, o1, o4, o3

Then the assignment that gives o1 and o3 to agent 1 and o2 and o4 to agent 2 is EF.
One potential drawback of the AL method is that it assumes that the agents express strict preferences over objects. This may not always be the case especially if we have multiple copies of the same object or if an agent finds two different objects equally good.
 

Recently, I have extended the AL method to Generalized AL (GAL) which satisfies the same properties as AL but for the more general domain where agents may express indifference among objects. One nice property of GAL is that there exists no other assignment that Pareto dominates the GAL outcome. Another desirable aspect of GAL is that it can be used to check whether there exists a complete EF assignment or not. Previous algorithms for problem requires solving network flows which may not be something which lay people would do!

I illustrate how GAL works with the help of an example in which agents have the following (decreasing) preferences. An agent is indifferent among objects within the same set such as agent 1 is indifferent between o1, o2 and o3.

1: {o7}, {o1, o2 , o3}, {o4 , o5, o6}
2: {o7}, {o1}, {o3}, {o4, o5}, {o2, o6}

Based on the preferences, we build strict priority orders of the agents. The priority orders are a refinement of the preferences where if an agent is indifferent between two objects, it has higher priority for the object less preferred by the other agent. If both agents are indifferent among two objects, then agent 1 has higher priority for the object with the lower index and agent 2 has priority for the object with the higher index.

>_1: o7, o2, o3, o1, o4, o5, o6, o7
>_2: o7, o1, o3, o5, o4, o6, o2

In each round agents either get their most preferred unallocated object that is different or they compete for the same object. If it is the same most preferred object o*, we see if we can give o* to one of the agents and give the next most preferred unallocated object to the other agent without violating EF. If this is not possible, o* is not allocated to either of the agents. So for the preferences over the seven objects listed above, GAL would run as follows and finish in four rounds.


Round 1 --- Agent 1's allocation: {}, Agent 2's allocation :{}, no one gets o7
Round 2 --- Agent 1's allocation: {o2}, Agent 2's allocation :{01}, no one gets o7
Round 3 --- Agent 1's allocation: {o2, o3}, Agent 2's allocation :{o1, o5}, no one gets o7
Round 4 --- Agent 1's allocation: {o2, o3, o4}, Agent 2's allocation :{o1, o5, o6}, no one gets o7 

It remains to be seen how the algorithm can be extended elegantly to the case of more than two agents. If the number of agents is linear, then unless P=NP, no polynomial-time algorithm exists that satisfies the properties of GAL. 

Comments

Popular posts from this blog

Smart Lotteries in School Choice Ex-ante Pareto-Improvement with Ex-post Stability

Fair budgets from ranked ballots: PB-EAR

Proportionally Representative Clustering