Publications

2026

1. WINE

   Selling Surplus Foods Through Surprise Bags: Online Inventory Routing Across Dual Channels

   Yiding Feng, Chui Shan Lee, Guodong Lyu, and Huan Zheng

   In Proceedings of the 22nd International Conference on Web and Internet Economics (WINE 2026) , Hong Kong, 2026

   Abs DOI PDF

   Reducing food waste while preserving profit is an important operational problem for retailers of perishable products. We study a finite-horizon inventory allocation problem with a regular channel and an opaque surprise-bag channel. Before observing each period’s regular demand, the retailer chooses product display quantities and surprise-bag offers. Each offered bag sells and creates a noncancellable commitment that must be fulfilled from inventory remaining at the horizon. The model incorporates waste costs and linear constraints on the expected aggregate composition of bag allocations, while allowing arbitrary correlation in regular demand across products and periods. Under productwise regular-channel profitability, an LP-based reservation policy achieves the optimal competitive ratio \( 1/(2 + κ) \)against a clairvoyant benchmark, where \( κ= w/s \)is the waste-cost-to-bag-reward ratio. An adaptive reservation policy weakly dominates the static policy in expected profit on every instance and inherits its guarantee. We also identify sufficient conditions under which deferred product assignment strictly improves optimal expected profit over immediate assignment, and extend the static guarantee to fixed multi-unit bags. In simulations calibrated from cafeteria sales data, the adaptive policy improves mean profit over the static policy by 6.2%-9.2% across the tested quality-floor settings.

2. EC

   Optimal Stopping with a Predicted Prior

   Tian Bai, Zhiyi Huang, Chui Shan Lee, and Dongchen Li

   In Proceedings of the 27th ACM Conference on Economics and Computation (EC 2026) , Rome, Italy, 2026

   Abs DOI arXiv

   There are two major models of value uncertainty in the optimal stopping literature: the secretary model, which assumes no prior knowledge, and the prophet inequality model, which assumes full information about value distributions. In practice, decision makers often rely on machine-learned priors that may be erroneous. Motivated by this gap, we formulate the model of optimal stopping with a predicted prior to design algorithms that are both consistent, exploiting the prediction when accurate, and robust, retaining worst-case guarantees when it is not.

   Existing secretary and prophet inequality algorithms are either pessimistic in consistency or not robust to misprediction. A randomized combination only interpolates their guarantees linearly. We show that a family of bi-criteria algorithms achieves improved consistency-robustness trade-offs, both for maximizing the expected accepted value and for maximizing the probability of accepting the maximum value. We further prove that for the latter objective, no algorithm can simultaneously match the best prophet inequality algorithm in consistency, and the best secretary algorithm in robustness.

2025

1. ICALP

   The Long Arm of Nashian Allocation in Online \(p \)-Mean Welfare Maximization

   Zhiyi Huang, Chui Shan Lee, Xinkai Shu, and Zhaozi Wang

   In Proceedings of the 52nd International Colloquium on Automata Languages and Programming (ICALP 2025) , Aarhus, Denmark, 2025

   Abs DOI arXiv

   We study the online allocation of divisible items to \(n \)agents with additive valuations for \(p \)-mean welfare maximization, a problem introduced by Barman, Khan, and Maiti (2022). Our algorithmic and hardness results characterize the optimal competitive ratios for the entire spectrum of \( -∞\le p \le 1 \).

   Surprisingly, our improved algorithms for all \(p \le \frac1\log n \)are simply the greedy algorithm for the Nash welfare, supplemented with two auxiliary components to ensure all agents have non-zero utilities and to help a small number of agents with low utilities. In this sense, the long arm of Nashian allocation achieves near-optimal competitive ratios not only for Nash welfare but also all the way to egalitarian welfare.

2024

1. WINE

   Online Matching Meets Sampling Without Replacement

   Zhiyi Huang, Chui Shan Lee, Jianqiao Lu, and Xinkai Shu

   In Proceedings of the 20th International Conference on Web and Internet Economics (WINE 2024) , Edinburgh, UK, 2024

   Abs DOI arXiv Slides

   Sampling without replacement is a natural online rounding strategy for converting fractional bipartite matching into an integral one. In Online Bipartite Matching, we can use the Balance algorithm to fractionally match each online vertex, and then sample an unmatched offline neighbor with probability proportional to the fractional matching. In Online Stochastic Matching, we can take the solution to a linear program relaxation as a reference, and then match each online vertex to an unmatched offline neighbor with probability proportional to the fractional matching of the online vertex’s type. On the one hand, we find empirical evidence that online matching algorithms based on sampling without replacement outperform existing algorithms. On the other hand, the literature offers little theoretical understanding of the power of sampling without replacement in online matching problems.

   This paper fills the gap in the literature by giving the first non-trivial competitive analyses of sampling without replacement for online matching problems. In Online Stochastic Matching, we develop a potential function analysis framework to show that sampling without replacement is at least \( 0.707 \)-competitive. The new analysis framework further allows us to derandomize the algorithm to obtain the first polynomial-time deterministic algorithm that breaks the \( 1-1/e \)barrier. In Online Bipartite Matching, we show that sampling without replacement provides provable online correlated selection guarantees when the selection probabilities correspond to the fractional matching chosen by the Balance algorithm. As a result, we prove that sampling without replacement is at least \( 0.513 \)-competitive for Online Bipartite Matching.

2021

1. Book

   排難解紛的數學—公平分配 [Mathematics of resolving disputes: Fairness in sharing]

   Ka Ho Law, and Chui Shan Lee

   Hong Kong Education Bureau, 2021

   PDF
2. COCOON

   On the Hardness of Opinion Dynamics Optimization with \( L_1 \)-Budget on Varying Susceptibility to Persuasion

   T.-H. Hubert Chan, and Chui Shan Lee

   In Proceedings of the 27th International Conference on Computing and Combinatorics (COCOON 2021), Tainan, Taiwan, 2021

   Abs DOI arXiv Slides

   Recently, Abebe et al. (KDD 2018) and Chan et al. (WWW 2019) have considered an opinion dynamics optimization problem that is based on a popular model for social opinion dynamics, in which each agent has some fixed innate opinion, and a resistance that measures the importance it places on its innate opinion; moreover, the agents influence one another’s opinions through an iterative process. Under certain conditions, this iterative process converges to some equilibrium opinion vector. Previous works gave an efficient local search algorithm to solve the unbudgeted variant of the problem, for which the goal is to modify the resistance of any number of agents (within some given range) such that the sum of the equilibrium opinions is minimized. On the other hand, it was proved that the \( L_0 \)-budgeted variant is NP-hard, where the \( L_0 \)-budget is a restriction given upfront on the number of agents whose resistance may be modified.

   Inspired by practical situations in which the effort to modify an agent’s resistance increases with the magnitude of the change, we propose the \( L_1 \)-budgeted variant, in which the \( L_1 \)-budget is a restriction on the sum of the magnitudes of the changes over all agents’ resistance parameters. In this work, we show that the \( L_1 \)-budgeted variant is NP-hard via a reduction from the vertex cover problem. However, contrary to the \( L_0 \)-budgeted variant, a very technical argument is needed to show that the optimal solution can be achieved by focusing the given \( L_1 \)-budget on as small a number of agents as possible, as opposed to spreading the budget over a large number of agents.