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

Basic Information

• Paper ID: 2505.13428
• Title: The Meta-rotation Poset for Student-Project Allocation
• Authors: Peace Ayegba, Sofiat Olaosebikan (University of Glasgow)
• Classification: cs.GT (Computer Science - Game Theory)
• Publication Date: October 10, 2025 (arXiv v2)
• Paper Link: https://arxiv.org/abs/2505.13428v2

Abstract

This paper investigates the Student-Project Allocation problem with lecturer preferences over students (SPA-S), which extends the classical stable marriage problem and the 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 objective is to compute stable matchings—assignments of students to projects (and consequently to lecturers)—such that neither students nor lecturers have incentive to deviate from the current assignment. Although originating from university contexts, this problem has applications in numerous allocation scenarios, such as limited resource allocation in wireless networks.

The authors develop meta-rotation theory for SPA-S to establish new structural results, which generalizes the rotation concept from the stable marriage problem. Each meta-rotation corresponds to a minimal set of changes that transforms one stable matching into another in the stable matching lattice. The set of meta-rotations, ordered by their precedence relations, forms a meta-rotation poset. The authors prove a one-to-one correspondence between the set of stable matchings and the closed subsets of the meta-rotation poset.

Research Background and Motivation

Problem Background

The Student-Project Allocation problem (SPA-S) is an important problem in matching theory with the following characteristics:

1. Three-tier Structure: Three levels of participants—students, projects, and lecturers—where projects serve as intermediaries between students and lecturers
2. Capacity Constraints: Both projects and lecturers have capacity limits
3. Preference Expression: Students express preferences over projects; lecturers express preferences over students
4. Stability Requirement: Matchings must satisfy stability conditions, i.e., no blocking pairs exist

Research Motivation

1. Theoretical Gap: While basic algorithms for SPA-S have been established, deep understanding of the structure of stable matchings remains lacking
2. Algorithmic Needs: Efficient algorithms are needed to enumerate and count stable matchings, as well as to compute stable matchings under other optimization objectives
3. Structural Complexity: The three-tier structure of SPA-S prevents direct application of classical rotation theory, requiring new theoretical frameworks
4. Practical Applications: More flexible matching schemes are needed in practical scenarios such as university project allocation and resource distribution

Limitations of Existing Methods

1. Difficulty in Direct Extension: Meta-rotation definitions from the hospital residents problem (HR) cannot be directly applied to SPA-S
2. Structural Differences: In SPA-S, projects may be allocated to different numbers of students across different stable matchings, violating the rural hospital theorem of HR
3. Algorithm Efficiency: Lack of efficient structured methods to explore the stable matching space

Core Contributions

1. Extension of Meta-rotation Theory: Develops meta-rotation theory for SPA-S by defining meta-rotations suitable for three-tier structures
2. Structural Theorems: Proves a one-to-one correspondence between the set of stable matchings and closed subsets of the meta-rotation poset
3. Algorithmic Foundation: Provides theoretical basis for enumerating, counting stable matchings, and computing optimal stable matchings
4. New Lemmas and Theorems: Establishes multiple important lemmas regarding the structure of stable matchings in SPA-S
5. Constructive Methods: Provides concrete algorithms for identifying and eliminating meta-rotations

Detailed Methodology

Problem Definition

SPA-S Problem Definition:

• Student set $S = \{s_1, \ldots, s_{n_1}\}$
• Project set $P = \{p_1, \ldots, p_{n_2}\}$
• Lecturer set $L = \{l_1, \ldots, l_{n_3}\}$
• Each project is offered by a unique lecturer: $P_k \subseteq P$ denotes the set of projects offered by lecturer $l_k$
• Capacity constraints: project capacity $c_j$, lecturer capacity $d_k$
• Preferences: students have strict preferences over projects; lecturers have strict preferences over students

Stability Definition: A matching $M$ is stable if and only if there exists no blocking pair $(s_i, p_j)$ where:

