Survey Lecture: Britta Peis: Stackelberg Network Pricing Games

Tuesday, June 28, 2022, 4:30pm

Location: Department of Computer Science, Ahornstr. 55, building E2 (no. 2356), ground floor, room: B-IT 5053.2.
We are looking forward to meeting you in person!
Nevertheless, all events are hybrid. To join remotely, please use:
Meeting ID: 960 0388 5007, Passcode: 273710

Speaker: Britta Peis



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