4
- 1.122525605*p3 - 0.1202590019*p3*p2 + 1.078803537*p2 + 0.7696590455*p4
+ 0.1628390188*p4*p3*p2 - 0.1163105815*p4*p3 - 0.5333928492*p4*p2
- 0.6823118878;
- 0.4266067331*p3 + 0.9756757996*p4 + 0.646954510E-01*p4*p3
- 0.2142068753*p3*p1 + 2.814522341*p1 + 0.3980853635*p4*p3*p1
- 2.546266040*p4*p1 - 1.157918209;
2.023260100*p2 - 0.1342402078*p4 - 0.3904810713*p4*p2 + 0.4274147938*p1
+ 0.5269506245*p4*p1 - 3.069473137*p2*p1 + 0.3284270487*p4*p2*p1
- 0.9128973443;
- 0.6256820158*p3 - 0.1614530476*p3*p2 + 1.080721123*p2 + 1.366746822*p3*p1
- 2.347725424*p1 + 0.5941402017*p2*p1 - 2.233884240*p3*p2*p1 + 1.026687422;
TITLE : totally mixed Nash equilibria for 4 players with two pure strategies
ROOT COUNTS :
total degree : 81
4-homogeneous Bezout number : 9
with partition : {p3 }{p2 }{p4 }{p1 }
generalized Bezout number : 9
based on the set structure :
{p3 }{p2 }{p4 }
{p3 }{p4 }{p1 }
{p2 }{p4 }{p1 }
{p3 }{p2 }{p1 }
mixed volume : 9
REFERENCES :
Andrew McLennan: "The maximal generic number of pure Nash equilibria",
Journal of Economic Theory, Volume 72, pages 408-410, 1997.
Richard D. McKelvey and Andrew McLennan: "The maximal number of regular
totally mixed Nash equilibria",
Journal of Economic Theory, Volume 72, pages 411-425, 1997.
David M. Kreps and Robert Wilson: "Sequential Equibria",
Econometrica, Volume 50, Number 4, pages 863-894,1982.
DESCRIPTION :
The index set I = { 1,2,..,n } identifies people invited to attend a party.
The economical relevance is for instance a group of fishermen who have to
exploit a certain site. The mathematical problem is then to decide the
probabilities of attendance or frequency of participation, the variables
are probabilities p1,p2,..,pn, all in [0,1].
At an equilibrium state, the payoff remains unchanged when you vary your
frequency of participation. Formally, for the i-th participant we have
\sum_{S^i \subseteq I^i} p(S^i) u_i(S^i \cup \{ i \})
= \sum_{S^i \subseteq I^i} p(S^i) u_i(S^i),
for I^i = I \setminus \{ i \},
p(S^i) = \prod_{j \in S^i} p_j \prod_{j \not\in S^i} (1-p_j),
with p(S^i) expressing the probability that the group S^i attends
and u_i(S^i) a fixed constant meaning the utility for S^i to attend.
The equilibrium system then becomes:
\sum_{S^i \subseteq I^i} p(S^i) v_i(S^i) = 0, for i=1,2,..,n,
where the constants v_i(S^i) are the differences of the utilities.
The n-homogeneous Bezout number provides a generically exact root count.
It equals #derangements of I, which is #permutations without a fixed point.
Asymptotically, this number is n!/e, illustrating the exploding complexity.
The above instance is generated by a naive Maple program and has 3 real
and 6 conjugated complex solutions.
# MapleV5 program to generate the equations for totally mixed Nash equilibria,
# for games with n players each having two pure strategies.
# The utility constants are chosen as random real numbers.
# Type "eqs(4)" to generate the 4-dimensional game.
prdp := proc ( n,i ) # returns product of p_j, j=1,2,..,n, j/= i
local res,j;
res := 1;
for j from 1 to n do
if j <> i
then res := res*p.j;
fi;
od;
RETURN(res);
end;
die := convert(rand(-10^14..10^14)/10^14,float);
recp := proc ( n,i,k,acc ) # generates all monomials for i-th equation
local res;
res := 0;
if k <> i
then res := die()*p.k*acc + die()*(1-p.k)*acc;
if k < n
then res := res + recp(n,i,k+1,p.k*acc)
+ recp(n,i,k+1,(1-p.k)*acc);
fi;
else if k < n
then res := recp(n,i,k+1,acc);
fi;
fi;
RETURN(res);
end;
nash := proc ( n,i ) # generates i-th equation
local res,acc;
acc := 1;
res := recp(n,i,1,acc);
RETURN(res);
end:
eqs := proc ( n ) # prints the equations
local i;
for i from 1 to n do
print(equation.i);
lprint(expand(nash(n,i)));
od;
end;
TIMING (black-box PHC, on Pentium II PC running Linux) :
---------------------------------------------------------------------
| TIMING INFORMATION SUMMARY |
---------------------------------------------------------------------
| root counts | start system | continuation | total time |
---------------------------------------------------------------------
| 0h 0m 0s740ms | 0h 0m 0s 40ms | 0h 0m 1s820ms | 0h 0m 2s890ms |
---------------------------------------------------------------------
THE SOLUTIONS :
9 4
===========================================================================
solution 1 : start residual : 7.105E-15
t : 1.00000000000000E+00 0.00000000000000E+00
m : 1
the solution for t :
p3 : 1.20207135996546E+00 3.90491606131416E+00
p2 : 7.05289831086892E-02 4.85282385222248E-01
p4 : -4.20760357534055E+00 5.21546258072302E+00
p1 : 2.16618017393526E-01 3.71033535799464E-01
== err : 8.726E-15 = rco : 1.078E-02 = res : 7.105E-15 = complex regular ==
solution 2 : start residual : 5.995E-15
t : 1.00000000000000E+00 0.00000000000000E+00
m : 1
the solution for t :
p3 : 1.13673925416567E+01 2.08809742975953E-53
p2 : 3.00236552649914E+00 -3.41691958908379E-54
p4 : 4.20372689943980E+00 2.61012178719941E-54
p1 : -1.36306330553272E-01 -2.03915764624954E-55
== err : 4.828E-15 = rco : 6.592E-03 = res : 5.995E-15 = real regular ==
solution 3 : start residual : 1.110E-15
t : 1.00000000000000E+00 0.00000000000000E+00
m : 1
the solution for t :
p3 : 9.41267336920057E-01 -1.83670992315982E-40
p2 : 1.78906366432274E+00 0.00000000000000E+00
p4 : -5.72319083041370E-01 5.51012976947947E-40
p1 : 5.58317908664846E-01 -6.88766221184934E-41
== err : 1.410E-15 = rco : 2.939E-02 = res : 1.110E-15 = real regular ==
solution 4 : start residual : 7.286E-16
t : 1.00000000000000E+00 0.00000000000000E+00
m : 1
the solution for t :
p3 : 1.90882759573636E-01 2.80449874990590E-01
p2 : 2.67524686818387E-01 5.28096464462515E-01
p4 : 9.75485872161110E-01 7.62566831944149E-02
p1 : 6.49664839410180E-01 3.29927069627074E-01
== err : 1.064E-15 = rco : 2.464E-01 = res : 7.286E-16 = complex regular ==
solution 5 : start residual : 4.746E-15
t : 1.00000000000000E+00 0.00000000000000E+00
m : 1
the solution for t :
p3 : 1.20207135996546E+00 -3.90491606131416E+00
p2 : 7.05289831086891E-02 -4.85282385222248E-01
p4 : -4.20760357534055E+00 -5.21546258072302E+00
p1 : 2.16618017393526E-01 -3.71033535799464E-01
== err : 1.145E-14 = rco : 1.078E-02 = res : 4.746E-15 = complex regular ==
solution 6 : start residual : 1.492E-16
t : 1.00000000000000E+00 0.00000000000000E+00
m : 1
the solution for t :
p3 : 1.78626029394593E+00 0.00000000000000E+00
p2 : -4.35294134302052E-02 0.00000000000000E+00
p4 : 4.76027740936828E+00 4.17619485951906E-53
p1 : 5.19449153497582E-01 0.00000000000000E+00
== err : 4.588E-16 = rco : 2.608E-02 = res : 1.492E-16 = real regular ==
solution 7 : start residual : 6.523E-16
t : 1.00000000000000E+00 0.00000000000000E+00
m : 1
the solution for t :
p3 : 1.90882759573636E-01 -2.80449874990590E-01
p2 : 2.67524686818387E-01 -5.28096464462515E-01
p4 : 9.75485872161110E-01 -7.62566831944148E-02
p1 : 6.49664839410180E-01 -3.29927069627074E-01
== err : 1.280E-15 = rco : 2.464E-01 = res : 6.523E-16 = complex regular ==
solution 8 : start residual : 3.768E-15
t : 1.00000000000000E+00 0.00000000000000E+00
m : 1
the solution for t :
p3 : 1.24549206499949E+00 3.90006072365250E-02
p2 : 2.57342908188006E+00 -3.07216368095310E+00
p4 : 2.77809519935403E+00 -2.70082446208238E-01
p1 : 3.99741872358003E-01 -1.89631036660809E-02
== err : 1.469E-14 = rco : 4.378E-03 = res : 3.768E-15 = complex regular ==
solution 9 : start residual : 2.054E-15
t : 1.00000000000000E+00 0.00000000000000E+00
m : 1
the solution for t :
p3 : 1.24549206499949E+00 -3.90006072365251E-02
p2 : 2.57342908188007E+00 3.07216368095310E+00
p4 : 2.77809519935403E+00 2.70082446208238E-01
p1 : 3.99741872358003E-01 1.89631036660808E-02
== err : 1.038E-14 = rco : 4.378E-03 = res : 2.054E-15 = complex regular ==
===========================================================================