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:

Saturday, June 28, 2014

ESEI / UTS Center for Market Design Conference in honor of John Ledyard: 24-25 July 2014

Location: Room B424, Level 4, ‘B Block’, UTS Business School 1-59 Quay Street, Haymarket, Sydney, Australia

July 24, 2014 

(9am - 4:30pm)

Roy Green, Dean of the UTS Business School.Welcome

John Ledyard (California Institute of Technology)
“A Simple Buy‐back Auction for Fisheries Management” with Guillerme Freitas and Theodore Groves 

Leslie M. Marx (Duke University)
“Equilibrium Bid Strategies in an Auction with Bidder Preferences and Resale”
with Simon Loertscher

Jun Zhang (University of Technology, Sydney)
“Information Disclosure In Contests: A Bayesian Persuasion Approach” with Junjie Zhou

Murali Agastya (University of Sydney)
“On Efficient Partnership Dissolution” with Oleksii Birulin

Paul PezanisChristou (University of Adelaide)
 “Supply information policies in sequential and simultaneous high‐bid auctions”
with Nobuyuki Hanaki and Tibor Neugebaeur

Tom Wilkening (University of Melbourne)
“A Long Way Coming: Designing Centralized Markets with Privately Informed Buyers and Sellers” with Simon Loertscher and Leslie M. Marx

Antonio Rosato (University of Technology, Sydney)
“Loss Aversion in Sequential Auctions: Endogenous Interdependence, Informational Externalities and the “Afternoon Effect"

July 25, 2014 

(9am - 4:30pm)

Peter Bossaerts (University of Melbourne)
“Human‐Robot Interaction In A Classical Experiment On Multi‐Period Asset Pricing” with Elena Asparouhova

Robert Slonim (University of Sydney)
“Improving Blood Donations: A Summary of 6 Papers” with Ashley Craig, Ellen Garbarino, Stephanie Heger, Victor Iajya, Mario Macis, Nicola Lacetera and Carmen Wang.

Haris Aziz (NICTA and UNSW)
“Cake Cutting Algorithms for Piecewise Constant and Piecewise Uniform Valuations” with Chun Ye

Andy McLennan (University of Queensland)
“On Uniqueness of Equilibrium in the Kyle Model” with Paulo Klinger Monteiro and Rabee Tourky

Claudio Mezzetti (University of Melbourne)
“Repeated Nash Implementation” with Ludovic Renou  

Juan Carlos, Carbajal (University of New South Wales)
“Plasticity, Monotonicity, and Implementability” with Rudolf Müller

Priscilla Man (University of Queensland)
“Generalized Majority Rules” with Marco Faravelli