Explore the vast range of titles available.

We study how to reduce congestion in two-sided matching markets with private preferences. We measure congestion by the number of bits of information that agents must (i) learn about their own preferences, and (ii) communicate with others before obtaining their final match. Previous results suggest that a high level of congestion is inevitable under arbitrary preferences before the market can clear with a stable matching. We show that when the unobservable component of agent preferences satisfies certain natural assumptions, it is possible to recommend potential matches and encourage informative signals such that the market reaches a stable matching with a low level of congestion. Moreover, under our proposed approach, agents have negligible incentive to leave the marketplace or to look beyond the set of recommended partners. The intuitive idea is to only recommend partners with whom there is a nonnegligible chance that the agent will both like them and be liked by them. The recommendations are based on both the observable component of preferences and signals sent by agents on the other side that indicate interest. This paper was accepted by Yan Chen, decision analysis.

Significance There are currently more than 100,000 patients on the waiting list in the United States for a kidney transplant from a deceased donor. To address this shortage, kidney exchange programs allow patients with living incompatible donors to exchange donors through cycles and chains initiated by altruistic nondirected donors. To determine which exchanges will take place, kidney exchange programs use algorithms for maximizing the number of transplants under constraints about the size of feasible exchanges. This problem is NP-hard, and algorithms previously used were unable to optimize when chains could be long. We developed two algorithms that use integer programming to solve this problem, one of which is inspired by the traveling salesman, that together can find optimal solutions in practice. As of May 2014 there were more than 100,000 patients on the waiting list for a kidney transplant from a deceased donor. Although the preferred treatment is a kidney transplant, every year there are fewer donors than new patients, so the wait for a transplant continues to grow. To address this shortage, kidney paired donation (KPD) programs allow patients with living but biologically incompatible donors to exchange donors through cycles or chains initiated by altruistic (nondirected) donors, thereby increasing the supply of kidneys in the system. In many KPD programs a centralized algorithm determines which exchanges will take place to maximize the total number of transplants performed. This optimization problem has proven challenging both in theory, because it is NP-hard, and in practice, because the algorithms previously used were unable to optimally search over all long chains. We give two new algorithms that use integer programming to optimally solve this problem, one of which is inspired by the techniques used to solve the traveling salesman problem. These algorithms provide the tools needed to find optimal solutions in practice.

Low adherence to prescribed medications causes substantial health and economic burden. We analyzed primary data from electronic medical records of 250,000 random patients from Israel’s Maccabi Healthcare services from 2007 to 2017 to predict whether a patient will purchase a prescribed antibiotic. We developed a decision model to evaluate whether an intervention to improve purchasing adherence is warranted for the patient, considering the cost of the intervention and the cost of non-adherence. The best performing prediction model achieved an average area under the receiver operating characteristic curve (AUC) of 0.684, with 82% accuracy in detecting individuals who had less than 50% chance of purchasing a prescribed drug. Using the decision model, an adherence intervention targeted to patients whose predicted purchasing probability is below a specified threshold can increase the number of prescriptions filled while generating significant savings compared to no intervention – on the order of 6.4% savings and 4.0% more prescriptions filled for our dataset. We conclude that analysis of large-scale patient data from electronic medical records can help predict the probability that a patient will purchase a prescribed antibiotic and can provide real-time predictions to physicians, who can then counsel the patient about medication importance. More broadly, in-depth analysis of patient-level data can help shape the next generation of personalized interventions.

We study the allocation of heterogeneous services to agents with incomplete information and without monetary transfers. Agents have private, multidimensional utilities over services, drawn from commonly known priors. The social planner’s goal is to maximize a potentially complex public objective. For tractability, we take an “engineering” approach, in which we solve a large-market approximation, and convert the solution into a feasible finite-market mechanism that still yields good results. We apply this framework to real data from Boston to design a mechanism that assigns students to public schools, in order to maximize a linear combination of utilitarian and max-min welfare, subject to capacity and transportation constraints. We show how to optimally solve a large-market formulation with more than 868 types of students and 77 schools, and we translate the solution into a finite-market mechanism that significantly outperforms the baseline plan chosen by the city in terms of efficiency, equity, and predictability. Data, as supplemental material, are available at http://dx.doi.org/10.1287/mnsc.2015.2162 . This paper was accepted by Martin Lariviere, operations management.

We consider the problem of allocating finitely many units of an indivisible good among a group of agents when each agent receives at most one unit of the good and pays a non-negative price. For example, imagine that a government allocates a fixed number of licenses to private firms, or that it distributes equally divided lands to households. Anonymity in welfare is a condition of impartiality in the sense that it requires allocation rules to treat agents equally in welfare terms from the viewpoint of agents who are ignorant of their own valuations or identities. We show that the Vickrey allocation rule is the unique allocation rule satisfying strategy-proofness, anonymity in welfare, and individual rationality.

