equilibria in airline markets. Econometrica 77, 6
14. Cole, R., Roughgarden, T. The sample complexity of
revenue maximization. ACM S TOC, (2014), 243–252.
15. Cummings, R., Ligett, K., Nissim, K., Roth, A., Wu,
Z. Adaptive learning with robust generalization
guarantees. In 29th Annual Conference on Learning
Theory, (2016), 772–814.
16. Edelman, B., Ostrovsky, M., Schwarz, M. Internet
advertising and the generalized second-price auction.
American Economic Review 97, 1 (2007), 242–259.
17. Freund, Y., Hsu, D. A new Hedging algorithm and
its application to inferring latent random variables.
18. Hart, S., Mas-Colell, A. A simple adaptive procedure
leading to correlated equilibrium. Econometrica 68,
19. Hartline, J., Syrgkanis, V., Tardos, É. No-Regret Learning
in Repeated Bayesian Games, Advances in Neural
Information Processing Systems 28 (NIPS 2015).
20. Hoy, D., Syrgkanis, V., Nekipelov, D. Robust data-driven
efficiency guarantees in auctions. arXiv:1505.00437, 2015
21. Kesselheim, T., Kleinberg, R., Tardos, E. Smooth online
mechanisms: a game-theoretic problem in renewable
energy markets, EC’ 15, 203–220, 2015.
22. Kleinberg, R., Piliouras, G., Tardos, E. Load balancing
without regret in the bulletin board model. Distributed
Computing 24, 1 (2011), 21–29.
23. Koutsoupias, E., Papadimitriou, C. Worst-case equilibria,
In Proceedings of the 16th Annual Symposium on
Theoretical Aspects of Computer Science (1999),
24. Lahaie, S. Mcafee, P. Efficient Ranking in Sponsored
Search, Internet and Network Economics (2011),
25. Lewis, R. Rao, J. The unfavorable economics of measuring
the returns to advertising, SSRN 2367103, 2014.
26. Littlestone, N. Warmuth, M. The weighted majority
algorithm. Information and Computation 108, 2
27. Lykouris, T., Syrgkanis, V., Tardos, É. Learning and
efficiency in games with dynamic population. SODA’ 16,
28. Morgenstern, J., Roughgarden, T. On the pseudo-dimension of nearly optimal auctions. NIPS’ 15,
29. Muthukrishnan, S. Ad exchanges: research issues.
Internet and Network Economics, 1–12, Springer, 2009.
30. Aggarwal, G. Muthukrishnan, S. Theory of sponsored
search auctions. foundations of computer science,
2008, FOCS’08. IEEE 49th Annual IEEE Symposium
on. IEEE, 2008.
31. Muthukrishnan, S. Internet ad auctions: insights and
directions. Automata, Languages and Programming,
14–23, Springer, 2008.
32. Myerson, R. Optimal auction design. Mathematics of
Operations Research 6, 1 (1981), 58–73.
33. Nekipelov, D., Syrgkanis, V., Tardos, E. Econometrics
for learning agents, EC ‘ 15, 1–18, 2015.
34. Ostrovsky, M., Schwarz, M. Reserve prices in internet
advertising auctions: a field experiment. EC’ 11, 59–60, 2011.
35. Lewis, R., Rao, J., Reiley, D. Measuring the Effects of
Advertising: The Digital Frontier, Economic Analysis
of the Digital Economy. University of Chicago Press,
36. Roughgarden, T. Intrinsic robustness of the price of
anarchy, Journal of the ACM 62, 5 (2015), article No. 32.
37. Syrgkanis, V., Tardos, É. Composable and efficient
mechanisms STOC ‘ 13, 211–220, 2013.
38. Ballings, M., Van den Poel, D. CRM in social media:
predicting increases in facebook usage frequency. Eur. J.
Oper. Res. 244, 1 (2015), 248–260.
39. Fulgoni, G., Lipsman, A. Numbers, please: digital game
changers: how social media will help usher in the era
of mobile and multi-platform campaign-effectiveness
measurement. J. Advert. Res. 54, 1 (2014), 11–16.
40. Xu, J., Forman, C., Kim, J.B., Van Ittersum, K. News
media channels: complements or substitutes? evidence
from mobile phone usage. J. Mark. 78, 4 (2014), 97–112.
41. Varian, H. Online ad auctions. Am. Econ. Rev. 99, 2
Denis Nekipelov ( firstname.lastname@example.org) is an associate
professor in the departments of Economics and Computer
Science at the University of Virginia, Charlottesville.
Tammy Wang ( email@example.com) is VP
of Data Science and Analytics at Riviera Partners,
San Francisco, CA.
© 2017 ACM 0001-0782/17/07 $15.00
caused by the ad). This is because search
engines, quite naturally, do not want to
rest a pricing solution on the estimates
with a large amount of noise with millions, if not billions, of dollars at risk.
The current practice is for advertisers to
figure their true return to advertising for
themselves. This approach is inefficient
because the platform possesses far
more information to conduct the inference, and thus is in a much better position conduct price-to-value conversion.
New generations of platform design
will break through the bottleneck of
the inefficiency leading to a decreased
loss of social welfare and a potential
increase in the platform revenue.
The detailed logging of digital advertising, combined with scale achieved
on major platforms, opens the potential for new observational methods
that could fulfill the promise of routinely measuring advertising effectiveness in an unbiased, precise manner.
Inference of user intentions and prediction of user actions are exceedingly
difficult outside of search engines
where advertisers explicitly specify
queries as proxy of intention. In social-,
entertainment-, or task-oriented contexts, rendering potential advertisers
in front of a user via dynamic mechanism is the most efficient, but not an
easily implementable approach. 38
While advertisers and advertising
platforms clearly move to performance-
based pricing, the user behavior is
becoming more complex. Current
trends show that device usage will con-
tinue to change how users consume
information, enjoy leisure time, and
communicate with each other (see
Fulgoni and Lipsman39 and Xu et al. 40).
In this context, the advertising ecosys-
tem is evolving. Brands have changed
ad formats to engage and interact with
users in-video, in-game, and in other
dynamic content. The hyper-local
nature of mobile applications provides
a new type of a signal about the user.
This more refined user information, in
turn, changes the composition of adver-
tisers. The typical persona an advertiser
has shifted from large business entities
like big-name brands or e-commerce
platforms on Google and Facebook, to
deep vertically integrated profession-
als. For example, on Yelp, Zillow, or
Grubhub, advertisers are small busi-
ness owners or individual professionals
like real estate agents or plumbers.
These business users do not have the
sophisticated business knowledge or
technology skills to aid them in ad cam-
paign management. The user actions
relevant for these new breeds of adver-
tisers shifted away from clicks to in-app
text, direct call, or email communica-
tion. Ideally, new vertical marketplaces
will provide users with better experi-
ences and advertisers with more accu-
rate user intent and direct access to
relevant users. But, it requires adver-
tising platforms to adapt and evolve.
Advanced machine learning technol-
ogy is essential for these new platforms
to accurately account for user actions
with a large volume of data points
across devices. Another key necessity is
the design of new auction mechanisms
that encompass the need to provide the
advertisers with simple and easy ways
to manage work flows. The technologi-
cal change that has been occurring over
the past decade creates the need for
new platforms that are both grounded
in the game theory but also account for
complex behavioral responses of users
The authors are indebted to Éva Tardos
who suggested the theme of this article
and helped them shape it.
1. Aradillas-Lopez, A. Tamer, E. The identification power
of equilibrium in simple games. J. Bus. Econ. Stat. 26,
3 (2008), 261–283.
2. Arora, S., Hazan, E., Kale, S. The multiplicative weights
update method: A meta-algorithm and applications.
Theory of Computing 8, (2012), 121–164.
3. Athey, S. Nekipelov, D. A Structural Model of Sponsored
Search Advertising Auctions. AdAuctions’ 10, 2010.
4. Bajari, P., Hong, H., Nekipelov, D. Game theory and
econometrics: a survey of some recent results, Advances
in Economics and Econometrics 3, (2013), 3–52.
5. Bajari, P., Hong, H., Krainer, M., Nekipelov, D. Estimating
static models of strategic interactions, J. Bus. Econ.
6. Beresteanu, A., Molchanov, I., Molinari, F. Sharp
identification regions in models with convex moment
predictions. Econometrica 79, (2011), 1785–1821.
7. Blake, T., Nosko, C., Tadelis, S. Customer heterogeneity
and paid search effectiveness: a large scale field
experiment. Econometrica 83, 1 (2015), 155–174.
8. Blum, A., Even-Dar, E., Ligett, K. Routing without regret:
on convergence to Nash equilibria of regret-minimizing
algorithms in routing games. PODC ‘06, 45–52,
9. Blum, A., Hajiaghayi, M., Ligett, K., Roth, A. Regret
minimization and the price of total anarchy. ACM
STOC, (2008), 373–382.
10. Blum, A., Mansour, Y. From external to internal regret.
J. Mach. Learn. Res. 8, (2007), 1307–1324.
11. Blum, A. Mansour, Y. Learning, regret minimization,
and equilibria. In Algorithmic Game Theory. N. Nisan
et al. eds. Cambridge University Press, 2007, 79–101.
12. Caragiannis, I., Kaklamanis, C., Kanellopoulos, P.,
Kyropoulou, M., Lucier, B., Paes Leme, R., Tardos, E.
Bounding the inefficiency of outcomes in generalized
second price auctions. J. Econ. Theo. 156, (2015),
13. Ciliberto, F., Tamer, E. Market structure and multiple