Papers for

online auction platforms

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 pricing strategies for intermediaries in repeated trade scenarios

Optimal Regret for Profit Maximization in Bilateral Trade

Abstract: Learning to profit from trade requires learning both sides of a market: what a seller is willing to accept and what a buyer is willing to pay. We study repeated bilateral trade, where an intermediary posts a purchase price to a seller and a sale price to a buyer whose valuations are drawn from an unknown joint distribution. Trade occurs only if both parties accept their respective prices, in which case the intermediary earns the difference between the two prices. The intermediary observes only whether trade occurs, without observing either valuation. We show that learning both sides of the market is no harder, in terms of regret, than learning just one. Specifically, we design an algorithm achieving regret $\widetilde{\mathcal{O}}(T^{2/3})$ against the best fixed pair of prices, matching, up to logarithmic factors, the classical lower bound for one-dimensional dynamic pricing. Our result shows that the classical one-dimensional regret rate survives the transition to two dimensions, raising the question of whether this absence of a curse of dimensionality extends to arbitrarily high dimensions.

Fri 6 NovComputer Science and Game TheoryMachine Learning
The gist
Setting prices for buying from sellers and selling to buyers can be tricky when you don’t know how much people value the items. This paper studies a situation where a middleman posts prices and only sees if trades happen, not the actual buyer or seller values. The authors show that learning the best prices on both sides is just as hard as learning on one side alone. They created an algorithm that nearly matches the best possible learning speed known for simpler one-sided cases, suggesting no extra difficulty in pricing both sides together.
Open → 2611.09558v1

Optimal algorithms achieve best ratios for matroid selection problems

As Easy as Rank One: Optimal Algorithms for Matroid Secretary and Single-Sample Matroid Prophet

Abstract: We resolve the matroid secretary conjecture in its strong form and the single-sample matroid prophet inequality problem, achieving competitive ratios $e$ and $2$, respectively. Both ratios are optimal, even for rank-one matroids. For matroid secretary, our ordinal algorithm accepts the elements of the canonical optimum independently, each with probability $1/e$. It needs only the number of elements in advance and uses an expected polynomial number of independence queries on arrived elements. For single-sample matroid prophet inequalities, our algorithm uses one sample per independent value distribution and $O(n^2)$ independence queries on a known $n$-element matroid. It works for every arrival order fixed independently of the samples, values, and algorithmic randomness. The selected elements and their values have exactly the joint distribution obtained by independently retaining each element--value pair in the canonical optimum of a fresh product draw with probability $1/2$. Our main algorithms maintain a reference state whose greedy solution contains every accepted element. Its updates, made even after rejections, preserve exact distributional invariants. A short reversible-update argument gives a $4$-probability-competitive secretary algorithm, already resolving the original conjecture; a related invariant gives the optimal single-sample prophet inequality. For secretary, we characterize the distributions achievable by ordinal algorithms through a finite polytope. A continuous-time formulation then lets us design an accepted-set distribution achieving the optimal ratio $e$ and realize it efficiently. We also obtain guarantees for matroid intersections.

Fri 6 NovData Structures and AlgorithmsComputer Science and Game Theory
The gist
This paper solves two long-standing problems about picking the best items under certain rules, called matroids. The authors found the best possible ways to choose elements online, achieving performance limits that can't be improved even in very simple cases. Their methods cleverly maintain a reference state so decisions are made fairly and efficiently, and work even without knowing the full problem in advance. These algorithms also work well when only limited information is available, like a single sample of item values.
Open → 2611.08869v1

Cryptographic methods ensure truthful auctions despite abort risks

Credible AUctions via MPC Gadgets: Bounding Information Leakage Under Abort

Abstract: The design of credible auctions---mechanisms where a revenue-maximizing auctioneer has no incentive to deviate from the protocol---faces a fundamental cryptographic barrier when the auctioneer controls shill bidders. While a natural approach is to use Secure Multi-Party Computation (MPC) to remove the trusted auctioneer, the impossibility of fair coin flipping of Cleve (1986) implies that monolithic MPC protocols grant the auctioneer a "free option": they can learn the auction's outcome and unilaterally abort if the revenue is unsatisfactory. Cryptographic commitments with ex-ante penalties mitigate this abort asymmetry, but no finite penalty suffices for heavy-tailed distributions. We circumvent this barrier by introducing the MPC Decomposition Principle. Rather than encrypting the entire mechanism, we use MPC strictly as an information-restriction tool. We isolate the winner determination problem into a minimal MPC gadget that computes and reveals the winner's identity but no payment information. This qualitative restriction mathematically bounds the information leaked upon an abort. By combining this gadget with sequential revelation and finite economic penalties, we design the Sequential Revelation Auction (SRA). We prove that bounding the information leakage strictly bounds the value of the free option, showing that a penalty of $k \geq \sum_{i=1}^n Rev(F_i)$ is sufficient for credibility, and tight: for equal-revenue distributions, every smaller penalty admits a profitable deviation. Using constant-round MPC, the SRA resolves an open question of Akbarpour and Li (2020) and Ferreira and Weinberg (2020) by providing a constant-round, incentive-compatible, revenue-optimal credible auction for all product distributions with vanishing revenue tails

Wed 23 SeptComputer Science and Game TheoryCryptography and Security
The gist
Traditional online auctions can be manipulated by the auctioneer, who might quit the process if the outcome is bad for them. The authors show that using secure computation only for deciding who wins, but not how much to pay, limits what information can be leaked if the auctioneer aborts. They combine this with penalties for aborting and revealing bids one step at a time to create an auction that is both truthful and discourages quitting early. Their method guarantees the auctioneer gains no advantage by deviating, under realistic conditions.
Open → 2609.27402v1

Two more sellers or buyers enable optimal trade in two-sided markets

The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets

Abstract: We study Bulow-Klemperer-style competition complexity in two-sided double auctions with $m$ unit-demand buyers drawn i.i.d. from $F_B$ and $n$ unit-supply sellers drawn i.i.d. from $F_S$. When $m \ge n$ and buyer valuations first-order stochastically dominate seller costs ($F_B \succeq_{\mathrm{FSD}} F_S$), we prove that recruiting just two additional sellers enables Seller Trade Reduction (STR), a prior-independent mechanism, to achieve expected Gains From Trade (GFT) at least the first-best GFT of the original market. When the buyer side is the smaller side of the market ($m \le n$), an analogous result holds for Buyer Trade Reduction with 2 additional buyers. This resolves open questions of Babaioff, Goldner, and Gonczarowski (SODA 2020) and Cai, Liaw, Mehta, and Zhao (STOC 2024). We complement our upper bound by showing that this uniform bound is optimal: already for $m = n = 1$, no prior-free mechanism (deterministic or randomized) that is dominant-strategy incentive-compatible, individually rational, and weakly budget-balanced can match the first-best GFT by recruiting only one additional seller.

Wed 23 SeptComputer Science and Game Theory
The gist
This paper studies trading between buyers and sellers, where each side has many participants with different values for goods. The researchers show that by adding just two extra participants on the smaller side, simple trading methods can achieve the best possible total gains from trade without knowing exact details about buyers or sellers. They also prove that adding only one extra participant is not enough to reach this optimal outcome. This answers previously open questions about how many extra participants are needed for effective trading mechanisms.
Open → 2609.27304v1

Improved learning strategy matches best possible regret rates

Optimal No-Regret Learning for Repeated Prophet Inequality

Abstract: We study repeated prophet inequalities under prefix feedback. In each of $T$ rounds, a learner encounters fresh values drawn independently from $n$ boxes with unknown $[0,1]$-supported distributions in a fixed order and must irrevocably accept one, observing only the prefix up to its stopping box. Regret is measured against the optimal stopping policy that knows the distributions. We give an efficient algorithm achieving $\widetilde O(\sqrt{T})$ expected regret, matching the lower bound up to logarithmic factors. Our algorithm explores directly through near-optimal policies, combining empirical backward induction with box-specific reach bonuses. A relative-drop aggregation rule then exploits the nesting structure of observed prefixes to preserve exploration, thereby removing the polynomial dependence on the box number $n$. This resolves an open question posed by Liu et al. (2025).

Sun 20 SeptMachine Learning
The gist
This paper looks at a situation where someone must make a single choice from a sequence of unknown options one after another, but only sees values up to the point they stop. The authors develop a strategy to learn the best way to make these choices over many rounds, doing almost as well as if they knew all the chances ahead of time. They create an efficient method that learns quickly without needing to try every option too often. Their approach answers a question from recent research about how to do this learning well when there are many options.
Open → 2609.23265v1