Abstract
We study the Provision-after-Wait problem in healthcare introduced by Braverman, Chen, and Kannan (2016). In this setting, patients seek a medical procedure, and the procedure can be performed by different hospitals of different costs. Each patient has a value for each hospital, and a budget-constrained government/planner pays for the medical expenses of the patients. The planner’s goal is to find an optimal stable assignment that is envy-free and maximizes the social welfare while keeping the expenses within the budget.
In this work, we focus on the settings where the patients have a common preference of the hospitals. We show that computing the optimal stable assignment for maximizing social welfare is NP-hard. Furthermore, we construct a fully polynomial-time approximation scheme (FPTAS) that runs in time O((n+m)n3mε), where m and n are the number of hospitals and patients, respectively. In order to develop the FPTAS, we have defined and studied a new problem, ordered Knapsack.
We also consider the setting where the planner uses lottery as a rationing tool. For a large sub-class of our settings, we show the conditions under which the optimal lottery scheme has a simple structure and generates more social welfare than the optimal stable assignment. Moreover, such optimal lottery scheme can be computed by a linear program.
