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

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

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:

Friday, January 9, 2015

Friday, December 12, 2014

Schedule of WINE 2014

[Taken from]

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