CT-Talk "Game Thory in Networks" with Guy Avni, 28.06. (10:00 | SR10)

Die Fakultät lädt am 28.06. um 10:00 Uhr herzlich zum CT Talk mit Guy Avni zum Thema "Game Thory in Networks" im SR 10 im Fakultätsgebäude.

Abstract

I will review two projects that consider games that arise from networks. A network game is played on a directed graph by multiple players. Each player has a source and target vertex, which he wishes to connect, and a strategy is a choice of path from source to target. The cost a player pays for an edge depends on the number of players using the edge. For example, in congestion games, the cost increases with the number of players, modelling a traffic jam. Network games constitute an important class of games that has been well studied mostly due to their favorable properties; e.g., every network game has at least one Nash equilibrium. Their simple structure makes them a perfect sandbox to develop ideas and concepts. We combine network games with concepts that arise in formal verification such as rich specifications, ongoing behavior, reasoning about huge systems, and reasoning about real-time.

In the second part of the talk I will describe work on adding fault-tolerant capabilities to time-triggered scheduling, which are a deterministic communication infrastructure used by real-time distributed embedded systems. Due to the criticality of the applications running over them, developers need to ensure that end-to-end communication is dependable and predictable. Traditional approaches assume static networks that are not flexible to changes caused by reconfigurations or, more importantly, faults, which are dealt with in the application using redundancy. We suggest a relaxed forwarding scheme that can, on the one hand, handle faults to some extent, and, on the other hand, is simple enough to maintain simplicity, predictably, and a relatively simple synthesis procedure.