UnRAVeL Survey Lecture: Britta Peis: Stackelberg Network Pricing Games
Tuesday, June 28, 2022
UnRAVeL Survey Lecture: Britta Peis: Stackelberg Network Pricing Games
- Dr. rer. nat., Universitätsprofessorin Britta Peis – Fakultät für Wirtschaftswissenschaften
Abstract
We study a variant of bilevel games, termed Stackelberg network pricing games, in which one distinguished player, the leader, can set prices on a subset of the edges or vertices in the underlying network. The remaining edges or vertices are assigned a fixed costs. Based on the leader’s decision, one or several followers optimize a polynomial-time solvable combinatorial optimization problem. That is, after the leader decided on the prices, each follower individually selects an optimal solution (e.g. a shortest path, a max weight matching, or a min cost spanning tree) based on the fixed costs and the leader’s prices. The leader’s goal is to select the prices such that the resulting revenue, which is determined by the sold items and their prices, is maximised.
Briest et al. and Balcan et al. independently showed that the maximum revenue can be approximated to a factor of (roughly) log k, where k is the number of priceable elements. In the lecture, we discuss algorithms and complexity results for Stackelberg network pricing games in general, and Stackelberg Max Closure and Stackelberg Bipartite Min Weight Vertex Cover, in particular.
Parts of the talk are based on joint work with Karsten Jungnitsch and Marc Schröder.