Latency-Aware Resource Allocation over Heterogeneous Networks: A Lorentz-Invariant Market Mechanism

Saad Alqithami

cs.GTApr 4, 2026

Latency-Aware Resource Allocation over Heterogeneous Networks: A Lorentz-Invariant Market Mechanism

Authors: Saad Alqithami

Abstract

We present a telecom-native auction mechanism for allocating bandwidth and time slots across heterogeneous-delay networks, ranging from low-Earth-orbit (LEO) satellite constellations to delay-tolerant deep-space relays. The Lorentz-Invariant Auction (LIA) treats bids as spacetime events and reweights reported values based on the horizon slack, a causal quantity derived from the earliest-arrival times relative to a public clearing horizon. Unlike other delay-equalization rules, LIA combines a causal-ordering formulation, a uniquely exponential slack correction implied by a semigroup-style invariance axiom, and a critical-value implementation that ensures truthful reported values once slacks are fixed by trusted infrastructure. We analyze the incentive result in the exogenous-slack regime and separately examine bounded slack-estimation error and endogenous-delay limitations. Under fixed feasible slacks, LIA is individually rational and achieves welfare at least $e^{-λΔ}$ relative to the optimal feasible allocation, where $Δ$ is the slack spread. We evaluate LIA on STARLINK-200, INTERNET-100, and DSN-30 across 52,500 baseline instances with market sizes $n\in\{10,20,30,40,50\}$ and conduct additional robustness sweeps. On Starlink and Internet, LIA maintains near-efficiency while eliminating measured timing rents. However, on DSN, welfare is lower in thin markets but improves with depth. We also distinguish winner-determination time from the background cost of maintaining slack estimates and study robustness beyond independent and identically distributed (iid) noise through error-spread bounds and structured (distance-biased and subnetwork-correlated) noise models. These results suggest that causal-consistent mechanism design offers a practical non-buffering alternative to synchronized delay equalization in heterogeneous telecom infrastructures.

Figures & tables

Panel of Figure 1 — Figure 1: Spacetime view of two bids. Dashed lines are light-cone boundaries under unit aspect ( $c{=}1$ ). The shaded rectangle marks a causal slab where bids are incomparable; the red line is the frontier where horizon-discounted bids are compared (i.e., where $\theta_{1}e^{-\lambda\delta_{1}}=\theta_{2}e^{-\lambda\delta_{2}}$ ). Its position depends on the values $(\theta_{1},\theta_{2})$ , the parameter $\lambda$ , and how each bid’s horizon slack $\delta_{i}$ changes with emission time. Proper-time lapses $\delta_{i}$ (horizon slacks) are measured along each worldline from emission to the clearing horizon $H$ , with $\delta_{i}\equiv\Delta\tau_{i}$ .

Design family	Core idea	Artificial waiting?	Global schedule?	Per-bid causal slack?	Value-DSIC with fixed delay weights?	Typical limitation in heterogeneous networks
Frequent batch auctions	Periodic clearing on a public batch clock	Yes	Yes	No	Yes	Fairness improves only by buffering; batch size directly increases waiting
Speed bumps / HoldBack	Delay early arrivals to equalize access	Yes	Usually yes	No	Yes	Requires trusted delay equalization and can impose unnecessary holdback
Common-deadline normalization	Wait until a public horizon and clear on raw values	Yes	Yes	No	Yes	Eliminates order advantage only by delaying everyone to the deadline
Asynchronous / distributed auctions	Clear under partial arrivals or replicated logs	Low / variable	Not necessarily	Usually no	Case specific	Often preserves residual propagation advantage or sacrifices simple truthfulness
LIA	Clear at a public horizon using value weighted by horizon slack from earliest arrival	No extra holdback	Public horizon, but no synchronized buffering	Yes	Yes, conditional on fixed exogenous slacks	Requires trusted or bounded-error slack estimates; endogenous slack lies outside the single-parameter theorem

Table 1: Positioning LIA relative to other latency-fairness design classes.

Symbol	Meaning
$\tau_{H}$	Clearing horizon time on the auctioneer worldline $\gamma_{H}$
$T_{H}(v,\tau)$	True earliest-arrival time at $H$ for a bid event $(v,\tau)$
$\hat{T}_{H}(v,\tau)$	Estimated earliest-arrival time used by the controller in deployment
$\delta_{i}$	Horizon slack for bidder $i$ , $\delta_{i}:=\tau_{H}-T_{H}(v_{i},\tau_{i})$
$\hat{\delta}_{i}$	Estimated slack, $\hat{\delta}_{i}:=\tau_{H}-\hat{T}_{H}(v_{i},\tau_{i})$
$\lambda$	Discount rate (units $\text{time}^{-1}$ ) used in $e^{-\lambda\delta_{i}}$

Table 2: Notation summary.

Function $D(\delta)$	Boundary	Monotonicity	Composition
	$D(0)=1$	$D^{\prime}(\delta)<0$	$D(\delta_{1}+\delta_{2})=D(\delta_{1})D(\delta_{2})$
Linear: $1-\lambda\delta$	✓	✓	Fails
Rational: $1/(1+\lambda\delta)$	✓	✓	Fails
Polynomial: $(1-\lambda\delta)^{k}$	✓	✓	Fails
Exponential: $e^{-\lambda\delta}$	✓	✓	✓

Table 3: Comparison of candidate discount functions

D(\delta)

against required axioms. Only the exponential form satisfies all requirements for a causal-consistent pricing rule.

Operation	Asymptotic cost	Dominant primitive
Slack-map refresh (static snapshot)	$O(\|E\|\log\|V\|)$	Reverse-graph Dijkstra / shortest paths
Slack-map refresh (time varying)	Controller dependent	Time-dependent earliest-arrival or periodic recomputation
Per-bid slack lookup	$O(1)$	Array / hash lookup in cached slack map
Winner & payment computation	$O(n)$	Single pass over discounted bids
Audit logging	$O(n)$	Persist values, slacks, winner, payment

Table 4: Complexity decomposition for deployment.

Topology	$\Delta$ p50 (ms)	$\Delta$ p95 (ms)	Mean feasible fraction
STARLINK-200	$50.98$	$61.61$	$0.949$
INTERNET-100	$13.15$	$15.35$	$0.950$
DSN-30	$1.16\text{\times}{10}^{6}$	$1.19\text{\times}{10}^{6}$	$0.931$

Table 5: Observed slack-spread summaries at

n=50

under the paper’s horizon policy (1,000 sampled instances per topology).

Topology	Mechanism	$\mathrm{SW}/\text{OPT}_{\mathrm{all}}$	$\mathrm{Rev}/\text{OPT}_{\mathrm{all}}$	Compute (ms)	Clearing latency (ms)
STARLINK-200	Sync-VCG	$0.999958$ [ $0.999937$ , $0.999975$ ]	$0.998932$ [ $0.998865$ , $0.998996$ ]	$0.0942143$ [ $0.0934602$ , $0.0949781$ ]	$69.544$ [ $69.5432$ , $69.5448$ ]
	HoldBack	$0.999958$ [ $0.999937$ , $0.999975$ ]	$0.998932$ [ $0.998865$ , $0.998996$ ]	$0.0575046$ [ $0.0570964$ , $0.0579745$ ]	$69.5073$ [ $69.5068$ , $69.5078$ ]
	LIA ( $\lambda{=}0.25\,\mathrm{s}^{-1}$ )	$0.999322$ [ $0.999254$ , $0.999388$ ]	$0.997625$ [ $0.997523$ , $0.997726$ ]	$0.186934$ [ $0.185626$ , $0.188752$ ]	$69.634$ [ $69.6327$ , $69.6358$ ]
	LIA ( $\lambda{=}0.5\,\mathrm{s}^{-1}$ )	$0.998741$ [ $0.998635$ , $0.998841$ ]	$0.996526$ [ $0.996384$ , $0.996664$ ]	$0.185737$ [ $0.184899$ , $0.186586$ ]	$69.6328$ [ $69.6319$ , $69.6337$ ]
	LIA ( $\lambda{=}1\,\mathrm{s}^{-1}$ )	$0.997896$ [ $0.997739$ , $0.998047$ ]	$0.994906$ [ $0.99471$ , $0.995098$ ]	$0.185736$ [ $0.184865$ , $0.186611$ ]	$69.6328$ [ $69.6319$ , $69.6337$ ]
	LIA ( $\lambda{=}2\,\mathrm{s}^{-1}$ )	$0.996806$ [ $0.996605$ , $0.997006$ ]	$0.992733$ [ $0.992468$ , $0.992992$ ]	$0.18507$ [ $0.184244$ , $0.185896$ ]	$69.6321$ [ $69.6313$ , $69.633$ ]

Table 6: Large-market (

n=1000

) performance by topology. Entries are means with 95% bootstrap CIs over 1,000 instances per topology. Compute time is winner determination time on a single CPU core.

Mechanism	Fairness strategy	$\mathrm{SW}/\text{OPT}_{\mathrm{all}}$	LAI ( $\sup g$ )	Clearing latency (ms)	Explicit waiting rule
Fast-VCG	Arrival-order clearing	$0.505$	$314.95$	$18.65$	No
Batch-VCG ( $B=10$ ms)	Public batch window	$0.710$	$235.24$	$28.65$	Yes
Batch-VCG ( $B=50$ ms)	Public batch window	$0.994$	$1.56$	$66.24$	Yes
Sync-VCG	Common horizon	$0.999$	$0.026$	$69.21$	Yes
HoldBack	Delay equalization	$0.999$	$0.017$	$69.21$	Yes
LIA ( $\lambda=1\,\mathrm{s}^{-1}$ )	Causal slack discount	$0.997$	$0.000$	$68.97$	No

Table 7: Exact mechanism comparison on STARLINK-200 at

n=50

and

\varepsilon=0

ms from the full main-sweep experiment.

Figure 2: Latency-Arbitrage Index (LAI) curves

g(\Delta)

for STARLINK-200 and INTERNET-100 at

n=50

(log scale). For each mechanism,

g(\Delta)

measures the expected utility gain from reducing a bidder’s one-way propagation delay by

\Delta

. Fast-VCG exhibits large timing rents that grow with

\Delta

, frequent batch auctions reduce timing rents only by imposing buffering, and LIA drives the curve to zero (within estimator resolution) while maintaining the horizon-level clearing latency.

Figure 3: Empirical evaluation summary. (a,b) Fairness–latency frontier at

n=50

for Starlink and Internet: timing rent (LAI,

\sup g

) versus mean clearing latency. (c) Winner-determination runtime versus market size (shaded bands show min–max across topologies;

n=1000

points from Table 6 ). (d) Welfare ratio versus market size. (e,f) Robustness of welfare and timing rent under bounded slack-estimation error

\varepsilon

(iid perturbations, solid; common-mode clock bias, dashed), averaged over Starlink and Internet at

n=50

	$\mathrm{SW}/\text{OPT}_{\mathrm{all}}$				$\mathrm{Rev}/\text{OPT}_{\mathrm{all}}$
$\varepsilon$ (ms)	iid	bias	dist	subnet	iid	bias	dist	subnet
$0$	$0.9980$	$0.9980$	$0.9982$	$0.9982$	$0.9758$	$0.9758$	$0.9756$	$0.9756$
$0.5$	$0.9977$	$0.9979$	$0.9978$	$0.9976$	$0.9757$	$0.9756$	$0.9759$	$0.9745$
$1$	$0.9975$	$0.9979$	$0.9972$	$0.9978$	$0.9756$	$0.9755$	$0.9750$	$0.9743$
$2$	$0.9978$	$0.9977$	$0.9974$	$0.9977$	$0.9749$	$0.9754$	$0.9747$	$0.9758$
$5$	$0.9979$	$0.9975$	$0.9980$	$0.9977$	$0.9748$	$0.9757$	$0.9744$	$0.9749$

Table 8: Robustness of LIA (

\lambda=1\,\mathrm{s}^{-1}

) to bounded slack-estimation error at

n=50

(mean over Starlink and Internet).

Mechanism Design

Mechanism design studies rules for allocating resources and shaping incentives when participants hold private information or act strategically.

See all 137 papers

Mar 2, 2026

Large Language Models as Bidding Agents in Repeated HetNet Auction

This paper investigates the integration of large language models (LLMs) as reasoning agents in repeated spectrum auctions within heterogeneous networks (HetNets). While auction-based mechanisms have been widely employed for efficient resource allocation, most prior works assume one-shot auctions, static bidder behavior, and idealized conditions. In contrast to traditional formulations where base station (BS) association and power allocation are centrally optimized, we propose a distributed auction-based framework in which each BS independently conducts its own multi-channel auction, and user equipments (UEs) strategically decide both their association and bid values. Within this setting, UEs operate under budget constraints and repeated interactions, transforming resource allocation into a long-term economic decision rather than a one-shot optimization problem. The proposed framework enables the evaluation of diverse bidding behaviors -from classical myopic and greedy policies to LLM-based agents capable of reasoning over historical outcomes, anticipating competition, and adapting their bidding strategy across episodes. Simulation results reveal that the LLM-empowered UE consistently achieves higher channel access frequency and improved budget efficiency compared to benchmarks. These findings highlight the potential of reasoning-enabled agents in future decentralized wireless networks markets and pave the way for lightweight, edge-deployable LLMs to support intelligent resource allocation in next-generation HetNets.

Ismail Lotfi, Ali Ghrayeb, Samson Lasaulce +1

College of Science and Engineering, Hamad Bin Khalifa University, Doha, Qatar · CNRS, Universite de Lorraine, CRAN, France · Department of Computer Science, Khalifa University, Abu Dhabi, UAE

Wireless Resource Allocation Automated Bidding LLM Agents

Ask PDF

Oct 15, 2026

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

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.

Jihun Kim, Pan-Yang Su, Maria G. Mendoza +3

University of California, Berkeley · University of Pennsylvania · Johns Hopkins University

Mechanism Design Air Traffic Management

Ask PDF

Jul 13, 2025

Efficiency, Feasibility, and Incentive-Awareness in Constrained Online Resource Allocation

We study the dynamic allocation of indivisible resources to strategic agents under long-term constraints, where the planner aims to maximize social welfare, satisfy multiple constraints, and elicit near-truthful reports. We find standard primal-dual methods fragile in this setting: agents easily manipulate their reports to distort dual variables, sacrificing social efficiency for individual utility. To address this, we propose the Incentive-Aware Primal-Dual (IAPD) framework. On the primal side, we integrate three components to suppress manipulation: a VCG-based payment neutralizes immediate misreporting benefits, while epoch-based lazy updates and random exploration together ensure potential future gains are outweighed by immediate penalties. On the dual side, to overcome a learning barrier due to lazy updates -- which we call the "price of incentives" -- we design a novel optimistic online learning algorithm, O-FTRL-FP. It utilizes a fixed-point oracle to resolve the circular dependency between optimistic dual variables and the resulting allocations. Ultimately, our mechanism attains

\tilde{\mathcal O}(\sqrt T)

social welfare regret, satisfies all long-term constraints, and induces a near-truthful equilibrium. It also smoothly generalizes to multi-unit multi-demand allocation problems. Notably, this

\tilde{\mathcal O}(\sqrt T)

regret near-matches the non-strategic

Ω(\sqrt T)

lower bound, demonstrating that incentive-awareness can be accommodated at nearly no cost.

Yan Dai, Negin Golrezaei, Patrick Jaillet

Operations Research Center, MIT. · Sloan School of Management, MIT. · Department of EECS, MIT.

Primal-Dual Optimization Online Convex Optimization Mechanism Design Game Theory Constrained Optimization Online Resource Allocation

Ask PDF

Abstract

Mechanism Design

Explore similar work

Large Language Models as Bidding Agents in Repeated HetNet Auction

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

Efficiency, Feasibility, and Incentive-Awareness in Constrained Online Resource Allocation