Online marketplaces will be transformed by autonomous AI agents acting on behalf of consumers. Rather than humans browsing and clicking, AI agents can parse webpages or interact through APIs to evaluate products, and transact. This raises a fundamental question: what do AI agents buy—and why? We develop ACES, a sandbox environment that pairs a platform-agnostic agent with a fully programmable mock marketplace to study this. We first explore aggregate choices, revealing that modal choices can differ across models, with AI agents sometimes concentrating on a few products, raising competition questions. We then analyze the current drivers of choices through randomized experiments on product positions and listing attributes. Models show sizeable and heterogeneous position effects: all favor the top row, yet different models prefer different columns, undermining the assumption of a universal ''top'' rank. They penalize sponsored tags, reward endorsements, and sensitivities to price, ratings, and reviews are directionally as expected, but vary sharply across models. Our findings reveal how AI agents behave in e-commerce, and surface concrete monitoring, seller strategy, platform design, and regulatory questions.

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.

Recommendation systems are widespread, and through customized recommendations, promise to match users with options they will like. To that end, data on engagement is collected and used. Most recommendation systems are ranking-based, where they rank and recommend items based on their predicted engagement. However, the engagement signals are often only a crude proxy for user utility, as data on the latter is rarely collected or available. This paper explores the following question: By optimizing for measurable proxies, are recommendation systems at risk of significantly under-delivering on user utility? If that is indeed the case, how can one improve utility which is seldom measured? To study these questions, we introduce a model of repeated user consumption in which, at each interaction, users select between an outside option and the best option from a recommendation set. Our model accounts for user heterogeneity, with the majority preferring “popular” content, and a minority favoring “niche” content. The system initially lacks knowledge of individual user preferences but can learn these preferences through observations of users’ choices over time. Our theoretical and numerical analysis demonstrate that optimizing for engagement signals can lead to significant utility losses. Instead, we propose a utility-aware policy that initially recommends a mix of popular and niche content. We show that such a policy substantially improves utility despite not measuring it. As the platform becomes more forward-looking, our utility-aware policy achieves the best of both worlds: near-optimal user utility and near-optimal engagement simultaneously. Our study elucidates an important feature of recommendation systems; given the ability to suggest multiple items, one can perform significant exploration without incurring significant reductions in short term engagement. By recommending high-risk, high-reward items alongside popular items, systems can enhance discovery of high utility items without significantly affecting engagement.

How significant was the role of racial preferences in U.S. college admissions before the Supreme Court's 2023 decision to ban race-based affirmative action? How much might test-optional admission policies impact racial diversity and academic merit? In this work, we estimate a simple model of college admissions decisions from 2012--2021, leveraging a novel dataset of applicant profiles and admissions outcomes across the full spectrum of college selectivity. We find that, broadly, the impact of race and testing policies on diversity and merit of admits decreases by college selectivity. For America's less selective colleges that collectively enroll over three-quarters of students, fully eliminating racial preferences---expressed either directly or via unobserved correlates---has little impact on the proportion of underrepresented minorities (URM) and on the average SAT score of admitted students. In contrast, for the 34 most selective colleges accounting for 3 percent of total enrollment, our estimates suggest that admissions going "race blind"---absent any compensating changes in admissions criteria---could reduce URM admission by one-third while increasing the average SAT score of admits by no more than 10 points. We also estimate that universal test-optional admission does not materially affect the proportion of URMs at elite colleges, and may decrease the average SAT score by up to 10 points. At less selective institutions, the effects are estimated to be negligible.

Motivated by matching platforms that match agents in a centralized manner, we introduce a model of dynamic two-sided matching where both demand and supply are heterogeneous with many types and the pool of supply units is limited. We model heterogeneity on the two sides of the market by i.i.d. demand weight vectors and i.i.d. supply feature vectors, with possibly different distributions. The matching of a demand-supply pair generates a utility that depends on their weight and feature vectors. To reflect the realistic structure of a heterogeneous matching market while also avoid impossibility results, we consider various levels of assumptions (in particular, the spatial structure) on matching utilities and feature distributions. The goal of the centralized platform is to dynamically assign supply units to sequentially arriving demand units in order to maximize utility. Many popular heuristic policies are either sub-optimal (like the myopic policy) or computationally inefficient (like the certainty equivalent policy). We propose a forward-looking supply-aware policy dubbed Simulate-Optimize-Assign-Repeat (SOAR) that combines practicality and strong theoretical guarantee. Inspired by model predictive control (MPC), SOAR leverages the power of simulation to balance between producing immediate high match utility and preserving valuable supply for future demands. We use regret as our performance metric for matching policies, specifically the additive loss relative to the utility per match achievable in the continuum limit (n → ∞). Under mild regularity assumptions on the offline matching instances, we prove that SOAR achieves the optimal regret scaling (up to a log factor). We further characterize the optimal regret scaling for interesting classes of problems with additional model structure, in particular, two classes of utility functions: (i) the "spatial utilities", namely the negative p-th power of the Euclidean distance between the supply and demand vectors where p ≥ 1; and (ii) the dot-product utility (equivalently p = 2 of (i)), and two classes of distributions: (i) both supply and demand distributions are smooth (a more stringent assumption) and (ii) supply and demand distributions are supported over compact sets (a mild assumption). En route to proving our guarantees we develop a novel framework for analyzing the performance of our SOAR policy which may be of wider applicability and independent interest. As a corollary of our techniques, we also resolve an open problem posed in Kanoria 2022.

We study the problem of networked online convex optimization, where each agent individually decides on an action at every time step and agents cooperatively seek to minimize the total global cost over a finite horizon. The global cost is made up of three types of local costs: convex node costs, temporal interaction costs, and spatial interaction costs. In deciding their individual action at each time, an agent has access to predictions of local cost functions for the next $k$ time steps in an $r$-hop neighborhood. Our work proposes a novel online algorithm, Localized Predictive Control (LPC), which generalizes predictive control to multi-agent systems. We show that LPC achieves a competitive ratio of $1 + \tilde{O}(\rho_T^k) + \tilde{O}(\rho_S^r)$ in an adversarial setting, where $\rho_T$ and $\rho_S$ are constants in $(0, 1)$ that increase with the relative strength of temporal and spatial interaction costs, respectively. This is the first competitive ratio bound on decentralized predictive control for networked online convex optimization. Further, we show that the dependence on $k$ and $r$ in our results is near optimal by lower bounding the competitive ratio of any decentralized online algorithm.

We study the multi-secretary problem with capacity to hire up to B out of T candidates, and values drawn i.i.d. from a distribution F on [0,1]. We investigate achievable regret performance, where the latter is defined as the difference between the performance of an oracle with perfect information of future types (values) and an online policy. While the case of distributions over a few discrete types is well understood, very little is known when there are many types, with the exception of the special case of a uniform distribution of types. In this work we consider a larger class of distributions which includes the few discrete types as a special case. We first establish the insufficiency of the common certainty equivalent heuristic for distributions with many types and "gaps" (intervals) of absent types; even for simple deviations from the uniform distribution, it leads to regret Θ(√T), as large as that of a non-adaptive algorithm. We introduce a new algorithmic principle which we call "conservativeness with respect to gaps" (CwG), and use it to design an algorithm that applies to any distribution. We establish that the proposed algorithm yields optimal regret scaling of ~Θ (T1/2 - 1/(2(β + 1))) for a broad class of distributions with gaps, where β quantifies the mass accumulation of types around gaps. We recover constant regret scaling for the special case of a bounded number of types (β=0 in this case). In most practical network revenue management problems, the number of types is large and the current certainty equivalent heuristics scale poorly with the number of types. The new algorithmic principle called Conservatism w.r.t Gaps (CwG) that we developed, can pave the way for progress on handling many types for the broader class of network revenue management problems like order fulfillment and online matching.

Motivated by a variety of online matching platforms, we consider demand and supply units which are located i.i.d. in d-dimensional space, and each demand unit needs to be matched with a supply unit. The goal is to minimize the expected average distance between matched pairs (the "cost"). We model dynamic arrivals of one or both of demand and supply with uncertain locations of future arrivals, and characterize the scaling behavior of the achievable cost in terms of system size (number of supply units), as a function of the dimension d. Our achievability results are backed by concrete matching algorithms. Across cases, we find that the platform can achieve cost (nearly) as low as that achievable if the locations of future arrivals had been known beforehand. Furthermore, in all cases except one, cost nearly as low as the expected distance to the nearest neighboring supply unit is achievable, i.e., the matching constraint does not cause an increase in cost either. The aberrant case is where only demand arrivals are dynamic, and space is one-dimensional d=1; excess supply significantly reduces cost in this case.

