Economics Faculty Database
Economics
Arts & Sciences
Duke University

 HOME > Arts & Sciences > Economics > Faculty    Search Help Login pdf version printable version 

Publications [#236235] of Vincent Conitzer

Journal articles or Book chapters PUBLISHED

  1. Conitzer, V; Sandholm, T, A technique for reducing normal-form games to compute a nash equilibrium, Proceedings of the International Conference on Autonomous Agents, vol. 2006 (December, 2006), pp. 537-544, ACM Press [doi]
    (last updated on 2024/03/28)

    Abstract:
    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 satisfiability 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 sufficient for finding a Nash equilibrium in linear time. Finally, we discuss using the technique to compute approximate Nash equilibria. Copyright 2006 ACM.


Duke University * Arts & Sciences * Economics * Faculty * Research * Staff * Master's * Ph.D. * Reload * Login