IDEAS home Printed from https://ideas.repec.org/
MyIDEAS: Log in (now much improved!) to save this article

A game mechanism for single machine sequencing with zero risk

Listed author(s):
  • Kovalyov, Mikhail Y.
  • Pesch, Erwin
Registered author(s):

    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.

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

    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 look for a different version under "Related research" (further below) or search for a different version of it.

    Article provided by Elsevier in its journal Omega.

    Volume (Year): 44 (2014)
    Issue (Month): C ()
    Pages: 104-110

    as
    in new window

    Handle: RePEc:eee:jomega:v:44:y:2014:i:c:p:104-110
    DOI: 10.1016/j.omega.2013.11.001
    Contact details of provider: Web page: http://www.elsevier.com/wps/find/journaldescription.cws_home/375/description#description

    Order Information: Postal: http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
    Web: https://shop.elsevier.com/order?id=375&ref=375_01_ooc_1&version=01

    References listed on IDEAS
    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.:

    as
    in new window


    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, December.
    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, January.
    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)

    This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.

    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)

    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 references are entirely missing, you can add them using this form.

    If the full references list an item that is present in RePEc, but the system did not link 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 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.

    This information is provided to you by IDEAS at the Research Division of the Federal Reserve Bank of St. Louis using RePEc data.