Papers for

auction platform developers

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.

Improving fair share guarantees for complex value settings in item division

Toward Constant-Factor Maximin Share Guarantees for Subadditive Valuations

Abstract: For $n$ agents and $m$ indivisible goods, an agent's maximin share (MMS) is the largest minimum bundle value she can obtain by partitioning the goods into $n$ bundles. Constant MMS approximations are known for additive, submodular, or XOS valuations, but whether such a guarantee exists for general subadditive valuations remains open. We advance this question in two directions. For general subadditive valuations, we exponentially improve the guarantee from $Ω(1/\log\log n)$ to $Ω(1/\log^* n)$, where $\log^* n$ is the iterated logarithm. We then seek constant MMS guarantees under additional structure on subadditive valuations by studying $q$-partitioning valuations: every partition of a bundle into at most $q$ groups admits nonnegative group prices that sum to the bundle's value and whose sum on any collection of groups is at most the value of their union. This hierarchy ranges from subadditivity at $q=2$ to XOS for $q\ge m$. We give the first study of MMS in the intermediate classes and prove constant guarantees whenever $q/n$ has a fixed positive lower bound, including $1/6$ for $q\ge n$ and $1/4$ for $q\ge2n$. For XOS valuations, we further improve the universal guarantee from $4/17\approx 0.2353$ to $5/16=0.3125$. For subadditive valuations, we prove a bidding amplification theorem that gives an exponential bound on each agent's probability of receiving less than half her MMS, while satisfying her budget in every outcome. For $q$-partitioning valuations, we give a scalar criterion that converts bounds on the value lost from disjoint deletions within a bundle into bounds on potential losses, even when an agent contributes zero below the target bundle value. For XOS valuations, we prove a reservation theorem that selects goods for integral assignment together with auxiliary additive valuations and accounts for the loss in rounding.

Tue 3 NovComputer Science and Game Theory
The gist
Dividing items fairly among many people is hard when everyone's value for groups of items isn't simple to add up. This paper improves how close we can get to a fair share for each person in very complex situations, making it much better than before. The authors break down complex value systems into levels and show constant fair share guarantees for several of these, including some where previous results didn't exist. They also develop new technical tools that make these guarantees stronger and more reliable.
Open → 2611.05073v1

Local certificates replace monotonicity in learning first-price auctions

Coercive at the equilibrium, monotone nowhere: exact convergence certificates for learning in first-price auctions

Abstract: The Bayes-Nash equilibria of an auction are the solutions of a variational inequality, and for standard auctions its operator fails every monotonicity notion, so the theory of monotone operators is unavailable to learning in auctions. We show what replaces monotonicity for the first-price auction: a certificate that is strong but local. For uniform values the single-population operator has an exact closed form and an exact Minty identity at the equilibrium; for two bidders its Gateaux derivative there is $L^2$-coercive with best constant exactly one in every piecewise-linear bid space with $m$ pieces, while the Minty inequality holds only on a ball whose radius decays like $m^{-5/2}$. The decay is exact: $m^{5/2}$ times the radius converges to $1/(8 \cdot 3^{1/4})$, and the worst perturbations converge to an alternating geometric profile with ratio $-(2-\sqrt{3})$. Refinement shrinks the ball, not the constant; independent learners see the same constant. For a general prior and bidder count there are two certificates, at the true equilibrium and at the equilibrium of the finite-dimensional bid space a learning algorithm runs in. The first is an explicit weight $w_F$, positive for every log-concave prior, equal to the second exactly for the value distributions $F(v)=v^a$. Otherwise the learners' certificate differs by knot masses, because the discretized equilibrium's slopes oscillate with a law proved for two and three bidders, and for four under a computer-verified bottom layer. The limit of the learners' certificate is proved in closed form, a function of the prior alone, and characterizes positivity: positive uniformly in $m$ in the limit exactly when that minimum is positive, with a known rate; for one prior at every $m$ by interval arithmetic. For more bidders the limit is conjectured. The exact identities and leading-order inequalities are machine-checked in Lean.

Tue 3 NovComputer Science and Game Theory
The gist
Learning strategies in first-price auctions is difficult because the usual math tools, built on a property called monotonicity, do not apply. The authors found a new type of certificate, a local but strong condition, that holds exactly at auction equilibria and helps understand learning behavior. They provide explicit formulas and machine-verified proofs to show how this certificate behaves depending on the number of bidders and bid discretization. This work helps explain how learning algorithms perform when bidding strategies are refined, even though the usual mathematical assumptions fail.
Open → 2611.04545v1

Graph neural networks improve public infrastructure auction design

Differentiable Combinatorial Auction Design: Optimizing Revenue-Welfare-Fairness Frontiers With Graph Attention Networks

Abstract: Designing optimal auctions for allocating public infrastructure-such as airport slots and energy resources-is challenging due to interdependent resources and complex side-constraints. While the Vickrey-Clarke-Groves (VCG) auction guarantees maximum welfare, it cannot maximize revenue or accommodate the multi-objective trade-offs inherent in public infrastructure systems. We propose a differentiable, constraint-aware framework for combinatorial auction design that enables end-to-end learning of fractionally feasible, approximately strategy-proof mechanisms. Our primary contribution is a combinatorial constraint enforcement technique that ensures fractional feasibility by construction, bypassing the need for penalty-based approximations. We introduce CAGraph, a novel graph-based architecture designed to capture dependencies between items and bidders, alongside CANet and CAFormer as deep learning baselines, for combinatorial settings. We also provide a Matching Pursuit-inspired decomposition that maps fractional allocations to feasible discrete allocations and empirically evaluates the resulting discretization gap. In synthetic benchmarks and an airport slot-divestiture case study, respectively, the learned mechanisms achieve up to 73.5% and 180% higher expected revenue than VCG, under small empirical regret. Finally, we visualize the Pareto frontiers for revenue, welfare, and fairness, providing regulators with a decision-support tool to design infrastructure auctions that balance profitability, efficiency and equity.

