Manuscripts
Major revision in Operations Research
Yuri Faenza, Ayoub Foussoul, and Chengyue He
Abstract
We introduce and study Minimum Cut Representability, a framework to solve optimization and feasibility problems over stable matchings by representing them as minimum s-t cut problems on digraphs over rotations. We provide necessary and sufficient conditions on objective functions and feasibility sets for problems to be minimum cut representable. In particular, we define the concepts of first and second order differentials of a function over stable matchings and show that a problem is minimum cut representable if and only if, roughly speaking, the objective function can be expressed solely using these differentials, and the feasibility set is a sublattice of the stable matching lattice. To demonstrate the practical relevance of our framework, we study a range of real-world applications, including problems involving school choice with siblings and a two-stage stochastic stable matching problem. We show how our framework can be used to help solving these problems.
arXiv: Minimum Cut Representability of Stable Matching ProblemsManuscript
Itai Feigenbaum and Chengyue He
Abstract
We provide a new mixed integer linear programming formulation for the problem of maximizing the expected number of transplants in kidney exchange with cancellations. Our formulation uses O(|E| + |G ⟲ |) variables and O(|V| + |E| + |G ⟲ |) constraints, where |E| is the number of edges in the compatibility graph, |V| is the number of vertices, and |G ⟲ | is the number of cycles of allowed size. This improves upon the best known formulation, which uses O(L|E| + |G ⟲ |) variables and O(L|V| + L|E| + |G ⟲ |) constraints, where L is a predetermined chain length cap. Another advantage of our formulation is that it does not require capping chain lengths in advance. Our formulation is based on a modification of the mixed integer linear program provided by Dickerson et al. [2020], where we drop the position-indexing. This is a partial draft: additional results and computational experiments will be added soon.
SSRN: Improved Formulation for Optimal Failure Aware Kidney ExchangeJournal Articles
Mathematics of Operations Research · 2026
Yuri Faenza, Chengyue He, and Jay Sethuraman
Abstract
Scarf's algorithm gives a pivoting procedure to find a special vertex—a dominating vertex—in down-monotone polytopes. This paper studies the behavior of Scarf's algorithm when employed to find stable matchings in bipartite graphs. First, it proves that Scarf's algorithm can be implemented to run in polynomial time, showing the first positive result on its runtime in significant settings. Second, it shows an infinite family of instances where, no matter the pivoting rule and runtime, Scarf's algorithm outputs a matching from an exponentially small subset of all stable matchings, thus showing a structural weakness of the approach.
arXiv: Scarf's Algorithm and Stable MarriagesAccepted for publication in Mathematics of Operations Research
Itai Feigenbaum and Chengyue He
Abstract
Patients requiring kidney transplant may have proxy donors, who wish to donate a kidney to the patient—but are incompatible. However, patients can swap their proxy donors for a compatible one. Transplants often get canceled, so planned swaps should maximize the expected number of non-canceled transplants. Exact maximization is neither strategyproof nor core-stable: patients can increase their probability of receiving a kidney via hiding proxy donors, or via side-arrangements. We introduce a group-strategyproof and core-stable mechanism called SuperGreedy. On uniform markets, where cancellation probabilities are equal across transplants, SuperGreedy is worst-case 2.03-approximate for realistically large cancellation probabilities, and empirically average-case 1.142-approximate in simulation. Our results extend beyond current practice, to when patients can swap multiple proxy donors, with weaker theoretical approximation guarantees but even stronger empirical performance. SuperGreedy is efficiently computable when restricted to size-2 cycles; without this restriction SuperGreedy is NP-hard, but still practically computable on uniform markets.
SSRN: Managing Self-Interested Behavior in Failure-Aware Kidney ExchangeConference Proceedings
ICALP · 2025
Karthekeyan Chandrasekaran, Yuri Faenza, Chengyue He, and Jay Sethuraman
Abstract
Scarf's algorithm—a pivoting procedure that finds a dominating extreme point in a down-monotone polytope—can be used to show the existence of a fractional stable matching in hypergraphs. The problem of finding a fractional stable matching in a hypergraph, however, is PPAD-complete. In this work, we study the behavior of Scarf's algorithm on arborescence hypergraphs, the family of hypergraphs in which hyperedges correspond to the paths of an arborescence. For arborescence hypergraphs, we prove that Scarf's algorithm can be implemented to find an integral stable matching in polynomial time. En route to our result, we uncover novel structural properties of bases and pivots for the more general family of network hypergraphs. Our work provides the first proof of polynomial-time convergence of Scarf's algorithm on hypergraphic stable matching problems, giving hope to the possibility of polynomial-time convergence of Scarf's algorithm for other families of polytope.
arXiv: Scarf's Algorithm on Arborescence HypergraphsIPCO · 2024
Yuri Faenza, Ayoub Foussoul, and Chengyue He
Abstract
We introduce and study a two-stage stochastic stable matching problem between students and schools. A decision maker chooses a stable matching in a marriage instance; then, after some agents enter or leave the market following a probability distribution D, chooses a stable matching in the new instance. The goal is, roughly speaking, to maximize the expected quality of the matchings across the two stages and minimize the expected students’ discontent for being downgraded to a less preferred school in the second-stage. We consider both the case when D is given explicitly and when it is accessed via a sampling oracle. In the former case, we give a polynomial time algorithm. In the latter case, we show that, unless P = NP, no algorithm can find the optimal value or the optimal solution of the problem in polynomial-time. On the positive side, we give a pseudopolynomial algorithm that computes a solution of arbitrarily small additive error. Our techniques include the use of a newly defined poset of stable pairs, which may be of independent interest.
Open-access PDF: Two-Stage Stochastic Stable Matching