Stackelberg Max Closure with Multiple Followers

Karsten Jungnitsch (), Britta Peis () and Marc Schröder ()
Additional contact information
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

Mathematics of Operations Research, 2022, vol. 47, issue 4, 3010-3024

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.

Keywords: Primary: 68R10; secondary: 05C21; 91A65; project selection; Stackelberg games; computational complexity (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1240 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:47:y:2022:i:4:p:3010-3024

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().