Using school choice as a motivating example, we introduce a stylized model of a many-to-one matching market where the clearinghouse seeks to implement contingent priorities—i.e., priorities that depend on the current assignment—to improve the likelihood that students with siblings are assigned 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 finding one if it exists, 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. A full version of this paper can be found at https://arxiv.org/abs/2409.04914

Given increasing congestion and pollution concerns, cities are turning to congestion pricing to charge drivers to use the roadways. The promise of technology advances is to enable data-driven prices, much like advances in algorithmic pricing have transformed ride-hailing platforms. However, making such decisions in a data-driven manner is difficult because of multiple desiderata and uncertainty in individuals' behavior.

Centralized mechanisms are becoming the standard approach to solve several assignment problems. Examples include the allocation of students to schools (school choice), high-school graduates to colleges, residents to hospitals and refugees to cities. In most of these markets, a desirable property of the assignment is stability, which guarantees that no pair of agents has incentive to circumvent the matching. Using school choice as our matching market application, we introduce the problem of jointly allocating a school capacity expansion and finding the best stable matching for the students in the expanded market. We analyze theoretically the problem, focusing on the trade-off behind the multiplicity of student-optimal assignments, and the problem complexity. Since the theoretical intractability of the problem precludes the adaptation of classical approaches to solve it efficiently, we generalize existent mathematical programming formulations of stability constraints to our setting. These generalizations result in integer quadratically-constrained programs, which are computationally hard to solve. In addition, we propose a novel mixed-integer linear programming formulation that is exponentially-large on the problem size. We show that the stability constraints can be separated in linear time, leading to an effective cutting-plane method. We evaluate the performance of our approaches in a detailed computational study, and we find that our cutting-plane method outperforms mixed-integer programming solvers applied to existent formulations extended to our problem setting. We also propose two heuristics that are effective for large instances of the problem. Finally, we use the Chilean school choice system data to demonstrate the impact of capacity planning under stability conditions. Our results show that each additional school seat can benefit multiple students. On the one hand, we can focus on access by prioritizing extra seats that benefit previously unassigned students; on the other hand, we can focus on merit by allocating extra seats that benefit several students via chains of improvement. These insights empower the decision-maker in tuning the matching algorithm to provide a fair application-oriented solution.

Online bipartite matching (OBM) is a fundamental model underpinning many important applications, including search engine advertisement, website banner and pop-up ads, and ride hailing. We study the independent and identically distributed (i.i.d.) OBM problem, in which one side of the bipartition is fixed and known in advance, whereas nodes from the other side appear sequentially as i.i.d. realizations of an underlying distribution and must immediately be matched or discarded. We introduce dynamic relaxations of the set of achievable matching probabilities; show how they theoretically dominate lower dimensional, static relaxations from previous work; and perform a polyhedral study to theoretically examine the new relaxations’ strength. We also discuss how to derive heuristic policies from the relaxations’ dual prices in a similar fashion to dynamic resource prices used in network revenue management. We finally present a computational study to demonstrate the empirical quality of the new relaxations and policies. Summary of Contribution: Online bipartite matching (OBM) is one of the fundamental problems in the area of online decision analysis with a wide variety of applications in operations research and computer science, for example, online advertising, ride sharing, and general resource allocation. Over the last decades, both communities have been interested in the design and analysis of new approaches. Our main contribution is to provide a polyhedral study that considers the problem’s sequential nature. Specifically, we achieve this via dynamic relaxations. We also discuss how to derive heuristic policies from the relaxations’ dual prices. We support our theoretical findings with a detailed computational study.

Constrained submodular function maximization has been used in subset selection problems such as selection of most informative sensor locations. Although these models have been quite popular, the solutions obtained via this approach are unstable to perturbations in data defining the submodular functions. Robust submodular maximization has been proposed as a richer model that aims to overcome this discrepancy as well as increase the modeling scope of submodular optimization. In this work, we consider robust submodular maximization with structured combinatorial constraints and give efficient algorithms with provable guarantees. Our approach is applicable to constraints defined by single or multiple matroids and knapsack as well as distributionally robust criteria. We consider both the offline setting where the data defining the problem are known in advance and the online setting where the input data are revealed over time. For the offline setting, we give a general (nearly) optimal bicriteria approximation algorithm that relies on new extensions of classical algorithms for submodular maximization. For the online version of the problem, we give an algorithm that returns a bicriteria solution with sublinear regret. Summary of Contribution: Constrained submodular maximization is one of the core areas in combinatorial optimization with a wide variety of applications in operations research and computer science. Over the last decades, both communities have been interested on the design and analysis of new algorithms with provable guarantees. Sensor location, influence maximization and data summarization are some of the applications of submodular optimization that lie at the intersection of the aforementioned communities. Particularly, our work focuses on optimizing several submodular functions simultaneously. We provide new insights and algorithms to the offline and online variants of the problem which significantly expand the related literature. At the same time, we provide a computational study that supports our theoretical results.

It is well known that the standard greedy algorithm guarantees a worst-case approximation factor of $1-1/e$ when maximizing a monotone submodular function under a cardinality constraint. However, empirical studies show that its performance is substantially better in practice. This raises a natural question of explaining this improved performance of the greedy algorithm. In this work, we define sharpness for submodular functions as a candidate explanation for this phenomenon. We show that the greedy algorithm provably performs better as the sharpness of the submodular function increases. This improvement ties in closely with the faster convergence rates of first order methods for sharp functions in convex optimization.

Constrained submodular function maximization has been used in subset selection problems such as selection of most informative sensor locations. While these models have been quite popular, the solutions obtained via this approach are unstable to perturbations in data defining the submodular functions. Robust submodular maximization has been proposed as a richer model that aims to overcome this discrepancy as well as increase the modeling scope of submodular optimization. In this work, we consider robust submodular maximization with structured combinatorial constraints and give efficient algorithms with provable guarantees. Our approach is applicable to constraints defined by single or multiple matroids, knapsack as well as distributionally robust criteria. We consider both the offline setting where the data defining the problem is known in advance as well as the online setting where the input data is revealed over time. For the offline setting, we give a nearly optimal bi-criteria approximation algorithm that relies on new extensions of the classical greedy algorithm. For the online version of the problem, we give an algorithm that returns a bi-criteria solution with sub-linear regret.