Thursday, September 25, 2014

Two-person fair division of indivisible objects

Image taken from

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. 

Friday, September 19, 2014

Hardy the cricket enthusiast

G. H. Hardy was one of the most well-known pure mathematicians.
His book  A Mathematician's Apology remains a classic piece of literature attempting to explain mathematics to lay people. Many sentences from the book became famous quotes.

 If one reads the book carefully, one can already find some allusions to cricket. For example, Hardy wonders aloud about would have happened had Bradman the cricketing legend had been a poet (Page 5). Haider Riaz Khan has picked up on Hardy's interest in cricket and written an interesting piece on the topic.

Tuesday, September 9, 2014

WINE 2014 Accepted Paper list

The accepted paper list is now available:

Regular papers:

1.   A Near-Optimal Mechanism for Impartial Selection by Nicolas Bousquet, Sergey Norin and Adrian Vetta.
2.   Optimal Cost-Sharing in Weighted Congestion Games Vasilis Gkatzelis by Konstantinos Kollias and Tim Roughgarden
3.   Truthful Multi-unit Procurements with Budgets by Hau Chan and Jing Chen
4.   A Truthful-in-expectation Mechanism for the Generalized Assignment Problem by Salman Fadaei and Martin Bichler
5.   Bounding the Potential Function in Congestion Games and Approximate Pure Nash Equilibria by Matthias Feldotto, Martin Gairing and Alexander Skopalik
6.   Limiting Price Discrimination when Selling Products with Positive Network Externalities by Luděk Cigler, Wolfgang Dvořák, Monika Henzinger and Martin Starnberger
7.   The Shapley Value in Knapsack Budgeted Games by Smriti Bhagat, Anthony Kim, S. Muthukrishnan and Udi Weinsberg
8.   Fast Convex Decomposition for Truthful Social Welfare Approximation by Dennis Kraft, Salman Fadaei and Martin Bichler
9.   Resource Competition on Integral Polymatroids by Tobias Harks, Max Klimm and Britta Peis
10. PTAS for Minimax Approval Voting by Jarosław Byrka and Krzysztof Sornat
11. Sampling and Representation Complexity of Revenue Maximization by Shaddin Dughmi, Li Han and Noam Nisan
12. Coalitional Games on Sparse Social Networks by Edith Elkind
13. Learning economic parameters from revealed preferences by Maria-Florina Balcan, Amit Daniely, Ruta Mehta, Ruth Urner and Vijay V. Vazirani
14. Privacy Games by Yiling Chen, Or Sheffet and Salil Vadhan
15. Simple and Near-Optimal Mechanisms For Market Intermediation by Rad Niazadeh, Yang Yuan and Robert Kleinberg
16. Cake Cutting Algorithms for Piecewise Constant and Piecewise Uniform Valuations by Haris Aziz and Chun Ye
17. Computing Approximate Nash Equilibria in Polymatrix Games by Argyrios Deligkas, John Fearnley, Rahul Savani and Paul Spirakis
18. Network Cournot Competition by Mohammadtaghi Hajiaghayi, Hamid Mahini, Anshul Sawant, Mohammadhossein Bateni and Melika Abolhassani
19. Value-based Network Externalities and Optimal Auction Design by Kamesh Munagala and Xiaoming Xu
20. Revenue Maximizing Envy-free Fixed-price Auctions with Budgets by Qiang Zhang, Stefano Leonardi, Riccardo Colini Baldeschi and Piotr Sankowski
21. Not Just an Empty Threat: Subgame-Perfect Equilibrium in Repeated Games Played by Computationally Bounded Players by Joseph Y. Halpern, Rafael Pass and Lior Seeman
22. GSP with General Independent Click-Through-Rates by Ruggiero Cavallo and Christopher Wilkens
23. Dynamic Reserve Prices for Repeated Auctions: Learning from Bids by Yash Kanoria and Hamid Nazerzadeh
24. Truthful Approximations to Range Voting by Aris Filos-Ratsikas and Peter Bro Miltersen
25. Biobjective Online Bipartite Matching by Gagan Aggarwal, Yang Cai, Aranyak Mehta and George Pierrakos
26. Bounds on the Profitability of a Durable Good Monopolist by Gerardo Berbeglia, Peter Sloan and Adrian Vetta
27. The Value of Temporally Richer Data for Learning of Influence Networks by Munther Dahleh, John Tsitsiklis and Spyros Zoumpoulis
28. Randomized Revenue Monotone Mechanisms for Online Advertising by Gagan Goel, Mohammadtaghi Hajiaghayi and Mohammad Reza Khani
29. Matching Dynamics with Constraints by Martin Hoefer and Lisa Wagner
30. Concise Bid Optimization Strategies with Multiple Budget Constraints by Arash Asadpour, Mohammadhossein Bateni, Kshipra Bhawalkar and Vahab Mirrokni
31. To Save Or Not To Save: The Fisher Game by Nithum Thain, Adrian Vetta, Ruta Mehta and Laszlo Vegh
32. General Truthfulness Characterizations Via Convex Analysis by Rafael Frongillo and Ian Kash

