Lecturers Nicola Gatti (nicola.gatti at polimi dot it) Marcello Restelli (marcello.restelli at polimi dot it)
Course description Internet monetization is an emerging new scientific sub-discipline, at the intersection of large scale search and text analysis, information retrieval, statistical modeling, machine learning, classification, optimization, and microeconomics. The central problem of internet monetization is to find the "best match" between a given user in a given context and a suitable advertisement. The context could be a user entering a query in a search engine ("sponsored search"), a user reading a web page ("content match" and "display ads"), a user watching a movie on a portable device, and so on. The information about the user can vary from scarily detailed to practically nil. The number of potential advertisements might be in the billions. Thus, depending on the definition of "best match" this problem leads to a variety of massive optimization and search problems, with complicated constraints, and challenging data representation and access problems. The solution to these problems provides the scientific and technical foundations for the $20 billion online advertising industry.
Detailed program of the course, hand notes, and exercises 0) Introduction (slides) 1) Computational (micro)economic foundations 1.1) Game theory (notes - exercises) 1.1.1) Strategic-form model 1.1.2) Equilibrium in dominant strategies 1.1.3) Nash equilibrium 1.1.4) Bayes-Nash equilibrium [advanced topic] 1.2) Economic mechanisms (notes - exercises) 1.2.1) Mechanism model 1.2.2) Revelation principle and direct-revelation mechanisms 1.2.3) Implementation in dominant strategies: Groves' mechanisms 1.2.4) Properties of Groves' mechanisms (impossibilities and generality) 1.2.5) Desirable properties 1.2.6) Linear environment and Myerson's monotonicity [advanced topic] 1.2.7) Maximal-in-its-range mechanisms 1.3) Computational complexity and algorithms (notes) 1.3.1) Algorithms and complexity 1.3.2) P vs NP 1.3.3) NP-completeness 1.3.4) SAT and 3SAT [advanced topic] 1.3.5) SAT and INDSET [advanced topic] 2) Auction mechanisms for the Web 2.1) Matching markets (notes - exercises) 2.1.1) Bipartite graphs 2.1.2) Matching problem and perfect matching 2.1.3) Assignment problem 2.1.4) Hungarian algorithm 2.1.5) Clearing-market prices 2.1.6) Examples: NetFlix 2.2) Sponsored search auctions (data - notes - exercises) 2.2.1) Basic model 2.2.2) Position-dependent externalities 2.2.3) Cascade models 2.2.4) General externalities 2.2.5) Examples: AdWords and AdSense 2.3) Combinatorial auctions (notes - exercises) 2.3.1) Model 2.3.2) NP-hardness [advanced topic] 2.3.3) Searching algorithm 2.3.4) Examples 2.4) Markets with intermediaries (notes - exercises) 2.4.1) Model of trading on networks 2.4.2) Equilibrium in trading: perfect competition and implicit perfect competition 2.4.3) Relation with VCG auction 2.4.4) Social welfare 2.4.5) Traders' profit 2.4.6) Examples: Ad exchange and real-estate market 2.5) Double auctions (notes - exercises) 2.5.1) VCG weakness 2.5.2) McAfee double auction 2.5.3) Examples 3) Information cascades and social influence (notes) 3.1) Network effects 3.2) Information cascades 3.3) Power-laws 3.4) Rich-get-richer phenomena 3.5) Cascading behavior in networks 3.6) Small-world phenomena 3.7) Epidemics 3.8) Viral marketing 4) Learning 4.1) Introduction (slides) 4.2) Markov Decision Problems (slides) 4.3) Reinforcement learning (slides) 4.4) Multi-armed bandits (slides)
Suggested textbooks “Networks, Crowds, and Markets: Reasoning About a Highly Connected World” by David Easley and Jon Kleinberg (website)
Lecture notes (by students) Notes (pdf; warning: these notes could contain some mistakes, as well as they could contain additional arguments than those discussed during the lectures) Exercises (pdf; warning: these exercises are not complete) Further readings (pdf)
Thesis topics A number of thesis topics are available on all the themes discussed in the course. We suggest the interested students to ask both lecturers for further information and details.
Related courses r“Introduction to computational advertising” at Stanford University (website) “Market & Social Systems on the Internet” at University of Pennsylvania (website) “Economics and computation” at Harvard University and MIT (website)