Finding best players in a tournament with a probabilistic comparison function https://ift.tt/37H9UBb

I am currently facing the following problem in my research and I have no clue how to tackle this kind of question.

The problem

Imagine you have a tournament with $n$ players $P=\{p_1,...,p_n\}$. My goal is to determine one of the best players in my tournament.

I do have a comparison function $f: P x P\to \{0,1\}$ that can tell me which of two given players is better, i.e. $f(p_1,p_2)=1$ iff player two is better than player one and $f(p_1,p_2)=0$ iff player one is better than player two. You can think of $f$ as the $<$ relation.

The kicker is that my comparison function $f$ has an error, meaning that it will give me the correct result of my comparison with a probability $p>0.5$. Calculating $f$ will take some time and thus I want to find a good player for my tournament with the least amount of queries. My current approach is to compare all players with each other which gives me a total amount of $b \in O(n^2)$ comparison calls. I then chose the player $p_i$, which "won" the most comparisons.

Edit:

Please be aware that my comparison function will give me the same result for a call $f(p_i,p_j)$ no matter how often I call it. So the probability that the result is correct is $p$, but the function itself is deterministic. My example below is a bit misleading. However, each comparison call is only done once so this won't be a problem.

Key questions

1. What is the probability that the chosen player is the best player?

2. What is the probability that the chosen player is in the top k percent?

My thoughts

I think that question one might be easier to calculate as my best player will win all comparisons if $p=1$ and I can deduce the probability that $k$ comparisons were correct. However, I am stuck at the point at which I have to calculate the probability that it in fact is the player that "won" the most comparisons as others might be evaluated incorrectly.

My dream is to get a formula that allows me to calculate the desired probabilities for different $p,n$, and budget $b$.

Simulation

I wrote a small simulation in Python which revealed some interesting facts about the influence of $p$. In my example, the tournament players are represented as numbers $0,...,63$. The function $f$ is the standard $<$ relation with a given probability. In the plot below I have plotted the mean position (y-axis) that was selected as the best individual for different $p$ (x-axis). You can find the source code below.

import random
import numpy as np
from itertools import combinations
from tqdm import tqdm
import matplotlib.pyplot as plt

x, y = [], []

n = 64 # How many players
nums = np.arange(n).tolist() # Player strengths
count = 1000 # The amount of tests (O(n^2)) combinations that should be made

for p in tqdm(np.arange(0, 1, 0.01)):
    x.append(p)

    def compare(a, b):
        r = random.random()
        if r <= p:
            return a < b
        else:
            return a >= b

    def tournament():
        scores = [0] * n
        for a, b in combinations(nums, 2):
            result = compare(a, b)
            if result:
                scores[b] += 1
            else:
                scores[a] += 1

        best = max(nums, key=lambda x: scores[x])
        return best

    vals = []

    for _ in range(count):
        vals.append(tournament())

    y.append(np.mean(vals))

plt.plot(x, y)

plt.show()

from Hot Weekly Questions - Mathematics Stack Exchange
michip96