Лучший торговый цикл

Топовый торговый цикл (ТТС) — это алгоритм торговли неделимыми предметами без использования денег. Он был разработан Дэвидом Гейлом и опубликован Гербертом Скарфом и Ллойдом Шепли . ^[1]^: 30–31

Рынок жилья

Базовый алгоритм TTC иллюстрируется следующей задачей распределения домов . Есть $n$ студенты, проживающие в студенческих общежитиях. Каждый студент живет в отдельном доме. Каждый студент имеет отношение предпочтений к домам, а некоторые студенты предпочитают дома, закрепленные за другими студентами. Это может привести к взаимовыгодному обмену. Например, если студент 1 предпочитает дом, выделенный студенту 2, и наоборот, они оба выиграют от обмена своими домами. Цель состоит в том, чтобы найти стабильное распределение – перераспределение домов между студентами таким образом, чтобы были реализованы все взаимовыгодные обмены (т. е. ни одна группа студентов не может вместе улучшить свое положение путем обмена домами).

Алгоритм работает следующим образом.

Попросите каждого агента указать свой «верхний» (самый предпочтительный) дом.
Нарисуйте стрелку от каждого агента $i$ агенту, обозначенному $\operatorname {Top} (i)$ , который держит верхнюю палату $i$ .
Обратите внимание, что в графе должен быть хотя бы один цикл (это может быть цикл длины 1, если какой-то агент $i$ в настоящее время владеет собственным высшим домом). Осуществите сделку, указанную в этом цикле (т. е. перераспределите каждый дом агенту, указывающему на него), и удалите всех задействованных агентов из графа.
Если агенты остались, вернитесь к шагу 1.

Алгоритм должен завершиться, так как на каждой итерации мы удаляем хотя бы одного агента. Можно доказать, что этот алгоритм приводит к устойчивому к ядру распределению.

Например, ^[2]^{: 223–224} предположим, что порядок предпочтений агентов следующий (где актуальны только не более 4 лучших вариантов):

Агент:	1	2	3	4	5	6
1-й выбор:	3	3	3	2	1	2
2-й выбор:	2	5	1	5	3	4
3-й выбор:	4	6	. . .	6	2	5
4-й выбор:	1	. . .	. . .	4	. . .	6
. . .	. . .	. . .	. . .	. . .	. . .	. . .

В первой итерации единственным торговым циклом с наибольшим успехом является {3} (это цикл длиной 1), поэтому агент 3 сохраняет свой текущий дом и уходит с рынка.

Во второй итерации верхний дом агента 1 равен 2 (поскольку дом 3 недоступен). Аналогично, верхний дом агента 2 равен 5, а верхний дом агента 5 равен 1. Следовательно, {1,2,5} — это лучший торговый цикл. Он реализуется: агент 1 получает дом 2, агент 2 получает дом 5 и агент 5 получает дом 1. Эти три агента уходят с рынка.

В третьей итерации верхний торговый цикл равен {4,6}, поэтому агенты 4 и 6 обмениваются домами. Агентов больше не осталось, поэтому игра окончена. Окончательное распределение таково:

Агент:	1	2	3	4	5	6
Дом:	2	5	3	6	1	4

Такое распределение является стабильным для ядра, поскольку ни одна коалиция не может улучшить свое положение путем взаимного обмена.

Тот же алгоритм можно использовать и в других ситуациях, например: ^[2] предположим, что в ночные смены назначены 7 врачей; каждый врач закреплен за ночной сменой в один день недели. Некоторые врачи предпочитают смены, предоставленные другим врачам. Здесь можно использовать алгоритм ТТС для достижения максимального взаимовыгодного обмена.

Характеристики

ТТС – это правдивый механизм . Это доказал Элвин Рот . ^[3]

Когда предпочтения строгие (нет безразличия), TTC всегда находит строго эффективное по Парето распределение. Более того, он всегда находит стабильное для ядра распределение. Более того, при строгих предпочтениях существует уникальное стабильное распределение, и именно оно найдено TTC.

В области строгих предпочтений TTC является единственным механизмом, который удовлетворяет критериям индивидуальной рациональности, эффективности по Парето и устойчивости стратегии. ^[4]^[5]

Предпочтения с безразличием

