A General Bounded Envy-free Protocol

Cake cutting is a playful metaphor for an abstract mathematical setting which models fair division and conflict resolution. The setting concerns agents having different valuations over subsets of a single divisible resource (the cake). In cake parlance, it could be that someone prefers the icing and someone else prefers the cherry. It is assumed the cake is infinitely divisible and agents' valuation of the union of two disjoint cake pieces is simply the sum of the valuations of the pieces. Due to its fundamental nature, the field of cake cutting has been explored by mathematicians, computer scientists, economists, and political scientists for decades.
The most central problem in cake cutting is to query the agents about their valuations of sub-intervals and use these answers to efficiently identify an envy-free allocation in which no agent prefers another agent's allocation. The solution to this problem has long been known for the case of two agents in the shape of the Divide and Choose protocol. In this protocol, the first agent is asked to divide the cake into two equally preferred pieces.  Then the second agent is asked to pick the piece he/she prefers. The first agent is not envious as long as he/she obediently and truthfully divides the cake into two equally preferred pieces. The second agent is certainly not envious because he/she chose one of the two pieces first. The protocol has been known since Biblical times (Book of Genesis (Chapter 13)):  Abraham divides the land of Canaan and Lot chooses first. The protocol also features in Greek mythology with Greek gods Prometheus and Zeus dividing meat using the same protocol. In recent times, the protocol has been used in the United Nations Convention of the Law of the Sea.

In 1960’s, the Divide and Choose protocol was generalized to the case where three instead of two agents are dividing the cake. The protocol is known as the Selfridge-Conway protocol after its inventors John Selfridge and John Conway who discovered it independently. It is considered one of the most elegant algorithms in the field of fair division. In a recent biography (Genius At Play: The Curious Mind of John Horton Conway by Siobhan Roberts) of polymath Conway, it is reported that then when he discovered the protocol for three agents, he immediately wrote to Martin Gardner (who is famous for his books on mathematical puzzles).

Since the Conway-Selfridge protocol, a protocol for four or more agents has eluded researchers. In 1995, political scientist Steven Brams and mathematician Alan Taylor made a breakthrough by proposing the first envy-free protocol for any number of agents. Although the protocol terminates in finite time, it had one drawback: it is not bounded even for four agents. In other words, the number of queries required to identify an envy-free allocation can be arbitrarily large.

Since the discovery of the Brams-Taylor protocol, it has been an open problem to devise a bounded envy-free cake-cutting protocol even for four agents. In a recent paper co-authored with Simon Mackenzie who is a PhD student in our group, we proposed a protocol that requires a bounded number of queries as well cuts of the cake. At a very high level, the protocol is based on two main ideas. One is the idea of dominance: an agent dominates another agent with respect to a partially allocated envy-free allocation, if the former is not envious of the latter even if the latter gets the remaining unallocated cake. This idea of dominance is also known as irrevocable advantage in the literature. The other idea we use is that of permutation: agent's allocations are permuted or exchanged. This may cause some agents to be less happy than before but the permutation is done in a careful way so as to not cause envy. Such permutations are done to identify partial envy-free allocations with more structure than makes it easier to identify complete envy-free allocation.
Even though our 4-agent protocol was an encouraging success, Simon and I were keen to settle the question whether there exists a bounded envy-free protocol for any number of agents. This month, we have written up a new protocol that generalizes the 4-agent protocol to any number of agents. Although the protocol is bounded in the number of agents (say n), the bound is huge (a tower of n). The protocol requires various algorithms interacting with each other. We are hopeful that some of the algorithmic techniques can be used in other new protocols for fair division.

So what’s next? Firstly, our protocol is bounded but the bound is huge. It will be interesting to see how much this bound can decreased by more careful analysis  or non-trivial new algorithmic techniques.  Secondly, our general protocol is for the setting where agents view cake favourably. In case, a cake represents 'chores' for which agents have negative utility, it remains open whether a bounded envy-free protocol exists. Could it be that chores are much harder to divide fairly than goods?

Comments

Umayr Hassan said…
It'd be great if you folks updated Wikipedia (https://en.wikipedia.org/wiki/Fair_cake-cutting)
May 26, 2016 at 3:28 AM
Post a Comment

Popular posts from this blog

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

Image
Working Paper: https://cgi.cse.unsw.edu.au/~haziz/PIRMES.pdf  Abstract: In a typical school choice application, the students have strict preferences over the schools while the schools have coarse priorities over the students based on their distance and their enrolled siblings. The outcome of a centralized admission mechanism is then usually obtained by the Deferred Acceptance (DA) algorithm with random tie-breaking. Therefore, every possible outcome of this mechanism is a stable solution for the coarse priorities that will arise with certain probability. This implies a probabilistic assignment, where the admission probability for each student-school pair is specified. In this paper, we propose a new efficiency-improving stable `smart lottery' mechanism. We aim to improve the probabilistic assignment ex-ante in a stochastic dominance sense, while ensuring that the improved random matching is still ex-post stable, meaning that it can be decomposed into stable matchings regarding the ...
Read more

Proportionally Representative Clustering

Image
H. Aziz, B. Lee, S. Morota Chu, and J. Vollen. Proportionally Representative Clustering.  WINE 2024 .  [  Pdf  ]  In recent years, there has been a surge in effort to formalize notions of fairness in machine learning. We focus on centroid clustering— one of the fundamental tasks in unsupervised machine learning. We pro- pose a new axiom “proportionally representative fairness” (PRF) that is designed for clustering problems where the selection of centroids re- flects the distribution of data points and how tightly they are clustered together. Our fairness concept is not satisfied by existing fair cluster- ing algorithms. We design efficient algorithms to achieve PRF both for unconstrained and discrete clustering problems. Our algorithm for the unconstrained setting is also the first known polynomial-time approxi- mation algorithm for the well-studied Proportional Fairness (PF) axiom [ 13 ]. Our algorithm for the discrete setting also matches the best kn...
Read more

Fair budgets from ranked ballots: PB-EAR

How do you split a shared budget fairly when people rank projects that cost very different amounts? PB-EAR, from our AAAI 2021 paper  Proportionally Representative Participatory Budgeting with Ordinal Preferences  ( AAAI version ), gives every voter an equal slice of the budget and lets groups pool their slices to fund the projects they rank highest, looking further down the ballots only when nothing is yet affordable. Every cohesive group is guaranteed its proportional share, and the rule extends our  Expanding Approvals Rule  for elections to budgets with project costs, ties and unequal voter weights.  That makes it a natural fit for DAO grant rounds such as   TheDAO Security Fund 's ETHSecurity Initiatives, where badge holders will rank the security initiatives listed on   the app  to allocate the fund's budget. The two-minute video below walks through a worked example. Here's an educational tool someone built to show how PB-EAR works. 
Read more