Introduction to Computational Advertising

Tutors: Evgeniy Gabrilovich and Vanja Josifovski
Yahoo! Research, Computational Advertising and Search Technology Group

Web advertising is the primary driving force behind many Web
activities, including Internet search as well as publishing of online
content by third-party providers. A new discipline - Computational
Advertising - has recently emerged, which studies the process of
advertising on the Internet from a variety of angles. A successful
advertising campaign should be relevant to the immediate user's
information need as well as more generally to user's background and
personalized interest profile, be economically worthwhile to the
advertiser and the intermediaries (e.g., the search engine), as well
as be aesthetically pleasant and not detrimental to user experience.

The tutorial does not assume any prior knowledge of Web advertising,
and will begin with a comprehensive background survey of the topic. In
this tutorial, we focus on one important aspect of online advertising,
namely, contextual relevance. It is essential to emphasize that in
most cases the context of user actions is defined by a body of text,
hence the ad matching problem lends itself to many NLP methods. At
first approximation, the process of obtaining relevant ads can be
reduced to conventional information retrieval, where one constructs a
query that describes the user's context, and then executes this query
against a large inverted index of ads. We show how to augment the
standard information retrieval approach using query expansion and text
classification techniques. We demonstrate how to employ a relevance
feedback assumption and use Web search results retrieved by the query.
This step allows one to use the Web as a repository of relevant
query-specific knowledge. We also go beyond the conventional bag of
words indexing, and construct additional features using a large
external taxonomy and a lexicon of named entities obtained by
analyzing the entire Web as a corpus. Computational advertising poses
numerous challenges and open research problems in text summarization,
natural language generation, named entity extraction, computer-human
interaction, and others. The last part of the tutorial will be devoted
to recent research results as well as open problems, such as
automatically classifying cases when no ads should be shown, handling
geographic names, context modeling for vertical portals, and using
natural language generation to automatically create advertising
campaigns.

Economic Aspects of Social Networks

Tutors: Brian Rogers and Florian Herold
MEDS, Kellogg School of Management, Northwestern University

Many mechanisms that mediate the interests of economic agents rely,
either implicitly or explicitly, on a particular pattern of feasible
interactions. Properly accounting for this observation leads to a
rich variety of models in which predictions often diverge from those
of more traditional analyses. Moreover, they allow the researcher to
study the issue of how outcomes depend on the particular structure of
the network of interactions. This tutorial will focus on recent
advances and applications of network analysis in the economics
literature, although we will also highlight important contributions
from statistical physics, sociology and mathematics. Topics include
strategic network formation, random graph theoretic models of social
networks, diffusion, learning, and games played on a network
structure. We will also discuss relationships to percolation theory.
While the material will be mostly self-contained, a familiarity with
basic probability and game theory will be useful.

Communication Requirements of Economic Mechanisms

Tutors:
Liad Blumrosen, Microsoft Research, Silicon Valley
Ilya Segal, Department of Economics, Stanford University

Asymmetric information is a central problem in economic environments:
some information is available to a sub-set of the players and not to
others. Markets are designed to overcome this problem by communicating
information between the participants until some system-wise goal is
achieved. For example, search engines match advertisers to ad slots
based on their reported values for keywords, and the FCC allocates
spectrum licenses according to the demand of the bidders at various
price levels presented to them.

One of the exciting lines of research on the interplay of computer
science and economics analyzes the role of information and
communication in such environments. This line of research is motivated
by real-life problems, and provides guidelines for the design of
electronic marketplaces. In this tutorial, we will survey recent
results in this area of research, and characterize tradeoffs between
informational simplicity and expressive communication. The tutorial
will touch the information requirements of various allocation rules,
with and without incentive constraints, and also discuss the power of
several natural communication schemes (like posted prices,
discriminatory prices and ascending-price auctions). The main open
questions in this area of research will be highlighted.

Automated Mechanism Design: Approaches and Applications

Tutors:
Vincent Conitzer, Department of Computer Science and Department of Economics, Duke University
Yevgeniy Vorobeychik, Department of Computer Science, University of Michigan

The field of mechanism design has had considerable impact over the
years, particularly in enlightening the design of complex auctions
such as the FCC auction for selling wireless spectrum licenses.
Nevertheless, as useful as theory has been in providing intuition, it
has also occasionally created much confusion when attempts have been
made to apply it in practice. One problem is that while the
theoretical literature has much to say about mechanism design with the
objective of maximizing efficiency, it has considerably less to say
about revenue maximizing auctions in general settings, and almost
nothing for more esoteric objectives. In practice, it appears that
the esoteric objectives often dominate design considerations, either
because of the specific context in which the design choices are made,
or because the true notion of social welfare is too difficult to
quantify, and the designer attempts to use proxy objectives in its
stead.

Automated mechanism design (AMD) is an attempt to address the issue of
designing mechanisms computationally for arbitrary objective
functions. In this tutorial, we describe the AMD problem in two
settings. First, we assume that the outcome and type sets are finite
for all players. In that case, randomized mechanisms can be designed
in polynomial time, for example, using linear programming, whereas
designing deterministic mechanisms is NP-Hard. Second, we assume that
the designer has control over a finite set of continuous parameters,
and the sets of outcomes and player types are infinite. In this
setting, AMD can be formulated as a stochastic black-box optimization
problem and solved using stochastic search techniques such as
simulated annealing. In addition, we review the work in automated
mechanism design when only partial type information is revealed and
describe a series of applications of the various approaches.