Error message

Deprecated function: Array and string offset access syntax with curly braces is deprecated in include_once() (line 20 of /mnt/web104/a0/07/510451407/htdocs/includes/file.phar.inc).

Price of Anarchy in Sequencing Situations and the Impossibility to Coordinate

Printer-friendly version
Working paper
Author/s: 
Herbert Hamers, Flip Klijn and Marco Slikker
Issue number: 
709
Publisher: 
Barcelona GSE
Year: 
2013
Scheduling jobs of decentralized decision makers that are in competition will usually lead to cost inefficiencies. This cost inefficiency is studied using the Price of Anarchy (PoA), i.e., the ratio between the worst Nash equilibrium cost and the cost attained at the centralized optimum. First, we provide a tight upperbound for the PoA that depends on the number of machines involved. Second, we show that it is impossible to design a scheduled-based coordinating mechanism in which a Nash equilibrium enforces the centralized or first best optimum. Finally, by simulations we illustrate that on average the PoA is relatively small with respect to the established tight upperbound.
Developed by Paolo Gittoi