Selfish behavior can often lead to suboptimal outcome for all
participants, a phenomenon illustrated by classical examples in game
theory, such as the prisoner dilemma . Yet, many algorithms, that are
originally designed without explicitly considering incentive
properties, are later used in settings when participants can act
strategically. How good are they in the presence of strategic
behavior? We'll will show robust guarantees for performance on a broad
range of algorithms in presence of strategic behavior of the
participants. Joint work with Paul Duetting and Thomas Kesselheim.
Eva Tardos is Jacob Gould Schurman Professor of Computer Science at
Cornell University, was Computer Science department chair 2006-2010.
She received her BA and PhD from Eotvos University in Budapest. She
joined the faculty at Cornell in 1989. She has been elected to the
National Academy of Engineering, the National Academy of Sciences, the
American Academy of Arts and Sciences, is an external member of the
Hungarian Academy of Sciences, and is the recipient of a number of
fellowships and awards including the Packard Fellowship, the Goedel
Prize, Dantzig Prize, Fulkerson Prize, and the IEEE Technical
Achievement Award. She was editor editor-in-Chief of SIAM Journal of
Computing 2004-2009, and is currently editor of several other journals
including the Journal of the ACM and Combinatorica, served as problem
committee member for many conferences, and was program committee chair
for SODA'96, FOCS'05, and EC'13.
Tardos's research interest is algorithms and algorithmic game theory,
the subarea of theoretical computer science theory of designing
systems and algorithms for selfish users. Her research focuses on
algorithms and games on networks. She is most known for her work on
network-flow algorithms, approximation algorithms, and quantifying the
efficiency of selfish routing.
Host: Professor Philip Klein