Two-Stage Stochastic Capacity Expansion in Stable Matching under Truthful or Strategic Preference Uncertainty

This paper introduces a two-stage stochastic capacity expansion model for many-to-one matching markets that accounts for both exogenous preference uncertainty and endogenous strategic misreporting, proposing sample average approximation-based heuristics to optimize school capacities and improve student outcomes compared to deterministic approaches.

The Gist

Imagine you are the principal of a school district. You have a big problem: you need to decide today how many new classrooms to build for next year. But you don't know yet which students will apply, or which schools they actually want to attend.

This is the core challenge of the paper: How do you build capacity (classrooms) when you don't know the future demand?

Here is a simple breakdown of the paper's ideas, using some everyday analogies.

1. The Big Mistake: Guessing the Average

Most schools and governments make decisions based on an "Average Scenario."

• The Analogy: Imagine you run a lemonade stand. You look at the weather forecast for the whole month and see the average temperature is 75°F. So, you buy exactly enough lemons for a 75°F day.
• The Problem: In reality, some days are 90°F (you run out of lemonade), and some are 60°F (you have too much). By planning for the "average," you are often wrong.
• In the Paper: Previous research assumed schools knew exactly what students wanted before building classrooms. This paper says, "No, we have to build before we know." If you just plan for the "average" student, you might build too many classrooms for a popular school and too few for a less popular one, leaving kids unhappy or unassigned.

2. The Twist: Students Are Not Robots

The paper adds a second layer of complexity: Students don't always tell the truth.

