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

    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.
    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.
    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. N/A, 2001. "Index to International Regional Science Review," International Regional Science Review, , vol. 24(4), pages 528-529, October.
    10. Hosoda, Takamichi & Disney, Stephen M., 2012. "A delayed demand supply chain: Incentives for upstream players," Omega, Elsevier, vol. 40(4), pages 478-487.
    11. Oecd, 2001. "The Internet and Business Performance," OECD Digital Economy Papers 57, OECD Publishing.
    12. Edward Clarke, 1971. "Multipart pricing of public goods," Public Choice, Springer, vol. 11(1), pages 17-33, September.
    13. Groves, Theodore, 1973. "Incentives in Teams," Econometrica, Econometric Society, vol. 41(4), pages 617-631, July.
    14. 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. repec:spr:orspec:v:40:y:2018:i:3:d:10.1007_s00291-018-0512-8 is not listed on IDEAS

    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.

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

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

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.