Metraipolis › archive › dc_1890a55dfd80

Computing Equilibria in Integer Programming Games with Shared Constraints — arXiv:2610.04279

Source: arXiv
Original: https://arxiv.org/abs/2610.04279
License (as archived): CC0-1.0
Archived: 2026-10-06T05:29:29.967Z
SHA-256 of the archived text: e6dc95f884b3b5daf54c59518cd4089a58ef4e86e0ebb5fd919be7bbd2fab3f6
Stable URL of this page: https://metraipolis.com/documento/dc_1890a55dfd80

How to cite

Computing Equilibria in Integer Programming Games with Shared Constraints — arXiv:2610.04279 — arXiv, https://arxiv.org/abs/2610.04279 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_1890a55dfd80 (Metraipolis archive dc_1890a55dfd80, sha256 e6dc95f884b3b5daf54c59518cd4089a58ef4e86e0ebb5fd919be7bbd2fab3f6)

BibTeX

@misc{dc1890a55dfd80,
  title = {Computing Equilibria in Integer Programming Games with Shared Constraints — arXiv:2610.04279},
  howpublished = {arXiv},
  url = {https://arxiv.org/abs/2610.04279},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_1890a55dfd80; sha256 e6dc95f884b3b5daf54c59518cd4089a58ef4e86e0ebb5fd919be7bbd2fab3f6},
  year = {2026}
}

Archived text

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

We develop a cutting-plane algorithm for computing pure Nash equilibria in finite integer games with shared constraints, where a deviation may be feasible against one opponent profile and infeasible against another. Conditional equilibrium inequalities capture this dependence through an explicit activation term. We give affine encodings of costs and activation conditions and prove that the resulting inequalities characterize the equilibrium set exactly. Embedded as lazy constraints in branch-and-cut, they yield the Generalized Zero-Regret algorithm for optimizing a linear objective over exact or approximate equilibria; a bisection procedure maintains certified bounds on the smallest achievable approximation factor. We also prove that, when the conditional polytopes have integral vertices, a concave cost is constant on the minimal face containing an equilibrium strategy, so strict concavity forces vertex strategies; for uniform integer-splittable bin packing, a cost-preserving transformation yields vertex equilibria even without strict concavity. We give formulations for bin packing, network formation, and knapsack games with shared capacities and evaluate the algorithm on 3,300 instances, computing a socially optimal equilibrium on all but 43, certifying nonexistence on 16, and certifying approximation factors within a few percent where no exact equilibrium exists.

Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno).
Categorie arXiv: Optimization and Control (math.OC) ; Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2610.04279 — 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-06T05:25:35.328Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).