2025-11-22T09:49:16.331628

Meta-rotations and the Structure of Stable Matchings in the Student Project Allocation Problem

Ayegba, Olaosebikan

We study the Student Project Allocation problem with lecturer preferences over Students (SPA-S), an extension of the well-known Stable Marriage and Hospital Residents problem. In this model, students have preferences over projects, each project is offered by a single lecturer, and lecturers have preferences over students. The goal is to compute a stable matching which is an assignment of students to projects (and thus to lecturers) such that no student or lecturer has an incentive to deviate from their current assignment. While motivated by the university setting, this problem arises in many allocation settings where limited resources are offered by agents with their own preferences, such as in wireless networks. We establish new structural results for the set of stable matchings in SPA-S by developing the theory of meta-rotations, a generalisation of the well-known notion of rotations from the Stable Marriage problem. Each meta-rotation corresponds to a minimal set of changes that transforms one stable matching into another within the lattice of stable matchings. The set of meta-rotations, ordered by their precedence relations, forms the meta-rotation poset. We prove that there is a one-to-one correspondence between the set of stable matchings and the closed subsets of the meta-rotation poset. By developing this structure, we provide a foundation for the design of efficient algorithms for enumerating and counting stable matchings, and for computing other optimal stable matchings, such as egalitarian or minimum-cost matchings, which have not been previously studied in SPA-S.

academic

Meta-rotations and the Structure of Stable Matchings in the Student Project Allocation Problem

基本信息

论文ID: 2505.13428
标题: The Meta-rotation Poset for Student-Project Allocation
作者: Peace Ayegba, Sofiat Olaosebikan (University of Glasgow)
分类: cs.GT (Computer Science - Game Theory)
发表时间: 2025年10月10日 (arXiv v2)
论文链接: https://arxiv.org/abs/2505.13428v2

摘要

本文研究了带有讲师对学生偏好的学生项目分配问题(SPA-S)，这是经典稳定婚姻问题和医院住院医师问题的扩展。在该模型中，学生对项目有偏好，每个项目由单一讲师提供，讲师对学生有偏好。目标是计算稳定匹配，即学生到项目(进而到讲师)的分配，使得没有学生或讲师有动机偏离当前分配。虽然源于大学环境，但该问题在许多分配场景中都有应用，如无线网络等有限资源分配场景。

作者通过发展元旋转(meta-rotations)理论为SPA-S建立了新的结构性结果，这是对稳定婚姻问题中旋转概念的推广。每个元旋转对应于在稳定匹配格中将一个稳定匹配转换为另一个的最小变化集合。元旋转集合按其优先关系排序，形成元旋转偏序集。作者证明了稳定匹配集合与元旋转偏序集的闭子集之间存在一一对应关系。

研究背景与动机

问题背景

学生项目分配问题(SPA-S)是匹配理论中的一个重要问题，具有以下特点：

三层结构：学生、项目、讲师三个层次，其中项目是学生和讲师之间的中介
容量约束：每个项目和讲师都有容量限制
偏好表达：学生对项目有偏好，讲师对学生有偏好
稳定性要求：匹配必须满足稳定性条件，即不存在阻塞对

研究动机

理论缺口：虽然SPA-S的基本算法已经建立，但对其稳定匹配结构的深入理解仍然缺乏
算法需求：需要高效的算法来枚举和计数稳定匹配，以及计算其他优化目标下的稳定匹配
结构复杂性：SPA-S的三层结构使得经典的旋转理论不能直接应用，需要新的理论框架
实际应用：在大学项目分配、资源分配等实际场景中需要更灵活的匹配方案

现有方法的局限性

直接扩展困难：医院住院医师问题(HR)的元旋转定义不能直接应用于SPA-S
结构差异：SPA-S中项目可能在不同稳定匹配中分配到不同数量的学生，违反了HR的乡村医院定理
算法效率：缺乏高效的结构化方法来探索稳定匹配空间

核心贡献

元旋转理论扩展：为SPA-S发展了元旋转理论，定义了适合三层结构的元旋转概念
结构性定理：证明了稳定匹配集合与元旋转偏序集闭子集之间的一一对应关系
算法基础：为枚举、计数稳定匹配以及计算最优稳定匹配提供了理论基础
新的引理和定理：建立了多个关于SPA-S稳定匹配结构的重要引理
构造性方法：提供了识别和消除元旋转的具体算法

方法详解

任务定义

SPA-S问题定义：

学生集合 $S = \{s_1, \ldots, s_{n_1}\}$
项目集合 $P = \{p_1, \ldots, p_{n_2}\}$
讲师集合 $L = \{l_1, \ldots, l_{n_3}\}$
每个项目由唯一讲师提供： $P_k \subseteq P$ 为讲师 $l_k$ 提供的项目集合
容量约束：项目容量 $c_j$ ，讲师容量 $d_k$
偏好：学生对项目有严格偏好，讲师对学生有严格偏好

稳定性定义：匹配 $M$ 是稳定的，当且仅当不存在阻塞对 $(s_i, p_j)$ ，其中：

$s_i$ 未分配或偏好 $p_j$ 胜过 $M(s_i)$
满足以下条件之一：
- $p_j$ 和 $l_k$ 都未满载
- $p_j$ 未满载， $l_k$ 满载，且 $l_k$ 偏好 $s_i$ 胜过 $M(l_k)$ 中最差学生
- $p_j$ 满载且 $l_k$ 偏好 $s_i$ 胜过 $M(p_j)$ 中最差学生