Metraipolis › archive › dc_4bd33eaa627f

The Fixed Server Locality Gap of Count Load Assignment Games — arXiv:2609.12572

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.12572
License (as archived)
CC0-1.0
Archived
2026-10-16T03:09:03.076Z
SHA-256 of the archived text
7c8833f08bdf12acbb850c6324dbf4f2d484ec5853730d94665fade106f86db2
Stable URL of this page
https://metraipolis.com/documento/dc_4bd33eaa627f

How to cite

The Fixed Server Locality Gap of Count Load Assignment Games — arXiv:2609.12572 — arXiv (en), https://arxiv.org/abs/2609.12572 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_4bd33eaa627f (Metraipolis archive dc_4bd33eaa627f, sha256 7c8833f08bdf12acbb850c6324dbf4f2d484ec5853730d94665fade106f86db2)
BibTeX
@misc{dc4bd33eaa627f,
  title = {The Fixed Server Locality Gap of Count Load Assignment Games — arXiv:2609.12572},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.12572},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_4bd33eaa627f; sha256 7c8833f08bdf12acbb850c6324dbf4f2d484ec5853730d94665fade106f86db2},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.12572. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\Theta_M(\kappa^{1-2^{-M}})$ as the workload-ratio cap $\kappa$ 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.

Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-14 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2609.12572 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T03:04:07.410Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-14?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).