🤝 匹配市场

Alvin Roth 的诺贝尔奖工作——没有价格的匹配问题如何解决

什么是匹配市场？

有些市场没有价格——你不能"买"一个肾脏，也不能"买"一个学校名额。这些市场需要匹配：双边各有一组参与者，每组对另一组有偏好，需要设计一个算法让匹配结果满足特定性质。

📐 匹配市场 vs 商品市场

	商品市场	匹配市场
价格机制	有（价格调节供需）	没有（不能用价格分配）
例子	股票、商品期货	器官移植、学校录取、就业
设计挑战	定价策略	匹配算法+激励设计
关键性质	均衡价格	稳定匹配

Gale-Shapley 算法：稳定匹配

🔑 1962 年的突破

David Gale 和 Lloyd Shapley 在 1962 年提出了延迟接受算法（Deferred Acceptance），证明了：对于任何偏好结构，都存在一个稳定匹配。Shapley 因此获得 2012 年诺贝尔经济学奖。

稳定匹配的条件：不存在一对参与者，他们都更偏好彼此而非当前的匹配对象。如果存在这样的"破坏对"，匹配就是不稳定——他们会"私奔"。

# Gale-Shapley 延迟接受算法
def gale_shapley(men_preferences, women_preferences):
    """
    men_preferences: {man: [woman1, woman2, ...]} 按偏好排序
    women_preferences: {woman: [man1, man2, ...]} 按偏好排序
    返回: 稳定匹配 {man: woman}
    """
    # 初始化
    free_men = list(men_preferences.keys())
    proposals = {man: 0 for man in men_preferences}  # 每个男人下次向谁求婚
    matches = {}  # {woman: man} 当前匹配
    
    while free_men:
        man = free_men[0]
        # 男人向偏好列表中下一个女人求婚
        woman = men_preferences[man][proposals[man]]
        proposals[man] += 1
        
        if woman not in matches:
            # 女人空闲 → 暂时接受
            matches[woman] = man
            free_men.remove(man)
        else:
            # 女人已有匹配 → 比较偏好
            current_man = matches[woman]
            woman_rank = women_preferences[woman]
            if woman_rank.index(man) < woman_rank.index(current_man):
                # 女人更喜欢新求婚者 → 换人
                matches[woman] = man
                free_men.remove(man)
                free_men.append(current_man)  # 前任重新进入自由市场
            # 否则，男人被拒绝，继续向下一个求婚
    
    return {man: woman for woman, man in matches.items()}

# 示例
men_prefs = {
    'A': ['X', 'Y', 'Z'],
    'B': ['Y', 'X', 'Z'],
    'C': ['X', 'Y', 'Z'],
}
women_prefs = {
    'X': ['B', 'A', 'C'],
    'Y': ['A', 'B', 'C'],
    'Z': ['A', 'B', 'C'],
}
result = gale_shapley(men_prefs, women_prefs)
# 结果: A-Y, B-X, C-Z (男性最优稳定匹配)
# 注意：Gale-Shapley 给出的是"求婚方最优"的稳定匹配

真实世界的匹配市场

🏥 NRMP：医生-医院匹配

美国国家住院医匹配计划（NRMP）是匹配理论最成功的应用：

问题：每年 ~40000 名医学院毕业生需要匹配到住院医项目
机制：修改版 Gale-Shapley 算法（考虑夫妻配对等约束）
历史：1952 年就开始使用，1998 年 Alvin Roth 重新设计算法解决夫妻配对问题
效果：匹配率 > 95%，几乎不存在"破坏对"

为什么不用价格？：伦理原因——医生不应"买"住院医岗位，医院也不应"买"医生。

🏫 学校选择：波士顿机制 vs 顶级交易循环

学校分配也是一个匹配问题。不同的匹配机制导致完全不同的策略行为：

