Stochastic transitivity

Last updated

Stochastic transitivity models [1] [2] [3] [4] 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).

Contents

A binary relation on a set is called transitive, in the standard non-stochastic sense, if and implies for all members of .

Stochastic versions of transitivity include:

  1. Weak Stochastic Transitivity (WST): and implies , for all ; [5] :12 [6] :43rg
  2. Strong Stochastic Transitivity (SST): and implies , for all ; [5] :12
  3. Linear Stochastic Transitivity (LST):, for all , where is some increasing and symmetric[ clarify ] function (called a comparison function), and is some mapping from the set 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 is the number of blue marbles and is the number of green marbles in the bag, then the probability of Billy winning against Gabriela is

.

In this example, the marble game satisfies linear stochastic transitivity, where the comparison function is given by and the merit function is given by , where is the number of marbles of the player. This game happens to be an example of a Bradley–Terry model. [7]

Applications

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 SSTWST ;
  2. Since the Bradley-Terry models and Thurstone's Case V model [8] are LST models, they also satisfy SST and WST;
  3. Due to the convenience of more structured models[ clarify ], a few authors [1] [2] [3] [4] [20] [21] have identified axiomatic justifications[ clarify ] of linear stochastic transitivity (and other models), most notably Gérard Debreu showed that: [10] Quadruple Condition[ clarify ] + Continuity[ clarify ] LST (see also Debreu Theorems);
  4. Two LST models given by invertible comparison functions and are equivalent[ clarify ] if and only if for some [22]

Negative Results:

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

See also

References

  1. 1 2 Fishburn, Peter C. (November 1973). "Binary choice probabilities: on the varieties of stochastic transitivity". Journal of Mathematical Psychology. 10 (4): 327–352. doi:10.1016/0022-2496(73)90021-7. ISSN   0022-2496.
  2. 1 2 Clark, Stephen A. (March 1990). "A concept of stochastic transitivity for the random utility model". Journal of Mathematical Psychology. 34 (1): 95–108. doi:10.1016/0022-2496(90)90015-2.
  3. 1 2 3 Ryan, Matthew (2017-01-21). "Uncertainty and binary stochastic choice". Economic Theory. 65 (3): 629–662. doi:10.1007/s00199-017-1033-4. ISSN   0938-2259. S2CID   125420775.
  4. 1 2 3 Oliveira, I.F.D.; Zehavi, S.; Davidov, O. (August 2018). "Stochastic transitivity: Axioms and models". Journal of Mathematical Psychology. 85: 25–35. doi:10.1016/j.jmp.2018.06.002. ISSN   0022-2496.
  5. 1 2 Donald Davidson and Jacob Marschak (Jul 1958). Experimental tests of a stochastic decision theory (PDF) (Technical Report). Stanford University.
  6. Michel Regenwetter and Jason Dana and Clintin P. Davis-Stober (2011). "Transitivity of Preferences" (PDF). Psychological Review. 118 (1): 42–56. doi:10.1037/a0021150. PMID   21244185.
  7. Bradley, Ralph Allan; Terry, Milton E. (December 1952). "Rank Analysis of Incomplete Block Designs: I. The Method of Paired Comparisons". Biometrika. 39 (3/4): 324. doi:10.2307/2334029. JSTOR   2334029.
  8. 1 2 Thurstone, L. L. (1994). "A law of comparative judgment". Psychological Review. 101 (2): 266–270. doi:10.1037/0033-295X.101.2.266. ISSN   0033-295X.
  9. Luce, R. Duncan (Robert Duncan) (2005). Individual choice behavior : a theoretical analysis. Mineola, N.Y.: Dover Publications. ISBN   0486441369. OCLC   874031603.
  10. 1 2 Debreu, Gerard (July 1958). "Stochastic Choice and Cardinal Utility" (PDF). Econometrica. 26 (3): 440–444. doi:10.2307/1907622. ISSN   0012-9682. JSTOR   1907622.
  11. Regenwetter, Michel; Dana, Jason; Davis-Stober, Clintin P. (2011). "Transitivity of preferences". Psychological Review. 118 (1): 42–56. doi:10.1037/a0021150. ISSN   1939-1471. PMID   21244185.
  12. Cavagnaro, Daniel R.; Davis-Stober, Clintin P. (2014). "Transitive in our preferences, but transitive in different ways: An analysis of choice variability". Decision. 1 (2): 102–122. doi:10.1037/dec0000011. ISSN   2325-9973.
  13. 1 2 Shah, Nihar B.; Balakrishnan, Sivaraman; Guntuboyina, Adityanand; Wainwright, Martin J. (February 2017). "Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues". IEEE Transactions on Information Theory. 63 (2): 934–959. arXiv: 1510.05610 . doi: 10.1109/tit.2016.2634418 . ISSN   0018-9448.
  14. 1 2 Chatterjee, Sabyasachi; Mukherjee, Sumit (June 2019). "Estimation in Tournaments and Graphs Under Monotonicity Constraints". IEEE Transactions on Information Theory. 65 (6): 3525–3539. arXiv: 1603.04556 . doi:10.1109/tit.2019.2893911. ISSN   0018-9448. S2CID   54740089.
  15. 1 2 Oliveira, Ivo F.D.; Ailon, Nir; Davidov, Ori (2018). "A New and Flexible Approach to the Analysis of Paired Comparison Data". Journal of Machine Learning Research. 19: 1–29.
  16. Israel, Robert B. (December 1981). "Stronger Players Need not Win More Knockout Tournaments". Journal of the American Statistical Association. 76 (376): 950–951. doi:10.2307/2287594. ISSN   0162-1459. JSTOR   2287594.
  17. Chen, Robert; Hwang, F. K. (December 1988). "Stronger players win more balanced knockout tournaments". Graphs and Combinatorics. 4 (1): 95–99. doi:10.1007/bf01864157. ISSN   0911-0119. S2CID   44602228.
  18. Adler, Ilan; Cao, Yang; Karp, Richard; Peköz, Erol A.; Ross, Sheldon M. (December 2017). "Random Knockout Tournaments". Operations Research. 65 (6): 1589–1596. arXiv: 1612.04448 . doi:10.1287/opre.2017.1657. ISSN   0030-364X. S2CID   1041539.
  19. Sen, Amartya (January 1977). "Social Choice Theory: A Re-Examination". Econometrica. 45 (1): 53–89. doi:10.2307/1913287. ISSN   0012-9682. JSTOR   1913287.
  20. Blavatskyy, Pavlo R. (2007). Stochastic utility theorem. Inst. for Empirical Research in Economics. OCLC   255736997.
  21. Dagsvik, John K. (October 2015). "Stochastic models for risky choices: A comparison of different axiomatizations". Journal of Mathematical Economics. 60: 81–88. doi:10.1016/j.jmateco.2015.06.013. ISSN   0304-4068.
  22. Yellott, John I. (April 1977). "The relationship between Luce's Choice Axiom, Thurstone's Theory of Comparative Judgment, and the double exponential distribution". Journal of Mathematical Psychology. 15 (2): 109–144. doi:10.1016/0022-2496(77)90026-8. ISSN   0022-2496.
  23. Rockwell, Christina; Yellott, John I. (February 1979). "A note on equivalent Thurstone models". Journal of Mathematical Psychology. 19 (1): 65–71. doi:10.1016/0022-2496(79)90006-3. ISSN   0022-2496.
  24. deCani, John S. (December 1969). "Maximum Likelihood Paired Comparison Ranking by Linear Programming". Biometrika. 56 (3): 537–545. doi:10.2307/2334661. ISSN   0006-3444. JSTOR   2334661.