IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v47y2022i4p3010-3024.html
   My bibliography  Save this article

Stackelberg Max Closure with Multiple Followers

Author

Listed:
  • Karsten Jungnitsch

    (School of Business and Economics, RWTH Aachen University, 52062 Aachen, Germany)

  • Britta Peis

    (School of Business and Economics, RWTH Aachen University, 52062 Aachen, Germany)

  • Marc Schröder

    (School of Business and Economics, Maastricht University, 6211 LK Maastricht, Netherlands)

Abstract

In a Stackelberg max closure game, we are given a digraph whose vertices correspond to projects from which firms can choose and whose arcs represent precedence constraints. Some projects are under the control of a leader who sets prices in the first stage of the game, while in the second stage, the firms choose a feasible subset of projects of maximum value. For a single follower, the leader’s problem of finding revenue-maximizing prices can be solved in strongly polynomial time. In this paper, we focus on the setting with multiple followers and distinguish two situations. In the case in which only one copy of each project is available (limited supply), we show that the two-follower problem is solvable in strongly polynomial time, whereas the problem with three or more followers is NP-hard. In the case of unlimited supply, that is, when sufficient copies of each project are available, we show that the two-follower problem is already APX-hard. As a side result, we prove that Stackelberg min vertex cover on bipartite graphs with a single follower is APX-hard.

Suggested Citation

  • Karsten Jungnitsch & Britta Peis & Marc Schröder, 2022. "Stackelberg Max Closure with Multiple Followers," Mathematics of Operations Research, INFORMS, vol. 47(4), pages 3010-3024, November.
    • Handle: RePEc:inm:ormoor:v:47:y:2022:i:4:p:3010-3024
    DOI: 10.1287/moor.2021.1240
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/moor.2021.1240
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2021.1240?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
    ---><---

    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:inm:ormoor:v:47:y:2022:i:4:p:3010-3024. 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.

    We have no bibliographic references for this item. You can help adding them by using 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.