Even if the matching system is designed to be fair (like a "strategy-proof" system where lying doesn't help), students often lie or strategize because they are scared of getting rejected.

• The Analogy: Think of applying to colleges. You love Harvard, but you think your chances are tiny. So, you don't even list it on your application because you think, "Why bother? I'll just list schools I'm sure to get into."
• The Paper's Insight: Your chances of getting into a school depend on how big that school is.
  • If the school builds a new wing (increases capacity), your chances go up.
  • If you know the school is expanding, you might finally list it as your top choice.
  • If you think the school is small and full, you might skip it entirely.

This creates a feedback loop: The number of classrooms you build changes what students want, which changes who gets in.

3. The Three Types of Students

The authors tested three different "personas" for how students might behave:

1. The Truth-Teller (UM): "I love School A, School B, and School C. I will list them exactly in that order, no matter what." (This is the "Average Scenario" approach).
2. The Portfolio Manager (CEUM): "I love School A, but it's super competitive. I'll list School A, but I'll also list School B and C just in case I get rejected from A. I'm trying to maximize my chances of getting any good school." (This is the most realistic, complex strategy).
3. The Simple Calculator (IEUM): "I love School A. I think I have a 50% chance. I'll list it. I don't worry about the risk of getting rejected from A blocking my chance at B." (A simpler, slightly less smart version of the Portfolio Manager).

4. The Solution: A "Crystal Ball" Approach

Since the authors can't predict the future, they use a math technique called Sample Average Approximation (SAA).

• The Analogy: Instead of guessing one "average" future, imagine you have a crystal ball that shows you 100 different possible futures.
  • Future 1: It's hot, everyone wants the beach school.
  • Future 2: It's rainy, everyone wants the indoor school.
  • Future 3: A new bus route opens, and suddenly the city school is popular.
• The Method: The computer simulates all 100 of these futures. It asks, "If I build 5 classrooms here, how does that work out in Future 1? How about Future 2? What is the average result across all 100?"
• The Result: This allows the principal to build a capacity plan that works well regardless of which future actually happens.

5. The Big Findings

The paper ran thousands of computer simulations and found some surprising things:

• Uncertainty Matters: Planning for the "average" student is a disaster. The "Crystal Ball" (SAA) method consistently got students into schools they liked much better than the old methods.
• Behavior Matters: If you assume students will tell the truth, but they are actually strategizing (trying to game the system), your classroom plan will be wrong.
  • Example: If you build classrooms assuming students will be honest, but they are actually being strategic, you might end up with empty classrooms at the "popular" schools and overcrowding at the "safe" schools.
• The "List Length" Trick: The paper found a cool nuance. If students are allowed to list many schools (a long list), assuming they are "Truth-Tellers" actually works pretty well. But if they can only list one or two schools, you must account for their strategic behavior, or you will fail.

6. The Toolkit

Because this math is incredibly hard (like trying to solve a Sudoku puzzle where the numbers keep changing), the authors didn't just write a theory; they built a toolkit:

• Exact Solvers: For small problems, they found the perfect answer.
• Heuristics (Smart Guessing): For huge problems (like a whole city), they created fast algorithms that get "good enough" answers in seconds, rather than waiting days for the perfect one.

Summary

This paper is about planning for a chaotic future. It teaches us that when you are building schools, hospitals, or refugee centers:

1. Don't just plan for the "average" person.
2. Realize that people will act strategically based on what you build.
3. Use simulations (like a crystal ball) to test your plans against many different possible futures.

By doing this, you ensure that when the doors open, the right number of seats are available for the right students, maximizing happiness and fairness.

Technical Summary

Here is a detailed technical summary of the paper "Two-Stage Stochastic Capacity Expansion in Stable Matching under Truthful or Strategic Preference Uncertainty."

1. Problem Definition

The paper introduces the Two-Stage Stochastic Capacity Expansion in Two-Sided Many-to-One Matching Problem (2-STMMP). This problem addresses a critical gap in matching market design (e.g., school choice, residency matching) where capacity decisions must be made before agents' preferences are revealed.

• Context: In many real-world scenarios (e.g., school districts planning infrastructure), capacity expansion decisions are made years in advance. However, student preferences are uncertain at this stage. Furthermore, even in strategy-proof mechanisms, students often act strategically, misreporting preferences based on their perceived admission chances, which are themselves influenced by the capacity decisions.
• Structure:
  • Stage 1 (First Stage): A clearinghouse decides on capacity expansions ($x$) for schools within a budget $B$. At this point, student preferences are unknown.
  • Stage 2 (Second Stage): Student preferences are realized. Students submit reported preferences (which may be truthful or strategic). The clearinghouse then computes a student-optimal stable matching using the Deferred Acceptance Algorithm (DAA) based on the expanded capacities and reported preferences.
• Objective: Minimize the expected sum of the ranks of the schools assigned to students (maximizing student welfare) across all possible preference realizations.
• Uncertainty Types:
  • Exogenous Uncertainty: Students report true preferences (Utility Maximization - UM). The distribution of preferences is independent of capacity decisions.
  • Endogenous (Decision-Dependent) Uncertainty: Students act strategically. Their reported preferences depend on their true preferences and their perceived admission chances, which are functions of the capacity decisions ($x$). This creates a feedback loop where the decision variable affects the probability distribution of the second-stage inputs.

2. Methodology

A. Behavioral Models

The authors model three distinct student behaviors:

1. Utility Maximization (UM): Students truthfully report their top $K$ preferred schools. Preferences are exogenous.
2. Conjoint Expected Utility Maximization (CEUM): Students strategically select a subset of schools to maximize expected utility, accounting for the probability of admission to each school and the probability of rejection from higher-ranked schools (based on the portfolio choice model by Chade and Smith, 2006).
3. Individual Expected Utility Maximization (IEUM): A simplified strategic model where students maximize the sum of individual expected utilities, ignoring the rejection risk from higher-ranked schools (bounded rationality).

B. Mathematical Formulation

• Transformation Approach: To handle endogenous uncertainty, the authors use the random-variable transformation method (Bazotte et al., 2025). They define the reported preferences as a deterministic function of the first-stage capacity decisions ($x$) and the exogenous true preferences ($u$). This transforms the problem into a standard two-stage stochastic program with exogenous uncertainty, albeit with complex, non-linear transformations.
• Sample Average Approximation (SAA): Since the scenario space is continuous and intractable, the authors approximate the expected value using a finite set of sampled scenarios ($N$).
• Exact Formulations:
  • For UM, they adapt the modified L-constraints formulation for stable matching.
  • For CEUM and IEUM, they develop single-level mixed-integer linear formulations. These involve modeling the inner optimization problems (the students' preference selection) using auxiliary variables and constraints (e.g., Marginal Improvement Algorithm logic for CEUM). This results in a bilevel structure that is reformulated into a single-level MILP.

C. Solution Algorithms

Due to the NP-hardness of the problem and the complexity of endogenous uncertainty, the authors propose a toolkit of exact and heuristic methods:

1. Lagrangian Relaxation (LR) Heuristic (for UM): Relaxes stability constraints to derive strong lower bounds. Combined with DAA to generate upper bounds.
2. Assignment (ASG) Heuristic: A simplified version of LR that performs a single iteration, effectively solving a relaxed assignment problem.
3. Local Search Heuristics (for all behaviors):
   • Greedy Local Search (LS): Hill-climbing strategy exploring capacity transfers and swaps.
   • Simulated Annealing (SA): Probabilistic search allowing uphill moves to escape local optima.
   • These heuristics evaluate neighbors by computing reported preferences (via MIA or IOA algorithms) and solving the stable matching via DAA.

3. Key Contributions

1. Novel Problem Formulation: First study to jointly model capacity expansion and stable matching under preference uncertainty, distinguishing between exogenous (truthful) and endogenous (strategic) uncertainty.
2. Behavioral Integration: Formalizes how strategic student behaviors (CEUM and IEUM) transform capacity decisions into reported preferences, creating a decision-dependent uncertainty framework.
3. Algorithmic Toolkit:
   • Develops exact single-level MILP formulations for strategic behaviors.
   • Proposes efficient heuristics (LR, LS, SA) that handle large-scale instances where exact methods fail.
   • Demonstrates that the Simulated Annealing heuristic offers the best trade-off between runtime and solution quality for strategic cases.
4. Empirical Insights: Extensive computational experiments validating the necessity of stochastic modeling and accurate behavioral assumptions.

4. Experimental Results

A. Value of Stochastic Solution (VSS)

• Superiority of SAA: The SAA-based approach consistently outperforms the deterministic "Expected Value" (EV) approach (which assumes average preferences).
• Metrics: SAA solutions yield significantly better student matching preferences (lower average rank) and result in more students being matched or improving their assignments.
• Magnitude: For large budgets, the VSS reaches up to 9.3% improvement in matching quality for truthful behavior and remains significant (5-7%) for strategic behaviors.

B. Impact of Behavioral Misspecification

• Truthful vs. Strategic: Designing capacity based on the assumption that students are truthful (UM) when they are actually strategic (CEUM/IEUM) leads to suboptimal outcomes.
• Strategic Misalignment: Assuming the wrong strategic model (e.g., assuming IEUM when students follow CEUM) causes significant welfare losses.
• List Size ($K$) Effect:
  • When the preference list limit $K$ is small, strategic behavior (CEUM) diverges significantly from truthful behavior.
  • When $K$ is large, strategic behavior (CEUM) converges closer to truthful behavior, making the simpler UM model a viable approximation. However, IEUM remains distinct regardless of $K$.

C. Computational Performance

• Truthful (UM): Exact methods (MILP) solve ~18% of large instances to optimality within 2 hours; heuristics (LR, ASG) provide near-optimal solutions (<0.1% gap) in seconds.
• Strategic (CEUM/IEUM): Exact methods struggle significantly due to endogenous uncertainty, often failing to close gaps within 8 hours.
• Heuristics: The Simulated Annealing (SA) heuristic is the most robust, consistently finding high-quality solutions (upper bound gaps <0.3%) with stable runtimes across all budget sizes and behavioral models, outperforming Greedy Local Search (LS) which suffers from scalability issues on large budgets.

5. Significance and Implications

• Policy Relevance: The study provides a rigorous framework for public sector planners (schools, hospitals, refugee agencies) to make capacity investment decisions under uncertainty. It proves that ignoring preference uncertainty or assuming truthful reporting leads to inefficient resource allocation and reduced social welfare.
• Strategic Planning: It highlights that capacity design is not just a logistical problem but a game-theoretic one; the design of the mechanism (capacity) influences the behavior of the agents (students), which in turn affects the outcome.
• Methodological Advance: The paper successfully bridges stochastic programming and matching theory, offering a generalizable approach to handle endogenous uncertainty in discrete optimization problems where the distribution of random variables depends on decision variables.

In conclusion, the paper demonstrates that stochastic modeling is essential for capacity expansion in matching markets and that accurately modeling student strategic behavior is critical to achieving optimal outcomes. The proposed SAA-based toolkit provides a practical solution for decision-makers facing these complex, uncertain environments.