We study dynamic matching in an infinite-horizon stochastic market. Although all agents are potentially compatible with each other, some are hard to match and others are easy to match. Agents prefer to be matched as soon as possible, and matches are formed either bilaterally or indirectly through chains. We adopt an asymptotic approach and compute tight bounds on the limit of waiting time of agents under myopic policies that differ in matching technology and prioritization. We find that when hard-to-match agents arrive less frequently than easy-to-match ones, (i) bilateral matching is almost as efficient as chains (waiting times scale similarly under both, though chains always outperform bilateral matching by a constant factor), and (ii) assigning priorities to hard-to-match agents improves their waiting times. When hard-to-match agents arrive more frequently, chains are much more efficient than bilateral matching, and prioritization has no impact. Furthermore, somewhat surprisingly, we find that in a heterogeneous market and under bilateral matching, increasing the arrival rate of hard-to-match agents has a nonmonotone effect on waiting times. This behavior is in contrast with that of a homogeneous dynamic market, where increasing arrival rate always improves waiting time, and it highlights fundamental differences between heterogeneous and homogeneous dynamic markets.

In school choice, children submit a preference ranking over schools to a centralized assignment algorithm, which takes into account schools’ priorities over children and uses randomization to break ties. One criticism of existing school choice mechanisms is that they tend to disperse communities, so children do not go to school with others from their neighborhood. We suggest improving community cohesion by implementing a correlated lottery in a given school choice mechanism: we find a convex combination of deterministic assignments that maintains the original assignment probabilities, thus maintaining choice but improving community cohesion. To analyze the gain in cohesion for a wide class of mechanisms, we first prove the following characterization, which may be of independent interest: any mechanism that, in the large market limit, is nonatomic, Bayesian incentive compatible, symmetric, and efficient within each priority class is a “lottery-plus-cutoff” mechanism. This means that the large market limit can be described as follows: given the distribution of preferences, every student receives an identically distributed lottery number, every school sets a lottery cutoff for each priority class, and a student is assigned to her most preferred school for which she meets the cutoff. This generalizes liu-pycia-2012 to allow arbitrary priorities. Using this, we derive analytic expressions for maximum cohesion under a large market approximation. We show that the benefit of lottery-correlation is greater when students’ preferences are more correlated. In practice, although the correlated-lottery implementation problem is NP-hard, we present a heuristic that does well. We apply this to real data from Boston elementary school choice 2012 and find that we can increase cohesion by 79% for kindergarten 1 (K1) and 37% for kindergarten 2 (K2) new families. Greater cohesion gain is possible (tripling cohesion for K1 and doubling for K2) if we reduce the choice menus on top of applying lottery correlation.

Assigning refugee families to different locations in a host country is a timely challenge due to the global refugee crisis. This paper studies how to assign refugees to different locations while accommodating various distributional constraints. The social planner seeks to find a constrained efficient assignment with respect to refugees’ preferences over different locations. As Pareto-efficient assignments may differ significantly in the number of assigned refugees, a key challenge is to match as many refugees as possible. The paper generalizes the well-known serial dictatorship (SD) and probabilistic serial (PS) mechanisms for assigning indivisible objects to agents to accommodate distributional constraints. The new generalizations of SD and PS maintain their desirable properties while satisfying the distributional constraints with a small error. Both mechanisms assign at least the same number of students as the optimum fractional assignment. We generalize the serial dictatorship (SD) and probabilistic serial (PS) mechanism for assigning indivisible objects (seats in a school) to agents (students) to accommodate distributional constraints. Such constraints are motivated by equity considerations. Our generalization of SD maintains several of its desirable properties, including strategyproofness, Pareto optimality, and computational tractability, while satisfying the distributional constraints with a small error. Our generalization of the PS mechanism finds an ordinally efficient and envy-free assignment while satisfying the distributional constraint with a small error. We show, however, that no ordinally efficient and envy-free mechanism is also weakly strategyproof. Both of our algorithms assign at least the same number of students as the optimum fractional assignment.

We study dynamic matching policies in a stochastic marketplace for barter, with agents arriving over time. Each agent is endowed with an item and is interested in an item possessed by another agent homogeneously with probability p , independently for all pairs of agents. Three settings are considered with respect to the types of allowed exchanges: (a) only two-way cycles, in which two agents swap items, (b) two-way or three-way cycles, (c) (unbounded) chains initiated by an agent who provides an item but expects nothing in return. We consider the average waiting time as a measure of efficiency and find that the cost outweighs the benefit from waiting to thicken the market. In particular, in each of the above settings, a policy that conducts exchanges in a greedy fashion is near optimal. Further, for small p , we find that allowing three-way cycles greatly reduces the waiting time over just two-way cycles, and conducting exchanges through a chain further reduces the waiting time significantly. Thus, a centralized planner can achieve the smallest waiting times by using a greedy policy, and by facilitating three-way cycles and chains, if possible. The online appendix is available at https://doi.org/10.1287/opre.2017.1644 .

Labor markets can often be viewed as many-to-one matching markets. It is well known that if complementarities are present in such markets, a stable matching may not exist. We study large random matching markets with couples. We introduce a new matching algorithm and show that if the number of couples grows slower than the size of the market, a stable matching will be found with high probability. If however, the number of couples grows at a linear rate, with constant probability (not depending on the market size), no stable matching exists. Our results explain data from the market for psychology interns.