Fixed server assignments show growing inefficiency with uneven workloads
The Fixed Server Locality Gap of Count Load Assignment Games
Computer Science and Game Theory
Summary
The paper looks at how tasks with different sizes get assigned to shared servers when each server has limits. The authors study how the system's worst inefficiency grows as workloads vary more widely, finding precise mathematical bounds. They also show this problem can model real-world scenarios like drones connecting to fixed stations. Their results help identify when stable task assignments are less efficient and clarify what affects these outcomes.
What this means in practice
- •For network schedulers: Design efficient assignment strategies for workloads on fixed-capacity servers knowing how inefficiency scales with workload diversity.
- •For drone network operators: Optimize UAV client-to-ground server connections by understanding assignment inefficiencies with varying drone workloads and server limits.
Tested on simulated data.
Authors
Hao Li, Mengfan Ma
Abstract
Marginal-contribution pricing makes the social objective an exact potential, but does not ensure that every stable assignment is efficient. We study indivisible clients with heterogeneous workloads, arbitrary nonnegative assignment costs, and private eligibility menus over a fixed number of shared servers and optional local execution. Each server's social cost is its occupancy multiplied by its aggregate workload and a server-specific coefficient. For every fixed server cap $M$, we prove that the price of anarchy over this class is $Θ_M(κ^{1-2^{-M}})$ as the workload-ratio cap $κ$ grows. The upper bound applies to every equilibrium and every feasible comparison, without an acyclic-comparison or strongly-connected-component restriction. Its proof combines a common-multiplier certificate, a source-weighted residual inequality and an ordered moment recurrence. A matching chain family has a realization by mobile unmanned aerial vehicle (UAV) clients and fixed ground servers, with positive altitude, positive-width coverage and an explicitly paid wireless baseline. We prove exact waypoint elimination and give an input-computable component refinement. Scheduling and congestion identities delimit which established bounds transfer. Exact enumeration of 2,800 synthetic games identifies inefficient equilibria, while 270 primary-parameterized synthetic instance-budget records evaluate incremental latency relative to a feasible multistart reference. Tightness concerns the heterogeneity exponent for fixed $M$, not matching leading constants or measured frequency of the worst-case configurations.