Исходный алгоритм TTC предполагал, что предпочтения строгие, так что у каждого агента всегда есть одна верхняя палата. В реалистичных условиях агентам может быть безразлично, какой дом находится, и у агента может быть две или более верхних палаты. Для этой настройки было предложено несколько различных алгоритмов. ^[6]^[7] Позже они были обобщены несколькими способами. ^[8]^[9]^[10] Общая схема следующая.

Попросите каждого агента указать все свои лучшие дома.
Постройте TTC-граф G : ориентированный граф, в котором каждый агент указывает на всех агентов, владеющих его верхними домами.
Повторить:
- Проанализируйте связные компоненты G . сильно
- Определите стоки — компоненты, у которых нет выходящих ребер (есть хотя бы одно).
- Определите терминальные приемники — приемники, в которых каждый агент владеет одним из своих лучших вариантов.
  - Если оконечных стоков нет — ломаем и переходим к шагу 4.
  - В противном случае для каждого терминального приемника S : навсегда назначьте каждого агента в S его текущему дому, удалите его с рынка, обновите график TTC и вернитесь к шагу 3.
Выберите набор непересекающихся торговых циклов, используя заранее определенное правило выбора. Осуществите торговлю, указанную этими циклами, и удалите их с рынка.
Если агенты остались, вернитесь к шагу 1.

Механизмы различаются правилом отбора, используемым на шаге 4. Правило отбора должно удовлетворять нескольким условиям: ^[9]

Уникальность: правило выбирает для каждого агента уникальный дом из числа его лучших домов.
Завершение: алгоритм, использующий правило, гарантированно завершится.
Персистентность: в сокращенном графе, полученном по правилу, каждый направленный путь, заканчивающийся у неудовлетворенного агента i (агента, не владеющего верхней палатой), является постоянным - путь остается в графе до тех пор, пока агент i не покинет рынок или не продаст свой дом. .
Независимость неудовлетворенных агентов: если агент i неудовлетворен, а два графа TTC отличаются только ребрами, исходящими из i , то приведенные графы TTC отличаются только ребром, исходящим из i .

Если правило отбора удовлетворяет критериям уникальности и прекращения, результирующий механизм дает распределение, эффективное по Парето и находящееся в слабом ядре (ни одно подмножество агентов не может получить для всех строго лучший дом путем торговли между собой). Слабое ядро также подразумевает, что оно индивидуально-рационально. Если, кроме того, правило отбора удовлетворяет постоянству, независимости неудовлетворенных агентов и некоторым другим техническим условиям, полученный механизм является нестратегичным .

Конкретным правилом выбора, которое удовлетворяет этим условиям, является правило объекта с наивысшим приоритетом (HPO). Он предполагает заранее определённую очередность расположения домов. Это работает следующим образом. ^[9]

(а) Каждый неудовлетворенный агент указывает на владельца дома с наивысшим приоритетом среди его лучших домов. Все неудовлетворенные агенты помечаются.
(б) Среди немаркированных агентов рассмотрим тех, у которых верхняя палата принадлежит маркированному агенту. Среди них выберите агента i, владеющего домом с наивысшим приоритетом. Пусть я укажу на дом с наивысшим приоритетом, принадлежащий отмеченному агенту. Агент этикетки i .
(c) Если есть немаркированные агенты, вернитесь к пункту (b).

Когда действие правила прекращается, все агенты помечаются, и каждый помеченный агент имеет уникальное исходящее ребро. Правило гарантирует, что на каждой итерации во всех циклах будет хотя бы один неудовлетворенный агент. Таким образом, на каждой итерации удовлетворяется хотя бы один новый агент. Следовательно, алгоритм завершается не более чем через n итераций. Время выполнения каждой итерации равно $O(n\log {n}+n\gamma )$ , где $\gamma$ — максимальный размер класса безразличия. Таким образом, общее время работы равно $O(n^{2}\log {n}+n^{2}\gamma )$ .

Другие расширения

Алгоритм TTC был расширен различными способами.

1. Условия, в которых помимо студентов, уже проживающих в домах, есть также новые студенты без дома и пустующие дома без студента. ^[11]

2. Установка выбора школы . ^[12] Школьный округ Нового Орлеана по восстановлению принял версию TTC по выбору школы в 2012 году. ^[13]

3. Настройка обмена почек : основные торговые циклы и цепочки (TTCC). ^[14]

