Two-Stage Stochastic Capacity Expansion in Stable Matching under Truthful or Strategic Preference Uncertainty
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914380373819392 |
|---|---|
| author | Bazotte, Maria Carvalho, Margarida Vidal, Thibaut |
| author_facet | Bazotte, Maria Carvalho, Margarida Vidal, Thibaut |
| contents | Recent studies on many-to-one matching markets have explored agents with flexible capacity and truthful preference reporting, focusing on mechanisms that jointly design capacities and select a matching. However, in real-world applications such as school choice and residency matching, preferences are revealed after capacity decisions are made, with matching occurring afterward; uncertainty about agents' preferences must be considered during capacity planning. Moreover, even under strategy-proof mechanisms, agents may strategically misreport preferences based on beliefs about admission chances. We introduce a two-stage stochastic matching problem with uncertain preferences, using school choice as a case study. In the first stage, the clearinghouse expands schools' capacities before observing students' reported preferences. Students either report their true preferences, producing exogenous uncertainty, or act strategically, submitting reported preferences based on their true preferences and admission chances (which depend on capacities), introducing endogenous uncertainty. In the second stage, the clearinghouse computes the student-optimal stable matching based on schools' priorities and students' reported preferences. In strategic cases, endogenous reported preferences are utility-maximizing transformations of capacity decisions and exogenous true preferences; we handle uncertainty using sample average approximation(SAA). We develop behavior-based mathematical formulations and, due to problem complexity, propose Lagrangian- and local-search-based behavior-specific heuristics for near-optimal solutions. Our SAA-based approaches outperform the average scenario approach on students' matching preferences and admission outcomes, emphasizing the impact of stochastic preferences on capacity decisions. Student behavior notably influences capacity design, stressing the need to consider misreports. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_22560 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Two-Stage Stochastic Capacity Expansion in Stable Matching under Truthful or Strategic Preference Uncertainty Bazotte, Maria Carvalho, Margarida Vidal, Thibaut Computer Science and Game Theory Optimization and Control Recent studies on many-to-one matching markets have explored agents with flexible capacity and truthful preference reporting, focusing on mechanisms that jointly design capacities and select a matching. However, in real-world applications such as school choice and residency matching, preferences are revealed after capacity decisions are made, with matching occurring afterward; uncertainty about agents' preferences must be considered during capacity planning. Moreover, even under strategy-proof mechanisms, agents may strategically misreport preferences based on beliefs about admission chances. We introduce a two-stage stochastic matching problem with uncertain preferences, using school choice as a case study. In the first stage, the clearinghouse expands schools' capacities before observing students' reported preferences. Students either report their true preferences, producing exogenous uncertainty, or act strategically, submitting reported preferences based on their true preferences and admission chances (which depend on capacities), introducing endogenous uncertainty. In the second stage, the clearinghouse computes the student-optimal stable matching based on schools' priorities and students' reported preferences. In strategic cases, endogenous reported preferences are utility-maximizing transformations of capacity decisions and exogenous true preferences; we handle uncertainty using sample average approximation(SAA). We develop behavior-based mathematical formulations and, due to problem complexity, propose Lagrangian- and local-search-based behavior-specific heuristics for near-optimal solutions. Our SAA-based approaches outperform the average scenario approach on students' matching preferences and admission outcomes, emphasizing the impact of stochastic preferences on capacity decisions. Student behavior notably influences capacity design, stressing the need to consider misreports. |
| title | Two-Stage Stochastic Capacity Expansion in Stable Matching under Truthful or Strategic Preference Uncertainty |
| topic | Computer Science and Game Theory Optimization and Control |
| url | https://arxiv.org/abs/2506.22560 |