Fair and efficient allocation of indivisible goods without the use of money often requires randomization. However, existing mechanisms in combinatorial assignment settings only ensure desirable properties either ex ante or ex post, but not both. To address this, we introduce a class of mechanisms in which agents face a single competitive price vector that exactly clears the ex-ante economy while approximately clearing every ex-post economy. Our Competitive Equilibrium from Random Incomes (CERI) assigns each agent a random budget of tokens, determines a profile of optimal lotteries, and sets prices that exactly clear the ex-ante economy. A CERI exists for any continuous distribution of token budgets. We establish that an allocation is ordinally efficient if and only if it is a CERI allocation and any CERI allocation can be implemented as a lottery over ex-post efficient near-feasible allocations. When token budget distributions are identical, the CERI allocation is ordinally envy-free, and when they have sufficiently small support, then every realization of the CERI allocation is ex-post envy-free up to one good. Moreover, by leveraging the single market-clearing price property, we design a CERI-based mechanism that is uniformly strategyproof, i.e., in which, with probability arbitrarily close to 1 in a large market, truthtelling strategies are weakly dominant for all agents at once. As a result, in addition to efficiency and envy-freeness properties, our CERI-based mechanism offers significantly stronger incentive-compatibility guarantees compared to existing asymptotic strategyproofness properties, which only limit deviation incentives on an agent-by-agent basis. Therefore, CERI captures difficult tradeoffs between efficiency, envy and incentive compatibility in combinatorial assignment, offers new price-theoretic foundations for several existing mechanisms, and can be practically used for a variety of applications including course allocation, allocation of food donations to food banks, and refugee resettlement.

We consider combinatorial exchanges where agents have (possibly random) endowments and ordinal preferences over bundles of indivisible goods. For any market instance, we show that there exists an approximately feasible, individually rational, and ordinally efficient lottery assignment. This assignment can be supported by prices derived from a novel competitive equilibrium concept, which we term a Budget-Relaxed Approximate Competitive Equilibrium (BRACE). Any BRACE can be implemented as a lottery over deterministic allocations that are approximately feasible, individually rational and efficient. When endowments are deterministic, it can be implemented over near-feasible weak core outcomes. Moreover, BRACEs are ordinally envy-free and ex-post envy-free up to one good (where envy is only justified if another agent's endowment is either smaller or worth less in equilibrium). A mechanism that implements a BRACE is strategyproof in the large. Our framework can be used in many real-world market design applications, such as organ exchanges, tuition exchanges, time bank sharing, shift exchanges, and resource reallocation.

We develop sealed-bid combinatorial auction formats for indivisible goods in which bidders can express budget constraints. To do so, we analyze the extent to which the designer must adjust budgets or the supply of goods in order to guarantee the existence of competitive equilibrium. We show that large adjustments can be avoided by perturbing both the budget and supply of goods at the same time. We first give analytical results for additive, assignment and substitutes valuations and explain how budgets can be incorporated into existing auction formats. We then develop a new flexible and parsimonious bidding language---combinatorial assignment valuations---and express the adjustment tradeoff for combinatorial assignment auctions in terms of a parameter that captures the complementarity between goods.

Pseudomarkets are useful in many market design applications without transfers, including the allocation of donations to food banks, course assignment, and school choice. We give a necessary and sufficient condition for the existence of equilibria in pseudomarkets with indivisible goods. In particular, we show that all random equilibria in a pseudomarket can be realized as lotteries over allocations if and only if competitive equilibria exist in a transferable utility economy within the same class of valuations. Our equivalence result bridges two fundamental models of competitive market designs for indivisible resources, offering new insights into equilibrium existence and maximal domain results for pseudomarkets. We extend the main equivalence result to incorporate priorities (e.g., school choice), ex-ante individual constraints (e.g., portfolios), and expost aggregate constraints (e.g., regional capacities). Our paper highlights the broad applicability of the pseudomarkets for resource allocation, even in the presence of preference complementarities and complex constraints.

Employment outcomes of resettled refugees depend strongly on where they are placed inside the host country. While the United States sets refugee capacities for communities on an annual basis, refugees arrive and must be placed over the course of the year. We introduce a dynamic allocation system based on two-stage stochastic programming to improve employment outcomes. Our algorithm is able to achieve over 98 percent of the hindsight-optimal employment compared to under 90 percent of current greedy-like approaches. This dramatic improvement persists even when we incorporate a vast array of practical features of the refugee resettlement process including indivisible families, batching, and uncertainty with respect to the number of future arrivals. Our algorithm is now part of the Annie™? MOORE optimization software used by a leading American refugee resettlement agency. The full version of this paper is available at https://arxiv.org/pdf/2105.14388.pdf.

We analyze the implications of financial or other budget constraints in a model of matching with contracts. We assume that agents' preferences satisfy the net substitutability condition: i.e, if a price of a good increases, then minimizing the cost of obtaining a given level of utility would lead buyers (resp. sellers) to buy (resp. sell) more (resp. less) of other goods. The net substitutability condition coincides with gross substitutability if agents' preferences are quasilinear, but is strictly weaker otherwise. If agents have sufficient incomes for hard budget constraints not to bind, stable outcomes exist and coincide with competitive equilibrium outcomes. Otherwise, competitive equilibria can fail to exist, but stable outcomes exist and coincide with quasiequilibrium outcomes. Stable outcomes are at least weakly Pareto-efficient, but do not form a lattice and do not satisfy a Lone Wolf (or Rural Hospitals) Theorem. Our results suggest a new scope for sealed-bid auctions and matching with budget constraints.

We show that, with indivisible goods, the existence of competitive equilibrium fundamentally depends on agents' substitution effects, not their income effects. Our Equilibrium Existence Duality allows us to transport results on the existence of equilibrium from transferable utility economies to settings with income effects. One consequence is that net substitutability-which is a strictly weaker condition than gross substitutability-is sufficient for the existence of equilibrium. We also extend the "demand types" classification of valuations to settings with income effects and give necessary and sufficient conditions for a pattern of substitution effects to guarantee the existence of competitive equilibrium.

We analyze a threshold contagion process in a graphon. We interpret the graphon as a stochastic network formation model. We investigate whether contagion in networks sampled from a graphon can be predicted by only exploiting information about the graphon. Our main results show that contagion in large but finite networks sampled from a graphon is well approximated by contagion in the graphon. We illustrate our results by providing analytical characterizations of contagion and optimal seeding policies in graphons with finite and with infinite types.

We show how frictions and continuous transfers jointly affect equilibria in a model of matching in trading networks. Our model incorporates distortionary frictions such as transaction taxes, bargaining costs, and incomplete markets. When contracts are fully substitutable for firms, competitive equilibria exist and coincide with outcomes that satisfy a cooperative stability property called trail stability. In the presence of frictions, competitive equilibria might be neither stable nor (constrained) Pareto-efficient. In the absence of frictions, on the other hand, competitive equilibria are stable and in the core, even if utility is imperfectly transferable.