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 Part of the programme of the research training group UnRAVeL is a series of introductory lectures on the topics of "randomness" and "uncertainty" in UnRAVeL’s research thrusts: Algorithms and complexity, verification, logic and languages, and their application scenarios. The main aim is to

Dear all, this is a reminder for Britta Peis' talk on Stackelberg Network Pricing Games <https://www.unravel.rwth-aachen.de/go/id/tbciy?lidx=1#aaaaaaaaaatbcjr> taking place *today at 16:30* in room 5053.2 and on Zoom. Please find the details below. provide doctoral researchers as well as master students a broad overview of the subjects of UnRAVeL. Science undergoes continuous change and lives from the constant quest for novel and better results, which are presented at conferences and in journals. This year, 10 UnRAVeL professors will present some of their most recent research successes. Everyone interested, in particular doctoral researchers and master students, are invited to attend the UnRAVeL lecture series 2022 and engage in discussions with the researchers. The talks take place on Tuesdays, 16:30–18:00 in room 5053.2 in the ground floor of building E2. All events are hybrid. To join remotely, please use https://rwth.zoom.us/j/96003885007?pwd=aUczMVdVU0ZXVGtQUFpwQnJHQUFhUT09 / Meeting ID: 960 0388 5007 / Passcode: 273710 Please find a list of all upcoming talks on the UnRAVeL website <https://www.unravel.rwth-aachen.de/cms/UnRAVeL/Studium/~pzix/Ringvorlesung-Veranstaltung/?lidx=1> and below: * 28/06/2022 Britta Peis: Stackelberg Network Pricing Games * 05/07/2022 Gerhard Lakemeyer: Tractable Reasoning in First-Order Knowledge Bases We are looking forward to seeing many of you in the UnRAVeL survey lecture "What's New in UnRAVeL?". Best regards, Andreas Klinger, Birgit Willms, and Tim Seppelt Logo