Zhaohong Sun

Tenma Wakasugi, Zhaohong Sun, Kei Kimura et al.

We study two-sided matching markets under hereditary constraints, which extend beyond simple capacity limits and arise in applications such as diversity requirements and refugee resettlement. In these settings, fairness and non-wastefulness are often incompatible, and existing approaches typically address this tension by prioritizing one property at the expense of the other. We take a different approach by relaxing both properties simultaneously in a controlled and symmetric manner. We introduce two notions indexed by an integer $k$: envy-received up to $k$ peers (ER-$k$) and non-wastefulness up to $k$ objections (NW-$k$). Our main theoretical result shows that ER-$k$ and NW-$k$ are always compatible under hereditary constraints for any fixed $k$. We provide two equivalent polynomial-time algorithms to compute such matchings: a $k$-admissible cutoff algorithm and a $k$-admissible college-proposing deferred acceptance mechanism. Finally, experimental results demonstrate that even small relaxations achieve a favorable balance between fairness and non-wastefulness.

Ya Zhou, Zhaohong Sun, Tianxiang Hao et al.

Structural heart disease (SHD) is a prevalent condition with many undiagnosed cases, and early detection is often limited by the high cost and accessibility constraints of echocardiography (ECHO). Recent studies show that artificial intelligence (AI)-based analysis of electrocardiograms (ECGs) can detect SHD, offering a scalable alternative. However, existing methods are fully black-box models, limiting interpretability and clinical adoption. To address these challenges, we propose an interpretable and effective framework that integrates clinically meaningful ECG foundation-model predictors within a generalized additive model, enabling transparent risk attribution while maintaining strong predictive performance. Using the EchoNext benchmark of over 80,000 ECG-ECHO pairs, the method demonstrates relative improvements of +0.98% in AUROC, +1.01% in AUPRC, and +1.41% in F1 score over the latest state-of-the-art deep-learning baseline, while achieving slightly better performance even with only 30% of the training data. Subgroup analyses confirm robust performance across heterogeneous populations, and the estimated entry-wise functions provide interpretable insights into the relationships between risks of traditional ECG diagnoses and SHD. This work illustrates a complementary paradigm between classical statistical modeling and modern AI, offering a pathway to interpretable, high-performing, and clinically actionable ECG-based SHD screening.

Zhaohong Sun, Makoto Yokoo

Strategy-proofness is a fundamental desideratum in mechanism design, ensuring truthful reporting and robust participation. Stability is another central requirement in matching markets, widely adopted in applications such as school choice and labor market clearing. In practice, however, these markets are invariably governed by complex distributional constraints, ranging from diversity quotas and regional balance to global capacity slacks, under which stable matchings often fail to exist. This raises a fundamental question: how to distribute unavoidable instability across agents while preserving strategy-proofness? To address this, we propose \texttt{MenuNet}, a strategy-proof mechanism design framework based on a neural representation of menus. Rather than directly constructing assignments, \texttt{MenuNet} learns to generate personalized probabilistic menus, from which assignments are realized via a structured sequential choice rule that guarantees strategy-proofness by construction. By decomposing stability into fairness (no envy) and non-wastefulness, our approach models these properties as vector-valued quantities and optimizes their distribution through differentiable objectives, providing a principled trade-off between competing axioms. Empirically, \texttt{MenuNet} navigates this trade-off effectively: it consistently outperforms Random Serial Dictatorship (RSD) in terms of envy and Deferred Acceptance (DA) in terms of waste, while maintaining scalability and computational efficiency. These results suggest that learning-based menu mechanisms provide a flexible and scalable paradigm for mechanism design in highly constrained, real-world environments.

Gergely Csáji, Zhaohong Sun

Stable matching theory is the foundation of centralized clearinghouses worldwide, from school choice programs to medical residency allocations. However, incorporating complex distributional goals-such as multi-dimensional diversity quotas or sibling co-assignment guarantees-often compromises stability or renders the problem computationally intractable. The existing literature typically addresses this tension by weakening stability to accommodate distributional constraints. In contrast, the reverse question remains largely unexplored: if we restrict attention to stable matchings, to what extent can such distributional objectives be achieved? In this paper, we resolve this tension by introducing a general, polynomial-time algorithmic framework to optimize arbitrary institutional (or even two-sided) objectives within the set of stable matchings. We prove that for any polynomial-time computable set functions $g_i$ evaluating the assigned students at institutions $i \in I$, a stable matching minimizing either the utilitarian objective $\sum_{i\in I} g_i$ or the egalitarian objective $\max_{i\in I} g_i$ can be found efficiently. Our approach leverages the structural properties of stable matchings, mapping arbitrary set functions to linear edge weights. We apply this theorem to efficiently solve major open practical problems: finding stable matchings that minimally violate overlapping diversity quotas (under both total and maximum violations) and maximizing the number of sibling families assigned to the same institution. Even when the distributional objective is prioritized, our algorithm helps to quantify the ``price of stability'', i.e., the gap between the maximally diverse matching and the maximally diverse stable matching.

Haris Aziz, Serge Gaspers, Zhaohong Sun et al.

In the past few years, several new matching models have been proposed and studied that take into account complex distributional constraints. Relevant lines of work include (1) school choice with diversity constraints where students have (possibly overlapping) types and (2) hospital-doctor matching where various regional quotas are imposed. In this paper, we present a polynomial-time reduction to transform an instance of (1) to an instance of (2) and we show how the feasibility and stability of corresponding matchings are preserved under the reduction. Our reduction provides a formal connection between two important strands of work on matching with distributional constraints. We then apply the reduction in two ways. Firstly, we show that it is NP-complete to check whether a feasible and stable outcome for (1) exists. Due to our reduction, these NP-completeness results carry over to setting (2). In view of this, we help unify some of the results that have been presented in the literature. Secondly, if we have positive results for (2), then we have corresponding results for (1). One key conclusion of our results is that further developments on axiomatic and algorithmic aspects of hospital-doctor matching with regional quotas will result in corresponding results for school choice with diversity constraints.