cs.CYFeb 14, 2025

Matching with Choice: Menu Design for Patient--Provider Assignment

Authors: Naveen Raman, Holly Wiberg

Organizations: Carnegie Mellon University

Abstract

High-quality matches between patients and primary care providers improve downstream health outcomes, yet provider turnover breaks these matches and forces patients to be reassigned. Health systems facing this problem must decide not only which providers to recommend, but how much choice to offer. Direct assignment avoids competition for scarce provider capacity but relies on noisy estimates of patient preferences; broader choice allows patients to correct these estimates using private information but can create costly coordination failures. We study this tradeoff through the design of fixed, personalized menus from which patients choose providers. We show that constructing the optimal menu is NP-hard and establish an information-theoretic lower bound. We find that offering each patient a single provider matches this bound up to a constant factor, while unrestricted choice can perform arbitrarily poorly. However, we show that additional choice improves on single-provider assignment when the system cannot reliably distinguish among a patient's alternatives. We formalize this tradeoff through two forms of loss: menu loss, which arises when menus offer too few options, and coordination loss, which arises when scarce capacity is exposed to too much choice. Motivated by this decomposition, we develop the Scenario-Averaged Marginals (SAM) algorithm, which tailors menus based on provider shadow prices so choice is offered only when utility exceeds the capacity cost. We identify sufficient conditions which SAM's regret matches the lower bound, namely when patients have valuable alternatives and offered menus don't create competition for scarce capacity. In a semi-synthetic environment calibrated to a provider network using Medicare data, SAM improves total utility by up to 19% over single-provider assignment as preference uncertainty grows, while improving utility for the least-served ZIP codes.

Figures & tables

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

May 4, 2026

MenuNet: A Strategy-Proof Mechanism for Matching Markets

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 MenuNet, a strategy-proof mechanism design framework based on a neural representation of menus. Rather than directly constructing assignments, 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, 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.
Sep 30, 2026

Patient-Centered Treatment Planning for Chronic Multimorbidity: A Hierarchical Reinforcement Learning Framework for Preference Modeling

Patient preference, defined as a patient's demonstrated willingness and capacity to adhere to clinical recommendations, is a primary determinant of therapeutic effect yet remains structurally absent from existing computational treatment planning models. We address this gap by presenting patient-centered factored-action hierarchical option-critic (FAHOC), a hierarchical reinforcement learning (HRL) framework that jointly learns high-level options corresponding to therapeutic strategies and factored intra-option policies that decompose the joint action space into disease- and intervention-specific subcomponents, while imposing a cooperation-aware action masking mechanism. This enables structured exploration, improved credit assignment across hierarchy levels, and more interpretable decision pathways, while enforcing patients' preferences. Formal guarantees establish that cooperative patients achieve higher optimal expected health outcomes than non-cooperative patients, and that the factored Q-function approximation error is provably bounded. The framework is evaluated using longitudinal data collected from approximately 50,000 comorbid hypertension and type 2 diabetes mellitus patients from five hospitals in the Southeast U.S. FAHOC achieves a quality-adjusted life year expectancy equivalent improvement of 0.669 (vs -0.133 observed clinician practice), correctly identifies cooperative patients in 95.9% of cases and never violates a patient's preference in held-out test, demonstrating that HRL with explicit preference constraints can support preference-consistent, clinically safe decision-making in multimorbidity management.
Oct 22, 2026

FairFRESH: A Neuro-Symbolic Framework for Fair and Explainable Household Food Recommendation

Recommender systems typically serve one user at a time. However, in households, members share a finite pantry and follow different dietary rules, making independent recommendations prone to resource conflicts and dietary violations. We formulate household food recommendation as constrained fair division and present FairFRESH, a neuro-symbolic framework that learns per-member utilities, allocates foods under explicit welfare objectives, enforces dietary rules through a deterministic filter, and explains recommendations using Shapley and Banzhaf attributions. Theoretically, we show that no finite penalty guarantees compliance near a dietary-rule threshold, establish approximation guarantees for greedy allocation under utilitarian and smoothed Nash objectives in the stock-free model before filtering, and characterize the scale invariance of Nash welfare. We also use the minimax theorem to analyze rotating shared meals. On NHANES-derived data, the learned utility model achieves Recall@20 of 0.293, outperforming five learned recommenders (at most 0.244) but not a previous-day repetition heuristic (0.321). On held-out four-person households, Nash allocation reduces Gini disparity by 42% relative to conflict resolution while improving Recall@20 from 0.180 to 0.197. It comes within 2% of an upper bound on the smoothed Nash optimum, and rescaling one member's utilities changes at most 1.5% of assignments. All recommendations satisfy the encoded dietary rules, while attribution scores correlate with utility loss upon component removal (r = 0.76). In simulation, shared meals reduce pantry use by about one-third, and weekly rotation increases the worst-off member's utility by 38% over the best fixed meal.