Congestion Games: Optimization in Competition

Channel:
Microsoft Research
Subscribers:
344,000
Published on ● Video Link: https://www.youtube.com/watch?v=j4yZkshcqXI


Duration: 54:45
1,638 views
11

Congestion games are a natural approach to model resource allocation among selfish or myopic players. In a congestion game there is a set of resources, and a strategy of a player corresponds to the selection of a subset of these resources, e.g., each player aims at allocating a shortest path between a source/destination pair in a given network or each player aims at allocating a minimum weight spanning tree in a given graph. The cost (delay, payoff) of a resource (edge) is a function of the congestion, i.e., the number of players allocating the resource. We survey recent results on the complexity of computing Nash equilibria for congestion games and the convergence time towards Nash equilibria. In particular, we study how the combinatorial structure of the strategy spaces influences the complexity and convergence time. We also discuss extensions of congestion games towards congestion games with weighted players and player-specific latency functions. This talk is based on joint work with Heiner Ackermann and Berthold Voecking.



Other Videos By Microsoft Research


2016-09-06The promise, the limits, and the beauty of software
2016-09-06Bayesian Methods for Unsupervised Language Learning
2016-09-06Games, gamers, and digital entertainment in the home: sociological studies of computation and play
2016-09-06Generative Models of Discourse
2016-09-06Consolidarity: Exploring Patterns of Social Commonality Among File Directories at Work
2016-09-06High Fidelity Image-Based Modeling
2016-09-06The Meaning of the 21st Century: A Blueprint for Ensuring Our Future           
2016-09-06Social Balance on Networks: The Dynamics of Friendship and Hatred [1/30]
2016-09-06Provably Optimal Solutions to Geometric Vision Problems
2016-09-06Interaction Design Projects for Health and Wellness
2016-09-06Congestion Games: Optimization in Competition
2016-09-06Bayesian topic models
2016-09-06A Passion for Calendars -- From the Maya to Mars
2016-09-06Persuasive Games: The Expressive Power of Videogames           
2016-09-06In-Network, Physical Adaptation of Sensor Networks
2016-09-06Secure Virtual Architecture: A Novel Foundation for Operating System Security
2016-09-06Engineering Performance Using Control Theory: A One Day How-To: Theory Part 2
2016-09-06Effective Scientific Data Management through Provenance Collection
2016-09-06Unified Dimensionality Reduction: Formulation, Solution and Beyond
2016-09-06Engineering Performance Using Control Theory: A How-To: Control Analysis & Real world applications
2016-09-06A Real-World Test-bed for Mobile Adhoc Networks: Methodology, Experimentations, Simulation & Results


Tags:
microsoft research