{
"cells": [
{
"cell_type": "code",
"execution_count": 1,
"id": "7c700538",
"metadata": {},
"outputs": [],
"source": [
"# This file contains code for computing the possible combinatoriall types of the Correlated Equilibria polytope for 2x3 games. This file is part of the proof of Theorem 5.9.\n",
"# In mathematica we computed a representative Y for each chamber of the oriented matroid strata. Since the combinatorial type of the polytope is constant\n",
"# in each chamber, we only need to compute the combinatorial type for a single Y in that chamber to know the type for all possible Y's in the chamber\n",
"\n",
"# First we read in the Y vectors which represent each strata\n",
"f = open(\"strataReps2x3.txt\", \"r+\")\n",
"exec(f.read())\n",
"\n",
"# Now we define the variables. Here yijkl = Y_j^i(k, l)\n",
"var('y1112, y1212, y1312, y2112, y2212, y2113, y2213, y2123, y2223')\n",
"variables = [y1112, y1212, y1312, y2112, y2212, y2113, y2213, y2123, y2223]\n",
"\n",
"# This is the matrix who's rows give the inequalities of the Correlated Equilibria cone for a 2x3 game\n",
"A = [[y1112, y1212, y1312, 0, 0, 0], \n",
" [0, 0, 0, -y1112, -y1212, -y1312],\n",
" [y2112, 0, 0, y2212, 0, 0],\n",
" [y2113, 0, 0, y2213, 0, 0],\n",
" [0, -y2112, 0, 0, -y2212, 0],\n",
" [0, y2123, 0, 0, y2223, 0],\n",
" [0, 0, -y2113, 0, 0, -y2213],\n",
" [0, 0, -y2123, 0, 0, -y2223],\n",
" [1, 0, 0, 0, 0, 0],\n",
" [0, 1, 0, 0, 0, 0],\n",
" [0, 0, 1, 0, 0, 0],\n",
" [0, 0, 0, 1, 0, 0],\n",
" [0, 0, 0, 0, 1, 0],\n",
" [0, 0, 0, 0, 0, 1]]"
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "ffb5130e",
"metadata": {},
"outputs": [],
"source": [
"# Now we compute the all of the polytopes P(Y) given by the matrix of inequalities A(Y) for each Y in strataReps\n",
"polytopes = []\n",
"\n",
"# There is only one equality constraint on this polytope in general which is that all the coordinates sum to 1\n",
"eqns = [[-1] + [1 for i in range(6)]]\n",
"\n",
"for y in strataReps:\n",
" \n",
" Ay = matrix(A).subs({variables[i]:y[i] for i in range(9)})\n",
" Ay = matrix(QQ, Ay)\n",
" Ay = [[0] + list(Ay.row(i)) for i in range(Ay.nrows())]\n",
" Py = Polyhedron(ieqs = Ay, eqns = eqns)\n",
"\n",
" polytopes.append(Py)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "996944ea",
"metadata": {},
"outputs": [],
"source": [
"# Here we can see that the only dimensions that appear are 1, 4, 6\n",
"dims = sorted(set([P.dim() for P in polytopes]))\n",
"\n",
"# Now we sort the cones by dimension. To do this we create a dictionary whose keys are the dimensions\n",
"# and whose values are \n",
"polytopesByDim = {}\n",
"\n",
"for i in dims:\n",
" polytopesByDim[i] = []\n",
" \n",
"for P in polytopes: \n",
" \n",
" polytopesByDim[P.dim()].append(P)"
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "c57bf194",
"metadata": {},
"outputs": [],
"source": [
"# Lastly we check to make sure that within dimensions 4 and 6 we get only 1 combinatorial type\n",
"# We check that each polytope is combinatorially isomorphic to the first polytope in the list\n",
"allEquiv3 = sum([polytopesByDim[3][0].is_combinatorially_isomorphic(P) for P in polytopesByDim[3]]) == len(polytopesByDim[3])\n",
"allEquiv5 = sum([polytopesByDim[5][0].is_combinatorially_isomorphic(P) for P in polytopesByDim[5]]) == len(polytopesByDim[5])"
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "22570de5",
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Lastly we check that the 3-dimensional polytope is combinatorially isomorphic to the full dimensional polytope of a 2x2 game\n",
"# To do this we use the polytope discussed in Example 2.3 which is pictured in Figure 2 of our paper\n",
"P = Polyhedron(vertices = [(0, 0, 1, 0), (0, 1, 0, 0), (9801/10000, 99/10000, 99/10000, 1/10000), (99/101, 1/101, 1/101, 0), (0, 99/199, 99/199, 1/199)])\n",
"polytopesByDim[3][0].is_combinatorially_isomorphic(P)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c6d286fd",
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "SageMath 9.6",
"language": "sage",
"name": "sagemath-9.6"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.10.3"
}
},
"nbformat": 4,
"nbformat_minor": 5
}