EC '25: Proceedings of the 26th ACM Conference on Economics and Computation

We generalize the problem of online submodular welfare maximization to incorporate various stochastic elements that have gained significant attention in recent years. We show that a non-adaptive Greedy algorithm, which is oblivious to the realization of these stochastic elements, achieves the best possible competitive ratio among all polynomial-time algorithms, including adaptive ones, unless NP=RP. This result holds even when the objective function is not submodular but instead satisfies the weaker submodular order property. Our results unify and strengthen existing competitive ratio bounds across well-studied settings and diverse arrival models, showing that, in general, adaptivity to stochastic elements offers no advantage in terms of competitive ratio.

To establish these results, we introduce a technique that lifts known results from the deterministic setting to the generalized stochastic setting. The technique has broad applicability, enabling us to show that, in certain special cases, non-adaptive Greedy-like algorithms outperform the Greedy algorithm and achieve the optimal competitive ratio. We also apply the technique in reverse to derive new upper bounds on the performance of Greedy-like algorithms in deterministic settings by leveraging upper bounds on the performance of non-adaptive algorithms in stochastic settings.

The full paper can be found at https://arxiv.org/abs/2403.18059.

This paper investigates regulatory distortion in the incentives to invest in transmission capacity in the United States natural gas pipeline network. We are motivated by the fact that trade of gas between states should temper regional price variation. However, price differences between locations frequently exceed the marginal cost of transmission, indicating that capacity constraints are binding. Gas pipelines are tightly regulated through both rate-of-return for pricing and a costly approval process, both of which could distort the firms' investment incentives. When combined, the two sides of the regulatory structure could be used in tandem to design incentives that promote efficient network growth.

To understand how well the policy aligns incentives with social value, we develop a structural model of a pipeline firm's dynamic investment problem. We estimate the model nonparametrically, using recent advancements in automatically-debiased deep neural networks and kernel embeddings. We then construct a measure of the social value of pipeline capital, based on a social planner model that ties the value of capacity expansion to regional price gaps.

In most areas, the incentives of firms to invest under fixed rates of return exceed the social value of capital, highlighting the importance of costly approvals as a secondary tool to control investments. Even for a range of discount factors that rationalize the observed policy on average, there are systematic deviations from the optimal policy both spatially and intertemporally. We suggest a welfare improving reallocation of regulatory costs that would streamline the approval process in certain parts of the northeast, but shift focus toward the southeast and parts of the mountain west.

A full version of this paper can be found at https://www.psolimine.net/workingpapers/pipelines/pipelines.pdf

A patient player interacts with a sequence of short-run players. The patient player is either an honest type who always takes a commitment action and never erases any record, or an opportunistic type who decides which action to take and whether to erase his action at a low cost. I show that in every equilibrium, the patient player will have an incentive to take the commitment action until he has accumulated a long enough good record, at which point he can secure a payoff that is strictly greater than his commitment payoff. However, as long as the patient player is sufficiently long-lived, his equilibrium payoff must be close to his minmax value. This is because the ability to erase records enables the opportunistic type to pool with the honest type who is younger in age. As the player's expected lifespan increases, his opponents' posterior belief will assign a lower probability to him being the honest type since the honest type is younger on average. This will lower his reputation at any history, slow down his reputation-building process, and wipe out his returns from building reputations. However, a small probability of the opportunistic type only has a negligible effect on the short-run players' welfare, which is close to their expected payoff in a repeated complete information game where the patient player's type is common knowledge.

The full version of this paper is available at https://arxiv.org/abs/2308.13956

Choice correspondences are crucial in decision-making, especially when faced with indifferences or ties. While tie-breaking can transform a choice correspondence into a choice function, it often introduces inefficiencies. This paper introduces a novel notion of path-independence (PI) for choice correspondences, extending the existing concept of PI for choice functions. Intuitively, a choice correspondence is PI if any consistent tie-breaking produces a PI choice function. This new notion yields several important properties. First, PI choice correspondences are rationalizabile, meaning they can be represented as the maximization of a utility function. This extends a core feature of PI in choice functions. Second, we demonstrate that the set of choices selected by a PI choice correspondence for any subset forms a generalized matroid. This property reveals that PI choice correspondences exhibit a nice structural property. Third, we establish that choice correspondences rationalized by ordinally concave functions inherently satisfy the PI condition. This aligns with recent findings that a choice function satisfies PI if and only if it can be rationalized by an ordinally concave function.

Building on these theoretical foundations, we explore stable and efficient matchings under PI choice correspondences. Specifically, we investigate constrained efficient matchings, which are efficient (for one side of the market) within the set of stable matchings. Under responsive choice correspondences, such matchings are characterized by cycles. However, this cycle-based characterization fails in more general settings. We demonstrate that when the choice correspondence of each school satisfies both PI and monotonicity conditions, a similar cycle-based characterization is restored. These findings provide new insights into the matching theory and its practical applications.

