On the Convergence of No-Regret Dynamics in Information Retrieval Games with Proportional Ranking Functions

## Abstract

Abstract Publishers who publish their content on the web act strategically, in a behavior that can be modeled within the online learning framework.
Regret, a central concept in machine learning, serves as a canonical measure for assessing the performance of learning agents within this framework.
We prove that any proportional content ranking function with a concave activation function induces games in which no-regret learning dynamics converge.
Moreover, for proportional ranking functions, we prove the equivalence of the concavity of the activation function, the social concavity of the induced games and the concavity of the induced games.
We also study the empirical trade-offs between publishers’ and users’ welfare, under different choices of the activation function, using a state-of-the-art no-regret dynamics algorithm. Furthermore, we demonstrate how the choice of the ranking function and changes in the ecosystem structure affect these welfare measures, as well as the dynamics’ convergence rate.

## 1 Introduction

In the era of digital content consumption, recommender systems play an essential role in shaping user experiences and engagement on various platforms, including search engines, streaming services, social networks, and more. The core task of a recommender system is to match users with relevant content, created by content creators. By that, the system induces an ecosystem in which content providers compete for exposure and often engage in strategic behavior to maximize visibility []. In particular, the specific recommendation mechanism used by the platform determines the incentives, and hence the strategic behavior, of the content providers. In the context of search engines, this phenomenon is often referred to as *Search Engine Optimization (SEO)* and is widely observed in real-world search engines [].

These dynamics have major implications for various economic aspects of the ecosystem. First, strategic behavior affects the *welfare* of both end users (seeking relevant content) and content creators, whose profits are often proportional to the level of exposure they receive from the platform. The second aspect is *stability*, which refers to the existence of, and the convergence to, a stable state, in which content providers have no incentive to modify their content given the content provided by their competitors. In the game-theoretic jargon, this stability is captured by the notion of *Nash equilibrium*. Not surprisingly, these two aspects have been shown, for example empirically in [], to be interconnected.

The study of convergence to equilibrium through the lens of game theory, a field often referred to as *learning dynamics*, has been adopted to analyze the stability of recommendation and ranking mechanisms. Specifically, two concrete dynamics that arise in the presence of strategic behavior over time are *better-response dynamics* and *no-regret dynamics*.
The convergence of better-response dynamics has been studied in the context of information retrieval under different modeling assumptions [, ]. In this paper, we study no-regret learning dynamics in information retrieval games. We adopt the game-theoretic framework of [, ], in which both content and users are represented in a continuous, multi-dimensional embedding space, and the content providers aim to maximize exposure while maintaining the integrity of their original content. As in [], and unlike in [], we consider mechanisms that only control the exposure of each content provider, without any additional reward in the form of payments (as done in platforms such as YouTube []). These mechanisms contain, among others, search engines that control the probability of presenting documents in response to a user query. That is, the mechanism considered is a *ranking function* which is a mapping from the publishers’ documents to a distribution over the publishers, determining each publisher’s exposure rate.

##### Our contribution

In the spirit of previous work [, , , ], we model SEO as a game and define a natural class of ranking functions we term *proportional ranking functions*. While in our model a ranking function is a vector-valued function (as it assigns exposure probabilities for each publisher), a proportional ranking function is uniquely defined by a one-variable scalar function, which we call an *activation function*.
Importantly, the choice of the ranking function determines the incentives of the strategic publishers and hence affects the content available to users in the corpus. Relying on the notion of socially concave games, a subclass of concave games presented in [], we prove that the concavity of the activation function guarantees the convergence of any no-regret learning dynamics in any induced SEO game.
To do so, we establish a rather stronger statement by proving the equivalence of the following three conditions: the activation function is concave; any induced game is socially-concave; any induced game is concave (as in []).
We also study the empirical trade-offs between users’ and publishers’ welfare under different choices of the activation function, using a state-of-the-art no-regret dynamics algorithm [].
In addition, we demonstrate the effect of the game parameters such as the penalty factor and the number of publishers on the publishers’ welfare, the users’ welfare and the convergence rate.

### 1.1 Related work

In a recent growing line of research work, a variety of game-theoretic frameworks have been proposed to analyze the strategic dynamics of content providers in recommendation systems, particularly in the context of search engines. The study of strategic behavior of content creators under the mediation of a recommender system was initiated in a series of research works [, , ]. The Shapley mediator was proposed as a mechanism satisfying both stability (in the form of equilibrium existence guarantee) as well as fairness-related axioms.

Another concurrent line of works focused on the analysis of an adversarial information retrieval framework, in which content providers compete on exposure [, ]. These works demonstrated the sub-optimality of greedy ranking according to the probability ranking principle (PRP) of [] in terms of social welfare at equilibrium. [] then studied both theoretically and empirically the SEO competition in a repeated setting. Under similar modeling assumptions, [] showed that better-response dynamics of publishers in PRP-based retrieval games are guaranteed to converge.

More recent studies on strategic behavior within recommendation and search ecosystems have adapted several modeling assumptions that reflect the use of deep learning and dense representations [, , , ]. Unlike earlier studies, these recent efforts assume that content is represented within a continuous embedding space, rather than a discrete set of ”topics”. In contrast to [], we focus on the case in which the platform can only control the exposure rate of the publishers. The main focus of these works was on equilibria characterization [, ] and the study of better-response dynamics convergence [] under specific recommendation or ranking mechanisms. In contrast, this work characterizes a rich and intuitive family of mechanisms that guarantee the convergence of *no-regret dynamics*.

The fundamental connections between no-regret learning and game-theoretic solution concepts [, , , , ] have made the regret-minimization framework very appealing to the machine learning and artificial intelligence communities [, , , , , , , , ]. In particular, the notion of concave games [] and its connection to the convergence of no-regret dynamics showed by [] plays a crucial role in our analysis.

## 2 Preliminaries

##### Game theory

An $n$-person game is a tuple $G=(N,\{X_{i}\}_{i\in N},\{u_{i}\}_{i\in N})$, where $N=\{1,...,n\}$ is the set of players, $X_{i}$ is the set of actions of player $i$, and $u_{i}:X\to\operatorname*{\mathbb{R}}$ is the utility function of player $i$, where $X=X_{1}\times...\times X_{n}$ is the set of all possible action profiles. Throughout the paper, we assume that for every player $i$, $X_{i}$ is a convex and compact set of actions. In addition, we assume that $u_{i}$ is twice differentiable and bounded for all $i$.

For any action profile $x\in X$, we denote by $x_{-i}=(x_{1},...x_{i-1},x_{i+1},...x_{n})$ the actions of all players except player $i$ within the profile $x$. An action profile $x$ is said to be an *$\varepsilon$-Nash equilibrium* ($\varepsilon$-NE) if for any player $i$, and for any action $x^{\prime}_{i}\in X_{i}$, deviation of player $i$ from $x_{i}$ to $x^{\prime}_{i}$ does not increase her utility by more than $\varepsilon$. Formally,
for any $\varepsilon\geq 0$, $x\in X$ is an $\varepsilon$-NE if $u_{i}(x^{\prime}_{i},x_{-i})-u_{i}(x)\leq\varepsilon,\forall i\in N,\forall x^
{\prime}_{i}\in X_{i}$. For $\varepsilon=0$, a 0 0-NE is referred to as a *Nash equilibrium* (NE).

