We study fair allocation of indivisible goods among agents. Prior research focuses on additive agent preferences, which leads to an impossibility when seeking truthfulness, fairness, and efficiency. We show that when agents have binary additive preferences, a compelling rule—maximum Nash welfare (MNW)—provides all three guarantees. Specifically, we show that deterministic MNW with lexicographic tie-breaking is group strategyproof in addition to being envy-free up to one good and Pareto optimal. We also prove that fractionalMNW—known to be group strategyproof, envy-free, and Pareto optimal—can be implemented as a distribution over deterministic MNW allocations, which are envy-free up to one good. Our work establishes maximum Nash welfare as the ultimate allocation rule in the realm of binary additive preferences.

Two-sided matching platforms provide users with menus of match recommendations. To maximize the number of realized matches between the two sides (referred to as customers and suppliers respectively), the platform must balance the inherent tension between recommending customers more potential suppliers to match with and avoiding potential collisions. We introduce a stylized model to study the above trade-off. The platform offers each customer a menu of suppliers, and customers choose, simultaneously and independently, to either select a supplier from their menu or remain unmatched. Suppliers then see the set of customers that have selected them, and choose to either match with one of these customers or remain unmatched. A match occurs if a customer and a supplier choose each other (in sequence). Agents' choices are probabilistic, and proportional to the public scores of agents in their menu and a score that is associated with the outside option of remaining unmatched. The platform's problem is to construct menus for customers to maximize the number of matches. We show the problem is strongly NP-hard and provide an efficient algorithm that achieves a constant-factor approximation to the optimal expected number of matches. Our algorithm uses bucketing techniques, which group similar suppliers into buckets, together with linear programming based relaxations and rounding. We finally provide simulations to better understand how the algorithm might behave in practice.

In this paper, we introduce a Bayesian revenue-maximizing mechanism design model where the items have fixed, exogenously-given prices. Buyers are unit-demand and have an ordinal ranking over purchasing either one of these items at its given price, or purchasing nothing. This model arises naturally from the assortment optimization problem, in that the single-buyer optimization problem over deterministic mechanisms reduces to deciding on an assortment of items to "show". We study its multi-buyer generalization in the simplest setting of single-winner auctions, or more broadly, any service-constrained environment. Our main result is that if the buyer rankings are drawn independently from Markov Chain ranking models, then the optimal mechanism is computationally tractable, and structurally a virtual welfare maximizer. We also show that for ranking distributions not induced by Markov Chains, the optimal mechanism may not be a virtual welfare maximizer.

We study a dynamic non-bipartite matching problem. There is a fixed set of agent types, and agents of a given type arrive and depart according to type-specific Poisson processes. The value of a match is determined by the types of the matched agents. We present an online algorithm that is (1/8)-competitive with respect to the value of the optimal-in-hindsight policy, for arbitrary weighted graphs. This is the first result to achieve a constant competitive ratio when both arrivals and departures are random and unannounced. Our algorithm treats agents heterogeneously, interpolating between immediate and delayed matching in order to thicken the market while still matching valuable agents opportunistically.

We build upon recent work by Kleinberg, Oren, and Raghavan [10-12] that considers present biased agents, who place more weight on costs they must incur now than costs they will incur in the future. They consider a graph theoretic model where agents must complete a task and show that present biased agents can take exponentially more expensive paths than optimal. We propose a theoretical model that adds competition into the mix - two agents compete to finish a task first. We show that, in a wide range of settings, a small amount of competition can alleviate the harms of present bias. This can help explain why biased agents may not perform so poorly in naturally competitive settings, and can guide task designers on how to protect present biased agents from harm. Our work thus paints a more positive picture than much of the existing literature on present bias.

Ridehailing services have become an integral part of transportation systems all over the world. For this reason, efficient ridesharing is important to the efficiency of transportation systems. We study ridesharing as an online matching problem where riders arrive to a platform over time, and the efficiency of putting two riders in a single vehicle depends on their pickup and dropoff locations. The platform's goal is to match multiple users together (indicating they will share a ride) to maximize system efficiency. We present algorithms for ridesharing that have the optimal worst-case performance in this model. Existing work focuses on the case where at most two users can share a ride. Since ridehailing vehicles often have more than two passenger seats, our model allows multiple users to share a ride.

In the Hospital Residents problem with lower and upper quotas (HR-Q_L^U), the goal is to find a stable matching of residents to hospitals where the number of residents matched to a hospital is either between its lower and upper quota or zero [Biro et al., TCS 2010]. We analyze this problem from a parameterized perspective using several natural parameters such as the number of hospitals and the number of residents. Moreover, we present a polynomial-time algorithm that finds a stable matching if it exists on instances with maximum lower quota two. Alongside HR-Q_L^U, we also consider two closely related models of independent interest, namely, the special case of HR-Q_L^U where each hospital has only a lower quota but no upper quota and the variation of HR-Q_L^U where hospitals do not have preferences over residents, which is also known as the House Allocation problem with lower and upper quotas.