Алгоритм Топ-Трейдинг Циклов
- Автор метода
- 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
- Стратегически устойчивый в определенных условиях: агенты не могут улучшить свое положение, искажая предпочтения
- Вычислительно эффективный: полиномиальное время с простой реализацией
- Прозрачный: агенты понимают, как их выбор приводит к распределению
Применение
- Обмен почками: сопоставление доноров органов и реципиентов для повышения совместимости трансплантатов посредством многосторонних обменов
- Распределение жилья: эффективное назначение комнат в университетских общежитиях или квартир в государственном жилом фонде
- Выбор школы: назначение учащихся в школы с ограничениями по вместимости и разнообразием предпочтений
- Обмен долями печени: содействие парным обменам доноров для трансплантации печени от живого донора
- Обмен мебелью и товарами: организация эффективных бартерных обменов на платформах совместного использования
Как это работает
Как это работает
Создать ориентированный граф, где каждый агент указывает на наиболее предпочтительного агента среди тех, кто еще находится на рынке.
Найти все циклы в графе (последовательности, где A указывает на B, B указывает на C, ..., обратно на A).
Для каждого идентифицированного цикла выполнить сделки: каждый агент получает endowment (имущество) агента, на которого он указал.
Удалить агентов, совершивших сделки, и их endowment с рынка. Реконструировать граф предпочтений среди оставшихся агентов и повторить, пока не останется больше циклов.
Частые ошибки
- Смешение Парето-эффективности с справедливостью или равенством; TTC максимизирует эффективность, но не равенство результатов
- Предположение о стратегической устойчивости во всех условиях; TTC является правдивым только в определенных контекстах (например, на рынке жилья, но не в обмене почками с приоритезацией)
- Упущение того, что алгоритм завершается, когда больше нет прибыльных циклов, потенциально оставляя агентов без сделки
- Забывание, что TTC требует строгих предпочтений без безразличия; применение его со слабыми предпочтениями требует расширения
Часто задаваемые вопросы
Почему Парето-эффективность важна при распределении ресурсов?
Парето-эффективность гарантирует, что ни один агент не может быть улучшен без ухудшения положения другого. Это минимальное требование для «хорошего» распределения; нарушение его означает, что ресурсы тратятся впустую и могут быть перераспределены в пользу кого-то.
Может ли TTC произвести несколько различных распределений?
Нет. Алгоритм TTC с его уникальным графом предпочтений производит уникальное Парето-эффективное распределение. Путь к этому распределению (порядок идентификации цикла и выполнения сделки) может варьироваться, но конечный результат всегда один и тот же.
Как TTC модифицируется для обмена почками, когда не все пары донор-реципиент совместимы?
При обмене почками граф предпочтений строится только на совместимых парах. Затем алгоритм идентифицирует циклы и цепочки обменов между совместимыми агентами, расширяя исходный TTC для учета биологических ограничений.
Похожие методы
Источники
Shapley, L. S., & Scarf, H. (1974). On cores and indivisibility. Journal of Mathematical Economics, 1(1), 23-37.
Открыть ссылку DOIСкопировано.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Скопировано.