A full version of this paper is available at arXiv (https://arxiv.org/abs/2502.09265).

Electric power systems are undergoing a major transformation as they integrate intermittent renewable energy sources, and batteries to smooth out variations in renewable energy production. As privately-owned batteries grow from their role as marginal "price-takers" to significant players in the market, a natural question arises: How do batteries operate in electricity markets, and how does the strategic behavior of decentralized batteries distort decisions compared to centralized batteries? We propose an analytically tractable model that captures salient features of the highly complex electricity market. We derive in closed form the resulting battery behavior and generation cost in three operating regimes: (i) no battery, (ii) centralized battery, and (ii) decentralized profit-maximizing battery. We establish that a decentralized battery distorts its discharge decisions in three ways. First, there is quantity withholding, i.e., discharging less than centrally optimal. Second, there is a shift in participation from day-ahead to real-time, i.e., postponing some of its discharge from day-ahead to real-time. Third, there is reduction in real-time responsiveness, or discharging less in response to smoothing real-time demand than centrally optimal. We also quantify the impact of the battery market power on total system cost via the Price of Anarchy metric, and prove that it is always between 9/8 and 4/3. That is, incentive misalignment always exists, but it is bounded even in the worst case. We calibrate our model to real data from Los Angeles and Houston. Lastly, we show that competition is very effective at reducing distortions, but many market power mitigation mechanisms backfire, and lead to higher total cost. The work provides stakeholders with a framework to understand and detect market power from batteries. It also shows that the potential loss from battery market power is relatively small compared to the cost reduction achievable from having enough battery capacity in the system. Therefore, independent system operators in rapidly changing markets might want to prioritize market entry of batteries and only shift to market power mitigation once the market is more mature.

We consider a group of agents who can each take an irreversible costly action whose payoff depends on an unknown state. Agents learn about the state from private signals, as well as from past actions of their social network neighbors, which creates an incentive to postpone taking the action. We show that outcomes depend on network structure: on networks with a linear structure patient agents do not converge to the first-best action, while on regular directed tree networks they do.

We consider the computational complexity of computing Bayes-Nash equilibria in first-price auctions, where the bidders' values for the item are drawn from a general (possibly correlated) joint distribution. We show that when the values and the bidding space are discrete, determining the existence of a pure Bayes-Nash equilibrium is NP-hard. This is the first hardness result in the literature of the problem that does not rely on assumptions of subjectivity of the priors, or convoluted tie-breaking rules. We then present two main approaches for achieving positive results, via bid sparsification and via bid densification. The former is more combinatorial and is based on enumeration techniques, whereas the latter makes use of the continuous theory of the problem developed in the economics literature. Using these approaches, we develop polynomial-time approximation algorithms for computing equilibria in symmetric settings or settings with a fixed number of bidders, for different (discrete or continuous) variants of the auction.

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.

The full paper is available at https://papers.ssrn.com/abstract=5283955.

When bidders have correlated private information, optimal auction mechanisms screen bidders based on their beliefs. We show that the possibility of ex post withdrawal by bidders provides a foundation for uniform price auctions that applies even in settings with correlated information. Withdrawal rights therefore provide a realistic framework for studying optimal auction design with correlated information. Our results are not driven by ex post individual rationality constraints or their interaction with the winner's curse. Instead, our analysis relies on a strategic impact of withdrawal rights: bidders can engage in "double deviations" that involve misreporting and then (sometimes) withdrawing ex post.

A monopolist wants to sell multiple goods, accounting for the possibility of returns. For any bundle purchased, a buyer can return any part of the bundle for a partial refund specified by a return policy. The seller is constrained to offer additive return policies: the total price of a bundle must be divided into return values for each of the goods in the bundle. We show that if the buyer's values are additive and independent across goods, then selling each good separately is optimal. The result applies even if the seller can use stochastic mechanisms, and holds for general multidimensional screening problems. We show that selling separately remains approximately optimal if the buyer experiences small return costs, as well as if the return policy only has to be close to additive or the buyer's values are weakly correlated. Applying our analysis to multiproduct pricing without returns, we introduce a new concept of bundle discounts and show that obtaining revenue gains from using any complex mechanism requires discounting bundles in our sense.

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.

The full version of the paper is available at https://web.ics.purdue.edu/~nguye161/multipara.pdf

AI systems are increasingly used to support human decision-making. In many cases, despite the algorithm's superior performance, the final decision remains in human hands. For example, an AI may assist doctors in determining which diagnostic tests to run, but the doctor ultimately makes the diagnosis. Focusing on these scenarios, this paper studies AI-assisted decision-making where the human learns through repeated interactions with the algorithm. In our framework, the algorithm - designed to maximize decision accuracy according to its own model - determines which features the human can consider. The human then makes a prediction based on their own, less accurate model. Additionally, we consider the possibility of a constraint on the number of features that can be taken into account.

We observe that the discrepancy between the algorithm's model and the human's model creates a fundamental trade-off. Should the algorithm prioritize recommending more informative features, encouraging the human to recognize their importance, even if it results in less accurate predictions in the short term until learning occurs? Or is it preferable to forgo educating the human and instead select features that align more closely with their existing understanding, minimizing the immediate cost of learning? This trade-off is shaped by both the algorithm's patience (the time-discount rate of its objective function over multiple periods) and the human's willingness and ability to learn.

Our results show that optimal feature selection has a surprisingly clean combinatorial characterization, reducible to a stationary sequence of feature subsets that is tractable to compute. As the algorithm becomes more patient or the human's learning improves, the algorithm increasingly selects more informative features, enhancing both prediction accuracy and the human's understanding of the world. Notably, early investment in learning leads to the selection of more informative features compared to a later investment. We complement our analysis by showing that the impact of errors in the algorithm's knowledge is limited as it does not make the prediction directly.

For the full paper, see: https://arxiv.org/abs/2502.13062

Clock auctions are a natural class of simple auction mechanisms, with numerous desirable properties including obvious strategyproofness, credibility, and unconditional winner privacy. These properties make clock auctions an ideal solution for real-world allocation problems, such as radio spectrum (re)allocation. Accordingly, significant effort has been made in understanding the performance (and in particular, economic efficiency) of clock auctions. In this paper, we make progress along this direction on multiple fronts.

Computationally, we investigate two natural problems: implementation and optimization. The former asks to find a clock auction protocol that implements a particular input allocation function whenever there exists one, and declare that this is impossible otherwise; the latter asks to find a clock auction protocol that maximizes social welfare among all clock auction protocols on a particular input prior distribution. We give an efficient algorithm for the implementation problem, and show that the optimization problem is NP-complete. To our knowledge, these are the first results regarding the computational complexity of clock auctions. En route to these results, we develop a complete characterization of allocation functions that can be implemented using clock auctions, which may be of independent interest.

Information-theoretically, we present a framework connecting the economic efficiency of clock auctions to a much cleaner problem that we call "upper tail extraction". In particular, the inexistence of constant-factor clock auctions for upper tail extraction would immediately imply a super-constant efficiency gap for clock auctions. On the other hand, the existence of constant-factor clock auctions for upper tail extraction would imply approximate efficiency in an important class of instances, strongly suggesting approximate efficiency in general. We then construct constant-factor clock auctions for upper tail extraction in the special case with iid agents, which, through our framework, implies approximate efficiency of clock auctions with independent groups of agents that are each homogeneous. This removes the immediate technical obstacle to unconditional approximate efficiency identified in prior work, and showcases the power of our framework.

A knockout tournament is one of the most simple and popular forms of competition. Here, we are a given binary tournament tree where all leaves are labeled with seed position names. The players participating in the tournament are assigned to the seed positions. In each round, the two players assigned to leaves of the tournament tree with a common parent compete, and the winner is promoted to the parent. The last remaining player is the winner of the tournament.

In this work, we study the problem of making knockout tournaments robust against manipulation, where the form of manipulation we consider is changing the outcome of a game. We assume that our input is only the number of players that compete in the tournament, and the number of manipulations against which the tournament should be robust. Furthermore, we assume that there is a strongest player, that is, a player that beats any of the other players. However, the identity of this player is not part of the problem input.

To ensure robustness against manipulation, we uncover an unexpected connection between the problem at hand and communication protocols that utilize a feedback channel, offering resilience against adversarial noise. We explore the trade-off between the size of the robust tournament tree and the degree of protection against manipulation. Specifically, we demonstrate that it is possible to tolerate up to a 1/3 fraction of manipulations along each leaf-to-root path, at the cost of only a polynomial blow-up in the tournament size.

Two-sided marketplaces such as Amazon, Alibaba, Google, and Yelp connect customers with providers and commonly rank providers based on quality while allowing them to promote themselves through sponsored ads. This paper develops a game-theoretic model of such platforms, where providers strategically choose customer prices and advertising intensity in response to the platform's ad placement and pricing policy. The analysis characterizes equilibrium outcomes and examines how platforms can design policies to optimize key objectives. The results show that ranking sponsored ads by the product of bid and clickthrough rate—a widely used heuristic—always maximizes supply-side surplus, defined as the sum of provider profits and platform revenue. To also enhance customer surplus, platforms should discount the per-impression cost of ads based on estimated provider quality, enabling providers that better meet customer needs to pay less per impression. This quality-adjusted pricing rule achieves the best possible multiplicative guarantee relative to the first-best social welfare, which includes both supply-side and customer surplus. In contrast, when provider quality is imperfectly estimated, removing sponsored ads and relying solely on organic rankings yields strictly worse welfare guarantees. These results offer prescriptive guidance for platform design and establish normative benchmarks for evaluating digital marketplace policies.

Link to the full paper: https://ssrn.com/abstract=5132218

Motivated by the challenges in last-mile delivery operations, we consider a natural dynamic staffing problem in which a decision-maker sequentially hires staff over a finite time horizon to meet an unknown target demand at the end. The decision-maker also receives a sequence of predictions about the demand that become increasingly more accurate over time. Consequently, the decision-maker prefers to delay hiring decisions to avoid overstaffing. However, workers' availability decreases over time, resulting in a fundamental trade-off between securing staff early (thus risking overstaffing) versus hiring later based on more accurate predictions (but risking understaffing).

We study the above problem when predictions take the form of uncertainty intervals that encompass the true demand. The goal of the decision-maker is to minimize the staffing imbalance cost at the end of the horizon against any sequence of prediction intervals being chosen by an adversary. Our main result is the characterization of a simple and computationally efficient online algorithm that obtains the optimal worst-case imbalance cost; said differently, it is minimax optimal. At a high level, our algorithm relies on identifying a restricted adversary against which we can characterize the minimax optimal cost by solving a certain offline LP. We then show how to emulate the LP solution in a general instance to obtain a cost bounded above by the LP's objective. Besides the base model of staffing for one target demand, We show how to extend our LP-based emulator minimax optimal policy to various generalizations with (i) multiple target demands, (ii) costly hiring and releasing with budgets, and (iii) jointly minimizing the cost of hiring and over-/under-staffing.

A full version of this paper can be found at http://dx.doi.org/10.2139/ssrn.4732158.

How do people navigate the exploration-exploitation (EE) trade-off when making repeated choices with unknown rewards? We study this question through the lens of multi-armed bandit problems and introduce a novel behavioral model, Quantal Choice with Adaptive Reduction of Exploration (QCARE). It generalizes Thompson Sampling, allowing for a principled way to quantify the EE trade-off and reflect human decisionmaking patterns. The model adaptively reduces exploration as information accumulates, with the reduction rate serving as a parameter to quantify the EE trade-off dynamics. We theoretically analyze how varying reduction rates influence decision quality, shedding light on the effects of "over-exploration" and "under-exploration." Empirically, we validate QCARE through experiments collecting behavioral data from human participants. QCARE not only captures critical behavioral patterns in the EE trade-off but also outperforms alternative models in predictive power. Our analysis reveals a behavioral tendency toward over-exploration.

[See full paper: https://doi.org/10.48550/arXiv.2207.01028]

We quantify the value of the monopoly's bargaining power in terms of competition complexity—that is, the number of additional bidders the monopoly must attract in simple auctions to match the expected revenue of the optimal mechanisms —within the setting of multi-item auctions. We show that for simple auctions that sell items separately, the competition complexity is Θ(n/α) in an environment with n original bidders under the slightly stronger assumption of α-strong regularity, in contrast to the standard regularity assumption in the literature, which requires Ω (n · ln m/n) additional bidders. This significantly reduces the value of learning the distribution to design the optimal mechanisms, especially in large markets with many items for sale. For simple auctions that sell items as a grand bundle, we establish a constant competition complexity bound in a single-bidder environment when the number of items is small or when the value distribution has a monotone hazard rate. Some of our competition complexity results also hold when we compete against the first best benchmark (i.e., optimal social welfare).

A full version of this paper can be found at https://ssrn.com/abstract=5283621.

We consider a generalization of the classical newsvendor problem to a multi-location setting. A seller determines the initial inventory of a product across multiple locations on a metric. Then, the seller decides a fulfillment policy to satisfy uncertain demand that realizes sequentially over time. The goal is to minimize the expected inventory and shipping costs. To address the distributional ambiguity, we consider a distributionally robust model where only the mean and variance of the demand are known and the goal is to minimize costs under the worst-case realization of the demand distribution.

For a single location, the seminal paper of Scarf (1959) shows that the problem admits a closed form optimal solution given by [EQUATION] where μ and σ denote the mean and standard deviation of the unknown demand distribution and b and h denote the per-unit underage and overage costs.

We design an approximation policy for the multi-location problem that significantly generalizes Scarf's solution maintaining its simplicity and interpretability. Our policy can be described as follows:

Well-Separated Hierarchal Partition. Our policy computes a special hierarchical clustering of the locations called Well-Separated Hierarchical Clustering. A "virtual" underage cost b_C is then assigned to each cluster C.

Inventory Solution. Our policy holds the minimum amount of inventory necessary to ensure that each cluster C contains an amount of inventory that is at least the order quantity given by Scarf's solution with mean and standard deviation corresponding to the total demand within the cluster subject to the "virtual" underage cost b_C and original overage cost h.

Fulfillment Policy. Demand is fulfilled using a hierarchical greedy approach: each demand request is fulfilled from the smallest cluster with remaining inventory that contains the request. Within the selected cluster, inventory is drawn uniformly equally from its subclusters, then uniformly equally from their respective subclusters, and so on, down to the individual locations level.

We show that our policy gives a polylogarithmic approximation for the problem. To the best of our knowledge, this is the first algorithm with provable guarantees for this fundamental problem. We also demonstrate through extensive numerical experiments that our policy performs well in practice.

A full version of this paper can be found at https://arxiv.org/abs/2410.12134.

Projected gradient ascent is known to satisfy no-external regret as a learning algorithm. However, recent empirical work shows that projected gradient ascent often finds the Nash equilibrium in settings beyond two-player zero-sum interactions or potential games, including those where the set of coarse correlated equilibria is very large. We show that gradient ascent in fact satisfies a stronger class of linear Φ-regret in normal-form games; resulting in a refined solution concept which we dub semicoarse correlated equilibria. Our theoretical analysis of the discretised Bertrand competition mirrors those recently established for mean-based learning in first-price auctions. With at least two firms of lowest marginal cost, Nash equilibria emerge as the only semicoarse equilibria under concavity conditions on firm profits. In first-price auctions, the granularity of the bid space affects semicoarse equilibria, but finer granularity for lower bids also induces convergence to Nash equilibria. Unlike previous work that aims to prove convergence to a Nash equilibrium that often relies on epoch based analysis and probability theoretic machinery, our LP-based duality approach enables a simple and tractable analysis of equilibrium selection under gradient-based learning.

A full version of this paper can be found at https://arxiv.org/abs/2502.20466.

We consider the classical Dynamic Max-min fair (DMMF) mechanism for allocating an indivisible resource without money over multiple agents and T rounds. We show that under mild assumption on value distributions, it guarantees every agent close to optimal utility in large markets.

Each agent i has a fair share α_i (where α_i > 0 and Σ_i α_i = 1), representing her nominal share. In every round, each agent has a non-negative value for the item which is a random variable independent of other agents. The DMMF mechanism allocates as follows: every round a subset of agents requests the resource; out of these, the one with the least past allocations gets the item.

We use ideal utility to benchmark our results: v^*_i is agent i's maximum expected average per-round utility if allocated her favorite α_i fraction of the rounds. We show that in the DMMF mechanism, any agent i can use a simple strategy to make utility guarantees that hold under arbitrary (potentially adversarial and collusive) behavior by the other agents. Specifically, when her values are i.i.d. across rounds, agent i can guarantee total expected utility by every round t ≤ T:

• [EQUATION] under any value distribution.

• [EQUATION] when her values are uniformly distributed.

• [EQUATION] when her value distribution's pdf max and min value over its support differ by a λ ≥ 1 multiplicative factor.

The last two results are approximately optimal in the large market setting (when α_i → 0) and greatly outperform the [EQUATION] upper bound that holds for worst-case distributions. With some modifications, similar results are achieved for resources needed for multiple contiguous periods.

We also prove that an agent can have utility guarantees under the same mechanism, even when her values are dependent across rounds, generated by a hidden Markov model. We use a parameter γ ∈ (0, 1] to measure the dependence of values across rounds, where γ = 1 indicates that values are independent and lower γ indicates more dependence across rounds. In this case, we prove that agent i can always guarantee Ω(γ)v^*_i t - O(1) utility for small α. We also offer guarantees that are independent of γ.

The full version of our paper can be found in https://arxiv.org/abs/2310.08881.

Positional goods are goods or services whose value to consumers depends on their relative positions in consumption. Examples include luxury goods, priority services, education, and organizational hierarchies. The allocation of positional goods has externalities on consumers, as moving up the position of one consumer would push down that of another. At the same time, when more consumers buy the same good or service, its value depreciates due to more extensive use.

Using a mechanism design approach, I study the optimal allocation of positional goods in the presence of positional externalities. I characterize the externalities by a feasibility condition: an incentive-compatible status allocation is feasible (i.e., can be induced by an allocation of positional goods) if and only if it is weakly majorized by the probability distribution of the buyer's type in the quantile space.

My first set of results focuses on revenue maximization. If the buyer's type distribution satisfies Myerson's regularity condition, the optimal mechanism excludes buyers with negative marginal revenue and fully separates the participants. If Myerson's regularity condition fails for some types, the optimal mechanism pools them into the same level of positional goods. Importantly, the seller can guarantee at least half the maximum revenue by selling a single level of positional goods.

I then study how the number of positional good levels and exclusion affect consumer welfare. Holding the exclusion level fixed, the consumer surplus is higher when the seller offers more positional good levels if the buyer's type distribution has an increasing failure rate (IFR). This result highlights the tension between the seller's revenue and consumer welfare. By contrast, if the type distribution has a decreasing failure rate, the consumer surplus is higher when the seller offers fewer positional good levels. Furthermore, under IFR, expanding consumer participation increases the consumer surplus, as the marginal gain of additional participants exceeds the inframarginal loss of the existing participants from reduced status due to pooling.

My findings also have implications for education and organizational hierarchies, where agents invest effort to attain higher status. If the ability distribution satisfies IFR, total pooling without exclusion, such as admission lotteries, maximizes agent welfare. In contrast, if the ability distribution has a decreasing failure rate (or a heavy tail), full separation without exclusion, or meritocratic allocation, is optimal for agent welfare.

The full paper is available at: https://arxiv.org/abs/2411.06285.

Cap-and-quota regulations are a commonly employed policy tool to address distributional disparities in matching markets. This paper develops a theoretical and empirical framework to evaluate the effectiveness of such regulations by integrating regional constraints into a transferable utility matching model. Using novel data from the Japan Residency Matching Program, we estimate participants' preferences and simulate counterfactual matching outcomes under various policy interventions. Simulation results reveal that cap-based regulations lead to significant efficiency losses, whereas a modest subsidy for each match in underserved regions achieves distributional constraints while improving social welfare.

Full Paper: https://arxiv.org/abs/2205.14387

The structure of network externalities influences platform competition and can determine whether a two-sided market is winner-takes-all or highly contestable. Yet, because of analytical challenges, relatively little is known about these structures in different markets, raising several research questions: How do network externalities arise in specific markets? What is the structure of network externalities? How does the structure influence the competition between two-sided platforms? What conditions lead to a monopoly or an oligopoly outcome, enabling or discouraging entry? We address these questions in the context of ride-hailing platforms, identifying the externalities that arise from congestion.

We propose a model of platform competition in ride-hailing. The market consists of riders and drivers whose utilities are affected by the congestion within the platforms. Riders are sensitive to price and delay; drivers value high wages and utilization. We first find representations of congestion, which serve as micro-foundations for platform competition. Then, we establish general conditions for the existence and uniqueness of the equilibrium, offering insights into the markets that can lead to a monopolistic or an oligopolistic outcome. Moreover, we analyze entry when incumbents cannot set their prices and wages irreversibly. Finally, we examine how changing market conditions affect equilibrium outcomes using comparative statics.

Our results demonstrate that ride-hailing platforms benefit from economies of scale, becoming more efficient as they attract more riders and drivers. This could lead to winner-takes-all scenarios in markets with low demand or attractive outside options. However, service variability arising from differing distances between riders and drivers introduces differentiation, enabling multiple platforms to coexist in suitable markets. In such cases, entrants can leverage service variability to enter, potentially driving profits to zero and making the market highly contestable. The results challenge conventional wisdom, suggesting that having a large network may no longer guarantee survival and that platforms need credible commitment mechanisms to retain users. We discuss the reasons behind, shedding light on potential strategies that platform managers can follow while avoiding the ones that can inadvertently harm competition.

The full version can be found at https://papers.ssrn.com/sol3/papers.cfm?abstract_id=5119391

A typical goal for a gambler facing an online selection problem is to choose the best element, particularly in comparison to the best hindsight-optimal selection. This objective is nontrivial when there is high competition for top elements. For example, highly skilled job candidates are often recruited by top companies, leaving less competitive companies with the remaining candidates. This phenomenon introduces nontrivial correlations among the remaining candidates; hence, a gambler facing this problem with misaligned beliefs might act sub optimally if she expects a top element to still be available for selection. Motivated by these considerations, we introduce the residual prophet inequality (k-RPI) problem. In the k-RPI problem, we consider a finite sequence of n nonnegative independent random values with known distributions and a known integer 0 ≤ k ≤ n - 1. Before the gambler observes the sequence, the top k values are removed from the sequence whereas the remaining n - k values are streamed sequentially to the gambler. Upon observing a value, the gambler must decide irrevocably if to accept/reject a value without the possibility of revisiting past values. We study two variants of k-RPI, according to whether the gambler learns online of the identity of the variable that he sees (FI-model) or not (NI-model). Our main result is a randomized algorithm in the FI-model with competitive ratio of at least 1/(k + 2), which we show is tight. Our algorithm is data-driven and requires access only to the k + 1 largest values of a single sample from the n input distributions. In the NI-model, we provide a similar algorithm that guarantees a competitive ratio of 1/(2k + 2). We further analyze independent and identically distributed instances when k = 1. We build a single-threshold algorithm with a competitive ratio of at least 0.4901, and show that no single-threshold strategy can get a competitive ratio greater than 0.5464.

Full paper available at : https://www.dii.uchile.cl/jcorrea/papers/Manuscripts/2025CPSZ.pdf

Social connections provide various benefits, such as access to information, support, and collaboration, motivating individuals to form networks. However, in many social settings—like academic conferences or networking events—participants are initially strangers, making the networking process inherently anonymous and random. This paper incorporates anonymity into the canonical non-cooperative connections model ([Bala and Goyal, 2000]) to explore symmetric, mixed-strategy equilibria in network formation. We show that, for any trembling-hand perfect equilibrium, strategies can be interpreted as socialization effort and yield a random network, closely related to but distinct from classical Erdos-Renyi graphs. This provides a strategic microfoundation for random graphs. We fully characterize these equilibria and efficient networks for large populations as a function of connection costs.

We study when and how explanations of complex models can aid a decision maker (DM) whose payoff depends on a state of the world described by inputs and outputs. The DM cannot directly understand the true model linking inputs to outputs and must instead rely on an explanation from a class of simpler intelligible models. We analyze mappings from the infinite-dimensional space of possible true models to the finite-dimensional space of intelligible ones — what we call explainers — and focus on those that yield explanations which are robustly useful: that is, they allow the DM to improve their worst-case payoff across all models that are consistent with the explanation received.

When a decision maker cares about their average payoff across inputs, it is possible to offer an explanation that is robustly first-best across models using the canonical OLS approach. But no explainer can offer a useful explanation that is robust across both models and inputs, or even across both models and distributions of inputs. Moreover, the robust explanation offered by OLS is not robust to sampling error.

We apply these results to policy evaluation and AI regulation. For average-scenario decisions, OLS explanations can guide action when data are reliable. For tail risk—such as policies affecting the worst-off or AI failures under extreme conditions—explanations are uninformative unless paired with strong theoretical structure. In such settings, theory is needed to rule out models that explanations cannot distinguish. Direct recommendations about actions is another way to achieve optimal decisions, but only if they are aligned with the DM's preferences.

A full version of this paper can be found at https://papers.ssrn.com/sol3/papers.cfm?abstract_id=4723587.

Membership design involves allocating an economic good whose value to any individual depends on who else receives it. We introduce a framework for optimal membership design by combining an otherwise standard mechanism-design model with allocative externalities that depend flexibly on agents' observable and unobservable characteristics. Our main technical result demonstrates that the optimal mechanism offers distinct membership tiers—differing in prices and level of access—and that the number of membership tiers is increasing in the complexity of the externalities. This insight may help explain a number of mechanisms used in practice to sell membership goods, including musical artists charging below-market-clearing prices for concert tickets, certain admission procedures used by colleges concerned about the diversity of the student body, heterogeneous pricing tiers for access to digital communities, and the use of vesting and free allocation in the distribution of network tokens.

Full Paper: https://ssrn.com/abstract=4776110

We study the problem of finding an envy-free allocation of indivisible goods among agents with additive valuations. We focus on the fairness notion of envy-freeness up to any good (EFX). A central open question in fair division is whether EFX allocations always exist for any number of agents. While EFX has been established for three agents [Chaudhury et al., 2024] and for any number of agents with at most two distinct valuations [Mahara, 2023], its existence in more general settings remains open.

In this paper, we make significant progress by proving that EFX allocations exist for any number of agents when there are at most three distinct additive valuations. This result simultaneously generalizes both the three-agent case and the two-type case, settling an open question in the field (see [Mahara, 2023]).

Lindahl equilibrium is a solution concept for allocating a fixed budget across several divisible public goods. It always lies in the core, meaning that the equilibrium allocation satisfies desirable stability and proportional fairness properties. We consider a model where agents have separable linear utility functions over the public goods, and the output assigns to each good an amount of spending, summing to at most the available budget.

In the uncapped setting, each of the public goods can absorb any amount of funding. In this case, it is known that Lindahl equilibrium is equivalent to maximizing Nash social welfare, and this allocation can be computed by a public-goods variant of the proportional response dynamics. We introduce a new convex programming formulation for computing this solution and show that it is related to Nash welfare maximization through duality and reformulation. We then show that the proportional response dynamics is equivalent to running mirror descent on our new formulation, thereby providing a new and very immediate proof of the convergence guarantee for the dynamics. Our new formulation has similarities to Shmyrev's convex program for Fisher market equilibrium.

In the capped setting, each public good has an upper bound on the amount of funding it can receive, which is a type of constraint that appears in fractional committee selection and participatory budgeting. In this setting, existence of Lindahl equilibrium was only known via fixed-point arguments. The existence of an efficient algorithm computing one has been a long-standing open question. We prove that our new convex program continues to work when the cap constraints are added, and its optimal solutions are Lindahl equilibria. Thus, we establish that Lindahl equilibrium can be efficiently computed in the capped setting. Our result also implies that approximately core-stable allocations can be efficiently computed for the class of separable piecewise-linear concave (SPLC) utilities.

Full paper at https://arxiv.org/abs/2503.16414

Swap regret is a notion that has proven itself to be central to the study of general-sum normal-form games, with swap-regret minimization leading to convergence to the set of correlated equilibria and guaranteeing non-manipulability against a self-interested opponent. However, the situation for more general classes of games - such as Bayesian games and extensive-form games - is less clear-cut, with multiple candidate definitions for swap-regret but no known efficiently minimizable variant of swap regret that implies analogous non-manipulability guarantees.

In this paper, we present a new variant of swap regret for polytope games that we call "profile swap regret", with the property that obtaining sublinear profile swap regret is both necessary and sufficient for any learning algorithm to be non-manipulable by an opponent (resolving an open problem of Mansour et al., 2022). Although we show profile swap regret is NP-hard to compute given a transcript of play, we show it is nonetheless possible to design efficient learning algorithms that guarantee at most [EQUATION] profile swap regret in d-dimensional polytope games. Finally, we explore the correlated equilibrium notion induced by low-profile-swap-regret play, and demonstrate a gap between the set of outcomes that can be implemented by this learning process and the set of outcomes that can be implemented by a third-party mediator (in contrast to the situation in normal-form games).

In this paper, we introduce a novel approach to repeated auctions that accounts for bidders' temporal preferences, important in applications such as advertising. In our model, when a player wins an auction after not winning for ℓ rounds, she is awarded r(ℓ) utility and her goal is to maximize her total utility. r : ℕ → ℝ _≥0 satisfies the following properties. (i) The more rounds without a win, the higher the reward, i.e., r is weakly increasing. (ii) As more rounds pass without winning, the increase in reward becomes smaller, i.e., r is concave. The motivation behind these properties comes from the advertising literature, which states that an increased frequency of winning builds advertising effectiveness at a decreasing (but not declining) rate. The above properties guarantee that adding more wins to any sequence of winning intervals increases the total reward.

In addition to defining this model, we also develop online learning algorithms for a budget-limited player with such a reward model who participates in T second-price auctions with stationary competition. Our proposed learning algorithm achieves [EQUATION] regret with high probability against the optimal algorithm. This result holds in the contextual case, where before bidding, the player observes a context. The context includes a conversion rate (the probability of getting a conversion conditioned on winning the auction) and can be thought of as a value, implying that our model fully captures the classical model without spacing when r (ℓ) = 1 for all ℓ.

The full version of our paper can be found in https://arxiv.org/abs/2411.04843.

In many resource allocation settings, the value derived from resources depends on their usage history, with resources that have sufficient recovery or idle periods between allocations often providing greater utility or reward. This paper studies a resource allocation problem in which resource rewards recover over time following each use. Motivated by settings such as content recommendation, service platforms, and renewable energy management, we consider a dynamic matching problem with non-stationary arrivals, where customer types and matching preferences vary over time. Each arriving customer must be immediately and irrevocably matched to a resource or lost. The reward from matching a resource is non-decreasing in the time since its previous use. The goal is to maximize the expected reward collected from all arrivals over a finite time horizon.

Computing the optimal policy for this problem is computationally intractable as the number of resources grows. While the greedy policy achieves at least 1/2 of the optimal expected revenue for subadditive reward functions, it performs arbitrarily poorly for general non-decreasing reward functions. To address this, we propose an approximate policy based on a novel value function approximation that achieves a 1/3 performance guarantee for general non-decreasing reward functions. We show that for the special case of concave reward functions as well as the special case where all resources are reusable, the approximate policy's guarantee improves to 1/2. Our approximation leverages resource-specific dynamic programs that incorporate each resource's recovery level as a state, a framework that we believe to be new to the literature.

A full version of this paper can be found at https://ssrn.com/abstract=5046898.

We consider the problem of fair allocation of m indivisible goods to n agents with either subadditive or XOS valuations, in the arbitrary entitlements case. As fairness notions, we consider the anyprice share (APS) ex-post, and the maximum expectation share (MES) ex-ante.

We observe that there are randomized allocations that ex-ante are at least 1/2-MES in the subadditive case and (1 - 1/e)-MES in the XOS case. Our more difficult results concern ex-post guarantees. We show that [EQUATION]-APS allocations exist in the subadditive case, and 1/6-APS allocations exist in the XOS case.

For the special case of equal entitlements, we show 4/17-APS allocations for XOS.

Our results are the first for subadditive and XOS valuations in the arbitrary entitlements case, and also improve over the previous best results for the equal entitlements case.

We study the design of credible auctions when a seller has private information about her costs and cannot commit to public announcements. Akbarpour and Li [2020] show that when the reserve price is common knowledge, the first-price auction is the unique mechanism that is simultaneously optimal, static, and credible. Our paper demonstrates that this conclusion is overturned when the seller is privately informed about her cost, a common feature in many real-world markets.

Our first main result is a strong impossibility theorem: no static mechanism can be both optimal and credible. This is driven by a novel class of dynamic deviations. An informed seller running an optimal first-price auction (where the reserve price depends on her cost) has an incentive to deviate. For example, a low-cost seller can interact with one bidder, and upon receiving a high bid, turn to a second bidder and pretend to be a high-cost type, setting a new, higher reserve price based on the first bid. This deviation is undetectable to the second bidder and strictly profitable. We show that the dynamic English (ascending) auction restores both optimality and credibility, even when communication is private and bilateral. The English auction is immune to the dynamic threat because the seller can always "go back" and in fact find it optimal to continue as if it were an English auction even after such a deviation. In contrast, other dynamic formats like the optimal Dutch auction may not be credible.

For settings where static auctions are nonetheless necessary, we characterize the entire class of credible, symmetric, static mechanisms. They are all first-price auctions with two key features: (1) a public bid space that is independent of the seller's cost, preventing her from signaling her type; and (2) a secret reserve, where the seller's cost is incorporated only ex-post via a walk-away option if the highest bid is too low. Our results provide a new rationale for the prevalence of dynamic mechanisms in informal and decentralized auctions.

The full paper can be found at https://martinobanchio.github.io/files/DTCA.pdf.

We develop a method to recover primitives from data generated by artificial intelligence (AI) agents in strategic environments such as online marketplaces and auctions. Building on the design of leading online learning AIs, we assume that agents minimize their regret. Under asymptotic no regret, we show that the time average of play converges to the set of Bayes coarse correlated equilibrium (BCCE) predictions. Our econometric procedure is based on BCCE restrictions and convergence rates of regret-minimizing AIs. We apply the method to pricing data in a digital marketplace for used smartphones. We estimate sellers' cost distributions and find lower markups than in centralized platforms.

Full paper available at: https://papers.ssrn.com/sol3/papers.cfm?abstract_id=4269273

We consider the fundamental problem of allocating T indivisible items that arrive over time to n agents with additive preferences, with the goal of minimizing envy. This problem is tightly connected to the online multicolor discrepancy problem: vectors v₁,...,v_T ∈ ℝ^d with ||v_i||₂ ≤ 1 arrive online and must be, immediately and irrevocably, assigned to one of n colors to minimize [EQUATION] at each step, where Sℓ is the set of vectors having color ℓ. The special case of n = 2 is called online vector balancing. It is known that envy minimization reduces to multicolor discrepancy minimization. For an adaptive adversary, both problems have the same optimal bound: [EQUATION]; it is not known, however, whether this matches for weaker adversaries. Against an oblivious adversary, Alweiss et al. [2021] give a bound of O (log T), with high probability, for online multicolor discrepancy. Recently, Kulkarni et al. [2024] improve this to a tight [EQUATION] bound for online vector balancing. However, it has remained an open problem whether a [EQUATION] bound is possible for multicolor discrepancy. Furthermore, these results imply the state-of-the-art upper bounds for online envy minimization (for an oblivious adversary) for n and two agents, respectively; it is open whether better bounds are possible. We resolve all the aforementioned open problems. We establish that online envy minimization is, in fact, equivalent to online multicolor discrepancy for oblivious adversary: we give an [EQUATION] bound, for multicolor discrepancy, and a lower bound of [EQUATION] for envy minimization, resolving both problems. For weaker adversaries we prove that the two problems are no longer equivalent. Against an i.i.d. adversary, for online vector balancing, we give a [EQUATION] lower bound, while for envy minimization, we give an algorithm that guarantees a constant upper bound. Full version: https://arxiv.org/abs/2502.14624.

We study online combinatorial allocation problems in the secretary setting, under interdependent values. In the interdependent model, introduced by Milgrom and Weber (1982), each agent possesses a private signal that captures her information about an item for sale, and the value of every agent depends on the signals held by all agents. Mauras, Mohan, and Reiffenhäuser (2024) were the first to study interdependent values in online settings, providing constant-approximation guarantees for secretary settings, where agents arrive online along with their signals and values, and the goal is to select the agent with the highest value.

In this work, we extend this framework to combinatorial secretary problems, where agents have interdependent valuations over bundles of items, introducing additional challenges due to both combinatorial structure and interdependence. We provide 2e-competitive algorithms for a broad class of valuation functions, including submodular and XOS functions, matching the approximation guarantees in the single-choice secretary setting. Furthermore, our results cover the same range of valuation classes for which constant-factor algorithms exist in classical (non-interdependent) secretary settings, while incurring only an additional factor of 2 due to interdependence. Finally, we extend our study to strategic settings, and provide a 4e-competitive truthful mechanism for online bipartite matching with interdependent valuations, again meeting the frontier of what is known, even without interdependence.

We study the social efficiency of bilateral trade between a seller and a buyer. In the classical Bayesian setting, the celebrated Myerson-Satterthwaite impossibility theorem states that no Bayesian incentive-compatible, individually rational, and budget-balanced mechanism can achieve full efficiency. As a counterpoint, Deng, Mao, Sivan, and Wang (STOC 2022) show that if pricing power is delegated to the right person (either the seller or the buyer), the resulting mechanism can guarantee at least a constant fraction of the ideal (yet unattainable) gains from trade.

In practice, the agent with pricing power may not have perfect knowledge of the value distribution of the other party, and instead may rely on samples of that distribution to set a price. We show that for a broad class of sampling and pricing behaviors, the resulting market still guarantees a constant fraction of the ideal gains from trade in expectation. Our analysis hinges on the insight that social welfare under sample-based pricing approximates the seller's optimal revenue—a result we establish via a reduction to a random walk.

Digital businesses are increasingly adopting data-sharing practices, granting employees broader access to internal datasets to improve operational efficiency. Yet, many organizations may be sharing too much: a recent survey found that 33% of firms give employees access to all company data, and another 35% grant more access than is strictly necessary for their roles. Such overexposure increases cybersecurity risk, particularly when adversaries exploit employee access (e.g., through phishing attacks). Such overexposure exposes firms to cybersecurity risks such as data breaches

We study this problem using a game-theoretic model featuring a firm and an adversary. The firm (i) chooses a data access allocation—specifying which employees have access to which datasets—and (ii) sets a global cybersecurity protection level. While granting access generates economic value, it also increases the potential damage if an adversary succeeds. The attacker may be either opportunistic (random) or strategic (targeting the most valuable employees). The firm does not observe the attacker's type but knows the probability of each.

Our analysis shows that giving full access to all employees is only optimal when the adversary's attack strength is sufficiently low. As the threat intensifies, the firm must restrict access—either selectively or uniformly—depending on its underlying technology. With vertical differentiation (i.e., some employees and datasets are more valuable), the firm adopts a hierarchical structure. With horizontal differentiation (i.e., employees specialize in certain datasets), the firm compartmentalizes access, choosing a structure aligned with Zero-Trust principles.

To characterize access structures, we define two summary statistics: the average access level—the expected number of datasets per employee—and the access inequality—a measure of how unevenly access is distributed across employees. As the adversary's strength increases, the average access level declines, while access inequality follows an inverse U-shape: it initially rises as the firm concentrates access among a small subset of employees, then declines as restrictions are applied more uniformly. Protection investment may decrease once access is sufficiently limited. As the probability of facing a strategic (rather than opportunistic) adversary increases—that is, as adversarial sophistication rises—firms reduce access inequality and may even expand overall access. Finally, when employee productivity is highly concentrated, the firm benefits from allocating more data to top performers while relying less on protection.

Our results highlight how firms should coordinate data access and protection decisions in response to both external and internal factors. We show when hierarchical, compartmentalized, or mixed access structures emerge, and how these structures adapt to changes in adversarial strength and sophistication, as well as in the distribution of employee productivity.

Full paper available at: https://papers.ssrn.com/sol3/papers.cfm?abstract_id=4293509

We initiate the study of the prophet inequality problem through the resource augmentation framework in scenarios when the values of the rewards are correlated. Our goal is to determine the number of additional rewards an online algorithm requires to approximate the maximum value of the original instance. While the independent reward case is well understood, we extend this research to account for correlations among rewards. Our results demonstrate that, unlike in the independent case, the required number of additional rewards for approximation depends on the number of original rewards, and that block-threshold algorithms, which are optimal in the independent case, may require an infinite number of additional rewards when correlations are present. We develop asymptotically optimal algorithms for the following three scenarios: (1) where rewards arrive in blocks corresponding to the different copies of the original instance; (2) where rewards across all copies are arbitrarily shuffled; and (3) where rewards arrive in blocks corresponding to the different copies of the original instance, and values within each block are pairwise independent rather than fully correlated.

We consider a package assignment problem with multiple units of indivisible items. The seller can specify preferences over partitions of their supply between buyers as packaging costs. We propose incremental costs together with a graph that defines cost interdependence to express these preferences. This facilitates the use of linear programming to characterize Walrasian equilibrium prices. Firstly, we show that equilibrium prices are uniform, anonymous, and linear in packages. Prices and marginal gains exhibit a nested structure, which we characterize in closed form for complete graphs. Secondly, we provide sufficient conditions for the existence of package-linear competitive prices using an ascending auction implementation. Our framework of partition preferences ensures fair and transparent dual pricing and admits preferences over the concentration of allocated bundles in the market. The full paper is available at https://arxiv.org/abs/2306.14247.

This paper investigates the role of mediators in Bayesian games by examining their impact on social welfare through the price of anarchy (PoA) and price of stability (PoS). Mediators can communicate with players to guide them toward equilibria of varying quality, and different communication protocols lead to a variety of equilibrium concepts collectively known as Bayes (coarse) correlated equilibria. To analyze these equilibrium concepts, we consider a general class of Bayesian games with submodular social welfare, which naturally extends valid utility games and their variant, basic utility games. These frameworks, introduced by Vetta (2002), have been developed to analyze the social welfare guarantees of equilibria in games such as competitive facility location, influence maximization, and other resource allocation problems.

We provide upper and lower bounds on the PoA and PoS for a broad class of Bayes (coarse) correlated equilibria. Central to our analysis is the strategy representability gap, which measures the multiplicative gap between the optimal social welfare achievable with and without knowledge of other players' types. For monotone submodular social welfare functions, we show that this gap is 1 - 1/e for independent priors and [EQUATION] for correlated priors, where n is the number of players. These bounds directly lead to upper and lower bounds on the PoA and PoS for various equilibrium concepts, while we also derive improved bounds for specific concepts by developing smoothness arguments. Notably, we identify a fundamental gap in the PoA and PoS across different classes of Bayes correlated equilibria, highlighting essential distinctions among these concepts.

The full version is available at http://arxiv.org/abs/2506.02655.

Prediction problems are ubiquitous in the economy. To give a few examples, firms selling products often want to predict customers' willingness to pay and may use business analytics tools to do so. In science and engineering, researchers want to predict the viability of compounds in domains ranging from drug discovery to materials science. Campaigns and observers want to predict elections, and may commission polls to do so.

Making quantitative predictions usually involves collecting relevant data and training statistical models based on that data. While firms, organizations, and individuals can conduct this modeling internally, many rely on external firms for these services. In this paper, we provide an economic theory analysis of settings where firms sell prediction models. Our focus is on how market structure and welfare depend on the statistical properties of the models available to firms.

We consider a consumer who faces a prediction problem. The consumer's utility is the negative of the mean squared error of their prediction (or a fixed outside option). To make predictions, the consumer purchases models from firms. These firms decide whether to enter, choose models to train on their datasets, and set prices for the resulting predictions. We take an abstract approach to model choice that can accommodate simple models such as linear or ridge regression but also allows for more complex models. Importantly for our analysis, the consumer can use a single model but can also purchase multiple models and use a weighted average of these models.

We show that market outcomes given model choices can be expressed in terms of the bias-variance decompositions of the models that firms sell. When a single firm enters the market, it can extract all surplus. When multiple firms enter, each is paid the marginal value of combining their model with other models. Hence, our framework yields simple mappings from the statistical structures of firms' models to outcomes.

Our analysis delivers two main findings. First, we show that identical firms servicing identical consumers will often choose differentiated models. Model differentiation always benefits firms at the expense of the consumer. The reason is that models with different biases can have a higher degree of complementarity, allowing firms to charge higher prices.

Second, an incumbent firm may choose an excessively biased model, or overinvest in variance reduction, to deter entry. The incumbent firm has incentives to distort its model to reduce the profits of potential entrants. This gives rise to inefficient market structures as well as inefficient model choices.

The paper can be found in this link: https://arxiv.org/abs/2503.02946.

We study monotone persuasion in the linear case, where posterior distributions over states are summarized by their mean. We develop a novel methodological approach to solve the two leading cases where optimal unrestricted signals can be nonmonotone. First, if the objective is s-shaped and the state is discrete, then optimal monotone signals are upper censorship, whereas optimal unrestricted signals may require randomization. Second, if the objective is m-shaped and the state is continuous, then optimal monotone signals are interval disclosure, whereas optimal unrestricted signals may require nonmonotone pooling. Unlike with unrestricted persuasion, the value of monotone persuasion can decrease with the informativeness of the prior. We illustrate our results with an application to media censorship.

The full paper is available at https://arxiv.org/abs/2412.14400.

We study the utilitarian distortion of social choice mechanisms under the recently proposed learning-augmented framework where some (possibly unreliable) predicted information about the preferences of the agents is given as input. In particular, we consider two fundamental social choice problems: single-winner voting and one-sided matching. In these settings, the ordinal preferences of the agents over the alternatives (either candidates or items) is known, and some prediction about their underlying cardinal values is also provided. The goal is to leverage the prediction to achieve improved distortion guarantees when it is accurate, while simultaneously still achieving reasonable worst-case bounds when it is not. This leads to the notions of consistency and robustness, and the quest to achieve the best possible tradeoffs between the two. We show tight tradeoffs between the consistency and robustness of ordinal mechanisms for single-winner voting and one-sided matching, for different levels of information provided as prediction.

The study of rational queueing has a long and distinguished history focused on individuals' preference to avoid waiting. Surprisingly, there are settings in which some potential arrivals (which we also refer to as requests) derive utility from waiting and disutility from service. Our primary example is the U.S. affirmative asylum process. In this context, applicants obtain a work permit while waiting for an asylum interview; hence, if the (expected) wait is long enough, then even an applicant who knows that their application will be denied and lead to deportation proceedings, may find it in their interest to apply and thus benefit from legally working during the wait. Similar dynamics could occur in other settings like content moderation in social networks.

The common thread of these examples is the potentially self-exciting queue: when wait times are long, many arrivals are incentivized to join, and wait times become even longer. However, the system designer usually wants to avoid a large backlog. Indeed, the US Citizenship and Immigration Services (USCIS) mostly schedules asylum interviews in a Last-In-First-Out (LIFO) manner with the explicit goal of dissuading applicants with non-meritorious cases trying to exploit the long backlog. Despite this interesting scheduling choice in practice, and the potential prevalence of similar settings in other applications, the existing literature on rational queueing lacks frameworks to study the impact of wait-driven requests.

Motivated by this gap in the literature, we formalize a dynamical system where in each round, a given scheduling policy and a realized request rate determine the wait time distribution in a fluid queueing system. Observing the expected benefit from waiting in one round, requests update their decisions, setting the request rate for the next round. Assuming a concave benefit function from waiting, alongside general conditions, we prove that, for minimizing the backlog, LIFO is most effective while First-In-First-Out (FIFO) is least effective among all work-conserving policies. Moreover, we show that the dynamical system exhibits metastability: for either FIFO or LIFO, the system converges to either a zero-wait or a congested equilibrium.

Although some asylum practitioners support the use of LIFO, critics often admonish the real-world use of LIFO for its failure to maintain FIFO's order fairness: earlier requests should get earlier service. Our results demonstrate this trade-off between LIFO and FIFO. But we also show limitations of hybrid policies, which probabilistically follow either LIFO or FIFO, in navigating the trade-off between LIFO's efficiency and FIFO's fairness. Our work formalizes the concept of order fairness in queueing systems with abandonment and demonstrates that hybrid policies can be Pareto-dominated by LIFO: they may have both longer backlog and worse order fairness. Finally, we use real-world data on the scheduling of affirmative asylum applications to evaluate the change in fairness over the past 20 years under different policies.

A full version of this paper can be found at https://papers.ssrn.com/sol3/papers.cfm?abstract_id=5284321.

We consider a model with three economic agents: a certifier, a sender and a receiver (e.g., test provider, student and school). The sender has imperfect private information about the state of the world (e.g., student's ability), assumed to be binary. The certifier offers a menu of tests with different prices, from which the sender chooses her preferred option. The test generates a certificate which is informative about the state and therefore guides the receiver's action (e.g., admission decision), also assumed to be binary. The sender would like the receiver to always take the high action, but the receiver would only like to do so if the state is high. The test may provide information to the receiver through two channels. The first channel is informativeness of actual tests. Second, selection of different types into different tests conveys information, as the receiver updates her belief about the state based on which test the sender chooses.

The main theorem identifies the revenue-maximizing menu. First, it has a monotone structure such that sender types are partitioned into convex intervals and those who belong to a common group purchase a common test. Second, the menu exhibits the cutoff structure that sender purchases a test if and only if her belief is above a lower threshold, and she buys a Kamenica-Gentzkow style test if her belief exceeds an upper threshold. Third, we observe that all tests in the menu are equally informative (in certain sense), and those who purchase a test are indifferent among all options in the menu. Finally, the receiver obtains zero surplus.

The optimality of this structure depends on how the sender's test selection reveals additional information to the receiver. We show that if the certifier could conceal which test the sender selects, the optimal menu could look very different. Under a certain condition on the distribution of the sender's belief, it would become optimal to segment the market by offering two tests with heterogeneous informativeness: a fully informative, cheaper test sold to high sender types and an uninformative, more expensive test chosen by middle sender types.

The full paper is available at: https://papers.ssrn.com/sol3/papers.cfm?abstract_id=5062549

Multi-dimensional mechanism design problems stand out as some of the most difficult problems in contemporary economic theory. Despite their clear importance in applications and more than four decades of research in economics and computer science, they remain poorly understood.

This paper characterizes the structure of optimal mechanisms for a large class of multi-dimensional mechanism design problems. Specifically, we consider any problem where a mechanism designer and an agent have linear preferences over a space of allocations and where these preferences depend on the agent's private information. This setup subsumes as a special case the well-known multi-good monopoly problem but also economically interesting problems without transfers such as delegation or veto bargaining problems.

In this class of problems, the mechanisms that are optimal for generic instances of the designer's utility maximization problem are extreme points of the set of incentive-compatible (IC) mechanisms. Our main results comprehensively characterize these extreme points, significantly extending earlier results by Manelli and Vincent [2007] in both breadth and depth. To do so, we introduce novel techniques from the mathematical literature on indecomposable convex sets.

The main insight is that in every problem with one-dimensional types, the set of extreme points admits a tractable description, whereas in every problem with multi-dimensional types, the set of extreme points is virtually as rich as the set of all incentive-compatible mechanisms. We show that this insight persists when considering the maximizers of families of objective functionals that naturally arise in applications. For example, in the multi-good monopoly problem, the set of mechanisms that uniquely maximize revenue for some value distribution is dense in the set of mechanisms that make non-positive transfers. These findings cast doubt on the ability of the standard Bayesian mechanism design framework to make meaningful parameter-independent predictions. A full version of this paper can be found at https://arxiv.org/abs/2412.00649.

The delegated choice problem, introduced by Armstrong and Vickers (ECTA'10), involves a principal delegating a decision-making of selecting an element among n to an agent with potentially misaligned utility. To mitigate the agent's selfish behavior, the principal commits to acceptable sets and utilities in advance. Kleinberg and Kleinberg (EC'18) observed a novel connection to prophet inequality, a central problem in optimal stopping theory, stating that the delegated choice problem is equivalent to a version of prophet inequality with oblivious stopping rules in the single choice setting. This amplifies the significance of prophet inequality, originally cemented by its fruitful connection to numerous problems including posted pricing in the online auction for digital goods/multi-dimensional mechanisms, stochastic optimization, secretary problem, and Pandora's box. A fundamental question in this context is, whether the connection between prophet inequality and delegated choice follows the same path even under arbitrary combinatorial constraints.

We answer this question negatively by providing the first provable separation of prophet inequality and delegated choice for downward-closed constraints. Namely, we obtain a 0.1098-approximate mechanism for the delegated choice under downward-closed constraint, which implies a strict separation between the two problems since prophet inequality does not allow constant approximation under downward-closed constraint as shown by Rubinstein (STOC'16). Up to matroid constraint, however, we show that the connection carries over, which implies several constant approximate mechanisms for various matroid constraints. We complement this result by proving that matroid structure is even necessary to maintain such connection, thereby exactly characterizing the regime for such correspondence. We finally examine the power of knowing the agent's utility distribution, which corresponds to order-hinted algorithms that know the distribution of the arrival order of elements in prophet inequality. Interestingly, we prove that order-hinted non-adaptive algorithms (and induced delegation mechanisms) are not strictly better than order-oblivious non-adaptive algorithms (and induced delegation mechanisms), i.e., the gain from knowing the elements' arrival distributions is negligible.

We initiate the study of how auction design affects the division of surplus among bidders. We propose a parsimonious measure for equity and apply it to standard auctions for homogeneous goods. Our surplus-equitable mechanism is efficient, Bayesian-Nash incentive compatible, and achieves surplus parity among winners ex-post. The uniform-price auction is equity-optimal if and only if bidders have a common value. Against intuition, the pay-as-bid auction is not always equity-preferred if bidders have private values. In auctions with price mixing between pay-as-bid and uniform prices, we provide prior-free bounds on the equity-preferred pricing under a common regularity condition on signals. The full paper is available at https://arxiv.org/abs/2403.07799.

We study resale platforms, an emerging type of online marketplaces in developing countries. Resale platforms are designed for individuals (resellers) to sell products to others as opposed to buying for themselves, enabling them to supplement their income by earning a margin on the transactions they generate. One challenge these platforms face is that competition among resellers may emerge as more of them join the platform, as their social circles increasingly overlap.

Our paper investigates the mechanisms by which competition affects resellers and the role of the platform's design in shaping this relationship. We combine analytical modeling with empirical analysis. Our model captures the resellers' interactions with the platform (in searching for products to sell) and with consumers (in offering these products for purchase); the level of competition depends on the extent to which consumers receive offers from multiple resellers. We find that as competition intensifies, resellers not only lower their margins but also reduce the effort they exert in searching for products to sell. We empirically validate these equilibrium predictions using data from a major platform: as competition increases, resellers earn lower margins and reduce the number of products they view while browsing on the app, which we interpret as lower search effort.

Finally, we explore two platform interventions that aim to benefit resellers: centralizing margin decisions (a practice adopted by several platforms) and optimizing its product ranking algorithm. Despite constraining their choices, centralization tends to benefit resellers to a greater extent as it mitigates the competitive pressure on margins, and shifts resellers to compete only in terms of the selection of products they offer. Our work offers insights to guide key design choices for resale platforms, aiming to foster sustainable online entrepreneurship in developing economies.

The full paper is available at: https://papers.ssrn.com/sol3/papers.cfm?abstract_id=4753023

As AI technologies improve, people are increasingly willing to delegate tasks to AI agents. In many cases, the human decision-maker chooses whether to delegate to an AI agent based on properties of the specific instance of the decision-making problem they are facing. Since humans typically lack full awareness of all the factors relevant to this choice for a given decision-making instance, they perform a kind of categorization by treating indistinguishable instances - those that have the same observable features - as the same. In this paper, we define the problem of designing the optimal algorithmic delegate in the presence of categories. This is an important dimension in the design of algorithms to work with humans, since we show that the optimal delegate can be an arbitrarily better teammate than the optimal standalone algorithmic agent. The solution to this optimal delegation problem is not obvious: we discover that this problem is fundamentally combinatorial, and illustrate the complex relationship between the optimal design and the properties of the decision-making task even in simple settings. Indeed, we show that finding the optimal delegate is computationally hard in general. However, we are able to find efficient algorithms for producing the optimal delegate in several broad cases of the problem, including when the optimal action may be decomposed into functions of features observed by the human and the algorithm. Finally, we run computational experiments to simulate a designer updating an algorithmic delegate over time to be optimized for when it is actually adopted by users, and show that while this process does not recover the optimal delegate in general, the resulting delegate often performs quite well.

Coordination lies at the heart of many economic phenomena. A well-known example is currency crises, in which traders decide whether to launch a speculative attack. On one hand, shocks to the currency's fundamentals can propagate: as more traders attack, the central bank's foreign reserves are depleted, which in turn encourages further attacks as traders seek to exploit a weakening currency. On the other hand, shocks can also fizzle out: traders may quickly learn that the central bank's balance sheet is strong, causing pessimism to dissipate and attacks to subside. When do shocks propagate, and when do they fizzle out? In particular, how do these outcomes depend on the speed at which traders learn about the fundamental?

Motivated by these questions, we propose a model of inertial coordination games—dynamic coordination games where players repeatedly decide whether to take a risky action. The payoff from this risky action depends on (i) a persistent fundamental; and (ii) an endogenous component that depends on others' past play. Players receive private signals about the persistent fundamental over time and form beliefs about the current state. Notably, the current state depends on past play, which in turn depends on past beliefs about play yet farther back into the past. Thus, expectations about histories shape behavior in the present which, in turn, drives the evolution of future states and future play.

Our main result develops a tight connection between the speed of learning and limit aggregate play: the risk-dominant action is played in the limit if and only if posterior precisions grow sub-quadratically. This has sharp implications for the long-run propagation of shocks. With slow (sub-quadratic) learning, limit play exhibits history independence: initial shocks have no lasting effect, and limit play is determined solely by fundamentals. By contrast, with fast (super-quadratic) learning, limit play is history dependent: initial shocks can be self-fulfilling, and whether they propagate depends jointly on fundamentals, the size of the shock, and the speed of learning. Our results offer a novel perspective on whether 'history' or 'expectations' shape long-run coordination outcomes: in our model, expectations about histories is what matters for whether self-fulfilling spirals occur.

Finally, we show that the speed of learning also shapes the path of play, focusing on the case of sub-quadratic learning. When signals are precise, aggregate play exhibits a sudden transition from nearly all players choosing the non-risk-dominant action to nearly all players choosing the risk-dominant action. In contrast, when signals are noisy, the transition is gradual, with the share of players choosing the risk-dominant action increasing gradually over time. This suggests that "spikes" in aggregate behavior (such as a sudden and massive sell-off of a currency) can be consistent with transition to limit equilibrium play, and need not indicate an "equilibrium shift."

A full version of this paper can be found at https://arxiv.org/abs/2409.08145.

A powerful feature in mechanism design is the ability to irrevocably commit to the rules of a mechanism. Commitment is achieved by public declaration, which enables players to verify incentive properties in advance and the outcome in retrospect. However, public declaration can reveal superfluous information that the mechanism designer might prefer not to disclose, such as her target function or private costs. Avoiding this may be possible via a trusted mediator; however, the availability of a trustworthy mediator, especially if mechanism secrecy must be maintained for years, might be unrealistic. We propose a new approach to commitment, and show how to commit to, and run, any given mechanism without disclosing it, while enabling the verification of incentive properties and the outcome—all without the need for any mediators. Our framework is based on zero-knowledge proofs—a cornerstone of modern cryptographic theory. Applications include both private-type settings such as auctions and private-action settings such as contracts, as well as non-mediated bargaining with hidden yet binding offers.

A full version of this paper can be found at https://arxiv.org/abs/2302.05590.

We study the impact on consumer financial health of the widespread legalization of sports betting in the United States, which began in 2018. We use the state-by-state rollout of legal betting combined with a large representative dataset on consumer credit outcomes to identify effects. We find that states with legal sports betting, particularly online or mobile betting, experienced small decreases in credit scores, as well as large increases in some indicators of excessive debt, including bankruptcies and debt sent to collection agencies. These adverse outcomes are overwhelmingly concentrated among consumers with poor financial health prior to gambling legalization.

Full paper available at: https://papers.ssrn.com/sol3/papers.cfm?abstract_id=4903302

We study the problem of estimating Dynamic Discrete Choice (DDC) models, also known as offline Maximum Entropy-Regularized Inverse Reinforcement Learning (offline MaxEnt-IRL) in machine learning. The objective is to recover reward or Q functions that govern agent behavior from offline behavior data. In this paper, we propose a globally convergent gradient-based method for solving these problems without the restrictive assumption of linearly parameterized rewards. The novelty of our approach lies in introducing the Empirical Risk Minimization (ERM) based IRL/DDC framework, which circumvents the need for explicit state transition probability estimation in the Bellman equation. Furthermore, our method is compatible with non-parametric estimation techniques such as neural networks. Therefore, the proposed method has the potential to be scaled to high-dimensional, infinite state spaces. A key theoretical insight underlying our approach is that the Bellman residual satisfies the Polyak-Łojasiewicz (PL) condition-a property that, while weaker than strong convexity, is sufficient to ensure fast global convergence guarantees. Through a series of synthetic experiments, we demonstrate that our approach consistently outperforms benchmark methods and state-of-the-art alternatives.

We propose and analyze a new policy gradient algorithm for reinforcement learning (RL), relative Monte Carlo (rMC). The method estimates policy gradients using relative returns between a root sample path and counterfactual simulated paths, instantiated by taking a different action from the root. The resulting gradient estimate is both unbiased and has low variance. rMC is compatible with any differentiable policy, including neural networks, and is guaranteed to converge even for infinite horizon tasks. The method utilizes common random number coupling of the simulated paths to reduce variance and increase the likelihood that paths merge, thereby reducing simulation complexity. It is particularly well suited to discrete event control problems where actions have a "local" effect, such as queueing, supply chain, or ride-hailing problems. Indeed, we show that it has provably low complexity for a family of inventory control problems. Numerical tests on a challenging inventory and fulfillment problem show that compared to traditional RL approaches, rMC converges in far fewer iterations (lower variance), has better policy performance (unbiased), and requires minimal hyperparameter tuning.

In this paper, we develop a model of in-kind redistribution where consumers participate in either a private market or a government-designed program, but not both. We characterize when a social planner, seeking to maximize weighted total surplus, can strictly improve upon the laissez-faire outcome. We show that the optimal mechanism consists of three components: a public option, nonlinear subsidies, and laissez-faire consumption. We quantify the resulting distortions and relate them to the correlation between consumer demand and welfare weights. Our findings reveal that while private market access constrains the social planner's ability to redistribute, it also strengthens the rationale for non-market allocations.

A full version of this paper can be found at: https://arxiv.org/pdf/2409.06112.

How should a principal incentivize an agent to explore risky alternatives when the principal has limited knowledge of these alternatives? We study this question in a robust moral hazard model in which the agent sequentially searches over projects to generate a prize. At the outset, the principal only knows one of these projects, and evaluates contracts by their worst-case performance.

Our main result characterizes the set of robustly optimal contracts and shows that a minimum debt level is essential. The key observation driving this result is a parallel between the debt contract and the index used to guide the agent's search strategy. Withholding payment until the prize exceeds a certain threshold incentivizes the agent to "swing for the fences" and prevents the agent from terminating search too early. This result contrasts with prior robust contracting literature, where linear contracts are typically optimal. While linear contracts guard the principal against risk in static moral hazard settings, they discourage exploration in our sequential search environment.

The class of optimal contracts includes pure debt, convertible debt, and capped-earnout debt. We study extensions where each contract format emerges uniquely: pure debt, under efficiency considerations or repeated sampling; convertible debt, under concerns of principal moral hazard; and capped-earnout debt, when the agent is more risk-averse than the principal. The robustness of our debt-contract insight demonstrates its practical relevance in a broad range of environments including innovation financing, publishing, and venture capital.

The full paper is available at https://arxiv.org/abs/2504.17948

This paper proposes a novel model of multidimensional screening, where a candidate (she) with two attributes—training and talent—chooses how much hard evidence of training to present. Then, the evaluator (he) possibly verifies at a cost the value of a composite measure of the candidate's training and talent before deciding whether to accept or reject the candidate. The candidate cannot unilaterally provide evidence of talent. The composite measure is increasing in both training and talent, and the evaluator (weakly) values both training and talent in the candidate. If the evaluator is going to verify the value of the composite measure, the candidate may have incentives to withhold evidence of training—although the evaluator values training—to influence how the evaluator interprets the composite measure. Particularly, she may want to withhold evidence of training to make the evaluator attribute the composite measure to talent instead, thereby overestimating her talent.

This problem arises when the composite measure is less sensitive to talent than talent is valuable to the evaluator. In that case, the optimal evaluation scheme never combines evidence and verification in the evaluation of a certain candidate. Rather, it asks for evidence of training only to accept a high-training candidate without verification. The optimal mechanism favors high- over low-training candidates: (i) It accepts some high-training candidates—including unworthy ones—without verifying their composite measure but rather only by asking them for a certain level of evidence of training; and (ii) among candidates who do not meet that level of evidence, (iia) it accepts (after verification) some unworthy candidates with high training but low talent while (iib) rejecting some worthy candidates with high talent but low training.

Remarkably, this is the structure of the optimal mechanism even when the evaluator only values talent. The evaluator still optimally favors high-training candidates even though training is worthless to him. He does so because of two forces: (i) to save on verification costs by accepting high-training candidates without verifying their composite measure and (ii) due to the strategic incentives of candidates to withhold evidence of training when the evaluator verifies the value of a composite measure that is under-sensitive to talent. The two forces are complements in inducing errors in favor of high- and against low-evidence candidates. Namely, the second force exacerbates the errors due to the verification cost by decreasing the effectiveness of verification, thereby pushing the evaluator to accept high-training candidates without verifying their composite measure to save on verification costs.

The full paper is available at: https://orestisvravosinos.netlify.app/uploads/JMP_Orestis_Vravosinos.pdf

We investigate stochasticity in choice behavior across diverse decisions. Each decision is modeled as a menu of actions with associated outcomes, and a stochastic choice rule assigns probabilities to actions based on the outcome profile. We characterize rules whose predictions are not affected by whether or not additional, irrelevant decisions are included in the model. Our main result is that such rules form the parametric family of mixed-logit rules.

A full version of this paper can be found at https://arxiv.org/abs/2312.04827.

We study a matching problem between agents and public goods, in settings without monetary transfers. Since goods are public, they have no capacity constraints. There is no exogenously defined budget of goods to be provided. Rather, each provided good must justify its cost by being utilized by sufficiently many agents, leading to strong complementarities in the "preferences" of goods. Furthermore, goods that are in high demand given other already-provided goods must also be provided. The question of the existence of a stable solution (a menu of public goods to be provided) exhibits a rich combinatorial structure. We uncover sufficient conditions and necessary conditions for guaranteeing the existence of a stable solution, and derive both positive and negative results for strategyproof stable matching.

A full version of this paper can be found at https://arxiv.org/abs/2402.11370.

In approval-based budget division, a budget needs to be distributed to some candidates based on the voters' approval ballots over these candidates. In the pursuit of simple, well-behaved, and approximately fair rules for this setting, we introduce the class of sequential payment rules, where each voter controls a part of the budget and repeatedly spends his share on his approved candidates to determine the final distribution. We show that all sequential payment rules satisfy a demanding population consistency notion and we identify two particularly appealing rules within this class called the maximum payment rule (MP) and the 1/3-multiplicative sequential payment rule (1/3-MSP). More specifically, we prove that (i) MP is, apart from one other rule, the only monotonic sequential payment rule and gives a 2-approximation to a fairness notion called average fair share, and (ii) 1/3-MSP gives a 3/2-approximation to average fair share, which is optimal among sequential payment rules.

The rise of interactive platforms like conversational AI assistants introduces a new dimension to ad auctions: time. As a conversation evolves, a platform can learn more about a user's interests, creating a fundamental trade-off: delay ad delivery to acquire precise information about ad quality, or deliver the ad immediately to capitalize on a thick market before potential bidders are revealed to be poor matches. We study this trade-off in a model where a revenue-maximizing platform can commit to an auction format (first- or second-price) but not to its timing, endogenously choosing when to run the auction after observing its beliefs about advertisers' ad quality.

We characterize the equilibria and observe a stark divergence in outcomes. In a first-price auction (FPA), the platform seeks information, delaying the auction to learn ad qualities perfectly and ensure an efficient allocation. However, advertisers anticipate this delay and the resulting market thinness, leading them to shade their bids aggressively and severely depressing revenue. In contrast, in a second-price auction (SPA), the platform avoids information. Delay introduces the risk of vanishing competition, so the platform runs the auction immediately. This results in an inefficient allocation but leverages market thickness to generate revenue that can be arbitrarily larger than in an FPA.

Finally, we show that optimal reserve prices fundamentally alter these dynamics and flip the revenue ordering. A reserve price in an FPA mitigates bid shading, allowing the platform to delay, allocate efficiently, and implement the revenue-optimal mechanism without needing time-commitment. Conversely, in an SPA with a reserve price, the platform's incentive to stop early persists, making the mechanism non-truthful and preventing implementation of the optimal outcome. Our results highlight how the choice of auction format dictates the endogenous resolution of the trade-off between information acquisition and market thickness, offering insights for designing ad auctions in dynamic, interactive environments.

The full paper can be found at https://arxiv.org/abs/2403.11022.

We study a model of competitive information design in an oligopoly search market with heterogeneous consumer search costs. A unique class of equilibria—upper-censorship equilibria—emerges under intense competition. In equilibrium, firms balance competitive pressure with local monopoly power granted by search frictions. Notably, firms disclose only partial information even as the number of firms approaches infinity. The maximal informativeness of equilibrium decreases under first-order shifts in the search cost distribution, but varies non- monotonically under mean-preserving spreads. Instead, informativeness increases in the evenness of the search cost distribution, measured by min_c H(c)/c. Finally, the model nests two canonical benchmarks as limiting cases: it converges to full disclosure as search frictions vanish and to no disclosure when search costs become homogeneous.

A full version of this paper can be found at https://papers.ssrn.com/sol3/papers.cfm?abstract_id=5206437

Decision-making often requires an individual to navigate a multitude of options with incomplete knowledge of their own preferences. Information provisioning tools such as public rankings and personalized recommendations have become central to helping individuals make choices, yet their value proposition under different marketplace environments remains unexplored. This paper studies a stylized model to explore the impact of these tools in two marketplace settings: uncapacitated supply, where items can be selected by any number of agents, and capacitated supply, where each item is constrained to be matched to a single agent. We model the agents utility as a weighted combination of a common term which depends only on the item, reflecting the item's population-level quality, and an idiosyncratic term, which depends on the agent-item pair capturing individual-specific preferences. Public rankings reveal the common term, while personalized recommendations reveal both terms.

In the supply unconstrained settings, both public rankings and personalized recommendations improve welfare, with their relative value determined by the degree of preference heterogeneity. Public rankings are effective when preferences are relatively homogeneous, while personalized recommendations become critical as heterogeneity increases. In contrast, in supply constrained settings, revealing just the common term of the utility, as done by public rankings, provides limited benefit since the total common value available is limited by capacity constraints, whereas, personalized recommendations, by revealing both common and idiosyncratic terms, significantly enhance welfare by enabling agents to match with items they idiosyncratically value highly. These results illustrate the interplay between supply constraints and preference heterogeneity in determining the effectiveness of information provisioning tools, offering insights for their design and deployment in diverse settings.

The full version of the paper can be found at https://arxiv.org/abs/2506.03369.

The problem of computing near-optimal contracts in combinatorial settings has recently attracted significant interest in the computer science community. Previous work has provided a rich body of structural and algorithmic insights into this problem. However, most of these results rely on the assumption that the principal has an unlimited budget for incentivizing agents, an assumption that is often unrealistic in practice. This motivates the study of the optimal contract problem under budget constraints.

In this work, we study multi-agent contracts with binary actions under budget constraints. Our contribution is threefold. First, we show that all previously known approximation guarantees on the principal's utility extend (asymptotically) to budgeted settings. Second, through the lens of budget constraints, we uncover insightful connections between the standard objective of maximizing the principal's utility and other relevant objectives. Specifically, we identify a broad class of objectives, which we term BEST objectives, including reward, social welfare, and principal's utility, and show that they are all equivalent (up to a constant factor), leading to approximation guarantees for all BEST objectives. Third, we introduce the price of frugality, which quantifies the loss due to budget constraints, and establish near-tight bounds on this measure, providing deeper insights into the tradeoffs between budgets and incentives.

A key structural insight facilitating our results is a downsizing lemma, which reduces any set of agents to fit (almost) any budget, while ensuring the principal's reward decreases at most linearly with the payments. Our analysis of the price of frugality shows that this linear loss is unavoidable, even for additive reward functions.

The full version of the paper can be found at: https://arxiv.org/abs/2504.01773.

We consider a mechanism design problem where an auctioneer allocates k units of an item to multiunit demand buyers arriving in an online fashion, each with a constant private marginal value. The auctioneer can inspect buyers allocated to learn their types and use this information to lower payments to reward truthful buyers. By using tools from the Calculus of Variations, we fully characterize the optimal mechanism for a single-buyer problem subject to an upper bound on the allocation expectation. In particular, we characterize the optimal allocation strategy as the solution of an ordinary differential equation and establish that it is a continuous and monotonically increasing function of the buyer's types. With the solution to the single-buyer problem, and by using connections to the prophet inequality literature, we design an online mechanism that achieves [EQUATION] of the optimal (offline) revenue, where α_max denotes the highest fraction of all units a buyer requests.¹

Multi-item mechanism design has been studied extensively in the literature of economics and computation in the past two decades. Many recent works in the multi-dimensional mechanism design setting have been focused on approximating the optimal revenue via simple mechanisms. One particularly important mechanism that is both studied in the literature and implemented in real-world scenarios is the item pricing mechanism.

We study the item pricing mechanisms for a single unit-demand buyer who wants to obtain at most one item. A monopoly seller has n items to sell to a single buyer. The buyer has value v_i ∈ [0, 1] for each item i, which is independently drawn from distribution D_i. The seller posts a price p_i for each item i and given the posted prices, the buyer chooses the item i with the highest non-negative utility v_i - p_i.

Traditional research on Bayesian revenue maximization assumes that the seller has full information on the buyer's underlying value distribution. Recent literature has been studying more realistic models about how the seller gets access to the buyer's value information. One important model is the sample access model: instead of directly observing buyer's value distributions, the seller can get i.i.d. samples from buyer's underlying value distributions. The sample complexity of the problem is defined by the number of samples from each distribution needed for the seller to learn a mechanism, such that with high probability the expected payment collected from the buyer is at most ϵ away from the optimal revenue with accurate prior information. Another important model that has attracted much attention recently is the pricing query access model. In each round of query interaction, the seller chooses one item i and posts a price p_i. An independent sample v_i ~ D_i is drawn and the seller only observes a binary outcome 1[v_i ≥ p_i]. The pricing query complexity of the revenue maximization problem is defined by the number of queries needed for the learner to learn a mechanism with revenue at most ϵ away from the optimal revenue of a mechanism with the exact value distributions.

In this paper, we give nearly tight sample complexity and pricing query complexity of the unit-demand pricing problem. For sample complexity, we show [EQUATION] samples over each value distribution are necessary and sufficient to learn a posted pricing mechanism p with revenue at most ϵ less than the optimal item pricing. For pricing query complexity, we show [EQUATION] pricing queries over D are sufficient to learn a posted pricing mechanism p with revenue at most ϵ less than the optimal item pricing. We also provide a matching lower bound for the ex-ante relaxation version of the problem.

We study identifying assumptions in the random utility model, the standard empirical paradigm in modern economics. Our main result characterizes those ex-ante restrictions which lead to identification. Our characterization utilizes a simple class of mass preserving swaps. These swaps take in two preferences which share a common upper and lower contour set but disagree on their ordering within these two sets. The output of this procedure is two preferences which are created by swapping the matching between the ordering of the upper and lower contour sets of the two input preferences. Any two distributions over preferences are observationally equivalent if and only if one can be recovered from the other by a finite sequences of such swaps. It follows that a random utility model is identified if it does not contain any two such distributions over preferences.

To visualize this swapping procedure, suppose that an agent has preferences over four pieces of fruit: an apple, a banana, some cherries, or a dragonfruit {a, b, c, d}, and consider the following four preferences, where each preference is listed in order of descending desirability:

[EQUATION]

The two preferences a ≻ b ≻ c ≻ d and b ≻ a ≻ d ≻ c correspond to the input of the swap and the two preferences a ≻ b ≻ d ≻ c and b ≻ a ≻ c ≻ d correspond to the output of the swap.

Using this swapping procedure, we obtain specialized characterizations of which restrictions on the support of a random utility model yield identification, as well as of the extreme points of the set of distributions rationalizing a given data set. Finally, when a model depends smoothly on some set of parameters, we show that under mild topological assumptions, identification is characterized by a straightforward, local test. Geometrically, this test amounts to verifying that the linear subspace generated by our swapping procedure is never tangent to the image of the model.

Link to paper: https://arxiv.org/pdf/2408.06547v1

We consider the problem of pricing a reusable resource service system. Potential customers arrive according to a Poisson process and purchase the service if their valuation exceeds the current price. If no units are available, customers immediately leave without service. Serving a customer corresponds to using one unit of the reusable resource, where the service time has a general distribution. The objective is to maximize the steady-state revenue rate. This system is equivalent to the classical Erlang loss model with price-sensitive customers, which has applications in vehicle sharing, cloud computing, and spare parts management.

With general service times, the optimal pricing policy depends not only on the number of customers currently in the system but also on how long each unavailable unit has been in use. We prove several results that show a simple static policy is universally near-optimal for any service rate distribution, arrival rate, and number of units in the system. When there are multiple classes of customers, we prove that static pricing guarantees 78.9% of the revenue of the optimal dynamic policy, achieving the same guarantee known for a single class of customers with exponential service times. When there is one class of customers who have a monotone hazard rate valuation distribution, we prove that a static pricing policy guarantees 90.4% of the revenue from the optimal inventory-based policy. Finally, we prove that the optimal static policy can be easily computed, resulting in the first polynomial-time approximation algorithm for the multi-class problem.

A full version of this paper can be found at https://arxiv.org/abs/2302.11723.

We study the communication complexity of computing a fair allocation of m indivisible goods to n equally entitled agents, where agents transmit information about their private valuation functions to an allocation algorithm that needs to output a fair allocation. For some classes of valuations and some fairness notions, we design randomized allocation algorithms in which on average (over the agents), each agent needs to transmit only very little information. For example, for additive valuations we show that average expected O (log m) bits suffice for computing approximately proportional allocations (these allocations are simultaneously proportional up to one item (Prop1) and give each agent at least a n/(2n − 1) fraction of her truncated proportional share (TPS)), and for unit demand valuations, average expected O (1) bits suffice for computing maximin share (MMS) allocations.

This paper proposes two rankings of statistical experiments based on the linear convex order, providing simpler and more tractable characterizations than Blackwell order, which relies on the convex order. We apply these rankings to compare statistical experiments in decision problems with a binary-action space and in decision problems that aggregate payoffs over a collection of binary-action decision problems. Furthermore, these rankings can be used to compare statistical experiments in moral hazard problems without requiring the first-order approach to be valid, thereby complementing the results in Holmström (1979) and Kim (1995). The full paper is available at: https://arxiv.org/abs/2505.14639

In many decentralized markets, participants search sequentially over alternatives without knowing future matching opportunities, which can lead to suboptimal outcomes. Intuitively, efficiency can be improved by an explicit right to renege, preserving one party's option value to keep searching for better opportunities while the other sacrifices theirs for the duration of the agreement. The question is then: how should this right be priced?

This paper studies the optimal pricing and welfare implications of the right to renege in the context of the U.S. trucking industry, using novel data from a brokerage firm that allocates advance shipment contracts to carriers through dynamic auctions and applies reputational cancellation penalties to reneging carriers. I develop a model linking carriers' bidding decisions to the firm's cancellation penalties through a joint shipment search and optimal bidding problem. The model reveals a fundamental trade-off: higher penalties reduce cancellation rates conditional on a match, but also increase carriers' bids through higher opportunity costs of matching.

I structurally estimate the model from rich data on bids and cancellations, enabling counterfactual analysis and welfare evaluations of alternative cancellation penalties. When the firm is constrained to reputational penalties, the optimal penalty level is zero, coinciding with the social planner's solution. This rationalizes the large degree of contractual flexibility observed in the trucking industry as an efficient market outcome rather than one constrained by limited enforcement. However, if the firm could switch to monetary cancellation fees, the profit-maximizing penalty would be much higher than the social optimum, enabling rent extraction from carriers' outside opportunities and raising concerns for other markets where high cancellation fees are observed, such as airlines.

Full paper: https://arxiv.org/abs/2506.01650.

We study when interventions can robustly increase market surplus despite imprecise information about economic primitives, in a setting with many strategic firms possessing market power. The key sufficient condition, recoverable structure, requires large-scale product complementarities. The analysis works by decomposing the incidence of interventions in terms of principal components of a Slutsky matrix. Under recoverable structure, a noisy signal of this matrix reveals enough about these principal components to design robust interventions. Our results demonstrate the utility of spectral methods for analyzing imperfectly observed strategic interactions with many agents.

We model n strategic firms pricing differentiated products. Consumer demand, a vector of quantities q(p) ∈ ℝⁿ demanded at a vector of prices p ∈ ℝⁿ, is captured by a Slutsky matrix D (D_ij = ∂q_i/∂p_j). An authority implements per-unit subsidies σ ∈ ℝⁿ with the goal of increasing total surplus, possessing only noisy signals of market primitives: [EQUATION] = D + E and [EQUATION]. The error matrix E has spectral norm bounded by b (n) in expectation, and ε are i.i.d. An intervention rule maps signals to interventions, and is ϵ-robust if its chosen intervention achieves a desired property (e.g., surplus increase) with probability ≥ 1 - ϵ for any true market state (D, q⁰) in a pre-specified set Θ.

A property called (M(n), δ)-recoverable structure is sufficient for robust interventions: D has eigenvalues λ_ℓ with |λ_ℓ| ≥ M(n), and the initial quantity vector q⁰ must have a substantial projection (norm ≥ δ > 0) onto the eigenspace ℒ(D, M(n)) of these dominant eigenvectors u^ℓ. Economically, such large eigenvalues signify extensive complementarities. The method uses the spectral decomposition of D. Intervention effects are analyzed via eigenvector projections.

Our main result assumes that the market has (M(n), δ)-recoverable structure and bounded observational noise: M(n)/b(n) → ∞, which requires a high signal-to-noise ratio for dominant eigenvalues. In that case, under some further technical conditions, robust interventions are possible in the following sense. For any target expenditure s > 0, an intervention rule can ϵ-robustly achieve total surplus (consumer plus producer) increasing by approximately twice the expenditure s on the intervention, while leaving consumers approximately indifferent. The Davis-Kahan theorem allows reliable estimation of ℒ(D, M(n)) from the noisy [EQUATION], and the claimed intervention outcome is achieved by targeting this recovered subspace.

This outcome is nearly the maximum possible total surplus gain for the same expenditure, subject to the requirement of not harming consumers. We also exhibit several classes of environments that demonstrate the tightness of our results, e.g., showing that recoverable structure cannot be completely dispensed with.

A full version of the paper can be found at https://arxiv.org/abs/2411.03026.

This paper studies games of voluntary disclosure in which a sender discloses evidence to a receiver who then offers an allocation and transfers. We characterize all equilibrium payoffs using information design as a tool. Our main result establishes that any payoff profile that can be achieved through information design can also be supported by an equilibrium of the disclosure game. Hence, our analysis suggests an equivalence between disclosure and design in this setting. We apply our results to monopoly pricing, trading financial assets, insurance markets, and policy negotiations.

A full version of this paper can be found at https://arxiv.org/abs/2411.03608.

Recent advances in large language models have brought us closer to a world in which artificial intelligence—trained on vast collections of written and spoken communications—can convincingly mimic individual personalities. This development has the potential to transform search over human candidates in various contexts. Dating platforms are already developing "AI clones" of users to simulate dialogues between potential matches, with other possible applications extending to job interviews and childcare matching.

Competitive equilibrium is a fundamental concept in the study of markets, describing stable outcomes that can emerge from agents' trading. Proportional response is a well-established distributed algorithm which has been shown to converge to competitive equilibria in both Fisher and Arrow-Debreu markets, for various sub-families of homogeneous utilities, including linear and Constant Elasticity of Substitution (CES) utilities. However, homogeneous utilities remain a relatively restrictive subset compared to the diverse preferences that economists have considered. For instance, even the intuitive separable utilities of the form u (x) = Σ_j u_j(x_j) are generally not homogeneous. This gap motivates the open question: to what extent can the proportional response dynamics be applied to markets with non-homogeneous utility functions?

Inspired by past algorithmic successes in computing competitive equilibria, we focus on gross substitutes (GS) utilities, a widely studied and well-behaved class of preferences. We introduce a natural extension of the proportional response dynamics for GS utilities, generalizing prior work for substitute CES utilities. We prove that this generalized proportional response dynamics converge to competitive equilibria in Fisher markets for GS utilities. This is the first convergence result of a proportional response style dynamics in Fisher markets for utilities beyond the homogeneous utilities covered by the Eisenberg-Gale convex program. We show an empirical convergence rate of O (1/T) for the prices. Furthermore, we show that the allocations of a lazy version of the generalized proportional response dynamics converge to competitive equilibria in Arrow-Debreu markets.

The full version of this paper is available at: https://arxiv.org/abs/2506.02852.

We study 2-player zero-sum concurrent (i.e., simultaneous move) stochastic Büchi games and Transience games on countable graphs. Two players, Max and Min, seek respectively to maximize and minimize the probability of satisfying the game objective. The Büchi objective is to visit a given set of target states infinitely often. This can be seen as a special case of maximizing the expected lim sup of the daily rewards, where all daily rewards are in {0, 1}. The Transience objective is to visit no state infinitely often, i.e., every finite subset of the states is eventually left forever. Transience can only be met in infinite game graphs.

We show that in Büchi games there always exist ϵ-optimal Max strategies that use just a step counter (discrete clock) plus 1 bit of public memory. This upper bound holds for all countable graphs, but it is a new result even for the special case of finite graphs. The upper bound is tight in the sense that Max strategies that use just a step counter, or just finite memory, are not sufficient even on finite game graphs.

This upper bound is a consequence of a slightly stronger new result: ε-optimal Max strategies for the combined Büchi and Transience objective require just 1 bit of public memory (but cannot be memoryless). Our proof techniques also yield a closely related result, that ε-optimal Max strategies for the Transience objective alone can be chosen as memoryless.

Predictions about people are increasingly automated using black-box algorithms. How should individuals compare evaluation by algorithms (e.g., medical diagnosis by a machine learning algorithm) with more traditional evaluation by human experts (e.g., medical diagnosis by a doctor)?

The problem of fair allocation of indivisible goods studies allocating a set of m goods among n agents in a fair manner. While fairness is a fundamental requirement in many real-world applications, it often conflicts with (economic) efficiency. This raises a natural and important question: How can we identify the most welfare-efficient allocation among all fair allocations? This paper gives an answer from the perspective of computational complexity. Specifically, we study the problem of maximizing utilitarian social welfare (the sum of agents' utilities) under two widely studied fairness criteria: envy-freeness up to any item (EFX) and envy-freeness up to one item (EF1). We examine both normalized and unnormalized valuations, where normalized valuations require that each agent's total utility for all items is identical.

The key contributions of this paper can be summarized as follows: (i) we sketch the complete complexity landscape of welfare maximization subject to fair allocation constraints; and (ii) we provide interesting bounds on the price of fairness for both EFX and EF1. Specifically: (1) For n = 2 agents, we develop polynomial-time approximation schemes (PTAS) and provide NP-hardness results for EFX and EF1 constraints. (2) For n > 2 agents, under EFX constraints, we design algorithms that achieve approximation ratios of O (n) and [EQUATION] for unnormalized and normalized valuations, respectively. These results are complemented by asymptotically tight inapproximability results. We also obtain similar results for EF1 constraints. (3) When the number of agents is a fixed constant, we show that the optimal solution can be computed in polynomial time by slightly relaxing the fairness constraints, whereas exact fairness leads to strong inapproximability. (4) Furthermore, our results imply the price of EFX is [EQUATION] for normalized valuations, which is unknown in the literature.

Centralized matching markets that prioritize specific participants to achieve certain policy goals are common in practice, but priority is often assigned using endogenous characteristics of participants. In the heart transplant waitlist in the United States, the treatment that a patient receives is used to assign waitlist priority. Policymakers recently changed the prioritization in an attempt to reduce waitlist mortality by assigning higher priority to patients receiving specific treatments previously associated with high waitlist mortality. First, I document a significant response to waitlist incentives in treatments given and transplants that take place. Then, I develop and estimate a structural model of treatment and transplant choices to evaluate the effect of the policy change on patients' outcomes and doctors' decisions. I find three main results from my model. First, there is little change in aggregate survival, and the effect of the change has been mainly re-distributive. Second, the change has effectively targeted patients with lower untransplanted survival, with these patients receiving higher expected survival under the current design. Third, the effect on survival is largely driven by changes in the decision to accept/decline offers for transplants rather than directly due to a change in treatment decisions. The policy implications suggest that future designs of the waitlist should disincentivize declining offers for transplants.

We propose a solution concept—satisficing equilibrium—in which each agent i does not necessarily optimize but selects one of their top k_i actions in response to the actions of others. Our concept accounts for bounded rationality, which may vary across agents. We illustrate our solution concept in a number of games from the literature. We show that non-trivial satisficing equilibria may fail to exist. However, we introduce the class of approximate potential games where their existence is guaranteed and, moreover, we show that satisficing equilibrium in which all but one agent best-respond and the remaining agent plays at least a second-best action exist in asymptotically almost all games. We provide positive foundations analogous to Nash equilibrium and show that a simple dynamic converges to satisficing equilibrium in almost all large games. Moreover, we characterize satisficing equilibrium via decision theoretic axioms. Finally, we turn to the testable implications of satisficing equilibrium.

This paper offers a new estimation approach for balancing statistical flexibility and economic regularity in structural econometric models. We focus our analysis on nonparametric demand systems for differentiated goods where such trade-offs are especially salient. Our framework is based on a quasi-Bayes model that transforms a sieve-based estimator of the inverse demand function into a quasi-likelihood, and then uses priors to regularize and enforce economic constraints. The induced quasi-posterior is defined over a complex domain which poses challenges for off-the-shelf sampling methods. We implement novel sampling procedures that (i) repose the heavily constrained target as the limit of a sequence of softly constrained targets, and then (ii) utilize Sequential Monte Carlo algorithms to push and filter samples through this sequence. We evaluate the performance of our approach using both simulations and retail scanner data. We find that our proposed quasi-Bayes framework can more effectively enforce constraints relative to previous methods and, by doing so, improves finite sample performance. Finally, we introduce an accompanying Julia package (NPDemand.jl) to help make nonparametric demand estimation more feasible in applied work.

A full version of this paper can be found at https://ssrn.com/abstract=5100826.

Organizations increasingly seek to share and access datasets to improve their ML models and derive insights. Despite the immense demand for quality data, data exchange and collaboration have not reached their full potential. One of the key reasons is the lack of reciprocity, where some participants perceive their contribution to others to be of higher value than what they receive in return.

We propose a general framework for data exchange without payments, focusing on two main properties: (i) reciprocal fairness, which ensures that each agent receives utility proportional to their contribution to the total welfare - contributions are quantifiable using well-established credit-sharing functions such as the Shapley share and proportional share, and (ii) core-stability, which guarantees that no coalition of agents can identify an exchange among themselves which they all unanimously prefer to the current exchange.

Surprisingly, we show that fair and stable exchanges exist for all monotone continuous utility functions. Building on this, we investigate the computational complexity of finding approximate fair and stable exchanges. We present a local search algorithm for instances with monotone submodular utility functions and cross-monotone credit-sharing functions, e.g., Shapley share. We prove that this problem belongs to CLS (= PPAD ∩ PLS) under mild assumptions. Our framework opens up several intriguing theoretical avenues for future research on data economics.

The full version of our paper can be accessed at https://arxiv.org/abs/2412.01968.

We study the design of procurement contracts in environments where the buyer faces uncertainty over the product's demand and the seller's cost. The buyer has a conjecture (model) but does not fully trust it. She first identifies all worst-case optimal contracts, which deliver the largest payoff guarantee over a set of plausible demand and cost functions. She then selects the contract that maximizes the expected payoff (under her model) over such a restricted set. We term contracts surviving this two-step procedure as robustly optimal contracts. In usual screening problems, just like the one considered here, there are many worst-case optimal contracts, and our approach offers a selection criterion.

We show that in every robustly optimal contract, there is an increase in the quantity procured from the least efficient sellers and a decrease in the quantity procured from the sellers with an intermediate cost (relative to the optimal contract in the absence of any model uncertainty).

Downward distortions in output in the absence of model uncertainty serve to reduce rents for more efficient types. The value of such distortions is significantly reduced when the buyer is concerned that her model could be wrong. As a result, robustness calls for an upward revision of the quantity procured from the least efficient types. Hence, contrary to what emerges under the familiar benchmark in the absence of model uncertainty, the robustly optimal contract features efficiency both at the top and the bottom of the modeled cost distribution. For the intermediate costs, further downward distortion is needed to avoid losses from over-procurement if nature chooses the lowest inverse demand.

We apply our results to monopoly regulation. The procurement mechanisms can be interpreted as quantity regulation. Alternatively, there is price regulation, where the government sets the price for the monopolist's goods and transfers subsidies conditional on the realized demand. The price regulation appears superior to the quantity regulation as the quantity produced under the price regulation is responsive to the realized demand. However, as we show, robustness concerns introduce a non-trivial trade-off between price and quantity regulation. Intuitively, worst-case optimality necessitates a price cap that safeguards consumer surplus in case demand turns out to be the lowest. But, at the same time, this price cap leads to overproduction if the realized demand turns out to be the conjectured one. We also identify conditions under which price regulation is superior to quantity regulation.

Full paper: https://faculty.wcas.northwestern.edu/apa522/robust-procurement.pdf

In many proportional parliamentary elections, electoral thresholds (typically 3–5%) are used to promote stability and governability by preventing the election of parties with very small representation. However, these thresholds often result in a significant number of "wasted votes" cast for parties that fail to meet the threshold, which reduces representativeness. One proposal is to allow voters to specify replacement votes, by either indicating a second choice party or by ranking a subset of the parties, but there are several ways of deciding on the scores of the parties (and thus the composition of the parliament) given those votes. We introduce a formal model of party voting with thresholds, and compare a variety of party selection rules axiomatically, and experimentally using a dataset we collected during the 2024 European election in France. We identify three particularly attractive rules, called Direct Winners Only (DO), Single Transferable Vote (STV) and Greedy Plurality (GP).

We consider the problem of allocating heterogeneous and indivisible goods among strategic agents, with preferences over subsets of goods, when there is no medium of exchange. This model captures the well studied problem of fair allocation of indivisible goods. Serial-quota mechanisms are allocation mechanisms where there is a predefined order over agents, and each agent in her turn picks a predefined number of goods from the remaining goods. These mechanisms are clearly strategy-proof, non-bossy, and neutral. Are there other mechanisms with these properties?

We show that for important classes of strict ordinal preferences (as lexicographic preferences, and as the class of all strict preferences), these are the only mechanisms with these properties. Importantly, unlike previous work, we can prove the claim even for mechanisms that are not Pareto-efficient. Moreover, we generalize these results to preferences that are cardinal, including any valuation class that contains additive valuations. We then derive strong negative implications of this result on truthful mechanisms for fair allocation of indivisible goods to agents with additive valuations.

A full version of this paper can be found at https://doi.org/10.48550/arXiv.2411.11131.

Many social programs attempt to allocate scarce resources to people with the greatest need. Indeed, public services increasingly use algorithmic risk assessments motivated by this goal. However, targeting the highest-need recipients often conflicts with attempting to evaluate the causal effect of the program as a whole, as the best evaluations would be obtained by randomizing the allocation. We propose a framework to design randomized allocation rules which optimally balance targeting high-need individuals with learning treatment effects, presenting policymakers with a Pareto frontier between the two goals. We give sample complexity guarantees for the policy learning problem and provide a computationally efficient strategy to implement it. We then collaborate with the human services department of Allegheny County, Pennsylvania to evaluate our methods on data from real service delivery settings. Optimized policies can substantially mitigate the tradeoff between learning and targeting. For example, it is often possible to obtain 90% of the optimal utility in targeting high-need individuals while ensuring that the average treatment effect can be estimated with less than 2 times the samples that a randomized controlled trial would require. Mechanisms for targeting public services often focus on measuring need as accurately as possible. However, our results suggest that algorithmic systems in public services can be most impactful if they incorporate program evaluation as an explicit goal alongside targeting.

A seller sells an object over time but is uncertain how the buyer learns their willingness-to-pay. We consider informational robustness under limited commitment, where the seller offers a price each period to maximize continuation profit against worst-case information arrival. Our formulation considers the worst case sequentially. Under general conditions, we characterize an essentially unique equilibrium. Furthermore, we identify a condition that ensures the equilibrium price path is "reinforcing," so even non-sequentially worst-case information arrival would not lower the seller's payoff below the equilibrium level.

The full version of the paper can be found at: https://arxiv.org/abs/2202.04616

Credit ratings are essential in capital markets, serving as a bridge to reduce information asymmetry between firms and investors. However, the prevalent issuer-pay model creates a potential conflict of interest: since CRAs are paid by the issuers, they may have incentives to inflate ratings to retain clients, compromising the credibility of ratings and threatening market stability. This concern is often linked to the observed discrepancies between solicited ratings (for paying firms) and unsolicited ratings (for non-paying firms), as documented in empirical studies.

This paper develops a theoretical model that captures the strategic interactions among CRAs, firms, and investors, and derives the following results. First, we characterize the CRA's optimal policy and the resulting market response. The CRA carefully designs the rating policy so that, despite investors being aware of the incentive to inflate solicited ratings, they continue to rely on the CRA's assessments. While CRAs penalize unsolicited firms with lower ratings, only high-quality firms choose to solicit ratings, leading to a separating equilibrium. As a result, average ratings increase with firm quality along the equilibrium path, consistent with empirical evidence and suggesting that the observed rating gap primarily reflects underlying quality differences. Second, our comparative statics explore how equilibrium outcomes respond to changes in investor willingness, rating fees, and firms' investment needs. When investors are more willing to invest or when rating fees rise, CRAs loosen rating standards to boost profits. In contrast, when firms are more eager for funding, CRA revenues rise but standards remain strict. Furthermore, we extend the analysis to incorporate endogenous rating fees and heterogeneous firm values, confirming the robustness of our results. Finally, empirical analysis using Standard & Poor's credit rating data provides support for the model's predictions.

Our analysis offers several managerial implications. Even when CRAs act strategically to maximize profit, the gap between solicited and unsolicited ratings mainly reflects firm quality differences due to adverse selection. While solicited ratings may be inflated, they still convey meaningful quality signals, preserving the informativeness of ratings and preventing market collapse. However, such manipulation is difficult to detect empirically, underscoring the need for stronger regulatory oversight, especially during periods of market optimism, when investors are more willing to invest or firms rely less on external financing.

The full paper is available at SSRN: https://ssrn.com/abstract=5284647.

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.

Full paper available at: https://t8el.com/wp-content/uploads/2025/06/nguyen-teytelboym-vardi.pdf.

Two sellers compete to sell identical products to a single buyer. Each seller chooses an arbitrary mechanism, possibly involving lotteries, to sell their product. The utility-maximizing buyer can choose to participate in one or both mechanisms, resolving them in either order. Given a common prior over buyer values, how should the sellers design their mechanisms to maximize their respective revenues?

We first consider a Stackelberg setting where one seller (Alice) commits to her mechanism and the other seller (Bob) best-responds. We show how to construct a simple and approximately-optimal single-lottery mechanism for Alice that guarantees her a quarter of the optimal monopolist's revenue, for any regular distribution. Along the way we prove a structural result: for any single-lottery mechanism of Alice, there will always be a best response mechanism for Bob consisting of a single take-it-or-leave-it price. We also show that no mechanism (single-lottery or otherwise) can guarantee Alice more than a 1/e fraction of the monopolist revenue. Finally, we show that our approximation result does not extend to Nash equilibrium: there exist instances in which a monopolist could extract full surplus, but neither competing seller obtains positive revenue at any equilibrium choice of mechanisms.

The full version of this paper can be found at https://arxiv.org/abs/2505.19453

We consider the problem of a learning agent who has to repeatedly play a general sum game against a strategic opponent who acts to maximize their own payoff by optimally responding against the learner's algorithm. The learning agent knows their own payoff function, but is uncertain about the payoff of their opponent (knowing only that it is drawn from some distribution D). What learning algorithm should the agent run in order to maximize their own total utility, either in expectation or in the worst-case over D?

When the learning algorithm is constrained to be a no-regret algorithm, we demonstrate how to efficiently construct an optimal learning algorithm (asymptotically achieving the optimal utility) in polynomial time for both the in-expectation and worst-case problems, independent of any other assumptions. When the learning algorithm is not constrained to no-regret, we show how to construct an ε-optimal learning algorithm (obtaining average utility within ε of the optimal utility) for both the in-expectation and worst-case problems in time polynomial in the size of the input and 1/ε, when either the size of the game or the support of D is constant. Finally, for the special case of the maximin objective, where the learner wishes to maximize their minimum payoff over all possible optimizer types, we construct a learner algorithm that runs in polynomial time in each step and guarantees convergence to the optimal learner payoff. All of these results make use of recently developed machinery that converts the analysis of learning algorithms to the study of the class of corresponding geometric objects known as menus.

Performance incentives tied to joint outcomes — such as equity for startup executives or bonuses for marketing teams — are a common tool for motivating teams. How should such incentive schemes be designed and how should they take into account the team's production function? We examine these questions in a simple non-parametric model of a team working on a joint project. Each member of the team chooses a costly effort level. These actions jointly determine a real-valued team performance according to a sufficiently smooth, increasing function of the efforts, which may entail interactions such as complementarities among agents' efforts. Any performance level determines a probability distribution over observable project outcomes.

A principal commits to a contract that specifies non-negative payments to each agent conditional on the realized project outcome. Crucially, contracts cannot condition directly on individual actions or on overall team performance. Given the contract, agents respond by playing a Nash equilibrium of the induced game. The principal's objective is to design a contract that maximizes profit — that is, revenue net of compensation paid to agents. Our main result characterizes the structure of optimal incentives in the presence of spillovers.

The characterization involves three quantities defined for each agent at a given contract and equilibrium action profile: marginal productivity (the derivative of team output with respect to the agent's action), centrality (a network-based measure capturing incentive spillovers to other agents, weighted by those agents' productivities), and marginal utility of money (reflecting how responsive the agent is to incentive pay). Our main result is that, when the binding incentive constraints are local, optimal contracts satisfy a balance condition: the product of the three quantities described above is equal across all agents receiving any incentive pay. This balance condition is necessary to prevent profitable reallocation of compensation. It also provides practical guidance: improve suboptimal contracts by shifting payments toward agents with a higher product of these terms.

The characterization just described is implicit, in the sense that it is in terms of equilibrium actions at a given contract, but we are able to obtain new, explicit contract characterizations in special cases. We derive explicit optimal contracts with Cobb-Douglas and CES production functions, which yield tractable solutions in our contract-design setting. Applying these results, we show that greater substitutability leads to more unequal contracts favoring productive agents, while complementarity promotes more balanced incentives. Our framework also recovers the linear-quadratic result of Dasaratha et al. [2023] as a special case.

A full version of the paper can be found at https://www.arxiv.org/abs/2411.08026.

Many centralized mechanisms for two-sided matching markets that enjoy strong theoretical properties assume that the planner solicits full information on the preferences of each participating agent. In particular, they expect that participants compile and communicate their complete preference lists over agents from the other side of the market. However, real-world markets are often very large and agents cannot always be expected to even produce a ranking of all options on the other side. It is therefore important to understand the impact of incomplete or truncated lists on the quality of the resultant matching.

In this paper, we focus on the Serial Dictatorship mechanism in a model where each agent of the proposing side (students) has a random preference list of length d, sampled independently and uniformly at random from n schools, each of which has one seat. Our main result shows that if the students primarily care about being matched to any school of their list (as opposed to ending up unmatched), then all students in position i ≤ n will prefer markets with longer lists, when n is large enough. Conversely, for each d there exists a j = j(d) ≥ n such that all students in position i ≥ j will prefer markets with shorter lists, again when n is large enough. Furthermore, j(d) → n as d → ∞. Schools on the other hand will always prefer longer lists in our model. We moreover investigate the impact of d on the rank of the school that a student gets matched to.

Our main result suggests that markets that are well-approximated by our hypothesis and where the demand of schools does not exceed supply should be designed with preference lists as long as reasonable, since longer lists would favor all agents.

The complete version of this paper can be accessed at https://arxiv.org/abs/2506.06217.

We study mechanism design when agents have private preferences and private information about a common payoff-relevant state. We show that standard message-driven mechanisms cannot implement socially efficient allocations when agents have multidimensional types, even under favorable conditions.

To overcome this limitation, we propose data-driven mechanisms that leverage additional post-allocation information, modeled as an estimator of the payoff-relevant state. Our data-driven mechanisms extend the classic Vickrey-Clarke-Groves class. We show that they achieve exact implementation in posterior equilibrium when the state is either fully revealed or the utility is affine in an unbiased estimator. We also show that they achieve approximate implementation with a consistent estimator, converging to exact implementation as the estimator converges, and present bounds on the convergence rate.

We demonstrate applications to digital advertising auctions and large language model (LLM)-based mechanisms, where user engagement naturally reveals relevant information.

A full version of this paper can be found at https://arxiv.org/abs/2412.16132.

We study how home sellers and buyers interact with Zillow's Zestimate algorithm throughout the sales cycle of residential properties, with an emphasis on the implications of such interactions. In particular, leveraging Zestimate's algorithm updates as exogenous shocks, we find evidence for a human-algorithm feedback loop: listing and selling outcomes respond significantly to Zestimate, and Zestimate is quickly updated for the focal and comparable homes after a property is listed or sold. This raises a concern that housing market disturbances may propagate and persist because of the feedback loop. However, simulations suggest that disturbances are short-lived and diminish eventually, mainly because all marginal effects in the selling process - though sizable and significant - are less than one. To further validate this insight in the real data, we leverage the COVID-19 pandemic as a natural experiment. We find consistent evidence that the initial disturbances created by the March 2020 declaration of national emergency faded away in a few months. Overall, our results identify the human-algorithm feedback loop in an important real-world setting but dismiss the concern that such a feedback loop generates persistent error propagation.

The full version of this paper can be found at https://papers.ssrn.com/sol3/papers.cfm?abstract_id=4061116.

Motivated by applications in online marketplaces, we propose a growth model of platforms operating as market markers in two-sided matching markets, such as between service providers and customers. The growth of these platforms, often dubbed the "chicken and egg dilemma" in the literature, poses an inherent challenge; service providers find value in joining the platform due to the presence of customers, while customers are drawn to the platform by the availability of diverse services. This endogenous network effect, created by the two sides of the market, influences the growth trajectory and propels emerging platforms towards "get big fast" strategies to rapidly achieve critical mass on both sides.

While an extensive literature in Economics, Industrial Organization, and more recently Operations has investigated the formation of two-sided platforms, one aspect that has been overlooked is the dynamic and stochastic nature of their growth process. Much of the existing literature characterizes market equilibria based on the assumption that all agents are initially present in the market and join the platform instantaneously driven by network effects that are instantly achieved in equilibrium.

To address this limitation, we model the platform as a Markovian system, with its state space s_t ∈ ℕ defined by the number of active service providers at time t ≥ 0, initially starting from s₀ = 0. Service providers join the platform according to a Poisson process with intensity μ(s_t), which is indirectly influenced by the compensation offered by the platform. Specifically, we assume that an arriving service provider joins the platform if they can earn a net-discounted expected compensation at least equal to an outside option υ. Additionally, active service providers are free to leave the platform at any time if their expectation of future payoffs falls below the threshold υ. In other words, the incentives for the service providers are based on the commitment the platform makes to them in the form of the compensation scheme υ. Customers, on the other hand, are transitory and arrive following a Poisson process with state-dependent intensity λ(s_t), a non-decreasing function of s_t that captures consumers' preferences for larger platforms. Each customer matched to a service provider pays a fixed fee p for the service. Under some mild conditions on the supply and demand functions, μ(·) and λ(·) respectively, we show that there are upper bounds on how fast and large the platform can grow. We also show that simple compensation rules, such as uniform payments, fail to achieve this optimal expansion. Instead, an optimal compensation mechanism must take into account the "seniority" of each individual active server, as measured by the time they joined the platform.

The full version of this paper is available at: https://papers.ssrn.com/sol3/papers.cfm?abstract_id=5201117

In the ever-evolving blockchain ecosystem, decentralized exchanges (DEXs) have seen significant growth, which, however, has also brought challenges of Maximal Extractable Value (MEV). DEXs offer a decentralized platform for cryptocurrency trading. Such trading mechanisms primarily include Constant Function Market Makers (CFMMs) and batch auctions.

We first examine MEV in batch auctions. By treating assets and transactions as goods and traders within a pure exchange market, batch auctions can be formulated as a linear market, allowing exchange rates and trading outcomes in a batch to be derived from the prices and allocation in its market equilibrium. This design ensures fairness and efficiency from the perspective of economics. Despite the general belief that batch auctions are less vulnerable to MEV due to uniform pricing and order independence of transactions, we highlight that the block builder's current ability to rearrange the batch content is sufficient to extract MEV in batch auctions, where the strategic behavior is a novel market equilibrium manipulation. We further explore the computation and show that: When the transactions in a batch form a Fisher market, an optimal attack can be computed in polynomial time. When the transactions form a general Arrow-Debreu market, under the Unique Games Conjecture, obtaining a 50.01%-approximation is NP-hard.

In addition, we show it is NP-hard to compute a strategy that obtains even 0.01% of optimal MEV in CFMMs when the fraction of swap fee is any constant larger than zero (e.g., 0.3%).

Full version of the paper is available at http://mengqianzhang.me/papers/ec2025-batch.pdf.

We consider the cooperative elements that arise in the design of public goods, such as transportation policies and infrastructure. These involve a variety of stakeholders: governments, businesses, advocates, and users. Their eventual deployment depends on the decision maker's ability to garner sufficient support from each of these groups; we formalize these strategic requirements from the perspective of cooperative game theory. Specifically, we introduce non-transferable utility, linear production (NTU LP) games, which combine the game-theoretic tensions inherent in public decision-making with the modeling flexibility of linear programming. We derive structural properties regarding the non-emptiness, representability and complexity of the core, a solution concept that models the viability of cooperation. In particular, we provide fairly general sufficient conditions under which the core of an NTU LP game is guaranteed to be non-empty, prove that determining membership in the core is co-NP-complete, and develop a cutting plane algorithm to optimize various social welfare objectives subject to core membership. Lastly, we apply these results in a data-driven case study on service plan optimization for the Chicago bus system. As our study illustrates, cooperation is necessary for the successful deployment of transportation service plans and similar public goods, but it may also have adverse or counterintuitive distributive implications.

A full version of this paper can be found at https://arxiv.org/abs/2506.05251.

We consider the impact of fairness requirements on the social efficiency of truthful mechanisms for trade, focusing on Bayesian bilateral-trade settings. Unlike the full information case in which all gains-from-trade can be realized and equally split between the two parties, in the private information setting, equitability has devastating welfare implications (even if only required to hold ex-ante). We thus search for an alternative fairness notion and suggest requiring the mechanism to be KS-fair: it must ex-ante equalize the fraction of the ideal utilities of the two traders. We show that there is always a KS-fair (simple) truthful mechanism with expected gains-from-trade that are half the optimum, but always ensuring any better fraction is impossible (even when the seller value is zero). We then restrict our attention to trade settings with a zero-value seller and a buyer with valuation distribution that is Regular or MHR, proving that much better fractions can be obtained under these conditions, with simple posted-price mechanisms.

A full version of this paper can be found at https://doi.org/10.48550/arXiv.2502.19050.

The time at which renewable energy resources (e.g., solar or wind) produce electricity cannot generally be controlled. However, in many settings, consumers have some flexibility in their energy consumption, and there is growing interest in demand-response programs that leverage this flexibility to shift energy consumption to better match renewable production—thus enabling more efficient utilization of these resources. We study demand response in a setting where consumers use home energy management systems (HEMS) to autonomously adjust their electricity consumption. Our core assumption is that HEMS operationalize flexibility by querying consumers for their preferences and computing the "indifference set"—the set of all energy consumption profiles that can satisfy these preferences. Given an indifference set, HEMS can then respond to grid signals while ensuring user-defined comfort and functionality. For example, if a consumer sets a temperature range, a HEMS can precool and preheat to align with peak renewable production, thus improving efficiency without sacrificing comfort.

In this work, we first formally characterize the optimal demand-response problem: the grid operator directly controls consumer devices to select consumption profiles that minimize a grid risk function (e.g., peak demand) while remaining within consumers' indifference sets. This formulation captures the maximum benefit of consumer flexibility for the grid. We then ask: can a practical demand-response program approach the performance of this direct-control benchmark? Focusing on price-based signals, we show that, although they may not be optimal in small markets and may exhibit a gap relative to the risk value of the direct-control method, they become optimal in the mean-field limit, i.e., they are able to match the performance of the direct-control method as the market size grows.

We then focus on learning the optimal price-based signal. We show that this signal can be expressed using mean-field market quantities and learned by querying HEMS for their consumption under various prices. Our approach can recover relevant gradients from zeroth-order queries, thus enabling fast learning and optimization despite limited access to consumer preferences or constraints. Finally, using an OpenDSS-powered grid simulation for Phoenix, Arizona, we demonstrate that our approach enables powerful demand response without creating grid instability.

The paper can be found at this link: https://arxiv.org/abs/2409.07655.

Algorithmic contract design studies scenarios where a principal incentivizes an agent to exert effort on her behalf. In this work, we focus on settings where the agent's type is drawn from an unknown distribution, and formalize an offline learning framework for learning near-optimal contracts from sample agent types. A central tool in our analysis is the notion of pseudo-dimension from statistical learning theory. Beyond its role in establishing upper bounds on the sample complexity, pseudo-dimension measures the intrinsic complexity of a class of contracts, offering a new perspective on the tradeoffs between simplicity and optimality in contract design. Our main results provide essentially optimal tradeoffs between pseudo-dimension and representation error (defined as the loss in principal's utility) with respect to linear and bounded contracts. Using these tradeoffs, we derive sample- and time-efficient learning algorithms, and demonstrate their near-optimality by providing almost matching lower bounds on the sample complexity. Conversely, for unbounded contracts, we prove an impossibility result showing that no learning algorithm exists.

Finally, we extend our techniques in three important ways. First, we provide refined pseudo-dimension and sample complexity guarantees for the combinatorial actions model, revealing a novel connection between the number of critical values and sample complexity. Second, we extend our results to menus of contracts and piecewise linear contracts, showing that their pseudo-dimension scales linearly with the menu size and polynomially with the number of linear pieces. Third, we adapt our algorithms to the online learning setting, where we show that a polynomial number of type samples suffices to learn near-optimal bounded contracts. Combined with prior work, this establishes a formal separation between expert advice and bandit feedback for this setting.

The full version of the paper can be found at: https://arxiv.org/abs/2501.14474.

Peer review is fundamental to academic research, yet its effectiveness hinges on reviewers voluntarily exerting costly effort to evaluate submissions. Current mechanisms used by conference organizers, such as random or affinity-based matching, fail to adequately incentivize effort, leading to suboptimal outcomes. This study investigates how peer review markets can be designed to maximize the acceptance of high-quality submissions while minimizing the acceptance of low-quality ones.

We model a one-sided market where each agent serves as both an author and a reviewer. Agents submit papers of private quality and decide whether to exert effort when reviewing. The designer (e.g., conference organizer) employs mechanisms to match papers to reviewers, with the goal of optimizing market welfare. We first analyze two existing mechanisms: Random, which induces no effort, and Symmetric, which incentivizes effort but can be exploited by low-quality authors. To address these issues, we propose a novel Admission Control (AC) mechanism, which penalizes reviewers who fail to exert effort by rejecting their submissions. Under perfectly observable effort, AC achieves first-best welfare, dominating the other mechanisms. When effort is noisily observed, AC uses stochastic penalties to ensure incentive compatibility and guarantees at least 1/2-optimal welfare, with simulations demonstrating stronger performance. Robustness analyses confirm the superiority of AC across various extensions, including noisy review outcomes, author biases, and status disclosures through preprints.

Our findings underscore the importance of linking reviewer effort to submission acceptance in peer review markets. The AC mechanism provides a practical framework for achieving this, suggesting that conference organizers should enforce effort-based participation criteria. While noisy observation of effort poses challenges, our results show that carefully calibrated penalties can mitigate these effects. Additionally, investing in technologies to improve effort detection significantly enhances outcomes. These insights offer actionable strategies for improving the integrity and efficiency of peer review processes in academic conferences. A full version of this paper can be found at https://papers.ssrn.com/sol3/papers.cfm?abstract_id=5205896

This paper studies competition under information heterogeneity in selection markets and examines the impact of public information regulations aimed at reducing information asymmetries between competing firms. We develop a novel model and introduce new empirical strategies to analyze imperfect competition in markets where firms have heterogeneous information about consumers, vary in cost structures, and offer differentiated products. Using data from the Italian auto insurance market, we find substantial differences in the precision of risk ratings across insurers, and those with less accurate risk-rating algorithms tend to have more efficient cost structures.

We evaluate the equilibrium effects of a public information policy where insurers' risk estimates are aggregated and made public through a centralized bureau. This policy significantly reduces prices by increasing competition, which in turn boosts consumer surplus by 15.7%, nearly matching the gains observed under the efficiency benchmark, where firms have full knowledge of consumers' true risk levels. We also observe interesting distributional effects. The centralized risk bureau primarily benefits low-risk consumers, in contrast to the scenario motivated by privacy regulations, where all firms adopt the least-advanced information technology. Lastly, the centralized bureau policy improves the matching efficiency between insurers and insurees, reducing average costs by 12 euros per contract.

Large language models (LLMs) now stand in for human decision makers in many settings, but it is unclear whether their choices arise from structured internal representations or surface-level pattern matching—and whether the economic preferences they express are correlated as in humans. We address these questions by analyzing three canonical preference domains - risk, time, and social - across several current LLMs.

Our study proceeds in three stages. (1) Behavioral elicitation: Using standard prospect theory, intertemporal-choice, and dictator-game vignettes, we confirm that the models reproduce familiar biases - risk aversion and temporal discounting. (2) Latent probing: Contrastive prompts that elicit risk-averse versus risk-seeking responses allow us to train a sparse linear probe and identify a one-dimensional "risk axis" in activation space that reliably orders the models' lottery choices. (3) Causal steering: Small perturbations along this axis predictably shift behavior: nudging the model toward risk seeking lowers its implied discount rate, whereas nudging toward risk aversion raises it—reversing the positive risk-aversion/patience correlation observed in humans. The same manipulation produces only a weak, model-specific increase in self-interested dictator allocations, indicating that social motives are encoded in largely separate subspaces.

We contribute three findings. First, LLMs encode risk attitudes along a structured linear continuum from aversion to seeking. Second, this dimension simultaneously governs time preferences, showing that the models internalize a probabilistic relationship between risk and patience rather than hard-coding each bias independently. Third, social preferences remain largely decoupled, highlighting domain-specific representation. Taken together, these results show that LLMs, even without real-world experience, acquire interpretable latent coordinates for abstract economic traits. The probe-and-steer method we introduce offers a practical tool for mapping and manipulating such traits, positioning LLMs as scalable testbeds for behavioral theory and as synthetic participants in social-science research.

For the full paper, please visit https://papers.ssrn.com/sol3/papers.cfm?abstract_id=5284661.

Points-based rewards programs are a prevalent model to incentivize customer loyalty; in these programs, customers who make repeated purchases from a seller accumulate points, working toward eventual redemption of a free reward. If implemented correctly, they are known to increase revenue for the seller. However, these programs have come under scrutiny of late due to accusations of unfair practices in their implementation. Motivated by these real-world concerns, this paper studies the problem of fairly designing points-based rewards programs, with a special focus on two major obstacles that put fairness at odds with their effectiveness: (i) the incentive to exploit customer heterogeneity by personalizing programs to customers' purchase behavior, and (ii) risks of devaluing customers' previously earned points when sellers need to experiment in uncertain environments. To study this problem, we focus on the popular "Buy N, Get One Free" (BNGO) rewards programs. We first show that the optimal individually fair program that uses the same redemption threshold for all customers suffers from a constant factor loss in revenue of at most 1 + ln 2, compared to the optimal personalized strategy which may unfairly offer different customers different thresholds. We then tackle the problem of designing temporally fair learning algorithms in the presence of demand uncertainty. Toward this goal, we design a "stable" learning algorithm that limits the risk of point devaluation due to experimentation by only changing the redemption threshold O(log T) times, over a learning horizon of length T. We prove that this algorithm incurs [EQUATION] regret in expectation; this guarantee is optimal, up to polylogarithmic factors. We then modify this algorithm to ever only decrease redemption thresholds, leading to improved fairness at a cost of only a constant factor in regret. Finally, we conduct extensive numerical experiments to show the limited value of personalization in average-case settings, in addition to demonstrating the strong practical performance of our proposed learning algorithms.

The full version of this paper is available at: http://arxiv.org/abs/2506.03911.

We present a decision-theoretic justification for viewing the question of how to best choose where to experiment in order to optimize external validity as a k-median (clustering) problem, a popular problem in computer science and operations research. We present conditions under which minimizing the worst-case, welfare-based regret among all nonrandom schemes that select k sites to experiment is approximately equal—and sometimes exactly equal—to finding the k most central vectors of baseline site-level covariates. The k-median problem can be formulated as a linear integer program. Two empirical applications illustrate the theoretical and computational benefits of the suggested procedure.

The full version of the paper can be found at https://arxiv.org/abs/2408.09187.

Blackwell's celebrated theorem is a cornerstone of information economics, establishing a necessary and sufficient condition for when a distribution F of posterior means can be induced from a prior G: namely, if and only if F majorizes G. While this result provides a deep understanding of the structure of feasible belief distributions, it is non-constructive and does not explain how to design a signal that achieves a given F.

Online matching markets face increasing needs to accurately learn the matching qualities between demand and supply for effective design of matching policies. However, the growing diversity of participants introduces a high-dimensional challenge in practice, as there are a substantial number of unknown matching rewards and learning all rewards requires a large amount of data. We leverage a natural low-rank matrix structure of the matching rewards in these two-sided markets, and propose to utilize matrix completion (specifically the nuclear norm regularization approach) to accelerate the reward learning process with only a small amount of offline data. A key challenge in our setting is that the matrix entries are observed with matching interference, distinct from the independent sampling assumed in existing matrix completion literature. We propose a new proof technique and prove a near-optimal average accuracy guarantee with improved dependence on the matrix dimensions. Furthermore, to guide matching decisions, we develop a novel "double-enhancement" procedure that refines the nuclear norm regularized estimates and further provides near-optimal entry-wise estimations. Our paper makes the first investigation into adopting matrix completion techniques for matching problems. We also extend our approach to online learning settings for optimal matching and stable matching by incorporating matrix completion in multi-armed bandit algorithms. We present improved regret bounds in matrix dimensions through reduced costs during the exploration phase. Finally, we demonstrate the practical value of our methods using both synthetic data and real data of labor markets.

Prediction markets elicit and aggregate beliefs by paying agents based on how close their predictions are to a verifiable future outcome. However, outcomes of many important questions are difficult to verify or unverifiable, in that the ground truth may be hard or impossible to access. We present a novel incentive-compatible prediction market mechanism to elicit and efficiently aggregate information from a pool of agents without observing the outcome, by paying agents the negative cross-entropy between their prediction and that of a carefully chosen reference agent. Our key insight is that a reference agent with access to more information can serve as a reasonable proxy for the ground truth. We use this insight to propose self-resolving prediction markets that terminate with some probability after every report and pay all but a few agents based on the final prediction. The final agent is chosen as the reference agent since they observe the full history of market forecasts, and thus have more information by design. We show that it is a perfect Bayesian equilibrium (PBE) for all agents to report truthfully in our mechanism and to believe that all other agents report truthfully. Although primarily of interest for unverifiable outcomes, this design is also applicable for verifiable outcomes.

An agent engages in sequential search. He does not directly observe the quality of the goods he samples, but he can purchase signals designed by profit maximizing principal(s). We formulate the principal-agent relationship as a repeated contracting problem within a stopping game, and characterize the set of equilibrium payoffs. We show that when the agent's search cost falls below a given threshold, competition does not impact how much surplus is generated in equilibrium nor how the surplus is divided. In contrast, competition benefits the agent at the expense of total surplus when the search cost exceeds that threshold. Our results challenge the view that monopoly decreases market efficiency, and moreover, suggest that it leads to more information provision than does competition.

Link to full paper: https://arxiv.org/abs/2411.11183

We analyze the performance of heterogeneous learning agents in asset markets with stochastic payoffs. Agents aim to maximize the expected growth rate of their wealth but have different theories on how to learn to do this best. Our main focus is on comparing Bayesian learners and no-regret learners who compete in markets and identifying the conditions under which each approach is more effective. Bayesian learners with a finite prior that assigns positive probability to the correct model have posterior beliefs that converge exponentially fast, and such agents survive even in the presence of agents who invest according to the correct model. Bayesian learners with a continuum prior converge at a slower rate of O((logT)/T).

Online learning theory provides no-regret algorithms for maximizing the log of wealth, achieving worst-case regret bounds of O(logT) without assuming a stationary stochastic process, but comparing against the best fixed investment rule. This regret, as we observe, is of the same order as that of a Bayesian learner with a continuum prior. Surprisingly, we find that even such low regret may not guarantee survival: an agent with regret O(logT), converging to the correct model at rate O((logT)/T) still vanishes when competing against an agent who invests according to the correct model, or even against a perfect Bayesian with a finite prior. On the other hand, we show that Bayesian learning is fragile, while no-regret learning requires less knowledge of the environment and is therefore more robust. Specifically, any no-regret learner will drive out of the market an imperfect Bayesian whose finite prior or update rule has even small errors. Motivated by the strengths and weaknesses of both approaches, we propose a simple method to regularize Bayesian updates that improves robustness and adaptability to distribution shifts, providing a step toward a "best-of-both-worlds" learning approach. In our analysis, we formally establish the relationship between the notions of survival and market dominance studied in economics and the framework of regret minimization, thus bridging these theories.

For a full version of the paper, see: https://arxiv.org/pdf/2502.08597.

Using school choice as a motivating example, we introduce a stylized model of a many-to-one matching market where the clearinghouse seeks to implement contingent priorities—i.e., priorities that depend on the current assignment—to improve the likelihood that students with siblings are assigned together. We provide a series of guidelines and introduce two natural approaches to implement them: (i) absolute, whereby a prioritized student can displace any student without siblings assigned to the school, and (ii) partial, whereby prioritized students can only displace students that have a less favorable lottery than their priority provider. We study several properties of the corresponding mechanisms, including the existence of a stable assignment under contingent priorities, the complexity of finding one if it exists, and its incentive properties. Furthermore, we introduce a soft version of these priorities to guarantee existence, and we provide mathematical programming formulations to find such stable matching or certify that one does not exist. Finally, using data from the Chilean school choice system, we show that our framework can significantly increase the number of students assigned to their top preference and the number of siblings assigned together relative to current practice. A full version of this paper can be found at https://arxiv.org/abs/2409.04914

We study the optimal design of tests in environments where agents can invest in inputs (e.g., effort) to enhance their individual outputs (e.g., human capital), which are then sold in a competitive market (e.g., labor market). Recognizing agents' heterogeneity in converting inputs into outputs, the designer devises a test to maximize the expected total output.

We present an algorithm for obtaining ϵ-minimax solutions of statistical decision problems. We are interested in problems where i) the statistician is allowed to choose randomly among I decision rules, and ii) the statistical model may have an infinite dimensional parameter space. The minimax solution of these problems admits a convex programming representation over the (I - 1)-simplex, and the algorithm suggested herein to obtain an ϵ-approximation of the minimax solution is a version of mirror subgradient descent, initialized with uniform weights and stopped after a finite number of iterations. The resulting iterative procedure is known in the computer science literature as the hedge algorithm (a particular case of the multiplicative weights update method) and it is used in algorithmic game theory as a practical tool to find approximate solutions of two-person zero-sum games. We apply the suggested algorithm to different minimax problems in the econometrics literature. An empirical application to the problem of optimally selecting sites to maximize the external validity of an experimental policy evaluation illustrates the usefulness of the suggested procedure. The full paper can be found at https://joseluismontielolea.com/epsilon_minimax_v2.pdf.

First-price auctions are one of the most popular mechanisms for selling goods and services, with applications ranging from display advertising to timber sales. Unlike their close cousin, the second-price auction, first-price auctions do not admit a dominant strategy. Instead, each buyer must design a bidding strategy that maps values to bids—a task that is often challenging due to the lack of prior knowledge about competing bids. To address this challenge, we conduct a principled analysis of prior-independent bidding strategies for first-price auctions using worst-case regret as the performance measure. First, we develop a technique for evaluating the worst-case regret for (almost) any given value distribution and bidding strategy, reducing the complex task of ascertaining the worst-case competing-bid distribution to a simple line search. Next, building on our evaluation technique, we minimize worst-case regret and characterize a minimax-optimal bidding strategy for every value distribution. We achieve it by explicitly constructing a bidding strategy as a solution to an ordinary differential equation, and by proving its optimality for the intricate infinite-dimensional minimax problem underlying worst-case regret minimization. Our construction provides a systematic and computationally-tractable procedure for deriving minimax-optimal bidding strategies. When the value distribution is continuous, it yields a deterministic strategy that maps each value to a single bid. We also show that our minimax strategy significantly outperforms the uniform-bid-shading strategies advanced by prior work. Importantly, our result allows us to precisely quantify, through minimax regret, the performance loss due to a lack of knowledge about competing bids. We leverage this to analyze the impact of the value distribution on the performance loss, and find that it decreases as the buyer's values become more dispersed.

The full paper can be found at https://arxiv.org/abs/2502.09907.

We study a new class of contract design problems where a principal delegates the execution of multiple projects to a set of agents. The principal's expected reward from each project is a combinatorial function of the agents working on it. Each agent has limited capacity and can work on at most one project, and the agents are heterogeneous, with different costs and contributions for participating in different projects. The main challenge of the principal is to decide how to allocate the agents to projects when the number of projects grows in scale.

We analyze this problem under different assumptions on the structure of the expected reward functions. As our main result, for XOS functions we show how to derive a constant approximation to the optimal multi-project contract in polynomial time, given access to value and demand oracles. Along the way (and of possible independent interest), we develop approximate demand queries for capped subadditive functions, by reducing to demand queries for the original functions. Our work paves the way to combinatorial contract design in richer settings.

In budget-feasible mechanism design, there is a set of items U, each owned by a distinct seller. The seller of item e incurs a private cost [EQUATION] for supplying her item. A buyer wishes to procure a set of items from the sellers of maximum value, where the value of a set S ⊆ U of items is given by a valuation function υ : 2^U → ℝ₊. The buyer has a budget of B ∈ ℝ₊ for the total payments made to the sellers. We wish to design a mechanism that is truthful, that is, sellers are incentivized to report their true costs, budget-feasible, that is, the sum of the payments made to the sellers is at most the budget B, and that outputs a set whose value is large compared to [EQUATION].

Budget-feasible mechanism design has been extensively studied, with the literature focussing on (classes of) subadditive (or complement-free) valuation functions, and various polytime, budget-feasible mechanisms, achieving constant-factor approximation to OPT, have been devised for the special cases of additive, sub-modular, and XOS (or fractionally subadditive) valuations. However, for general subadditive valuations, the best-known approximation factor achievable by a polytime budget-feasible mechanism (given access to demand oracles) was only O(log n/log log n), where n = |U| is the number of items.

We improve this state-of-the-art significantly by designing a randomized budget-feasible mechanism for subadditive valuations that achieves a substantially-improved approximation factor of O (log log n) and runs in polynomial time, given access to demand oracles.

Our chief technical contribution is to show that, given any set S ⊆ U, one can construct in polynomial time a distribution D over posted-payment vectors d ∈ ℝ^S₊ satisfying d(S) ≤ B (where d(S) = Σ_e∈S d_e) such that, [EQUATION] for every cost-vector c ∈ ℝ^S₊ satisfying c(S) ≤ B/O(log log n). Using this distribution, we show how to construct a budget feasible mechanism for subadditive valuations that achieves an approximation factor of O(log log n).

A full version of the paper is available at https://arxiv.org/abs/2506.04665.

How does firm size affect the privacy protections offered to customers? On the one hand, it could be that larger firms use their size to amass more data. On the other hand, smaller firms may be less careful in their data protection practices, because they have a different perception of risk. Using data from the Google Play Store over a three-year period, we explore this empirical question in the U.S. children's app market. Our findings indicate that larger app developers consistently implement stronger privacy protections, requesting less sensitive data compared to smaller developers. These results hold across empirical approaches, including instrumental variables and the propensity-score matching approach. Additionally, our analysis shows that mergers between developers and sudden increases in size of the user-bases of the product are associated with reduced data collection. We show that newly created and updated apps produced by large developers collect less data compared to existing apps. Our findings indicate a trend toward standardized privacy practices across different national regulatory regimes. This research highlights the potential for growth-driven improvements in data privacy practices among app developers, regardless of their regulatory context.

Opaque sales are a selling mechanism in which a seller offers multiple products but the buyer does not know which specific product they will receive until after the purchase. This mechanism is widely used in the tourism industry, such as staycation packages with undisclosed hotel options or tours to different destinations, and in e-commerce through mystery boxes. In many such settings, buyers operate under a unit demand constraint, meaning they derive benefit from only one item despite multiple options being available. In this paper, we formulate and solve a multi-item mechanism design problem for opaque sales. Our goal is to identify a distribution-free mechanism that maximizes the competitive ratio, defined as the ratio between the revenue generated by the mechanism and the maximum revenue attainable with full knowledge of the buyer's valuations. Despite the problem's infinite dimensionality, we show that the optimal mechanism admits a semi-analytical form, characterized by the solution of an auxiliary convex optimization problem whose size scales linearly with the number of items. Furthermore, we demonstrate that this mechanism can be equivalently implemented through a menu of infinite level-access lotteries, where the buyer pays an amount to access a randomly assigned subset of items, with higher payments granting access to a larger selection. We then analyze the impact of menu size limitations on the competitive ratio and conclude with a prototypical example illustrating our approach.

The full paper is available at: https://papers.ssrn.com/sol3/papers.cfm?abstract_id=5130478.

We investigate the problem of fairly allocating m indivisible items among n sequentially arriving agents with additive valuations, under the sought-after fairness notion of maximin share (MMS). We first observe a strong impossibility: without appropriate knowledge about the valuation functions of the incoming agents, no online algorithm can ensure any non-trivial MMS approximation, even when there are only two agents.

Motivated by this impossibility, we propose the OnlineKTypeFD model, where each agent belongs to one of k known valuation types (not necessarily constant). Upon arrival, an agent reveals her type, receives an irrevocable allocation, and departs. We analyze ex-post MMS guarantees under two arrival models.

• Adversarial arrivals: In this model, an adversary determines the type of each arriving agent. We design a 1/k-MMS competitive algorithm and complement it with a lower bound, ruling out any [EQUATION]-MMS-competitive algorithm, even for binary valuations.

• Stochastic arrivals: In this model, the type of each arriving agent is independently drawn from an underlying, possibly unknown distribution. Unlike the adversarial setting where the dependence on k is unavoidable, we surprisingly show that in the stochastic setting, an asymptotic, arbitrarily close-to-1/2-MMS competitive guarantee is achievable under mild distributional assumptions.

Our results extend to a learning-augmented setting, where predictions of valuations allow our algorithms to achieve competitive ratios that degrade gracefully with multiplicative errors. The main technical challenge is to ensure ex-post fairness for every agent. To address this, we develop new techniques—including tentative overlapping allocations, multi-phase bag-filling, and careful handling of high-valued items.

Full version of the paper can be found at: https://arxiv.org/abs/2503.02088

We study the robust regulation of incentive contracts. We consider the problem of a regulator choosing what contracts to authorize in the canonical principal-agent model with moral hazard. A firm (she) contracts with a worker (he), who then takes a costly productive action that yields a stochastic output. Hiring the worker imposes a fixed cost for the firm. The set of productive actions and the fixed cost define the firm's technology. The worker's actions being non-contractible, the firm incentivises production by offering an (authorised) contract that maps realised outputs to payments. We assume the firm and the worker are protected by limited liability, they are risk-neutral, and they maximise their profit and surplus. We add a third player to that standard model: the regulator (they). They choose the regulation, which is the set of authorised contracts the firm can offer. We assume that the regulator's payoff is a weighted sum of the firm's profit and the worker's surplus, where the latter has a (weakly) greater weight α ≥ 1. While the firm and the worker know the technology, the regulator has no information. They choose a regulation that minimises their worst-case regret.

We show that the regret-minimising regulation allows every contract above a linear one whose slope only depends on the weight α the regulator places on the worker's surplus. This regulation guarantees the worker a minimal piece rate compensation (or share of the production), thereby safeguarding his surplus. The minimum linear contract also preserves the firm's flexibility to provide incentives while limiting the firm's motives for distorting production. It incentivises the worker to choose productive actions, which lessens the firm's interest in distorting production downward. It also reduces the firm's incentive to distort production upward, as it stops the firm from offering overly convex (bonus) contracts that can implement high-output actions cheaply. Hence, the minimum linear contract aligns the firm's incentives with the regulator's preferences for efficiency. Furthermore, the optimal regulation limits the risk of stymieing production and wasting all potential surplus by granting the firm complete flexibility above the minimum contract. The optimal regulation trades off the risk of pushing the firm out of business and the regulator's preference for efficient production and fair allocation of the surplus.

The full paper is available at https://arxiv.org/abs/2411.04841.

We study a two-dimensional information design problem in a duopoly with vertical differentiation. A third-party designer, literal or metaphorical, designs a public joint signal structure to disclose information about product quality. Upon observing the quality signal, the firms compete by simultaneously setting prices. Consumers with heterogeneous preferences about quality choose one of the two products to purchase based on the publicly observed quality signal and the prices set by the firms.

Regardless of whether the market is fully covered by the firms, we show that to maximize the joint profits of the industry, one should only disclose the ranking of the products' qualities. This policy mitigates price competition by amplifying perceived differentiation. The ranking-only policy also maximizes the (unweighted) total surplus as it yields assortative matching between consumer type and product quality. In contrast, to maximize consumer surplus, one should not reveal the quality ranking of the products, including no dislcosure at all, which intensifies price competition to the largest extent.

In addition to the "ranking versus no-ranking" results, we further characterize the optimal policy when the designer's objective is an arbitrary weighted sum of duopoly profits and consumer surplus, under both covered and uncovered specifications. When the market is always covered, the fixed-market-share effect simplifies the problem. Whenever the Pareto weight on consumer surplus exceeds a certain cutoff, the no-ranking policy is optimal. Otherwise, the ranking-only policy is optimal.

When the market is uncovered, the equilibrium market shares are affected by the signal realization. As a consequence, an additional market share effect is introduced, leading to a richer but still relatively simple pattern of the optimal quality disclosure policy. In particular, the Pareto weight can be partitioned into five regions. Similar to the covered case, ranking-only is optimal when the weight on consumer surplus is small and no-ranking is optimal when the weight is large. Unlike the covered case, for interior weights the optimal solution could be full revelation, a combination of full revelation and the ranking-only policy, or a combination of full revelation and the no-ranking policy.

Welfare maximization in bilateral trade has been extensively studied in recent years. Previous literature obtained incentive-compatible approximation mechanisms only for the private values case. In this paper, we study welfare maximization in bilateral trade with interdependent values. Designing mechanisms for interdependent settings is much more challenging because the values of the players depend on the private information of the others, requiring complex belief updates and strategic inference.

We propose to classify information structures by quantifying the influence that a player's private signal has on their own valuation. We then paint a picture of where approximations are possible and impossible based on these information structures. Finally, we also study the possible approximation ratios for a natural family of information structures.

Consider the dispatch of ridesharing trips to drivers lining up at airports, or the allocation of deceased donor organs to patients in transplant wait lists. In such dynamic queueing games, heterogeneity in short-lived items combined with agents' discretion to decline induce substantial cherrypicking, resulting in high rates of unfulfilled trips and discarded organs. Existing research typically focuses on easy-to-analyze dispatch policies, sometimes making fluid assumptions for tractability. In this work, we introduce a best-response-based solver for general dispatch policies with closed-form updates, which computes agents' equilibrium acceptance, entry, and reneging strategies as functions of queue length and queue position. For a family of dispatch policies where dispatch probabilities are queue-length independent and items are offered monotonically down the queue, we prove that our solver converges to a Markov perfect equilibrium in a finite number of iterations and that such an equilibrium always exists. For more general dispatch policies, we characterize their equilibria, and the solver converges in simulation despite the lack of theoretical guarantees. Via extensive numerical results, we show that the solver recovers known equilibria for policies that can be analyzed theoretically, and provides insights (beyond what can be gleaned from previous analysis) into more complex policies better suited for practice.

A full version of this paper can be found at https://papers.ssrn.com/sol3/papers.cfm?abstract_id=5282750.

We study how recommendation algorithms affect trade and welfare in markets characterized by algorithmic consumption, such as e-commerce platforms and AI assistants. Our analysis begins with a model of bilateral trade in which a single product is exchanged between a buyer and a seller under uncertainty about product value and seller cost. An algorithm recommends the product based on its price and estimated buyer value, thereby steering purchasing decisions. We characterize the buyer-optimal algorithm and show that it deliberately biases recommendations to amplify buyer price sensitivity, inducing lower seller prices. This optimal algorithm strategically deviates from the ex post optimal rule to exploit price pressure and enhance buyer surplus.

Our findings further show that optimal algorithmic recommendations fundamentally reshape market behavior and welfare outcomes. Even when the seller engages in third-degree price discrimination, revealing buyer value to the seller leaves total welfare unchanged but reallocates surplus more equitably across buyer types. We demonstrate that these insights extend to multiseller markets and to the broader class of Pareto-optimal algorithmic designs, suggesting wide-ranging implications for consumer protection and market regulation. A full version of this paper can be found at https://arxiv.org/pdf/2309.12122.pdf.

Economists routinely make predictions in environments where data is unavailable, relying on evidence from related but distinct contexts. For example, an economist at a development agency may need to predict diffusion of microfinance takeup in one Indian village given data on diffusion in others. Or an economist at an insurance company may need to predict willingness-to-pay for certain insurance plans given data on willingness-to-pay for others.

Traditionally, economists address this challenge by estimating economic models on existing data and using the estimated parameters to make predictions in new domains. But the predictive success of machine learning algorithms in several economics applications raises the question of whether the economic model is essential in this process, or whether predictions would be improved by training and porting a flexible machine learning algorithm instead.

This is an empirical question: On the one hand, machine learning methods are capable of uncovering novel patterns that existing models miss; on the other, many researchers believe that structured economic models capture fundamental regularities that generalize more reliably across domains. Understanding whether economic models do transfer better across domains is important to understanding their future role within economic analysis and policymaking.

Our paper provides a conceptual framework that formalizes the “out-of-domain” transfer problem, and allows systematic comparison between economic modeling and machine learning algorithms. Instead of considering a particular realization of the data, we consider an ex-ante perspective in which the economist is aware of a set of domains that are relevant but does not know which specific transfer problem will realize from this class of possible transfer problems.

Our main theoretical contribution is the construction of finite-sample forecast intervals that characterize how well a model or algorithm performs in new domains. We provide intervals that are valid for a benchmark setting where all domains are equally likely to realize for training and testing (domains are exchangeable), as well as when the testing domain is qualitatively different from the training domains.

Using this framework, we compare the generalizability of economic models versus black-box machine learning methods in predicting certainty equivalents for lotteries. While machine learning algorithms outperform economic models when trained and tested on (disjoint) data generated under the same conditions, economic models generalize better across domains. Our analysis suggests the primary reason for this is not that the machine learning algorithms overfit, but rather that economic models of risk preference are more effective at extrapolating from observed cases to new ones.

Optimistic rollups rely on fraud proofs — interactive protocols executed on Ethereum to resolve conflicting claims about the rollup's state — to scale Ethereum securely.

To mitigate against potential censorship of protocol moves, fraud proofs grant participants a significant time window, known as the challenge period, to ensure their moves are processed on-chain. Major optimistic rollups today set this period at roughly one week, mainly to guard against strong censorship that undermines Ethereum's own crypto-economic security. However, other forms of censorship are possible, and their implication on optimistic rollup security is not well understood.

This paper considers economic censorship attacks, where an attacker censors the defender's transactions by bribing block proposers. At each step, the attacker can either censor the defender — depleting the defender's time allowance at the cost of the bribe — or allow the current transaction through while conserving funds for future censorship.

We analyze three game-theoretic models of these dynamics and determine the challenge period length required to ensure the defender's success, as a function of the number of required protocol moves and the players' available budgets.

Stackelberg equilibria, as functions of the players' payoffs, can inversely reveal information about the players' incentives. In this paper, we study to what extent one can learn about the leader's incentives by actively querying the leader's optimal commitments against strategically designed followers. We show that, by using polynomially many queries and operations, one can learn a payoff function that is strategically equivalent to the leader's, in the sense that: 1) it preserves the leader's preference over almost all strategy profiles; and 2) it preserves the set of all possible (strong) Stackelberg equilibria the leader may engage in, considering all possible follower types. As an application, we show that the information acquired by our algorithm is sufficient for a follower to induce the best possible Stackelberg equilibrium by imitating a different follower type. To the best of our knowledge, we are the first to demonstrate that this is possible without knowing the leader's payoffs beforehand.

A full version of this paper can be found at https://arxiv.org/abs/2302.11829.

The two standard fairness notions in the resource allocation literature are proportionality and envy-freeness. If there are n agents competing for the available resources, then proportionality requires that each agent receives at least a 1/n fraction of their total value for the set of resources. On the other hand, envy-freeness requires that each agent weakly prefers the resources allocated to them over those allocated to any other agent. Each of these notions has its own benefits, but it is well known that neither one of the two is always achievable when the resources being allocated are indivisible. As a result, a lot of work has focused on satisfying fairness notions that relax either proportionality or envy-freeness.

In this paper, we focus on MXS (a relaxation of proportionality) and EFL (a relaxation of envy-freeness), each of which was previously shown to be achievable on its own [Barman et al., 2018, Caragiannis et al., 2023]. Our main result is an algorithm that constructs allocations that simultaneously satisfy both, combining the benefits of approximate proportionality and approximate envy-freeness. In fact, we prove this for any instance involving agents with valuation functions that are restricted MMS-feasible, which are more general than additive valuations. Also, since every EFL allocation directly satisfies other well-studied fairness notions like EF1, 1/2-EFX, 1/2-GMMS, and 2/3-PMMS, and every MXS allocation satisfies 4/7-MMS, the allocations returned by our algorithm simultaneously satisfy a wide variety of fairness notions.

Citizens' assemblies are an increasingly influential form of deliberative democracy, where randomly selected people discuss policy questions. The legitimacy of these assemblies hinges on their representation of the broader population, but participant dropout often leads to an unbalanced composition. In practice, dropouts are replaced by preselected alternates, but existing methods do not address how to choose these alternates. To address this gap, we introduce an optimization framework for alternate selection. Our algorithmic approach, which leverages learning-theoretic machinery, estimates dropout probabilities using historical data and selects alternates to minimize expected misrepresentation. Our theoretical bounds provide guarantees on sample complexity (with implications for computational efficiency) and on loss due to dropout probability mis-estimation. Empirical evaluation using real-world data demonstrates that, compared to the status quo, our method significantly improves representation while requiring fewer alternates.

We conduct an incentivized laboratory experiment to study people's perception of generative artificial intelligence (GenAI) alignment in the context of economic decision-making. Using a panel of economic problems spanning the domains of risk, time preference, social preference, and strategic interactions, we ask human subjects to make choices for themselves and to predict the choices made by GenAI on behalf of a human user. These problems confront agents with trade-offs (e.g., higher payoff vs. earlier payoff, efficiency vs. equity, riskier but potentially higher rewards vs. safer but lower rewards) and the optimal choices depend on the agent's preferences. We find that people overestimate the degree to which GenAI choices are aligned with human preferences in general (anthropomorphic projection), and with their personal references in particular (self projection). On average, human subjects' predictions about GenAI's choices in every decision environment are much closer to the average human-subject choice than to the average GenAI choice. At the individual level, human subjects' predictions about GenAI's choices in a given environment are highly correlated with their own choices in the same environment.

We explore the implications of anthropomorphic projection and self projection in a stylized theoretical model. Our theoretical analysis shows that anthropomorphic projection and self projection can lead to over-delegation to GenAI. More subtly, we also find that objectively improving AI alignment can harm agents who exhibit anthropomorphic projection (because they mistakenly adjust their delegation decisions in a detrimental fashion). Similarly, among agents who exhibit self projection, welfare may be higher for those who have more unusual preferences (since they are less likely to mistakenly delegate).

The full paper can be found at: https://arxiv.org/abs/2502.14708

The "EIP-1559 algorithm" is used by the Ethereum blockchain to assemble transactions into blocks. While prior work has studied it under the assumption that bidders are "impatient", we analyze it under the assumption that bidders are "patient", which better corresponds to the fact that unscheduled transactions remain in the mempool and can be scheduled at a later time. We show that with "patient" bidders, this algorithm produces schedules of near-optimal welfare, provided it is given a mild resource augmentation (that does not increase with the time horizon). We prove some generalizations of the basic theorem, establish lower bounds that rule out several candidate improvements and extensions, and propose several questions for future work.

A full version of this paper can be found at https://arxiv.org/abs/2502.20031.

In this paper, we explore a scenario where a sender provides an information policy and a receiver, upon observing a realization of this policy, decides whether to take a particular action, such as making a purchase. The sender's objective is to maximize her utility derived from the receiver's action, and she achieves this by careful selection of the information policy. Building on the work of Kleiner et al., our focus lies specifically on information policies that are associated with power diagram partitions of the underlying domain. To address this problem, we employ entropy-regularized optimal transport, which enables us to develop an efficient algorithm for finding the optimal solution. We present experimental numerical results that highlight the qualitative properties of the optimal configurations, providing valuable insights into their structure. Furthermore, we extend our numerical investigation to derive optimal information policies for monopolists dealing with multiple products, where the sender discloses information about product qualities.

Effective teamwork is essential in structured, performance-driven environments, from professional organizations to high-stakes competitions. As tasks grow more complex, high performance requires not only technical proficiency but also interpersonal skills that enable effective coordination. Prior research has identified social skills and familiarity as key drivers of team performance, but their combined effects—particularly in temporary teams—remain underexplored due to data and design limitations. We analyze a large panel dataset of temporary teams in a competitive environment. The data capture millions of interactions in the real-time strategy game Age of Empires 2, where players are assigned quasi-randomly to teams and must coordinate under pressure. We isolate individual contributions to team success by comparing observed outcomes to predictions based on task proficiency. Our findings confirm a robust "team player effect": certain individuals consistently improve team outcomes beyond what their technical skills predict. This effect is amplified by team familiarity—teams with shared experience benefit more from the presence of such individuals. The effect also grows with team size, suggesting that social skills help overcome coordination challenges in larger groups. These results demonstrate the team player effect's robustness in a quasi-randomized, high-stakes setting. Social skills and familiarity interact complementarily—not additively—offering broader implications for team-based production in organizations and labor markets.

The full paper is available at: https://papers.ssrn.com/sol3/papers.cfm?abstract_id=5283300

Copyright policies play a pivotal role in protecting the intellectual property of creators and companies in creative industries. The advent of cost-reducing technologies, such as generative AI, in these industries calls for renewed attention to the role of these policies. This paper studies competition in a market of creatively differentiated products and the competitive and welfare effects of copyright protection. A common feature of products with creative elements is that their key attributes (e.g., images and text) are unstructured and thus high-dimensional. We focus on a stylized design product, fonts, and use data from the world's largest online marketplace for fonts. We construct neural network embeddings to quantify unstructured attributes and measure the visual similarity. We show that this measure closely aligns with actual human perception. Based on this measure, we empirically find in a descriptive analysis that competitions occur locally in the visual characteristics space. We then develop a structural model for supply and demand that integrate the embeddings. On the supply side, our model describes firms' location choices within the visual characteristics space as well as pricing and entry decisions. A copyright policy is modeled as imposing restrictions on the area of possible choices in the characteristics space, providing local protection to right holders. On the demand side, we characterize consumers' heterogeneous preferences for visual attributes, focusing on recovering substitution patterns across different designs. Overall, the estimated demand model reveals that the substitution patterns are effectively explained by the visual similarity. The estimated supply-side model indicates that the firm's development costs are low when mimicking close competitors and increase as products become more visually differentiated. This suggests the existence of a mimicking externality: the presence of a design product reduces the fixed costs of visually similar entrants. Through counterfactual analyses, we find that local copyright protection can enhance consumer welfare when products are relocated, and the interplay between copyright and cost-reducing technologies is essential in determining an optimal policy for social welfare. We believe that the embedding analysis and empirical models introduced in this paper can be applicable to a range of industries where unstructured data captures essential features of products and markets.

We consider a two-person inspection game, in which a defender positions a limited number of detectors across a critical system to detect multiple attacks caused by an attacker. We assume that detection is imperfect, and each detector location is associated with a probability of detecting attacks within its set of monitored system components. The objective of the defender (resp. attacker) is to minimize (resp. maximize) the expected number of attacked components that remain undetected. To compute Nash Equilibria (NE) for this large-scale zero-sum game, we formulate a linear program with a small number of constraints, which we solve via column generation. We provide an exact mixed-integer program for the pricing problem, which entails computing a defender's pure best response, and leverage its supermodular structure to derive two efficient approaches to obtain approximate NE with theoretical guarantees: A column generation and a multiplicative weights update (MWU) algorithm with approximate best responses. To address the computational challenges posed by combinatorial attacker strategies, each iteration of our MWU algorithm requires computing a projection under the unnormalized relative entropy. We provide a closed-form solution and a linear-time algorithm for the projection problem. Our computational results in real-world gas distribution networks illustrate the performance and scalability of our solution approaches.

A full version of this article is available at https://arxiv.org/abs/2404.11545.

We study the problem of fair allocation of indivisible goods for subadditive agents. While constant-MMS bounds have been given for additive and fractionally subadditive agents, the best existential bound for the case of subadditive agents is 1/O(log n log log n). In this work, we improve this bound to a 1/O((log log n)²)-MMS guarantee. To this end, we introduce new matching techniques and rounding methods for subadditive valuations that we believe are of independent interest and will find their applications in future work.

We study the set of multidimensional monotone functions from [0, 1]ⁿ to [0, 1] as well as their one-dimensional marginals. We characterize the extreme points of these convex sets subject to finitely many linear constraints. These characterizations lead to new results in various mechanism design and information design problems, including public good provision with interdependent values; interim efficient bilateral trade mechanisms; asymmetric reduced form auctions; and optimal private private information structure. As another application, we also present a mechanism anti-equivalence theorem for two-agent, two-alternative social choice problems: A mechanism is payoff-equivalent to a deterministic DIC mechanism if and only if they are ex-post equivalent.

A subset A of [0,1]ⁿ is said to be an up-set if for any x ∈ A, every element larger than x also belongs to A. It is known that a monotone function from [0,1]ⁿ to [0,1] is an extreme point if and only if it is an indicator function on an up-set. Therefore, every extreme point of the set of multidimensional monotone functions that satisfy m < ∞ linear constraints must be a mixture of m + 1 indicator functions on up-sets. Our first main result sharpens this characterization and shows that every extreme point of such sets must be a mixture of at most m + 1 indicator functions on nested up-sets, so that these up-sets must be totally ordered. Our second main result characterizes the extreme points of tuples of monotone functions that can be rationalized by a multidimensional function from [0, 1]ⁿ to [0, 1], subject to m linear constraints. We show that every extreme point of rationalizable tuples must be rationalized by at most m + 1 indicator functions defined on nested up-sets. When n = 2 and m = 0, this characterization is tight, and every extreme point is also uniquely rationalized by an indicator function on an up-set. When n = 2 and m = 1, every extreme point must be rationalized by a mixture of two indicators on nested up-sets that differ by a rectangle.

These abstract characterizations have multiple economic applications. In the setting of public good provision with two alternatives, our characterizations immediately lead to a characterization of a surplus-maximizing ex-post IC and IR mechanism subject to an ex-ante budget constraint. In the setting of bilateral trade, our characterization immediately leads to a characterization of interim efficient mechanisms. In the setting of a two-agent, two-alternative and independent private value allocation problem, our characterization implies that BIC-DIC equivalence and deterministic-stochastic equivalence can never hold at the same time. For a general n agent, two alternative, independent private value allocation problem, we also show that there is no non-trivial BIC-DIC equivalence for mechanisms that are uniquely optimal for some linear objective. Our results can also be applied to settings of asymmetric reduced-form auctions, as well as private private information.

A full version of this paper can be found at https://arxiv.org/abs/2502.18876.

In an auction, a seller may masquerade as one or more bidders in order to manipulate the clearing price. We characterize single-item auction formats that are shill-proof in the sense that a profit-maximizing seller has no incentive to submit shill bids. We distinguish between strong shill-proofness, in which a seller with full knowledge of bidders' valuations can never profit from shilling, and weak shill-proofness, which requires only that the expected equilibrium profit from shilling is nonpositive. The Dutch auction (with a suitable reserve) is the unique (revenue-)optimal and strongly shill-proof auction. Moreover, the Dutch auction (with no reserve) is the unique prior-independent auction that is both efficient and weakly shill-proof. While there are multiple ex-post incentive compatible, weakly shill-proof, and optimal auctions; any optimal auction can satisfy only two properties in the set {static, ex-post incentive compatible, weakly shill-proof}.

Full Paper: https://arxiv.org/abs/2404.00475

We study rental games—a single-parameter dynamic mechanism design problem, in which a designer rents out an indivisible asset over n days. Each day, an agent arrives with a private valuation per day of rental, drawn from that day's (known) distribution. The designer can either rent out the asset to the current agent for any number of remaining days, charging them a (possibly different) payment per day, or turn the agent away. Agents who arrive when the asset is not available are turned away. A defining feature of our dynamic model is that agents are stagewise-IR (individually rational), meaning they reject any rental agreement that results in temporary negative utility, even if their final utility is positive. We ask whether and under which economic objectives it is useful for the designer to exploit the stagewise-IR nature of the agents.

We show that an optimal rental mechanism can be modeled as a sequence of dynamic auctions with seller costs. However, the stagewise-IR behavior of the agents makes these auctions quite different from classical single-parameter auctions: Myerson's Lemma does not apply, and indeed we show that truthful mechanisms are not necessarily monotone, and payments do not necessarily follow Myerson's unique payment rule. We develop alternative characterizations of optimal mechanisms under several classes of economic objectives, including generalizations of welfare, revenue and consumer surplus. These characterizations allow us to use Myerson's unique payment rule in several cases, and for the other cases we develop optimal mechanisms from scratch. Our work shows that rental games raise interesting questions even in the single-parameter regime.

A full version of this paper can be found at https://arxiv.org/abs/2505.07579.

We develop an economic framework to analyze the optimal pricing and product design of Large Language Models (LLM). Our framework captures several key features of LLMs: variable operational costs of processing input and output tokens; the ability to customize models through fine-tuning; and high-dimensional user heterogeneity in terms of task requirements and error sensitivity. In our model, a monopolistic seller offers multiple versions of LLMs through a menu of products. The optimal pricing structure depends on whether token allocation across tasks is contractible and whether users face scale constraints.

When it is possible to contract on the entire assignment of tokens to tasks, the seller's problem ("Token Allocations") is an infinite-dimensional screening problem, which is well-known to be difficult. We are nonetheless able to make progress in two important classes of environments: binary environment and two dimensional value-scale heterogeneity, in which case users with similar aggregate value-scale characteristics choose similar levels of fine-tuning and token consumption. When only the total number of tokens is contractible ("Token Packages"), we leverage the tractability of a constant elasticity of substitution framework to drastically simplify the problem: the buyer's type-a function mapping each task to a value of precision- is an index. This index for the value of precision allows the seller to solve a one-dimensional screening problem. The optimal mechanism can be implemented through menus of two-part tariffs, with higher markups for more intensive users. Our results rationalize observed industry practices such as tiered pricing based on model customization and usage levels. A full version of this paper can be found at https://arxiv.org/abs/2502.07736.

Experiments in online platforms frequently suffer from network interference, where treatments applied to one unit affect outcomes of connected ones, violating the Stable Unit Treatment Value Assumption (SUTVA) and substantially biasing treatment effect estimations. A common solution is to cluster connected units and randomize treatments at the cluster level, typically followed by estimation using either a simple difference-in-means (DM) estimator, which ignores remaining interference and suffers from O(δ) bias where δ measures interference strength; or the unbiased Horvitz-Thompson (HT) estimator, which eliminates bias through importance sampling but incurs exponentially high variance scaling with d, the maximum network degree. This fundamental limitation persists even with sophisticated clustering designs, creating narrow bias-variance tradeoffs often inadequate for practical applications.

Motivated by this gap, we introduce a novel estimator called Differences-in-Neighbors (DN) that achieves favorable bias-variance tradeoffs. The key insight underlying DN is that when measuring the impact of i's treatment, one should also include the outcomes of the neighbors of i. Notably, DN reveals that temporal interference can be viewed as a special case of network interference, enabling a unified estimation framework.

Our main theoretical contribution shows that DN achieves bias O(d²δ²), second order in δ, while maintaining polynomial variance of O(d⁴/N). We also introduce a version of the DN estimator tailored to clustered experimental designs. This estimator achieves bias O(∑i(d_i - d^C_i)²/N·δ²), where d^C_i represents the within-cluster degree of node i, showing a reduced dependence on degree compared to the unit-level design due to the clustering structure. This provides an additional dimension for bias reduction orthogonal to δ order reduction.

Our empirical evaluation validates DN's superior practical performace. On both synthetic random graphs (small-world and Erdős-Rényi) and a real Twitter network graph (81, 306 nodes), DN consistently outperforms DM with various clustering granularity. Most compellingly, in a pricing experiment conducted on a city-scale ride-sharing simulator, DN reduces bias by over 50% and RMSE by 35% relative to the naive DM estimator. This experiment demonstrates DN's effectiveness in spatio-temporal settings without closed-form outcome functions, confirming its superior performance at practical scales.

The full paper is available at https://arxiv.org/abs/2503.02271.

Regulations mandating consumer consent for data collection and use have led firms to employ "dark patterns"—interface designs that encourage data sharing. We study the causal effects of these designs on consumer consent choices and explore their implications for consumer welfare. We conduct a field experiment where a browser extension randomizes consent interfaces while study participants browse the internet. We find that consumers accept all cookies over half of the time absent dark patterns, with substantial user heterogeneity. Hiding options behind an extra click significantly sways choices toward visible options, while purely visual manipulations have smaller impacts. Users also frequently close banners without active selection, highlighting the importance of default settings. While better-known firms achieve higher baseline consent rates, dark patterns do not amplify this advantage. We use a structural model to show that the consumer surplus-maximizing banner removes dark patterns and defaults to accepting cookies upon consumer inaction. A browser-level global consent choice further improves consumer welfare compared to site-by-site consent interactions, primarily by reducing time costs.

We consider assortment and inventory planning problems with dynamic stockout-based substitution effects, and without replenishment, in two different settings: (1) Customers can see all available products when they arrive, a typical scenario in physical stores. (2) The seller can choose to offer a subset of available products to each customer, which is more common on online platforms. Both settings are known to be computationally challenging, and the current approximation algorithms for the two settings are quite different. We develop a unified algorithm framework under the MNL choice model for both settings. Our algorithms improve on the state-of-the-art algorithms in terms of approximation guarantee and runtime, and the ability to manage uncertainty in the total number of customers and handle more complex constraints. In the process, we establish various novel properties of dynamic assortment planning (for the MNL choice model) that may be useful more broadly. A full version of this paper can be found at https://arxiv.org/abs/2404.03604.

In the well-studied metric distortion problem in social choice, we have voters and candidates located in a shared metric space, and the objective is to design a voting rule that selects a candidate with minimal total distance to the voters. However, the voting rule has limited information about the distances in the metric, such as each voter's ordinal rankings of the candidates in order of distances. The central question is whether we can design rules that, for any election and underlying metric space, select a candidate whose total cost deviates from the optimal by only a small factor, referred to as the distortion.

A long line of work resolved the optimal distortion of deterministic rules, and recent work resolved the optimal distortion of randomized (weighted) tournament rules, which only use the aggregate preferences between pairs of candidates. In both cases, simple rules achieve the optimal distortion of 3. Can we achieve the best of both worlds: a deterministic tournament rule matching the lower bound of 3? Prior to our work, the best rules have distortion [EQUATION].

In this work, we establish a lower bound of 3.1128 on the distortion of any deterministic tournament rule, even when there are only 5 candidates, and improve the upper bound with a novel rule guaranteeing distortion 3.9312. We then generalize tournament rules to the class of k-tournament rules which obtain the aggregate preferences between k-tuples of candidates. We show that there is a family of deterministic k-tournament rules that achieves distortion approaching 3 as k grows. Finally, we show that even with k = 3, a randomized k-tournament rule can achieve distortion less than 3, which had been a longstanding barrier even for the larger class of ranked voting rules.

The full version of the paper can be found here: https://arxiv.org/pdf/2505.13630.

Discrete choice models are fundamental for predicting how individuals select among alternatives based on their preferences and the attributes of the options. Traditional Random Utility Models assume stochastic rationality, often failing to capture context-dependent behavior—where the presence of certain alternatives alters the perceived utility of others.

In this work, we introduce a flexible framework that embeds choice utilities into a vector-valued Reproducing Kernel Hilbert Space (RKHS) over choice-set and feature pairs, and thereby captures high-order interactions among items without imposing strong structural assumptions. In the featureless setting, we design a set kernel that accommodates varying choice-set sizes via a masking mechanism; with features, we construct a product kernel that combines set structure with item-specific attributes. Estimation under a fixed kernel reduces to a finite-dimensional convex program via the Representer Theorem.

To ensure scalability, we propose two approaches: (i) random-feature approximations, which map data into a randomized low-dimensional space, reducing computational costs from quadratic to linear in both the number of items and samples; and (ii) a Neural Tangent Kernel formulation, which adopts deep multi-head attention neural architectures to learn a data-adaptive kernel, enabling efficient convergence via stochastic gradient descent. We establish generalization bounds that avoid the exponential "curse of cardinality". Empirical results on synthetic and real-world datasets demonstrate that our approach consistently outperforms existing benchmarks in both predictive accuracy and generalization.

The full paper is available at https://ssrn.com/abstract=5267975.

We revisit the celebrated Ranking algorithm by Karp, Vazirani, and Vazirani (STOC 1990) for online bipartite matching under the random arrival model, that is shown to be 0.696-competitive for unweighted graphs by Mahdian and Yan (STOC 2011) and 0.662-competitive for vertex-weighted graphs by Jin and Williamson (WINE 2021).

In this work, we explore the limitation of the primal-dual analysis of Ranking and aim to bridge the gap between unweighted and vertex-weighted graphs. We show that the competitive ratio of Ranking is between 0.686 and 0.703, under our current knowledge of Ranking and the framework of primal-dual analysis. This confirms a conjecture by Huang, Tang, Wu, and Zhang (TALG 2019), stating that the primal-dual analysis could lead to a competitive ratio that is very close to 0.696. Our analysis involves proper discretizations of a variational problem and uses LP solver to pin down the numerical number. As a bonus of our discretization approach, our competitive analysis of Ranking applies to a more relaxed random arrival model. E.g., we show that even when each online vertex arrives independently at an early or late stage, the Ranking algorithm is at least 0.665-competitive, beating the 1 - 1/e ≈ 0.632 competitive ratio under the adversarial arrival model.

In many auction settings the auctioneer must disclose the identity of the winner and the price he pays. We characterize the auction that minimizes the winner's privacy loss among those that maximize total surplus or the seller's revenue, and are strategy-proof. Privacy loss is measured with respect to what an outside observer learns from the disclosed price, and is quantified by the mutual information between the price and the winner's willingness to pay. When only interim individual-rationality is required, the most privacy preserving auction involves stochastic ex-post payments. Under ex-post individual rationality, and assuming the bidders' type distribution exhibits a monotone hazard rate, privacy loss is minimized by the second-price auction with deterministic payments.

Full version available at: https://eilatr.github.io/ppa/PPA.pdf

Motivated by the recent popularity of machine learning training services, we introduce a contract design problem in which a provider sells a service that results in an outcome of uncertain quality for the buyer. The seller has a set of actions that lead to different distributions over outcomes. We focus on a setting in which the seller has the ability to commit to an action and the buyer is free to accept or reject the outcome after seeing its realized quality. Our model is related to Mussa and Rosen's classic paper on selling products of differing qualities and monopolist lottery pricing, as well as recent work on selling hidden actions.

We propose a two-stage payment scheme where the seller designs a menu of contracts, each of which specifies an action, an upfront price and a vector of outcome-dependent usage prices. Upon selecting a contract, the buyer pays the upfront price, and after observing the realized outcome, the buyer either accepts and pays the corresponding usage price, or rejects and is exempt from further payment. We show that this two-stage payment structure is necessary to maximize profit: only upfront prices or only usage prices is insufficient. We then study the computational complexity of computing a profit-maximizing menu in our model. While computing the exact maximum seller profit is NP-hard even for two buyer types, we derive a fully-polynomial time approximation scheme (FPTAS) for the maximum profit for a constant number of buyer types. Finally, we prove that in the single-parameter setting in which buyers' valuations are parametrized by a single real number that seller revenue can be maximized using a menu consisting of a single contract.

A full version of the paper is available at https://arxiv.org/abs/2502.13334.

I develop a model of peer conversation. The key features are that conversation is voluntary (both parties must consent for conversation to occur) and learning is mutual (both parties learn from one another). Under these assumptions, even small costs of communication can greatly affect selection into communication. In a static two-person setting, selection can be advantageous (better-informed individuals talk more) or adverse (the opposite pattern). I characterize when these different situations arise. In a dynamic model of sequential communication in larger groups, adverse selection dominates as the group grows. Signals of intermediate precision facilitate communication; a planner diffusing information prefers such signals. Contracts for communication only partially resolve selection problems. These results suggest an explanation for the slow information diffusion observed empirically in some settings.

A full version of this paper can be found at: https://tinyurl.com/selectedcommunication.

A seminal result of [Fleischer et al., 2004], [Karakostas and Kolliopoulos, 2004] and [Yang and Huang, 2004] states that system optimal multi-commodity static network flows are always implementable as tolled Wardrop equilibrium flows even if users have heterogeneous value-of-time sensitivities. Their proof uses LP-duality to characterize the general implementability of network flows by tolls. For the much more complex setting of dynamic flows, [Graf et al., 2025] identified necessary and sufficient conditions for a dynamic s-d flow to be implementable as a tolled dynamic equilibrium. They used the machinery of (infinite-dimensional) strong duality to obtain their characterizations. Their work, however, does not answer the question of whether system optimal dynamic network flows are implementable by tolls.

We consider this question for a general dynamic flow model involving multiple commodities with individual source-destination pairs, fixed inflow rates and heterogeneous valuations of travel time and money spent. We present both a positive and a, perhaps surprising, negative result: For the negative result, we provide a network with multiple source and destination pairs in which under the Vickrey queuing model no system optimal flow is implementable - even if all users value travel times and spent money the same. Our counter-example even shows that the ratio of the achievable equilibrium travel times by using tolls and of the system optimal travel times can be unbounded. For the single-source, single-destination case, we show that if the traversal time functions are suitably well-behaved (as is the case, for example, in the Vickrey queuing model), any system optimal flow is implementable.

The full version of this paper is available at https://arxiv.org/abs/2503.07387.

Metric distortion in social choice is a framework for evaluating how well voting rules minimize social cost when both voters and candidates exist in a shared metric space, with a voter's cost defined by their distance to a candidate. Voters submit rankings, and the rule aggregates these rankings to determine a winner. We extend this framework to incorporate probabilistic voting, recognizing that real-world voters exhibit randomness in how they vote. Our extension includes various probability functions, notably the widely studied Plackett-Luce (PL) model.

We show that the distortion results under probabilistic voting better correspond with conventional intuitions regarding popular voting rules such as Plurality, Copeland, Random Dictator and Borda than those under deterministic voting. For example, in the PL model with candidate strength inversely proportional to the square of their metric distance from a voter, we show that Copeland's distortion is at most 2, whereas that of RandomDictator is [EQUATION] in large elections (i.e., number of voters n → ∞), where m is the number of candidates. This contrasts sharply with the classical model, where RandomDictator beats Copeland with a distortion of 3 versus 5. In the PL model where the candidate strength is inversely proportional to the distance raised to power θ, the distortion under Borda is Θ(m^1–2/θ) when θ > 2 and Θ(1) otherwise. This generalizes the classical deterministic voting model where the distortion of Borda is 2m - 1. The proof uses a novel variant of asymptotic duality where we choose the Lagrange multiplier via asymptotically maximizing the derivative of the objective function. Overall, our work opens a new frontier for analyzing voting rules.

Pure proportional voting rules can sometimes lead to highly suboptimal outcomes. We introduce the Method of Equal Shares with Bounded Overspending (BOS Equal Shares), a robust variant of the Method of Equal Shares that balances proportionality and efficiency. BOS Equal Shares addresses inefficiencies implied by strict proportionality axioms, yet still provides fairness guarantees, similar to the original Equal Shares. Our extensive empirical analysis shows excellent performance of BOS Equal Shares across several metrics. In the course of the analysis, we also study a fractional variant of the Method of Equal Shares.

Experimentation in online digital platforms is often used to inform decision making. Specifically, the goal of many experiments is to optimize a metric of interest. Null hypothesis statistical testing can be ill-suited to this task, as it is indifferent to the magnitude of effect sizes and opportunity costs. Moreover, in practice, related experiments can often be grouped into portfolios called experimentation programs where the goal is to optimize a single metric. Past tests in an experimentation program inform useful priors on treatment effects. In these settings, we discuss how experimentation practice should change when the goal is optimization. We survey the literature on Bayesian and empirical Bayes analyses of A/B test portfolios, and single out the A/B Testing Problem [Azevedo et al., 2020] as a starting point, which treats experimentation as a constrained optimization problem. We emphasize that the framework can be implemented by appropriately tuning p-value thresholds, a result which seems under-utilized by practitioners. Furthermore, we develop several extensions of the A/B testing problem to managing multiple experimentation programs, managing a single program over time, and allowing units to be enrolled in multiple tests. Each of these can be solved by dynamic programming, and together they extend the utility of the framework in practice. We also consider the case of new experimentation programs without a strong prior on treatment effects. Finally, we discuss the implications of these results on experimentation programs in industry. For example, under no-cost assumptions, firms should be testing many more ideas, reducing test allocation sizes, and relaxing p-value thresholds away from p = 0.05. These results are exemplified with an application to data from Netflix experimentation programs. A draft of the paper may be found at https://arxiv.org/abs/2412.05508.

Recent work [Soleymani et al., 2025] introduced a variant of Optimistic Multiplicative Weights Updates (OMWU) that adaptively controls the learning pace in a dynamic, non-monotone manner, achieving new state-of-the-art regret minimization guarantees in general games. In this work, we demonstrate that no-regret learning acceleration through adaptive pacing of the learners is not an isolated phenomenon. We introduce Cautious Optimism, a framework for substantially faster regularized learning in general games. Cautious Optimism takes as input any instance of Follow-the-Regularized-Leader (FTRL) and outputs an accelerated no-regret learning algorithm by pacing the underlying FTRL with minimal computational overhead. Importantly, we retain uncoupledness (learners do not need to know other players' utilities). Cautious Optimistic FTRL achieves near-optimal O_T (log T) regret in diverse self-play (mixing-and-matching regularizers) while preserving the optimal O(T) regret in adversarial scenarios. In contrast to prior works (e.g. Syrgkanis et al. [2015], Daskalakis et al. [2021]), our analysis does not rely on monotonic step-sizes, showcasing a novel route for fast learning in general games. A full version of this paper can be found at https://arxiv.org/abs/2506.05005.

We study the problem of delegated choice with inspection cost (DCIC), which is a variant of the delegated choice problem by Kleinberg and Kleinberg (EC'18) as well as an extension of the Pandora's box problem with nonobligatory inspection (PNOI) by Doval (JET'18). In our model, an agent may strategically misreport the proposed element's utility, unlike the standard delegated choice problem which assumes that the agent truthfully reports the utility for the proposed alternative. Thus, the principal needs to inspect the proposed element possibly along with other alternatives to maximize its own utility, given an exogenous cost of inspecting each element. Further, the delegation itself incurs a fixed cost, thus the principal can decide whether to delegate or not and inspect by herself.

We show that DCIC indeed is a generalization of PNOI where the side information from a strategic agent is available at certain cost, implying its NP-hardness by Fu, Li, and Liu (STOC'23). In fact, we observe that DCIC becomes significantly more challenging than PNOI and the delegated choice problem in several aspects. First, neither of (i) running PNOI policy without delegation nor (ii) running a simple delegation mechanism can achieve a constant approximation to the optimal mechanism for DCIC, implying that we need to use both the delegation and inspection for efficient mechanisms. Furthermore, the standard approaches to PNOI (or Pandora's box problem) for upper bounding the optimal policy in a structured way to obtain algorithms do not easily extend to DCIC.

Nevertheless, we provide constant approximate mechanisms for DCIC problem. En route to this result, we first consider a costless delegation setting in which the cost of delegation is free. We prove that the maximal mechanism over the pure delegation with a single inspection and an PNOI policy without delegation achieves a 3-approximation for DCIC with costless delegation, which is further proven to be tight. These results hold even when the cost comes from an arbitrary monotone set function, and can be improved to a 2-approximation if the cost of inspection is the same for every element. We extend these techniques by presenting a constant factor approximate mechanism for the general setting for rich class of instances.

A principal delegates a project to a team S from a pool of n agents. The project's value if all agents in S exert costly effort is f(S). To incentivize the agents to participate, the principal assigns each agent i ∈ S a share ρ_i ∈ [0,1] of the project's final value (i.e., designs n linear contracts). The shares must be feasible—their sum should not exceed 1. It is well-understood how to design these contracts to maximize the principal's own expected utility, but what if the goal is to coordinate the agents toward maximizing social welfare?

We initiate a systematic study of multi-agent contract design with objectives beyond principal's utility including welfare maximization, for various classes of value functions f. Our exploration reveals an arguably surprising fact: If f is up to XOS in the complement-free hierarchy of functions, then the optimal principal's utility is a constant-fraction of the optimal welfare. This is in stark contrast to the much larger welfare-utility gaps in auction design, and no longer holds above XOS in the hierarchy, where the gap can be unbounded.

Such constant bounds on the welfare-utility gap immediately imply that existing algorithms for designing contracts with approximately-optimal principal's utility, in fact also guarantee approximately-optimal welfare. The downside of reducing welfare to utility in this way is the loss of large constants. To obtain better guarantees, we develop polynomial-time algorithms directly for welfare, for different classes of value functions. These include a tight 2-approximation to the optimal welfare for symmetric XOS functions.

Finally, we extend our analysis beyond welfare to the objective of approximating the project's value under general budget-feasibility constraints. Our results immediately translate to budgeted welfare and utility.

We study committee voting rules under ranked preferences, which map the voters' preference relations to a subset of the alternatives of predefined size. In this setting, the compatibility between proportional representation and committee monotonicity is a fundamental open problem that has been mentioned in several works. We address this research question by designing a new committee voting rule called the Solid Coalition Refinement (SCR) rule that simultaneously satisfies committee monotonicity and Dummett's PSC as well as one of its variants called inclusion PSC. This is the first rule known to satisfy both of these properties. Moreover, we show that this is effectively the best that we can hope for as other fairness notions adapted from approval voting are incompatible with committee monotonicity. For truncated preferences, we prove that the SCR rule still satisfies PSC and a property called independence of losing voter blocs, thereby refuting a conjecture of Graham-Squire et al. (2024). Finally, we discuss the consequences of our results in the context of rank aggregation.

We study whether a given Nash equilibrium can be improved within the set of correlated equilibria for arbitrary objectives. Our main contribution is a sharp characterization: in a generic game, a Nash equilibrium is an extreme point of the set of correlated equilibria if and only if at most two agents randomize. Consequently, any sufficiently mixed Nash equilibrium involving at least three randomizing agents can always be improved by correlating actions or switching to a less random equilibrium, regardless of the underlying objective. We show that even if one focuses on objectives that depend on payoffs, excess randomness in equilibrium implies improvability. We extend our analysis to symmetric games and coarse correlated equilibria, revealing a fundamental tension between the randomness in Nash equilibria and their optimality.

Full version: https://www.lyariv.com/papers/ExtremeEquilibria.pdf.

We study resource allocation in two-sided markets from a fundamental perspective and introduce a general modeling and algorithmic framework to effectively incorporate the complex and multidimensional aspects of fairness. Our main technical contribution is to show the existence of a range of near-feasible resource allocations parameterized in different model primitives to give flexibility when balancing the different policymaking requirements, allowing policy designers to fix these values according to the specific application. To construct our near-feasible allocations, we start from a fractional resource allocation and perform an iterative rounding procedure to get an integer allocation. We show a simple yet flexible and strong sufficient condition for the target feasibility deviations to guarantee that the rounding procedure succeeds, exhibiting the underlying trade-offs between market capacities, agents' demand, and fairness. To showcase our framework's modeling and algorithmic capabilities, we consider three prominent market design problems: school allocation, stable matching with couples, and political apportionment. In each of them, we obtain strengthened guarantees on the existence of near-feasible allocations capturing the corresponding fairness notions, such as proportionality, envy-freeness, and stability.

The world is constantly changing, yet decision makers do not continuously update their worldview. When should one acquire new information and what should they learn? This paper develops a tractable framework to study the tradeoff between the timing and content of information acquisition. A decision maker sequentially choose times at which to acquire information (entailing a fixed cost) and what to learn (entailing a variable cost) about a changing state. I characterize optimal policies, using an appropriate Bellman equation that decomposes the problem into a static optimal information acquisition problem and an optimal stopping problem. Optimal information acquisition must eventually either stop or settle into a simple cycle in which information is acquired at regular intervals (when uncertainty reaches specific thresholds) and updates lead to two possible outcomes, captured by two target posterior beliefs. The convergence result enables the study of properties of long run optimal information acquisition. Optimal policies may exhibit path dependency in the form of "learning traps". The world becoming more volatile has generically ambiguous effects on the frequency of information acquisition. In the limit as fixed costs vanish, the agent optimally either waits or acquires infinitesimal amounts of information so as to confirm the current belief until rare news prompts a jump to an alternative belief; in the long run, the agent's belief jumps between two possible beliefs (and actions). In an application to a portfolio problem, optimal behavior exhibits continuous rebalancing towards diversification, punctuated by periodic shifts to more extreme allocations. With asymmetry between a safe and a risky action, optimal information acquisition can generate distortions between good and bad news, typically leading to better quality but more frequent updating for information which suggests undertaking risky actions.

Link to full paper: https://cesarbarilla.com/files/Barilla_When-And-What.pdf

In many real-world applications such as data centers and cloud computing, the systems often consist of multiple frontends (routers) that receive job requests and backends (servers) that process these jobs. Efficient resource management is becoming increasingly important given the growing demand for serving machine learning inference queries, which incur high latencies and require expensive computational resources.

Motivated by this, we study distributed load balancing in bipartite queueing systems, where a set of frontends independently route jobs to a set of backends that have heterogeneous workload-dependent service rates, modeled as general functions of their workload. The system's connectivity—governed by compatibility constraints like data residency or resource requirements—is represented by an arbitrary bipartite graph. We assume at each period, the number of jobs arriving at each frontend is drawn independently with fixed mean and the number of jobs departing from each backend equals its instantaneous workload-dependent service rate in expectation.

We propose a simple distributed load balancing policy called the Greatest Marginal Service Rate policy (GMSR): when a job arrives at a frontend, it is routed to a connected backend with the highest marginal service rate. GMSR is agnostic to job arrival rates and fully distributed while facilitates effective coordination among frontends. We show the discrete-time stochastic system dynamics converges to a fluid limit when we scale the arrival rates and normalize the workload correspondingly. In this fluid limit, we show that GMSR drives every δ-suboptimal initial workload to ϵ-suboptimality in O(δ + log 1/ϵ) time, ensuring stability and asymptotic latency optimality. Our analyses introduce a novel Lyapunov function that depends on flow imbalance (difference between job arrivals and service completions) and develop a combinatorial argument to show that the Lyapunov function consistently decreases over time, which may be of independent interest.

A full version of this paper can be found at https://arxiv.org/pdf/2411.17103.

Achieving covariate balance in randomized experiments enhances the precision of treatment effect estimation. However, existing methods often require heuristic adjustments based on domain knowledge and are primarily developed for binary treatments.

This paper presents Gaussianized Design Optimization, a novel framework for optimally balancing covariates in experimental design. The core idea is to Gaussianize the treatment assignments: we model treatments as transformations of random variables drawn from a multivariate Gaussian distribution. Under Gaussianization, we derive a measure of covariate balance as a function of covariates and the Gaussian covariance matrix, which effectively assesses the estimation error of the widely used Horvitz-Thompson estimator. This converts the design problem into a nonlinear continuous optimization over Gaussian covariance matrices. Compared to existing methods, our approach offers great flexibility in optimizing covariate balance across a diverse range of designs and covariate types.

Adapting the Burer-Monteiro approach for solving semidefinite programs, we introduce first-order local algorithms for optimizing covariate balance, improving upon several widely used designs. Furthermore, we develop inferential procedures for constructing design-based confidence intervals under Gaussianization and extend the framework to accommodate continuous treatments. Simulations demonstrate the effectiveness of Gaussianization in multiple practical scenarios.

The full version of this paper can be found at https://arxiv.org/abs/2502.16042.

Many industries, including the NFL with the Rooney Rule and law firms with the Mansfield Rule, have adopted interview-stage diversity interventions requiring a minimum representation of disadvantaged groups in the interview set. However, the effectiveness of such policies remains inconclusive. In light of this, we develop a framework of a two-stage hiring process, where rational firms, with limited interview and hiring capacities, aim to maximize the match value of their hires. The labor market consists of two equally sized social groups, m and w, with identical ex-post match value distributions. Match values are revealed only post-interview, while interview decisions rely on partially informative pre-interview scores. Pre-interview scores are more informative for group m, while interviews reveal more for group w; as a result, if firms could interview all candidates, both groups would be equally hired. However, due to limited interview capacity and information asymmetry, we show that requiring equal representation in the interview stage does not translate into equal representation in the hiring outcome, even though interviews are more informative for group w. In certain regimes, with or without intervention, a firm may interview more group w candidates but still hire fewer. At an individual level, we show that strong candidates from both groups benefit from the intervention as the candidate-level competition weakens. For borderline candidates, only group w candidates gain at the expense of group w. To understand the impact of non-universal interview-stage interventions on the market, we study a model with two vertically differentiated firms, where only the top firm adopts the intervention. We characterize the unique equilibrium and demonstrate potentially negative effects: we show that in certain regimes the lower firm hires fewer group w candidates due to increased firm-level competition for them, and further find examples where overall fewer group w candidates are hired across the market. At an individual level, while superstar candidates in both groups benefit, surprisingly the impact on borderline candidates may reverse: the lower firm may replace borderline group w candidates with borderline group m candidates in its interview set, effectively reducing the chance of those borderline group w candidates being hired. Overall, our findings highlight challenges in diversifying the labor market at early hiring stages due to information asymmetry, filtering, and competition. Beyond our context, our natural framework of a market with two-stage hiring may be of independent interest.

The full version of our paper is available at https://papers.ssrn.com/sol3/papers.cfm?abstract_id=5179386.

This paper develops a flexible approach to predict the price effects of horizontal mergers using ML/AI methods. While standard merger simulation techniques rely on restrictive assumptions about firm conduct, we propose a data-driven framework that relaxes these constraints when rich market data are available. We develop and identify a flexible nonparametric model of supply that nests a broad range of conduct models and cost functions. To overcome the curse of dimensionality, we adapt the Variational Method of Moments (VMM) [Bennett and Kallus, 2023] to estimate the model, allowing for various forms of strategic interaction. Monte Carlo simulations show that our method significantly outperforms an array of misspecified models and rivals the performance of the true model, both in test sample prediction and in counterfactual merger simulations. As a way to interpret the economics of the estimated supply function, we simulate pass-through and find that the model learns markup and cost functions that imply approximately correct pass-through. Applied to the American Airlines-US Airways merger, our method produces more accurate post-merger price predictions than traditional approaches. The results demonstrate the potential for ML/AI techniques to enhance merger analysis while maintaining (nonparametric) structure from economics.

A full version of the paper is available on SSRN.

Screening settings, in which a profit-maximizing principal faces a privately-informed agent, have been studied extensively in the economics literature. A leading example is second-degree price discrimination with alternatives that correspond to different quantities or qualities of a product. In this case, it is natural to order the alternatives from worst (lowest quantity/quality) to best (highest quantity/quality) and to assume that the agent's private information concerns his marginal willingness to pay (for quantity/quality). This results in "increasing differences," which states that for any pair of alternatives, higher types are willing to pay more than lower types in order to obtain the better alternative instead of the worse one.

Many natural settings, however, involve alternatives and types that are not naturally ordered from "best" to "worst" or from "low" to "high." To analyze such settings, we investigate a screening model in which the agent has one of only two possible types, but his (quasi-linear) utility from the various alternatives is otherwise unrestricted. In particular, we do not assume that the alternatives or the types are ordered in a particular way, so neither type is necessarily "high" or "low." Our main results provide a complete, geometric characterization of the optimal menus.

The key to the characterization is our notion of an uncontested type. A type is uncontested if his valuation for his efficient alternative weakly exceeds the other type's valuation for this alternative. Otherwise, the type is contested. We show that at least one of the types is uncontested. So, if the other type is contested, an optimal menu is pinned down by the contested type's alternative. Unlike in the standard settings with increasing differences, where the only possible distortion in the low type's allocation is a "downward" distortion, in our setting there may be many possible directions for the distortion in the contested type's allocation, and our characterization identifies the optimal distortion.

We illustrate the potential usefulness of our results with two applications. The first application combines vertical and horizontal product differentiation. Each type and product is represented by a size and a horizontal location, and the value of a type for a product is the dot product of the corresponding vectors. The second application is bundling multiple products. Each type has a valuation for each product, and a type's valuation for a bundle is the sum of the type's valuations for the products in the bundle.

The full version of the paper can be accessed here: https://nimahaghpanah.com/pdfs/twotypes.pdf

Motivated by stochastic optimization, we introduce the problem of learning from samples of contextual value distributions. A contextual value distribution can be understood as a family of real-valued distributions, where each sample consists of a context x and a random variable drawn from the corresponding real-valued distribution D_x. By minimizing a convex surrogate loss, we learn an empirical distribution D'_x for each context, ensuring a small Levy distance to D_x.

We apply this result to obtain the sample complexity bounds for the learning of an ϵ-optimal policy for stochastic optimization problems defined on an unknown contextual value distribution. The sample complexity is shown to be polynomial for the general case of strongly monotone and stable optimization problems, including Single-item Revenue Maximization, Pandora's Box and Optimal Stopping.

A full version can be found at https://arxiv.org/abs/2505.16829.

We consider a revenue-optimizing auctioneer in single-dimensional environments with matroid feasibility constraints. Akbarpour and Li [2020] argue that any revenue-optimal, truthful, and credible mechanism requires unbounded communication. Recent works [Chitra et al., 2023, Essaidi et al., 2022, Ferreira and Weinberg, 2020] circumvent their impossibility for single-items setting through the use of cryptographic commitments and blockchains. We extend their results to matroid feasibility constraints.

At a high level, the two-round Deferred-Revelation Auction (DRA) discussed by Ferreira and Weinberg [2020] and Chitra et al. [2023] requires each bidder to submit a deposit, which is slashed upon presenting verifiable evidence indicating a deviation from the behaviour prescribed by the mechanism. We prove that the DRA satisfies truthfulness, credibility and revenue-optimality for all matroid environments when bidders' values are drawn from α-strongly regular distributions for α > 0. Further, we argue that the DRA is not credible for any feasibility constraint beyond matroids and for any smaller deposits than suggested by previous literature even in single-item environments.

Finally, we modify the Ascending Deferred-Revelation Auction (ADRA) for single-item settings proposed by Essaidi et al. [2022] for arbitrary bidder value distributions. We implement a Deferred-Revelation variant of the deferred-acceptance auction for matroids due to Bikhchandani et al. [2011], which requires the same bounded communication as the ADRA.

This paper addresses the disconnect between classical full implementation theory - which assumes sophisticated agent capable of achieving Nash equilibrium - and the reality of boundedly rational agents who often rely on simple heuristics in decision-making. Drawing on learning theory that demonstrates how elementary adaptive procedures steer behavior toward equilibrium, we investigate the implementation in correlated equilibria (CE).

We make two primary contributions. Theoretically, for a finite environment involving finite type spaces and bounded utilities, we construct a novel finite mechanism which implements any Maskin Monotonic social choice functions or correspondences in CE. The mechanism's finiteness is critical for the feasibility of machine experiments (simulations) as well as the direct application of results from the learning literature. This requires that we avoid the "integer" or "modulo" game constructions which are commonly seen in the implementation literature and rely on stochastic outcomes and off-the-equilibrium transfers instead.

Maskin Monotonicity yields that there is an agent who has a preference reversal (across a lie and the true state) between an SCF outcome for the true state and a preselected test allocation. This agent can challenge a lie by "asking for" the test allocation, which yields a credible challenge to a lie. Lies which other agents can challenge are handled by using a large penalty (τ¹) which makes it prohibitively costly for agents to present such lies if others challenge it. The more subtle issue of self-challenges is difficult to deter since other agents may not "see" this self-challenge conditional on each of their messages owing to possible correlations in the message distribution. This makes it difficult for the designer to penalize the self-challenger using cross-checks. The mechanism deals with this issue by (i) using a small penalty (τ²) which incentivizes others (j ≠ i) to "join" a self-challenger (say i) in challenging herself while disincentivizing agent(s) j from challenging agent i when there is indeed no self-challenge from i; and (ii) invoking a large penalty (τ³) on the self-challenger (i) if their lie is inconsistent with the (now-truthful) reports from all other (j ≠ i) participants. This detects and penalizes any self-challengeable lie, rendering misreporting unprofitable and the equilibrium outcome(s) socially desirable.

Practically, we substantiate the mechanism's efficacy through simulations in a bilateral trade setting, wherein agents' play under regret-matching dynamics due to Hart and Mas-Colell (2000). Simulations based on our mechanism demonstrate rapid convergence to the socially desirable outcome. Comparative analyses further demonstrate that, under the regret-matching dynamics, the proposed mechanism outperforms existing mechanisms for Nash implementation or virtual implementation, in terms of convergence speed, realized social surplus, and the required off-the-equilibrium transfers.

The full version of the paper is available at http://arxiv.org/abs/2506.03528

We use contention resolution schemes (CRS) to derive algorithms for the fair rationing of a single resource when agents have stochastic demands. We aim to provide ex-ante guarantees on the level of service provided to each agent, who may measure service in different ways (Type-I, II, or III), calling for CRS under different feasibility constraints (rank-1 matroid or knapsack). We are particularly interested in two-order CRS where the agents are equally likely to arrive in a known forward order or its reverse, which is motivated by online rationing at food banks. Indeed, for a mobile pantry driving along cities to ration food, it is equally efficient to drive that route in reverse on half of the days, and we show that doing so significantly improves the service guarantees that are possible, being more "fair" to the cities at the back of the route.

In particular, we derive a two-order CRS for rank-1 matroids with guarantee 1/(1 + e^-1/2) ≈ 0.622, which we prove is tight. This improves upon the 1/2 guarantee that is best-possible under a single order (Alaei, SIAM J. Comput. 2014), while achieving separation with the 1 - 1/e ≈ 0.632 guarantee that is possible for random-order CRS (Lee and Singla, ESA 2018).. Because CRS guarantees imply prophet inequalities, this also beats the two-order prophet inequality with ratio [EQUATION] from (Arsenis, SODA 2021), which was tight for single-threshold policies. Rank-1 matroids suffice to provide guarantees under Type-II or III service, but Type-I service requires knapsack. Accordingly, we derive a two-order CRS for knapsack with guarantee 1/3, improving upon the 1/(3 + e^-2) ≈ 0.319 guarantee that is best-possible under a single order (Jiang et al., SODA 2022). To our knowledge, 1/3 provides the best-known guarantee for knapsack CRS even in the offline setting. Finally, we provide an upper bound of 1/(2 + e^-1) ≈ 0.422 for two-order knapsack CRS, strictly smaller than the upper bound of (1 - e^-2)/2 ≈ 0.432 for random-order knapsack CRS.

We study revenue maximization in multi-dimensional auctions with n bidders and m items. When the bidders are constant-demand and either the number of bidders or the number of items is a constant, we give a quasi-polynomial time algorithm that computes an ε-Bayesian Incentive Compatible (ε-BIC) mechanism that obtains at least a (1 - ε) faction of the expected revenue of the optimal Bayesian Incentive Compatible (BIC) mechanism. We obtain this guarantee even when the value distribution of each bidder is unbounded, extending the main result of [Kothari et al., 2019] from a single bidder to multiple bidders.

If people find it costly to evaluate the options available to them, their choices may not directly reveal their preferences. Yet, it is conceivable that a researcher can still learn about a population's preferences with careful experiment design. We formalize the researcher's problem in a model of robust mechanism design where it is costly for individuals to learn about how much they value a product. We characterize the statistics that the researcher can identify, and find that they are quite restricted. Finally, we apply our positive results to social choice and propose a way to combat uninformed voting. Link to paper: https://arxiv.org/abs/2505.19570

Kidney Exchange Programs (KEPs) facilitate the exchange of kidneys, and larger pools of recipient-donor pairs tend to yield proportionally more transplants, leading to the proposal of international KEPs (IKEPs). However, as studied by Mincu et al. [2021], practical limitations must be considered in IKEPs to ensure that countries remain willing to participate. Thus, we study IKEPs with country-specific parameters, represented by a tuple Γ, restricting the selected transplants to be feasible for the countries to conduct, e.g., imposing an upper limit on the number of consecutive exchanges within a country's borders. We provide a complete complexity dichotomy for the problem of finding a feasible (according to the constraints given by Γ) cycle packing with the maximum number of transplants, for every possible Γ. We also study the potential for countries to misreport their parameters to increase their allocation. As manipulation can harm the total number of transplants, we propose a novel individually rational and incentive compatible mechanism M_order. We first give a theoretical approximation ratio for M_order in terms of the number of transplants, and show that the approximation ratio of M_order is asymptotically optimal. We then use simulations which suggest that, in practice, the performance of M_order is significantly better than this worst-case ratio.

The classic notion of truthfulness requires that no agent has a profitable manipulation — an untruthful report that, for some combination of reports of the other agents, increases her utility. This strong notion implicitly assumes that the manipulating agent either knows what all other agents are going to report, or is willing to take the risk and act as-if she knows their reports.

Without knowledge of the others' reports, most manipulations are risky - they might decrease the manipulator's utility for some other combinations of reports by the other agents. Accordingly, a recent paper (Bu, Song and Tao, "On the existence of truthful fair cake cutting mechanisms", Artificial Intelligence 319 (2023), 103904) suggests a relaxed notion, which we refer to as risk-avoiding truthfulness (RAT), which requires only that no agent can gain from a safe manipulation — one that is sometimes beneficial and never harmful.

Truthfulness and RAT are two extremes: the former considers manipulators with complete knowledge of others, whereas the latter considers manipulators with no knowledge at all. In reality, agents often know about some — but not all — of the other agents. This paper introduces the RAT-degree of a mechanism, defined as the smallest number of agents whose reports, if known, may allow another agent to safely manipulate, or n if there is no such number. This notion interpolates between classic truthfulness (degree n) and RAT (degree at least 1): a mechanism with a higher RAT-degree is harder to manipulate safely.

To illustrate the generality and applicability of this concept, we analyze the RAT-degree of prominent mechanisms across various social choice settings, including auctions, indivisible goods allocations, cake-cutting, voting, and two-sided matching.

Extended Version:¹ https://arxiv.org/abs/2502.18805

We study an online forecasting setting in which, over T rounds, N strategic experts each report a forecast to a mechanism, the mechanism selects one forecast, and then the outcome is revealed. In any given round, each expert has a belief about the outcome, but the expert wishes to select its report so as to maximize the total number of times it is selected. The goal of the mechanism is to obtain low belief regret: the difference between its cumulative loss (based on its selected forecasts) and the cumulative loss of the best expert in hindsight (as measured by the experts' beliefs). We consider exactly truthful mechanisms for non-myopic experts, meaning that truthfully reporting its belief strictly maximizes the expert's subjective probability of being selected in any future round. Even in the full-information setting, it is an open problem to obtain the first no-regret exactly truthful mechanism in this setting. We develop the first no-regret mechanism for this setting via an online extension of the Independent-Event Lotteries Forecasting Competition Mechanism (I-ELF). By viewing this online I-ELF as a novel instance of Follow the Perturbed Leader (FPL) with noise based on random walks with loss-dependent perturbations, we obtain [EQUATION] regret. Our results are fueled by new tail bounds for Poisson binomial random variables that we develop. We extend our results to the bandit setting, where we give an exactly truthful mechanism obtaining Õ(T^2/3N^1/3) regret; this is the first no-regret result even among approximately truthful mechanisms.

A full version of this paper can be found at https://arxiv.org/abs/2502.11483.

This paper introduces the concept of leakage-robust Bayesian persuasion. Situated between public Bayesian persuasion and private Bayesian persuasion, leakage-robust persuasion considers a setting where one or more signals privately communicated by a sender to the receivers may be leaked. We study the design of leakage-robust Bayesian persuasion schemes and quantify the price of robustness using two formalisms:

- The first notion, k-worst-case persuasiveness, requires a signaling scheme to remain persuasive as long as each receiver observes no more than k leaked signals from other receivers. We quantify the Price of Robust Persuasiveness (PoRP_k)— i.e., the gap in sender's utility as compared to the optimal private persuasion scheme—as Θ(min{2^k,n}) for supermodular sender utilities and Θ(k) for submodular or XOS sender utilities, where n is the number of receivers. This result also establishes that in some instances, Θ(log k) leakages are sufficient for the utility of the optimal leakage-robust persuasion to degenerate to that of public persuasion.

- The second notion, expected downstream utility robustness, relaxes the persuasiveness requirement and instead considers the impact on sender's utility resulting from receivers best responding to their observations. By quantifying the Price of Robust Downstream Utility (PoRU) as the gap between the sender's expected utility over the randomness in the leakage pattern as compared to private persuasion, our results show that, over several natural and structured distributions of leakage patterns, PoRU improves PoRP to Θ(k) or even Θ(1), where k is the maximum number of leaked signals observable to each receiver across leakage patterns in the distribution.

En route to these results, we show that subsampling and masking serve as general-purpose algorithmic paradigms for transforming any private persuasion signaling scheme to one that is leakage-robust, with minmax optimal loss in sender's utility.

A full version of this paper can be found at https://arxiv.org/abs/2411.16624.

Path independence is arguably one of the most important choice rule properties in economic theory. We show that a choice rule is path independent if and only if it is rationalizable by a utility function satisfying ordinal concavity, a concept closely related to concavity notions in discrete mathematics. We also provide a rationalization result for choice rules that satisfy path independence and the law of aggregate demand. A full version is available at https://arxiv.org/abs/2303.00892.

Many microeconomic models involve optimizing a piecewise linear function, such as in contract design, posted-price auctions, and first-price auctions. When key parameters are unknown and stochastic, the task becomes learning to optimize an unknown piecewise linear reward function. This is typically cast as an online learning problem, where the goal is to minimize regret relative to the best fixed decision in hindsight.

This paper introduces a general online learning framework that offers a unified approach to tackle regret minimization for piecewise linear rewards, under a suitable monotonicity assumption. We design a learning algorithm that attains a regret of [EQUATION], where n is the number of "pieces" of the reward function and T is the number of rounds. This result is tight when n is small relative to T, specifically when n ≤ T^1/3. Our algorithm solves two open problems in the literature on learning in microeconomic settings. First, it shows that the state-of-the-art Õ(T^2/3) regret bound for learning optimal linear contracts is not tight when the number of agent actions is small relative to T. Second, our algorithm demonstrates that in the problem of learning to set prices in posted-price auctions, it is possible to attain optimal instance-independent regret bounds.

A full version of this paper can be found at https://arxiv.org/abs/2503.01701

We consider a package assignment problem with money, in which a finite set M of objects is allocated to agents. Each agent receives a package of objects and makes a payment, and has preferences over pairs consisting of a package and a payment. These preferences are not necessarily quasi-linear. The admissible set of object allocations is chosen by the planner to pursue specific objectives in conjunction with the rule. A rule satisfies constrained efficiency if no allocation—whose object allocation is admissible under the rule—Pareto dominates the allocation selected by the rule. We study the compatibility between constraints on admissible object allocations and desirable properties of rules, and characterize the rules that satisfy both. Our first main result shows that: If a rule satisfies constrained efficiency, no wastage, equal treatment of equals, strategy-proofness, individual rationality, and no subsidy, then the set of admissible object allocations under the rule must be bundling unit-demand for some partition of M, and must satisfy no wastage and anonymity. Second, building on the results of [Demange and Gale, 1985], [Morimoto and Serizawa, 2015], and [Wakabayashi et al., 2025], we show that: A rule satisfies constrained efficiency, no wastage, equal treatment of equals, strategy-proofness, individual rationality, and no subsidy if and only if its admissible set of object allocations is bundling unit-demand for some partition of M, satisfies no wastage and anonymity, and the rule is a bundling minimum price Walrasian rule.

The full paper is available at:

https://drive.google.com/file/d/1Ck3Neq7KKBUGvh0ZUvARYrO66ykkzlhj/view?usp=sharing

I study the problem of a government providing benefits to agents who differ in wealth and need for the benefit, and whose types are private information. The government faces an equity constraint requiring that equally deserving agents receive equal benefits. The deservingness of different types of agents is modeled using a merit function, which increases with need for the benefit and decreases with wealth.

I consider mechanisms for allocating benefits that screen agents with two instruments: payments, which are less costly to the rich, and wait times, which are less costly to the poor. I show that while the government cannot equitably screen with a single instrument (payments or wait times), combining both of these instruments, which on their own favor different groups, allows it to screen while still producing an equitable allocation. Indeed, combining wait times and payments lets the government implement any allocation rule that is increasing in agents' merit.

Intuitively, screening with only payments violates equity because, among agents with the same need, the richer ones are more willing to pay for the benefit. The allocation would thus be "biased toward the rich," which is the opposite of what the merit function requires. The reason why screening with payments alone (generically) fails the equity constraint is more subtle. Screening with wait times differs from screening with payments in that the allocation it produces is biased toward the poor, which is the direction of bias that the merit function requires. However, the equity constraint also requires the allocation to be constant along iso-merit curves, and with only one screening device, the government will have too few degrees of freedom to pool agents in this way. This problem can be resolved, however, by using fees and wait times together. Every level of the benefit can then be offered with a menu of payment options composed of different fee and wait time pairs. The government can fine-tune these payment menus to achieve the precise bias in allocation that equity requires.

I then extend my notion of equity by developing a measure of equity violation, capturing how far a particular allocation is from satisfying the equity constraint. I ask which of the two screening instruments, when used on its own, produces larger equity violations. A naïve intuition suggests that screening with wait times biases the allocation in the right direction and thus violates equity less. However, a mechanism screening with wait times will generically fail to pool together agents in a way that matches the shape of the iso-merit curve. As it turns out, in some cases this "shape effect" dominates the "direction effect," leading to screening with only payments being more equitable than screening with only wait times. Screening with only wait times will nevertheless produce smaller equity violations when the merit function depends on wealth sufficiently strongly.

The full paper is available at https://arxiv.org/abs/2402.08781.

We study a many-to-one assignment problem, where a set of applicants need to be assigned to a set of schools with limited seats. We formulate distributional objectives by a set of standard axioms. Axiom 1 has two parts. First, the number of applicants of each type at each school should be less than the corresponding quota. Second, whenever the number of applicants of a given type assigned to a school is less than the corresponding reserve, then it should be that no other applicant of that type prefers the school to their own assignment. Axiom 2 requires that whenever a school has available seats, it should be that there is no applicant that prefers that school to their own assignment. Finally, we say that an applicant a violates the priority of another applicant b at school s, if b prefers s to their own assignment, and b has a higher priority at that school than a. In this case, the triplet (a, b, s) is called a priority violation instance. Axiom 3 requires that there are no priority violation instances including two applicants of the same type.

We restrict attention to assignments that satisfy Axioms 1–3. Within this class, we want to minimize priority violations. We adopt a set-inclusion notion of comparing the priority violations across the assignment. Namely, we say that an assignment μ priority violations dominates another assignment μ′, if the set of priority violation instances of μ is a proper subset of the set of priority violation instances of μ′. We say that μ is priority violations minimal in a class of assignments, if μ belongs to the class, and no assignment in the class priority violations dominates μ.

We show that the assignment produced by the celebrated deferred acceptance algorithm coupled with a particular reserves- and quotas-based choice rule, called the regular rule, is constrained optimal in the following sense: the assignment is either priority violations minimal in the class of assignment satisfying Axioms 1–3, or it Pareto dominates any other assignment in this class that priority violations dominates it. In other word, given the outcome of the algorithm, it is impossible to further reduce priority violation instances, without creating new ones, or unambiguously reducing welfare for applicants. We show that the algorithm is the unique one with this property, that also satisfies strategy-proofness and monotonicity axioms. Thus, our paper provides a one of a kind theoretical justification for both deferred acceptance and the reserves and quotas-based choice rules in allocation problems with distributional objectives.

For other natural objectives, such as minimizing the number of priority violation instances, we find that there are no polynomial time algorithms (unless P=NP), or a strategy-proof algorithms, that are constrained optimal.

A full version of this paper can be found at https://papers.ssrn.com/sol3/papers.cfm?abstract_id=5284396

This paper introduces a novel framework for modeling diversity using the theory of majorization and applies it to school choice problems. We consider a school with limited capacity that must select students from an applicant pool, where each student is classified into types (e.g., by race, gender, or socioeconomic status). Within this setting, we ask: How should we compare the diversity of student groups? And what admissions procedure balance the school's goal of admitting students with the highest priority (e.g., academic merit, proximity to the school) and achieving a diverse student body?

We formalize a notion of diversity by comparing how concentrated student type distributions are, using majorization to capture the idea that "less concentrated" means "more diverse." Specifically, a student body A is more diverse than another equally-sized body B if A's type distribution is majorized by B's type distribution. However, such a notion of diversity based on standard majorization implicitly assumes that the uniform distribution is the ideal benchmark for diversity, which can be overly restrictive when the school wishes to match the composition of its student body to the population distribution in the relevant geographical community. To address this, we extend majorization theory to allow any target distribution as the benchmark, yielding a more flexible notion of diversity, which we term b-targeting diversity.

We next turn to admissions procedures and make three main contributions. First, we propose three axioms for school choice rules: Nonwastefulness, Promotion of b-targeting diversity and b-targeting Schur-revealed preference. We prove that these axioms uniquely characterize the b-targeting Schur choice rule, which admits students greedily based on priority while respecting diversity constraints. Second, we show that the b-targeting Schur choice rule is optimal in the sense that any alternative rule either admits fewer students, a less diverse student body, or a student body with lower priority. Third, we establish that the b-targeting Schur choice rule is equivalent to a greedy algorithm that maximizes priority subject to a majorization constraint. This connection reveals a matroid structure underlying the problem, linking our work to combinatorial optimization.

The full paper can be found at: https://arxiv.org/abs/2407.17589

The COVID-19 pandemic underscored the urgent need for fair and effective allocation of scarce resources, from hospital beds to vaccine distribution. In this paper, we study a healthcare rationing problem where identical units of a resource are divided into different categories, and agents are assigned based on priority rankings. We first introduce a simple and efficient algorithm that satisfies four fundamental axioms critical to practical applications: eligible compliance, non-wastefulness, respect for priorities, and maximum cardinality. This new algorithm is not only conceptually simpler but also computationally faster than the Reverse Rejecting rules proposed in recent work. We then extend our analysis to a more general sequential setting, where categories can be processed both sequentially and simultaneously. For this broader framework, we introduce a novel algorithm that preserves the four fundamental axioms while achieving additional desirable properties that existing rules fail to satisfy. Furthermore, we prove that when a strict precedence order over categories is imposed, this rule is the unique mechanism that satisfies these properties.

We consider online procurement auctions, where the agents arrive sequentially, in random order, and have private costs for their services. The buyer aims to maximize a monotone submodular value function for the subset of agents whose services are procured, subject to a budget constraint on their payments. We consider a posted-price setting where upon each agent's arrival, the buyer decides on a payment offered to them. The agent accepts or rejects the offer, depending on whether the payment exceeds their cost, without revealing any other information about their private costs whatsoever. We present a randomized online posted-price mechanism with constant competitive ratio, thus resolving the main open question of (Badanidiyuru, Kleinberg and Singer, EC 2012). Posted-price mechanisms for online procurement typically operate by learning an estimation of the optimal value, denoted as OPT, and using it to determine the payments offered to the agents. The main challenge is to learn OPT within a constant factor from the agents' accept / reject responses to the payments offered. Our approach is based on an online test of whether our estimation is too low compared against OPT and a carefully designed adaptive search that gradually refines our estimation.

Understanding the formation of opinions on multiple interconnected topics within social networks is of significant importance. It offers insights into collective behavior and decision-making processes, with applications in Graph Neural Networks. Existing models propose that individuals form opinions based on a weighted average of their peers' opinions and potentially their own beliefs. This averaging process, when viewed as a best-response game, can be seen as an individual minimizing disagreements with peers, defined by a quadratic penalty, leading to an equilibrium. Bindel, Kleinberg, and Oren (FOCS 2011) provided tight bounds on the "price of anarchy," which is defined as the maximum level of overall disagreement at equilibrium relative to a social optimum. Bhawalkar, Gollapudi, and Munagala (STOC 2013) generalized the penalty function to consider non-quadratic penalties and provided tight bounds on the price of anarchy of these functions.

When considering multiple topics, an individual's opinions can be represented as a vector. Parsegov, Proskurnikov, Tempo, and Friedkin (2016) proposed a multidimensional model using the weighted averaging process, but with constant interdependencies between topics for any individual. However, the same question of the price of anarchy for this model remained open. We address this question by providing tight bounds on the price of anarchy of the multidimensional model, while also generalizing the model to consider more complex interdependencies. Furthermore, through novel approaches, following the work of Bhawalkar, Gollapudi, and Munagala, we provide tight bounds on the price of anarchy under non-quadratic penalty functions. Surprisingly, these bounds match the bounds for the scalar model used by them. We further demonstrate that the bounds for the price of anarchy remain unchanged even when we add another layer of complexity to the dynamics, involving multiple individuals working in groups to minimize their overall internal and external disagreement penalty, a common occurrence in real-life scenarios. Lastly, we provide a novel lower bound showing that for any reasonable penalty function, the worst-case price of anarchy across all networks is at least 2/(e ln 2). This lower bound naturally applies to both the multidimensional and scalar models and was previously unknown even for scalar models.

Φ-equilibria—and the associated notion of Φ-regret—are a powerful and flexible framework at the heart of online learning and game theory, whereby enriching the set of deviations Φ begets stronger notions of rationality. Recently, Daskalakis, Farina, Fishelson, Pipis, and Schneider (STOC '24) settled the existence of efficient algorithms when Φ contains only linear maps under a general, d-dimensional convex constraint set X. In this paper, we significantly extend their work by resolving the case where Φ is k-dimensional; degree-ℓ polynomials constitute a canonical such example with k = d^O(ℓ). In particular, we obtain two main positive results: i) a poly(n, d, k, log(1/ϵ))-time algorithm for computing ϵ-approximate Φ-equilibria in n-player multilinear games, and ii) an efficient online algorithm that incurs average Φ-regret at most ϵ using poly(d, k)/ϵ² rounds.

We also show nearly matching—up to constant factors in the exponents—lower bounds parameterized by k in the online learning setting. We thus obtain for the first time a family of deviations that captures the learnability of Φ-regret. At the heart of our approach is a polynomial-time algorithm for computing an expected fixed point of any ϕ : X → X—that is, a distribution μ ∈ Δ(X) such that E_x~μ[ϕ(x) - x] ≈ 0—based on the seminal ellipsoid against hope (EAH) algorithm of Papadimitriou and Roughgarden (JACM '08). In particular our algorithm for computing Φ-equilibria is based on executing EAH in a nested fashion—each step of EAH itself being implemented by invoking a separate EAH call.

The full version of the paper is available at arxiv.org/pdf/2502.18582.

Beliefs about the performance of new technologies strongly condition their usage. Among new technologies, artificial intelligence (AI)—and in particular LLMs—stand out because they can be used for extremely diverse sets of tasks. This versatility, however, complicates the problem of learning about AI capabilities, especially since the technological frontier created by AI is often "jagged": among seemingly similar tasks, AI can vastly out-perform humans on some, yet under-perform on others. Inaccurate perceptions of performance could lead to productivity losses, if AI is used for tasks on which it performs poorly.

We study how people learn about the performance of AI and how this affects their usage decisions. Our hypothesis is that people project human-relevant task features when assessing the performance of AI, as they generalize from observed instances to its performance on all tasks within a domain. We model a principal who observes binary performance of an agent on a task with a known level of difficulty, and updates over the agent's ability—informing performance over all tasks. We call Human Projection the perception of AI-difficulty being (partly) determined by human-difficulty. The principal's beliefs in the agent's performance decrease more after observing a failure on a human-easier task, and increase more after a success on a human-harder task. Intuitively, "easy failures" and "hard successes" are seen as more diagnostic of a low and high ability level, respectively. Yet, such beliefs are inaccurate in contexts where human- and AI-difficulty differ.

We document such misperceptions of performance in mathematics. We assemble a new benchmark of more than 400 standardized math problems, and elicit incentivized beliefs in performance in a lab experiment. Here, even though ChatGPT 3.5's performance is uncorrelated with the tasks' human-difficulty, elicited beliefs confirm our model's predictions and are consistent with the projection of human difficulty onto AI. Projection leads to over-reactions to AI's failures on human-easy tasks and to its successes on human-difficult tasks.

We find evidence for projection of another feature—an answer's reasonableness—in a field experiment with an AI giving parenting advice. Potential users strongly infer from answers that are equally uninformative but deemed less reasonable, understood as less similar to the expected (useful) answer. Conditional on usefulness, lower reasonableness significantly reduces trust and continued engagement with AI (measured over a three-week period). Unreasonable AI answers are seen as a sign of overall incompetence, even though a large majority of AI answers were separately rated by potential users as highly useful.

Finally, we embed our framework into an adoption model with endogenous signals of AI performance. We show that projection leads to an "all-or-nothing" adoption in Berk-Nash equilibrium, where AI gets adopted either for easy and hard tasks alike, or not at all. To vary projection, we manipulate AI's human-likeness in a lab experiment and find it increases the share of suboptimal over-adoption of AI. Results suggest AI "anthropomorphism" can backfire by de-aligning users' expectations and AI performance.

The full version of this paper is available at: https://tinyurl.com/yc6czxan

Political polarization is a significant issue in American politics, influencing public discourse, policy, and consumer behavior. While studies on polarization in news media have extensively focused on verbal content, non-verbal elements, particularly visual content, have received less attention due to the complexity and high dimensionality of image data. Traditional descriptive approaches often rely on feature extraction from images, leading to biased polarization estimates due to information loss.

In this paper, we introduce the Polarization Measurement using Counterfactual Image Generation (PMCIG) algorithm, which combines the economic structure of the problem with generative models to generate comparable counterfactual images and measure polarization in visual content. The key advantage of our framework in comparison to the traditional regression-based approaches lies in its ability to overcome the potential confounding and mis-estimation of polarization due to information loss from feature extraction.

Applying this framework to a decade-long dataset featuring 30 prominent politicians across 20 major news outlets, we identify significant polarization in visual content, with notable variations across outlets and politicians. At the news outlet level, we develop a measure called Conservative Visual Slant (CVS) that measures each outlet's preference for a positive portrayal of a Republican politician relative to a Democratic politician. We find that outlets such as Daily Mail, Fox News, and Newsmax tend to portray Republican politicians more favorably in their visual content, while The Washington Post, USA Today, and The New York Times exhibit a slant in favor of Democratic politicians. At the politician level, we develop a politician-specific measure called Overall Visual Polarization (OVP), which measures the overall dispersion in a politician's portrayal across outlets. Our results reveal substantial variation in OVP, with Donald Trump and Barack Obama among the most polarizing figures, while Joe Manchin and Susan Collins are among the least.

Finally, we conduct a series of validation tests demonstrating the consistency of our proposed measures with external measures of media slant that rely on non-image-based sources. In particular, we find that our outlet-specific CVS measure is highly correlated with external measures of media slant that rely on verbal content and references. Moreover, we find that our politician-specific OVP measure is correlated with the ideological alignment of a politician's constituency and that politicians from swing states tend to exhibit lower levels of polarization.

A full version of this paper can be found https://dx.doi.org/10.2139/ssrn.5175092.

We study two axioms for social choice functions that capture the impact of similar candidates: independence of clones (IoC) and composition consistency (CC). We clarify the relationship between these axioms by observing that CC is strictly more demanding than IoC, and investigate whether common voting rules that are known to be independent of clones (such as Single Transferable Vote, Ranked Pairs, Schulze Method, and Split Cycle) are composition-consistent. While for most of these rules the answer is negative, we identify a variant of Ranked Pairs that satisfies CC. Further, we show how to efficiently modify any (neutral) social choice function so that it satisfies CC, while maintaining its other desirable properties. Our transformation relies on the hierarchical representation of clone structures via PQ-trees. We extend our analysis to social preference functions. Finally, we interpret IoC and CC as measures of robustness against strategic manipulation by candidates, with IoC corresponding to strategy-proofness and CC corresponding to obvious strategy-proofness.

The full version of this paper is available at https://arxiv.org/abs/2502.16973.

Forecast aggregation combines the predictions of multiple forecasters to improve accuracy. However, the lack of knowledge about forecasters' information structure hinders optimal aggregation. Given a family of information structures, robust forecast aggregation aims to find the aggregator with minimal worst-case regret compared to the omniscient aggregator. Previous approaches for robust forecast aggregation rely on heuristic observations and parameter tuning. We propose an algorithmic framework for robust forecast aggregation. Our framework provides efficient approximation schemes for general information aggregation with a finite family of possible information structures. In the setting considered by Arieli et al. [2018] where two agents receive independent signals conditioned on a binary state, our framework also provides efficient approximation schemes by imposing Lipschitz conditions on the aggregator or discrete conditions on agents' reports. Numerical experiments demonstrate the effectiveness of our method by providing a nearly optimal aggregator in the setting considered by Arieli et al. [2018].

Stability has been a foundational concept in the two-sided matching literature. For fractional matchings under strict preferences, it is commonly formalized as ex ante stability. When agents on one side have weak preferences involving indifferences, the seminal work of Kesten and Ünver [Theoretical Economics, 2015] introduces strong ex ante stability, which combines ex ante stability with a fairness criterion that ensures no discrimination among (equally-preferred) agents on one side. They propose the Fractional Deferred Acceptance (FDA) algorithm, which is guaranteed to converge to a strongly ex ante stable (fractional) matching, but may require infinitely many iterations to do so. To address this, they propose another algorithm, which we call FDA-Cycle, that computes the matching to which FDA converges; they further claim that FDA-Cycle terminates in polynomial time.

Our first contribution is to show that this claim is incorrect: we provide a counterexample on which FDA-Cycle gets trapped in an infinite loop, similar to the ones which prevent the FDA algorithm from terminating. This reopens the question of polynomial-time computability of a strongly ex ante stable matching.

Our second contribution is to generalize the FDA algorithm to be able to handle indifferences in the preferences of agents on both sides of the market. We introduce the Doubly-Fractional Deferred Acceptance (DFDA) algorithm, and the notion of doubly-strong ex ante stability, a strengthening of strong ex ante stability which guarantees fairness for equally-preferred agents on either side of the market. Just as the FDA algorithm converges to a strongly ex ante stable matching, we show that the DFDA algorithm converges to a doubly-strong ex ante stable matching. However, like FDA, DFDA may fail to terminate in finite time.

Our final and most significant contribution is to develop a new algorithm, which we call Doubly-Fractionally Deferred Acceptance via Strongly Connected Components (DFDA-SCC), which loosely mimics the iterations of DFDA. Using novel algorithmic insights, we prove that DFDA-SCC computes a doubly-strong ex ante stable matching while terminating in polynomial time, thus positively resolving the open question stated above.

A full version of this paper can be found at https://www.cs.toronto.edu/~nisarg/papers/dfda.pdf.

We study approval-based committee voting from a novel perspective. While extant work largely centers around proportional representation of the voters, we shift our focus to the candidates while preserving proportionality. Intuitively, candidates supported by similar voter groups should receive comparable representation. Since deterministic voting rules cannot achieve this ideal, we develop randomized voting rules that satisfy ex-ante neutrality, monotonicity, and continuity, while maintaining strong ex-post proportionality guarantees.

Continuity of the candidate selection probabilities proves to be the most demanding of our ex-ante desiderata. We provide it via voting rules that are algorithmically stable, a stronger notion of robustness which captures the continuity of the committee distribution under small changes. First, we introduce Softmax-GJCR, a randomized variant of the Greedy Justified Candidate Rule (GJCR) [Brill and Peters, 2023], which carefully leverages slack in GJCR to satisfy our ex-ante properties. This polynomial-time algorithm satisfies EJR+ ex post, assures ex-ante monotonicity and neutrality, and provides O(k³/n)-stability (ignoring log factors). Building on our techniques for Softmax-GJCR, we further show that stronger stability guarantees can be attained by (i) allowing exponential running time, (ii) relaxing EJR+ to an approximate α-EJR+, and (iii) relaxing EJR+ to JR.

We finally demonstrate the utility of stable voting rules in other settings. In online dynamic committee voting, we show that stable voting rules imply dynamic voting rules with low expected recourse, and illustrate this reduction for Softmax-GJCR. Our voting rules also satisfy a stronger form of stability that coincides with differential privacy, suggesting their applicability in privacy-sensitive domains.

Sequential decision-making by a large set of myopic agents has gained significant attention over the past decade. In such settings, even a small amount of experimentation by a few agents would benefit all others but obtaining such experimentation could be challenging for a central planner. The academic literature has focused on mechanisms for promoting experimentation through monetary incentives and persuasion through careful information disclosure. In this paper, we study a simple control that the central planner can use to coordinate experimentation. We consider a set of myopic agents that observe their own histories but not the histories of other agents. In a continuous-time stochastic multi-armed bandit model, the agents pick arms myopically and receive instantaneous rewards. Meanwhile, the central planner can observe the history of all agents. We consider a class of policies where the central planner is allowed to irrevocably remove arms. We show that an appropriately chosen policy within this class can generate the needed experimentation and match the regret bounds for a centralized problem, thus mitigating the cost of decentralization. We also quantify the minimum number of agents that are needed for such a policy to be asymptotically optimal and the impact of the number of agents on the speed of learning.

The paper is available at https://papers.ssrn.com/sol3/papers.cfm?abstract_id=5266599.

When an experimenter has the option of running an adaptive trial, is it admissible to ignore this option and run a non-adaptive trial instead? We provide a negative answer to this question in the best-arm identification problem, where the experimenter aims to allocate measurement efforts judiciously to confidently deploy the most effective treatment arm. We find that, whenever there are at least three treatment arms, there exist simple adaptive designs that universally and strictly dominate non-adaptive completely randomized trials. This dominance is characterized by a notion called efficiency exponent, which quantifies a design's statistical efficiency when the experimental sample is large. Our analysis focuses on the class of batched arm elimination designs, which progressively eliminate underperforming arms at pre-specified batch intervals. We characterize simple sufficient conditions under which these designs universally and strictly dominate completely randomized trials. These results resolve the second open problem posed in Qin [2022]. The full version of this paper is available at https://arxiv.org/pdf/2506.05329.

The rise of big data technologies, allowing firms to collect detailed consumer data to estimate their willingness to pay, has reignited the longstanding debate on the welfare implications of price discrimination. A significant difficulty in regulating data collection practices is that it is close to impossible to perfectly monitor and control how firms use consumer data, which makes highly targeted regulation impractical. Often the relevant question is if data collection should be permitted, without knowing how much information the firm already has nor how much additional information it might be able to collect.

To answer this question, we develop a model to study endogenous market segmentation by a monopolist subject to residual uncertainty. There is a given set of consumer types each represented by a downward-sloping demand curve specifying the distribution of consumers' valuations of that type. The seller has access to some information structure that maps types to signal realizations, allowing her to segment the market and charge a profit-maximizing price for each segment. Types in our setting represent everything that is possibly knowable, e.g., a complete profile of consumer characteristics, and a segmentation reflects what the seller actually knows, e.g., perhaps only consumer locations.

Within this framework, we examine how additional information impacts welfare through a pair of opposing properties. Information is "monotonically bad" if every refinement of any segmentation reduces weighted surplus — a convex combination of consumer and producer surplus. Information is "monotonically good" if weighted surplus is higher for any refinement. We refer to these properties as surplus-monotonicity properties.

Our main result characterizes each surplus-monotonicity property and has two parts. The first part of the result reduces the problem, for an unrestricted set of demand curves, to one with only two demand curves. It says that surplus-monotonicity holds if and only if three conditions are satisfied. First, the demand curves cannot be too far apart in the sense that the optimal monopoly price of each of them is in the interior of any other's domain of prices. Second, the set of all demand curves is decomposable into at most two basis demand curves. Third, the two basis demand curves satisfy the surplus-monotonicity condition themselves. Given the reduction in the first part of the result, the second part then identifies a closed-form expression that characterizes when a given pair of demand curves satisfies surplus-monotonicity.

The full version of the paper can be accessed here: https://nimahaghpanah.com/pdfs/gooddata.pdf

We propose to solve revenue-maximizing selling mechanisms for a multiproduct monopoly based on nonlinear pricing à la Bulow and Roberts [1989]. We derive the marginal revenue change due to a price perturbation on any subset of bundles, holding the prices of other bundles fixed. We show that the MR of any bundle can be expressed as the integral of an "MR density" over the set of types who self-select this bundle (demand set), minus the mass of types on the boundary of its intersection with the type space. Given any optimal taxation mechanism, the revenue must not increase with any small price change for bundles with positive demand (MR = 0), nor with a small price decrease for bundles with zero demand (MR ≥ 0).

Background and motivation. Online platforms frequently deploy nudges—short prompts or design elements intended to influence user behavior—in a wide range of contexts, from increasing engagement with digital products to encouraging healthier choices. Despite their widespread use, key challenges remain in optimizing nudges over time, particularly when users' responsiveness is unknown and repeated exposure to the same nudge leads to diminishing returns. This work introduces a novel framework to address these challenges, focusing on the interplay between unknown user responses, the cost of generating or refreshing nudges, and fatigue effects from repeated exposure to the same prompt.

The I.I.D. Prophet Inequality is a fundamental problem in optimal stopping theory where, given n independent random variables X₁, ..., X_n drawn from a known distribution D, one has to decide at every step i whether to stop and accept X_i; or discard it forever and continue. The goal is to maximize (or minimize) the selected value and compete against the all-knowing prophet. For the maximization setting, a tight constant-competitive guarantee of ≈ 0.745 is well-known [Correa, Foncea, Hoeksma, Oosterwijk, Vredeveld, 2019], whereas the minimization setting is qualitatively different: the optimal constant is distribution-dependent and can be arbitrarily large [Livanos and Mehta, 2024].

In this paper, we provide a novel framework via the lens of Extreme Value Theory to analyze optimal threshold algorithms. We show that the competitive ratio for the minimization setting has a closed form described by a function Λ, which depends only on the extreme value index γ; in particular, it corresponds to Λ(γ) for γ ≤ 0. Despite the contrast of the optimal guarantees for maximization and minimization, our framework turns out to be universal and is able to recover the results of [Kennedy and Kertz, 1991] for the maximization case as well. Surprisingly, the optimal competitive ratio for the maximization setting is given by the same function Λ(γ), but for γ ≥ 0. Along the way, we obtain several results on the algorithm and the prophet's objectives from the perspective of extreme value theory, which might be of independent interest.

We next study single-threshold algorithms for the minimization setting. Again, using the extreme value theory, we generalize the results of [Livanos and Mehta, 2024] which hold only for special classes of distributions, and obtain poly-logarithmic in n guarantees on the competitive ratio. Finally, we consider the k-multi-unit prophet inequality in the minimization setting and show that there exist constant-competitive single-threshold algorithms when k ≥ log n.

We envision a marketplace where diverse entities offer specialized "modules" through APIs, allowing users to compose the outputs of these modules for complex tasks within a given budget. This paper studies the market design problem in such an ecosystem, where module owners strategically set prices for their APIs (to maximize their profit) and a central platform orchestrates the aggregation of module outputs at query-time. One can also think about this as a first-price procurement auction with budgets. The first observation is that if the platform's algorithm is to find the optimal set of modules then this could result in a poor outcome, in the sense that there are price equilibria which provide arbitrarily low value for the user. We show that under a suitable version of the "bang-per-buck" algorithm for the knapsack problem, an ε-approximate equilibrium always exists, for any arbitrary ε > 0. Further, our first main result shows that with this algorithm any such equilibrium provides a constant approximation to the optimal value that the buyer could get under various constraints including (i) a budget constraint and (ii) a budget and a matroid constraint. This can also be interpreted as a price of anarchy result for budget-constrained first-price procurement auctions. Finally, we demonstrate that these approximately efficient equilibria can be learned through decentralized price adjustments by module owners using no-regret learning algorithms.

We provide optimal solutions to an institution that has distributional objectives when choosing from a set of applications based on merit (or priority). For example, in college admissions, administrators may want to admit a diverse class in addition to choosing students with the highest qualifications. We provide a family of choice rules that maximize merit subject to attaining a level of the distributional objective. We study the desirable properties of choice rules in this family and use them to find all subsets of applications on the Pareto frontier of the distributional objective and merit. In addition, we provide two novel characterizations of matroids. A full version is available at https://arxiv.org/abs/2301.00237.

We study the benefits of a one-shot price experiment for a seller who has limited information about customer valuations of a product. The seller only knows the exact purchase probability associated with a single historical price and aims to maximize the worst-case revenue ratio compared to an oracle with complete knowledge of the value distribution. The seller conducts a one-shot price experiment by first choosing an experiment price and then setting a final price based on the realized purchase probabilities from both the historical and experimental prices. We assume that the customer's virtual value function is non-decreasing. Our main findings are threefold:

Optimal Experiment Price and Policy Structure: We analytically characterize the optimal distributionally robust experiment price and provide its performance guarantee for any historical purchase probability. Moreover, we show that the optimal one-shot price experiment policy follows a keep-or-adjust structure: the seller uses a predetermined final price if the experiment price does not yield higher profits, and otherwise adjusts the final price based on the experiment's outcome. We use this keep-or-adjust structure, along with novel geometric arguments, to address the technical challenges of the problem.

Markup vs. Markdown Experimentation: We determine when it is optimal for the firm to experiment with a higher (markup) or lower (markdown) price than the historical price. When the purchase probability at the historical price is above a threshold—surprisingly low at approximately 29.5%—the firm should experiment with a markup price. Otherwise, it should use a markdown price. The intuition is that if the markup experiment fails to improve profits, the firm can still fall back to a lower final price than the historical one.

Bimodal Value of Experimentation: We prove that as the historical purchase probability increases from 0 to 1, the value of conducting a one-shot price experiment compared to not experimenting is bimodal: it first increases, then decreases, then increases again, and finally decreases.

Finally, we extend the model to settings where the experiment may be noisy and to cases where the seller has access to multiple initial data points. In the latter case, we show that the seller needs to use at most five specific initial data pairs to compute the optimal experimental and final prices.

A full version of this paper is available at http://ssrn.com/abstract=4899852.

We study network games in which players choose partners and an effort level. There is a finite set of players N, each choosing an action s_i; from an ordered set S_i and forming links G, with payoffs u_i(G, s). We study two stability concepts: an outcome (G, s) is strictly pairwise stable if (i) actions s are a Nash equilibrium for fixed G; (ii) no player wishes to unilaterally sever an existing link; and (iii) no pair of unlinked players both weakly desire to form a link. The network is strictly pairwise Nash stable if no player can strictly benefit from simultaneously changing their action and severing some links.

Our analysis focuses on environments with only vertical heterogeneity, where all agents agree on the ranking of others as partners. Key ordinal payoff conditions determine stable network shapes.

In the simple case of separable games, where ui(G, s) = vi(s)+∑_j∈Gi g(s_i, s_j), these concern:

(1) Spillovers from actions: positive (negative) spillovers if higher actions make a player more (less) attractive.

(2) Interaction between actions and links: action-link complements (substitutes) if higher own actions make links more (less) beneficial.

We then have a taxonomy of stable network structures:

• Positive spillovers and action-link complements imply nested split graphs in which actions are increasing in degree.

• Negative spillovers and action-link substitutes imply nested split graphs in which actions are decreasing in degree.

• Either of positive spillovers and action-link substitutes or negative spillovers and action-link complements implies ordered overlapping cliques. This network structure is a union of complete graphs, with homophily in actions.

These structures emerge as stable outcomes more generally, without assuming separability, under ordinal properties of consistency, reflecting a shared view of partner desirability, and alignment, linking one's attractiveness to one's own linking propensity

Several applications illustrate the value of the framework. First, we explain perverse outcomes in peer group design, where ignoring network formation yields interventions that hurt the individuals they are meant to help. Second, we analyze status competitions, predicting homophilous cliques in situations with action-link complements (e.g., conspicuous consumption and socializing are complements) and negative externalities (due to social comparisons with friends who conspicuously consume). Third, we microfound group matching models by identifying conditions under which it is without loss of generality to assume players form cliques, even when they can discriminate at the link level.

A full version of the paper can be found at https://www.arxiv.org/abs/2411.08026.