Short papers:

1.   Position Auctions with Externalities and Brand Effects by Patrick Hummel and Preston McAfee
2.   Quality of Service in Network Creation Games by Andreas Cord-Landwehr, Alexander Mäcker and Friedhelm Meyer Auf der Heide
3.   Multilevel Network Games by Sebastian Abshoff, Andreas Cord-Landwehr, Daniel Jung and Alexander Skopalik
4.   On the Existence of Low-Rank Explanations for Mixed Strategy Behavior by Siddharth Barman, Umang Bhaskar, Federico Echenique and Adam Wierman
5.   Congestion games with higher demand dimensions by Max Klimm and Andreas Schütz
6.   Algorithmic and Hardness Results for Markets under Piecewise Leontief Concave Utilities by Jugal Garg
7.   The Role of Common and Private Signals in Two-Sided Matching With Interviews by Sanmay Das and Zhuoshu Li
8.   The Sequential Price Of Anarchy for Atomic Congestion Games by Jasper de Jong and Marc Uetz
9.   The Pricing War Continues: On Competitive Multi-Item Pricing by Omer Lev, Joel Oren, Craig Boutilier and Jeffrey Rosenschein
10. Approximate pure Nash equilibria in Social Context Congestion Games by Martin Gairing, Grammateia Kotsialou and Alexander Skopalik
11. Nash Stability in Fractional Hedonic Games by Vittorio Bilo', Angelo Fanelli, Michele Flammini, Gianpiero Monaco and Luca Moscardelli
12. Coordination Games on Graphs by Mona Rahn, Guido Schaefer, Sunil Simon and Krzysztof Apt
13. Time-Decaying Bandits for Non-stationary Systems by Junpei Komiyama and Tao Qin
14. Computing the Least-core and Nucleolus for Threshold Cardinality Matching Games by Qizhi Fang, Bo Li, Xiaoming Sun, Jia Zhang and Jialin Zhang

Tuesday, August 19, 2014

Approval voting

A short and amusing video showing how approval voting is better than the ubiquitous plurality voting (Hat tip to Nick Mattei!)

Tuesday, August 12, 2014

Maryam Mirzakhani wins the Fields Medal

Congratulations to Iranian Maryam Mirzakhani from Stanford University who is the first woman to win the Fields Medal.

Her Fields Medal citation includes the following:

Maryam Mirzakhani has made striking and highly original contributions to geometry and dynamical systems. Her work on Riemann surfaces and their moduli spaces bridges several mathematical disciplines—hyperbolic geometry, complex analysis, topology, and dynamics—and influences them all in return. She gained widespread recognition for her early results in hyperbolic geometry, and her most recent work constitutes a major advance in dynamical systems.

Here's an interesting biographical profile on Maryam.

Sunday, July 6, 2014

Harold Kuhn passes away

Pioneering mathematician Harold Kuhn has passed away this week. Kuhn was known for various contributions: Karush–Kuhn–Tucker conditions (for a solution in nonlinear programming to be optimal); Kuhn's theorem (that relates perfect recall, mixed and unmixed strategies and their expected payoffs); and the Hungarian method for computing the minimum cost perfect matching of a bipartite graph.

I recall attending Kuhn's plenary lecture at EURO 2010 in Lisbon where he gave a charming talk about the history of the Hungarian method and the recent discovery of how Carl Gustav Jacobi had already solved the assignment problem in the 19th century. Kuhn gave a detailed history of the other figures such as Dénes Konig and Jenó Egerváry who all played their part in the development of ideas related to the Hungarian Method.

Thursday, July 3, 2014

Cutting a round cake on scientific principles

Cake cutting started off as a topic of mathematical curiosity but has become a full-fledged topic within the field of "fair division" because of its ability to abstractly capture settings in which a heterogeneous divisible good is to be allocated among multiple people. The main goal is to identify methods to cut the cake that are as fair and welfare maximizing as possible. The field originated in the 1940's due to to work of Polish mathematicians Steinhaus, Knaster & Banach.

Recently, a video has been doing the rounds that suggests that a formal study of cake cutting dates even earlier than the 1940's. The video discusses a Nature letter by Francis Galton dated 1906 regarding the optimal method to cut the cake so as to minimize the exposed surface that may become dry.

For those who are interested to see Galton's actual letter, here it is: