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-