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:

http://www.lorentzcenter.nl/lc/web/2015/702/info.php3?wsid=702&venue=Oort

Sunday, May 24, 2015

New Results about the Adjusted Winner Procedure


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



http://www.sustainable.org/images/stories/CreatingCommunity_Conflict_02_.jpg

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.



Bob
Carol
Item


Custody (sole)
25
65
House
15
10
Alimony
60
25
Total
100
100


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.        
           
       
   

Wednesday, April 1, 2015

Mathematical Writing on Candy Crush

Congratulations to Toby Walsh for his  Candy Crush article from the American Scientist which has just been selected for the 2015 annual anthology  "The Best Writing on Mathematics", published by Princeton University Press.


http://www.cse.unsw.edu.au/~tw/wamericanscientist2014.pdf
 
This year's anthology has work from a number of well known writers including the famous mathematician (and inventor of the Game of Life) John Conway, and the scientist and New York Times writer Stephen Strogatz.

Past anthologies have included articles written by the Nobel prize winner Lloyd Shapley, and the Field's medalist and Australian of the Year, Terence Tao.



Friday, March 27, 2015

Another feather in Nash's cap



Twenty four years after winning the Nobel Prize for his work on Nash equilibrium, John Nash has now won the Abel Prize for work in the field of geometric analysis.

Princeton University has a nice piece on Nash's achievements.

Tuesday, January 13, 2015

EXPLORE-2015: The 2nd Workshop on Exploring Beyond the Worst Case in Computational Social Choice

The website of EXPLORE 2015 is now up!

Main information:

EXPLORE-2015: The 2nd Workshop on Exploring Beyond the Worst Case in Computational Social Choice

To be held at the 14th Conference for Autonomous Agents and Multi-Agent Systems, AAMAS 2015.

May 4-8, 2015

Istanbul, Turkey


Computational Social Choice (ComSoc) is a rapidly developing field at the intersection of computer science, economics, social choice, and political science. Many, often disjoint, groups of researchers both outside and within computer science study group decision making and preference aggregation. The computer science view of social choice focuses on computational aspects of social choice and importing ideas from social choice into computer science, broadly. While the surge of research in this area has created dramatic benefits in the areas of market matchings, recommendation systems, and preference aggregation, much of the ComSoc community remains focused on worst case assumptions.

As ComSoc evolves in the coming years there will be an increased need to relax or revise some of the more common assumptions in the field: worst case complexity, complete information, and overly-restricted domains, among others. This means going beyond traditional algorithmic and complexity results and providing a more nuanced look, using real-data, parametrized algorithms, and human and agent experimentation to provide a fresh and impactful view of group decision making. This goes hand in hand with highlighting the practical applications of much of the theoretical research — as much of the most impactful work in ComSoc does. It also involves looking at more complex preference aggregation settings that help model real world requirements.

We encourage research related to:

Algorithms
Empirical Studies
Average case analysis
Identification of tractable sub-cases
Fixed parameter complexity analysis
Benchmarking and analysis from the preference handling and recommendation systems
Studies of matching and auction mechanisms
Crowd-sourcing and other real-world data aggregation domains.

Many of these tools, techniques, and studies are concentrated in a particular sub-field and researchers in other areas of ComSoc and related communities may be keen to import some of the tools and techniques developed in other areas.



Program Notes
------------------------------

The workshop is currently scheduled for 1/2 a day (though this may change based on the number and quality of submissions).  The program will include a mini-tutorial (1 hour) which will focus on practical and/or theoretical aspects of moving beyond the worst case in computational social choice.


Important Dates
-------------------------------

Paper Submission Deadline: February 5, 2014

Author Notification: March 1, 2014

Conference and Workshop: May 4-8, 2014


Organization Committee
-------------------------------

Haris Aziz, NICTA and UNSW

Nicholas Mattei, NICTA and UNSW

Nina Narodytska, Carnegie Mellon University.



Submission Instructions
-------------------------------

Submissions will be handled by EasyChair, the site is available at https://easychair.org/conferences/?conf=explore2015.

Papers should be in AAMAS format, allowing 8 pages of text plus 1 page for references.



Travel and Attendance Information
-----------------------------------

The workshop will be held in conjunction with AAMAS 2015 in Istanbul, Turkey.
Please see the AAMAS website for more information regarding registration,
travel, and accommodations: http://www.aamas2015.com.