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:

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.

Friday, January 9, 2015

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: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: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.