Стохастическая транзитивность модель [1] [2] [3] [4] являются стохастическими версиями транзитивности свойства бинарных отношений , изучаемых в математике . Существует несколько моделей стохастической транзитивности, которые использовались для описания вероятностей, участвующих в экспериментах парных сравнений., особенно в сценариях, где ожидается транзитивность, однако эмпирические наблюдения бинарного отношения являются вероятностными. Например, можно ожидать, что навыки игроков в спорте будут транзитивными, т.е. «если игрок A лучше, чем B, а B лучше, чем C, то игрок A должен быть лучше, чем C»; однако в любом конкретном матче более слабый игрок все равно может выиграть с положительной вероятностью. Точно подобранные игроки могут иметь больше шансов наблюдать эту инверсию, в то время как игроки с большими различиями в своих навыках могут видеть, что эти инверсии случаются редко. Модели стохастической транзитивности формализуют такие отношения между вероятностями (например, исхода матча) и лежащими в основе транзитивными отношениями (например, навыками игроков).
Бинарное отношение на съемочной площадке называется транзитивным в стандартном нестохастическом смысле, если а также подразумевает для всех участников из .
Стохастические версии, включающие транзитивность, включают:
- Слабая стохастическая транзитивность (WST): а также подразумевает , для всех ; [5] : 12 [6] : 43рг
- Сильная стохастическая транзитивность (SST): а также подразумевает , для всех ; [5] : 12
- Линейная стохастическая транзитивность (LST): , для всех , где - некоторая возрастающая и симметричная функция [ пояснить ] (называемая функцией сравнения ), и какое-то отображение из множества альтернатив реальной линии (называемой оценочной функцией ).
Пример игрушки
Игра в мрамор. Предположим, двое детей, Билли и Габриэла, собирают шарики. Билли коллекционирует синие шарики и зеленые шарики Габриэлы. Когда они собираются вместе, они играют в игру, в которой смешивают все свои шарики в сумке и выбирают один случайным образом. Если выбранный шарик зеленого цвета, то выигрывает Габриэла, а если он синий, то выигрывает Билли. Если количество синих шариков и количество зеленых шариков в сумке, тогда вероятность победы Билли над Габриэлой - это
.
В этом примере мраморная игра удовлетворяет линейной стохастической транзитивности, где функция сравнения дан кем-то и функция заслуг дан кем-то , где количество шариков игрока. Эта игра является примером модели Брэдли – Терри . [7]
Приложения
- Ранжирование и рейтинг. Модели стохастической транзитивности использовались в качестве основы для нескольких методов ранжирования и рейтинга. Примеры включают систему Elo-Rating, используемую в шахматах, го и других классических видах спорта, а также TrueSkill от Microsoft, используемую для игровой платформы Xbox.
- Модели психологии и рациональности - модели Терстона [8] (см. Случай 5 в законе сравнительного суждения ), фехнеровские модели [3], а также аксиома выбора Люса [9] - это теории, основанные на математике стохастической транзитивности. Кроме того, модели теории рационального выбора основаны на предположении о транзитивности предпочтений (см . Полезность фон Неймана и теоремы Дебре ), однако эти предпочтения часто обнаруживаются с шумом стохастическим образом. [10] [11] [12]
- Машинное обучение и искусственный интеллект (см. Обучение ранжированию ). Хотя Elo и TrueSkill полагаются на конкретные модели LST, модели машинного обучения были разработаны для ранжирования без предварительного знания базовой модели стохастической транзитивности или с более слабыми, чем обычно, предположениями о стохастической транзитивности. [13] [14] [15] Изучение парных сравнений также представляет интерес, поскольку позволяет агентам ИИ узнать основные предпочтения других агентов.
- Теория игр - справедливость турниров со случайным нокаутом сильно зависит от лежащей в основе модели стохастической транзитивности. [16] [17] [18] Теория социального выбора также имеет основы, которые зависят от моделей стохастической транзитивности. [19]
Связи между моделями
Положительные результаты:
- Каждая модель, удовлетворяющая линейной стохастической транзитивности, должна также удовлетворять сильной стохастической транзитивности, которая, в свою очередь, должна удовлетворять слабой стохастической транзитивности. Это представлено как: LST SSTWST ;
- Поскольку модели Брэдли-Терри и модель Турстана 5 [ пояснить ] являются моделями LST , они также удовлетворяют требованиям SST и WST ;
- Из-за удобства более структурированных моделей [ пояснить ] , несколько авторов [1] [2] [3] [4] [20] [21] определили аксиоматические обоснования [ уточните ] линейной стохастической транзитивности (и других моделей), в частности, Жерар Дебро показал, что: [22] Четверное условие [ прояснить ] + Непрерывность [ прояснить ] LST (см. Также теоремы Дебре );
- Две модели LST, заданные обратимыми функциями сравнения а также которые эквивалентны [ уточнить ] , если и только еслидля некоторых [23]
Отрицательные результаты:
- Стохастические модели транзитивности эмпирический непроверяемые [ уточнить ] , [4] , однако, они могут быть опровергнуты;
- Различие [ уточнить ] между функциями сравнения LST а также может быть невозможно, даже если бесконечное количество данных предоставляется по конечному числу точек [ пояснить ] ; [24]
- Проблема оценивания [ поясните ] для моделей WST , SST и LST в целом является NP-сложной , [25] однако, для моделей SST и LST известны почти оптимальные полиномиально вычислимые процедуры оценивания . [13] [14] [15]
Смотрите также
- Нетранзитивная игра
- Теория принятия решений
- Утилитаризм
Рекомендации
- ^ a b Фишберн, Питер С. (ноябрь 1973 г.). «Вероятности двоичного выбора: о разновидностях стохастической транзитивности». Журнал математической психологии . 10 (4): 327–352. DOI : 10.1016 / 0022-2496 (73) 90021-7 . ISSN 0022-2496 .
- ^ а б Кларк, Стивен А. (март 1990 г.). «Концепция стохастической транзитивности для случайной полезной модели». Журнал математической психологии . 34 (1): 95–108. DOI : 10.1016 / 0022-2496 (90) 90015-2 .
- ^ а б в Райан, Мэтью (21 января 2017 г.). «Неопределенность и бинарный стохастический выбор». Экономическая теория . 65 (3): 629–662. DOI : 10.1007 / s00199-017-1033-4 . ISSN 0938-2259 . S2CID 125420775 .
- ^ а б в Оливейра, IFD; Zehavi, S .; Давыдов, О. (август 2018). «Стохастическая транзитивность: аксиомы и модели». Журнал математической психологии . 85 : 25–35. DOI : 10.1016 / j.jmp.2018.06.002 . ISSN 0022-2496 .
- ^ а б Дональд Дэвидсон и Джейкоб Маршак (июль 1958 г.). Экспериментальные испытания теории стохастических решений (PDF) (Технический отчет). Стэндфордский Университет.
- ^ Мишель Регенветтер, Джейсон Дана и Клинтин П. Дэвис-Стобер (2011). «Транзитивность предпочтений» (PDF) . Психологический обзор . 118 (1): 42–56. DOI : 10.1037 / a0021150 . PMID 21244185 .
- ^ Брэдли, Ральф Аллан; Терри, Милтон Э. (декабрь 1952 г.). «Ранговый анализ неполных блочных конструкций: I. Метод парных сравнений». Биометрика . 39 (3/4): 324. DOI : 10,2307 / 2334029 . JSTOR 2334029 .
- ^ Терстон, LL (1994). «Закон сравнительного суждения». Психологический обзор . 101 (2): 266–270. DOI : 10.1037 / 0033-295X.101.2.266 . ISSN 0033-295X .
- ^ Люс, Р. Дункан (Роберт Дункан) (2005). Индивидуальный выбор поведения: теоретический анализ . Минеола, Нью-Йорк: Dover Publications. ISBN 0486441369. OCLC 874031603 .
- ^ Дебре, Жерар (июль 1958). «Стохастический выбор и кардинальная полезность» (PDF) . Econometrica . 26 (3): 440–444. DOI : 10.2307 / 1907622 . ISSN 0012-9682 . JSTOR 1907622 .
- ^ Регенветтер, Мишель; Дана, Джейсон; Дэвис-Стобер, Клинтин П. (2011). «Транзитивность предпочтений». Психологический обзор . 118 (1): 42–56. DOI : 10.1037 / a0021150 . ISSN 1939-1471 . PMID 21244185 .
- ^ Cavagnaro, Daniel R .; Дэвис-Стобер, Клинтин П. (2014). «Переходный в наших предпочтениях, но переходный по-разному: анализ изменчивости выбора». Решение . 1 (2): 102–122. DOI : 10.1037 / dec0000011 . ISSN 2325-9973 .
- ^ а б Shah, Nihar B .; Балакришнан, Шивараман; Гунтубойина, Адитьянанд; Уэйнрайт, Мартин Дж. (Февраль 2017 г.). «Стохастически транзитивные модели для парных сравнений: статистические и вычислительные вопросы» . IEEE Transactions по теории информации . 63 (2): 934–959. DOI : 10,1109 / tit.2016.2634418 . ISSN 0018-9448 .
- ^ а б Чаттерджи, Сабьясачи; Мукерджи, Сумит (июнь 2019 г.). «Оценка в турнирах и графики в условиях монотонности». IEEE Transactions по теории информации . 65 (6): 3525–3539. arXiv : 1603.04556 . DOI : 10,1109 / tit.2019.2893911 . ISSN 0018-9448 . S2CID 54740089 .
- ^ а б Oliveira, Ivo FD; Айлон, Нир; Давыдов, Ори (2018). «Новый и гибкий подход к анализу парных сравнительных данных» . Журнал исследований в области машинного обучения . 19 : 1–29.
- ^ Израиль, Роберт Б. (декабрь 1981 г.). «Более сильным игрокам не нужно побеждать в большем количестве турниров на выбывание». Журнал Американской статистической ассоциации . 76 (376): 950–951. DOI : 10.2307 / 2287594 . ISSN 0162-1459 . JSTOR 2287594 .
- ^ Чен, Роберт; Hwang, FK (декабрь 1988 г.). «Более сильные игроки выигрывают более сбалансированные турниры на выбывание». Графы и комбинаторика . 4 (1): 95–99. DOI : 10.1007 / bf01864157 . ISSN 0911-0119 . S2CID 44602228 .
- ^ Адлер, Илан; Цао, Ян; Карп, Ричард; Peköz, Erol A .; Росс, Шелдон М. (декабрь 2017 г.). «Случайные турниры на выбывание». Исследование операций . 65 (6): 1589–1596. arXiv : 1612.04448 . DOI : 10.1287 / opre.2017.1657 . ISSN 0030-364X . S2CID 1041539 .
- ^ Сен, Амартия (январь 1977 г.). «Теория социального выбора: переосмысление». Econometrica . 45 (1): 53–89. DOI : 10.2307 / 1913287 . ISSN 0012-9682 . JSTOR 1913287 .
- ^ Блаватский, Павел Р. (2007). Теорема о стохастической полезности . Inst. для эмпирических исследований в области экономики. OCLC 255736997 .
- ^ Дагсвик, Джон К. (октябрь 2015 г.). «Стохастические модели для рискованного выбора: сравнение различных аксиоматизаций». Журнал математической экономики . 60 : 81–88. DOI : 10.1016 / j.jmateco.2015.06.013 . ISSN 0304-4068 .
- ^ Дебре, Жерар (июль 1958). «Стохастический выбор и кардинальная полезность» (PDF) . Econometrica . 26 (3): 440–444. DOI : 10.2307 / 1907622 . ISSN 0012-9682 . JSTOR 1907622 .
- ^ Йеллотт, Джон И. (апрель 1977 г.). «Связь между Аксиомой выбора Люси, Теорией сравнительного суждения Терстона и двойным экспоненциальным распределением» . Журнал математической психологии . 15 (2): 109–144. DOI : 10.1016 / 0022-2496 (77) 90026-8 . ISSN 0022-2496 .
- ^ Рокуэлл, Кристина; Йеллотт, Джон И. (февраль 1979 г.). «Примечание об эквивалентных моделях Thurstone» . Журнал математической психологии . 19 (1): 65–71. DOI : 10.1016 / 0022-2496 (79) 90006-3 . ISSN 0022-2496 .
- ^ деКани, Джон С. (декабрь 1969 г.). «Максимальное правдоподобие парных сравнений по линейному программированию». Биометрика . 56 (3): 537–545. DOI : 10.2307 / 2334661 . ISSN 0006-3444 . JSTOR 2334661 .