Public agencies are often tasked with allocating scarce resources (such as public housing or financial aid) to a target population. In many such cases, the goal is to maximize social welfare, which requires identifying agents who have the highest social value for the resource. The challenge is that while public agencies may be able to access some data about potential beneficiaries (for example, through means testing), they generally lack information necessary to achieve perfect targeting. When monetary transfers are unavailable or ineffective in targeting, public agencies often rely on "ordeals" instead. Natural examples include standing in line, filing out complicated forms, dealing with "red tape," waiting, visiting an office at an inconvenient time, or traveling to a registration site. But what makes one costly screening device better than another?

We study dynamic matching in a spatial setting. Drivers are distributed at random on some interval. Riders arrive in some (possibly adversarial) order at randomly drawn points. The platform observes the location of the drivers and can match newly arrived riders immediately or can wait for more riders to arrive. Unmatched riders incur a waiting cost of c per period. Furthermore, the platform can match riders and drivers irrevocably, and the cost of matching a driver to a rider is equal to the distance between them.

We propose an economic framework for determining the optimal allocation of a scarce supply of vaccines that become gradually available during a public health crisis, such as the Covid-19 pandemic. Agents differ in observable and unobservable characteristics, and the designer maximizes a social welfare function over all feasible mechanisms---accounting for agents' characteristics, as well as their endogenous behavior in the face of the pandemic. The framework emphasizes the role of externalities and incorporates equity as well as efficiency concerns. Our results provide an economic justification for providing vaccines immediately and for free to some groups of agents, while at the same time showing that a carefully constructed pricing mechanism can improve outcomes by screening for individuals with the highest private and social benefits of receiving the vaccine. The solution casts light on the classic question of whether prices or priorities should be used to allocate scarce public resources under externalities and equity concerns.

In many real-world resource allocation problems, optimization is computationally intractable, so any practical allocation mechanism must be based on an approximation algorithm. We study investment incentives in strategy-proof mechanisms that use such approximations. In sharp contrast with the Vickrey-Clark-Groves mechanism, for which individual returns on investments are aligned with social welfare, we find that some algorithms that approximate efficient allocation arbitrarily well can nevertheless create misaligned investment incentives that lead to arbitrarily bad overall outcomes. However, if a near-efficient algorithm "excludes bossy negative externalities," then its outcomes remain near-efficient even after accounting for investments. A weakening of this "XBONE" condition is necessary and sufficient for the result.

We propose a new matching algorithm -- Unpaired kidney exchange -- to tackle the problem of double coincidence of wants without using money. The fundamental idea is that "memory" can serve as a medium of exchange. In a dynamic matching model with heterogeneous agents, we prove that average waiting time under the Unpaired algorithm is close to optimal, substantially less than the standard pairwise and chain exchange algorithms. We evaluate this algorithm using a rich dataset of kidney patients in France. Counterfactual simulations show that the Unpaired algorithm can match 57% of the patients, with an average waiting time of 440 days (state-of-the-art algorithms match about 34% with an average waiting time of 695 days). The optimal algorithm, which is practically infeasible, performs only slightly better: it matches 58% of the patients and leads to an average waiting time of 426 days. The Unpaired algorithm confronts two incentive-related practical challenges. We address those challenges via a modified version of the Unpaired algorithm that employs kidneys from the deceased donors waiting list. It can match 86% of the patients, while reducing the average waiting time to about 155 days.

Consider an extensive-form mechanism, run by an auctioneer who communicates sequentially and privately with agents. Suppose the auctioneer can make any deviation that no single agent can detect. We study the mechanisms such that it is incentive-compatible for the auctioneer not to deviate - the credible mechanisms. Consider the optimal auctions in which only winners make transfers. The first-price auction is the unique credible static mechanism. The ascending auction is the unique credible strategy-proof mechanism.

Identifying the optimal set of individuals to first receive information (`seeds') in a social network is a widely-studied question in many settings, such as the diffusion of information, microfinance programs, and new technologies. Numerous studies have proposed various network-centrality based heuristics to choose seeds in a way that is likely to boost diffusion. Here we show that, for some frequently studied diffusion processes, randomly seeding S + x individuals can prompt a larger cascade than optimally targeting the best S individuals, for a small x. We prove our results for large classes of random networks, but also show that they hold in simulations over several real-world networks. This suggests that the returns to collecting and analyzing network information to identify the optimal seeds may not be economically significant. Given these findings, practitioners interested in communicating a message to a large number of people may wish to compare the cost of network-based targeting to that of slightly expanding initial outreach.

Even when global income redistribution is not feasible, market designers can seek to mitigate inequality within individual markets. If sellers are systematically poorer than buyers, for example, they will be willing to sell at relatively low prices. Yet a designer who cares about inequality might prefer to set higher prices precisely when sellers are poor -- effectively, using the market as a redistributive tool. In this paper, we seek to understand how to design goods markets optimally in the presence of persistent inequality. Using a mechanism design approach, we find that redistribution through markets can indeed be optimal. When there is substantial inequality across sides of the market, the designer uses a tax-like mechanism, introducing a wedge between the buyer and seller prices, and redistributing the resulting surplus to the poorer side of the market via lump-sum payments. When there is significant within-side inequality, meanwhile, the designer imposes price controls even though doing so induces rationing.

Whether an idea, information, disease, or innovation diffuses throughout a society depends not only on the structure of the network of interactions, but also on the timing of those interactions. Recent studies have shown that diffusion can fail on a network in which people are only active in "bursts," active for a while and then silent for a while, but diffusion could succeed on the same network if people were active in a more random Poisson manner. Those studies generally consider models in which nodes are active according to the same random timing process and then ask which timing is optimal. In reality, people differ widely in their activity patterns -- some are bursty and others are not. We model diffusion on networks in which agents differ in their activity patterns. We show that bursty behavior does not always hurt the diffusion, and in fact having some (but not all) of the population be bursty significantly helps diffusion. We prove that maximizing diffusion requires heterogeneous activity patterns across agents, and the overall maximizing pattern of agents' activity times does not involve any Poisson behavior.

We introduce a “high-probability” framework for repeated games with incomplete information. In our non-equilibrium setting, players aim to guarantee a certain payoff with high probability, rather than in expected value. We provide a high-probability counterpart of the classical result of Mertens and Zamir for the zero-sum repeated games. Any payoff that can be guaranteed with high probability can be guaranteed in expectation, but the reverse is not true. Hence, unlike the average payoff case where the payoff guaranteed by each player is the negative of the payoff by the other player, the two guaranteed payoffs would differ in the high-probability framework. One motivation for this framework comes from information transmission systems, where it is customary to formulate problems in terms of asymptotically vanishing probability of error. Finally, we introduce compound arbitrarily varying channels, and use the high-probability framework to study this problem.

We introduce a simple benchmark model of dynamic matching in networked markets, where agents arrive and depart stochastically and the network of acceptable transactions between agents forms a random graph. We analyze our model from three perspectives: waiting time, optimization, and information. The main insight of our analysis is that waiting to thicken the market can be substantially more important than increasing the speed of transactions, and this is quite robust to the presence of waiting costs. From an optimization perspective, naive local algorithms, that choose the right time to match agents but do not exploit global network structure, can perform very close to optimal algorithms. From an information perspective, algorithms that employ even partial information on agents' departure times perform substantially better than those that lack such information. Information and waiting are complements; information about departure times is necessary for waiting to yield large gains. To elicit agents' departure times, we design an incentive-compatible continuous-time dynamic mechanism without transfers. LINK: www.ssrn.com/abstract=2394319