FDDS-Solver: A tool for very efficient detection of dominant strategies in normal form games

Introduction

This tool is intended for simulation (numerical) solutions in normal-form games (see literature on Game Theory). A game in normal-form of N players is a vektor (Q;S_1,...,S_N;U_1,...,U_N), where

Q is a set of players, i.e. Q={1,...,N}
S_i are sets of strategies of players i\in Q, S=S_1 x S_2 x ... x S_N is a total set of profiles.
U_i are utility functions in form U_i: S->R

By saying numerical, we mean an existence of certain computer procedure (or oracle) called cellModel, which returns a vector R^N of payoffs to each given profile s in S. When solving such a game, we have to:

invoke cellModel(s) for all s in S,
complete all profiles and store their utilities in memory,
determine the equilibrium point.

Anyone can insight that this computation may be rather difficult due the fact of size of the set of profiles |S|. The algorithmic and memory complexity of the computation can be significantly decreased by transforming a given game to its strategic equivalent (it keeps all equilibrias of the original game).

Thus, we need an algorithm transforming a given game to its smaller equivalent which does not suffer from the disadvantages mentioned above. FDDS-Solver is a method and algorithm satisfying that. FDDS-Solver has been implemented as a computer tool.

How it works

The algorithm was formally defined in [1].

We give a rather implementation notes here:

FDDS-Solver is a computerized mechanism which experiment with a given game description and a cellModel
it is assumed that the given cellModel is implemented in such a manner that each player i has just one pure best-response strategy to every sub-profile s_{-i}. This condition is not necessary, but makes the algorithm working very efficiently

In your program, link the tool to your software, specify your cellModel class and GameDescription – see an example

References

[1] Hruby, M.: Algorithmic Approaches to Game-theoretical Modeling and Simulation, In: AUCO Czech Economic Review, Vol. 2, No. 3, 2008, Praha, CZ, p. 268-300, ISSN 1802-4696, available on-line at AUCO

Download and licence

The program is available through GPL licence. Prospective users are kindly asked to send an information e-mail to the author.

Download this: fdds-solv-0.tar.gz

Contact the author

Martin Hruby
e-mail: hrubym atttt fit.vutbr.cz
www: homepage-of-author