{"id":183116,"date":"2007-02-07T00:00:00","date_gmt":"2009-10-31T10:19:38","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/msr-research-item\/dynamics-and-equilibria-communication-complexity-and-adaptive-heuristics\/"},"modified":"2016-09-09T09:49:28","modified_gmt":"2016-09-09T16:49:28","slug":"dynamics-and-equilibria-communication-complexity-and-adaptive-heuristics","status":"publish","type":"msr-video","link":"https:\/\/www.microsoft.com\/en-us\/research\/video\/dynamics-and-equilibria-communication-complexity-and-adaptive-heuristics\/","title":{"rendered":"Dynamics and Equilibria:  Communication Complexity and Adaptive Heuristics"},"content":{"rendered":"<div class=\"asset-content\">\n<p>Part 1: &#8220;The Communication Complexity of Uncoupled Nash Equilibrium Procedures&#8221;, by Sergiu Hart and Yishay Mansour<\/p>\n<p>http:\/\/www.ma.huji.ac.il\/hart\/abs\/comcom.html<\/p>\n<p>We study the question of how long it takes players to reach a Nash equilibrium in &#8220;uncoupled&#8221; setups, where each player initially knows only his own payoff function. We derive lower bounds on the number of bits that need to be transmitted in order to reach a Nash equilibrium, and thus also on the required number of steps. These lower bounds are exponential in the number of players. We then show that, in contrast, the communication complexity of reaching a correlated equilibrium is polynomial in the number of players.<\/p>\n<p>Part 2: &#8220;Adaptive Heuristics&#8221; (Econometrica 2005)<\/p>\n<p>http:\/\/www.ma.huji.ac.il\/hart\/abs\/heurist.html<\/p>\n<p>We exhibit a large class of simple rules of behavior, which we call adaptive heuristics, and show that they generate rational behavior in the long run. These adaptive heuristics are based on natural regret measures, and may be viewed as a bridge between rational and behavioral viewpoints.<\/p>\n<p>The results presented here, taken together, establish a solid connection between the dynamic approach of adaptive heuristics and the static approach of correlated equilibria.<\/p>\n<\/div>\n<p><!-- .asset-content --><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Part 1: &#8220;The Communication Complexity of Uncoupled Nash Equilibrium Procedures&#8221;, by Sergiu Hart and Yishay Mansour http:\/\/www.ma.huji.ac.il\/hart\/abs\/comcom.html We study the question of how long it takes players to reach a Nash equilibrium in &#8220;uncoupled&#8221; setups, where each player initially knows only his own payoff function. We derive lower bounds on the number of bits that [&hellip;]<\/p>\n","protected":false},"featured_media":194905,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr_hide_image_in_river":0,"footnotes":""},"research-area":[],"msr-video-type":[],"msr-locale":[268875],"msr-post-option":[],"msr-session-type":[],"msr-impact-theme":[],"msr-pillar":[],"msr-episode":[],"msr-research-theme":[],"class_list":["post-183116","msr-video","type-msr-video","status-publish","has-post-thumbnail","hentry","msr-locale-en_us"],"msr_download_urls":"","msr_external_url":"https:\/\/youtu.be\/H4WH3HtOdK8","msr_secondary_video_url":"","msr_video_file":"","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/183116","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-video"}],"version-history":[{"count":0,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/183116\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media\/194905"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=183116"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=183116"},{"taxonomy":"msr-video-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video-type?post=183116"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=183116"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=183116"},{"taxonomy":"msr-session-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-session-type?post=183116"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=183116"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=183116"},{"taxonomy":"msr-episode","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-episode?post=183116"},{"taxonomy":"msr-research-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-theme?post=183116"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}