Finding best players in a tournament with a probabilistic comparison function 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

*

*What is the probability that the chosen player is the best player?


*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()

 A: Not an answer, but an equivalent (and hopefully neater) reformulation of the problem.
We have $n$ players indexed from $1$ to $n$. When players $i,j$ ($i<j$) are matched, the probability that $i$ wins is a constant $p>1/2$ (no draws). The play a round-robin tournament.
What is the probability that player $1$ (the strongest one) is the (only) winner?
More in general: What is the probability that player $1$ is among the $k$ best scores?
A: The score of player $p_i$ is roughly normal with mean $p(i-1)+(1-p)(n-1-i)$ and constant variance $(n-1)p(1-p)$.  Integrate the pdf of the top one multiplied by the cdfs of all the others.  That won't have a nice formula but might have a nice approximation.  With a gap of $2p-1$ between players' means and standard deviation of $\sqrt{np(1-p)}$, the odds of the top player winning could be $O((2p-1)/\sqrt{np(1-p)})$.  Probabilities $p=1-k/ n$ for $k=O(1)$ might be the transition region where the top player's chances falls from 1.  Conversely, $p=(1/2)+k/\sqrt n$ might be the region where the weakest players' chances drop from $1/n$ to much less.
There is a small error in that cross-correlation between any two comes from a single comparison.
With a budget $b$, the means and variances are both scaled down in proportion to $b$, so the spreads overlap more.
Simulations using the normal distribution approximation suggest the chance of number-one winning is
$$\frac1{1+\left(\frac{\sqrt{np(1-p)}}{4p-2}\right)}$$
or, if you do $c{n\choose2}$ of the comparisons with $0\lt c\lt 1$,
$$\frac1{1+\left(\frac{\sqrt{np(1-p)/c}}{4p-2}\right)}$$