##### No-regret dynamics

No-regret dynamics is a well-known type of dynamics within the online learning framework, in which each player $i$ is a learning agent that has to select a strategy $x_{i}^{(t)}\in X_{i}$ in every round $t\in\operatorname*{\mathbb{N}}$, in response to the sequence of the observations she has received up until round $t$. A widely acceptable way to measure the performance of player $i$ up to some horizon time $T\in\operatorname*{\mathbb{N}}$ in this setting is regret,(^1^11We consider the notion of external regret, not to be confused with internal (’swap’) regret.) defined as follows:

$$ $\text{Reg}^{T}_{i}\coloneqq\max_{x_{i}\in X_{i}}\Biggl{\{}\sum_{t=1}^{T}u_{i}( x_{i},x_{-i}^{(t)})\Biggr{\}}-\sum_{t=1}^{T}u_{i}(x^{(t)})$ (1) $$

That is, the regret of player $i$ is measured with respect to the utility she could have gained had she selected in every round the best fixed strategy in hindsight. In our context, as standard in the online learning literature, e.g. [], it is assumed that each player observes in every round $t$ the gradient of her utility function with respect to her strategy, evaluated at the strategy profile selected by all players in this round. That is, in round $t$ player $i$ observes $\nabla_{x_{i}}u_{i}(x^{(t)})$.

##### Concave games

We now introduce two special classes of games. A game $G$ is said to be a *(strictly) concave game* if for any player $i$, $u_{i}(x_{i},x_{-i})$ is (strictly) concave in $x_{i}$ for any fixed $x_{-i}$. In his seminal work, [] introduced the class of concave games, and showed that every (strictly) concave game has a (unique) Nash equilibrium.(^2^22Concave games are well studied, and possess some other nice properties, see e.g. [, ].) An important subclass of concave games is the class of *socially-concave games*, introduced by [].

###### Definition 1 .

A game $G$ is socially-concave if the following properties hold:

- A1.
There exist strictly positive coefficients $\alpha_{1},...\alpha_{n}>0$, such that $\sum_{i=1}^{n}\alpha_{i}=1$ and the function $g(x)\coloneqq\sum_{i=1}^{n}\alpha_{i}\cdot u_{i}(x)$ is concave in $x$.
- A2.
The utility function of each player $i$ is convex in the actions of all other players. That is, $\forall i\in N,\forall x_{i}\in X_{i}$, the function $f(x_{-i})\coloneqq u_{i}(x_{i},x_{-i})$ is convex in $x_{-i}$.

[] showed that every socially-concave game is a concave game, but the reverse direction is not necessarily true. [] also showed that if each player follows any regret minimization procedure in a socially-concave game, then the dynamics are guaranteed to converge. The convergence is in the sense that both the average action vector converges to a Nash equilibrium and the average utility of each player converges to her utility in that Nash equilibrium.

###### Definition 1 .

## 3 The model

An $n$-player publishers’ game is a game in which $n$ content providers (publishers) generate content (documents) to maximize exposure to users while maintaining the integrity of their original content (initial documents). In this setup, each document is modeled as a $k$-dimensional vector, which can be thought of as the document’s $k$-dimensional embedding representation. We assume the embedding space is normalized to the $k$-dimensional unit cube $[0,1]^{k}$. The $n$ publishers, denoted by the set $N\coloneqq\{1,\dots,n\}$, constitute the set of players of the publishers’ game. For any player $i\in N$, player $i$’s set of possible actions in the game is defined to be the embedding space, that is $X_{i}\coloneqq[0,1]^{k}$.

Information needs of the users are denoted by $x^{*}\in[0,1]^{k}$ and modeled as vectors in the same embedding space as the publishers’ documents. This approach mirrors the common practice in standard models of dense retrieval [, ]. We model the fact that in real life there are often multiple information needs by a demand distribution $P^{*}\in\mathcal{P}([0,1]^{k})$, a distribution of information needs. In addition, each publisher has an initial document $x_{0}^{i}\in[0,1]^{k}$.

Distance between two documents in the embedding space is measured by a given semi-metric(^3^33A semi-metric is similar to a metric, except it does not need to satisfy the triangle inequality.) $d:[0,1]^{k}\times[0,1]^{k}\to\operatorname*{\mathbb{R}}_{+}$, which is assumed to be normalized such that for any two documents $a,b\in[0,1]^{k}$ we have $0\leq d(a,b)\leq 1$. Another standard assumption that we make is that $d(a,x_{0}^{i})$ and $d(a,x^{*})$ are twice differentiable in $a$ for all the initial documents $\{x_{0}^{i}\}_{i\in N}$ and for every information need $x^{*}$.
This assumption is needed for the utilities to be twice differentiable.
Moreover, we assume that $d(a,b)$ is bi-convex, meaning that it is convex in $a$ for any fixed $b$ and vice-versa.
The role of $d$ in our model is two-fold. Firstly, it measures the integrity to the initial content, with the interpretation that a small distance between a publisher’s strategy document and her initial document represents strong integrity. Secondly, $d$ is used by the system designer to assess the relevance of documents to a given information need $x^{*}$, with the interpretation that $d$-proximity implies relevance.

Publishers’ exposure to users is determined by a pre-defined ranking function $r:[0,1]^{k\cdot n}\times[0,1]^{k}\to\mathcal{P}(N)$, selected by the system designer. $r$ receives as input a strategy profile of documents chosen by the publishers, as well as an information need, and outputs a distribution over the publishers, with the interpretation that $r_{i}(x;x^{*})$ is the proportion of the users who are interested in the information need $x^{*}$ that are exposed to publisher $i$’s document if the strategy profile that is played by the publishers is $x$.(^4^44An alternative interpretation would be that $r_{i}(x;x^{*})$ is the probability publisher $i$ would be ranked first in a search engine in response to a query $x^{*}$ if the strategy profile that is played by the publishers is $x$.)
Typically, $r_{i}(x;x^{*})$ would decrease in $d(x_{i},x^{*})$ and increase in $d(x_{j},x^{*})$ for $j\neq i$.(^5^55In addition, ranking functions should be oblivious, meaning they should exhibit symmetry among publishers.)

Each publisher $i$ tries to achieve two goals simultaneously: on the one hand, maximize the expected chance of her being ranked first by the search engine, which for a given strategy profile $x$ is $\mathbb{E}_{x^{*}\sim P^{*}}\left[r_{i}(x;x^{*})\right]$; and on the other hand, provide content $x_{i}$ which is as faithful as possible to her initial document, meaning with $d(x_{i},x_{0}^{i})$ as small as possible. Her trade-off between these two goals is determined by an integrity parameter $\lambda_{i}>0$.

Formally, an $n$-player publishers’ game is a tuple $G\coloneqq(N,k,d,r,P^{*},\{x_{0}^{i}\}_{i\in N},\{\lambda_{i}\}_{i\in N})$. The set of players of the game is $N\coloneqq\{1,\dots,n\}$, the action space of each publisher $i\in N$ is the embedding space $X_{i}\coloneqq[0,1]^{k}$, and her utility function is defined as follows:

$$ $u_{i}(x)\coloneqq\mathbb{E}_{x^{*}\sim P^{*}}\left[r_{i}(x;x^{*})\right]- \lambda_{i}\cdot d(x_{i},x_{0}^{i})$ (2) $$

We now turn to the natural definition of ranking functions that induce socially-concave games and ranking functions that induce concave games:

###### Definition 2 .

We say a ranking function $r$ induces socially-concave (concave) games if any publishers’ game with $r$ as its ranking function is a socially-concave (concave) game.

Note that condition A1. of social concavity holds with $\alpha_{i}=\frac{1}{n}$ in every publishers’ game, since $\sum_{i=1}^{n}r_{i}\equiv 1$. This leads to the following useful lemma, whose proof is deferred to Appendix A.1.

###### Lemma 1 .

A ranking function $r$ induces socially-concave games if and only if for every information need $x^{*}$, for every publisher $i\in N$ and for every $x_{i}\in X_{i}$, $r_{i}(x_{i},x_{-i};x^{*})$ is convex in $x_{-i}$.

In the sequel, we restrict our attention to the very natural class of *proportional ranking functions*:

###### Definition 3 .

We say a ranking function $r$ is a proportional ranking function if there exists a twice differentiable and strictly decreasing function $g:[0,1]\to\operatorname*{\mathbb{R}}_{++}$ such that

$$ $r_{i}(x;x^{*})=\frac{g\bigl{(}d(x_{i},x^{*})\bigr{)}}{\sum_{j=1}^{n}g\bigl{(}d (x_{j},x^{*})\bigr{)}}$ (3) $$

The function $g$ is called the activation function of $r$.

Our main objective is to characterize the subset of proportional ranking functions that induce socially-concave games.
These ranking functions possess various desirable properties, such as the existence of a Nash equilibrium, and a guarantee that if publishers engage according to any regret-minimization procedure, they will converge to a Nash equilibrium.
We can then simulate no-regret dynamics for various instances of the publishers’ game for different ranking functions, and compare them in terms of publishers’ and users’ welfare.

###### Definition 2 .

###### Lemma 1 .

###### Definition 3 .

## 4 Main result

We now provide a necessary and sufficient condition for a proportional ranking function to induce socially-concave games. This condition turns out to have a relatively simple form: the activation function should be concave.
We show this by proving a stronger statement:

###### Theorem 1 .

Let $r$ be a proportional ranking function with activation function $g$. Then, the following are equivalent:

- I.
The activation function $g$ is concave
- II.
$r$ induces concave games
- III.
$r$ induces socially-concave games

Moreover, if $d$ is strictly bi-convex, then $r$ induces strictly concave games if and only if $g$ is concave.

###### Proof.

We prove the theorem by showing that concavity of the activation function is sufficient for social concavity ($\ref{II}\implies\ref{I}$), then showing that if $g$ is not concave then $r$ does not even induce concave games ($\ref{III}\implies\ref{II}$), which wraps up the proof of the equivalence of I., II. and III. since [] showed that any socially-concave game is a concave game ($\ref{I}\implies\ref{III}$).
For the moreover part, in Appendix A.3 we show that in the case where $d$ is strictly bi-convex, a concave $g$ implies that $r$ induces strictly concave games.

$\ref{II}\implies\ref{I}$: By Lemma 1, it is enough to show that for every information need $x^{*}$, for every publisher $i\in N$ and for every $x_{i}\in X_{i}$, $r_{i}(x_{i},x_{-i};x^{*})$ is convex as a function of $x_{-i}$. So let $i\in N$, $x^{*}\in[0,1]^{k}$, $x_{i}\in X_{i}$.
Denote $C=g\bigl{(}d(x_{i},x^{*})\bigr{)}$
and $h(x_{-i})=\sum_{j\neq i}g\bigl{(}d(x_{j},x^{*})\bigr{)}$.
So we need to show that the following function is convex in $x_{-i}$:

$$ $r_{i}(x_{i},x_{-i};x^{*})=\frac{g\bigl{(}d(x_{i},x^{*})\bigr{)}}{\sum_{j=1}^{n }g\bigl{(}d(x_{j},x^{*})\bigr{)}}=\frac{C}{C+h(x_{-i})}$ $$

By our assumption that $d$ is bi-convex, $d(x_{j},x^{*})$ is convex in $x_{j}$ for any player $j\in N$. Since $g$ is concave and decreasing, $g\bigl{(}d(x_{j},x^{*})\bigr{)}$ is concave in $x_{j}$ as a composition of a concave and decreasing function on a convex function. So $h(x_{-i})$ is concave in $x_{-i}$ as a sum of concave functions.

Now, define a function $\ell:\operatorname*{\mathbb{R}}\to\operatorname*{\mathbb{R}}$ as follows: $\ell(t)=\frac{C}{C+t}$. So:

$$ $r_{i}(x_{i},x_{-i};x^{*})=\ell\bigl{(}h(x_{-i})\bigr{)}$ $$

$C>0$ guarantees that $\ell$ is convex and decreasing in $\operatorname*{\mathbb{R}}_{+}$. Therefore $r_{i}(x_{i},x_{-i};x^{*})$ is convex in $x_{-i}$ as a composition of a convex and decreasing function on a concave function.

$\ref{III}\implies\ref{II}$: If $g$ is not concave, there exists $\hat{a}\in(0,1)$ such that $g^{\prime\prime}(\hat{a})>0$. We now construct a publishers’ game instance $G$, with $r$ as its proportional ranking function (with activation $g$), which is not a concave game. We construct $G$ to be a publishers’ game with embedding dimension $k=1$, a number of players $n$ that satisfies $n>\frac{2g^{\prime}(\hat{a})^{2}}{g^{\prime\prime}(\hat{a})g(0)}+1$, a one-hot distribution on the information needs that places probability $1$ on $x^{*}=0$ and a semi-metric $d(a,b)=|a-b|$. We choose the initial documents of all players $i\in N$ to be $x_{0}^{i}=1$.
Note that since all initial documents are located at $1$ and the only information need is located at 0 0, the utilities are indeed twice differentiable, as we assume in the sequel.
Let $\hat{x}_{-1}$ be a strategy profile of all publishers but publisher $1$ in which each of the other publishers $j\neq 1$ plays $\hat{x}_{j}=0$. Now, a simple calculation (deferred to Appendix A.2) shows that the function $f(x_{1})\coloneqq u_{1}(x_{1},\hat{x}_{-1})$ satisfies $f^{\prime\prime}(\hat{a})>0$.
Hence, $u_{1}(x_{1},\hat{x}_{-1})$ is not concave in $x_{1}$, so by definition $G$ is not a concave game.
∎

Theorem 1, together with the findings of [] that in socially-concave games any no-regret dynamics converges, and the guarantee of [] that (strictly) concave games possess a (unique) NE, leads to the following result:

###### Corollary 1 .

