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 ==
===========================================================================