Friday, December 12, 2014

Schedule of WINE 2014


[Taken from http://wine2014.amss.ac.cn/dct/page/70014]


December 14:
Location of Conference Venue: South Building of AMSS
9:00am17:00pm: Registration (Location:the 2nd floor near N204)

10:00am12:00pm: Tutorial
Nir Gavish.
Computation of equilibrium bidding strategies in asymmetric first price auctions. (Location: N204)
1:303:30pm: Tutorial (Location: N204) Kamal Jain.
Theoretical Analysis of Business Models.
3:304:00pm: Coffee break
4:006:00pm: Tutorial (Location: N204)
Martin Gairing.
Quantifying the Efficiency of Congestion Games
6:00pm: End of Tutorials day. 


December 15:
8:00am12:00am: Registration (Location:the 2nd floor near N204) 8:509:00am: Opening (Location: N204)
9:00am: Invited Talk by Robert Aumann
10:00am: Coffee Break

10:30am: Session 1 (Location: N204)
10:30
10:54:Shaddin Dughmi, Li Han and Noam Nisan. Sampling and
Representation Complexity of RevenueMaximization
10:5411:18:Qiang Zhang, Stefano Leonardi, Riccardo Colini Baldeschi and Piotr Sankowski. Revenue Maximizing Envyfree Fixedprice Auctions with Budgets
11:1811:42: MuntherDahleh, John Tsitsiklis and Spyros Zoumpoulis. The
Value of Temporally Richer Data for Learning of Influence Networks 11:4212:06: Yash Kanoria and Hamid Nazerzadeh. Dynamic Reserve Prices for Repeated Auctions: Learning from Bids
12:0612:30: Gerardo Berbeglia, Peter Sloan and Adrian Vetta. Bounds on the Profitability of a Durable Good Monopolist
12:30pm: Buffet Lunch (Location:the 3rd floor at Wuke Hotel; A ticket is needed) 2:00pm: Invited Talk by Noam Nisan (Location: N204)
3:00pm: Coffee Break
3:30pm: Session 2 (Location: N204)

3:303:54:Nicolas Bousquet, Sergey Norin and Adrian Vetta. A NearOptimal Mechanism for Impartial Selection
3:544:18:JarosławByrka and Krzysztof Sornat. PTAS for Minimax Approval Voting
4:184:42:ArisFilosRatsikas and Peter Bro Miltersen. Truthful Approximations to Range Voting
4:425:06:Haris Aziz and Chun Ye. Cake Cutting Algorithms for Piecewise Constant and Piecewise Uniform Valuations
5:065:30:Yiling Chen, Or Sheffet and SalilVadhan. Privacy Games
5:305:54: Rad Niazadeh, Yang Yuan and Robert Kleinberg. Simple and Near
Optimal Mechanisms for Market Intermediation
7:00pm: Banquet andfolk music performance with traditional Chinese instruments (Location: Chao Fu Gong at the 2nd floor of Jade Palace Hotel; A ticket is needed)
9:00pm: End of Day 


December 16:
8:20am: Registration and Coffee (Location: 2nd floor of South Bld.) 8:50am: Announcement on WINE’15 (Location: N204)
9:00am: Invited Talk by Andrew Yao (Location: N204)
10:00am: Coffee Break

10:30am: Session 1 (Location: N204)
10:30
10:54:Vasilis Gkatzelis, Konstantinos Kollias and Tim Roughgarden.
Optimal CostSharing in Weighted Congestion Games
10:5411:18:Matthias Feldotto, Martin Gairing and Alexander Skopalik.
Bounding the Potential Function in Congestion Games and Approximate Pure Nash Equilibria
11:1811:42: Tobias Harks, Max Klimm and Britta Peis. Resource Competition on Integral Polymatroids
11:4212:06: SmritiBhagat, Anthony Kim, S. Muthukrishnan and Udi Weinsberg. The Shapley Value in Knapsack Budgeted Games
12:0612:30: ArgyriosDeligkas, John Fearnley, Rahul Savani and Paul Spirakis.
Computing Approximate Nash Equilibria in Polymatrix Games
12:30pm: Lunch (Location:the 4th floor at Wuke Hotel; A ticket is needed) 2:00pm: Invited Talk by Christos Papadimitriou(Location: N204)
3:00pm: Coffee Break
3:30pm: Session 2 (Location: N204)

3:303:54:Hau Chan and Jing Chen. Truthful Multiunit Procurements with Budgets
3:544:18:Dennis Kraft, Salman Fadaei and Martin Bichler. Fast Convex Decomposition for Truthful Social Welfare Approximation
4:184:42:MariaFlorinaBalcan, Amit Daniely, Ruta Mehta, Ruth Urner and Vijay V. Vazirani. Learning economic parameters from revealed preferences
4:425:06:Salman Fadaei and Martin Bichler. A Truthfulinexpectation Mechanism for the Generalized Assignment Problem
5:065:30:Rafael Frongillo and Ian Kash. General Truthfulness Characterizations Via Convex Analysis
5:30pm:Short Break and WINE Business Meeting (Location: N204)
6:30pm: Poster Session/Reception (Location:the 2
nd floor in the opposite of the lifts) 9:30pm: End of Day 


December 17:
8:30am: Registration and Coffee (Location: 2nd floor of South Bld.) 9:00am: Invited Talk by Xiaotie Deng (Location: N204)
10:00am: Coffee Break
10:30am: Session 1 (Location: N204)

10:3010:54: Ruggiero Cavallo and Christopher Wilkens. GSP with General Independent ClickThrough Rates
10:5411:18: Gagan Aggarwal, Yang Cai, Aranyak Mehta and George Pierrakos. Biobjective Online Bipartite Matching
11:1811:42: GaganGoel, Mohammadtaghi Hajiaghayi and Mohammad Reza Khani. Randomized Revenue Monotone Mechanisms for Online Advertising
11:4212:06: Arash Asadpour, Mohammadhossein Bateni, Kshipra Bhawalkar and VahabMirrokni. Concise Bid Optimization Strategies with Multiple Budget Constraints
12:0612:30: Joseph Y. Halpern, Rafael Pass and Lior Seeman. Not Just an Empty Threat: SubgamePerfect Equilibrium in Repeated Games Played by Computationally Bounded Players
12:30pm: Lunch (Location: the 4th floor at Wuke Hotel; A ticket is needed) 2:00pm: Invited Talk by Peng Ye (Location: N204)
3:00pm: Coffee Break
3:30pm: Session 2 (Location: N204)

3:303:54: LudkCigler, Wolfgang Dvoák, Monika Henzinger and Martin Starnberger. Limiting Price Discrimination when Selling Products with Positive Network Externalities
3:544:18: Edith Elkind. Coalitional Games on Sparse Social Networks
4:184:42: MohammadtaghiHajiaghayi, Hamid Mahini, AnshulSawant, Mohammadhossein Bateni and MelikaAbolhassani. Network Cournot Competition
4:425:06:KameshMunagala and Xiaoming Xu. Valuebased Network Externalities and Optimal Auction Design
5:065:30: Martin Hoefer and Lisa Wagner. Matching Dynamics with Constraints
5:305:54: Nithum Thain, Adrian Vetta, Ruta Mehta and Laszlo Vegh. To Save or Not To Save: The Fisher Game
6:00pm: End of Day and WINE2014

Sunday, December 7, 2014

Interesting new website on game theory

The Game Theory Group at Polytechnic of Milano has a web page, with interesting info for game theoristshttp://www.gametheory.polimi.it/

Thursday, September 25, 2014

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. 

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!)