Assigning More Students to Their Top Choices: A Tiebreaking Rule Comparison
Games and Economic Behavior, forthcoming.
with Itai Ashlagi, Assaf Romm.
School districts that implement stable matchings face various decisions that affect students' assignments to schools. We study properties of the rank distribution of students with random preferences when schools use different tie-breaking rules to rank equivalent students. Under a single tie-breaking rule, where all schools use the same ranking, a constant fraction of students are assigned to one of their top choices. In contrast, under a multiple tie-breaking rule, where each school independently ranks students, a vanishing fraction of students are matched to one of their top choices. However, by restricting the students to submitting relatively short preference lists under a multiple tie-breaking rule, a constant fraction of students will be matched with one of their top choices, whereas only a "small" fraction of students will remain unmatched.
Budget Feasible Procurement Auctions
with Nima Anari and Gagan Goel.
This work is an attempt to respond to the Wilson Doctrine in procurement auctions. We consider a simple model for procurement problems and solve it to optimality. A buyer with a fixed budget wants to procure, from a set of available workers, a budget feasible subset that maximizes her utility: Any worker has a private reservation price and provides a publicly known utility to the buyer in case of being procured. The buyer's utility function is additive over items. The goal is designing a direct revelation mechanism that solicits workers' reservation prices and decides which workers to recruit and how much to pay them. Moreover, the mechanism has to maximize the buyer's utility without violating her budget constraint. We consider a prior-free setting, i.e. there are no distributional assumptions. Our main contribution is finding the optimal mechanism in this setting, under the "Small Bidders" assumption, which ensures that the bid of each seller is small compared to the buyer's budget.
What matters in tie-breaking rules? How competition guides design
with Itai Ashlagi.
Many school districts apply the student-proposing deferred acceptance algorithm after ties among students are broken exogenously. We compare two common tie-breaking rules: one in which all schools use a single common lottery, and one in which every school uses a separate independent lottery. We identify the balance between supply and demand as the determining factor in this comparison. First we analyze a two-sided matching model with random preferences in over-demanded and under-demanded markets. In a market with a surplus of seats a common lottery is less equitable and there are efficiency trade-offs between the two tie-breaking rules. However, a common lottery is always preferable when there is shortage of seats. The theory suggests that popular schools should use a common lottery to resolve ties. We run numerical experiments with New York City choice data after partitioning the market into popular and non-popular schools. The experiments support our findings.
Approximate Random Allocation Mechanisms
R&R in The Review of Economic Studies
with Mohammad Akbarpour.
We generalize the scope of random allocation mechanisms, in which the mechanism first identifies a feasible "expected allocation" and then implements it by randomizing over nearby feasible integer allocations. Previous literature had shown that the cases in which this is possible are sharply limited. We show that if some of the feasibility constraints can be treated as goals rather than hard constraints then, subject to weak conditions that we identify, any expected allocation that satisfies all the constraints and goals can be implemented by randomizing among nearby integer allocations that satisfy all the hard constraints exactly and the goals approximately. By defining ex post utilities as goals, we are able to improve the ex post properties of several classic assignment mechanisms, such as the random serial dictatorship. We use the same approach to prove the existence of ε-competitive equilibrium in large markets with indivisible items and feasibility constraints.
Thickness and Competition in Ride-sharing Markets
We study the effects of thickness and competition on the equilibria of ride-sharing markets, in which price-setting firms provide platforms to match customers ("riders") and workers ("drivers"). To study thickness, we vary the number of potential workers ("the labor pool") and, to study competition, we change the number of firms from one to two. When the market is sufficiently thick, wage and workers' average welfare decrease with size of the labor pool, as expected. There is, however, an unexpected effect in the thin market regime: wage and workers' average welfare increase with the labor pool. Intuitively, workers are "complements" in a thin market --their wage and average welfare goes up with the labor pool-- but they become "substitutes" and compete with each other in a thick market.
We demonstrate that a similar insight holds in another context: consider improving the matching technology, i.e. improving the matching algorithm of the firm so that waiting times go down, given the same labor supply. We show that improving the matching technology can be like increasing the labor pool, benefiting workers when the market is not sufficiently thick, while otherwise reducing their wage and average welfare. In other words, matching technology complements labor in a thin market, but substitutes it in a thick market.
We study competition by comparing the monopoly and duopoly equilibria. We find that competition benefits workers: their wage and average welfare are always higher in the duopoly equilibrium. However, the effect of competition on price and customers' average welfare depends on thickness. When the market is not sufficiently thick, there is an adverse effect of competition on customers: price is higher and customers' average welfare is lower in the duopoly equilibrium.
Matching in Dynamic Imbalanced Markets
with Itai Ashlagi, Philipp Strack.
We study matching policies in a dynamic exchange market with random compatibility, in which some agents are easier to match than others.
In steady state this asymmetry creates an endogenous imbalance: hard-to-match agents wait for partners, while easy-to-match agents can match almost immediately upon arrival and leave the market quickly.
A greedy policy, which attempts to match agents upon arrival, does not account for the positive externality waiting agents generate as they make it easier to match agents that arrive in the future, and may result in more unmatched than other policies. While this trade-off between a "thicker market" and quick matching is present in small markets we show that it vanishes in large markets and the greedy policy nevertheless dominates any other dynamic matching policy.
As arrival rate increases the greedy policy matches a (weakly) higher fraction of agents than any other policy and leads to (weakly) lower average waiting time than any other policy.
We show that in a large market greedy matching strictly outperforms
batching policies (e.g., weekly matching) and a patient policy, which attempts to match agents only as they are about to depart the market.
We test our large market predictions with kidney exchange data from the National Kidney Registry (NKR). Numerical simulations show that, in line with our predictions, the greedy policy matches patient-donor pairs significantly faster (roughly 20-30 days) than other commonly used policies and at most 1% percent fewer pairs than the patient policy.
When Pareto-optimal assignments are (not) payoff-equivalent?
We prove that in a random matching market, there exists an assignment with an average rank that is independent of the market size (i.e., constant average rank). The proof relies on techniques from random graph theory and the FKG inequality, a fundamental correlation inequality in statistical mechanics and probabilistic combinatorics. The FKG inequality is used here to keep track of the correlations between the objects' ranks on an agent's lists. We elaborate next that the non-existence of such correlations has significant consequences regarding the payoff-equivalency of a large family of assignments including Pareto-optimal assignments.
The existence of an assignment with a constant average rank means that the average rank under the Random Serial Dictatorship mechanism takes a heavy toll compared to the first-best.
This is in apparent contrast with recent results that show the payoff-equivalency of Pareto-optimal assignments. We account for this difference by showing that the equivalence result relies on the assumption that the idiosyncratic components of the utility of an agent for objects are iid.
When the iid assumption is replaced with negative correlation, Pareto-optimal assignments can have very different payoff distributions. Strict ordinal preferences indeed encapsulate a notion of correlated idiosyncrasy.
Under the iid assumption, however, we show that a large family of assignments, including Pareto-efficient assignments as well as assignments with large Pareto-inefficiencies, are payoff-equivalent. We introduce abundance of competent choices, a likely phenomenon under the iid assumption,
as a deriving force of such equivalencies. We show that this phenomenon also occurs in other setups, such as in Gale and Shapley's model of marriage markets.
Persuading a Pessimist
While in practice most persuasion mechanisms have a simple structure, optimal signals in the Bayesian persuasion framework may not be so.
Many signals in practice have an "interval structure", i.e. they partition an ordered state space into intervals. The interval structure of optimal signals has been studied in the Bayesian persuasion literature; e.g., there is work that provide sufficient, and in some cases, necessary conditions for the optimality of such signals in different settings. Another studied structural property is "monotonicity",
which means that the optimal signal does not recommend lower actions at higher higher states when both of the action and state spaces are ordered.
We show that the optimal signal features both of the properties -the interval structure and monotonicity- when Receiver is a pessimist.
Loosely speaking, a pessimistic receiver, rather than maximizing expected payoff, takes the action that promises the highest guaranteed level of payoff.
This notion of pessimism is remarkably simple compared to the existing sufficient conditions for either of the properties.
Such maxmin utility specifications are widely used to model decision-making when probabilities are ambiguous and not objectively known.
Our findings draw a connection between the popularity of simple signals in practice and the ambiguity of the prior to Receiver.
We also show that the optimal signal is robust to (i) misspecification of the prior and (ii) misspecification of Sender or Receiver's cardinal utilities, as long as their ordinal preferences do not change. Moreover, Sender needs a much weaker type of commitment power than the standard one in Bayesian persuasion.
We establish similar findings when Receiver has an incomplete preference ordering forming a lattice.
Finally, we build on our approach to find optimal signals in the presence of upper quota constraints on the signal size, and to analyze the size of optimal signals in stochastic problem instances, demonstrating that optimal signals are typically small.
Financing Transplant Costs of the Poor: A Dynamic Model of Global Kidney Exchange
Afshin Nikzad, Mohammad Akbarpour, Michael Reese, Alvin Roth.
In some developing nations, many end-stage renal disease (ESRD) patients die within weeks of their diagnosis mainly because the costs of kidney transplantation and dialysis are beyond the reach of most citizens. In this paper, we analyze two proposals for extending kidney exchange to include patients in countries in which transplantation is unavailable to them. First, we analyze a recently proposed concept, Global Kidney Exchange, in which a U.S. health authority invites patients with financial restrictions who have willing donors to come to the United States to exchange their donor's kidney with an immunologically incompatible American patient-donor pair and to receive a transplant utilizing the incompatible American donor's kidney for free. We create a dynamic model of this proposal and show that this proposal can be self-financing in the long run. Our analysis shows that, under plausible assumptions, the proposal remains self-financing even when the average dialysis cost of American patients declines below the cost of surgery (as waiting times for transplant are shortened by the increased availability of transplants).
You can access my google scholar page here.