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

Large Language Models as Bidding Agents in Repeated HetNet Auction
Mar 2, 2026Ismail Lotfi, Ali Ghrayeb, Samson Lasaulce +1Wireless Resource Allocation Automated Bidding
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
Dynamic Auction Mechanisms in a Closed-Credit Economy: Sequential Slot Reallocation in Air Traffic Management
Oct 15, 2026Jihun Kim, Pan-Yang Su, Maria G. Mendoza +3Mechanism Design Air Traffic Management
University of California, Berkeley · University of Pennsylvania · Johns Hopkins University
Efficiency, Feasibility, and Incentive-Awareness in Constrained Online Resource Allocation
Jul 13, 2025Yan Dai, Negin Golrezaei, Patrick JailletPrimal-Dual Optimization Online Convex Optimization
Operations Research Center, MIT. · Sloan School of Management, MIT. · Department of EECS, MIT.

Mar 2, 2026J/K move · Enter open · S save

Large Language Models as Bidding Agents in Repeated HetNet Auction

Ismail Lotfi, Ali Ghrayeb, Samson Lasaulce, Merouane Debbah

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

Open paper AskPDF arXiv

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.

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