CS Paper Radar

Extending Mechanisms

Sergiu Hart, Noam Nisan

cs.GT econ.TH ·submitted 2026-10-20 08:26 UTC · v1

Abstract

Given an incentive-compatible mechanism for a single agent on a restricted domain of valuations, we consider its incentive-compatible extensions to the entire valuation space. We identify two extreme extensions: the "keep-the-menu" extension, which minimizes buyer payoffs and maximizes canonical prices pointwise, and the "keep-the-pricing" extension, which maximizes buyer payoffs and minimizes canonical prices pointwise.

Closest papers

Nearest neighbours by meaning across the whole index.

Pairwise Maximin Share Allocations Need Not Exist

cs.GT ·2026-09-05 ·Haris Aziz
similarity 0.68
Abstract

We study the fair allocation of indivisible goods among agents with strictly positive additive valuations. Pairwise maximin share fairness (PMMS) asks that, for every ordered pair of agents, the first agent value her own bundle at least as highly as the best worst-case share she could secure by repartitioning the two agents' combined bundles into two parts. Whether a PMMS allocation always exists for positive additive valuations has remained open since the notion was introduced. We resolve this question in the negative. We construct an instance with four agents and strictly positive additive valuations that admits no complete PMMS allocation.

0.43

Auction Design with ROI-Constrained Bidders: Truthfulness and Revenue Maximization

cs.GT econ.TH ·2026-09-15 ·Zhiqiang Zhuang, Quan Yu, Yisong Wang, Kewen Wang, Zhe Wang
theory similarity 0.66
Abstract

The return-on-investment (ROI) constraint is central to many auctions, particularly in online advertising, where a bidder is unwilling to pay more than a fixed fraction of the value obtained. We study truthful and revenue-maximizing auctions for ROI-constrained bidders. We first characterize truthful auctions when both valuations and ROI constraints are private, showing that the allocation rule uniquely determines the payment rule. Building on this characterization, for multiple bidders we introduce $σ$-increment mechanisms that resemble Myerson's optimal mechanism~\cite{journals/mor/Myerson81}; as $σ$ vanishes, these mechanisms become asymptotically optimal among deterministic truthful mechanisms, and their revenue approaches at least a $1/\bar r$ fraction of the optimal expected revenue over all truthful mechanisms, where $\bar r$ is the largest possible ROI constraint. In the single-bidder setting, we prove that every truthful auction can be replaced by a convex pricing function with weakly higher payments for every type, and we derive the optimal pricing functions when either the valuation or the ROI constraint is public.

0.21

Maximin Share Allocations Beyond Weakly Lexicographic Valuations

cs.GT ·2026-09-12 ·Nicholas Teh
theory similarity 0.65
Abstract

We study the fair division of indivisible goods among agents with nonnegative additive valuations. An agent's maximin share (MMS) is the value she can guarantee by partitioning the goods into as many bundles as there are agents and receiving a least-valued bundle. We prove the existence of exact MMS allocations for a valuation domain that generalizes several few-valued domains as well as weakly lexicographic valuations. For each agent, the lower-valued goods, after a positive rescaling, may take values in $\{0,1,d,d+1\}$, $\{0,1,2,2e\}$, or $\{0,1,2,3,4\}$, where $d,e\ge 2$ are integers. Above these goods, the valuation may contain arbitrarily many value classes, subject to the condition that a single good in each class is worth at least the total value of all strictly lower-valued goods. The value classes, scaling factors, and parameters may vary across agents. We give an algorithm that computes an MMS allocation in $O(nm\log^2(2+m))$ time, where $n$ is the number of agents and $m$ is the number of goods.

0.34

Dynamic Auction Mechanisms in a Closed-Credit Economy: Sequential Slot Reallocation in Air Traffic Management

cs.GT cs.MA ·2026-10-15 ·Jihun Kim, Pan-Yang Su, Maria G. Mendoza, Victoria Marie Tuck, Chinmay Maheshwari +1 more
hot direction similarity 0.64
Abstract · 12 pages, 4 figures

