Compute Nash via Dynamic

nash-dynamic.py

def nash(N, A, u, rounds=500):
    "N is set of voters, A is set of alternatives, u is a utility dictionary"
    "where u[i,x] >= 0 is the utility of i for x, usually either 0 or 1"
    p = {x : 1/len(A) for x in A}
    for _ in range(rounds):
        q = {x : 0 for x in A}
        for i in N:
            util = sum(u[i,x] * p[x] for x in A)
            for x in A:
                q[x] += (1/len(N)) * (u[i,x] * p[x]) / util
        if p == q:
            return p
        p = q
    return p

For proof that this converges to the optimum Nash distribution, see Theorem 2 here: https://www.sciencedirect.com/science/article/pii/S0304406821001476