Applications of Learning Theory in Algorithmic Game Theory

author: Tim Roughgarden, Computer Science Department, Stanford University
published: Aug. 20, 2015,   recorded: July 2015,   views: 4175
Categories

Slides

Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.
  Bibliography

Description

Algorithmic game theory is a field that uses and extends tools from economics and game theory to reason about fundamental computer science problems. The field is important both for its applications, which span the gamut from network routing to online advertising, and for its remarkably diverse and rich connections to other areas of theoretical computer science, including complexity theory and approximation algorithms. In this talk, we survey two ways in which definitions and tools from learning theory have been crucial to recent advances in algorithmic game theory. First, we outline a theory of robust bounds on the "price of anarchy" --- meaning approximation guarantees for game-theoretic equilibria --- that apply to all outcome sequences generated by no-regret learners playing a multi-player game. Second, we explain how to use concepts from learning theory to make traditional (Bayesian) optimal auction theory operational, replacing the practically problematic "common prior" assumption with a data-driven approach.

See Also:

Download slides icon Download slides: colt2015_roughgarden_game_theory_01.pdf (583.2┬áKB)


Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Reviews and comments:

Comment1 Edgar, December 22, 2019 at 8:45 a.m.:

Building new games you should always need some great concept behind it. Which will lead you to the best suggestion in games? I share my thoughts with https://www.rushmypapers.me/ and they appreciate it.


Comment2 shawnkemp, March 20, 2020 at 10:14 p.m.:

This article is really contains lot more information about This Topic. We have read your all the information some points are also good and some https://www.assignmentuk.co.uk/write-... usually are awesome. Great post I would like to thank you for the efforts you have ma


Comment3 jonathantrott, March 27, 2020 at 9:43 p.m.:

I will always let you and your words become part of my day because you never know how much you make my day happier and more complete. There are even times when I feel so down but I will feel better https://www.glamourjackets.com/men-de... right after checking your blogs. You have made me feel so good about myself all the time and please know that I do appreciate everything that you have


Comment4 shawnkemp, April 1, 2020 at 1:15 a.m.:

This article is really contains lot more information about This Topic. We have read your all the information some points are also good and some usually are awesome. Great post I would like to thank you for www.topcelebrityjackets.com/ryan-gosl... the efforts you have ma


Comment5 lauratrott, April 1, 2020 at 1:51 a.m.:

It is good to hear that your store is now expanding to new locations. I have been a patron of Fantastic Eyes because of all the wonderful work that you guys do. I hope that this expansion move of yours will https://www.uhjackets.com/blade-runne... turn out to be successful. I will definitely go and see this new store of yours

Write your own review or comment:

make sure you have javascript enabled or clear this field: