Papers for

online marketplace engineers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Optimal online combinatorial auctions cannot ensure half the best outcome

The Optimal Competitive Ratio for Subadditive Online Combinatorial Auctions is Less Than 1/2

Abstract: We construct a four-buyer online combinatorial auction with independent subadditive valuations and a fixed, known arrival order in which every online rule earns strictly less than $1/2$ of the expected offline optimum. A common partition, revealed at the third arrival, gives the first three buyers one unit of welfare per item. If the rule uses three distinct partitions, either an item allocated early contributes zero or the fourth buyer's expected value for the remaining bundle is one less than its size. We compute the optimal online and offline welfare exactly and show that a $1/2$ guarantee always holds with at most three buyers.

Wed 18 NovComputer Science and Game Theory
The gist
This paper looks at a type of auction where items are sold to several buyers arriving one after another, with values that don't simply add up. The authors show an example where any method used online will earn less than half the total value possible if buyers were known in advance. They find this limit happens from four buyers onwards, but if there are three or fewer buyers, a method can always get at least half the best possible total value. This means there's a hard barrier in how well online auctions can perform compared to offline ones.
Open → 2611.24920v1

Computing optimal online matching is hard for random arrivals

Computational Hardness of Online Stochastic Matching

Abstract: In the online stochastic matching problem on a bipartite graph, offline vertices are given in advance, and online requests arrive sequentially from known distributions, each matched immediately and irrevocably to a free neighbor or rejected. Computational hardness results of the optimal online strategy have been known only for instances where online vertices have a fixed arrival order [Papadimitriou et al., 2024]. For random-order arrivals or even i.i.d. arrivals, it has been long open since the problem was proposed [Feldman et al., 2009]. In this paper, we give the first computational hardness results for online stochastic matching with random-order arrivals. In particular, we prove that for known i.i.d. arrivals, computing the online optimum is APX-hard, ruling out a Polynomial-Time Approximation Scheme unless P = NP, even in unweighted graphs with two offline neighbors per online vertex. For random-order arrivals, even when there is only one offline node (i.e., the prophet secretary setting), computing the optimal online policy is #P-hard, resolving an open problem since [Dütting et al., 2023].

Tue 17 NovData Structures and AlgorithmsComputational ComplexityComputer Science and Game Theory
The gist
Finding the best way to match online requests to fixed resources as they arrive randomly is a difficult problem. The paper shows that even with simple graph structures and known probability patterns for requests, calculating the absolute best matching strategy is computationally very hard. This means no fast algorithms can guarantee near-perfect solutions unless some major assumptions in computer science are overturned. The results answer open questions about how complexity changes when requests arrive in random orders or independently.
Open → 2611.23157v1

Impatience in matching systems makes optimal pairing very hard

Impatience Makes Matching NP-Hard

Abstract: Motivated by emerging applications such as online marketplaces and quantum switches, we study a dynamic bipartite matching model with impatient agents, where the two sides represent customers and suppliers. Agents of each type arrive according to an independent Poisson process, and the platform decides which pairs of agents to match. The agents are possibly impatient and may leave the system if not matched before their patience expires. The platform aims to maximize throughput, i.e., the number of matches per unit time. In this paper, we reveal an interesting phase transition in the computational hardness of throughput maximization. In particular, we show that approximating the optimal long-run throughput within a sufficiently small fixed relative error is NP-hard, even when all agents have rate-one exponential patience. This result implies a computational barrier to constructing near-optimal, efficiently executable matching policies that induce a matching process with fast mixing. On the other hand, when all agents on at least one side have infinite patience, we provide a simple polynomial-time algorithm that maximizes the throughput.

Sun 15 NovComputational ComplexityData Structures and Algorithms
The gist
Matching customers with suppliers quickly is important in many online systems, but when people get impatient and leave if not matched fast enough, the problem of maximizing matches becomes very hard to solve. The authors show that even when everyone is equally impatient, finding nearly the best long-term pairing plan is computationally impossible unless P equals NP. However, if one side of the matching is always patient, then they provide an efficient way to maximize matches. This highlights a big difference in how easily these matching problems can be solved depending on how patient the agents are.
Open → 2611.20234v1

First-price auctions can allocate AI tasks efficiently with less welfare loss

Price of Anarchy of First-Price Auctions in Agentic Markets

Abstract: An agentic market is a decentralized serving-time market where AI agents bid to claim each user prompt. An agent's bid is based on its expected value for the prompt, which is the expectation of the reward for its response minus its inference costs. First-price auctions (FPAs), in which the highest bidder pays its bid and receives the prompt, are a natural way to allocate prompts in such a market, since they are simple and transparent to run, and do not require central knowledge of private capabilities and costs. However, FPAs are not truthful: participants may bid less than their true value in the hope of a larger profit, and the prompt may then be allocated to someone other than the bidder who values it the most. This welfare loss is quantified by the $\textit{price-of-anarchy}$ (PoA). In this paper, we argue that agentic markets are likely to possess features that reduce the price-of-anarchy. The first is a $\textit{competitive floor}$, which occurs when multiple bidders usually value the prompt above some baseline share of the optimal welfare (e.g., because the best models are often distilled into cheaper alternatives, which perform similarly). We show that competition among them then limits the welfare loss, which can be driven to zero as the floor rises. The second feature is $\textit{near-independence}$ of values after conditioning on the prompt, which occurs when most of the predictable variation in the expected value is determined by the difficulty of the prompt. As the value distribution approaches conditional independence, we can derive an efficiency guarantee that approaches a factor of $1 - 1/e^2$ of the optimal welfare. Thus, both features give rise to welfare lower bounds that are significantly better than the well-known general case of $1 - 1/e$. We validate these results empirically using auctions with strategic bidders simulated on the EmbedLLM prompt routing dataset.

Wed 14 OctComputer Science and Game TheoryArtificial IntelligenceMachine Learning
The gist
When many AI programs bid to answer questions, the way they bid can lead to less-than-ideal outcomes if the highest bidder pays their bid. The authors explore how certain natural features of these markets—like competition at a baseline value and how AI values depend mainly on the question’s difficulty—can reduce this inefficiency. They show that these features make the system almost as good as if everyone was perfectly truthful. Their findings are supported by testing on simulated AI bidding data.
Open → 2610.20587v1

Bipartite matching accuracy depends on rounds and queries used

Bipartite Matching with Few Rounds of Demand Queries

Abstract: We study the randomised and deterministic demand-query complexity of approximate bipartite matching with few query rounds. The demand-query model, introduced in [Blumrosen and Nisan SICOMP 2009; Nisan SODA 2021], is inspired by combinatorial auctions and welfare maximisation, where an oracle returns the first neighbouring vertex (item) of a vertex u (agent) according to a given permutation pi (preference ordering of the agent over the items). For randomised algorithms, our main result gives a trade-off between the number of rounds k, the per-round query budget q=n^{1+δ}, and the achievable approximation ratio. Let 1 <= k <= log n, and -1 <= delta <= 1/k. Every k-round randomised algorithm using O(q) demand queries per round has a worst-case expected-size approximation factor of Omega(n^{1/2k-delta/2}/k). Conversely, we give a randomised algorithm achieving approximation factor O(n^{(1-k*delta)/(k+1)}/k) in expectation. For deterministic algorithms, for k*q >= n, we show that the optimal deterministic approximation factor is ~Theta(n^2/(q*k^2)), thereby improving the previous lower bound of [Nisan SODA 2021] by a polynomial factor over a wide range of parameters. In particular, for q=Theta(n), we improve the deterministic round-complexity lower bound for constant-factor approximation from ~Omega(n^{1/3}) to ~Omega(sqrt n). Our algorithms produce matching and vertex-cover certificates; the deterministic trade-off also extends to minimum vertex cover and maximum fractional matching. We extend the randomised upper bounds to the weaker Demand-OR model [Nisan 2021]. We prove a non-adaptive simulation of uniform random-neighbour queries using known techniques, avoiding the O(log n)-round penalty of the trivial binary-search simulation. Consequently, our upper bounds yield the same k-round approximation guarantees using O(q * log^2 n) Demand-OR queries per round.

Tue 13 OctData Structures and AlgorithmsComputational Complexity
The gist
Matching items to people can be hard when we only get limited information from each request. The authors studied how many questions you need to ask and over how many steps to get a good approximate pairing between two groups. They found clear trade-offs showing how accuracy improves when you allow more rounds of questions or more queries each time. The paper also improves previous results for methods where the question order is fixed and provides algorithms that work with weaker types of queries.
Open → 2610.18777v1

Auction designs measured by worst case environment performance

Robustness in Mechanism Design

Abstract: The article reviews the robust design and analysis of auctions, focusing on the predominant paradigm in the computer science literature, which quantifies robustness by the worst-case, over environments, ratio between the robust auction's performance and that of an optimal auction for the environment. Applications include robust analysis of canonical auctions such as the first-price auction for the welfare objective, prior-robust auction design for the revenue objective, and prior-robust design of exchange mechanisms for the gains-from-trade objective. Finally, the revelation principle is not without loss in robust mechanism design. The potential loss can be quantified by the revelation gap, the fraction of the optimal robust guarantee that is lost when restricting from all mechanisms to revelation mechanisms.

Thu 1 OctComputer Science and Game Theory
The gist
This paper looks at how to design auctions that perform well no matter what the conditions are. The authors focus on measuring the worst-case performance of auctions compared to the best possible auction for any environment. They explore different types of auctions and objectives like how well resources are used, how much money is made, and how gains from trade are maximized. The paper also shows that some design shortcuts, like using revelation mechanisms, can reduce auction robustness, and they introduce a way to measure this loss.
Open → 2610.01805v1