Price of Anarchy in Sequencing Situations and the Impossibility to Coordinate

Herbert Hamers, Marco Slikker and Flip Klijn

No 709, Working Papers from Barcelona School of Economics

Abstract: 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.

Keywords: outsourcing; sequencing situations; first best solution; game theory; price of anarchy; coordinating mechanism (search for similar items in EconPapers)
JEL-codes: C72 D82 (search for similar items in EconPapers)
Date: 2015-09
New Economics Papers: this item is included in nep-cdm and nep-gth
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://bw.bse.eu/wp-content/uploads/2015/09/709-file.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bge:wpaper:709

Access Statistics for this paper

More papers in Working Papers from Barcelona School of Economics Contact information at EDIRC.
Bibliographic data for series maintained by Bruno Guallar ().