Skip to content

Instantly share code, notes, and snippets.

@DominikPeters

DominikPeters/nash-dynamic.py

Last active April 26, 2022 12:37
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save DominikPeters/e0dbe6069827360cb13896957c10bc53 to your computer and use it in GitHub Desktop.
Save DominikPeters/e0dbe6069827360cb13896957c10bc53 to your computer and use it in GitHub Desktop.
Download ZIP
Compute Nash via Dynamic
Raw
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
@DominikPeters
Copy link
Author

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment