Chengyue He

Hi, hope you have a great day!

I am a Postdoctoral Researcher in the Department of Industrial Engineering & Management Sciences at Northwestern University, working with Professor Simge Küçükyavuz.

I obtained my Ph.D. in the Department of Industrial Engineering and Operations Research at Columbia University, where I was fortunate to be advised by Professor Yuri Faenza and Professor Jay Sethuraman.

During my Ph.D., my research focused on discrete optimization, matching markets and mechanism design, with applications including stable matchings, school choice, kidney exchange programs, and strategic behaviors.

Recent News/Upcoming Talks

Education

Columbia University

Ph.D. in Operations Research

Columbia University

M.S. in Operations Research

Zhejiang University

B.S. in Mathematics

Publications
& preprints

Manuscripts

Major revision in Operations Research

Minimum Cut Representability of Stable Matching Problems

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 Problems

Manuscript

Improved Formulation for Optimal Failure Aware Kidney Exchange

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 Exchange

Journal Articles

Mathematics of Operations Research · 2026

Scarf's Algorithm and Stable Marriages

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 Marriages

Accepted for publication in Mathematics of Operations Research

Managing Self-Interested Behavior in Failure-Aware Kidney Exchange

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 Exchange

Conference Proceedings

ICALP · 2025

Scarf's Algorithm on Arborescence Hypergraphs

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 Hypergraphs

IPCO · 2024

Two-Stage Stochastic Stable Matching

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

Teaching

Instructor

  • Graph Theory by Example (Science Honors Program at Columbia Engineering)
    • PhDs and postdocs in the sciences and mathematical disciplines teach courses in their area of study aimed at high school students.
    • Spring 2022, Fall 2021

Teaching Assistant

  • IEOR 3609 Advanced Optimization (Undergrad course)
    • Spring 2025
  • IEOR 6613 Optimization I (PhD level course)
    • Fall 2024, Fall 2023

Personal
miscellany

Name

My name is Chengyue He (何呈栎), pronounced “Chuhng-yweh Huh.” Feel free to call me by my Starbucks name, Hector.

Good hobbies, but by no means good at

Cooking, tennis, hiking, and photography.

Bad hobbies, but partly good at

I have three furry kids.

I play poker. Before that, I played Dota 2.