Budget Feasible Procurement Auctions
Preliminary version in FOCS'14
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.
Persuading a Pessimist
Consider a (Bayesian) persuasion problem in which a pessimistic Receiver takes action to secure a "guaranteed payoff".
Through the lens of an ordinal utility model, we demonstrate the simple structure and the strong robustness properties of the "optimal" signal.
In particular, we show that when simple monotonicity conditions on Sender's and Receiver's preferences hold (essentially, when the action space and state space are ordered), a stochastically dominant signal exists, i.e. a signal that imposes a distribution on the realized outcome which stochastically dominates the distribution imposed by any other signal, with respect to Sender's preferences.
Furthermore, we show that the stochastically dominant signal has a simple structure, and satisfies strong robustness properties. In particular, the signal (i) is monotone, i.e. induces higher actions at higher states (ii) is a partitional signal that pools "adjacent" elements, and (iii) typically has a small size, i.e. partitions the state space into a small number of subsets. The signal is robust to (i) lack of commitment power from Sender, and (ii) (mis)specification of the prior.
To detect which of these properties hinge on the sufficient monotonicity conditions, we also study their relaxations. In particular, we show that even when the action space is not ordered, stochastically dominant signals still exist if the state space is compact and the prior is atomless.
The structural properties of the signal might not continue to hold, while the robustness properties do.
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.
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.
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).
What matters in tie-breaking rules? How competition guides design
Working paper. (Preliminary version in EC'16)
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.
Assigning More Students to Their Top Choices: A Tiebreaking Rule Comparison
R&R in Games and Economic Behavior.
(Preliminary version in EC'15)
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.
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.
You can access my google scholar page here.