Friday, September 4, 2015

A new cake cutting protocol

Cake cutting is a playful metaphor for an abstract mathematical setting that models fair division and conflict resolution. The settings concerns agents having different valuations over subsets of a single divisible resource (the cake) which is represented by an interval between 0 and 1. 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. The field of cake cutting has been explored by mathematicians, computer scientists, economists, and political scientists. At least two prominent books have been written on the subject. 

Books on cake cutting

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 and then asks the other agent to pick the piece he prefers. The first agent is not envious as long as he obediently and truthfully divides the cake into two equally preferred pieces. The second agent is certainly not envious because he 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.

Abraham and Lot divided land using the Divide and Choose protocol

Divide and Choose protocol is also mentioned in Greek mythology (Hesiod's Theogeny)

In recent times, the protocol has been enshrined in the Convention of the Law of the Sea.

Divide and Choose protocol us used in the 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 of polymath Conway, it is reported that then when he discovered the protocol for three agents, "he sat down at his orange typewriter and pecked out a letter to Martin Gardner."

John Selfridge

John Conway

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 for certain valuations functions. 

Steven Brams
Alan Taylor

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 report coauthored with Simon Mackenzie, we have come up with 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 i dominates another agent j with respect to a partially allocated envy-free allocation, if i is not envious of j even if j 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 case some 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 make it easier to identify complete envy-free allocation. 

You are welcome to read the report from arxiv. 

Wednesday, August 26, 2015

Tuesday, August 4, 2015

Monday, July 27, 2015

An Open Letter against "Killer Robots"

NYT has given coverage to the recent letter signed by many AI researchers against proliferation of autonomous weapons. The letter has been unveiled at the IJCAI 2015 conference that is taking place in Buenos Aires this week.

Saturday, July 25, 2015

The world’s most charismatic mathematician

The Guardian reviews the recent biography by Siobhan Roberts on John Horton Conway.

John Horton Conway

Conway as you may know has made contributions to such diverse fields as group theory, knot theory, number theory, combinatorial game theory and coding theory. He is probably best known for his Game of Life and his book series "Winning Ways for Your Mathematical Plays". For those interested in fair division problems, Conway is also one of the founders of the Selfridge-Conway envy-free cake cutting protocol for three agents.

Interestingly, the review as well as the book features the sprouts game that was invented in Cambridge by Conway and my PhD supervisor Mike Paterson.

Thursday, June 25, 2015

Interesting Workshop

The Lorentz Center hosts an interesting series of workshops on scientific topics. Recently, a workshop on Clusters, Games and Axioms was organized. The program and slides are available from:

Sunday, May 24, 2015

New Results about the Adjusted Winner Procedure

[Intended for a more general audience. Initial draft: comment welcome]

Adjusted Winner Procedure

The Adjusted Winner procedure is a well-known fair division mechanism to settle disputes and divide resource between two parties. It was proposed by political scientist Steven Brams and mathematician Alan Taylor:

Since the allocation of resources is typically seen in the context of conflict and cooperation, the parties are referred to as agents  or player as is standard in the field of game theory.

Adjusted Winner has been advocated as a fair division rule for divorce settlements, international border conflicts and real estate disputes. It has been termed as a way to obtain a win-win solution. For example, it has been shown that the agreement reached during Jimmy Carter’s presidency between Israel and Egypt is very close to what Adjusted Winner would have predicted.

Adjusted Winner has been patented by New York University and licensed to the law firm Fair Outcomes, Inc.

Adjusted winner works as follows.

Each of the two agents is given a certain number of total points (say 100) to bid on the items. In the first stage, each item is given to the agent that bids more for it. If both agents have the same bid for an item, the item is given to one of the two agents according to some tie-breaking rule. In the second stage, we check whether the number of points allocated to each of the agents is equal, then the tentative allocation from the first stage is the final allocation. Otherwise, if one agent say A has more points than agent B, then agent A needs to give some items(s) to B. The first item to be given to B is the one in which was tentatively allocated to A but for which the ratio of A's bid to B's bid is the lowest. Such items are reallocated to B until both A and B get exactly the same number of points from their respective allocation.

Illustrative Example of Adjusted Winner: The following example taken from here shows how a divorce dispute can be solved via Adjusted Winner. Consider the following hypothetical divorce dispute in which Bob and Carol bid a total of 100 points on the disputed issues/items.  In the first stage, custody is given to Carol whereas the house and alimony is given to Bob because he has higher bids for the house and alimony.  Carol gets 65 points via this tentative allocation whereas Bob gets 75. This means that Bob needs to give a portion (40%) of the house to Carol so that both get equal points. The Adjusted Winner procedure gives whole of Alimony to Bob, the sole custody to Carol. 40% of the house is given to Carol and 60% of the house is given to Bob.


Custody (sole)

Whenever allocations are made in practice, different people can have different ideas about whether the allocation is fair or not. An axiomatic approach can be taken to judge the desirability of an allocation: properties of allocations are formalized and it is then mathematically verified whether a given allocation satisfies those properties.

The Adjusted Winner rule has been advocated because it satisfies desirable axiomatic properties:

Pareto optimality: both agents cannot be happier by some re-allocation.
Envy-freeness: no agent envies the other agent and prefers the other agent's allocation over its own.
Equitability: both agents get the same number of points.

Pareto optimality is one of the most important notions of efficiency in economics and was proposed by Italian polymath Vilfredo Pareto. Envy-freeness captures a very basic fairness condition. Psychologically, people may not be happy be with an allocation if they prefer another person’s allocation. Finally equitability tries to capture the goal that both agents are "equally happy".

Characterizing the Adjusted Winner Procedure

The fact that Adjusted Winner satisfies nice properties does not mean it is the only mechanism satisfying these properties. Recently, we have written a report (Haris Aziz, Simina Brânzei, Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen.  The Adjusted Winner Procedure: Characterizations and Equilibria. arXiv:1503.06665.2015) in which we show that Adjusted Winner is in fact the only mechanism that satisfies these properties:

Adjusted Winner is the only Pareto optimal and equitable mechanism that requires the fractional allocation of at most one item.

If valuations/bids of the agents are different for each item, then the only Pareto optimal and equitable allocation is the result of Adjusted Winner.

Strategic Behaviour and the Adjusted Winner Procedure

The above theorems further reinforce the desirability of Adjusted Winner. Although Adjusted Winner is a desirable mechanism, its properties are satisfied assuming agents report their truthful valuations. However agents can in principle misreport their valuations if they know they will get an even better allocation by doing so. It is known that Adjusted Winner is susceptible to such a manipulation: an agent can misreport its bids to get additional utility if it knows the valuations of the other agent (as may be the case for example in divorce proceedings). In the example above, Carol has an incentive to lie about her valuations and slightly under-report her value for sole custody in order to get a bigger portion of the house and still retain the sole custody!

When agents may have incentive to misreport and "game" the procedure, it is natural to study what kind of outcomes strategic behaviour will lead to and under what combinations of valuations, no agent would have an incentive to change its reported valuation. Such combinations of valuations are called pure Nash equilibria.

In our technical report, we also examined the strategic aspects of Adjusted Winner. In particular, we check whether a pure Nash equilibrium exists or not. The results are mixed: pure Nash equilibria may not exist in general but exist if informed tie breaking is used that orders the items in a way to favour one of the agents. On the other hand an epsilon-Nash equilibrium (that can be considered in lay terms as "almost pure Nash equilibrium") exists even if informed tie breaking is not used.

A major concern when a mechanism is not strategyproof is that its normative properties may not be met under strategic behaviour.

However, we have positive news regarding Adjusted Winner:

A pure Nash equilibrium is envy-free and Pareto optimal and guarantees 75% of the maximum social welfare!   

Hence, even under strategic behaviour, Adjusted Winner does a good job in terms of fairness, efficiency, and welfare.