Department of Applied Mathematics & Physics, Kyoto Univiversity
Technical Report #97003 (January, 1997)
Optimization Games on Graphs
by Xiaotie Deng, Toshihide Ibaraki and Hiroshi Nagamochi
We introduce a general integer programming formulation
for a class of combinatorial optimization games, which
include many interesting problems on graphs.
The formulation immediately
allows us to improve the algorithmic result for
finding imputations in the core (an important solution
concept in cooperative game theory) of the network flow game
on unit networks by Kalai and Zemel.
An important result is a general theorem that the core for
this class of games is nonempty if and only if a related
linear program has an integer optimal solution.
We study the properties for this mathematical condition
to hold for several problems on graphs, and apply
them to resolve algorithmic and complexity issues
for their cores: decide whether the core is empty;
if the core is empty, find an imputation in the core;
given an imputation x, test whether x is in the core.
We also explore the properties of totally balanced games,
and relate our results with those matrices that guarantee
integer solutions.