Research
You can also find my articles on my Google Scholar profile.
Overlapping Rights in Orbit: Modeling Aggregate Interference and Spectrum Governance for Satellite Megaconstellations
Randall A. Berry, Federico Bobbio, M. Ghosh, D. Guo, Michael L. Honig, P. Krishnamurthy, I. Murtazashvili
Working paper, 2026. Presented at TPRC54
Market Signals without Mission Distortion: Auction Design for Scientific Spectrum Incumbents
Federico Bobbio, Randall A. Berry, Michael L. Honig
Working paper, 2026. Presented at TPRC54
Capacity Variation in the Many-to-one Stable Matching Abstract
Federico Bobbio, Margarida Carvalho, Andrea Lodi, Alfredo Torrico
Operations Research Letters 66:107416, 2026
DOI · arXiv
The many-to-one stable matching problem provides the fundamental abstraction of several real-world matching markets such as school choice and hospital-resident allocation. The classical setup assumes that the agents rank the opposite side and that the capacities of the hospitals are fixed. It is known that increasing the capacity of a single hospital improves the residents’ final allocation. On the other hand, reducing the capacity of a single hospital deteriorates the residents’ allocation. In this work, we study the computational complexity of finding the optimal variation of hospitals’ capacities that leads to the best outcome for the residents, subject to stability and a capacity variation constraint. First, we show that the decision problem of finding the optimal capacity expansion is NP-complete and the corresponding optimization problem is inapproximable within a certain factor. This result holds under strict and complete preferences, and even if we allocate extra capacities to disjoint sets of hospitals. Second, we obtain analogous computational complexity results for the problem of capacity reduction. Finally, we study the variants of these problems when the goal is to maximize the size of the final matching under incomplete preference lists.
Capacity Planning in Stable Matching Abstract
Federico Bobbio, Margarida Carvalho, Andrea Lodi, Ignacio Rios, Alfredo Torrico
Operations Research 74(3):1562–1580, 2026. Extended abstract at ACM EC 2023; presented at EAAMO 2022 and MATCH-UP 2022
Runner-up Award, CORS Open Student Paper Competition 2023
DOI · arXiv
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.
Sharing with Frictions: Limited Transfers and Costly Inspections Abstract
Federico Bobbio, Randall A. Berry, Michael L. Honig, Thanh Nguyen, Vijay G. Subramanian, Rakesh V. Vohra
Working paper, 2025
arXiv
The radio spectrum suitable for commercial wireless services is limited. A portion of the radio spectrum has been reserved for institutions using it for non-commercial purposes such as federal agencies, defense, public safety bodies and scientific institutions. In order to operate efficiently, these incumbents need clean spectrum access. However, commercial users also want access, and granting them access may materially interfere with the existing activity of the incumbents. Conventional market based mechanisms for allocating scarce resources in this context are problematic. Allowing direct monetary transfers to and from public or scientific institutions risks distorting their non-commercial mission. Moreover, often only the incumbent knows the exact value of the interference it experiences, and, likewise, only commercial users can predict accurately the expected monetary outcome from sharing the resource. Thus, our problem is to determine the efficient allocation of resources in the presence of private information without the use of direct monetary transfers. The problem is not unique to spectrum. Other resources that governments hold in trust share the same feature. We propose a novel mechanism design formulation of the problem, characterize the optimal mechanism and describe some of its qualitative properties.
Stable Matching with Contingent Priorities Abstract
Ignacio Rios, Federico Bobbio, Margarida Carvalho, Alfredo Torrico
ACM Conference on Economics and Computation (EC 2025). Poster at ACM EAAMO 2023
DOI · arXiv
Using school choice as a motivating example, we introduce a stylized model of a many-to-one matching market where the clearinghouse aims to implement contingent priorities, i.e., priorities that depend on the current assignment, to prioritize students with siblings and match them together. We provide a series of guidelines and introduce two natural approaches to implement them: (i) absolute, whereby a prioritized student can displace any student without siblings assigned to the school, and (ii) partial, whereby prioritized students can only displace students that have a less favorable lottery than their priority provider. We study several properties of the corresponding mechanisms, including the existence of a stable assignment under contingent priorities, the complexity of deciding whether there exists one, and its incentive properties. Furthermore, we introduce a soft version of these priorities to guarantee existence, and we provide mathematical programming formulations to find such stable matching or certify that one does not exist. Finally, using data from the Chilean school choice system, we show that our framework can significantly increase the number of students assigned to their top preference and the number of siblings assigned together relative to current practice.
Costly Measurements to Incentivize Spectrum Sharing Abstract
Federico Bobbio, Randall A. Berry, Michael L. Honig, Thanh Nguyen, Vijay G. Subramanian, Rakesh V. Vohra
IEEE International Symposium on Dynamic Spectrum Access Networks (DySPAN 2025)
Best Paper Award, Policy Track
DOI
Connectivity services, ranging from cellular broadband to private networks and satellite communications, are driving an unprecedented demand for spectrum. However, much of the prime spectrum is locked into existing federal and scientific allocations, which often by law cannot be relocated in exchange for monetary transfer, thus making market-based reallocation strategies infeasible. We investigate a spectrum allocation mechanism that does not require monetary transfers but instead utilizes measurements that may be costly as a way to incentivize truthful reporting. We consider a scenario involving three agents: An incumbent scientific or federal user (SFU), a commercial user (CU), and a regulator. The incumbent derives value from its current exclusive use of a spectrum band but faces increasing disutility as soon as the CU is allowed to either share the same band or use an adjacent band, while the CU benefits from gaining access. The regulator allocates spectrum based on the incumbent’s reported disutility and the CU’s utility, with provisions to verify reports and penalize dishonesty through spectrum reallocation. Our analysis demonstrates that this mechanism incentivizes truthful reporting and ensures more efficient spectrum utilization, supported by theoretical and experimental evidence on synthetic data.
Balancing Fairness and Match Quality
Federico Bobbio, Margarida Carvalho
Working paper, 2024. Poster at ACM EAAMO 2024
The First AI4TSP Competition: Learning to Solve Stochastic Routing Problems Abstract
Yingqian Zhang, Laurens Bliek, Paulo da Costa, Reza Refaei Afshar, Robbert Reijnen, Tom Catshoek, Daniël Vos, Sicco Verwer, Fynn Schmitt-Ulms, André Hottung, Tapan Shah, Meinolf Sellmann, Kevin Tierney, Carl Perreault-Lafleur, Caroline Leboeuf, Federico Bobbio, Justine Pepin, Warley Almeida Silva, Ricardo Gama, Hugo L. Fernandes, Martin Zaefferer, Manuel López-Ibáñez, Ekhine Irurozki
Artificial Intelligence 319:103918, 2023
First Place (three-way tie), Track 1, AI for TSP Competition (IJCAI 2021)
DOI · arXiv
This paper reports on the first international competition on AI for the traveling salesman problem (TSP) at the International Joint Conference on Artificial Intelligence 2021 (IJCAI-21). The TSP is one of the classical combinatorial optimization problems, with many variants inspired by real-world applications. This first competition asked the participants to develop algorithms to solve an orienteering problem with stochastic weights and time windows (OPSWTW). It focused on two learning approaches: surrogate-based optimization and deep reinforcement learning. In this paper, we describe the problem, the competition setup, and the winning methods, and give an overview of the results. The winning methods described in this work have advanced the state-of-the-art in using AI for stochastic routing problems. Overall, by organizing this competition we have introduced routing problems as an interesting problem setting for AI researchers. The simulator of the problem has been made open-source and can be used by other researchers as a benchmark for new learning-based methods.
Design and Implementation of an Heuristic-Enhanced Branch-and-Bound Solver for MILP Abstract
Warley Almeida Silva, Federico Bobbio, Flore Caye, Defeng Liu, Justine Pepin, Carl Perreault-Lafleur, William St-Arnaud
Report for the MIP 2022 Computational Competition. Poster at the MIP 2022 Workshop
Outstanding Student Submission, MIP 2022 Computational Competition
arXiv
We present a solver for Mixed Integer Programs (MIP) developed for the MIP competition 2022. Given the 10 minutes bound on the computational time established by the rules of the competition, our method focuses on finding a feasible solution and improves it through a Branch-and-Bound algorithm. Another rule of the competition allows the use of up to 8 threads. Each thread is given a different primal heuristic, which has been tuned by hyper-parameters, to find a feasible solution. In every thread, once a feasible solution is found, we stop and we use a Branch-and-Bound method, embedded with local search heuristics, to ameliorate the incumbent solution. The three variants of the Diving heuristic that we implemented manage to find a feasible solution for 10 instances of the training data set. These heuristics are the best performing among the heuristics that we implemented. Our Branch-and-Bound algorithm is effective on a small portion of the training data set, and it manages to find an incumbent feasible solution for an instance that we could not solve with the Diving heuristics. Overall, our combined methods, when implemented with extensive computational power, can solve 11 of the 19 problems of the training data set within the time limit. Our submission to the MIP competition was awarded the “Outstanding Student Submission” honorable mention.
Optimizing the Design of a Loyalty Program Abstract
Federico Bobbio, Margarida Carvalho, Adel Nabli, Sriram Sankaranarayanan, Simon Germain, Mohamed Ossama Hassan, Bassirou Ndao, Genevieve Pagé, Jeremy Piche-Bisson, Vincent Purenne, Russel Shaul
Proceedings of the Ninth Montréal Industrial Problem Solving Workshop, Les Cahiers du GERAD, 2020
Paper
Aeroplan is one of the biggest loyalty programs in Canada with more than five million members. In exchange for their participation in the program the members are offered miles each time they make purchases from the Aeroplan partners. Those miles can then be used by the members as an alternative currency allowing them to buy a variety of products and services offered by the pool of partners. The purpose of our work within the Ninth Montreal Industrial Problem Solving Workshop was to develop a methodology for optimizing the design elements of the loyalty program, i.e., maximizing profitability of the program and its attractiveness and value for its members over the long term. Our team’s goal was to build a conceptual model that would integrate key program dynamics in a game theory framework.
A Plausibility Model for Regret Games Abstract
Federico Bobbio, Jianying Cui
Multi-Agent Systems and Agreement Technologies (EUMAS 2017), Lecture Notes in Artificial Intelligence 10767, Springer, pp. 187–200, 2018
DOI
We develop a plausibility model by defining a new notion of rationality based on the assumption that a player believes that she doesn’t play a regret dominated strategy. Especially, we show that the interactive epistemic outcomes of this type of rationality are in line with the solutions of the Iterated Regret Minimization (IRM) algorithm; hence, we provide the epistemic foundation to the IRM algorithm. Indeed, we state that one can achieve a characterization of the IRM algorithm by keeping upgrading the assumption of rationality, and we obtain common belief of rationality in the limit model.