Price of Anarchy in Sequencing Situations and the Impossibility to Coordinate

  • Authors: Flip Klijn.
  • BSE Working Paper: 709 | September 15
  • Keywords: outsourcing , sequencing situations , first best solution , game theory , price of anarchy , coordinating mechanism
  • JEL codes: C72, D82
  • outsourcing
  • sequencing situations
  • first best solution
  • game theory
  • price of anarchy
  • coordinating mechanism
Download PDF Download pdf Icon

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.

Subscribe to our newsletter
Want to receive the latest news and updates from the BSE? Share your details below.
Founding institutions
Distinctions
Logo BSE
© Barcelona Graduate School of
Economics. All rights reserved.
YoutubeFacebookLinkedinInstagramX