Let $r$ be a proportional ranking function with activation function $g$. Then, if $g$ is concave, any no-regret learning dynamics in any publishers’ game induced by $r$ converges. Moreover, any induced publishers’ game possesses a NE, and if $d$ is strictly bi-convex the NE is unique.

###### Theorem 1 .

###### Proof.

###### Corollary 1 .

## 5 Experimental comparison of ranking functions

In this section, we present some proportional ranking functions with concave activation functions and compare them using no-regret dynamics simulations.
We highlight that our goal is to study the long-term behavior and dynamics of strategic, rational agents that engage with algorithmic tools for regret minimization, which is different than (and complementary to) other lines of work that evaluate the dynamics of human publishers that may be prone to various biases, e.g. [].
Therefore, we chose to evaluate the ranking functions using a code simulation in which agents use the state-of-the-art no-regret algorithm of [], which is designated for concave games as in our case.
We compare three families of proportional ranking functions based on some concave and decreasing functions as activation functions.

- •
The linear proportional ranking function family: $g_{lin}(t)=b-t$, where $b>1$ is the intercept hyperparameter.
- •
The root proportional ranking function family: $g_{root}(t)=(1-t)^{a}$, where $0<a<1$ is the power hyperparameter.
- •
The logarithmic proportional ranking function family: $g_{log}(t)=\ln(c-t)$, where $c>2$ is the shift hyperparameter.

Let $r^{lin}$, $r^{root}$ and $r^{log}$ be the proportional ranking functions induced by these activation functions. Unless stated otherwise, we use the default values of $b=1+\delta$, $a=\frac{1}{2}$, $c=2+\delta$, where $\delta\coloneqq 10^{-5}$.

### 5.1 Simulation details

Our simulations utilize the state-of-the-art no-regret algorithm presented in [], the Log-Regularized Lifted Optimistic FTRL (hereafter, LRL-OFTRL). For each player, the algorithm uses the current gradient of the utility, the gradients from previous rounds, and a learning rate $\eta$ to decide which action to play in the next round. The important feature of LRL-OFTRL is the logarithmic increase in regret as the dynamics progresses.
In our simulations, which are carried out in rounds, we define a publishers’ game $G$ and let the players choose their action in each round using the LRL-OFTRL algorithm. A simulation is said to *converge* if it has reached an $\varepsilon$-NE. Throughout all simulations, we used homogeneous $\lambda_{i}=\lambda$ for all $i\in N$, the squared Euclidean semi-metric $d(x,y)=\frac{1}{k}||x-y||_{2}^{2}$, learning rate $\eta=1/2$ and $\varepsilon=10^{-4}$.
In all simulations, we consider uniform demand distributions over a sample of $s\in\operatorname*{\mathbb{N}}$ information needs.(^6^66 Note that while we restrict our simulations to uniform demand distributions, any demand distribution can be approximated with $s$ large enough.)

##### Evaluation criteria

To evaluate the performance of the different ranking functions, we report three evaluation criteria: the publishers’ welfare, the users’ welfare and the convergence rate. The two welfare measures are defined similarly to previous work [, ].
The *publishers’ welfare* is defined to be the sum of publisher utilities:

$$ $\mathcal{U}(x)\coloneqq\sum_{i=1}^{n}u_{i}(x)=1-\lambda\sum_{i=1}^{n}d^{0}_{i} (x_{i})$ (4) $$

The *users’ welfare* is the expected relevance of the first-ranked document for each information need, where we quantify the relevance of a document $x_{i}$ by $1-d(x_{i},x^{*})$, and expectation is taken over both the demand distribution $P^{*}$ and the distribution over the publishers $r(x)$:

$$ $\mathcal{V}(x)\coloneqq\mathbb{E}_{x^{*}\sim P^{*}}\left[\sum_{i=1}^{n}\bigl{( }1-d(x_{i},x^{*})\bigr{)}\cdot r_{i}(x)\right]=1-\mathbb{E}_{x^{*}\sim P^{*}} \left[\sum_{i=1}^{n}d(x_{i},x^{*})\cdot r_{i}(x)\right]$ (5) $$

These welfare measures can be evaluated at any strategy profile $x\in X$, but we report the values obtained in the $\varepsilon$-NE the dynamics converged to, as these values represent the *long-term* welfares. The *convergence rate* is simply the number of rounds it took the dynamics to converge. For each parameter configuration and each evaluation criterion, we performed $500$ simulations, when initial documents and demand distributions were drawn uniformly i.i.d., and constructed bootstrap confidence intervals with a confidence level of 95% using a bootstrap sample size of $B=500$.

### 5.2 Simulations results

#### 5.2.1 Comparison between ranking function families

Figure 1 presents several interesting trends. A prominent phenomenon in the figure is a trade-off between the different measures - whenever an activation function induces an equilibrium in which the publishers’ welfare is high, the users’ welfare is lower and the game dynamics converge more slowly.
The activation functions that yield higher publishers’ welfare values are the ones that align the ranking function more closely with a uniform ranking (i.e., $r_{i}\equiv\frac{1}{n}$), or, in other words, the ones in which the impact of the publishers’ content on the ranking is less significant.
When ranking the documents using these functions, the publishers are less incentivized to create relevant content and thus stay closer to their respective initial documents. This leads to higher publishers’ welfare and lower users’ welfare. On the contrary, there are less uniform ranking functions, in which the distances from the information needs have a greater influence on the ranking. Those ranking functions encourage publishers to compete for each information need and to generally make their documents more relevant to the users, which leads to higher users’ welfare and lower publishers’ welfare.(^7^77To elucidate this point, let us compare the activation functions $g_{lin}$ and $g_{root}$. Note that $g_{root}$ is a concave transformation of the linear activation function. When applying a square root to a number in $[0,1]$, the smaller it is the bigger the factor it is increased by. Therefore, for any fixed profile, the ranking produced by $g_{root}$ is closer to uniform distribution than that produced by $g_{lin}$.)
In addition, when the ranking functions are less uniform, the absolute values of the gradients increase, which leads to faster convergence.

In the rest of the section, we demonstrate that this order relation between the ranking functions is robust to changes in the ecosystem structure, such as changes in the game parameters, and show how these changes affect our evaluation criteria.

##### The effect of the penalty factor λ 𝜆 \lambda italic_λ

Figure 1 illustrates how $\lambda$, the penalty factor, influences our evaluation criteria, showing similar trends to those discussed in [].
One might expect an increase in $\lambda$ to harm the publishers’ welfare, since a larger $\lambda$ imposes greater penalty on the publishers for providing content that differs from their initial documents. Yet, a higher $\lambda$ also incentivizes the publishers to adhere more closely to their initial documents, which increases the publishers’ welfare. This two opposing forces explain the non-monotonic trend observed in Figure 1 - for lower values of $\lambda$, the publishers’ welfare decreases as $\lambda$ increases, until it reaches a minimum point, after which it keeps increasing. The trend in the users’ welfare is simpler: it monotonically decreases as $\lambda$ increases, likely because higher penalties lead to less relevant content from publishers. Lastly, there is no significant impact of the penalty factor on the convergence rate.

