More than a year ago a badminton scandal during the London 2012 Olympics rocked the really-care-about-mechanism-design corner of the blogosphere. Bobby Kleinberg reported:
The competition is structured in two stages: a round-robin stage in which the teams compete to earn placement in a second-stage single-elimination tournament. The second-seeded team in the competition, Tian Qing and Zhao Yunlei of China, suffered an upset loss to a Danish team in the first stage. As a result, they were placed as one of the lowest-seeded teams in the second-stage tournament. At that point it became advantageous for the remaining teams that had already secured a second-stage berth to lose their final first-stage match in order to avoid being paired against Qing and Yunlei in the first round of the second stage. Spectators watched in frustration and disbelief as the athletes deliberately served into the net and hit shots out of bounds in an effort to lose the match. Olympic officials afterward decided to disqualify the offending teams from the competition.
Bobby asked whether it’s time for the International Olympic Committee to start reading research papers on mechanism design. A year ago the answer was “probably not”, but a recent paper may soon have members of the IOC scrambling to get their math degrees. There are two interesting things about this paper, written by Marc Pauly and published in Social Choice and Welfare.
The first interesting thing is, well, the results. Pauly considers competition formats in which the competing teams (or players) are partitioned into two subsets. In the first stage, the teams in each subset compete in a round-robin tournament, with the top (in terms of the number of wins) teams from each subset proceeding to the next stage. In the second stage, the winner is chosen by a function that aggregates the results of competitions between the second-stage teams. His main result is that there is no second-stage function that would make this process monotonic, which you can think of as strategyproof — a team should never be able to become a winner by throwing a match — if a few other basic axioms are imposed and there are at least six teams. My conclusion from this result is that the two-stage, round-robin-first format used in Badminton is inherently flawed — but, as Pauly notes in his conclusions, there are many other competition formats one can consider.
Back in 2012, people have floated different ideas for other competition formats, especially in response to a Cheap Talk blog post on the same topic. But I kinda like an idea suggested in a comment on Bobby’s post by… me (of course I’m being completely impartial here). Following up on a comment by Suresh Venkatsubramanian, I suggested determining the bracket in the second round uniformly at random, and incentivizing teams to do as well as they can in the first round by letting their probability of advancing to the second round monotonically increase with their number of wins in the first round. I thought this is nice because it reminded me of something Vince Conitzer once told me, that admittance into medical school in the Netherlands depends on your school grades and a lottery — the better your grades, the more likely you are to get in. As an aside, when I checked just now that I wasn’t making this up, I found an article claiming that the chance is only 70% for those with the highest grades. More interestingly, some universities that at some point started selecting half of their admitted students “deterministically” found that there is no difference in performance between this half and the students in the other half who just got lucky.
Going back to Pauly’s paper, another interesting thing about it is that it cites Bobby’s post and the Cheap Talk blog post. I haven’t seen many scientific papers citing blog posts, and it may well be the first published paper citing our blog. Ironically, the cheap talk post is called “Let’s write this paper”; apparently Pauly took the title literally!
Like this:
Like Loading...
Read Full Post »
Turing's Invisible Hand 