Approximate pure Nash equilibrium in weighted congestion games

报告人/Speaker: Mr. Christoph Hansknecht

报告题目/Title: Approximate pure Nash equilibrium in weighted congestion games

时间/Date & Time: 2:00 p.m. - 2:40 p.m., Feb. 20, 2017

地点/Location: ROOM M842, BISEC


We study the existence of approximate pure Nash equilibria in weighted congestion games. We develop techniques to obtain approximate potential functions that proves the existence of $\alpha$-approximate pure Nash equilibria and
the convergence of $\alpha$-improvement steps. We show how to obtain upper bounds for approximation factor $\alpha$ for a given class of cost functions. We demonstrate our techniques and establish the existence of approximate equilibria for specific classes of cost functions. For example, for concave cost functions the factor is at most $3/2$, for quadratic cost functions $4/3$, and for polynomial cost functions of maximal degree $d$ it is at most $d+1$. For games with two players we obtain tight bounds which are as small as for example $1.054$ in the case of quadratic cost functions.

报告人简介/About the speaker:

Mr. Hansknecht obtained his M.S. in Mathematics from TU Berlin in 2013. Now, he is a Ph.D. candidate in TU Braunschweig supervised by Prof. Dr. Sebastian Stiller. He mainly worked on the TEAM (Tomorrow's Elastic adaptive Mobility) project
funded by the European union. His research interests are traffic optimization and mathematical programming.