Реализация в программных пакетах

Р : Алгоритм Top-Trading-Cycles для задачи рынка жилья реализован как часть matchingMarkets упаковка. ^[15]^[16]
API : API MatchingTools предоставляет бесплатный интерфейс прикладного программирования для алгоритма Top-Trading-Cycles. ^[17]

См. также

Ссылки

^ Шепли, Ллойд; Шарф, Герберт (1974). «О ядрах и неделимости». Журнал математической экономики . 1 : 23–37. дои : 10.1016/0304-4068(74)90033-0 . S2CID 154744803 .
^ Перейти обратно: ^а ^б Эрве Мулен (2004). Справедливое разделение и коллективное благосостояние . Кембридж, Массачусетс: MIT Press. ISBN 9780262134231 .
^ Рот, Элвин Э. (1 января 1982 г.). «Стимулирующая совместимость на рынке неделимых товаров». Письма по экономике . 9 (2): 127–132. дои : 10.1016/0165-1765(82)90003-9 . ISSN 0165-1765 .
^ Ма, Цзиньпэн (1 марта 1994 г.). «Стратегическая устойчивость и строгое ядро неделимого рынка» . Международный журнал теории игр . 23 (1): 75–83. дои : 10.1007/BF01242849 . ISSN 1432-1270 . S2CID 36253188 .
^ Анно, Хидекадзу (01 января 2015 г.). «Краткое доказательство характеристики ядра рынков жилья» . Письма по экономике . 126 : 66–67. дои : 10.1016/j.econlet.2014.11.019 . ISSN 0165-1765 .
^ Алькальде-Унзу, Хорхе; Молис, Елена (01 сентября 2011 г.). «Обмен неделимыми благами и безразличиями: механизмы верхних торговых поглощающих множеств» . Игры и экономическое поведение . 73 (1): 1–16. дои : 10.1016/j.geb.2010.12.005 . hdl : 2454/18593 . ISSN 0899-8256 .
^ Харамильо, Паула; Манджунатх, Викрам (1 сентября 2012 г.). «Разница, которую безразличие вносит в стратегическое распределение объектов» . Журнал экономической теории . 147 (5): 1913–1946. дои : 10.1016/j.jet.2012.05.017 . ISSN 0022-0531 .
^ Азиз, Харис; Кейзер, Барт де (2012). «Рынки жилья с безразличием: история двух механизмов» . Материалы конференции AAAI по искусственному интеллекту . 26 (1): 1249–1255. дои : 10.1609/aaai.v26i1.8239 . ISSN 2374-3468 . S2CID 15395473 .
^ Перейти обратно: ^а ^б ^с Сабан, Даниэла; Сетураман, Джей (16 июня 2013 г.). «Распределение домов с безразличием» . Материалы четырнадцатой конференции ACM по электронной коммерции . ЭК '13. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 803–820. дои : 10.1145/2492002.2482574 . ISBN 978-1-4503-1962-1 .
^ Неизвестно ^{[ постоянная мертвая ссылка ]}
^ Абдулкадироглу, Атила; Сёнмез, Тайфун (1999). «Распределение дома с существующими арендаторами» . Журнал экономической теории . 88 (2): 233–260. дои : 10.1006/jeth.1999.2553 . . См. также презентацию Катарины Шаар .
^ Абдулкадироглу, Атила; Сёнмез, Тайфун (2003). «Выбор школы: подход к разработке механизма» (PDF) . Американский экономический обзор . 93 (3): 729–747. дои : 10.1257/000282803322157061 . HDL : 10161/2090 . S2CID 15609227 .
^ Ванакор, Андрес (16 апреля 2012 г.). «Централизованное зачисление в Школьный округ Восстановления проходит первую проверку» . «Таймс-Пикаюн» . Новый Орлеан . Проверено 4 апреля 2016 г.
^ Рот, Элвин; Сёнмез, Тайфун; Унвер, М. Утку (2004). «Обмен почек» . Ежеквартальный экономический журнал . 119 (2): 457–488. дои : 10.1162/0033553041382157 .
^ Кляйн, Т. (2015). «Анализ стабильных сопоставлений в R: рынки сопоставления пакетов» (PDF) . Виньетка для пакета R MatchingMarkets .
^ «matchingMarkets: анализ стабильных совпадений» . Р-проект . 12 января 2020 г.
^ «API MatchingTools» .

