Condorcet winning sets address the Condorcet paradox by selecting a small set of candidates—rather than a single winner—such that a majority prefers no unselected alternative over all members of the set. This notion extends to \(\alpha\)-undominated sets, which require the same property to hold for any \(\alpha\)-fraction of voters. Such sets are guaranteed to exist with constant size for any fixed \(\alpha\). However, the requirement that an outsider be preferred to every member of the set can be overly restrictive and difficult to justify in many applications. Motivated by this, we introduce a more flexible notion: \((t, \alpha)\)-undominated sets. Here, each voter compares an outsider to their \(t\)-th most preferred member of the set, and the set is undominated if no outsider is preferred by more than an \(\alpha\)-fraction of voters. This framework subsumes prior definitions, recovering Condorcet winning sets when \((t = 1, \alpha = 1/2)\) and \(\alpha\)-undominated sets when \(t = 1\), and introduces a new, tunable notion of collective acceptability for \(t \gt 1\).

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.

A stochastic mapping from states to signals induces a distribution over possible posteriors. For a variety of purposes one is interested in parameters of these posteriors, possibly multi-dimensional, such as their quartiles or whether they first-order stochastically dominate some given distribution. Many parameters of interest can be encoded by requiring the posterior at each signal lie point-wise between two given distributions. Given a collection of these bounding pairs, one for each signal, we characterize the set of posteriors that can be realized by some stochastic mapping of states to signals. We provide applications of this result to, among others, the design of securities, price, and statistical discrimination.

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.

Ensuring fair and stable allocation of scarce resources is a fundamental challenge in a wide range of applications. Examples of domains where these challenges manifest include applications where geographical and time constraints impede information collection, such as distributing resources to food banks and providing humanitarian aid to disaster areas and war zones [Aleksandrov et al., 2015, Aleksandrov and Walsh, 2020]. Even in online marketplaces devoid of physical constraints, such as dating services and job matching, evaluating information and collecting data presents a formidable challenge. Recent literature bridges this gap partially by learning noisy preferences as allocation decisions are made. This approach makes allocation processes more adaptable and efficient when the information is incomplete or dynamically changing. However, the current research typically assumes that input from all participants is available at each time-epoch of the allocation process [Bistritz et al., 2020, Cen and Shah, 2022, Leshem, 2024, Liu et al., 2020, Yamada et al., 2023]. Since gathering information is costly and often practical considerations make it infeasible, assuming its availability overlooks the possibility of designing efficient algorithms that operate with limited feedback and the accompanying analysis fails to illuminate which feedback is crucial for efficient design.

Gross substitutes for quasi-linear preferences is characterized by the single improvement property, which says an agent can improve upon a sub-optimal bundle by adding or dropping a single item, or exchanging one item for another. We extend this notion in two ways: by allowing for non-quasi-linear preferences and the exchange of up to Delta items. Our results connect the improvement property with the geometry of the choice correspondence. We derive prices at which the excess demand for each good is at most Delta-1 and provide applications to the design of pseudo-markets for allocating indivisible resources.

With COVID 19 prevalent in the USA and the world, efficient social distance seating became an option for sports venues. The social distancing constraint requires six feet between individuals when the game has live audiences. Depending on the seats' dimensions, this would translate to a certain number of empty rows and empty seats in a row between the individuals. As a result, it is not possible to seat all ticket holders with safe social distancing. Hence, it necessitates reassigning spectators to games. An important feature of this problem is that season tickets are grouped by family, and only a safe distance between two different families needs to be maintained. Members of the same family can sit next to each other. Therefore, a large family needs fewer empty seats per person to maintain social distancing. A football season has about six home games. If priority is given to larger families for all the games, then many people can watch the live games, but the outcome will be highly unfair. Striking a good balance between efficiency and fairness is a nontrivial task.

The problem of finding stable matches that meet distributional concerns is usually formulated by imposing various side constraints. Prior work has focused on constraints whose "right hand sides" are absolute numbers specified before the preferences or number of agents on the "proposing" side are known. In many cases it is more natural to express the relevant constraints as proportions. We treat such constraints as soft, but provide ex-post guarantees on how well the constraints are satisfied while preserving stability. We violate the proportions by an amount proportional to the reciprocal of the number of students assigned to the school. For example, if a school is assigned 100 students, then the actual proportion will differ from the desired proportion by at most 2%. Our technique requires an extension of Scarf's lemma, which is of independent interest.

The National Resident Matching program strives for a stable matching of medical students to teaching hospitals. With the presence of couples, stable matchings need not exist. For any student preferences, we show that each instance of a stable matching problem has a 'nearby' instance with a stable matching. The nearby instance is obtained by perturbing the capacities of the hospitals. Our approach is general and applies to other type of complementarities, as well as matchings with side constraints and contracts.

In a limited form cellular providers have long shared spectrum in the form of roaming agreements. The primary motivation for this has been to extend the coverage of a wireless carrier's network into regions where it has no infrastructure. As devices and infrastructure become more agile, such sharing could be done on a much faster time-scale and have advantages even when two providers both have coverage in a given area, e.g., by enabling one provider to acquire “overflow” capacity from another provider during periods of high demand. This may provide carriers with an attractive means to better meet their rapidly increasing bandwidth demands. On the other hand, the presence of such a sharing agreement could encourage providers to underinvest in their networks, resulting in poorer performance. We adapt the newsvendor model from the operations management literature to model such a situation and to gain insight into these trade-offs. In particular, we analyze the structure of revenue-sharing contracts that incentivize both capacity sharing and increased access for end-users.

We analyze an infinite horizon, non-cooperative bargaining model for a general coalitional formation framework. In each period of the game an opportunity for a feasible coalition to form arises according to a stochastic process, and a randomly selected agent in the coalition makes a take-it-or-leave-it offer. Agents that reach an agreement exit the game and are replaced by clones. We characterize the unique stationary payoff by a convex program. We examine the implications of this characterization when the feasible coalitions are determined by an underlying network. We show how an agent's payoff is related to the centrality of his position in the network.

We study how local bargaining in a networked market can cause endogenous fluctuations by a new approach that incorporates non-cooperative bargaining into a large networked economy. In particular, we consider a networked bargaining game that captures trade with intermediaries and define its replications. We examine the agents' behavior in the limit as the population size goes to infinity: a limit stationary equilibrium exists if there is a converging sequence of semi-stationary equilibria in the finite replications. The existence of a limit stationary equilibrium captures the hypothesis that when the market gets large, the agents will behave myopically and the market will be stable. However, we prove that limit stationary equilibria need not exist even when market fundamentals are deterministic, agents are patient and share a common belief. This shows that in our setting the underlying network is the main friction that hinders stationary markets.

We consider a weighted proportional allocation of resources that allows providers to discriminate usage of resources by users. This framework is a generalization of well-known proportional allocation by accommodating allocation of resources proportional to weighted bids or proportional to submitted bids but with weighted payments.

We consider a resource allocation game in polyhedral environments. Polyhedral environments model a wide range of problems, including bandwidth sharing, some models of Adwords auctions and general resource allocation. We extend the fair sharing mechanism for such resource allocation games. We show that our mechanism simultaneously creates approximately efficient allocations andallapproximately maximizes revenue. We also develop a new approach for analyzing games of these types. At the core of this approach is the relation between the condition for Nash equilibriums of the game and the dual of a certain linear program.