We revisit the popular random matching market model introduced by Knuth (1976) and Pittel (1989), and shown by Ashlagi, Kanoria and Leshno (2013) to exhibit a “stark effect of competition”; in particular, with any difference in the number of agents on the two sides (“imbalance”), the short side agents obtain substantially better outcomes. We generalize the model to allow “partially connected” markets with each agent having an average degree d in a random (undirected) graph. Each agent has a (uniformly random) preference ranking over only their neighbors in the graph. We characterize stable matchings in large markets and find that the short side enjoys a significant advantage only for d exceeding log2 n where n is the number of agents on one side: For moderately connected markets with d = o(log2 n), we find that there is no advantage to being on the short side (for O(n1–∊) market imbalance), with agents on both sides getting a -ranked partner on average. Notably, this “mild competition” regime extends far beyond the connectivity threshold of d = Θ(log n). In contrast, for densely connected markets with d = ω(log2 n), we find a strong effect of competition, namely, short side agents get a log n-ranked partner on average, while the long side agents get a partner of (much larger) rank d/log n on average. Our results and analysis suggest that in general matching markets, being on the short side confers an advantage if and only if the number of short-side agents who remain unmatched is small relative to the market imbalance.

We study the problem of maximizing payoff generated over a period of time in a general class of closed queueing networks with finite, fixed number of supply units which circulate in the system. Demand arrives stochastically, and serving a demand unit (customer) causes a supply unit to relocate from the "origin" to the "destination" of the customer. We consider general controls including entry control, pricing, and assignment. Motivating applications include shared transportation platforms and scrip systems.

We study how much communication is needed to find a stable matching in a two-sided matching market with private preferences. Segal (2007) and Gonczarowski et al.~(2015) showed that in the worst case, any protocol that computes a stable matching requires the communication cost per agent to scale linearly in the total number of agents. In real-world markets with many agents, this communication requirement is implausibly high. This casts doubts on whether stable matching can arise in large markets. We study markets with realistic structure on the preferences and information of agents, and show that in "typical" markets, a stable matching can be found with much less communication effort. In our model, the preferences of workers are unrestricted, and the preferences of firms follow an additively separable latent utility model. Our efficient communication protocol modifies workers-proposing DA, by having firms signal workers they especially like, while also broadcasting qualification requirements to discourage other workers who have no realistic chances from applying. In the special case of tiered random markets, the protocol can be modified to run in two-rounds and involve only private messages. Our protocols have good incentive properties and give insights on how to mediate large matching markets to reduce congestion.

We consider the problem faced by a service platform that needs to match supply with demand but also to learn attributes of new arrivals in order to match them better in the future. We introduce a benchmark model with heterogeneous workers and jobs that arrive over time. Job types are known to the platform, but worker types are unknown and must be learned by observing match outcomes. Workers depart after performing a certain number of jobs. The payoff from a match depends on the pair of types and the goal is to maximize the steady-state rate of accumulation of payoff.

Two-sided matching platforms, such as those for labor, accommodation, dating, and taxi hailing, can control and optimize over many aspects of the search for partners. To understand how the search for partners should be designed, we consider a dynamic model of search by strategic agents with costly discovery of pair-specific match value. We find that in many settings, the platform can mitigate wasteful competition in partner search via restricting what agents can see/do. For medium-sized screening costs (relative to idiosyncratic variation in utilities), the platform should prevent one side of the market from exercising choice (similar to Instant Book on Airbnb), whereas for large screening costs, the platform should centrally determine matches (similar to taxi hailing marketplaces). Surprisingly, simple restrictions can improve social welfare even when screening costs are small, and agents on each side are ex-ante homogeneous. In asymmetric markets where agents on one side have a tendency to be more selective (due to smaller screening costs or greater market power), the platform should force the more selective side of the market to reach out first, by explicitly disallowing the less selective side from doing so. This allows the agents on the less selective side to exercise more choice in equilibrium.When agents are vertically differentiated, forcing one side of the market to propose results in a significant increase in welfare even in the limit of vanishing screening costs. Furthermore, a Pareto improvement in welfare is possible in this limit: the weakest agents can be helped without hurting other agents. In addition, in this setting the platform can further boost welfare by hiding quality information.

