Back to search

Virginia Tech

Multi-Agent Integer Programming Games with Non-Cooperation and Cooperation

Abstract

dc:description.abstract

This dissertation studies integer programming games (IPGs), in which each of several self-interested players solves an integer program whose payoff is coupled to the others' discrete decisions. Because feasible sets are combinatorial and best responses require integer optimization, even deciding whether a pure Nash equilibrium (PNE) exists is computationally intractable in general. The unifying thesis is that the equilibrium of such a game is a computable and leverageable object around which better system-level decisions can be built, and this idea is developed across the non-cooperative, generalized, and cooperative regimes on a common branch-and-cut foundation of globally valid inequalities and best-response oracles. First, to make equilibrium computation scale, round-based random-restart best-response dynamics (RRR-BRD) are introduced with a Las Vegas convergence guarantee and hybridized with the zero-regret cutting-plane method (BZR), lifting tractable PNE computation and sampling from a handful of players to dozens; the methods are instantiated on edge-weighted budgeted maximum coverage games, including a Minnesota aquatic invasive species (AIS) inspection game with up to 84 counties. Second, Nash-informed planning converts computed equilibria into individual-rationality floors and optimizes social welfare above them, improving system outcomes without making any player worse off; the accompanying Price of Individual Rationality is proven to be bounded by the Price of Stability, and the welfare cost of guaranteeing participation is empirically negligible. Third, for generalized IPGs with shared constraints, conditional equilibrium inequalities and a generalized zero-regret algorithm optimize over the equilibrium set, while α-approximate equilibrium certificates and structural (VEST) cuts handle cost-sharing games such as integer splittable bin packing. Fourth, cooperative IPGs define coalition values through pooled integer programs and compute optimal, Core-stable coalition structures via stability inequalities and separation. Computational studies, anchored by the AIS application, demonstrate scalability, interpretability, and concrete policy improvements.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Industrial and Systems Engineering
Department dc:contributor.department
Industrial and Systems Engineering
Grantor dc:publisher
Virginia Tech
Year dc:date.issued
2026

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Lee, Hyunwoo
Chairs dc:contributor.committeechair
  • Buyuktahtakin Toy, Esra
  • Hildebrand, Robert
Committee members dc:contributor.committeemember
  • Kannan, Rohit
  • Cai, Wenbo

Subjects

dc:subject × 4

Rights

dc:rights
Statement dc:rights
  • In Copyright
Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Other
vt_gsexam:47610

Chain of custody

source
Harvested from
Virginia Tech
Base URL
vtechworks.lib.vt.edu/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Lee, Hyunwoo. Multi-Agent Integer Programming Games with Non-Cooperation and Cooperation. doctoral thesis, Virginia Tech, 2026. https://hdl.handle.net/10919/143793