Figure: Figure 1: The effect of the penalty factor $\lambda$, with $n=3,s=3$ and $k=3$.
Refer to caption: extracted/5781317/static_figures/lam_comp.png

Figure: Figure 2: The effect of the number of publishers $n$, with $\lambda=0.5$, $s=3$ and $k=3$.
Refer to caption: extracted/5781317/static_figures/n_comp.png

##### The effect of the number of publishers n 𝑛 n italic_n

The influence of $n$ on the welfare measures, as depicted in Figure 2, resembles that of $\lambda$. Just like $\lambda$, $n$ has two opposite effects on the publishers’ welfare. On the one hand, higher $n$ values make the competition for top ranking harder, discouraging publishers to participate in it and therefore incentivizing them to stay near their initial documents, thus reducing their penalty factor.
On the other hand, since all publishers incur a penalty, more publishers means more penalties, which directly lowers the publishers’ welfare. As a result, the publishers’ welfare is not monotonous in $n$ but rather has an internal minimum point. The users’ welfare decreases in $n$ since a bigger $n$ amplifies publishers’ adherence to their initial documents, which makes the content in the corpus less relevant to users.
Lastly, more players result in slower convergence rate, which is not surprising since it is measured by the time taken for the last publisher to reach an $\varepsilon$-NE.

##### The effect of the demand distribution support size s 𝑠 s italic_s

As depicted in Figure 3, increasing $s$ leads to an increase in the publishers’ welfare and a decrease in the users’ welfare, both trends eventually plateauing. A possible explanation is that when increasing $s$ while fixing $n$, a fixed number of publishers compete for an increasing number of information needs, which makes it harder for the publishers to maximize their exposure. Recall that a publisher’s utility from exposure is the expected value of her exposure for different information needs, so when a player is unable to meet a large portion of the information needs, she might be demotivated to try to be relevant to the users and focus on being faithful to her initial document, boosting the publishers’ welfare in the expense of the users.

The convergence rate is affected by $s$ as well. When $s$ is small, the publishers must compete for the same information needs, which leads to more complicated dynamics and hence to slower convergence. As $s$ increases, the publishers tend to focus on different information needs (the ones which are the closest to their initial document), therefore we get much simpler dynamics and faster convergence.

##### The effect of the embedding space dimension k 𝑘 k italic_k

Figure 4 reveals that while $k$ has a negligible influence on the publishers’ and users’ welfare, its effect on the convergence rate is substantial. Specifically, as $k$ increases, the dynamics require more rounds to converge (notice the large scale of the convergence rate axis in Figure 4). In this sense, our dynamics are similar to standard optimization algorithms, where the dimensionality of the problem significantly affects the convergence rate.

Figure: Figure 3: The effect of the demand distribution support size $s$, with $\lambda=0.5,n=3$ and $k=3$.
Refer to caption: extracted/5781317/static_figures/s_comp.png

Figure: Figure 4: The effect of the embedding space dimension $k$, with $\lambda=0.5$, $n=3$ and $s=3$.
Refer to caption: extracted/5781317/static_figures/k_comp.png

#### 5.2.2 Comparison within ranking function families

Beyond the comparison between the three ranking function families, tuning the hyperparameters within each family also reveals interesting phenomena. The experimental results supporting these observations are provided in Appendix B, and are discussed here. The results once again underscore the publisher-user trade-off discussed in §5.2.1: hyperparameter values that lead to higher publishers’ welfare result in lower users’ welfare and slower convergence rate, and vice versa.
As was the case in the comparison between ranking function families, the hyperparameters’ values that lead to higher publishers’ welfare (and lower users’ welfare) are the values that make the ranking function closer to uniform ranking. For example, a decrease in the power parameter $a$ of $r^{root}$ can be seen in Figure 6 to correlate with an increase in publishers’ and a decrease in users’ welfare, and indeed when the power parameter $a$ approaches 0 0, the root proportional ranking function approaches a uniform ranking. That is: $r^{root}_{i}\to\frac{1}{n}$ as $a\to 0$.
Similarly, both the intercept parameter $b$ of $r^{lin}$ and the shift parameter $c$ of $r^{log}$ are positively correlated with the publishers’ welfare and negatively correlated with the users’ welfare,
and indeed $r^{lin}_{i}\to\frac{1}{n}$ as $b\to\infty$ and $r^{log}_{i}\to\frac{1}{n}$ as $c\to\infty$.

## 6 Discussion

We studied an information retrieval game in which publishers have initial documents they prefer to provide and initiated the analysis of no-regret dynamics in such games. We defined the class of proportional ranking functions, which are ranking functions that are determined by a one-variable scalar activation function, and established a full characterization of which proportional ranking functions induce socially-concave games and which induce concave games. We then used this characterization to conclude that any concave activation function guarantees the convergence of no-regret dynamics, thereby offering a system designer a rich family of ranking functions that, under the assumption that publishers minimize their regret, guarantee the reach of the system to a stable state. We then empirically investigated the publishers’ welfare and the users’ welfare, as well as the convergence rate, which measures how long it takes the ecosystem to reach stability. In particular, we examined how these three criteria are affected by the choice of the ranking function and by changes in the ecosystem structure.

##### Limitations

Although we prove convergence of no-regret dynamics whenever the activation function is concave, our approach provides no insights regarding convergence in the case it is not concave. Further, we assumed each publisher is restricted to publishing only one document, while in practice a publisher can write several documents, e.g. in order to compete for exposure from multiple information needs simultaneously. A specific cost function was assumed to capture the cost the publishers incur for deviating from their initial documents.
A major limitation of our experiments is that we drew $x_{0}$ and $x^{*}$ i.i.d from a uniform distribution, and the trends presented in our analysis are not guaranteed to hold for other ecosystem distributions. A theoretical welfare and convergence rate analysis are also out of scope. We believe these limitations can serve as interesting directions for future work, and further expand our understanding of the dynamics of strategic publishers.

## Acknowledgments

This work was supported by funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement 740435).

## Appendix A Proofs

### A.1 Proof of Lemma 1

###### Proof.

$\implies:$
Let $x^{*}\in[0,1]^{k},i\in N,x_{i}\in X_{i}$. If $r$ induces socially-concave games, then in particular any game with $r$ as
its ranking function and with
a one-hot distribution of information needs $P^{*}$ which gives probability $1$ on $x^{*}$ is a socially-concave game. So by condition A2. of the definition of social concavity, $u_{i}(x)=r_{i}(x;x^{*})-\lambda_{i}\cdot d(x_{i},x_{0}^{i})$ is convex in $x_{-i}$. Since $\lambda_{i}\cdot d(x_{i},x_{0}^{i})$ is fixed in $x_{-i}$, this implies that $r_{i}(x;x^{*})$ is convex in $x_{-i}$.
$\impliedby:$
First, notice that for every ranking function $r$, condition A1. of the definition of social concavity holds with $\alpha_{i}=\frac{1}{n}$:

$$ $\displaystyle g(x)$ $\displaystyle\coloneqq\sum_{i=1}^{n}\alpha_{i}\cdot u_{i}(x)=\mathbb{E}_{x^{*} \sim P^{*}}\left[\sum_{i=1}^{n}\frac{1}{n}\cdot\left(r_{i}(x;x^{*})-\lambda_{i }\cdot d(x_{i},x_{0}^{i})\right)\right]$ (6) $\displaystyle=\frac{1}{n}-\frac{1}{n}\cdot\sum_{i=1}^{n}\lambda_{i}\cdot d(x_{ i},x_{0}^{i})$ $$

since $\sum_{i=1}^{n}r_{i}(x;x^{*})=1$ for any strategy profile $x\in X$ and information need $x^{*}\in[0,1]^{k}$. Now, $g(x)$ is concave since for every $i\in N$ and $x_{0}^{i}\in[0,1]^{k}$, $d(x_{i},x_{0}^{i})$ is convex in $x_{i}$.
Regarding condition A2., it can be easily shown (using the linearity and monotonicity of expectation) that the convexity of $r_{i}(x;x^{*})$ in $x_{-i}$ for any $x_{i}\in X_{i},x^{*}\in[0,1]^{k}$ implies that $\mathbb{E}_{x^{*}\sim P^{*}}\left[r_{i}(x;x^{*})\right]$ is convex in $x_{-i}$ for any $x_{i}\in X_{i}$. Together with the fact that $d(x_{i},x_{0}^{i})$ is fixed in $x_{-i}$, we get that $u_{i}(x)=\mathbb{E}_{x^{*}\sim P^{*}}\left[r_{i}(x;x^{*})-\lambda_{i}\cdot d(x
_{i},x_{0}^{i})\right]$ is convex in $x_{-i}$ for any $x_{i}\in X_{i}$.
∎

###### Proof.

### A.2 Full derivation of inequality f ′′ ⁢ ( a ^ ) > 0 superscript 𝑓 ′′ ^ 𝑎 0 f^{\prime\prime}(\hat{a})>0 italic_f start_POSTSUPERSCRIPT ′ ′ end_POSTSUPERSCRIPT ( over^ start_ARG italic_a end_ARG ) > 0 from the proof of Theorem 1

This appendix provides a detailed derivation of the equation $f^{\prime\prime}(\hat{a})>0$ from the proof of the main result. By the definition of the utility in publishers’ games, and since in the game we constructed the distribution over the information needs is a one-hot distribution that places probability $1$ on $x^{*}=0$:

$$ $f(x_{1})=u_{1}(x_{1},\hat{x}_{-1})=r_{1}(x_{1},\hat{x}_{-1};x^{*}=0)-\lambda_{ 1}d(x_{0}^{1},x_{1})$ (7) $$

Recall that $r$ is a proportional ranking function with activation function $g$ and that we chose $d(a,b)=|a-b|$ and $x_{0}^{1}=1$:

$$ $f(x_{1})=\frac{g\bigl{(}d(x_{1},0)\bigr{)}}{\sum_{j\neq i}g\bigl{(}d(\hat{x}_{ j},0)\bigr{)}+g\bigl{(}d(x_{1},0)\bigr{)}}-\lambda_{1}(1-x_{1})$ (8) $$

Recalling that for all the other players $j\neq 1$ we chose $\hat{x}_{j}=0$ we get:

$$ $f(x_{1})=\frac{g(x_{1})}{\sum_{j\neq i}g(0)+g(x_{1})}-\lambda_{1}(1-x_{1})= \frac{g(x_{1})}{(n-1)g(0)+g(x_{1})}-\lambda_{1}(1-x_{1})$ (9) $$

Let us denote $C\coloneqq(n-1)g(0)$. So

$$ $f(x_{1})=\frac{g(x_{1})}{C+g(x_{1})}-\lambda_{1}(1-x_{1})$ (10) $$

Now let us calculate the second derivative of $f$. First, its first derivative is

$$ $f^{\prime}(x_{1})=\frac{Cg^{\prime}(x_{1})}{\bigl{(}C+g(x_{1})\bigr{)}^{2}}+ \lambda_{1}$ (11) $$

And $f$’s second derivative is given by:

$$ $f^{\prime\prime}(x_{1})=\frac{C}{\bigl{(}C+g(x_{1})\bigr{)}^{3}}\biggl{[}g^{ \prime\prime}(x_{1})\bigl{(}C+g(x_{1})\bigr{)}-2g^{\prime}(x_{1})^{2}\biggr{]}$ (12) $$

Substituting $x_{1}=\hat{a}$ we get:

$$ $f^{\prime\prime}(\hat{a})=\frac{C}{\bigl{(}C+g(\hat{a})\bigr{)}^{3}}\biggl{[}g ^{\prime\prime}(\hat{a})\bigl{(}C+g(\hat{a})\bigr{)}-2g^{\prime}(\hat{a})^{2} \biggr{]}$ (13) $$

Now, recall that we chose $\hat{a}$ to satisfy $g^{\prime\prime}(\hat{a})>0$. Also, our choice of $n>\frac{2g^{\prime}(\hat{a})^{2}}{g^{\prime\prime}(\hat{a})g(0)}+1$ ensures that $C\coloneqq(n-1)g(0)>\frac{2g^{\prime}(\hat{a})^{2}}{g^{\prime\prime}(\hat{a})}$. Moreover, $g$ is a positive function so $\frac{C}{\bigl{(}C+g(\hat{a})\bigr{)}^{3}}>0$. We can use this to bound $f^{\prime\prime}(\hat{a})$ from below:

$$ $\displaystyle f^{\prime\prime}(\hat{a})$ $\displaystyle>\frac{C}{\bigl{(}C+g(\hat{a})\bigr{)}^{3}}\biggl{[}g^{\prime \prime}(\hat{a})\bigl{(}\frac{2g^{\prime}(\hat{a})^{2}}{g^{\prime\prime}(\hat{ a})}+g(\hat{a})\bigr{)}-2g^{\prime}(\hat{a})^{2}\biggr{]}$ (14) $\displaystyle=\frac{C}{\bigl{(}C+g(\hat{a})\bigr{)}^{3}}g^{\prime\prime}(\hat{ a})g(\hat{a})>0$ (15) $$

where the last inequality is since $C$, $g^{\prime\prime}(\hat{a})$ and $g(\hat{a})$ are all strictly positive.

### A.3 Proof that if d 𝑑 d italic_d is strictly bi-convex and g 𝑔 g italic_g is concave then r 𝑟 r italic_r induces strictly concave games

In this appendix, we prove that if we assume that $d$ is strictly bi-convex (an assumption satisfied, for example, by the squared Euclidean semi-metric, which is the semi-metric we use in our simulations in §5), and if $g$ is concave, then the proportional ranking function $r$ with activation function $g$ induces strictly concave games.

###### Proof.

Let $G$ be a game induced by $r$. Let us show that $G$ is strictly concave by definition - fix some player $i\in N$ and let $x_{-i}\in X_{-i}$ be some strategy profile of all players but $i$. We need to show that $u_{i}(x_{i},x_{-i})$ is strictly concave in $x_{i}$. Let $x^{*}$ be an information need in the support of the demand distribution $P^{*}$ of $G$. Since $d$ is strictly bi-convex, $d(x_{i},x^{*})$ is strictly convex in $x_{i}$. Also, $g$ is concave and recall (Definition 3) that $g$ is assumed to be strictly decreasing. Therefore, $g(d(x_{i},x^{*}))$ is strictly concave in $x_{i}$ as a composition of a concave and strictly decreasing function with a strictly convex function. Now, define the function

