Universität zu Köln

Bohnlein, Toni, Schaudt, Oliver and Schauer, Joachim (2023). Stackelberg packing games. Theor. Comput. Sci., 943. S. 16 - 36. AMSTERDAM: ELSEVIER. ISSN 1879-2294

Full text not available from this repository.

Abstract

Stackelberg pricing games are pricing problems over a set of items. One player, the leader, sets prices for the items and the second player, the follower, buys a subset of items at minimal total cost subject to feasibility constraints. The constraints are determined by an optimization problem. For example, the STACKELBERG SHORTEST PATH game is used to optimize the income from road tolls (cf. [21]). The items are edges in a network graph and the follower buys a subset of edges forming a path. The Stackelberg pricing games studied in the literature are formulated on top of covering problems. In this paper, we introduce pricing games based on packing problems. We are interested in the complexity of computing leader-optimal prices depending on different types of follower-constraints. We show that optimal prices can be computed in polynomial time if the follower-constraints are determined by the well-known INTERVAL SCHEDULING problem. This problem is equivalent to the INDEPENDENT SET problem on interval graphs. In case the follower-constraints are based on the INDEPENDENT SET problem on perfect graphs or on the BIPARTITE MATCHING problem, we prove APX-hardness for the pricing problem. On a more general note, we prove Sigma(p)(2)-completeness if the follower-constraints are given by a packing problem that is NP-complete, i.e., the leader's pricing problem is hard even if she has an NP-oracle at hand. (c) 2022 Elsevier B.V. All rights reserved.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Bohnlein, Toni UNSPECIFIED UNSPECIFIED UNSPECIFIED Schaudt, Oliver UNSPECIFIED UNSPECIFIED UNSPECIFIED Schauer, Joachim UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-672447
DOI:	10.1016/j.tcs.2022.12.006
Journal or Publication Title:	Theor. Comput. Sci.
Volume:	943
Page Range:	S. 16 - 36
Date:	2023
Publisher:	ELSEVIER
Place of Publication:	AMSTERDAM
ISSN:	1879-2294
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language APPROXIMATION; MODEL Multiple languages Computer Science, Theory & Methods Multiple languages
URI:	http://kups.ub.uni-koeln.de/id/eprint/67244