{"id":3311,"date":"2015-06-19T11:30:00","date_gmt":"2015-06-19T11:30:00","guid":{"rendered":"https:\/\/blogs.technet.microsoft.com\/inside_microsoft_research\/2015\/06\/19\/award-winning-theory-from-microsoft-researcher-goes-beyond-famous-nash-equilibrium\/"},"modified":"2016-07-20T07:29:13","modified_gmt":"2016-07-20T14:29:13","slug":"award-winning-theory-from-microsoft-researcher-goes-beyond-famous-nash-equilibrium","status":"publish","type":"post","link":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/blog\/award-winning-theory-from-microsoft-researcher-goes-beyond-famous-nash-equilibrium\/","title":{"rendered":"Award-winning theory from Microsoft researcher goes beyond famous Nash Equilibrium"},"content":{"rendered":"

Posted by George Thomas Jr.<\/span><\/p>\n

\" (opens in new tab)<\/span><\/a>Microsoft researcher Vasilis Syrgkanis (opens in new tab)<\/span><\/a> and two colleagues this week unveiled a new approach to understanding and optimizing online bidding and auctions, with implications far beyond the online advertising marketplace in which their study was based.<\/p>\n

Working with Denis Nekipelov (opens in new tab)<\/span><\/a> of the University of Virginia and Eva Tardos (opens in new tab)<\/span><\/a> of Cornell University, their research, Econometrics for Learning Agents (opens in new tab)<\/span><\/a><\/em>, goes beyond the long-standing approach of applying the famous Nash Equilibrium when analyzing online interactions. It was the only submission to receive the Best Paper award at the ACM Economics and Computation 2015 (opens in new tab)<\/span><\/a> conference in Portland, Ore., this week.<\/p>\n

John Forbes Nash Jr. (opens in new tab)<\/span><\/a>, famously portrayed by Russell Crowe in the award-winning film “A Beautiful Mind,” won the Nobel Prize in 1994 for his game theory (opens in new tab)<\/span><\/a> insight that a group of players are in equilibrium if they are making the best decisions possible, assuming no player has anything to gain by changing their strategy. This approach, however, is based on static assumptions, but the state of dynamic marketplaces are seldom static or in equilibrium.<\/p>\n

“The Nash Equilibrium (opens in new tab)<\/span><\/a> doesn’t apply to data sets in the online advertising market,” Syrgkanis said.<\/p>\n

Instead, he and his colleagues demonstrated how learning model agents can better optimize online auctions in the advertising space, assuming algorithms, not humans, are doing the bidding.<\/p>\n

Rather than rely on the Nash Equilibrium, this new approach assumes all participants merely understand the rules of the game, makes no assumptions about the other bidders and continually learns from changes in the dynamic environment.<\/p>\n

“Really, the learning is a fundamental part of the marketplace,” said David Pennock (opens in new tab)<\/span><\/a>, a principal researcher and assistant managing director of Microsoft Research in New York City (opens in new tab)<\/span><\/a>. Citing the importance of machine learning (opens in new tab)<\/span><\/a> in understanding economics and economic processes, Pennock described this new approach as “a pretty big leap” toward optimizing online auctions.<\/p>\n

While the study focused on Bing ads (opens in new tab)<\/span><\/a>, Syrgkanis said their approach could be applied “wherever you have any electronic market where bidding is applied algorithmically,” such as in financial markets, when buying a stock at an optimal price.<\/p>\n

Syrgkanis said the research could be applied to any system where learning agents are used.<\/p>\n

“That’s the nature of research,” Pennock said, “that things now may have a lasting impact in the years to come.”<\/p>\n

Pennock and Syrgkanis represent a small part of Microsoft’s presence at the conference. They’re joined by colleagues who are presenting papers and conducting workshops and tutorials on multiple topics related to the intersection of economics and computation.<\/p>\n

Additional papers with Microsoft contributors accepted to the conference:<\/h2>\n

Efficient Allocation via Sequential Scrip Auctions (opens in new tab)<\/span><\/a><\/em>
\nMicrosoft contributor: Gil Kalai<\/p>\n

Greedy Algorithms make Efficient Mechanisms (opens in new tab)<\/span><\/a><\/em>
\nMicrosoft contributors: Brendan Lucier, Vasilis Syrgkanis<\/p>\n

Information Asymmetries in Common Value Auctions with Discrete Signals (opens in new tab)<\/span><\/a><\/em>
\nMicrosoft contributor: Vasilis Syrgkanis<\/p>\n

Simple Auctions with Simple Strategies (opens in new tab)<\/span><\/a><\/em>
\nMicrosoft contributors: Nikhil Devanur , Vasilis Syrgkanis<\/p>\n

Randomization beats Second Price as a Prior-Independent Auction (opens in new tab)<\/span><\/a><\/em>
\nMicrosoft contributors: Hu Fu, Nicole Immorlica, Brendan Lucier<\/p>\n

Competitive analysis via benchmark decomposition (opens in new tab)<\/span><\/a><\/em>
\nMicrosoft contributors: Nick Gravin, Pinyan Lu<\/p>\n

Public projects, Boolean functions and the borders of Borders theorem (opens in new tab)<\/span><\/a><\/em>
\nMicrosoft contributor: Parikshit Gopalan<\/p>\n

Improved Efficiency Guarantees in Auctions with Budgets (opens in new tab)<\/span><\/a><\/em>
\nMicrosoft contributor: Pinyan Lu<\/p>\n

Revenue Maximization and Ex-Post Budget Constraints (opens in new tab)<\/span><\/a><\/em>
\nMicrosoft contributor: Nikhil Devanur<\/p>\n

Estimating the causal impact of recommendation systems using observational data (opens in new tab)<\/span><\/a><\/em>
\nMicrosoft contributors: Duncan Watts, Jake Hofman<\/p>\n

Bayesian Incentive-Compatible Bandit Explorations (opens in new tab)<\/span><\/a><\/em>
\nMicrosoft contributors: Aleksandrs Slivkins, Vasilis Syrgkanis,\u00a0Yishay Mansour<\/p>\n

Integrating Market Makers, Limit Orders, and Continuous Trade in Prediction Markets (opens in new tab)<\/span><\/a><\/em>
\nMicrosoft contributors: S\u00e9bastien Lahaie, David Pennock,\u00a0 Jennifer Wortman Vaughan<\/p>\n

The Wisdom of Multiple Guesses (opens in new tab)<\/span><\/a><\/em>
\nMicrosoft contributor: Johan Ugander<\/p>\n

Truthful Online Scheduling with Commitments (opens in new tab)<\/span><\/a><\/em>
\nMicrosoft contributors: Brendan Lucier, Ishai Menache<\/p>\n

Markets with Production: A Polynomial Time Algorithm and a Reduction to Pure Exchange (opens in new tab)<\/span><\/a><\/em>
\nMicrosoft contributor: Ravi Kannan<\/p>\n

Redesigning the Israeli Medical Internship Match (opens in new tab)<\/span><\/a><\/em>
\nMicrosoft contributor: Noga Alon<\/p>\n

Price Competition, Fluctuations and Welfare Guarantees (opens in new tab)<\/span><\/a><\/em>
\nMicrosoft contributors: Moshe Babaioff, Balasubramanian Sivan<\/p>\n

Combining Traditional Marketing and Viral Marketing with Amphibious Influence Maximization (opens in new tab)<\/span><\/a><\/em>
\nMicrosoft contributor: Wei Chen<\/p>\n

Learning What’s Going On: Reconstructing Preferences and Priorities from Opaque Transactions (opens in new tab)<\/span><\/a><\/em>
\nMicrosoft contributor:\u00a0Yishay Mansour<\/p>\n

Making the Most of Your Samples (opens in new tab)<\/span><\/a><\/em>
\nMicrosoft contributor:\u00a0Yishay Mansour<\/p>\n","protected":false},"excerpt":{"rendered":"

Posted by George Thomas Jr. Microsoft researcher Vasilis Syrgkanis and two colleagues this week unveiled a new approach to understanding and optimizing online bidding and auctions, with implications far beyond the online advertising marketplace in which their study was based. Working with Denis Nekipelov of the University of Virginia and Eva Tardos of Cornell University, […]<\/p>\n","protected":false},"author":30766,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr-author-ordering":[],"msr_hide_image_in_river":0,"footnotes":""},"categories":[194466,194467,194479,194455,194465],"tags":[187373,200641,201247,201391,201401,201403,202413,186418,202983,203141,203145,203147,204475],"research-area":[13561,13548],"msr-region":[],"msr-event-type":[],"msr-locale":[268875],"msr-post-option":[],"msr-impact-theme":[],"msr-promo-type":[],"msr-podcast-series":[],"class_list":["post-3311","post","type-post","status-publish","format-standard","hentry","category-algorithms","category-artifical-intelligence","category-economics","category-machine-learning","category-theory","tag-art","tag-best-paper-award-acm-economics-and-computation-2015","tag-david-pennock","tag-e-commerce","tag-econometrics-for-learning-agents","tag-economics-and-computing","tag-learning-model-agents","tag-machine-learning","tag-nash-equilibrium","tag-online-advertising","tag-online-auctions","tag-online-bidding","tag-vasilis-syrgkanis","msr-research-area-algorithms","msr-research-area-economics","msr-locale-en_us"],"msr_event_details":{"start":"","end":"","location":""},"podcast_url":"","podcast_episode":"","msr_research_lab":[],"msr_impact_theme":[],"related-publications":[],"related-downloads":[],"related-videos":[],"related-academic-programs":[],"related-groups":[],"related-projects":[],"related-events":[],"related-researchers":[],"msr_type":"Post","byline":"","formattedDate":"June 19, 2015","formattedExcerpt":"Posted by George Thomas Jr. Microsoft researcher Vasilis Syrgkanis and two colleagues this week unveiled a new approach to understanding and optimizing online bidding and auctions, with implications far beyond the online advertising marketplace in which their study was based. Working with Denis Nekipelov of…","locale":{"slug":"en_us","name":"English","native":"","english":"English"},"_links":{"self":[{"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/posts\/3311","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/users\/30766"}],"replies":[{"embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/comments?post=3311"}],"version-history":[{"count":1,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/posts\/3311\/revisions"}],"predecessor-version":[{"id":235653,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/posts\/3311\/revisions\/235653"}],"wp:attachment":[{"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/media?parent=3311"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/categories?post=3311"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/tags?post=3311"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=3311"},{"taxonomy":"msr-region","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-region?post=3311"},{"taxonomy":"msr-event-type","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-event-type?post=3311"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=3311"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=3311"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=3311"},{"taxonomy":"msr-promo-type","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-promo-type?post=3311"},{"taxonomy":"msr-podcast-series","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-podcast-series?post=3311"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}