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.
Tag: game theory
👓 In Game Theory, No Clear Path to Equilibrium | Quanta Magazine
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.
Game Theory’s Tit-for-Tat is Just a Mathematically Complete Version of Religion’s Golden Rule
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.)
in The Origins of Political Order: From Prehuman Times to the French Revolution (Farrar, Straus and Giroux, 2011)
Videos from the NIMBioS Workshop on Information and Entropy in Biological Systems
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:
- NIMBios Workshop page
- Participants list
- Workshop Agenda [.pdf download]
- Information and Entropy WordPress site
- YouTube playlist of videos
- Storify archive from the workshop (The storify service shuttered in May 2018. I’ve archived much of the content and links.)
https://www.youtube.com/playlist?list=PLRyq_4VPZ9g-3869ozbY_eEp6jZhWL0UE
Barnes & Noble Board Would Face Tough Choices in a Buyout Vote | Dealbook
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.