Posted by
(opens in new tab)Microsoft researcher Vasilis Syrgkanis (opens in new tab) 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 (opens in new tab) of the University of Virginia and Eva Tardos (opens in new tab) of Cornell University, their research, Econometrics for Learning Agents (opens in new tab), 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) conference in Portland, Ore., this week.
on-demand event
Microsoft Research Forum Episode 4
Learn about the latest multimodal AI models, advanced benchmarks for AI evaluation and model self-improvement, and an entirely new kind of computer for AI inference and hard optimization.
John Forbes Nash Jr. (opens in new tab), 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) 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.
“The Nash Equilibrium (opens in new tab) doesn’t apply to data sets in the online advertising market,” Syrgkanis said.
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.
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.
“Really, the learning is a fundamental part of the marketplace,” said David Pennock (opens in new tab), a principal researcher and assistant managing director of Microsoft Research in New York City (opens in new tab). Citing the importance of machine learning (opens in new tab) in understanding economics and economic processes, Pennock described this new approach as “a pretty big leap” toward optimizing online auctions.
While the study focused on Bing ads (opens in new tab), 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.
Syrgkanis said the research could be applied to any system where learning agents are used.
“That’s the nature of research,” Pennock said, “that things now may have a lasting impact in the years to come.”
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.
Additional papers with Microsoft contributors accepted to the conference:
Efficient Allocation via Sequential Scrip Auctions (opens in new tab)
Microsoft contributor: Gil Kalai
Greedy Algorithms make Efficient Mechanisms (opens in new tab)
Microsoft contributors: Brendan Lucier, Vasilis Syrgkanis
Information Asymmetries in Common Value Auctions with Discrete Signals (opens in new tab)
Microsoft contributor: Vasilis Syrgkanis
Simple Auctions with Simple Strategies (opens in new tab)
Microsoft contributors: Nikhil Devanur , Vasilis Syrgkanis
Randomization beats Second Price as a Prior-Independent Auction (opens in new tab)
Microsoft contributors: Hu Fu, Nicole Immorlica, Brendan Lucier
Competitive analysis via benchmark decomposition (opens in new tab)
Microsoft contributors: Nick Gravin, Pinyan Lu
Public projects, Boolean functions and the borders of Borders theorem (opens in new tab)
Microsoft contributor: Parikshit Gopalan
Improved Efficiency Guarantees in Auctions with Budgets (opens in new tab)
Microsoft contributor: Pinyan Lu
Revenue Maximization and Ex-Post Budget Constraints (opens in new tab)
Microsoft contributor: Nikhil Devanur
Estimating the causal impact of recommendation systems using observational data (opens in new tab)
Microsoft contributors: Duncan Watts, Jake Hofman
Bayesian Incentive-Compatible Bandit Explorations (opens in new tab)
Microsoft contributors: Aleksandrs Slivkins, Vasilis Syrgkanis, Yishay Mansour
Integrating Market Makers, Limit Orders, and Continuous Trade in Prediction Markets (opens in new tab)
Microsoft contributors: Sébastien Lahaie, David Pennock, Jennifer Wortman Vaughan
The Wisdom of Multiple Guesses (opens in new tab)
Microsoft contributor: Johan Ugander
Truthful Online Scheduling with Commitments (opens in new tab)
Microsoft contributors: Brendan Lucier, Ishai Menache
Markets with Production: A Polynomial Time Algorithm and a Reduction to Pure Exchange (opens in new tab)
Microsoft contributor: Ravi Kannan
Redesigning the Israeli Medical Internship Match (opens in new tab)
Microsoft contributor: Noga Alon
Price Competition, Fluctuations and Welfare Guarantees (opens in new tab)
Microsoft contributors: Moshe Babaioff, Balasubramanian Sivan
Combining Traditional Marketing and Viral Marketing with Amphibious Influence Maximization (opens in new tab)
Microsoft contributor: Wei Chen
Learning What’s Going On: Reconstructing Preferences and Priorities from Opaque Transactions (opens in new tab)
Microsoft contributor: Yishay Mansour
Making the Most of Your Samples (opens in new tab)
Microsoft contributor: Yishay Mansour
Algorithms 
Economics