3
$\begingroup$

There are a few tools, either online or offline, that could solve (find equilibrium) in a game explicitly given as a real-valued matrix.

Such tools are Game Theory Explorer and Gambit.

However, as far as I know, these can not be used for finding equilibrium in a game with parameters.

For example, consider a two player game symmetric game, parametrized by some $x\in[0,1]$, which is given by the following payoff matrix for the row player (and $A^t(x)$ for the column player): $$A(x)= \left( \begin{array}{ccc} \frac{x}{2} & x \\ 1-x & \frac{1-x}{2} \\ \end{array} \right) $$

Each equilibrium in this game can be represented as $<p_a,p_b>\in[0,1]^2$ where $p_a$ is the probability of the first player playing the first strategy and $p_b$ is the probability the second player plays the first strategy.

Analytically we can find all the equilibriums for this game

$$EQ(x)= \begin{cases} \{<1,1>\}&\mbox{if } x>\frac{2}{3}\\ \{<3x-1,3x-1>,<1,0>,<0,1>\}&\mbox{if } \frac{1}{3}\leq x\leq\frac{2}{3}\\ \{<0,0>\}& \mbox{else} \end{cases} $$

I'm looking for a solver which is able to understand inputs like $A(x)$ and produce $EQ(x)$.

Is there a tool which solves parametric games?

Improve this question
$\endgroup$
5
  • $\begingroup$ How can the entries depend on $x$? $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Jan 1, 2015 at 21:20
  • $\begingroup$ @KristofferArnsfeltHansen - what do you mean? For every $x$, $A(x)$ is a normal game given in matrix form. A parametric solver would be able to produce the output with respect to $x$. $\endgroup$
    – R B
    Jan 2, 2015 at 7:41
  • $\begingroup$ I understand that. But how is the input specified? For instance, in your example, the entries are simple linear functions of $x$. $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Jan 2, 2015 at 10:43
  • $\begingroup$ @KristofferArnsfeltHansen - assume you can simply write the matrix as $<f_{1,1}(x),f_{1,2}(x);f_{2,1}(x),f_{2,2}(x)>$, where $f_{i,j}$ is a some function of $x$, e.g. $<x/2, x; 1-x, (1-x)/2>$. Such tool would be very useful (for me anyways) even for a single parameter, small matrices (up to $3\times 3$) and linear functions of the parameter. $\endgroup$
    – R B
    Jan 2, 2015 at 11:40
  • $\begingroup$ For small matrices you can simply enumerate over square submatrices and use the characterization of Shapley and Snow. $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Jan 2, 2015 at 12:39

1 Answer 1

Reset to default
4
$\begingroup$

Is there a tool which solves parametric games?

Not that I am aware of (I am a co-author of GTE and help with Gambit).

The best suggestion I have if you don't find such a tool (and I doubt one exists) is to do a parameter sweep and solve a bunch of individual instantiations and see what the resulting sets of equilibria say about $EQ()$. Gambit is very tightly integrated with python, so you can easily define your game as a python function with the parameters as arguments and solve a set of instances via a parameter sweep.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Can you combine Gambit with sympy to solve the game symbolically? $\endgroup$
    – Erel Segal-Halevi
    Jan 3, 2019 at 19:22
  • $\begingroup$ For simple settings one might indeed be able to use sympy relatively easily. E.g., one could use solveset from sympy to do support enumeration for a bimatrix game with some parametrized payoffs, which would give (some parametric description of) the extreme NE. To find all NEs one then need to solve a maximal clique enumeration problem - probably tricky in this parametrized setting. For >= 3, the NE set can be any semi-algebraic set and we don't have robust enumerators for the non-parametric case, so unless the payoff parametrization is highly constrained, it may be hopeless. $\endgroup$
    – Rahul Savani
    Jan 5, 2019 at 12:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.