Skip to content
Назад к результатам поиска

Алгоритм Топ-Трейдинг Циклов

Автор метода
Lloyd Shapley, Herbert Scarf
Год
1974
Тип
algorithm
Семейство
Game-theoretic

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

Алгоритм Топ-Трейдинг Циклов (TTC) — это алгоритм распределения неделимых благ между агентами, при котором распределение является Парето-эффективным и индивидуально рациональным.

Разработанный Ллойдом Шепли и Гербертом Скарфом в 1974 году, алгоритм идентифицирует циклы сделок в ориентированном графе предпочтений, выполняет эти сделки и итеративно повторяет процесс до тех пор, пока дальнейшие сделки не станут невыгодными. TTC широко используется в обмене почками и распределении жилья благодаря своей эффективности и простоте реализации.

Интуиция метода

Представьте группу людей, каждый из которых владеет одним домом, и каждый человек ранжирует все дома по предпочтению. Алгоритм TTC спрашивает: кто мой фаворит? Укажите на него. Теперь посмотрите, кто указал на вас. Если это цикл (A указывает на B, B указывает на C, C указывает на A), выполните эти сделки — A получает дом B, B получает дом C, C получает дом A. Каждый в цикле доволен, потому что получил чей-то дом, который он предпочитает своему текущему. Удалите цикл и повторите, пока больше не останется циклов. Результат эффективен, потому что все выгодные сделки совершены.

История

Ллойд Шепли и Герберт Скарф представили алгоритм Top Trading Cycles в 1974 году как решение проблемы рынка жилья, доказав, что он дает уникальные Парето-эффективные распределения. Алгоритм приобрел практическое значение благодаря работе Элвина Рота по обмену почками, где он стал центральным элементом сопоставления доноров и реципиентов. Нобелевская премия 2012 года, присужденная Роту, подтвердила важность TTC для реального проектирования рынков, особенно в трансплантации органов.

Когда применять

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

Ограничения и замечания

  • Требует строгих порядков предпочтений без безразличия; расширения для слабых предпочтений сложны
  • Не является коалиционно-устойчивым: коалиции агентов могут искажать предпочтения для улучшения коллективного результата
  • Чувствительность к циклам предпочтений: отсутствие циклов может привести к тому, что некоторые агенты останутся без сделки
  • Ограничен сопоставлением без денежных переводов; неэффективен для гетерогенных оценок

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Парето-эффективный: не существует улучшений без сделок; все взаимовыгодные обмены выполнены
  • Индивидуально рациональный: каждый агент слабо предпочитает конечное распределение своему первоначальному endowment
  • Стратегически устойчивый в определенных условиях: агенты не могут улучшить свое положение, искажая предпочтения
  • Вычислительно эффективный: полиномиальное время с простой реализацией
  • Прозрачный: агенты понимают, как их выбор приводит к распределению

Применение

  • Обмен почками: сопоставление доноров органов и реципиентов для повышения совместимости трансплантатов посредством многосторонних обменов
  • Распределение жилья: эффективное назначение комнат в университетских общежитиях или квартир в государственном жилом фонде
  • Выбор школы: назначение учащихся в школы с ограничениями по вместимости и разнообразием предпочтений
  • Обмен долями печени: содействие парным обменам доноров для трансплантации печени от живого донора
  • Обмен мебелью и товарами: организация эффективных бартерных обменов на платформах совместного использования

Как это работает

Как это работает

1

Создать ориентированный граф, где каждый агент указывает на наиболее предпочтительного агента среди тех, кто еще находится на рынке.

2

Найти все циклы в графе (последовательности, где A указывает на B, B указывает на C, ..., обратно на A).

3

Для каждого идентифицированного цикла выполнить сделки: каждый агент получает endowment (имущество) агента, на которого он указал.

4

Удалить агентов, совершивших сделки, и их endowment с рынка. Реконструировать граф предпочтений среди оставшихся агентов и повторить, пока не останется больше циклов.

Частые ошибки

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

Часто задаваемые вопросы

Почему Парето-эффективность важна при распределении ресурсов?

Парето-эффективность гарантирует, что ни один агент не может быть улучшен без ухудшения положения другого. Это минимальное требование для «хорошего» распределения; нарушение его означает, что ресурсы тратятся впустую и могут быть перераспределены в пользу кого-то.

Может ли TTC произвести несколько различных распределений?

Нет. Алгоритм TTC с его уникальным графом предпочтений производит уникальное Парето-эффективное распределение. Путь к этому распределению (порядок идентификации цикла и выполнения сделки) может варьироваться, но конечный результат всегда один и тот же.

Как TTC модифицируется для обмена почками, когда не все пары донор-реципиент совместимы?

При обмене почками граф предпочтений строится только на совместимых парах. Затем алгоритм идентифицирует циклы и цепочки обменов между совместимыми агентами, расширяя исходный TTC для учета биологических ограничений.

Похожие методы

Источники

  1. Shapley, L. S., & Scarf, H. (1974). On cores and indivisibility. Journal of Mathematical Economics, 1(1), 23-37.

    Открыть ссылку DOI
    Скопировано.
  2. Roth, A. E., Sönmez, T., & Ünver, M. U. (2008). Efficient kidney exchange: Coincidence of wants in markets with compatibility. American Economic Review, 97(3), 828-851.

    Открыть ссылку DOI
    Скопировано.