We consider the problem of efficient operation of a barter exchange platform for indivisible goods. We introduce a dynamic model of barter exchange where in each period one agent arrives with a single item she wants to exchange for a different item. We study a homogeneous and stochastic environment: an agent is interested in the item possessed by another agent with probability p, independently for all pairs of agents. We consider two settings with respect to the types of allowed exchanges: a) Only two-way cycles, in which two agents swap their items, b) Two or three-way cycles. The goal of the platform is to minimize the average waiting time of an agent. Somewhat surprisingly, we find that in each of these settings, a policy that conducts exchanges in a greedy fashion is near optimal, among a large class of policies that includes batching policies. Further, we find that for small p, allowing three-cycles can greatly improve the waiting time over the two-cycles only setting. Specifically, we find that a greedy policy achieves an average waiting time of Θ(1/p2) in setting a), and Θ(1/p3/2) in setting b). Thus, a platform can achieve the smallest waiting times by using a greedy policy, and by facilitating three cycles, if possible. Our findings are consistent with empirical and computational observations which compare batching policies in the context of kidney exchange programs.

Assignment markets involve matching with transfers, as in labor markets and housing markets. We consider a two-sided assignment market with agent types and stochastic structure similar to models used in empirical studies, and characterize the size of the core in such markets. Each agent has a randomly drawn productivity with respect to each type of agent on the other side. The value generated from a match between a pair of agents is the sum of the two productivity terms, each of which depends only on the type but not the identity of one of the agents, and a third deterministic term driven by the pair of types. We allow the number of agents to grow, keeping the number of agent types fixed. Let n be the number of agents and K be the number of types on the side of the market with more types. We find, under reasonable assumptions, that the relative variation in utility per agent over core outcomes is bounded as O*(1/n1/K), where polylogarithmic factors have been suppressed. Further, we show that this bound is tight in worst case. We also provide a tighter bound under more restrictive assumptions.

We consider a decentralized two-sided matching market in which agents arrive and depart asynchronously. As a result, it is possible that an agent on one side of the market (a "buyer") identifies an agent on the other side of the market (a "seller") who is a suitable match, only to find that the seller is already matched. We find using a mean field approach that lack of knowledge about availability can create large welfare losses to both buyers and sellers. We consider a simple intervention available to the platform: limiting visibility of sellers. We find that this intervention can significantly improve the welfare of agents on both sides of the market; sellers pay lower application costs, while buyers are less likely to find that the sellers they screen have already matched. Somewhat counterintuitively, the benefits of showing fewer sellers to each buyer are greatest in markets in which there is a shortage of sellers.

We analyze large random matching markets with unequal numbers of men and women. Agents have complete preference lists that are uniformly random and independent, and we consider stable matchings under the realized preferences. We find that being on the short side of the market confers a large advantage.

We study agents in a social network who learn by observing the actions of their neighbors. The agents iteratively estimate an unknown "state of the world" s from initial private signals, and the past actions of their neighbors in the social network. First, we consider a set of Bayesian agents, and investigate the computational problem the agents face in implementing the (myopic) Bayesian decision rule. When private signals are independent conditioned on s, and when the social network graph is a tree, we provide a new `dynamic cavity algorithm' for the agents' calculations, with computational effort that is exponentially lower than what is currently known. We use our algorithm to perform the first numerical simulations of interacting Bayesian agents on networks with hundreds of nodes. Second, we investigate a different model of social learning, with naive agents who practice "majority dynamics", i.e., at each round adopt the majority opinion of their neighbors. Under mild conditions, we show that under majority dynamics, agents learn s with probability 1-ϵ in O(log log (1/ϵ)) rounds. We conjecture that on d-regular trees, myopic Bayesian agents learn s as quickly as agents who practice majority dynamics. Using our algorithm for Bayesian agents, the conjecture implies that the computational effort required of Bayesian agents to learn s is only polylogarithmic in 1/ϵ on d-regular trees. Thus, our results challenge the belief that iterative Bayesian learning is computationally intractable.

The binary deletion channel is the simplest point-to-point communication channel that models lack of synchronization. Input bits are deleted independently with probability d, and when they are not deleted, they are not affected by the channel. Despite significant effort, little is known about the capacity of this channel and even less about optimal coding schemes. In this paper, we develop a new systematic approach to this problem, by demonstrating that capacity can be computed in a series expansion for small deletion probability. We compute three leading terms of this expansion, and find an input distribution that achieves capacity up to this order. This constitutes the first optimal random coding result for the deletion channel. The key idea employed is the following: We understand perfectly the deletion channel with deletion probability d=0. It has capacity 1 and the optimal input distribution is iid Bernoulli (1/2). It is natural to expect that the channel with small deletion probabilities has a capacity that varies smoothly with d, and that the optimal input distribution is obtained by smoothly perturbing the iid Bernoulli (1/2) process. Our results show that this is indeed the case.

We study a model of Bayesian agents in social networks who learn from the actions of their neighbors. Agents attempt to iteratively estimate an unknown `state of the world' s from initial private signals, and the past actions of their neighbors in the network. We investigate the computational problem the agents face in implementing the (myopic) Bayesian decision rule. When private signals are independent conditioned on s, and when the social network graph is a tree, we provide a new `dynamic cavity algorithm' for the agents' calculations, with computational effort that is exponentially lower than a naive dynamic program. We use this algorithm to perform the first numerical simulations of Bayesian agents on networks with hundreds of nodes, and observe rapid learning of s in some settings.

