For a constant ϵ, we prove a poly(N) lower bound on the (randomized) communication complexity of ϵ-Nash equilibrium in two-player NxN games. For n-player binary-action games we prove an exp(n) lower bound for the (randomized) communication complexity of (ϵ,ϵ)-weak approximate Nash equilibrium, which is a profile of mixed actions such that at least (1−ϵ)-fraction of the players are ϵ-best replying.
John Nash’s notion of equilibrium is ubiquitous in economic theory, but a new study shows that it is often impossible to reach efficiently.
To some extent I also find myself wondering about repeated play as a possible random walk versus larger “jumps” in potential game play and the effects this may have on the “evolution” of a solution by play instead of a simpler closed mathematical solution.
The Golden Rule mandating that you treat others as you want them to treat you is simply a variation on tit-for-tat, one that emphasizes the benefit rather than the harm side. (The Christian principle of returning a favor for a harm in this respect is highly unusual and, one might note, more often than not unimplemented in Christian societies. No society I know of approves returning a harm for a favor as a general moral rule within the group.)
John Baez, one of the organizers of the workshop, is also going through them and adding some interesting background and links on his Azimuth blog as well for those who are looking for additional details and depth
Additonal resources from the Workshop:
https://www.youtube.com/playlist?list=PLRyq_4VPZ9g-3869ozbY_eEp6jZhWL0UE
If Leonard Riggio, Barnes & Noble's chairman, joins Liberty Media's proposed buyout of his company, the board needs to decide how to handle his 30 percent stake before shareholders vote on the deal.
