HOME

TheInfoList



OR:

Stochastic transitivity models are
stochastic Stochastic (, ) refers to the property of being well described by a random probability distribution. Although stochasticity and randomness are distinct in that the former refers to a modeling approach and the latter refers to phenomena themselv ...
versions of the transitivity property of binary relations studied in
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
. Several models of stochastic transitivity exist and have been used to describe the probabilities involved in experiments of paired comparisons, specifically in scenarios where transitivity is expected, however, empirical observations of the binary relation is probabilistic. For example, players' skills in a sport might be expected to be transitive, i.e. "if player A is better than B and B is better than C, then player A must be better than C"; however, in any given match, a weaker player might still end up winning with a positive probability. Tightly matched players might have a higher chance of observing this inversion while players with large differences in their skills might only see these inversions happen seldom. Stochastic transitivity models formalize such relations between the probabilities (e.g. of an outcome of a match) and the underlying transitive relation (e.g. the skills of the players). A binary relation \succsim on a set \mathcal is called transitive, in the standard ''non-stochastic'' sense, if a \succsim b and b \succsim c implies a \succsim c for all members a,b,c of \mathcal. ''Stochastic'' versions of transitivity include: # Weak Stochastic Transitivity (WST): \mathbb(a\succsim b)\geq \tfrac and \mathbb(b\succsim c)\geq \tfrac implies \mathbb(a\succsim c)\geq \tfrac, for all a,b,c \in \mathcal; # Strong Stochastic Transitivity (SST): \mathbb(a\succsim b)\geq \tfrac and \mathbb(b\succsim c)\geq \tfrac implies \mathbb(a\succsim c)\geq \max \, for all a,b,c \in \mathcal; # Linear Stochastic Transitivity (LST): \mathbb(a\succsim b) = F(\mu(a) - \mu(b)), for all a,b \in \mathcal, where F:\mathbb \to ,1/math> is some increasing and function (called a ''comparison function''), and \mu: \mathcal\to \mathbb is some mapping from the set \mathcal of alternatives to the real line (called a ''merit function'').


A toy example

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 B is the number of blue marbles and G is the number of green marbles in the bag, then the probability \mathbb(\text \succsim \text) of Billy winning against Gabriela is \mathbb(\text \succsim \text) = \frac = \frac = \frac. In this example, the marble game satisfies linear stochastic transitivity, where the comparison function F:\mathbb \to ,1/math> is given by F(x) = \frac and the merit function \mu: \mathcal\to \mathbb is given by \mu(M) = \ln(M), where M is the number of marbles of the player. This game happens to be an example of a Bradley–Terry model.


Applications

* ''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 TrueSkill is a skill-based ranking system developed by Microsoft for use with video game matchmaking on Xbox Live. Unlike the popular Elo rating system, which was initially designed for chess, TrueSkill is designed to support games with more than t ...
used for the Xbox gaming platform. * ''Models of Psychology and Rationality'' - Thurstonian models (see Case 5 in law of comparative judgement), Fechnerian models and also
Luce's choice axiom In probability theory, Luce's choice axiom, formulated by R. Duncan Luce (1959), states that the probability of selecting one item over another from a pool of many items is not affected by the presence or absence of other items in the pool. Select ...
are theories that have foundations on the mathematics of stochastic transitivity. Also, models of
rational choice theory Rational choice theory refers to a set of guidelines that help understand economic and social behaviour. The theory originated in the eighteenth century and can be traced back to political economist and philosopher, Adam Smith. The theory postula ...
are based on the assumption of transitivity of
preference In psychology, economics and philosophy, preference is a technical term usually used in relation to choosing between alternatives. For example, someone prefers A over B if they would rather choose A than B. Preferences are central to decision th ...
s (see Von Neumann's utility and Debreu's Theorems), these preferences, however, are often revealed with noise in a stochastic manner. * ''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. 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. Social choice theory also has foundations that depend on stochastic transitivity models.


Connections between models

Positive Results: # 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 \implies SST\impliesWST ; # Since the Bradeley-Terry models and the are LST models, they also satisfy SST and WST; # Due to the convenience of , a few authors have identified axiomatic of linear stochastic transitivity (and other models), most notably
Gérard Debreu Gérard Debreu (; 4 July 1921 – 31 December 2004) was a French-born economist and mathematician. Best known as a professor of economics at the University of California, Berkeley, where he began work in 1962, he won the 1983 Nobel Memorial Prize ...
showed that: + \implies LST (see also
Debreu Theorems In economics, the Debreu theorems are several statements about the representation of a preference ordering by a real-valued function. The theorems were proved by Gerard Debreu during the 1950s. Background Suppose a person is asked questions o ...
); # Two LST models given by
invertible In mathematics, the concept of an inverse element generalises the concepts of opposite () and reciprocal () of numbers. Given an operation denoted here , and an identity element denoted , if , one says that is a left inverse of , and that is ...
comparison functions F(x) and G(x) are if and only if F(x) = G(\kappa x)for some \kappa \geq 0. Negative Results: # Stochastic transitivity models are empirically , however, they may be falsifiable; # between LST comparison functions F(x) and G(x) can be impossible even if an infinite amount of data is provided over a finite number of ; # The for WST, SST and LST models are in general
NP-Hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
, however, near optimal polynomially computable estimation procedures are known for SST and LST models.


See also

* Nontransitive game *
Decision theory Decision theory (or the theory of choice; not to be confused with choice theory) is a branch of applied probability theory concerned with the theory of making decisions based on assigning probabilities to various factors and assigning numerical ...
*
Utilitarianism In ethical philosophy, utilitarianism is a family of normative ethical theories that prescribe actions that maximize happiness and well-being for all affected individuals. Although different varieties of utilitarianism admit different chara ...


References

{{reflist Transitive relations