波士顿机制（2005年前）：给第一志愿优先权。结果：家长策略性填报——不敢把热门学校填第一志愿，怕浪费。不是激励相容的！
顶级交易循环（TTC）：每个学生有一个"优先权"（如住得近），可以"交易"优先权。激励相容——报真话是最优策略。
延迟接受（DA）：Gale-Shapley 变体。激励相容（对学生而言），更常被采用。

教训：机制设计不只是数学——它改变了人们的策略行为，进而改变了结果。

❤️ 肾交换

Alvin Roth 最有影响力的工作：设计肾交换匹配系统。

问题：患者需要肾移植，亲人愿意捐但血型不匹配。A 的亲人可以给 B，B 的亲人可以给 A——但需要同时手术。
规模：美国每年约 8000 例活体肾移植，但等待名单上有 ~90000 人
机制：全国肾交换注册系统，用匹配算法找到最优的交换链（2-way、3-way 甚至更长链）
效果：Roth 设计的系统使得肾交换从每年几十例增加到数千例

Roth 因此与 Shapley 共同获得 2012 年诺贝尔经济学奖。

AI 中的匹配市场

🤖 用户-Agent 匹配

当你有多个专长不同的 Agent 和多个需求不同的用户时，这就是一个匹配市场：

用户偏好：需求类型、预算、速度要求、质量要求
Agent 特性：专长领域、响应速度、质量等级、成本
匹配目标：最大化用户满意度 + 最大化 Agent 利用率

设计选择：用价格（市场竞价）还是用偏好（匹配算法）？

价格机制：灵活，但用户可能不信任"按价格分配"
匹配算法：公平透明，但需要准确的偏好信息

🛠️ 任务-Agent 匹配

更细粒度的问题：不同子任务需要不同能力的 Agent：

# 基于 Gale-Shapley 的任务-Agent 匹配
class TaskAgentMatching:
    """任务与 Agent 的最优匹配"""
    
    def __init__(self, tasks, agents):
        self.tasks = tasks    # {task_id: {'type': ..., 'priority': ...}}
        self.agents = agents  # {agent_id: {'skills': [...], 'load': ...}}
    
    def compute_preferences(self):
        """计算偏好排序"""
        task_prefs = {}  # 每个任务对Agent的偏好
        agent_prefs = {}  # 每个Agent对任务的偏好
        
        for tid, task in self.tasks.items():
            # 任务偏好：技能匹配度 > 当前负载低
            scores = []
            for aid, agent in self.agents.items():
                match_score = len(set(task.get('skills',[])) & set(agent.get('skills',[])))
                load_score = 1 - agent.get('load', 0)
                scores.append((aid, match_score * 2 + load_score))
            task_prefs[tid] = [a for a, s in sorted(scores, key=lambda x: -x[1])]
        
        for aid, agent in self.agents.items():
            # Agent偏好：技能匹配 > 高优先级任务
            scores = []
            for tid, task in self.tasks.items():
                match = len(set(task.get('skills',[])) & set(agent.get('skills',[])))
                priority = task.get('priority', 0)
                scores.append((tid, match * 2 + priority))
            agent_prefs[aid] = [t for t, s in sorted(scores, key=lambda x: -x[1])]
        
        return task_prefs, agent_prefs
    
    def match(self):
        task_prefs, agent_prefs = self.compute_preferences()
        return gale_shapley(task_prefs, agent_prefs)

市场失灵的三个信号

⚠️ Roth 的市场失灵三要素

Alvin Roth 指出，匹配市场失灵有三个原因：

厚度不足（Thickness）：参与者太少，找不到好的匹配。
AI 应用：新上线的 Agent 技能市场，没有足够的买方和卖方。
拥塞（Congestion）：参与者太多，无法有效评估所有选项。
AI 应用：1000 个 Agent 竞争 100 个任务，匹配算法的复杂度爆炸。
不安全（Safety）：参与者不敢表达真实偏好。
AI 应用：Agent 不敢暴露自己的弱点（如"我不擅长数学"），导致匹配不优。

好的市场设计必须同时解决这三个问题。