Monday, April 7, 2014

Finding the optimal draw of a balanced knockout tournament for a player

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 tournament can significantly affect the outcome of the tournament. This phenomenon is explained in the next example.

Example 2: Consider the following pairwise comparisons between four tennis players based on their career head to head record in Table 1. +1 means that the row player has a winning head to head record against the column player and in this example let us (unreasonably) assume that in a pairwise match, the player with the better head to head record will win. If we make this assumption, then Federer will only win a balanced knockout tournament on the four players if Nadal plays Davydenko in the first round. Thus we can see that a suitably scheduled draw can affect the winner of the tournament. If Nadal plays Federer or Djokovic in the first round (semi-final), then Nadal will also go on to win the overall tournament.

Although this issue of the "significance of the draw"  has received much interest in mathematics, economics, and statistics, it was only in 2009 [VAS09] that a very natural computational problem was first formulated:  

Does there exist a draw in which a given player wins the balanced knockout tournament? 

We refer to the problem as TFP (Tournament Fixing Problem). The problem need not be seen in a negative light as some malicious tournament organizer trying to pave the way for his favorite player. The problem is also used in post tournament analysis and to gauge the relative strengths of the players and to analyze "what could have happened". The paper of Vu et al.  has received considerable received interest in the AI literature and was followed up with some interesting work [SV11a, SV11b, W10a]. Although generalizations of TFP have been examined, the complexity of TFP has remained an open problem.

Recently, in a paper
[AGM+14] with colleagues at the  ADT group, NICTA ---- Serge Gaspers,  Simon Mackenzie, Nicholas Mattei, Paul Stursberg (visiting from TU Munich) and Toby Walsh --- we have shown that TFP is NP-complete. The result has some interesting corollaries. If we consider a probabilistic model in which a player has a certain probability of winning against another player, then we obtain the corollary that unless P = NP, there exists no polynomial- time algorithm that approximates the maximum possible winning probability of a player within any given factor. A second corollary is that unless NP = RP, there exists no FPRAS for the problem of counting the number of draws in which a player wins.

We complement the result mentioned above by showing that there are two natural cases in which TFP can be solved in polynomial time. In the first case, the players can be divided into a constant number of player types. It appeals to the scenario where players can be divided into groups based on similar intrinsic ability. In the second case, there is a linear ordering on the ability of players with a constant number of exceptions where a player with lower ability beats a player with higher ability. 


[AGM+14] H. Aziz, S. Gaspers, S. Mackenzie, N. Mattei, P. Stursberg and T. Walsh. Fixing a Balanced Knockout Tournament. AAAI 2014 (forthcoming)

[SV11a] Stanton, I., and Vassilevska Williams, V. 2011. Manipulating stochastically generated single-elimination tournaments for nearly all players. In Proceedings of 7th In- ternational Workshop on Internet and Network Economics (WINE), 326–337. 
[SV11b] Stanton, I., and Vassilevska Williams, V. 2011. Rigging tournament brackets for weaker players. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI), 357–364. 

[VAS09] Vu, T.; Altman, A.; and Shoham, Y. 2009. On the complexity of schedule control problems for knockout tournaments. In Proceedings of the 8th International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 225–232. 

[W10a] Vassilevska Williams, V. 2010. Fixing a tournament. In Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI), 895–900. AAAI Press.

Monday, March 31, 2014

2nd Game Theory meets Optimisation Workshop

This is a plug for the 2nd Game Theory meets Optimisation Workshop, 9th April, NRL NICTA, Sydney:


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 Division

Fair Assignment Of Indivisible Objects Under Ordinal Preferences.

Simon MacKenzie, ADT, ORG@NICTA and UNSW

Cake Cutting Algorithms for Piecewise Constant and Piecewise Uniform Valuations.

Haris Aziz (joint work with Chun Ye), ADT, ORG@NICTA and UNSW

15.00 Tea & Coffee

15.20 Cooperative & other games

Iterated Crowdsourcing Dilemma.

Andres Abeliuk (joint work with Manuel Cebrian), ORG@NICTA and UMelbourne

Shapley Value in Vehicle Routing Games.

Nick Mattei, ADT group, ORG@NICTA

Seeding Tournaments.

Toby Walsh, ADT group, ORG@NICTA and UNSW

16.50 Discussion and close

Tuesday, March 11, 2014

The Addicitive Appeal of Candy Crush

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

Sunday, January 5, 2014

Predictions for 2014

In 1964, Isaac Asimov made some surprisingly accurate predictions about 2014:

[Hat tip to Toby Walsh for pointing out the article!]

Wednesday, December 25, 2013

Lessons of the 2012 Nobel Prize in Economics

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.

  1. 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.
  2. 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.
  3. 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 immediate national significance will probably lead to myopic incentive schemes that are detrimental to mathematics and to the creation of powerful abstract new ideas and concepts. 
  4. Fourth, Matching Theory is a great example of the breadth of current economic theory. It explores the ideas behind allocation of resources, and their implications for human wellbeing. 
  5. Finally, Matching Theory is an area with proven positive results in terms of public policy. However, in Australia, high school graduates are not allocated to universities with the use of a centralised mechanism that uses the DAA. The implementation of such a scheme would improve access of students to universities and would also lead to better matches between the two sides of the market. There are plenty of other areas that could benefit if Australian policymakers decided to use Matching Theory to formulate and implement better public policies.

Thursday, December 12, 2013

Engineering Social and Economic Institutions (ESEI)

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