[ShapleyScarf-1] Шепли, Ллойд; Шарф, Герберт (1974). «О ядрах и неделимости». Журнал математической экономики . 1 : 23–37. дои : 10.1016/0304-4068(74)90033-0 . S2CID 154744803 .

[Moulin-2] Перейти обратно: ^а ^б Эрве Мулен (2004). Справедливое разделение и коллективное благосостояние . Кембридж, Массачусетс: MIT Press. ISBN 9780262134231 .

[3] Рот, Элвин Э. (1 января 1982 г.). «Стимулирующая совместимость на рынке неделимых товаров». Письма по экономике . 9 (2): 127–132. дои : 10.1016/0165-1765(82)90003-9 . ISSN 0165-1765 .

[4] Ма, Цзиньпэн (1 марта 1994 г.). «Стратегическая устойчивость и строгое ядро неделимого рынка» . Международный журнал теории игр . 23 (1): 75–83. дои : 10.1007/BF01242849 . ISSN 1432-1270 . S2CID 36253188 .

[5] Анно, Хидекадзу (01 января 2015 г.). «Краткое доказательство характеристики ядра рынков жилья» . Письма по экономике . 126 : 66–67. дои : 10.1016/j.econlet.2014.11.019 . ISSN 0165-1765 .

[6] Алькальде-Унзу, Хорхе; Молис, Елена (01 сентября 2011 г.). «Обмен неделимыми благами и безразличиями: механизмы верхних торговых поглощающих множеств» . Игры и экономическое поведение . 73 (1): 1–16. дои : 10.1016/j.geb.2010.12.005 . hdl : 2454/18593 . ISSN 0899-8256 .

[7] Харамильо, Паула; Манджунатх, Викрам (1 сентября 2012 г.). «Разница, которую безразличие вносит в стратегическое распределение объектов» . Журнал экономической теории . 147 (5): 1913–1946. дои : 10.1016/j.jet.2012.05.017 . ISSN 0022-0531 .

[8] Азиз, Харис; Кейзер, Барт де (2012). «Рынки жилья с безразличием: история двух механизмов» . Материалы конференции AAAI по искусственному интеллекту . 26 (1): 1249–1255. дои : 10.1609/aaai.v26i1.8239 . ISSN 2374-3468 . S2CID 15395473 .

[:0-9] Перейти обратно: ^а ^б ^с Сабан, Даниэла; Сетураман, Джей (16 июня 2013 г.). «Распределение домов с безразличием» . Материалы четырнадцатой конференции ACM по электронной коммерции . ЭК '13. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 803–820. дои : 10.1145/2492002.2482574 . ISBN 978-1-4503-1962-1 .

[10] Неизвестно ^{[ постоянная мертвая ссылка ]}

[AbdSonmez-11] Абдулкадироглу, Атила; Сёнмез, Тайфун (1999). «Распределение дома с существующими арендаторами» . Журнал экономической теории . 88 (2): 233–260. дои : 10.1006/jeth.1999.2553 . . См. также презентацию Катарины Шаар .

[AbdSonmez2003-12] Абдулкадироглу, Атила; Сёнмез, Тайфун (2003). «Выбор школы: подход к разработке механизма» (PDF) . Американский экономический обзор . 93 (3): 729–747. дои : 10.1257/000282803322157061 . HDL : 10161/2090 . S2CID 15609227 .

[NewOrleansTTC-13] Ванакор, Андрес (16 апреля 2012 г.). «Централизованное зачисление в Школьный округ Восстановления проходит первую проверку» . «Таймс-Пикаюн» . Новый Орлеан . Проверено 4 апреля 2016 г.

[RSU-14] Рот, Элвин; Сёнмез, Тайфун; Унвер, М. Утку (2004). «Обмен почек» . Ежеквартальный экономический журнал . 119 (2): 457–488. дои : 10.1162/0033553041382157 .

[15] Кляйн, Т. (2015). «Анализ стабильных сопоставлений в R: рынки сопоставления пакетов» (PDF) . Виньетка для пакета R MatchingMarkets .

[16] «matchingMarkets: анализ стабильных совпадений» . Р-проект . 12 января 2020 г.

[17] «API MatchingTools» .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]