# Linear programming in Python: CVXOPT and game theory

• Using Docker is the fastest way to run the code. In only 5 commands you can replicate my environment and run the code.
• Alternatively, the code has the following dependencies: Python (3.5.3), numpy (1.12.1), cvxopt (1.1.9), glpk optimizer (but you can use the default optimizer, glpk is better for some more advanced problems)
`A = [[3, -2, 2], [-1, 0, 4] ,[-4, -3, 1]]`
`def maxmin(self, A, solver="glpk"):    num_vars = len(A)    # minimize matrix c    c = [-1] + [0 for i in range(num_vars)]    c = np.array(c, dtype="float")    c = matrix(c)    # constraints G*x <= h    G = np.matrix(A, dtype="float").T # reformat each variable is in a row    G *= -1 # minimization constraint    G = np.vstack([G, np.eye(num_vars) * -1]) # > 0 constraint for all vars    new_col = [1 for i in range(num_vars)] + [0 for i in range(num_vars)]    G = np.insert(G, 0, new_col, axis=1) # insert utility column    G = matrix(G)    h = ([0 for i in range(num_vars)] +          [0 for i in range(num_vars)])    h = np.array(h, dtype="float")    h = matrix(h)    # contraints Ax = b    A =  + [1 for i in range(num_vars)]    A = np.matrix(A, dtype="float")    A = matrix(A)    b = np.matrix(1, dtype="float")    b = matrix(b)    sol = solvers.lp(c=c, G=G, h=h, A=A, b=b, solver=solver)    return sol`
`sol = maxmin(A=A, solver=”glpk”)probs = sol[“x”]print(probs)# [ 1.67e-01]# [ 8.33e-01]# [ 0.00e+00]`
`A = [[6, 6], [2, 7], [7, 2], [0, 0]]`
`def ce(self, A, solver=None):    num_vars = len(A)    # maximize matrix c    c = [sum(i) for i in A] # sum of payoffs for both players    c = np.array(c, dtype="float")    c = matrix(c)    c *= -1 # cvxopt minimizes so *-1 to maximize    # constraints G*x <= h    G = self.build_ce_constraints(A=A)    G = np.vstack([G, np.eye(num_vars) * -1]) # > 0 constraint for all vars    h_size = len(G)    G = matrix(G)    h = [0 for i in range(h_size)]    h = np.array(h, dtype="float")    h = matrix(h)    # contraints Ax = b    A = [1 for i in range(num_vars)]    A = np.matrix(A, dtype="float")    A = matrix(A)    b = np.matrix(1, dtype="float")    b = matrix(b)    sol = solvers.lp(c=c, G=G, h=h, A=A, b=b, solver=solver)    return soldef build_ce_constraints(self, A):    num_vars = int(len(A) ** (1/2))    G = []    # row player    for i in range(num_vars): # action row i        for j in range(num_vars): # action row j            if i != j:                constraints = [0 for i in A]                base_idx = i * num_vars                comp_idx = j * num_vars                for k in range(num_vars):                    constraints[base_idx+k] = (- A[base_idx+k]                                               + A[comp_idx+k])                G += [constraints]    # col player    for i in range(num_vars): # action column i        for j in range(num_vars): # action column j            if i != j:                constraints = [0 for i in A]                for k in range(num_vars):                    constraints[i + (k * num_vars)] = (                        - A[i + (k * num_vars)]                        + A[j + (k * num_vars)])                G += [constraints]    return np.matrix(G, dtype="float")`
`sol = ce(A=A, solver="glpk")probs = sol["x"]print(probs)# [ 5.00e-01]# [ 2.50e-01]# [ 2.50e-01]# [ 0.00e+00]`

--

--

## More from Adam Novotny

Love podcasts or audiobooks? Learn on the go with our new app.