CS Paper Radar

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

Jihun Kim, Pan-Yang Su, Maria G. Mendoza, Victoria Marie Tuck, Chinmay Maheshwari, S. Shankar Sastry

cs.GT cs.MA ·submitted 2026-10-15 21:53 UTC · v1
hot direction

Abstract

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.

Comment
12 pages, 4 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Extending Mechanisms

cs.GT econ.TH ·2026-10-20 ·Sergiu Hart, Noam Nisan
similarity 0.64
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.

0.12

Pacing Equilibria in Abstract Mechanisms

cs.GT ·2026-09-23 ·Salam Afiouni, Christian Kroer
benchmarktheory similarity 0.63
Abstract

Digital platforms increasingly rely on automated budget-management systems to regulate participation across allocation opportunities. A common tool is multiplicative pacing, which scales buyers' bids so that campaign-level budgets are spent gradually. Although pacing is operationally simple, its aggregate behavior depends on the underlying mechanism. In first-price single-item auction markets, pacing enjoys strong structural and computational properties that often fail in second-price auctions. It is unclear whether these properties extend to richer platform mechanisms. We develop a unified theory of pacing equilibria across a hierarchy of mechanisms. We first show that, even in first-price position auctions, the market-equilibrium interpretation of the single-item benchmark can fail. We then identify bid-maximizing pay-your-bid mechanisms as a broad class in which pacing equilibria exist, are unique, and admit an Eisenberg-Gale-type convex-program characterization. This implies efficient computation, Pareto-efficiency, and liquid-welfare guarantees, enabling pacing integration into large-scale optimization-based allocation routines. Finally, for abstract mechanisms satisfying a payment monotonicity condition, we prove equilibrium existence by smoothing discontinuities. With additional conditions and appropriate tie-breaking, we obtain uniqueness, revenue maximality among budget-feasible pacing vectors, and shill-proof implementability, and provide convergent budget-adjustment dynamics for approximate equilibria. Overall, many favorable properties of first-price pacing extend beyond single-item auctions under appropriate mechanism-level conditions.

0.29

Generalized Prophet Inequalities for Online Auctions

cs.GT ·2026-09-30 ·Twan Kroll, Rebecca Reiffenhäuser
similarity 0.62
Abstract

Prophet Inequalities for online auctions, as many classical auction settings, traditionally consider agents who strive to maximize quasi-linear utility, i.e. their obtained value minus the price paid. This simplified view of the agents' objectives does not capture real-world settings where agents are almost always constrained by budgets, and can have different objectives altogether (e.g., very prominently, value maximizers in autobidding). We generalize classic prophet inequality auction settings to accommodate unknown, varying types of agent objectives and budgets, modeling them as stochastic input similar to the traditional valuation distributions. In this new model, we analyze (anonymous) posted-price mechanisms, one main category of which are the balanced prices central to many auction results in the prophet inequality model. We demonstrate both the resilience and limits of balanced price mechanisms for generalized prophet inequalities with stochastic agent objectives, budgets and valuations: our generalization of the balanced prices framework incorporates budget constraints and mixed objectives. We show constant competitive ratios for some the most central settings, spanning all the way up to agents with subadditive valuation functions. On the way, we establish trade-offs between competitive ratio and agents' price-sensitivity, and give a general reduction from the budgeted setting to budget-free value maximizers.

0.17

Fair Selection of Generalized Nash Equilibria: A Comparability Perspective

cs.GT eess.SYmath.OC ·2026-11-06 ·Sophie Hall, Heinrich H. Nax, Saverio Bolognani
published similarity 0.62
Abstract · Book chapter, 25 pages, 4 figures. To appear in Socio-Inspired and Socially Aware Control for Complex Systems, Springer

Generalized Nash equilibrium (GNE) problems model self-interested agents coupled through their costs and shared constraints, and arise throughout control applications that allocate a scarce common resource. Such problems typically admit a continuum of equilibria, so any implementation must \emph{select} one. This selection is not neutral: it decides how the cost of the shared constraint is distributed among the agents, a decision often expected to be fair. The variational GNE (v-GNE), which charges all agents a uniform shadow price, is the conventional choice and is frequently advocated as fair. Through the lens of \emph{comparability} from social choice theory, we show that the GNE set itself requires no inter-agent comparability of costs, whereas the v-GNE implicitly assumes cardinal unit comparability, one of the stronger notions. We then introduce the fair GNE (f-GNE), which selects an equilibrium by explicitly optimizing a fairness metric matched to the comparability at hand, and give constructive routes to compute it for single-constraint and linear-quadratic games. An electric-vehicle charging game serves as a running example throughout this self-contained tutorial.

0.53

Inter-Temporal Price Constraints in Dynamic Pricing: Performance Guarantees Under Price Monotonicity and Promotion Fatigue

cs.DM math.OC ·2026-09-23 ·Weiyuan Li, Paat Rusmevichientong, Huseyin Topaloglu
similarity 0.61
Abstract · 31 pages in main text, 14 pages in appendix, 1 figure

We study dynamic pricing problems under inter-temporal price constraints. We have resources with limited capacities. At each time period, we decide which products to make available and what prices to charge for the available products. The sale probability for a product depends on its price. If we make a sale for a product, then we collect a revenue reflecting the price and consume the capacities of a combination of resources. We work with two types of inter-temporal constraints. In price monotonicity, the prices charged for a product at different time periods have to be monotone. In promotion fatigue, we can discount a product at most once over each time interval of a fixed length. Computing the optimal policy is intractable. We use fluid approximations to construct policies. Traditionally, policies from fluid approximations make randomized decisions at each time period by following an optimal solution to the fluid approximation, but such randomized decisions easily violate price monotonicity or promotion fatigue constraints. We develop policies that sample price paths according to an optimal solution to the fluid approximation, while satisfying the inter-temporal constraints. Letting $c_{\min}$ be the smallest initial capacity of a resource and $L$ be the maximum number of resources used by a product, our policies have a performance guarantee of $\max\Big\{ \frac{1}{8L}, \, \frac{1}{2} - \sqrt{\frac{\log c_{\min}}{2 \,c_{\min}}} - \frac{L}{c_{\min}}\Big\}$. Thus, under large resource capacities, our policies are guaranteed to obtain at least half of the optimal total expected revenue. The latter performance guarantee is tight in the sense that no policy can, in general, obtain more than half of the optimal objective value of the fluid approximation even under large resource capacities. We unify our approach to open the path for extensions to other inter-temporal price constraints.

0.31

Balanced Posted Prices in Stationary Two-Sided Markets

cs.GT ·2026-10-22 ·Ilan Reuven Cohen
benchmark similarity 0.61
Abstract · 30 pages

We study an intermediary that buys nonperishing items from arriving sellers and sells them to arriving buyers, subject to limited storage. Sellers and buyers arrive according to independent Poisson processes. The intermediary pays and charges the same fixed item prices, aiming to maximize long-run gains from trade: buyer value minus seller cost. Our benchmark may choose allocations directly, has unlimited storage, and must purchase each unit before allocating it. Its optimal long-run gain rate equals the value of a linear program of average purchase and allocation rates, with or without knowledge of future arrivals. For buyers whose bundle values are maxima of nonnegative additive valuations (XOS), we compute static common prices that guarantee half of this benchmark for arbitrary finite item capacities, even one storage slot per item, regardless of how ties are resolved without using future arrivals. The prices are computable in polynomial time using demand and supporting-value queries. The construction equalizes itemwise lower bounds on buyer and seller contributions to gains from trade, accounting for procurement costs. We call this contribution balance. As a single-item foundation, we also equalize the rates of purchases and sales selected by the price, before checking inventory availability. We call this rate balance. For capacity $C$, it yields the tight guarantee $C/(C+1)$. The two principles parallel proofs of the classical prophet inequality based on half the expected benchmark and on a median threshold, adapting these balancing ideas to recurring two-sided markets with limited inventory.

0.13

Fair Allocation with Optional Selling

cs.GT econ.TH ·2026-08-25 ·Uriel Feige, Yotam Gafni
similarity 0.61
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 Online Learning in Bilateral Trade Through Interest

cs.GT ·2026-11-01 ·Mengfan Ma, Haoyu Song, Yiran Tong
similarity 0.61
Abstract · 52 pages, 5 figures

We consider online learning in bilateral trade on platforms such as Uber, Airbnb, and eBay. In each round, a platform posts a payment to a seller and a price to a buyer, both with private valuations, and observes only whether trade occurs. Its objective is to maximize cumulative gains-from-trade, the sum of the differences between buyers' and sellers' valuations across completed trades. We measure the platform's performance by its regret against the best fixed common price. Financial self-sufficiency motivates global budget balance (Bernasconi et al., 2024), which allows profits from some trades to subsidize others, provided that the final balance is nonnegative. Such financial planning should also account for the time value of money: profits earned earlier can accumulate interest, providing additional funds for future subsidies. Motivated by this observation, we introduce global budget balance with interest, under which a platform starting with no funds can use both trading profits and accrued interest to finance subsidies. For a horizon of $T$ rounds and a fixed exponent $θ\ge0$, we consider the per-round interest rate $r_T = T^{-θ}$. We study two classic valuation models, adversarial and correlated i.i.d., and obtain tight bounds on regret against the best fixed common price in both. As the interest rate grows, optimal regret in each model drops from $\tildeΘ(T^{3/4})$ to $\tildeΘ(T^{5/7})$. The intermediate rates differ: $\tildeΘ(T^{3θ/4})$ for adversarial valuations when $20/21 < θ< 1$, and $\tildeΘ(T^{(2θ+3)/7})$ for correlated i.i.d. valuations when $1 < θ< 9/8$. Finally, as an extension, we study $α$-regret, with approximation factor $α\ge1$, for adversarial valuations against the best feasible distribution over price pairs, and show that the optimal competitive ratio rises from 2 to 3 as interest strengthens.

0.36