Stochastic transitivity

The marble game - Assume two kids, Billy and Gabriela, collect marbles. Billy collects blue marbles and Gabriela green marbles. When they get together they play a game where they mix all their marbles in a bag and sample one randomly. If the sampled marble is green, then Gabriela wins and if it is blue then Billy wins. If ${\displaystyle B}$ is the number of blue marbles and ${\displaystyle G}$ is the number of green marbles in the bag, then the probability ${\displaystyle \mathbb {P} ({\text{Billy}}\succsim {\text{Gabriela}})}$ of Billy winning against Gabriela is

${\displaystyle \mathbb {P} ({\text{Billy}}\succsim {\text{Gabriela}})={\frac {B}{B+G}}={\frac {e^{\ln(B)}}{e^{\ln(B)}+e^{\ln(G)}}}={\frac {1}{1+e^{\ln(G)-\ln(B)}}}}$.

In this example, the marble game satisfies linear stochastic transitivity, where the comparison function ${\displaystyle F:\mathbb {R} \to [0,1]}$ is given by ${\displaystyle F(x)={\frac {1}{1+e^{-x}}}}$ and the merit function ${\displaystyle \mu$ :{\mathcal {A}}\to \mathbb {R} } is given by ${\displaystyle \mu (M)=\ln(M)}$, where ${\displaystyle M}$ is the number of marbles of the player. This game happens to be an example of a Bradley–Terry model.[7]

• Ranking and Rating - Stochastic transitivity models have been used as the basis of several ranking and rating methods. Examples include the Elo-Rating system used in chess, go, and other classical sports as well as Microsoft's TrueSkill used for the Xbox gaming platform.
• Models of Psychology and Rationality - Thurstonian models[8] (see Case 5 in law of comparative judgement), Fechnerian models[3] and also Luce's choice axiom[9] are theories that have foundations on the mathematics of stochastic transitivity. Also, models of rational choice theory are based on the assumption of transitivity of preferences (see Von Neumann's utility and Debreu's Theorems), these preferences, however, are often revealed with noise in a stochastic manner.[10][11][12]
• Machine Learning and Artificial Intelligence (see Learn to Rank) - While Elo and TrueSkill rely on specific LST models, machine learning models have been developed to rank without prior knowledge of the underlying stochastic transitivity model or under weaker than usual assumptions on the stochastic transitivity.[13][14][15] Learning from paired comparisons is also of interest since it allows for AI agents to learn the underlying preferences of other agents.
• Game Theory - Fairness of random knockout tournaments is strongly dependent on the underlying stochastic transitivity model.[16][17][18] Social choice theory also has foundations that depend on stochastic transitivity models.[19]

Positive Results:

1. Every model that satisfies Linear Stochastic Transitivity must also satisfy Strong Stochastic Transitivity, which in turn must satisfy Weak Stochastic Transitivity. This is represented as: LST ${\displaystyle \implies }$ SST${\displaystyle \implies }$WST ;
2. Since the Bradeley-Terry models and the Thurstanian model 5 are LST models, they also satisfy SST and WST;
3. Due to the convenience of more structured models, a few authors[1][2][3][4][20][21] have identified axiomatic justifications of linear stochastic transitivity (and other models), most notably Gérard Debreu showed that:[22] Quadruple Condition + Continuity ${\displaystyle \implies }$ LST (see also Debreu Theorems);
4. Two LST models given by invertible comparison functions ${\displaystyle F(x)}$ and ${\displaystyle G(x)}$ are equivalent if and only if ${\displaystyle F(x)=G(\kappa x)}$for some ${\displaystyle \kappa \geq 0.}$[23]

Negative Results:

1. Stochastic transitivity models are empirically unverifiable,[4] however, they may be falsifiable;
2. Distinguishing between LST comparison functions ${\displaystyle F(x)}$ and ${\displaystyle G(x)}$ can be impossible even if an infinite amount of data is provided over a finite number of points;[24]
3. The estimation problem for WST, SST and LST models are in general NP-Hard,[25] however, near optimal polynomially computable estimation procedures are known for SST and LST models.[13][14][15]

• Nontransitive game
• Decision theory
• Utilitarianism