$$ $h(t)=\frac{t}{t+\sum_{j\neq i}g(d(x_{j},x^{*}))}$ (16) $$

Note that since $\sum_{j\neq i}g(d(x_{j},x^{*}))>0$, $h$ is a concave and strictly increasing function. Therefore,

$$ $\frac{g(d(x_{i},x^{*}))}{\sum_{j=1}^{n}g(d(x_{j},x^{*}))}=h(g(d(x_{i},x^{*}))$ (17) $$

is strictly concave in $x_{i}$ as a composition of a concave and strictly increasing function on a strictly concave function. To sum up the proof, note that

$$ $u_{i}(x_{i},x_{-i})\coloneqq\mathbb{E}_{x^{*}\sim P^{*}}\left[r_{i}(x;x^{*}) \right]-\lambda_{i}\cdot d(x_{i},x_{0}^{i})$ (18) $$

is strictly concave in $x_{i}$ since the first term is strictly concave as an expectation of a strictly concave function and $\lambda_{i}\cdot d(x_{i},x_{0}^{i})$ is strictly convex in $x_{i}$ by the assumption that $d$ is strictly bi-convex.

∎

###### Proof.

## Appendix B Hyperparameters comparison figures

Figure: Figure 5: The effect of the intercept $b$ in the linear proportional ranking function, with $\lambda=0.5$, $n=3,s=3$ and $k=3$.
Refer to caption: extracted/5781317/static_figures/linear_comp.png

Figure: Figure 6: The effect of the power $a$ in the root proportional ranking function, with $\lambda=0.5$, $n=3,s=3$ and $k=3$.
Refer to caption: extracted/5781317/static_figures/root_comp.png

Figure: Figure 7: The effect of the shift $c$ in the logarithmic proportional ranking function, with $\lambda=0.5$, $n=3,s=3$ and $k=3$.
Refer to caption: extracted/5781317/static_figures/log_comp.png

## Peer Reviews

confidence: 5
contribution: 3
initial_rating: 3
presentation: 3
questions: Please address my comments and concerns raised in the weakness.
soundness: 3
strengths: The paper models the strategic interactions among content producers as an information retrieval game. By defining key concepts such as no-regret dynamics, concave games, socially concave games, proportional ranking functions (PRF), the authors provide technical proofs and establish conditions under which PRF induces stable equilibrium and guarantees the convergence of any no-regret dynamics. The main theorem and its insight are presented clearly. Overall I think this paper brings an interesting insight, especially the new concept PRF. I'm curious to see the potential of PRF in real-world applications.
summary: The paper examines strategic behavior in recommender systems, focusing on how content providers adapt their strategies to maximize visibility under different ranking principles. WIth a game-theoretic framework, the authors look at no-regret learning dynamics when competing for exposure. The authors then explore how these rankers impact stability (Nash equilibrium) of the resulting dynamics, and the issue of strategy convergence. The contributions of the paper include: 1. modeling SEO as a game: The authors introduce a new class of ranking functions termed proportional ranking functions and formulate the corresponding game-theoretic framework, 2. by employing the concept of socially concave games, the authors show that if the activation function in the ranking mechanism is concave, the no-regret learning dynamics will converge, thus ensuring stability.
weaknesses: 1. There might be a major technical flaw in Lemma 1. Since the socially concave game is a subclass of concave game, when one tries to verify the social-concavity of $u_i$, one should also verify that $u_i(x_i, x_{-i})$ is concave in $x_i$. However, neither the Definition 1 nor the proof of Lemma 1 considers this criterion. In fact, I think this loophole might not be easy to fix: the concavity of $g$ and convexity of $d$ are not sufficient to guarantee that a function of the form $r(x_i, x_{-i})=\frac{g(d(x_i))}{g(d(x_i))+C}$ is concave in $x_i$ (one can easily come up with counterexamples). One possible fix is to assume that $\lambda_i$ is sufficiently large so that even if we do not know the concavity of $\frac{g(d(x))}{g(d(x))+C}$, $\frac{g(d(x))}{g(d(x))+C}-\lambda_i d(x_i)$ can still be concave due to the convexity of d(x_i). However, the dominance of the cost term in the utility model does not make much sense to me. I hope the authors explain this issue in detail in the response, otherwise, this flaw renders the main theoretical result in Theorem 2 groundless as well. 

2. The stability guarantee offered by the socially concave property is a weak one in my perspective and does not provide sufficient real-world implications. As the authors acknowledged in L. 168, only the average strategy sequence over time converges to the Nash equilibrium. This means it does not guarantee the last-iterate convergence (the most common convergence concept in practice) since it does not preclude the cycling pattern of strategies (which is commonly observed in many game structures, e.g., in [1], gradient dynamics can cycle in minimax zero-sum game). Such a weak notion of convergence makes me skeptical about the significance of the theoretical result.

3. Insufficient related work. This paper tries to study no-regret dynamics running on a proposed SEO game which is socially concave: 
- Socially concave game is not a new concept: it is actually widely known as a criterion to verify monotone games (which is also a subclass of concave games and are extensively studied due to its provided nice convergence properties [2, 7]). The discussion of socially concave games can be found in appendix A.2 of [2], though without explicitly mentioning its name, and also [3]. I'm wondering since there are many works providing alternative dynamics that guarantee stronger last-iterate convergence in monotone (and thus socially concave) games, why the author insisted in establishing a weaker convergence result under no-regret dynamics. 
- Some related studies propose similar game structures modeling competition among content publishers, with a guarantee that the resulting game is monotone (see [4,5] and possibly more). 
- In addition, no-regret dynamics and their convergence in similar content publisher games are studied in [6]. 

Overall, I like the clear presentation and high-level conceptual contribution of this work. I lean towards rejection mainly due to: 1. a potential major technical flaw in the proof, and 2. the weak convergence guarantee and the insufficient discussion of related works make the contribution limited. However, I'm open to raising my score if the authors convince me there is something I have missed, or show a reasonable way to fix the first technical issue. 

[1] The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization, Neurips 2018
[2] Bandit learning in concave N-person games, Neurips 2018
[3] On existence and uniqueness of equilibrium points for concave N-person games, Econometrica 48(1) 251.
[4] Human vs. Generative AI in Content Creation Competition: Symbiosis or Conflict?, ICML 2024
[5] User Welfare Optimization in Recommender Systems with Competing Content Creators, KDD 2024
[6] How Bad is Top-K Recommendation under Competing Content Creators?, ICML 2023
[7] Doubly optimal no-regret learning in monotone games, ICML 2023

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 3
questions: **Questions:**

(Q1) See (W1).

(Q2) See (W2).

(Q3) How do you choose publishers' initial document $x_0^i$ in simulations? 

(Q4) I thought the goal of the "Equilibrium strategy learning" paragraph is to show that the strategies of the publishers not only time-average converge to equilibrium, but also last-iterate converge.  But I don't see how this goal is achieved by Proposition 1.  The $x^{eq}_i$ in Proposition 1 is still a time-average strategy, not last-iterate strategy.  An alternative argument to achieve this goal might be the following: Suppose the game has a unique NE $x$ (which is guaranteed under some conditions in Corollary 1). If the publishers' average strategies converge to $x$, then the last iteration strategies must converge to the same limit point $x$ as well. 



**Suggestions:**

- Equation (4): is $d_i^0(x_i)$ equal to $d(x_i, x^i_0)$? 

- As the authors mentioned, a limitation of this work is that the demand distribution $P^*$ if stationary.  Another future direction could be what if the demand distribution can change in response to the strategies played by the publishers. In recommender systems, for example, users' preferences (demand) can change due to the recommended content they see [1, 2].

[1] Dean & Morgenstern. Preference Dynamics under Personalized Recommendations. EC 2022.

[2] Lin et al. User-Creator Feature Polarization in Recommender Systems with Dual Influence. 2024.
soundness: 3
strengths: (S1) I really like the big question/motivation of this work: how to design a content ranking function to induce a publisher game that admit a stable/learnable equilibrium. While previous work like (Yao et al (2024)) considered how to induce stable equilibrium using payment to the publishers, this paper takes a different and novel approach of using content ranking function, which seems to be very useful in applications where payments are not allowed. 

(S2) The theoretical results are solid and not very straightforward. 

(S3) Writing is very clear.
summary: This paper considers the game among strategic content publishers in information retrieval systems (like search engines and recommender systems), where each publisher strategically chooses a document to maximize exposure minus the distance of the chosen document and their initial document. 
The authors theoretically prove that: if the content ranking function (recommendation policy) is a proportional function with concave activation, then the game is a concave game, thus admitting a pure Nash equilibrium that can be reached by no-regret learning dynamics of the publishers. Simulations with different concave ranking functions validate the equilibrium convergence result, and demonstrate a tradeoff between the publisher welfare and the user welfare.
weaknesses: However, I think there are some theoretical and experimental limitations in this work. 

Theoretical:

(W1) The main result shown by the authors (a concave ranking function can induce a publisher game with a learnable/stable equilibrium), although is not very straightforward, largely follows from the classical concave game theory.  Another practically relevant and technically interesting question is the welfare property of the learned equilibrium.  Unfortunately, the authors didn't provide any welfare characterization theoretically.  For example, can you prove a "price of anarchy" bound for the equilibrium? Can you characterize the publisher-user welfare tradeoff? 


Experimental: 

(W2) Some parts of the simulation setup feel unnatural: 

(W2.1) First, why do you first sample a small number $s$ of information needs and then consider the discrete uniform distribution on those $s$ points?  This does not seem to capture the real world where the demand distribution spans across a large range, with $s$ being millions (if I interpret each point as an Internet user).  Why don't you just let the demand distribution be a continuous distribution with support being the full unit cube $[0, 1]^k$? 

(W2.2) Second, the number of publishers $n$ is too small (<=10). You observed that the user welfare decreases with $n$ because "publishers adhere to their initial documents more when $n$ increases".  However, if $n$ becomes much larger, the $n$ publishers can cover a large space in the unit cube $[0, 1]^k$, which means that the information needs of different users should be more easily satisfied.  So we might see a "U" curve for user welfare.  I'm afraid that your observation of "user welfare decreasing with $n$" is an artifact of too-small $n$ or the choice of discrete demand distribution as I said in (W2.1).

It would be nice to include some experiments with continuous distributions and a larger number of publishers.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 4
questions: None
soundness: 4
strengths: I really enjoyed reading this paper. The exposition is very clear and it was very easy for me to follow, despite me having relatively little exposure to algorithmic game theory. I do believe this work is impactful, as it is important to understand how the content providers are going to strategize on search platforms. The way I see it, this provides some guidelines for what kind of ranking functions may be used for search ranking. That being said, this is not my primary area of research, and I will leave the judgement of novelty to other more knowledgeable reviewers.
summary: This paper studies the strategic behavior of content creators in an independently mediated recommendation platform from a game theoretic lens. In this setting, the goal of the any content creators is to maximize their exposure to an arriving user by the recommendation platform which uses a ranking function to map the creators’ contents to a distribution over all the creators (which becomes the exposure of their content to the arriving user). The content creators strategies (i.e. the content they produce), as well as the information needs of the arriving user are modeled as vectors in the same embedding space (a common assumption in dense retrieval) endowed with some semi-metric for measuring the distance (relevance) between a creators content and the users requirement. It is further assumed that each content creator has an initial piece of content (a base vector) that they can modify to increase the exposure of this document to the arriving user by the ranking algorithm. However, it is further assumed that the creators want to maintain the integrity of their initial document - i.e. the modified document should not be too far away (in terms of the semi-metric distance) from their initial document. This is modeled by assuming that the utility of the content creator which is their exposure of their (modified) content to the user by the ranking algorithm, is further penalized (linearly) by the distance of the modified document from the original document. In this general setting, the authors aim to understand the learning dynamics of the content creators if the creators were to employ a no-regret learning algorithm for minimizing their regret (defined over their utility). 

In this setting, the authors show that if the recommendation platform were to use a particular kind of a ranking function, which they term “proportional ranking function”, then the resultant game has several desirable properties. This proportional ranking function is a function that loosely converts the vector of distances of the content creators documents from the users information requirement into a distribution, and has a form that structurally looks like the softmax, but is more general as it allows for more general activation functions. In particular, the authors show that if the activation function within this proportional ranking function is concave, then the resultant game has a nash equilibrium, and moreover, the learning dynamics will converge to it if every player employs any regret minimization algorithm that achieves sublinear regret. 

The authors validate their theoretical guarantees with simulations, experimenting with proportional ranking functions with different activation functions. They experimentally analyze the effect of several parameters within their model, such as the dimensionality of the embedding space, the penalty factor (that penalizes the distance of the modified documents from the initial document in the creators utility functions), and the number of publishers.
weaknesses: That biggest limitation I see with this work is the form the utility function takes: it is a linear function that is the expected exposure of the document penalized by the distance from the initial document with some penalty factor. In practice, I assume the utilities of the content creators would be some more complicated payoff structure that may not necessarily increase linearly with exposure. Do the authors have any ideas as to what the learning dynamics would look like for more general utilities that are monotone, but not necessarily linear in the exposure, or what technical barriers might be faced that might make studying this difficult?

Meta-review: The paper analyzes the strategic behavior in recommender systems, focusing on how content providers adapt their strategies to maximize visibility under different ranking principles, using no-regret learning dynamics, when competing. The paper moreover explores the stability of Nash equilibrium of the resulting dynamics and their convergence properties. There are various contributions including modelling SEO as a game and proving convergence of no-regret learning dynamics when the activation function in the ranking mechanism is concave. All the reviewers were positive or slightly positive about this work and the AC shares the same opinion and recommends acceptance.

Decision: Accept (Poster)