We have recently modeled competitive retrieval settings as games. 2, 3 Publishers are players whose strategies are the types of documents they can write: either single-topic or multitopic documents. The search engine’s ranking function is the mediator that induces a ranking. A publisher is rewarded if her document is the highest ranked for a query. To simplify the analysis, we assumed each query is about a single topic and the distribution over queries is known to the publishers. We then examined two settings: all publishers have the same equal writing quality over all topics, and publishers have differential writing quality for different topics.

The type of documents publishers can write and the assumption regarding their writing quality entails a specific game. We assumed the ranking function has full knowledge of whether a document is relevant to a query (specifically, by topic matching) and analyzed the equilibria of the game, that is, publishers’ behavior in which modification of behavior will not be any unilaterally beneficial. We then analyzed the social welfare attained in the game, specifically, in various equilibria. Social welfare was defined as the sum of utilities attained by publishers. We assumed users’ utilities and publishers’ utilities were aligned and those were determined by whether the highest ranked document was relevant. A simple utility function was used: 1 if the highest-ranked document is relevant and 0 otherwise. 2, 3 This utility function corresponds to a setting where a user examines only the top-ranked document and her utility solely depends on the relevance of this document. The alignment between publishers’ and users’ utilities facilitates the formal treatment and corresponds to the assumption that if a user is satisfied by seeing a relevant document then the publisher of the document is rewarded to the same extent. In practice, however, publishers’ and users’ utilities are not necessarily aligned, and more evolved models are thereby called for. 2, 3

The games were further analyzed by
computing the price of anarchy: 21, 34 the
ratio between the maximal social wel-
fare that can be attained in a game and
the minimal social welfare attained in
any equilibrium of a game. In other
words, price of anarchy is the price
the echo system “pays” for the selfish
behavior of players. The accompany-
ing sidebar describes an example of a
game and its analysis.
We found that if publishers write
single-topic documents and they have
equal writing qualities for all topics
then the PRP is indeed an optimal cri-
terion for ranking. 2, 3 But, if publish-
ers write multitopic documents or
have differential writing qualities the
PRP becomes suboptimal in terms of
price of anarchy. The sidebar provides
a simple example that demonstrates
the suboptimality of the PRP. Indeed,
the PRP motivates publishers to write
single-topic documents, or documents
only on the topics they are most quali-
fied to write, as their resultant rank-
ing would be higher. Thus, the PRP
essentially does not promote content
breadth in the corpus—in terms of
topical coverage—in these natural set-
tings. Previously, we described a ca-
nonical example of this situation: the
publisher of a multitopic document,
with information unique to the docu-
ment, is driven by the PRP to remove
the unique information so as to better
focus the document for higher ranking
for queries of interest.
It turns out that introducing ran-
domization to the ranking functions
can improve the price of anarchy with
respect to that attained by using the
PRP as a ranking criterion, as random-
ization can help to promote content di-
versity. 2, 3 A case in point, promoting in
rankings a multitopic document with
respect to a single topic document, in
case the retrieval score of the latter is
a bit higher than that of the former,
does not significantly harm per-query
retrieval effectiveness but does result
in improved price of anarchy (and so-
cial welfare) due to increased content
breadth in the corpus.
These findings are especially im-
portant because they imply the most
fundamental principle used by exist-
ing retrieval methods and search en-
gines for ranking (the PRP) is subop-
timal in competitive retrieval settings.
Furthermore, these findings motivate
a new view of how ranking functions
should be learned: not (only) for mini-
mizing a “local” loss function but
rather maximizing the resultant social
welfare attained in equilibria. This is a
brand new challenge for the informa-
tion retrieval community, and other
communities interested in ranking,
as the task involves estimating post-
ranking effects. Our findings about
the merits of applying nondetermin-
istic ranking functions is a first small
step in this direction.
Characterizing a desired fair rec-
ommendation system. Heretofore, we
have mainly focused on search (retriev-
al) systems. Recommendation systems
(RSs hereinafter) have also rapidly de-
veloped over the past decade. By pre-
dicting a user preference for an item,
A simple way to demonstrate the suboptimality of the probability ranking principle
(PRP) in a game-theoretic setting is as follows: Assume two authors (players 1 and
2) who can write on two topics—that is, each player chooses between two strategies:
writing on topic A or writing on topic B. There is big user demand, U (A), to topic A, and
a slightly lower user demand U (B) = U (A) − ε, to topic B. (We assume a query is about
a single topic and the demand represents the distribution over queries.) Player 1 can
write with optimal quality ( 1) on both topics, while player 2 can write with close to
optimal quality ( 1 − ε) on topic A but with really poor quality (ε) on topic B. The authors’
gain (utility) is the quality of their writing times the demand they get on the topic for
which they are ranked the highest. The total users’ satisfaction (social welfare) however
is the overall total quality over both topics. According to the PRP, the higher-quality
document is ranked first for a query for each topic. In this game, the only equilibrium is
for player 1 to write on topic A, and for player 2 to write on topic B; in this case the total
users’ satisfaction is not much more than half of the total social welfare (satisfaction)
the users could get (that is, the price of anarchy is slightly less than 2). The PRP simply
gives no chance to player 2, who could be writing so well on topic A, although this is the
only topic he writes well about.
A Simple Example of the
Non-Optimality of the PRP