🔖 Communication complexity of approximate Nash equilibria | arXiv

Bookmarked Communication complexity of approximate Nash equilibria (arXiv)
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.
Suggested by In Game Theory, No Clear Path to Equilibrium by Erica Klarreich (Quanta Magazine)

👓 In Game Theory, No Clear Path to Equilibrium | Quanta Magazine

Read In Game Theory, No Clear Path to Equilibrium by Erica Klarreich (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.
There’s a couple of interesting sounding papers in here that I want to dig up and read. There are some great results that sound like they are crying out for better generalization and classification. Perhaps some overlap with information theory and complexity?

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

Francis Fukuyama (1952- ), American political scientist, political economist, author
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

Videos from the April 8-10, 2015, NIMBioS workshop on Information and Entropy in Biological Systems are slowly starting to appear on YouTube.

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:



Barnes & Noble Board Would Face Tough Choices in a Buyout Vote | Dealbook

Read Barnes & Noble Faces Tough Choices in a Buyout Vote by Steven Davidoff Solomon (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.

This story from the New York Times’ Dealbook is a good quick read on some of the details and machinations of the Barnes & Noble buyout. Perhaps additional analysis on it from a game theoretical viewpoint would yield new insight?