Skimming through the contents of the October 2015 issue of the Journal of the ACM, a paper’s title caught my eye: «Intrinsic Robustness of the Price of Anarchy» by Tim Roughgarden. Hm, let’s have a look at its abstract:
The price of anarchy, defined as the ratio of the worst-case objective function value of a Nash equilibrium of a game and that of an optimal outcome, quantifies the inefficiency of selfish behavior.
Interesting metric. The price of anarchy measures the consequences of behaving in each one’s self interest. We are not talking about short-eyed selfish actions. Rather we are talking about well-informed autonomous players who have extensively studied the rules of the game and play rationally, disergarding any feelings and impulses. As Raughgarden states:
Self-interested behavior by autonomous decision-makers generally leads to an inefficient result–an outcome that could be improved upon given dictatorial control over everyone’s actions.
It would be really interesting to explore the frequency distribution of how many games favor anarchy versus dictatorship.
Googling led me to a Wikipedia article for the Price of Anarchy, that computes its value for the Prisoner’s Dilemma game. What a coincidence, I have written an introductory text for the Prisoner’s Dilemma, which I updated.
But things got more enticing at Wikipedia:
… The term Price of Anarchy was first used by Koutsoupias and Papadimitriou …
There is greek involvement in this term. Papadimitriou is a rock star among CS professors. I’ve been lucky to have attended a lecture of his in Computer Engineering Department, at the University of Patras.
I located their 1999 paper, titled «Worst-case Equilibria» and dag further to discover the story behind the term «Price of Anarchy» in the January 2011 column of AMS by Joe Malkevitch. This column inevitably has political & economic implications:
Much of modern economics is based on the assumption that the «human actors» in the «economic drama» behave rationally. … When rational people just do what they want, how bad can the result be compared with what could be achieved if they were «regulated» or «induced» into other behavior which is optimal (best)?
igaviotis 