Skip to content
返回搜索结果

顶尖交易循环

提出者
Lloyd Shapley, Herbert Scarf
年份
1974
类型
algorithm
类别
Game-theoretic

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

顶尖交易循环(Top Trading Cycles, TTC)是一种为不可分割物品分配给代理人的算法,其分配结果满足帕累托效率和个体理性。该算法由Lloyd Shapley和Herbert Scarf于1974年开发,通过识别偏好图中的交易循环,执行这些交易,并迭代重复,直至没有进一步有益的交易为止。TTC因其效率和实现简单性,在肾脏交换和住房分配领域得到广泛应用。

方法背后的直觉

设想一群人,每人拥有一套房,并且每个人都按偏好对所有房屋进行排序。TTC算法的提问方式是:谁是我最喜欢的?指向他/她。现在看看谁指向了你。如果形成一个循环(A指向B,B指向C,C指向A),则执行这些交易——A得到B的房子,B得到C的房子,C得到A的房子。循环中的每个人都满意,因为他们得到了比当前房屋更偏好的房屋。移除该循环并重复,直到不存在更多循环为止。结果是有效的,因为所有有益的交易都已完成。

历史学

Lloyd Shapley和Herbert Scarf于1974年提出了顶尖交易循环算法,作为住房市场问题的解决方案,并证明该算法能产生唯一的帕累托有效分配。该算法通过Alvin Roth在肾脏交换方面的工作获得了实际重要性,并成为匹配捐赠者和接受者的核心。Roth于2012年获得诺贝尔奖,这验证了TTC在现实世界市场设计中的重要性,尤其是在器官移植领域。

何时使用

当分配具有严格偏好排序的物品(如房屋、器官、学校座位)给代理人时,应用TTC。适用于帕累托效率至关重要且不存在货币转移或不希望进行货币转移的情况。TTC特别适合代理人可以在本地识别有益交易的去中心化市场。当代理人拥有完整、无循环的偏好信息时效果最佳。

局限与注意事项

  • 要求严格的偏好排序,不允许无差异;扩展到弱偏好情况复杂
  • 不具备联盟不变性:代理人联盟可以通过谎报偏好来改善集体结果
  • 对偏好循环敏感:循环不存在可能导致某些代理人未被交易
  • 仅限于无货币转移的匹配;对于异质化估值效率不高

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 帕累托效率:不存在不使任何一方变差的交易改进;所有互利的交换都已执行
  • 个体理性:每个代理人最终获得的分配至少与其初始物品一样偏好(弱偏好)
  • 在某些情况下具有策略不变性:代理人通过谎报偏好无法获益
  • 计算效率高:实现简单且为多项式时间
  • 透明:代理人理解其指向的选择如何导致分配

应用

  • 肾脏交换:匹配器官捐赠者和接受者,通过多方交换提高移植兼容性
  • 住房分配:有效分配大学宿舍或公共住房单元
  • 学校选择:在有容量限制和偏好多样性的情况下分配学生到学校
  • 肝脏叶片交换:促进活体肝移植的配对捐赠交换
  • 家具和物品交换:在社区共享平台上组织有效的以物易物交换

使用方式

使用方式

1

构建一个有向图,其中每个代理人指向市场上剩余代理人中其最偏好的代理人。

2

在有向图中找到所有循环(例如A指向B,B指向C,...,回到A的序列)。

3

对于识别出的每个循环,执行交易:每个代理人获得其指向的代理人的物品。

4

从市场中移除已交易的代理人及其物品。在剩余代理人之间重建偏好有向图,并重复此过程,直到不存在更多循环为止。

常见陷阱

  • 将帕累托效率与公平或公正混淆;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 文献
    已复制。