Invited Talks |
Abstract: We present here recent results and fundamental notions of the theory of a quite broad class of games , called Congestion Games. In their original form , proposed by I. Milchtaich , they are noncooperative games with the payoff of a player for a particular strategy depending only on the total number of players playing the same strategy , in a decreasing way. We show a way to extend the theory to weighted congestion games , where the payoffs depend also on players individual weights. We survey important theorems about classical congestion games (eg Rosenthal's theorem and also the equivalence to Potential Games ) and we discuss the problem of finding or establishing existence of pure Nash Equilibria in the general case. We also present some of our recent results that we got , using such a framework, in routing unsplittable flows in networks. Several relations to convex optimization theory are indicated.
Paul Spirakis is a full Professor at the
Department of Computer Science and Engineering School of Engineering, Patras University,
and director and senior researcher of the (Research and Academic) Computer Technology Institute
in Patras, Greece. His research is focused in algorithms and complexity,
computer systems and networks.
presentation (pdf, 1.6MB)
Abstract:ATM networks and optical networks give rise to new and similar graph-theoretic models within which problems are stated and analyzed. In both cases one considers paths in a given network, and the routing is done using these paths. The models differ mainly in the parameters that have to be optimized. In ATM networks the two basic parameters are the load (number of paths sharing an edge) and the hop count (number of paths that form a routing), while in optical networks two basic parameters are the number of colors and the number of switches. In both models there are interesting trade-offs between these parameters. These two related areas offer a huge range of research. In the talk - that assumes no a priori knowledge - some appetite for these research areas will be built, by introducing the two graph-theoretic models, surveying some past work, detailing some results, and presenting some directions for future research.
Shmuel Zaks is a full Professor at the
Computer Science Department of Israel Institute of Technology (Technion).
His research interests include
theory of distributed computing, ATM and optical networks,
combinatorial and graph algorithms, combinatorics and graph theory, and discrete mathematics.
presentation (pps, 1.9MB)