4
$\begingroup$

Let $\Pi$ be a finite set of players. A game on $\Pi$ is a matrix of probabilities $p(i, j)$ for $i, j\in\Pi$ such that $p(i, j) = 1 - p(j, i)$ (we think of $p(i, j)$ as the probability of $i$ beating $j$ at some game).

A logistic game on $\Pi$ is a game $p$ satisfying the odds-transitivity property:

$$\omega(i, j) \omega(j, k) = \omega(i, k)\quad \forall i,j,k$$

where $\omega(i, j) = \frac{p(j, i)}{1 - p(i, j)}$ are the odds of $i$ beating $j$.

Where $p$ is any game, we define $A(p)$, the vector assigning to each player their probability of winning against a random other player:

$$A(p, i) = \frac 1 {n - 1} \sum_{j\neq i} p(i, j)$$

where $n$ is the number of players.

Conjecture. The mapping $p\to A(p)$ is injective on the set of logistic games.

Is this conjecture true? One can prove it for $n=3$ players and it's trivial for $n=2$. Essentially, if $p$ and $q$ are two games, the condition $A(p)=A(q)$ is a system of linear equations which has many solutions (there are on the order of $n^2$ variables, but only $n$ linear constraints). The condition that $p$ and $q$ be logistic is a non-linear constraint on the variables, so the claim is that the non-linear constraint is enough to give the non-determined linear system one solution.

This problem seems difficult to me, but maybe there's a simple solution. I kind of just want a sanity check.

(Background: the question is actually related to the question of convergence of the Elo rating update algorithm. The conjecture would imply that the only stable equilibrium of the algorithm is when it predicts the correct win probabilities for all players.)

$\endgroup$

1 Answer 1

3
$\begingroup$

Surprisingly (to me), this problem seems to have a simple solution via graph theory.

Imagine we start with a logistic game $p$, and we want to modify it to get another logistic game $q$ in which each player retains the same overall probability of winning. There must exist at least one pair of players $i, j$ such that $q(i, j) > p(i, j)$.

Since there is a player that has been made stronger against $j$, in order for $j$'s overall win probability to remain the same, $j$ must be made stronger against some other player. That player must then be made stronger against some other player, and so on. In this way we can walk through the finite set of players. Since the set is finite, at some point we must visit a previously visited player. But this implies a loop in which $i$ is stronger against $j$, $j$ is stronger against $k$, ...is stronger against $i$. The existence of this kind of loop violates odds transitivity.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.