IDEAS home Printed from https://ideas.repec.org/a/eee/jomega/v44y2014icp104-110.html
   My bibliography  Save this article

A game mechanism for single machine sequencing with zero risk

Author

Listed:
  • Kovalyov, Mikhail Y.
  • Pesch, Erwin

Abstract

A problem is studied in which several non-cooperating clients compete for earlier execution of their jobs in a processing sequence of a single service provider in order to minimize job completion time costs. The clients can move their jobs earlier in a given sequence. They are assumed not to take a risky decision that can decrease their utility function. A game mechanism is suggested such that each client has no incentive to claim false cost and a social criterion is addressed, which is the minimum total cost of all clients. Algorithmic aspects of this mechanism are analyzed such as relations between the values of game equilibria and the social optimum, the computational complexity of finding a game equilibrium and the values of the price of anarchy and the price of stability.

Suggested Citation

  • Kovalyov, Mikhail Y. & Pesch, Erwin, 2014. "A game mechanism for single machine sequencing with zero risk," Omega, Elsevier, vol. 44(C), pages 104-110.
    • Handle: RePEc:eee:jomega:v:44:y:2014:i:c:p:104-110
    DOI: 10.1016/j.omega.2013.11.001
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0305048313001126
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.omega.2013.11.001?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Oecd, 2001. "An International Campus in Switzerland," PEB Exchange, Programme on Educational Building 2001/11, OECD Publishing.
    2. Nisan,Noam & Roughgarden,Tim & Tardos,Eva & Vazirani,Vijay V. (ed.), 2007. "Algorithmic Game Theory," Cambridge Books, Cambridge University Press, number 9780521872829, October.
    3. Qi, Xiangtong & Bard, Jonathan F. & Yu, Gang, 2004. "Supply chain coordination with demand disruptions," Omega, Elsevier, vol. 32(4), pages 301-312, August.
    4. Qiang, Qiang & Ke, Ke & Anderson, Trisha & Dong, June, 2013. "The closed-loop supply chain network with competition, distribution channel investment, and uncertainties," Omega, Elsevier, vol. 41(2), pages 186-194.
    5. William Vickrey, 1961. "Counterspeculation, Auctions, And Competitive Sealed Tenders," Journal of Finance, American Finance Association, vol. 16(1), pages 8-37, March.
    6. Martin J. Osborne & Ariel Rubinstein, 1994. "A Course in Game Theory," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262650401, April.
    7. E. L. Lawler, 1973. "Optimal Sequencing of a Single Machine Subject to Precedence Constraints," Management Science, INFORMS, vol. 19(5), pages 544-546, January.
    8. Varmaz, Armin & Varwig, Andreas & Poddig, Thorsten, 2013. "Centralized resource planning and Yardstick competition," Omega, Elsevier, vol. 41(1), pages 112-118.
    9. Jacek Błażewicz & Klaus H. Ecker & Erwin Pesch & Günter Schmidt & Jan Węglarz, 2007. "Handbook on Scheduling," International Handbooks on Information Systems, Springer, number 978-3-540-32220-7, November.
    10. N/A, 2001. "Index to International Regional Science Review," International Regional Science Review, , vol. 24(4), pages 528-529, October.
    11. Hosoda, Takamichi & Disney, Stephen M., 2012. "A delayed demand supply chain: Incentives for upstream players," Omega, Elsevier, vol. 40(4), pages 478-487.
    12. Oecd, 2001. "The Internet and Business Performance," OECD Digital Economy Papers 57, OECD Publishing.
    13. Edward Clarke, 1971. "Multipart pricing of public goods," Public Choice, Springer, vol. 11(1), pages 17-33, September.
    14. Groves, Theodore, 1973. "Incentives in Teams," Econometrica, Econometric Society, vol. 41(4), pages 617-631, July.
    15. M. Y. Kovalyov & C. N. Potts & L. N. van Wassenhove, 1994. "A Fully Polynomial Approximation Scheme for Scheduling a Single Machine to Minimize Total Weighted Late Work," Mathematics of Operations Research, INFORMS, vol. 19(1), pages 86-93, February.
    16. Monderer, Dov & Shapley, Lloyd S., 1996. "Potential Games," Games and Economic Behavior, Elsevier, vol. 14(1), pages 124-143, May.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Kuzmicz, Katarzyna Anna & Pesch, Erwin, 2019. "Approaches to empty container repositioning problems in the context of Eurasian intermodal transportation," Omega, Elsevier, vol. 85(C), pages 194-213.
    2. Dominik Kress & Sebastian Meiswinkel & Erwin Pesch, 2018. "Mechanism design for machine scheduling problems: classification and literature overview," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(3), pages 583-611, July.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. William H. Sandholm, 2005. "Negative Externalities and Evolutionary Implementation," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 72(3), pages 885-915.
    2. Chun, Youngsub & Yengin, Duygu, 2017. "Welfare lower bounds and strategy-proofness in the queueing problem," Games and Economic Behavior, Elsevier, vol. 102(C), pages 462-476.
    3. Sandholm, William H., 2007. "Pigouvian pricing and stochastic evolutionary implementation," Journal of Economic Theory, Elsevier, vol. 132(1), pages 367-382, January.
    4. Bian, Zheyong & Liu, Xiang, 2019. "Mechanism design for first-mile ridesharing based on personalized requirements part I: Theoretical analysis in generalized scenarios," Transportation Research Part B: Methodological, Elsevier, vol. 120(C), pages 147-171.
    5. Keswani Mehra, Meeta & Mukherjee, Saptarshi & Dutta, Monica, 2012. "Toward a framework for implementation of climate change treaty through self-enforcing mechanisms," MPRA Paper 36286, University Library of Munich, Germany.
    6. William H. Sandholm, 2002. "Evolutionary Implementation and Congestion Pricing," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 69(3), pages 667-689.
    7. Philippe Jehiel & Moritz Meyer-ter-Vehn & Benny Moldovanu, 2008. "Ex-post implementation and preference aggregation via potentials," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 37(3), pages 469-490, December.
    8. Xiang-Yang Li & Zheng Sun & Weizhao Wang & Wei Lou, 2010. "Cost sharing and strategyproof mechanisms for set cover games," Journal of Combinatorial Optimization, Springer, vol. 20(3), pages 259-284, October.
    9. Dominik Kress & Sebastian Meiswinkel & Erwin Pesch, 2018. "Mechanism design for machine scheduling problems: classification and literature overview," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(3), pages 583-611, July.
    10. Crescenzio Gallo, 2005. "The design and development of Mobile Ad Hoc Networks," Quaderni DSEMS 05-2005, Dipartimento di Scienze Economiche, Matematiche e Statistiche, Universita' di Foggia.
    11. Heydenreich, B. & Müller, R.J. & Uetz, M.J., 2006. "Games and mechanism design in machine scheduling - an introduction," Research Memorandum 022, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    12. Nisan, Noam, 2015. "Algorithmic Mechanism Design," Handbook of Game Theory with Economic Applications,, Elsevier.
    13. Mu'alem, Ahuva & Schapira, Michael, 2018. "Setting lower bounds on truthfulness," Games and Economic Behavior, Elsevier, vol. 110(C), pages 174-193.
    14. Jing Chen & Silvio Micali, 2016. "Leveraging Possibilistic Beliefs in Unrestricted Combinatorial Auctions," Games, MDPI, vol. 7(4), pages 1-19, October.
    15. Lau, Stephanie, 2011. "Investment incentives in bilateral trading," Games and Economic Behavior, Elsevier, vol. 73(2), pages 538-552.
    16. Tafreshian, Amirmahdi & Masoud, Neda, 2022. "A truthful subsidy scheme for a peer-to-peer ridesharing market with incomplete information," Transportation Research Part B: Methodological, Elsevier, vol. 162(C), pages 130-161.
    17. Shrestha, Ratna K., 2017. "Menus of price-quantity contracts for inducing the truth in environmental regulation," Journal of Environmental Economics and Management, Elsevier, vol. 83(C), pages 1-7.
    18. Tommy Andersson & Lars Ehlers & Lars-Gunnar Svensson & Ryan Tierney, 2022. "Gale’s Fixed Tax for Exchanging Houses," Mathematics of Operations Research, INFORMS, vol. 47(4), pages 3110-3128, November.
    19. Mishra, Debasis & Parkes, David C., 2007. "Ascending price Vickrey auctions for general valuations," Journal of Economic Theory, Elsevier, vol. 132(1), pages 335-366, January.
    20. Loertscher, Simon & Mezzetti, Claudio, 2021. "A dominant strategy, double clock auction with estimation-based tatonnement," Theoretical Economics, Econometric Society, vol. 16(3), July.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:jomega:v:44:y:2014:i:c:p:104-110. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/375/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.