Capacity Planning in Stable Matching
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914904425889792 |
|---|---|
| author | Bobbio, Federico Carvalho, Margarida Lodi, Andrea Rios, Ignacio Torrico, Alfredo |
| author_facet | Bobbio, Federico Carvalho, Margarida Lodi, Andrea Rios, Ignacio Torrico, Alfredo |
| contents | Motivated by the shortage of seats that the Chilean school choice system is facing, we introduce the problem of jointly increasing school capacities and finding a student-optimal assignment in the expanded market. Due to the theoretical and practical complexity of the problem, we provide a comprehensive set of tools to solve the problem, including different mathematical programming formulations, a cutting plane algorithm, and two heuristics that allow obtaining near-optimal solutions quickly. On the theoretical side, we show the correctness of our formulations, different properties of the objective and feasible region that facilitate computation, and also several properties of the underlying mechanism to find a student-optimal matching under capacity expansions. On the computational side, we use data from the Chilean school choice system to demonstrate the impact of our framework and derive insights that could help alleviate the problem. Our results show that each additional seat can benefit multiple students and that we can effectively target the assignment of previously unassigned students or improve the assignment of several students through improvement chains. Nevertheless, our results show that the marginal effect of each additional seat is decreasing and that simply adding seats is insufficient to ensure every student gets assigned to some school. Finally, we discuss several extensions of our framework, showcasing its flexibility to accommodate different needs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2110_00734 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Capacity Planning in Stable Matching Bobbio, Federico Carvalho, Margarida Lodi, Andrea Rios, Ignacio Torrico, Alfredo Computer Science and Game Theory Computational Complexity Optimization and Control Motivated by the shortage of seats that the Chilean school choice system is facing, we introduce the problem of jointly increasing school capacities and finding a student-optimal assignment in the expanded market. Due to the theoretical and practical complexity of the problem, we provide a comprehensive set of tools to solve the problem, including different mathematical programming formulations, a cutting plane algorithm, and two heuristics that allow obtaining near-optimal solutions quickly. On the theoretical side, we show the correctness of our formulations, different properties of the objective and feasible region that facilitate computation, and also several properties of the underlying mechanism to find a student-optimal matching under capacity expansions. On the computational side, we use data from the Chilean school choice system to demonstrate the impact of our framework and derive insights that could help alleviate the problem. Our results show that each additional seat can benefit multiple students and that we can effectively target the assignment of previously unassigned students or improve the assignment of several students through improvement chains. Nevertheless, our results show that the marginal effect of each additional seat is decreasing and that simply adding seats is insufficient to ensure every student gets assigned to some school. Finally, we discuss several extensions of our framework, showcasing its flexibility to accommodate different needs. |
| title | Capacity Planning in Stable Matching |
| topic | Computer Science and Game Theory Computational Complexity Optimization and Control |
| url | https://arxiv.org/abs/2110.00734 |