Algorithmics, Social choice, Market Design, and Other Topics

Balanced knockout tournaments are one of the most common formats for sports competitions, and are also used in elections and decision-making. Such tournaments can be represented by a balanced binary tree in which the leaves correspond to the players. A balanced knockout tournament is conducted in the following fashion. Players that correspond to sibling leaf nodes play a match against each other. The winner of the match proceeds up the tree to the next round. The winner of the balanced knockout tournaments is the player who reaches the root node. Example 1 : One of the balanced knockout tournament of which I have fond memories is the one on four teams that represents the semi finals and final of the 1992 cricket world cup. South Africa and New Zealand who lost their respective semi-finals were eliminated whereas Pakistan and England contested the final in Melbourne. It has long been observed that the draw (the way players/teams are paired up) of a balanced knockout tourna...

This is a plug for the 2nd Game Theory meets Optimisation Workshop , 9th April, NRL NICTA, Sydney: Program 09.00 Welcome 09.10 Markets On The Durable Good Monopoly Problem. Gerardo Berbeglia, Melbourne Business School (Joint work with Peter Sloan and Adrian Vetta) Dynamic Markets for Lemons: Performance, Liquidity, and Policy Intervention. Prof. John Wooders, UTS 10.10 Tea & Coffee 10.30 Grids Towards a realistic application of mechanism design in demand response aggregation. Sleiman Mhanna, USyd Proposal Outline of Completely Distributed Power Control Game for Peer-Aware Communications. Nicole Sawyer, Network Research Group, CRL, NICTA. 11.30 Traffic games Is Traffic Equilibrium Pure Nash, Mixed or Stochastic? Evidence from Laboratory Experiments. Vinayak V. Dixit and Laurent Denant-Boemont, rCiti, UNSW Incentive-based Mechanisms to Promote Sustainable Transport. David Rey, Vinayak V. Dixit, Jean-Luc Ygnace and S. Travis Waller, rCiti, UNSW 12.30 Lunch 14.00 Fair Divisi...

There is interesting coverage in the New Scientist of Toby Walsh's recent report that the Candy Crush problem is NP-hard.

The 12th meeting of the Society for Social Choice and Welfare    June 18-21, 2014, Boston College Fifth International Workshop on Computational Social Choice Pittsburgh, Pennsylvania, June 23-25, 2014 Interdisciplinary Analysis of Voting Rules  Caen, France  July 8-12th 2014.

In 1964, Isaac Asimov made some surprisingly accurate predictions about 2014: http://www.nytimes.com/books/97/03/23/lifetimes/asi-v-fair.html [Hat tip to Toby Walsh for pointing out the article!]

Richard Cornes and José A. Rodrigues-Neto have penned down an article on "Is Policy Too Important to be Left to Empiricists? Lessons of the 2012 Nobel Prize in Economics" . The article surveys the contribution of Roth and Shapley. I reproduce the conclusions verbatim from the article. The last point mentions domains where matching markets can be useful in Australia. First, it could be dangerous to dismiss basic research as necessarily less important because of its lack of obvious immediate impact on pressing problems of the day. Second, some of the most applicable and useful ideas often come along first in the most abstract forms. They require time to mature and to prove their true value; in this case a few decades. This does not fit with the politics of the democratic electoral cycle. Third, the power of abstract mathematical ideas should never be underestimated. Looking to social sciences or policy studies through the lens of what seems to be of im...

I came across an interesting and impressive research group called Center for Engineering Social and Economic Institutions (ESEI), Zurich . The center's goal is to devise "new mechanisms for auctions, trading, matching, voting, social learning and networking".