6
$\begingroup$

You are given a function $\operatorname{rk}:\{1\dots 2^k\}\rightarrow \mathbb{N^+}$ representing the ranks of the players $1\dots2^k$ in a participating in a tournament. The tournament evolves in a random way, so that when player $i$ faces player $j$, he wins with probability $\frac{\operatorname{rk}(i)}{\operatorname{rk}(i)+\operatorname{rk}(j)}$. When a player loses a game, he gets knocked out of the tournament, thus the tournament finishes in $k$ rounds.

You are requested to arrange the players into a knockout tournament starting line-up (i.e. on the leaves of a complete binary tree of height $k$) in the way that maximizes the probability that player $1$ wins the tournament.

The official greedy solution, presented without any trace of proof, is the following:

  • Sort the players $1, r_2, r_3, \dots r_{2^k}$, where $r_2, \dots r_{2^k}$ are the players $2 \dots 2^k$ sorted in ascending order of their rank.
  • Arrange players $1, \dots, 2^{k-1}$ in the left-subtree and $2^{k-1} + 1, \dots 2^k$ in the right subtree and recurse.
  • For each node $v$ of the tree compute (bottom-up using dynamic programming) the probability vector $P_v$ such that $P_v[x]$ is the probability of player $x$ winning the sub-tournament rooted at $v$.

This algorithm runs in $\mathcal{O}(n^2 \log n)$.

How to prove that the algorithm is also correct?

The original problem is from ICPC NWERC 2017 (problem K). Here we posted a simplified version.

$\endgroup$
  • 1
    $\begingroup$ cs.stackexchange.com/q/59964/755 $\endgroup$ – D.W. Jan 13 at 18:49
  • 1
    $\begingroup$ This problem is a special case of the Probabilistic Tournament Fixing Problem (PTFP) in which the Bradley-Terry model is used for comparisons. $\endgroup$ – Throckmorton Jan 14 at 21:26
  • $\begingroup$ To clarify, the paper mentioned above by Bryce Kille does not deal with the current problem, as far as I have checked. That paper deals with tournament fixing problem (TFP), another very special case of PTFP. In TFP, for any two players, one of them always beats the other one. There can be "beating cycles" such as A beats B, B beats C and C beat A. $\endgroup$ – John L. Jan 15 at 17:44
  • $\begingroup$ @JohnL. Correct, the problem was introduced with no name in Vu et al 2009. See section 4 for the balanced tree restriction. $\endgroup$ – Throckmorton Jan 15 at 18:17
  • $\begingroup$ A more detailed overview is on Vu's thesis. See the discussion on the problem with monotonic winning probabilities (4.5.3). $\endgroup$ – Throckmorton Jan 15 at 18:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.