file.pdf (205.77 kB)
0/0

A Technique for Reducing Normal-Form Games to Compute a Nash Equilibrium

Download (205.77 kB)
journal contribution
posted on 01.01.2003 by Vincent Conitzer, Tuomas W Sandholm

We present a technique for reducing a normal-form (aka. (bi)matrix) game, O, to a smaller normal-form game, R, for the purpose of computing a Nash equilibrium. This is done by computing a Nash equilibrium for a subcomponent, G, of O for which a certain condition holds. We also show that
such a subcomponent G on which to apply the technique can be found in polynomial time (if it exists), by showing that the condition that G needs to satisfy can be modeled as a Horn satis¯ability problem. We show that the technique does not extend to computing Pareto-optimal or welfare maximizing equilibria. We present a class of games, which we call ALAGIU (Any Lower Action Gives Identical Utility) games, for which recursive application of (special cases of) the technique is su±cient for ¯nding a Nash equilibrium in linear time. Finally, we discuss using the technique to compute approximate Nash equilibria.

History

Date

01/01/2003

Exports

Exports