Login
Login

stochastic transitivity

Stochastic transitivity models{{Cite journal|last=Fishburn|first=Peter C.|date=November 1973|title=Binary choice probabilities: on the varieties of stochastic transitivity|journal=Journal of Mathematical Psychology|volume=10|issue=4|pages=327–352|doi=10.1016/0022-2496(73)90021-7|issn=0022-2496}}{{Cite journal|last=Clark|first=Stephen A.|date=March 1990|title=A concept of stochastic transitivity for the random utility model|journal=Journal of Mathematical Psychology|volume=34|issue=1|pages=95–108|doi=10.1016/0022-2496(90)90015-2}}{{Cite journal|last=Ryan|first=Matthew|date=2017-01-21|title=Uncertainty and binary stochastic choice|journal=Economic Theory|volume=65|issue=3|pages=629–662|doi=10.1007/s00199-017-1033-4|s2cid=125420775|issn=0938-2259}}{{Cite journal|last1=Oliveira|first1=I.F.D.|last2=Zehavi|first2=S.|last3=Davidov|first3=O.|date=August 2018|title=Stochastic transitivity: Axioms and models|journal=Journal of Mathematical Psychology|volume=85|pages=25–35|doi=10.1016/j.jmp.2018.06.002|issn=0022-2496}} are stochastic versions of the transitivity property of binary relations studied in 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{A} 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{A}.