The XOR-satisfiability (XORSAT) problem requires finding an assignment of n Boolean variables that satisfy m exclusive OR (XOR) clauses, whereby each clause constrains a subset of the variables. We consider random XORSAT instances, drawn uniformly at random from the ensemble of formulae containing n variables and m clauses of size k. This model presents several structural similarities to other ensembles of constraint satisfaction problems, such as k-satisfiability (k-SAT). For many of these ensembles, as the number of constraints per variable grows, the set of solutions shatters into an exponential number of well-separated components. This phenomenon appears to be related to the difficulty of solving random instances of such problems. We prove a complete characterization of this clustering phase transition for random k-XORSAT. In particular we prove that the clustering threshold is sharp and determine its exact location. We prove that the set of solutions has large conductance below this threshold and that each of the clusters has large conductance above the same threshold. Our proof constructs a very sparse basis for the set of solutions (or the subset within a cluster). This construction is achieved through a low complexity iterative algorithm.

Bargaining networks model the behavior of a set of players who need to reach pairwise agreements for making profits. Nash bargaining solutions in this context correspond to solutions which are stable and balanced. Kleinberg and Tardos [19] proved that, if such solutions exist, then they can by calculated in polynomial time. This left open the question: Are there dynamics which can describe the bargaining process of real-world players, and which converge quickly to a Nash bargaining solution? This paper provides an affirmative answer to that question. The contribution of this paper is threefold: (1) We introduce a single-stage local dynamics which models the way in which actual players could bargain. We show that (approximate) fixed points of our dynamics are in one-to-one correspondence with (approximate) Nash bargaining solutions. (2) We prove that our dynamics converges to an ∊-fixed point in O(1/∊2) iterations independent of the network size when the potential earnings (weights) are uniformly bounded. We use this to prove that an approximate Nash bargaining solution is reached in time polynomial in 1/∊, the network size and 1/g. Here g is the difference between the weights of the two corners of the matching polytope having largest weights, and controls the behavior of fast message passing algorithms for maximum weight matching (matching naturally arises as a subproblem of Nash bargaining). (3) Our proof introduces a new powerful technique from functional analysis to this set of problems. The technique allows us to extend our results in various directions. We believe the tools introduced here will be useful in many related problems. As a corollary, for bipartite graphs we prove polynomial time convergence to an approximate Nash bargaining solution, with probability close to one under small random perturbations.

We present a new technique for statistical static timing analysis (SSTA) based on Markov chain Monte Carlo (MCMC), that allows fast and accurate estimation of the right-hand tail of the delay distribution. A ¿naive¿ MCMC approach is inadequate for SSTA. Several modifications and enhancements, presented in this paper, enable application of MCMC to SSTA. Moreover, such an approach overcomes inherent limitations of techniques such as importance sampling and Quasi-Monte Carlo. Our results on open source designs, with an independent delay variation model, demonstrate that our technique can obtain more than an order of magnitude improvement in computation time over simple Monte Carlo, given an estimation accuracy target at a point in the tail. Our approach works by providing a large number of samples in the region of interest. Open problems include extension of algorithm applicability to a broader class of synthesis conditions, and handling of correlated delay variations. In a broader context, this work aims to show that MCMC and associated techniques can be useful in rare event analyses related to circuits, particularly for high-dimensional problems.

The deletion channel is the simplest point-to-point communication channel that models lack of synchronization. Despite significant effort, little is known about its capacity, and even less about optimal coding schemes. In this paper we initiate a new systematic approach to this problem, by demonstrating that capacity can be computed in a series expansion for small deletion probability.We compute two leading terms of this expansion, and show that capacity is achieved, up to this order, by i.i.d. uniform random distribution of the input. We think that this strategy can be useful in a number of capacity calculations.

We consider distributed computation of functions of distributed data in random planar networks with noisy wireless links. We present a new algorithm for computation of the maximum value which is order optimal in the number of transmissions and computation time. We also adapt the histogram computation algorithm of Ying et al [1] to make the histogram computation time optimal.