Indivisible resources allocated in advance may need to be reallocated when capacity reductions make existing assignments infeasible, yet monetary compensation is often impractical or undesirable. We develop a sequential resource reallocation scheme using reusable artificial credits, where agents hold pre-existing resource rights and have heterogeneous marginal valuations over time blocks. Capacity reductions produce fractional endowments, which our closed-credit scheme resolves into indivisible final allocations. We model agents' intertemporal preferences through a predicted-value-to-go function and characterize conditions ensuring that their optimal demand is non-increasing in price. We propose an ascending-auction mechanism that partitions agents into subgroups and uses the minimum subgroup market-clearing price as a common transaction price. We show that the mechanism preserves non-myopic individual rationality and weak nontrader neutrality. Moreover, we establish Pareto efficiency under optimal-demand clearing in the unified market and bound the expected gain from misreporting by the probability that an agent changes the common price. Simulations of airport slot reallocation demonstrate reductions in total modeled delay and cancellation costs relative to a ground-delay baseline.

0.38

Exact MMS Allocations under Personalized Bivalued Valuations: Goods and Chores

cs.GT cs.DS ·2026-08-16 ·Yuhao Zhang
benchmarktheory similarity 0.64
Abstract

The maximin share (MMS) is a central fairness benchmark for allocating indivisible goods and chores. We study additive valuations in the personalized bivalued setting, where each agent assigns one of two agent-specific values to every item. Whether exact MMS allocations always exist in this setting has remained a major open question, as highlighted by Ebadian, Peters, and Shah and by Garg, Huang, and Segal-Halevi. We answer this question affirmatively: we prove that exact MMS allocations always exist for both goods and chores and can be computed in polynomial time. Our proof combines a quota-based reformulation with an envelope relaxation, a sparse extreme-point construction, and flow-based rounding that controls the total rounding loss.

0.40

Fair Allocation with Optional Selling

cs.GT econ.TH ·2026-08-25 ·Uriel Feige, Yotam Gafni
similarity 0.63
Abstract

We consider fair allocation of indivisible goods in a setting in which agents have subjective valuation functions over the set of goods, and in addition, goods may be sold at given market prices. In this setting, a fair allocation involves {deciding which goods to sell, how to allocate the unsold goods, and how to divide the money received from the sold goods.} We adapt to this setting the definitions of share-based fairness notions, such as the maximin share (MMS) and the truncated proportional share (TPS), and comparison-based fairness notions such as EF1 and EFX (which we adapt to SEF1 and SEFX). We show the following results when the utility of each agent is additive both over goods and over money. With two agents, there are allocations that are simultaneously MMS and SEFX. With three agents, there are instances in which no allocation gives every agent more than $\frac{11}{12}$-MMS. With any number of agents, there are $\frac{2}{3}$-MMS allocations. There also are allocations that are simultaneously SEFX and $\frac{n}{2n-1}$-TPS. This latter ratio is best possible, even without the SEFX requirement.

0.32

Optimal Multi-Item Auctions with I.I.D. Values

cs.GT ·2026-10-08 ·Boyu Liu, Zhengyang Liu, Zihe Wang
similarity 0.62
Abstract · 51 pages, 1 table

We study revenue-maximizing multi-item auctions under dominant-strategy incentive compatibility (DSIC) and ex-post individual rationality. Buyers have additive valuations, and all item values are independent draws from a common finite distribution. For every two-point distribution and arbitrary numbers of buyers and items, we give an explicit deterministic mechanism that is optimal among all randomized mechanisms satisfying these requirements, together with a polynomial-time algorithm for computing the optimal expected revenue. For general finite-support distributions, computing the exact optimal revenue is $\#\mathrm P$-hard, both for a single buyer with an arbitrary number of items and for two items with an arbitrary number of buyers. For a single buyer, we also establish hardness of computing an optimal mechanism. Building on prior work, we also obtain exact and approximate algorithms under different parameter restrictions. Exact polynomial-time optimization is possible whenever any two of the buyer count, item count, and support size are fixed. When only the item count is fixed, a polynomial-time approximation scheme constructs a mechanism with expected revenue at least a $1-\varepsilon$ fraction of the optimum for every fixed $0<\varepsilon<1$. All these algorithms satisfy DSIC and ex-post individual rationality.

0.21

Price of Anarchy of First-Price Auctions in Agentic Markets

cs.GT cs.AIcs.LG ·2026-10-14 ·Shubhendu Trivedi, Jacob Eisenstein, Alekh Agarwal, Ian Gemp, Michael Kaisers +1 more
position similarity 0.62
Abstract · 40 pages

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.

0.34