Price of Anarchy in Sequencing Situations and the Impossibility to Coordinate
AbstractScheduling 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.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Barcelona Graduate School of Economics in its series Working Papers with number 709.
Date of creation: Aug 2013
Date of revision:
sequencing situations; outsourcing; first best solution; game theory; price of anarchy; coordinating mechanism;
Find related papers by JEL classification:
- C72 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Noncooperative Games
- D82 - Microeconomics - - Information, Knowledge, and Uncertainty - - - Asymmetric and Private Information; Mechanism Design
This paper has been announced in the following NEP Reports:
- NEP-ALL-2013-09-24 (All new papers)
- NEP-CDM-2013-09-24 (Collective Decision-Making)
- NEP-GTH-2013-09-24 (Game Theory)
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Heydenreich Birgit & Müller, Rudolf & Uetz, Marc, 2006. "Decentralization and Mechanism Design for Online Machine Scheduling," Research Memorandum 007, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
- Yossi Bukchin & Eran Hanany, 2007. "Decentralization Cost in Scheduling: A Game-Theoretic Approach," Manufacturing & Service Operations Management, INFORMS, vol. 9(3), pages 263-275, October.
- George L. Vairaktarakis, 2013. "Noncooperative Games for Subcontracting Operations," Manufacturing & Service Operations Management, INFORMS, vol. 15(1), pages 148-158, September.
- Tolga Aydinliyim & George L. Vairaktarakis, 2010. "Coordination of Outsourced Operations to Minimize Weighted Flow Time and Capacity Booking Costs," Manufacturing & Service Operations Management, INFORMS, vol. 12(2), pages 236-255, January.
- Curiel, Imma & Pederzoli, Giorgio & Tijs, Stef, 1989. "Sequencing games," European Journal of Operational Research, Elsevier, vol. 40(3), pages 344-351, June.
- Estevez Fernandez, M.A. & Borm, P.E.M. & Calleja, P. & Hamers, H.J.M., 2004.
"Sequencing Games with Repeated Players,"
2004-128, Tilburg University, Center for Economic Research.
- Manipushpak Mitra & Roland Hain, 2001.
"Simple Sequencing Problems with Interdependent Costs,"
Bonn Econ Discussion Papers
bgse20_2001, University of Bonn, Germany.
- Hain, Roland & Mitra, Manipushpak, 2004. "Simple sequencing problems with interdependent costs," Games and Economic Behavior, Elsevier, vol. 48(2), pages 271-291, August.
- van den Nouweland, Anne & Krabbenborg, Marc & Potters, Jos, 1992. "Flow-shops with a dominant machine," European Journal of Operational Research, Elsevier, vol. 62(1), pages 38-46, October.
- Curiel, I. & Pederzoli, G. & Tijs, S.H., 1989. "Sequencing games," Open Access publications from Tilburg University urn:nbn:nl:ui:12-154243, Tilburg University.
- Curiel, I. & Potters, J.A.M. & Rajendra Prasad, V. & Tijs, S.H. & Veltman, B., 1994. "Sequencing and cooperation," Open Access publications from Tilburg University urn:nbn:nl:ui:12-154192, Tilburg University.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Bruno Guallar).
If references are entirely missing, you can add them using this form.