vide an algorithm that most users will
find more compelling than the classical one, when they have to choose. We
now discuss two achievements that
have been obtained in this regard.
Best-response regression. An interesting extension of this general discussion is in the context of machine
learning, and in particular regression
tasks. In a regression task, a predictor is given a set of instances (points)
along with a real value for each point.
Subsequently, she must identify the
value of a new instance as accurately as
possible. Ben-Porat and Tennenholtz4
considered a regression task tackled
by two players, where the payoff of
each player is the proportion of the
points she predicts more accurately
than the other player. On the technical side, in order to do so, the authors
revise the probably approximately
correct (PAC) learning framework to
deal with the case of a duel between
two predictors. Then they devise an
algorithm that finds a linear regression predictor that is a best response
to any (not necessarily linear) regression algorithm. This algorithm has
linearithmic sample complexity, and
polynomial time complexity when the
dimension of the instances domain
is fixed. The approach has been also
tested in a high-dimensional setting,
and it has been shown to significantly
defeat classical regression algorithms
in the prediction duel.
Responding to a strong ranker.
Returning to the search and ranking
motivation, here is a fundamental interesting question. Say a search engine
has a relatively weak (somewhat ineffective) relevance ranking function;
specifically, with respect to that of
another (strong) search engine. This
could be, for example, due to a relatively small user base: indeed, user engagement signals are important features in
relevance-ranking functions.
Thus, an interesting duel between
the two search engines emerges. The
duel entails an interesting bimodal
utility function for the weak search en-
gine: the goal is to produce in response
to a query a document result list whose
effectiveness is not significantly lower
than that of the strong search engine;
and, the result list should also be
quite different than that produced by
the strong engine. In Izsak et al., 17 we
RSs have been successfully applied in
a variety of applications. However, in
order to address significant applica-
tions, where information is integrated
from many sources, such systems have
to generate recommendations that sat-
isfy the needs of both the end users and
other parties, and in particular content
providers (publishers). Many of the
content providers provide sponsored
or partially sponsored content that may
be relevant to a user, and an RS that will
not be fair with content providers, will
not survive.
Hence, an RS should be able to
deal in a fair way with strategic content providers, each of which aims
at maximizing its exposure. In addition, if an RS is not designed properly, then content providers may reach
a fluctuating system where content
providers rapidly change the type of
content they provide only to defeat
their competitors. Therefore, the
RS need not only be fair but to also
yield stability, that is, convergence
to equilibrium of content providers’
strategies. These RS requirements
were only formulated very recently
in a rigorous manner. 5 It has been
shown that classical RSs, which operate in the PRP style (that is, always
show the most relevant content) fail
to satisfy the requirements noted
here (that is, will be unfair or lead to
fluctuations). Indeed, the latter work
also shows a particular RS, selecting
among content providers in a well-defined probabilistic manner, that
does satisfy the related requirements, and in a sense is the only
recommendation system that satis-fies them. Technically, the results
use a classical concept in cooperative game theory, the Shapley value, 37
which measures the contribution
of parties to a cooperative act, and
adapt it to serve as an efficient mechanism for probabilistic selection
among content providers.
These findings complement the
observation about the failure of the
most fundamental principle used
by existing retrieval methods and
search engines for ranking (the PRP),
by showing that the corresponding
method also fails in the context of rec-
ommendation systems. It is subopti-
mal when considering strategic con-
tent providers. Indeed, well-defined
and well-grounded probabilistic sub-
stitutes are offered.
Dueling
So far we have dealt with the design
of systems, a.k.a. mechanisms or mediators, while taking into account that
participants in these systems (
specifically, publishers/content generators)
are self-motivated. Indeed, the role
of a search engine, as well as the role
of a RS, which integrate information
from different content providers, is to
serve as a mediator among selfish participants. However, such mechanisms
may also face a competition with other
mechanisms as we will discuss. Thus,
we now describe models that address
such competitions (specifically, between search engines/ranking functions and between prediction algorithms). In these settings, the systems
themselves can be thought of as the
players, in contrast to the settings discussed thus far where publishers were
the players.
Consider two competing search engines. A user thinks of a desired Web
page and submits a query intended to
target such a page to both search engines. The engine that ranks the desired page higher is chosen by the user
as the “winner.” Given a probability
distribution over the users as for their
desired pages given that query, the
optimal algorithm ranks the pages,
ω1,ω2, . . . ,ωn, in a decreasing order of
the corresponding probabilities; this
is essentially the probability ranking
principle (PRP). However, in a competitive setting the ranking ω2,ω3, . . . ,ωn,
ω1 wins (assuming the proportion of
users interested in ω1 is less than 0.5)
on every item that may be searched except for ω1. This is a highly simplified
example of the fact that different data
science mechanisms are in competition with one another, and therefore
the optimal way to design them should
be reconsidered.
Such setting was formalized first
in Immorlica et al., 16 under the title
dueling algorithms. The most basic
building block in such settings is to
consider a state-of-the-art algorithm
(for example, a ranker in the information retrieval setting, a regressor in a
prediction setting) and see if it can be
defeated when put in a competitive
setting; such as, whether one can pro-