Elliptic Curves in Game Theory
Supplementary Material
The script is ending with .m2 and is run in \(\verb|Macaulay2|\), the script ending with .nb is run in \(\verb|Mathematica|\), and the script ending with .gp is run in \(\verb|Pari/GP|\).
Computations for Section 2
Pareto dominance of dependency equilibria
For a generic \(2 \times 2\) game, i.e., a game that has only one totally mixed Nash equilibrium, we want to check if there exists a dependency equilibrium that yields better payoffs. The equations defining the totally mixed Nash equilibria \((q^{(1)},q^{(2)})\) are
which yields
and \(q^{(1)}_2 = 1-p^{(1)}_1\), \(q^{(2)}_2 = 1-p^{(2)}_1\) and where we assume that
in order for there to be a unique solution whose entries are actually indeterminate probabilities. The payoff curve is the curve describing the payoffs coming from \(\mathcal V \cap \Delta\). It is given by the determinant of the Konstanz matrix. Using quantifier elimination in Mathematica, we are able to check for a given game if there is a point on the payoff curve that has higher payoffs than the Nash equilibrium. The code for this is given in
CheckForParetoDominance.nb.
Computations for Section 3
Proof of Lemma 3.2
The complete computations for this are done in Lemma32.m2.
We want to investigate for which payoffs the Spohn cubic is reducible. After intersecting the cubic with the three lines \(\mathbb V(x), \mathbb V(y), \mathbb V(z)\) we draw lines through the points of intersection. If any of these lines is contained in the cubic, it is reducible.
R = QQ[a_(1,1)..a_(2,2),b_(1,1)..b_(2,2),x,y,z];
c_1 = (a_(1,1)-a_(2,2))*(b_(1,1)-b_(1,2));
c_2 = (a_(1,1)-a_(2,1))*(b_(2,2)-b_(1,1));
c_3 = (a_(1,2)-a_(2,2))*(b_(1,1)-b_(1,2));
c_4 = (a_(1,1)-a_(2,1))*(b_(2,2)-b_(2,1));
c_5 = (a_(1,2)-a_(2,2))*(b_(2,1)-b_(1,2));
c_6 = (a_(1,2)-a_(2,1))*(b_(2,2)-b_(2,1));
c_7 = (a_(1,2)-a_(2,1))*(b_(2,2)-b_(1,1))+(a_(1,1)-a_(2,2))*(b_(2,1)-b_(1,2));
f = c_1*x^2*y + c_2*x^2*z + + c_3*x*y^2 + c_4*x*z^2 + c_5*y^2*z + c_6*y*z^2 + c_7*x*y*z;
f1 = sub(f, {y=>-(c_1/c_3)*x});
den1 = denominator(f1);
num1 = numerator(f1);
P1 = primaryDecomposition ideal(num1);
We compute here the equation defining the intersection of the cubic with the first line. The denominator cannot vanish by assumption, therefore the equation is zero whenever it vanishes on an ideal in the primary decomposition of the numerator. In this case, this is quite simple.
Intersecting with the fifth line, the decomposition of the numerator contains a much longer ideal. We observe that it is of the form \(d_5 x + e_5 y\) and that in order to determine when it vanishes it suffices to decompose the ideal \((d_5,e_5)\).
f5 = sub(f, {z=>-((c_1*c_5)/(c_3*c_6))*x-(c_5/c_6)*y});
den5 = denominator(f5);
num5 = numerator(f5);
P5 = primaryDecomposition ideal(num5);
--examine long factor:
(M5,C5) = coefficients ((first entries gens P5#(#P5-1))#0, Variables => {x,y,z});
d5 = C5_(0,0);
e5 = C5_(1,0);
J5 = ideal(d5,e5);
D5 = decompose J5;
I11 = D5#6;
I12 = D5#7;
The components of J5 are precisely the ideals corresponding to cases (11) and (12). To actually obtain these cases, we need to show that the assumption that \(c_3,c_6 \neq 0\) is not necessary for reducibility.
--if c_3=0:
--b_(1,1)=b_(1,2) is covered by case (4)
--a_(1,2)=a_(2,2):
decompose(I11 + ideal(a_(1,2)-a_(2,2)))
decompose(I12 + ideal(a_(1,2)-a_(2,2)))
--if c_6=0:
--a_(1,2)=a_(2,1):
decompose(I11 + ideal(a_(1,2)-a_(2,1)))
decompose(I12 + ideal(a_(1,2)-a_(2,1)))
--b_(2,2)=b_(2,1):
decompose(I11 + ideal(b_(2,2)-b_(2,1)))
decompose(I12 + ideal(b_(2,2)-b_(2,1)))
For example decompose(I11 + ideal(a_(1,2)-a_(2,2))) yields
{ideal(b_(1,2)-b_(2,1),a_(1,2)-a_(2,1),a_(2,1)*b_(1,1)-a_(2,2)*b_(1,1)-a_(1,1)*b_(2,1)+a_(2,2)*b_(2,1)+a_(1,1)*b_(2,2)-a_(2,1)*b_(2,2)),
ideal(a_(2,1)-a_(2,2),a_(1,2)-a_(2,2),a_(1,1)-a_(2,2))}
The first component is already covered by case (6), the second contradicts the cubic being nonzero.
Decomposition of Spohn cubic
The computations for this are done in Decomposition of Spohn Cubic.m2. For the 12 cases from Lemma 3.2, assuming that the remaining entries of the payoff tables are generic, the Spohn cubic decomposes as follows:
One can check that, since we assume non-constant payoff tables, for any component that has multiple generators, these generators actually agree with each other, given the respective cases, such that \(\mathcal C\) always decomposes into a line and a conic.
Remark 3.3
The computations for this are done in Remark33.m2. We show that the conditions of cases (9) to (12) can be supplemented or replaced with other, similar conditions by showing that the generated ideals remain the same.
R = QQ[a_(1,1)..a_(2,2),b_(1,1)..b_(2,2)];
--------------------------------------------
--case 9
--generators of I9:
g9_1 = a_(1,2)*(b_(1,2)-b_(2,2)) + a_(2,1)*(b_(2,2)-b_(2,1)) + a_(2,2)*(b_(2,1)-b_(1,2));
g9_2 = a_(1,1)*(b_(2,2)-b_(1,2)) + a_(2,1)*(b_(1,1)-b_(2,2)) + a_(2,2)*(b_(1,2)-b_(1,1));
g9_3 = a_(1,1)*(b_(2,2)-b_(2,1)) + a_(1,2)*(b_(1,1)-b_(2,2)) + a_(2,2)*(b_(2,1)-b_(1,1));
I9 = ideal(g9_1,g9_2,g9_3);
--extra generator:
e9 = a_(1,1)*(b_(1,2)-b_(2,1)) + a_(1,2)*(b_(1,1)-b_(1,2)) + a_(2,1)*(b_(2,1)-b_(1,1));
--test if we can exchange generators
I9 == I9 + ideal(e9)
I9 == ideal(g9_1,g9_2,e9)
I9 == ideal(g9_1,g9_3,e9)
I9 == ideal(g9_2,g9_3,e9)
Decomposition of the Spohn variety
The computations for this are done in Decomposition of Spohn Variety.m2. For the 12 cases from Lemma 3.2, assuming that the remaining entries of the payoff tables are generic, the Spohn variety decomposes as follows:
The cases (4),(5) and (6) work completely analogously to (1), (2) and (3). Also, just as for the decomposition of the Spohn cubic above, one can check that since the payoff tables are non-constant, many of the generating polynomials are redundant given the respective cases.
Proof of Theorem 3.7
The complete computations for this are done in Theorem37.m2. If the irreducible components of the Spohn variety \(\mathcal V\) are of projective dimension 1 (i.e. codimension 2) and project to the irreducible components of the Spohn cubic \(\mathcal C\), Proposition 3.6 guarantees that they contain a real smooth point.
R = QQ[a_(1,1)..a_(2,2),b_(1,1)..b_(2,2),p_(1,1),p_(1,2),p_(2,1),p_(2,2)];
--Spohn variety V:
detM1 = (a_(2,1)-a_(1,1))*p_(1,1)*p_(2,1) + (a_(2,2)-a_(1,1))*p_(1,1)*p_(2,2) + (a_(2,1)-a_(1,2))*p_(1,2)*p_(2,1) + (a_(2,2)-a_(1,2))*p_(1,2)*p_(2,2);
detM2 = (b_(1,2)-b_(1,1))*p_(1,1)*p_(1,2) + (b_(2,2)-b_(1,1))*p_(1,1)*p_(2,2) + (b_(1,2)-b_(2,1))*p_(1,2)*p_(2,1) + (b_(2,2)-b_(2,1))*p_(2,1)*p_(2,2);
I = ideal(detM1,detM2);
--Spohn cubic C:
c_1 = (a_(1,1)-a_(2,2))*(b_(1,1)-b_(1,2));
c_2 = (a_(1,1)-a_(2,1))*(b_(2,2)-b_(1,1));
c_3 = (a_(1,2)-a_(2,2))*(b_(1,1)-b_(1,2));
c_4 = (a_(1,1)-a_(2,1))*(b_(2,2)-b_(2,1));
c_5 =(a_(1,2)-a_(2,2))*(b_(2,1)-b_(1,2));
c_6 = (a_(1,2)-a_(2,1))*(b_(2,2)-b_(2,1));
c_7 = (a_(1,2)-a_(2,1))*(b_(2,2)-b_(1,1))+(a_(1,1)-a_(2,2))*(b_(2,1)-b_(1,2));
f = c_1*p_(1,1)^2*p_(1,2) + c_2*p_(1,1)^2*p_(2,1) + c_3*p_(1,1)*p_(1,2)^2 + c_4*p_(1,1)*p_(2,1)^2 + c_5*p_(1,2)^2*p_(2,1) + c_6*p_(1,2)*p_(2,1)^2 + c_7*p_(1,1)*p_(1,2)*p_(2,1);
J = ideal(f);
---------------------------------------------------------------
--case (1)
CompV1 = decompose(I + ideal(a_(1,1)-a_(1,2)));
CompC1 = decompose(J + ideal(a_(1,1)-a_(1,2)));
--check if irred comp of V have proj dim 1/affine dim 2
--this corresponds to codim 3 here, since dimension goes down by 1 from the assumption
apply(#CompV1, q -> codim(CompV1#q))
--check if the elimination ideals of min primes of V are the min primes of C
#CompV1 == #CompC1
apply(#CompV1, q -> (eliminate(p_(2,2),CompV1#q) == CompC1#q))
Since, to consider the different cases, we add the condition of the respective case to the ideals describing \(\mathcal V\) and \(\mathcal C\), we need to substract the dimension of that condition from the overall dimension in our calculations. Doing this for all of the 12 cases shows that in all of them the minimal primes of \(\mathcal V\) have the desired dimension. In all cases except for case (7), eliminating \(p_{2,2}\) from the minimal primes of \(\mathcal V\) yields a minimal prime of \(\mathcal C\).
--case (7)
CompV7 = decompose(I + ideal(a_(1,2)-a_(2,2),b_(2,1)-b_(2,2)));
CompC7 = decompose(J + ideal(a_(1,2)-a_(2,2),b_(2,1)-b_(2,2)));
--check if irred comp of V have proj dim 1/affine dim 2
--this corresponds to codim 4 here, since dimension goes down by 2 from the assumption
apply(#CompV7, q -> codim(CompV7#q))
--check if the elimination ideals of min primes of V are the min primes of C
#CompV7 == #CompC7
eliminate(p_(2,2),CompV7#2) == CompC7#1
isSubset(CompC7#0, eliminate(p_(2,2),CompV7#0))
degree CompV7#0
isSubset(CompC7#0, eliminate(p_(2,2),CompV7#1))
degree CompV8#0
Here, two of the elimination ideals, \((p_{11},p_{12})\) and \((p_{11},p_{22})\), properly contain the minimal prime \((p_{11})\) of \(\mathcal C\). However, since they are lines, they trivially contain a real smooth point.
Example 3.8
The computations for this are done in Example38.m2
R = QQ[a_(1,1)..a_(2,2),b_(1,1)..b_(2,2),p_(1,1),p_(1,2),p_(2,1),p_(2,2)];
--Spohn variety V:
detM1 = (a_(2,1)-a_(1,1))*p_(1,1)*p_(2,1) + (a_(2,2)-a_(1,1))*p_(1,1)*p_(2,2) + (a_(2,1)-a_(1,2))*p_(1,2)*p_(2,1) + (a_(2,2)-a_(1,2))*p_(1,2)*p_(2,2);
detM2 = (b_(1,2)-b_(1,1))*p_(1,1)*p_(1,2) + (b_(2,2)-b_(1,1))*p_(1,1)*p_(2,2) + (b_(1,2)-b_(2,1))*p_(1,2)*p_(2,1) + (b_(2,2)-b_(2,1))*p_(2,1)*p_(2,2);
I = ideal(detM1,detM2);
--Spohn cubic C:
c_1 = (a_(1,1)-a_(2,2))*(b_(1,1)-b_(1,2));
c_2 = (a_(1,1)-a_(2,1))*(b_(2,2)-b_(1,1));
c_3 = (a_(1,2)-a_(2,2))*(b_(1,1)-b_(1,2));
c_4 = (a_(1,1)-a_(2,1))*(b_(2,2)-b_(2,1));
c_5 = (a_(1,2)-a_(2,2))*(b_(2,1)-b_(1,2));
c_6 = (a_(1,2)-a_(2,1))*(b_(2,2)-b_(2,1));
c_7 = (a_(1,2)-a_(2,1))*(b_(2,2)-b_(1,1))+(a_(1,1)-a_(2,2))*(b_(2,1)-b_(1,2));
f = c_1*p_(1,1)^2*p_(1,2) + c_2*p_(1,1)^2*p_(2,1) + c_3*p_(1,1)*p_(1,2)^2 + c_4*p_(1,1)*p_(2,1)^2 + c_5*p_(1,2)^2*p_(2,1) + c_6*p_(1,2)*p_(2,1)^2 + c_7*p_(1,1)*p_(1,2)*p_(2,1);
J = ideal(f);
-------------------------------
--show that C is irreducible:
decompose J
-------------------------------
--show that if a_(1,2)=a_(2,2) then not not every elimination ideal of minimal primes of I is a minimal prime of J
P = decompose(I + ideal(a_(1,2)-a_(2,2)))
C1 = eliminate(p_(2,2), P#0)
C2 = eliminate(p_(2,2), P#1)
C2 == J + ideal(a_(1,2)-a_(2,2))
isSubset(C2,C1)
We observe that, if \(a_{12}=a_{22}\), which is not one of the 12 cases, then the Spohn cubic remains irreducible and, in fact, not every elimination ideal of irreducible components of \(\mathcal V\) is an irreducible component of \(\mathcal C\).
Remark 3.9
The computations for this are done in Remark39.m2. We observe whether the irreducible components of the Spohn variety \(\mathcal V\) are contained in the union of hyperplanes
R = QQ[a_(1,1)..a_(2,2),b_(1,1)..b_(2,2)][p_(1,1),p_(1,2),p_(2,1),p_(2,2)];
--Spohn variety V:
detM1 = (a_(2,1)-a_(1,1))*p_(1,1)*p_(2,1) + (a_(2,2)-a_(1,1))*p_(1,1)*p_(2,2) + (a_(2,1)-a_(1,2))*p_(1,2)*p_(2,1) + (a_(2,2)-a_(1,2))*p_(1,2)*p_(2,2);
detM2 = (b_(1,2)-b_(1,1))*p_(1,1)*p_(1,2) + (b_(2,2)-b_(1,1))*p_(1,1)*p_(2,2) + (b_(1,2)-b_(2,1))*p_(1,2)*p_(2,1) + (b_(2,2)-b_(2,1))*p_(2,1)*p_(2,2);
I = ideal(detM1,detM2);
--union of hyperplanes W:
J = ideal (p_(1,1)+p_(1,2))*(p_(2,1)+p_(2,2))*(p_(1,1)+p_(2,1))*(p_(1,2)+p_(2,2));
------------------------
--for the 12 cases check if some components of V are contained in W
--case (1)
P1 = decompose(I + ideal(a_(1,1)-a_(1,2)));
apply(#P1, q -> isSubset(J,P1#q))
For example for case (1), this gives the output {false, true}, which implies that the second component is contained in \(\mathcal W\) and we therefore cannot say anything about dependency equilibria in that case.
The same holds for cases (2) to (7). In cases (8) to (12), no component is fully contained, which implies that any point \(p \in \mathcal V \cap \Delta\) is a dependency equilibrium.
Computations for Section 4
The Mathematica notebook is used to study arithmetic and algebraic quantities of elliptic curves whic h are obtained from the intersection of two quadrics (quadratic surfaces) in \(\mathbb P^3\) with an aribitrary but specified common rational point. The code in the Mathematica notebook IntersectionQuadricsJ.nb
- Transforms the intersection quadratic surfaces such that the common rational point is the point at infinity.
- Reduces to a smooth cubic in \(\mathbb P^2\), where it is expressible as an elliptic curve
- Computes the j-invariant for the elliptic curve in terms of the data of the two quadratic surfaces. The full j-invariant of the curve is available in Generic_J_invt.txt.
The Pari/GP file getJ.gp serves as a check: This file inputs the two quadrics such that their common rational point is the point at infinity and then uses standard arithmetic techniques built into Pari/GP to compute the J-invariant. This is simply to convince oneself that the results are indeed correct. For the case of the Spohn curve as in (Equation 1) in the paper which is obtained generally by intersection of quadrics \(P_1\) and \(P_2\) with common rational point \([0:0:0:1]\) of the form below
where \(A_{ij}, B_{ij}\) are rational numbers (or rational approximations of real numbers), the j-invariant of the Spohn curve can be found in SpohnCurveJInv.txt.
Functions in the Mathematica Notebook
The main functions in the Mathematica notebook are:
FindRedCubic[X_, pol1_, pol2_]: Takes in two quadrics in \(\mathbb P^3\) (pol1, pol2) and the common rational point \(X\) and computes the reduced cubic in \(\mathbb P^3\). This cubic can be fed into Pari/GP to compute the J invariant too.FindJ[X_, pol1_, pol2_]: Takes in two quadrics in \(\mathbb P^3\) (pol1, pol2) and the common rational point \(X\) and computes the j-invariant of the elliptic curve.FindDisc[X_, pol1_, pol2_]: Takes in two quadrics in \(\mathbb P^3\) (pol1, pol2) and the common rational point \(X\) and computes the discriminant of the elliptic curve via their Aronhold invariants.
The notebook is sufficiently documented. The functions used to compute the main functions above are entered in protected cells to avoid accidental type overs.
The examples section in IntersectionQuadricsJ.gp demonstrates how to use the notebook and should be self explanatory.
Functions in the Pari/GP script
To use the Pari/GP script, first ensure that Pari/GP (https://pari.math.u-bordeaux.fr/) is installed on your system. Once installed, on a terminal application enter
$ gp
Once in the Pari/GP environment, you may execute them script getJ.gp directly or copy paste the following commands into the terminal.
\\ Define commands
# termL(pol) = ’t*polcoef(pol,1,t);
\\ Computes terms of degree 1 in t
L(pol) = polcoef(pol,1,t);
# termQ(pol) = polcoef(pol,0,t);
\\ Computes terms of degree 0 in t
Q(pol) = polcoef(pol,0,t);
\\ Compute the reduced cubic in P2
CubicRed(cur1,cur2) = L(cur1)*Q(cur2) - L(cur2)*Q(cur1)
\\ Define the elliptic curve from the reduced cubic
E = ellfromeqn(CubicRed(cur1,cur2));
\\ To find the j invariant, first make sure that the two curves in P3 are defined and that they have a common rational point at [0:0:0:1]. If the curves have a different rational point, then use the algorithm in Intersection_Quadrics.nb to ensure a coordinate transformation such that the rational point is at [0:0:0:1].
\\ Now, initialize the elliptic curve as below
ec = ellinit(E);
\\ Compute the j invariant
ec.j
To execute the script directly from within Pari/GP:
\\ Define the two quartics cur1 and cur 2
\\ Example: cur1 = a*x^2 + b*x*y + c*x*z; cur2 = A*z*x + B* z*y ;
\r getJ.gp
This will compute the j-invariant directly.
Rational approximations of real numbers
In the paper, we assume that the payoff matrices are defined over \(\mathbb Q\). While the pay-off matrices are likely to be rational, they can generically be real numbers. In the even that the payoff matices are real, we can still the methods and algorithms listed in the paper since we can approximate to a model over \(\mathbb Q\). Real numbers can be approximated by rational numbers. A standard method to do this is via the approach of continued fractions.
confrac.gp contains a script to compute the continued fraction approximation to any real number (even irrational). It is worth noting that precision on Pari/GP is usually to 35 decimal digits and can be changed using the \p command. The script containt the following command
evalcontfrac(n,l) = { local(x=0, V = contfrac(n,l));
forstep(i = #V, 1, -1, x = V[i] + if(x,1/x,0));
return(x);}
To evaluate the code/script, download it to a destination folder. Navigate to the destination folder in the terminal window and enter into the Pari/GP environment in by entering the command gp in a terminal. Once inside the Pari/GP environment
\\ Define n to be the real number you wish to approximate and l to be the length of the continued fraction
\\ The larger the value of l, the better the approximation
\\ Example:
n = Pi;
l = 10;
\r confrac.gp
\\ This will output a rational number which is a rational approximation of Pi