Stochastic versions of transitivity include:

  1. Weak Stochastic Transitivity (WST): \mathbb{P}(a\succsim b)\geq \tfrac{1}{2} and \mathbb{P}(b\succsim c)\geq \tfrac{1}{2} implies \mathbb{P}(a\succsim c)\geq \tfrac{1}{2}, for all a,b,c \in \mathcal{A};{{cite report | url=https://web.stanford.edu/group/csli-suppes/techreports/IMSSS_17.pdf | author=Donald Davidson and Jacob Marschak | title=Experimental tests of a stochastic decision theory | institution=Stanford University | type=Technical Report | number=17 | date=Jul 1958 }}{{rp|12}}{{cite journal | url=https://www.chapman.edu/research/institutes-and-centers/economic-science-institute/_files/ifree-papers-and-photos/michel-regenwetter1.pdf | author=Michel Regenwetter and Jason Dana and Clintin P. Davis-Stober | title=Transitivity of Preferences | journal=Psychological Review | volume=118 | number=1 | pages=42–56 | year=2011 | doi=10.1037/a0021150 | pmid=21244185 }}{{rp|43rg}}
  2. Strong Stochastic Transitivity (SST): \mathbb{P}(a\succsim b)\geq \tfrac{1}{2} and \mathbb{P}(b\succsim c)\geq \tfrac{1}{2} implies \mathbb{P}(a\succsim c)\geq \max \{\mathbb{P}(a\succsim b),\mathbb{P}(b\succsim c)\}, for all a,b,c \in \mathcal{A};{{rp|12}}
  3. Linear Stochastic Transitivity (LST): \mathbb{P}(a\succsim b) = F(\mu(a) - \mu(b)), for all a,b \in \mathcal{A}, where F:\mathbb{R} \to [0,1] is some increasing and {{clarify span|symmetric|reason=The meaning here apparently deviates from that of the 'Symmetric function' article.|date=February 2020}} function (called a comparison function), and \mu: \mathcal{A}\to \mathbb{R} is some mapping from the set \mathcal{A} 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{P}(\text{Billy} \succsim \text{Gabriela}) of Billy winning against Gabriela is

\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 F:\mathbb{R} \to [0,1] is given by F(x) = \frac{1}{1+e^{-x

}} and the merit function \mu: \mathcal{A}\to \mathbb{R} 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.{{Cite journal|last1=Bradley|first1=Ralph Allan|last2=Terry|first2=Milton E.|date=December 1952|title=Rank Analysis of Incomplete Block Designs: I. The Method of Paired Comparisons|journal=Biometrika|volume=39|issue=3/4|pages=324|doi=10.2307/2334029|jstor=2334029}}

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 used for the Xbox gaming platform.
  • Models of Psychology and Rationality - Thurstonian models{{Cite journal|last=Thurstone|first=L. L.|date=1994|title=A law of comparative judgment.|journal=Psychological Review|volume=101|issue=2|pages=266–270|doi=10.1037/0033-295X.101.2.266|issn=0033-295X}} (see Case 5 in law of comparative judgement), Fechnerian models and also Luce's choice axiom{{Cite book|title=Individual choice behavior : a theoretical analysis|last=Luce, R. Duncan (Robert Duncan)|date=2005|publisher=Dover Publications|isbn=0486441369|location=Mineola, N.Y.|oclc=874031603}} 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.{{Cite journal|last=Debreu|first=Gerard|date=July 1958|title=Stochastic Choice and Cardinal Utility|journal=Econometrica|volume=26|issue=3|pages=440–444|doi=10.2307/1907622|issn=0012-9682|jstor=1907622|url=http://cowles.yale.edu/sites/default/files/files/pub/d00/d0039.pdf}}{{Cite journal|last1=Regenwetter|first1=Michel|last2=Dana|first2=Jason|last3=Davis-Stober|first3=Clintin P.|date=2011|title=Transitivity of preferences.|journal=Psychological Review|volume=118|issue=1|pages=42–56|doi=10.1037/a0021150|pmid=21244185|issn=1939-1471}}{{Cite journal|last1=Cavagnaro|first1=Daniel R.|last2=Davis-Stober|first2=Clintin P.|date=2014|title=Transitive in our preferences, but transitive in different ways: An analysis of choice variability.|journal=Decision|volume=1|issue=2|pages=102–122|doi=10.1037/dec0000011|issn=2325-9973}}
  • 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.{{Cite journal|last1=Shah|first1=Nihar B.|last2=Balakrishnan|first2=Sivaraman|last3=Guntuboyina|first3=Adityanand|last4=Wainwright|first4=Martin J.|date=February 2017|title=Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues|journal=IEEE Transactions on Information Theory|volume=63|issue=2|pages=934–959|doi=10.1109/tit.2016.2634418|issn=0018-9448|doi-access=free|arxiv=1510.05610}}{{Cite journal|last1=Chatterjee|first1=Sabyasachi|last2=Mukherjee|first2=Sumit|date=June 2019|title=Estimation in Tournaments and Graphs Under Monotonicity Constraints|journal=IEEE Transactions on Information Theory|volume=65|issue=6|pages=3525–3539|doi=10.1109/tit.2019.2893911|issn=0018-9448|arxiv=1603.04556|s2cid=54740089}}{{Cite journal|last1=Oliveira|first1=Ivo F.D.|last2=Ailon|first2=Nir|last3=Davidov|first3=Ori|year=2018|title=A New and Flexible Approach to the Analysis of Paired Comparison Data|url=http://www.jmlr.org/papers/v19/17-179.html|journal=Journal of Machine Learning Research|volume=19|pages=1–29}} 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.{{Cite journal|last=Israel|first=Robert B.|date=December 1981|title=Stronger Players Need not Win More Knockout Tournaments|journal=Journal of the American Statistical Association|volume=76|issue=376|pages=950–951|doi=10.2307/2287594|issn=0162-1459|jstor=2287594}}{{Cite journal|last1=Chen|first1=Robert|last2=Hwang|first2=F. K.|date=December 1988|title=Stronger players win more balanced knockout tournaments|journal=Graphs and Combinatorics|volume=4|issue=1|pages=95–99|doi=10.1007/bf01864157|s2cid=44602228|issn=0911-0119}}{{Cite journal|last1=Adler|first1=Ilan|last2=Cao|first2=Yang|last3=Karp|first3=Richard|last4=Peköz|first4=Erol A.|last5=Ross|first5=Sheldon M.|date=December 2017|title=Random Knockout Tournaments|journal=Operations Research|volume=65|issue=6|pages=1589–1596|doi=10.1287/opre.2017.1657|issn=0030-364X|arxiv=1612.04448|s2cid=1041539}} Social choice theory also has foundations that depend on stochastic transitivity models.{{Cite journal|last=Sen|first=Amartya|date=January 1977|title=Social Choice Theory: A Re-Examination|journal=Econometrica|volume=45|issue=1|pages=53–89|doi=10.2307/1913287|issn=0012-9682|jstor=1913287}}

Connections between models

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 \implies SST\impliesWST ;
  2. Since the Bradley-Terry models and Thurstone's Case V model are LST models, they also satisfy SST and WST;
  3. Due to the convenience of {{clarify span|more structured models|reason=Which of the mentioned models are meant here?|date=February 2020}}, a few authors{{Cite book|title=Stochastic utility theorem|last=Blavatskyy, Pavlo R.|date=2007|publisher=Inst. for Empirical Research in Economics|oclc=255736997}}{{Cite journal|last=Dagsvik|first=John K.|date=October 2015|title=Stochastic models for risky choices: A comparison of different axiomatizations|journal=Journal of Mathematical Economics|volume=60|pages=81–88|doi=10.1016/j.jmateco.2015.06.013|issn=0304-4068}} have identified axiomatic {{clarify span|justifications|reason=Axioms aren't intended to justify anything. Possibly, 'definition' is meant here?|date=February 2020}} of linear stochastic transitivity (and other models), most notably Gérard Debreu showed that: {{clarify span|Quadruple Condition|reason=This notion should be explained, or omitted ('... gave a sufficient condition for LST').|date=February 2020}} + {{clarify span|Continuity|reason=Ditto.|date=February 2020}} \implies LST (see also Debreu Theorems);
  4. Two LST models given by invertible comparison functions F(x) and G(x) are {{clarify span|equivalent|Give a definition, in particular, if it involves something like 'almost everywhere'.|date=February 2020}} if and only if F(x) = G(\kappa x)for some \kappa \geq 0.{{Cite journal|last=Yellott|first=John I.|date=April 1977|title=The relationship between Luce's Choice Axiom, Thurstone's Theory of Comparative Judgment, and the double exponential distribution|journal=Journal of Mathematical Psychology|volume=15|issue=2|pages=109–144|doi=10.1016/0022-2496(77)90026-8|issn=0022-2496|url=https://escholarship.org/uc/item/7z91732x}}

Negative Results:

  1. Stochastic transitivity models are empirically {{clarify span|unverifiable|reason=In which sense, and for what reason? E.g. non-stochastic transitivity can be verified if, and only if, the domain A is finite; it can be falsified for any A, given sufficient luck.|date=February 2020}}, however, they may be falsifiable;
  2. {{clarify span|Distinguishing|reason=Elaborate on the setting. What is given? What is asked for? Is there a notion of 'algorithm' (or a generalization to infinite input) involved?|date=February 2020}} 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 {{clarify span|points|reason=Are these members of A, or what else?|date=February 2020}};{{Cite journal|last1=Rockwell|first1=Christina|last2=Yellott|first2=John I.|date=February 1979|title=A note on equivalent Thurstone models|journal=Journal of Mathematical Psychology|volume=19|issue=1|pages=65–71|doi=10.1016/0022-2496(79)90006-3|issn=0022-2496|url=http://www.escholarship.org/uc/item/3c86p1kc}}
  3. The {{clarify span|estimation problem|date=February 2020}} for WST, SST and LST models are in general NP-Hard,{{Cite journal|last=deCani|first=John S.|date=December 1969|title=Maximum Likelihood Paired Comparison Ranking by Linear Programming|journal=Biometrika|volume=56|issue=3|pages=537–545|doi=10.2307/2334661|issn=0006-3444|jstor=2334661}} however, near optimal polynomially computable estimation procedures are known for SST and LST models.

See also

References

{{reflist}}

Category:Transitive relations