• $s_i$ is either unassigned or prefers $p_j$ to $M(s_i)$
• One of the following conditions holds:
  • Both $p_j$ and $l_k$ are undersubscribed
  • $p_j$ is undersubscribed, $l_k$ is at capacity, and $l_k$ prefers $s_i$ to the worst student in $M(l_k)$
  • $p_j$ is at capacity and $l_k$ prefers $s_i$ to the worst student in $M(p_j)$

Core Theoretical Construction

1. Next Project Definition

For student $s_i$, the next project $s_M(s_i)$ is the first project $p$ on their preference list satisfying:

• Condition (i): $p$ is at capacity in $M$ and lecturer $l$ prefers $s_i$ to $w_M(p)$ (the worst student in $p$)
• Condition (ii): $p$ is undersubscribed in $M$, $l$ is at capacity, and $l$ prefers $s_i$ to $w_M(l)$ (the worst student in $l$'s assignment)

2. Exposed Meta-rotation Definition

A meta-rotation $\rho = \{(s_0, p_0), (s_1, p_1), \ldots, (s_{r-1}, p_{r-1})\}$ is exposed in matching $M$ if and only if:

• Each $(s_t, p_t) \in M$
• $s_t$ is the worst student in $p_t$ under $M$
• $s_{t+1} = \text{next}_M(s_t)$ (indices modulo $r$)

3. Meta-rotation Elimination

Given a stable matching $M$ and an exposed meta-rotation $\rho$, eliminating $\rho$ yields a new matching $M/\rho$:

• Each student $s$ in $\rho$ is assigned to $s_M(s)$
• All other students retain their original assignments

Key Lemmas and Theorems

Lemmas 1-3: Structural Properties under Domination

When $M$ dominates $M'$ and student $s_i$ is assigned to different projects in the two matchings:

• If $s_i$ is assigned to a full project $p_j$ in $M'$, then the worst student in $M(p_j)$ is not in $M'(p_j)$
• If $s_i$ is assigned to an undersubscribed project $p_j$ in $M'$, then the lecturer must be at capacity in $M$

Lemma 6: Project Unreachability

In a meta-rotation, projects between the current project and the next project on a student's preference list cannot form stable pairs.

Lemma 7: Meta-rotation Existence

Any stable matching that is not lecturer-optimal contains at least one exposed meta-rotation.

Lemma 9: Stability After Elimination

The matching obtained by eliminating an exposed meta-rotation remains stable, and the original matching dominates the new matching.

Lemma 10: Consistency

If a student in a meta-rotation prefers the original matching, then all related students prefer the original matching.

Theorem 2: Main Result

There exists a one-to-one correspondence between the set of stable matchings and the closed subsets of the meta-rotation poset.

Experimental Setup

Example Analysis

The paper demonstrates theoretical applications through concrete instances:

Instance $I_1$:

• 9 students, 8 projects, 2 lecturers
• Project capacities: $c_1 = c_3 = 2$, other projects have capacity 1
• Lecturer capacities: $d_1 = 4, d_2 = 5$
• Total of 7 stable matchings

Meta-rotation Identification Process

1. Construct Directed Graph $H(M)$: Vertices are students assigned to different projects in $M$ and $M_L$
2. Path Tracing: Starting from any vertex, follow outgoing edges until revisiting a vertex
3. Cycle Extraction: The path between repeated vertices forms a meta-rotation

Algorithm Verification

Verify theory correctness by successively eliminating meta-rotations:

• $M_1 \xrightarrow{\rho_1} M_2 \xrightarrow{\rho_2} M_3$
• Each elimination produces a new stable matching
• Eventually reaches the lecturer-optimal matching

Experimental Results

Theoretical Verification

1. Meta-rotation Identification: Successfully identifies all 4 meta-rotations in the instance
2. Matching Transformation: Verifies correctness of meta-rotation elimination
3. One-to-One Correspondence: Confirms the correspondence between stable matchings and closed subsets

Structural Findings

1. Repeated Meta-rotation Exposure: The same meta-rotation can be exposed in multiple stable matchings
2. Coexistence of Multiple Meta-rotations: A single stable matching can contain multiple exposed meta-rotations
3. Path Uniqueness: The path starting from any student uniquely determines the meta-rotation

Algorithm Efficiency

• Polynomial-time Construction: The meta-rotation poset can be constructed in polynomial time
• Compact Representation: Although the number of stable matchings may be exponential, the poset provides a compact representation

Related Work

Development of Stable Matching Theory

1. Gale-Shapley Algorithm: Established the foundation of stable matching theory
2. Rotation Theory: Gusfield and Irving developed rotation posets for the stable marriage problem
3. Many-to-Many Extension: Bansal extended the rotation concept to many-to-many settings

SPA-S Related Research

1. Abraham et al.: Established basic algorithms and the unpopular projects theorem for SPA-S
2. Structural Property Research: Existing work primarily focuses on basic properties, lacking deeper structural analysis

Meta-rotation Development

1. HR Problem: Cheng developed meta-rotation theory for the hospital residents problem
2. Cases with Ties: Scott et al. studied super-stable matchings with tied preferences

Conclusions and Discussion

Main Conclusions

1. Theoretical Completeness: Establishes a complete meta-rotation theoretical framework for SPA-S
2. Structural Characterization: Provides a compact structured representation of the set of stable matchings
3. Algorithmic Foundation: Provides theoretical basis for various optimization problems

Limitations

1. Complexity Analysis: Lacks detailed time complexity analysis
2. Practical Validation: Lacks verification on large-scale real data
3. Extension Constraints: Theory primarily applies to strict preference cases

Future Directions

1. Polyhedral Characterization: Develop polyhedral representations of the stable matching set
2. Extension to Ties: Extend to cases with tied preferences
3. Algorithm Optimization: Develop more efficient meta-rotation identification and elimination algorithms
4. Application Research: Validate theoretical value in practical project allocation scenarios

In-Depth Evaluation

Strengths

1. Theoretical Innovation: Successfully extends rotation theory to more complex three-tier structures
2. Rigorous Proofs: Provides complete and rigorous mathematical proofs
3. Practical Value: Provides solid theoretical foundation for practical algorithm design
4. Clear Presentation: Paper structure is clear with accurate mathematical exposition

Technical Highlights

1. Definition Precision: Meta-rotation definition accurately captures structural characteristics of SPA-S
2. Constructive Methods: Provides practically feasible meta-rotation identification methods
3. Completeness Proof: Establishes complete one-to-one correspondence

Shortcomings

1. Computational Complexity: Lacks in-depth analysis of algorithm computational complexity
2. Experimental Scale: Examples are relatively small-scale, lacking large-scale validation
3. Comparative Analysis: Insufficient comparison with other methods

Impact Assessment

1. Theoretical Contribution: Provides important structural insights for matching theory
2. Algorithmic Significance: Offers new solution approaches for related algorithmic problems
3. Application Potential: Has practical application value in educational resource allocation and related fields

Applicable Scenarios

1. University Project Allocation: Directly applicable to student project allocation scenarios
2. Resource Allocation: Applicable to resource allocation problems with intermediary structures
3. Matching Optimization: Provides theoretical tools for various matching optimization problems

References

The paper cites important literature in matching theory, including:

• Gale & Shapley (1962): Pioneering work on the stable marriage problem
• Abraham et al. (2007): Foundational algorithms for SPA-S
• Gusfield & Irving (1989): Structure and algorithms for the stable marriage problem
• Bansal (2007): Polynomial-time algorithms for many-to-many stable allocation

This paper makes important theoretical contributions to the SPA-S problem. Through the development of meta-rotation theory, it not only deepens understanding of the structure of stable matchings but also provides new theoretical tools for solving related algorithmic problems. While there is room for improvement in experimental validation and complexity analysis, its theoretical value and potential application prospects are noteworthy.