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

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

Рынок жилья

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

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

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

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

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

Агент:123456
1-й выбор:333212
2-й выбор:251534
3-й выбор:46. . .625
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 обмениваются своими домами. Агентов больше не осталось, поэтому игра окончена. Окончательное распределение:

Агент:123456
Дом:253614

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

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

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

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

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

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

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

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

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

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

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

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

Конкретное правило выбора, которое удовлетворяет этим условиям, — правило Highest Priority Object (HPO). Оно предполагает предопределенный приоритетный порядок домов. Оно работает следующим образом. [9]

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

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

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

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

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

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

3. Настройки обмена почками : Top Trading Cycles and Chains (TTCC). [14]

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

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

Смотрите также

Ссылки

  1. ^ Шепли, Ллойд; Скарф, Герберт (1974). «О ядрах и неделимости». Журнал математической экономики . 1 : 23–37. doi :10.1016/0304-4068(74)90033-0. S2CID  154744803.
  2. ^ ab Herve Moulin (2004). Справедливое разделение и коллективное благосостояние . Кембридж, Массачусетс: MIT Press. ISBN 9780262134231.
  3. ^ Рот, Элвин Э. (1982-01-01). «Совместимость стимулов на рынке с неделимыми товарами». Economics Letters . 9 (2): 127–132. doi :10.1016/0165-1765(82)90003-9. ISSN  0165-1765.
  4. ^ Ма, Цзиньпэн (1994-03-01). «Стратегическая устойчивость и строгое ядро ​​на рынке с неделимостью». Международный журнал теории игр . 23 (1): 75–83. doi :10.1007/BF01242849. ISSN  1432-1270. S2CID  36253188.
  5. ^ Анно, Хидеказу (2015-01-01). «Краткое доказательство для характеристики ядра на рынках жилья». Economics Letters . 126 : 66–67. doi :10.1016/j.econlet.2014.11.019. ISSN  0165-1765.
  6. ^ Алькальде-Унзу, Хорхе; Молис, Елена (01.09.2011). «Обмен неделимыми товарами и безразличиями: основные механизмы торговых поглощающих множеств». Игры и экономическое поведение . 73 (1): 1–16. doi : 10.1016/j.geb.2010.12.005. hdl : 2454/18593 . ISSN  0899-8256.
  7. ^ Джарамилло, Паула; Манджунат, Викрам (01.09.2012). «Разница, которую безразличие вносит в распределение объектов, защищенное от стратегий». Журнал экономической теории . 147 (5): 1913–1946. doi :10.1016/j.jet.2012.05.017. ISSN  0022-0531.
  8. ^ Азиз, Харис; Кейзер, Барт де (2012). «Рынки жилья с безразличием: история двух механизмов». Труды конференции AAAI по искусственному интеллекту . 26 (1): 1249–1255. doi : 10.1609/aaai.v26i1.8239 . ISSN  2374-3468. S2CID  15395473.
  9. ^ abc Saban, Daniela; Sethuraman, Jay (2013-06-16). «Распределение домов с учетом безразличия». Труды четырнадцатой конференции ACM по электронной коммерции . EC '13. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 803–820. doi :10.1145/2492002.2482574. ISBN 978-1-4503-1962-1.
  10. ^ Неизвестно [ постоянная мертвая ссылка ]
  11. ^ Абдулкадироглу, Атила; Сёнмез, Тайфун (1999). «Распределение домов с существующими арендаторами». Журнал экономической теории . 88 (2): 233–260. doi : 10.1006/jeth.1999.2553 .. См. также презентацию Катарины Шаар.
  12. ^ Абдулкадироглу, Атила; Сёнмез, Тайфун (2003). «Выбор школы: подход к разработке механизма» (PDF) . Американский экономический обзор . 93 (3): 729–747. дои : 10.1257/000282803322157061. HDL : 10161/2090 . S2CID  15609227.
  13. ^ Vanacore, Andres (16 апреля 2012 г.). «Централизованная регистрация в Recovery School District получает первую пробу». The Times-Picayune . Новый Орлеан . Получено 4 апреля 2016 г.
  14. ^ Рот, Элвин; Сёнмез, Тайфун; Унвер, М. Утку (2004). «Обмен почками». Quarterly Journal of Economics . 119 (2): 457–488. doi :10.1162/0033553041382157.
  15. ^ Кляйн, Т. (2015). "Анализ стабильных соответствий в R: пакет сопоставления рынков" (PDF) . Виньетка к пакету R MatchingMarkets .
  16. ^ "matchingMarkets: Анализ стабильных соответствий". Проект R. 12 января 2020 г.
  17. ^ «API MatchingTools».
Взято с "https://en.wikipedia.org/w/index.php?title=Лучший_торговый_цикл&oldid=1238398463"