Near-optimal Cost Sharing with Selfish Agents

A class of games for cost sharing between selfish users is analyzed. The
games encompass competitive versions of a variety of optimization
settings, e.g. for integer covering, facility location, and Steiner tree
creation problems. Pure Nash equilibria in these games do not necessarily
exist, their existence can be hard to decide, and they can be very costly.
However, all games considered admit cheap and stable approximate Nash
equilibria. They can be computed in polynomial time with primal-dual
algorithms or combinatorial approaches. In addition, special classes of
games admit pure Nash equilibria that are efficient and/or computable in
polynomial time. Finally, I will give some ideas of my current work in
progress on network pricing and average-case aspects of selfish routing.