Thu 22 OctComputer Science and Game Theory
The gist
Public infrastructure like airport slots needs to be allocated fairly and efficiently, but designing auctions for this is very complex. The authors created a new method using graph-based neural networks to design auctions that better balance revenue, fairness, and overall benefit. Their system learns auction rules that follow rules exactly and are hard to cheat. In tests, their approach raised expected revenue much higher than traditional methods and helps regulators see trade-offs clearly.
Open → 2610.31977v1

Communication limits challenge truthful combinatorial auction designs

The Hardness of Dominant Strategy Mechanism Design, Revisited

Abstract: We study the communication complexity of \emph{dominant-strategy incentive-compatible} (DSIC) mechanisms for combinatorial auctions. For $γ\in [\log m, m]$, let $\mathsf{DSIC_{GEN}}(m, γ)$, $\mathsf{DSIC_{XOS}}(m, γ)$, and $\mathsf{DSIC_{GS}}(m, γ)$ denote the best approximation ratio attainable by a deterministic, individually rational, no-negative-transfers, DSIC mechanism using at most $2^γ$ communication over $m$ items, for general monotone, XOS, and gross substitutes (GS) valuations, respectively. We give a unified proof that shows $\mathsf{DSIC_{GEN}}(m, γ) = Ω(m/γ)$, $\mathsf{DSIC_{XOS}}(m, γ) = Ω((m/γ)^{1/5})$, and $\mathsf{DSIC_{GS}}(m, γ) = Ω((m/γ)^{1/7})$. The GS lower bound answers an open question of~\cite{DobzinskiRV22}: although poly-communication welfare maximization for GS valuations admits a poly-communication deterministic truthful mechanism via VCG, no good approximation is possible in poly-communication for deterministic DSIC mechanisms. Additionally, the general lower bound establishes that $\mathsf{DSIC_{GEN}}(m, γ) = Θ(m/γ)$ due to the deterministic DSIC $O(m/γ)$-approximation of~\cite{QiuW24}. We also obtain several results in the two-bidder setting. We show that attaining a $1.0001$-approximation for two weighted matroid-rank valuations (a subclass of GS) with a universally DSIC mechanism requires exponential communication. On the other hand, we give a poly-communication $(1+\sqrt{5})/2 \approx 1.618$-approximation for two submodular bidders using a universally DSIC mechanism. Prior to this work, it was not known whether even a poly-communication universally truthful mechanism could beat a $2$-approximation for two submodular valuations, nor whether a poly-communication universally DSIC mechanism could beat a $2$-approximation for two weighted matroid rank valuations.

Mon 5 OctComputer Science and Game Theory
The gist
This paper looks at how hard it is for auction systems to guarantee honest bidding when selling many items at once. The authors show that if the auction tries to communicate efficiently while ensuring honesty, it cannot achieve very good results, especially in complex cases. They prove that even for special types of bidder preferences, improving accuracy requires a lot of communication. They also give new examples demonstrating these limits in simple two-bidder auctions.
Open → 2610.06773v1

Improved worst case efficiency bound for random trade offers

An Improved Upper Bound for the Random-Offerer Mechanism in Bilateral Trade via Recursive Hard Instances

Abstract: We study the worst-case efficiency of the random-offerer mechanism in bilateral trade relative to the first-best gains from trade. We construct a family of independent buyer value and seller cost distributions whose ratio converges to $0.436943488\ldots$, improving the previous upper bound of $0.460242308\ldots$. Our construction combines recursively nested seller distributions with downward transport of buyer values. The recursive structure allows contributions from different scales to accumulate, leading to stronger hard instances. We analyze this construction through a recurrence and obtain an analytic characterization of the limiting constant.

Mon 5 OctComputer Science and Game Theory
The gist
The paper studies how efficient a simple trade method is when a buyer and seller randomly decide offers. The authors find new worst-case examples showing the method performs a bit worse than previously known, improving the known limit from about 46% to about 44%. They build tricky value and cost scenarios using a repeating pattern to make the efficiency drop. This helps better understand the limitations of random offer trading mechanisms.
Open → 2610.06547v1

Strongly polynomial algorithm solves auctions with budget limits and costs

Solving the Arctic Product-Mix Auction

Abstract: Arctic product-mix auctions allow budget-constrained bidders to express preferences over multiple substitute goods. We give the first strongly polynomial algorithm to find the competitive equilibria when the auctioneer has separable convex piecewise-linear costs. It combines a strongly polynomial reduction to the costless Arctic auction with an existing strongly polynomial algorithm for costless Arctic auctions. We also give a polynomial-time Turing reduction from costless Arctic auctions to linear Fisher markets, and a strongly polynomial many-to-one reduction to linear Arrow-Debreu exchange markets. If a good is sold in positive quantity in two competitive equilibria, its price is the same in both.

Mon 28 SeptComputer Science and Game Theory
The gist
Auctions often need to manage bidders who have budgets and want multiple similar goods. This paper presents the first efficient method to find stable prices and allocations in auctions where the seller has certain cost structures. The authors connect this problem to other well-studied market models, showing relationships between them. They also prove that if a good is sold in more than one stable outcome, its price remains consistent.
Open → 2609.36346v1