On the Convergence of No-Regret Dynamics in Information Retrieval Games with Proportional Ranking Functions
Authors: Omer Madmon
Idan Pipano
Itamar Reinman
Moshe Tennenholtz
Venue: ICLR 2025 Poster (2025)
Keywords: Game theory
no-regret dynamics
recommendation systems
information retrieval
Primary area: learning theory
TL;DR: We characterize a natural set of ranking functions for which no-regret dynamics of content providers converge, through the lens of socially-concave games.

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.

Published as a conference paper at ICLR 2025
ON THE CONVERGENCE OF NO-REGRET DYNAMICS IN INFORMATION RETRIEVAL GAMES WITH PROPORTIONAL RANKING FUNCTIONS
Omer Madmon
Idan Pipano
Technion Israel Institute of Technology cmermadmont campus. technion....... ac. i1
Technion Israel Institute of Technology
i idan. pipanop campus... technion.
Itamar Reinman
Moshe Tennenholtz
Technion Israel Institute of Technology it ttmarr@campus technion. ac. i1l
Technion Israel Institute of Technology moshet moshet@technn @technion. ac.il
ABSTRACT
Publishers who publish their content the web act strategically, in a behavior that can be modeled within the online learning framework. Regret, a central concept in machine learning, serves canonical measure for assessing the performance of learning agents within this framework. We prove that any proportional content ranking function with 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 differ- ent choices of the activation function, using a state-of-the-arl no-regret dynamics algorithm. Furthermore, we demonstrate how the choice of the ranking function and changes in the ecosystem structure affect these welfare measures, well as the dynamics' convergence rate.
INTRODUCTION
In the of digital content consumption, recommender systems play 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 strategic behavior to maximize visibility (Qian & Jain 2024). 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 (Kurland Tennenholtz) 2022).
These dynamics have major implications for various economic aspects of the ecosystem. First, strategic behavior affects the welfare 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 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 aspects have been shown to be interconnected in Madmon al. 2023).
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 dy-
All authors contributed equally this work.

---

Published as a conference paper at ICLR 2025
namics has been studied in the context of information retrieval under different modeling assumptions (Ben-Porat et al. 2019b: Madmon et al. 2023).
In this paper, study no-regret learning dynamics in information retrieval games, as they particularly relevant for modeling SEO behavior. In many practical applications, publishers use the service of SEO experts, who employ advanced techniques maximize the visibility of their content. These experts are judged based on hindsight taaasigght-secfffcalllyyy how much more they could have achieved had they known their competitors' strategies in advance. This retrospective, backward-looking evaluation, which SEO strategies aim to minimize, is precisely encapsulated by the concept of regret.
In the spirit of previous work (Hron al.
2022 Jagadeesan et al. 2023 Madmon al. 2023 Yao
iet al., 2023: 2024a b c). we take a game-theoretie approach and model SEO as game. In our model, both content and users are represented in continuous, multi-dimensional embedding space, and the content providers aim to maximize exposure while maintaining the integrity of their original content. As in Madmon et al. (2023), 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 Tube 2023). These mechanisms contain, among others, search engines that control the probability of presenting documents in response to user query. That is, the mechanism considered 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 We define natural class of ranking functions we term proportional ranking functions (PRFs). 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, subclass of concave games presented in Even-dar et al. (209)), 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, establish a rather stronger statement by proving the equivalence of the following three conditions: the activation function is concave; any induced game socially concave; any induced game is concave (as in [Rosen| 1965). This result can also be interpreted as addressing the learnability of equilibrium strategies' embedding representations from the publishers' perspective. It highlights how platform designers can devise ranking schemes that induce ecosystems in which publishers can learn an equilibrium through no- regret dynamics. This learnability result also serves as a stability guarantee, since the publishers know that they will not gain much by deviating from the learned equilibrium. Importantly, as the learned equilibrium is pure, this means the publishers will play deterministically, thus achieving stability.
We also study the empirical trade-offs between users' and publishers' welfare under different choices of the activation function, using a state-of-the-ee no-regret dynamics algorithm (Farina et al., (022). In addition, we demonstrate the effect of the game parameters such the penalty factor and the number of publishers on the publishers' welfare, the users' welfare and the convergence rate.
1.1 RELATED WORK
In recent growing line of research work, a variety of game-theoretic frameworks have been proposed to analyze the strategic dynamics of content providers 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 (Ben-Porat & Tennenholtz [017]] 2018: Ben-Porat et al., 2019a). The Shapley mediator was proposed as mechanism satisfying both stability (in the form of equilibrium existence guarantee) as well as faimnes--related axioms.
Another concurrent line of works focused on the analysis of an adversarial information retrieval framework, in which content providers compete on exposure (Ben Basat et al. 2015 2017). These works demonstrated the sub-optimality of greedy ranking according to the probability ranking principle (PRP) of Robertson (1977) in terms of social welfare at equilibrium. Raifer et al. (2017) then studied both theoretically and empirically the SEO competition in repeated setting. Under similar modeling assumptions, Ben-Porat et al. (2019b) showed that better-rreponse dynamics of publishers in PRP-based retrieval games are guaranteed to converge.
2

---

Published as a conference paper at ICLR 2025
More recent studies strategic behavior within recommendation and search ecosystems have adapted several modeling assumptions that reflect the use of deep learning and dense representations (Hron ct al. 2022 Jagadeesan et al. 2023 Madmon et al. 2023 Yao et al. 2023 2024a blc). Unlike earlier studies, these recent efforts assume that content is represented within a continuous embedding space, rather than discrete set of "topies". In contrast Yao al. (2024b), 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 (Hron et al., 2022; Jagadeesan al. [0023] Yao et al. 2024a blc) and the study of learning dynamics (Madmon et al. 2023] Yao et al., 2023) under specific exposure or
rewarding mechanisms. In contrast, this work characterizes a general, rich and intuitive family of
mechanisms that guarantee the convergence of no-regrei dynamics to Nash equilibrium M
The fundamental connections between no-regret learning and same-theoretic solution concepts (Foster & Vohra, 1997; Freund & Schapire, 1999, HHart & Mas-Colell, 2000; BBlu et al.) 2008
Roughgarden| 2015) have made the eggretmmnimization framework very appealing to the machine
learning and artificial intelligence communities (Rakhlin & Sridharan 2013 Bowling et al. 2015
Syrgkanis et al., 2013 Moravčík et al. 20177] Brown & Sandholm [20 ( Kangarshahi et al. 2018
Daskalakis et al., 2021 Farina al. [022] Anagnostides al. (0024). In particular, the notion of
concave games (Rosen
1965) and its connection to the convergence of no-regret dynamics showed
by Even-dar et al. (2009) plays crucial role in our analysis.
PRELIMINARIES
Game theory An n-person game is a tuple G (N, [X,)eN furtee), where N = {1, .......) n2 is the set of players, X; is the set of actions of player i, and u, : X -> R is the utility function of player where X X1 x x X,, is the set of all possible action profiles. Throughout the paper, we assume that for every player i, X, is convex and compact set of actions. In addition, we assume that u, is twice differentiable and bounded for all
For any action profile x E X, we denote by x=; (21, ... ... the actions of all players except player i within the profile æ. An action profile said be an e-Nash equilibrium (s-NB) if for any player i, and for any action x E X,, deviation of player i from to z does not increase her utility by more than e. Formally, for any E 2 N, Var E XG For & = 0, a O-NE is referred to as Nash equilibrium (NE).
X is an S-NE if u,(x', x=1) - (z(x) S E, Vi
No-regret dynamics No-regret dynamics is a well-known type of dynamics within the online
(e) E X; learning framework, in which each player i is a learning agent that has to select strategy x;
in every round E N, in response to the sequence of the observations she has received up until round t. A widely accepted way to measure the performance of player up to some horizon time T E N in this setting is regrei defined as follows:
) Σ (a((()))
T = max Reg
Σ uelass xe
x;EX;
That is, the regret of player 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 the online learning literature, e.g. [Farina et al. (2022). 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 player observes V., (2x()))) no-regres dynamics is dynamics in which for any player i, Reg! o(T), meaning that the player's 's regret grows sub-linee sub-linearly with respect to the time horizon T.
Concave games concave game if for any player i, u, (i)) is (strictly) concave in z; for any fixed z-i. In his
We now introduce two special classes of games. A game Gi is said to be a (strictly)
While Yao al. 2023) also studied no-regret dynamics, their analysis is focused partieular structure of publishers incentives. They also did not study stahility criteria such as convergence to a Nash equilibrium, hut instead focused on studying average welfare over time.
We consider the notion of external regret, not to be confused with internal ('swap' regret.
3

---

Published as a conference paper at ICLR 2025
seminal work, Rosen (1965) introduced the class of concave games, and showed that every (strictly) concave game has a (unique) Nash equilibrium " An important subclass of concave games is the class of socially-concave games, introduced by Even-dar al. (009)).
Definition 1. A game G is socially-concave if the following properties hold:
Al. There exist strictly positive coefficients 01,...,0n function g(x) = Ei=1 a4 (,(z)) is concave in æ.
On > O, such that >i= OG = 1 and the
A2. The utility fanction of each player i is convex in the actions of all other players. That is, Vi E N, Vay E x,, the function (xx-2) = ui( x-i) is convex in --
game is a concave game, but the reverse direction is not necessarily true. [Even-dar et al.] (2009) 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 the average action vector converges to a Nash equilibrium.
Even-dar et al. 2009) showed that every socially-conee
Theorem 1. Evvnn-dar al. 2009 Let (x(") H[=1 be a sequence of strategy profiles in a socially- concave game. Then the average strategy profile vector a(T) == 7 Σi= x(1) is an ET-NE, where ET
a,Res] and Ommin == minjeN aj.
Oue Ejen
3 THE MODEL
An n-player publishers' game is game in which n content providers (publishers) generate content (documents) 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]s. The n publishers, denoted by the set N := [1...., n). constitute the set of players of the publishers' game. For any player E N, player i's set of possible actions in the game is defined to be the embedding space, that is X, == 1]..
Information needs of the users are denoted by x= E [0, 11 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 (Zhan et al., 2020) Zhhoo et al.] (2022). We model the fact that in real life there are often multiple information needs by demand distribution Pa P([0, 1Jx), distribution of information needs. In addition, each publisher has an initial document v) E [0, 1j
Distance between documents in the embedding space is measured by given semi-metrid" [0, 11 x [0. 11f + R., which is assumed to be normalized such that 0 S d(a, < 1 for any two documents a, E [0, 1l Another standard assumption that make is that d(a, x and d(a,x*) are twice differentiable in for all the initial documents {zi hee and for every information need x in the support of P* This assumption is needed for the utilities to be twice differentiable. Moreover, we assume that d(aa. 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 two-fold. Firstly, it measures the integrity to the initial content, with the interpretation that small distance between a publisher's '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 z², with the interpretation that d-proximity implies relevance.
Publishers' exposure to users is determined by a pre-defined ranking function r : [0, 1 x [0, 1 > P(N), selected by the system designer. receives input 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;(2;; x*) the proportion of the users who interested in the information need xx that are exposed to publisher i's document if the strategy profile that is played by the publishers is Typically, r, (x;; x²) would decrease in d(x, x²) and increase in di d(xy, xx" for j *
Concave games are well studicd, and possess some other propertics; see, c.g. 2008 ; Einy et al. 2022 "A semi-metric is similar a metric, except it does not need satisfy the triangle inequality.
5 An alternative interpretation would he that ry (a(;;; x²) is the probability publisher would ranked first in search engine in response to query x" if the strategy profile that is played by the publishers is z.
'I addition, ranking functions should he oblivious, meaning they should exhibit symmetry among publishers.
4

---

Published as a conference paper at ICLR 2025
Each publisher i tries to achieve two goals simultaneously: the one hand, maximize the expected chance of her being ranked first by the search engine, which for a given strategy profile x is E=+-pp- [r; 2²" ); and the other hand, provide content z; which is as faithful possible to her initial document, meaning with d(z;; mb) as small as possible. Her trade-off between these two goals determined by integrity parameter X; O.
Formally, an n-player publishers' game is tuple G == (N,,, (r. faehie (Milee). The set of players of the game is N .I,..., n., y the action space of each publisher N is the embedding space X; = [0, 1j and her utility function is defined as follows:
(x) = EpT~P [r(();=")] - X d(2,, 2b)
(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 ranking function induces socially-concave (concave) games if any publishers' game with r as its ranking function a socially-concave (concave) game.
Note that condition A1. of social concavity holds with a; +. in every publishers' game, since EL T3 1. This leads to the following useful lemma, whose proof is deferred to Appendix B.1 Lemma 1. ranking function r induces socially-concuve games if and only if for every information need x², for every publisher& i E N and for every 3; E Xú Vilzi, x";x";""))) is convex in T-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 proportional ranking function (PRF) if there exists twice differentiable and strictly decreasing fumction [0, R++ such that
g((xx;,)))
r=(1;;²)) Σラ= (dd(z,,x*))
The function g is called the activation function of
Our main objective is to characterize the subset of PRFs that induce socially-concave games. These ranking functions possess various desirable properties, such as the existence of Nash equilibrium, and guarantee that if publishers engage according to any regret-minimization procedure, they will converge 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.
MAIN RESULT
We now provide necessary and sufficient condition for a PRF to induce socially-concave games. This condition turns out to have relatively simple form: the activation function should be concave. We show this by proving a stronger statement:
Theorem Let be PRF with activation function g. Then, the following are equivalent:
The activation function is concave
II. induces concave games
III. r induces socially-concave games
Moreover, if is strictly bi-convex, then induces strictly concave games if and only if g is concave.
In the proof, provided in Appendix B.2 the equivalence of the three conditions is established through circular implications. We first show = III. utilizing Lemma D and standard convexity by showing that given any non-concave activation function
arguments. We then prove we can construct a concoce publishers' game. Specifically, we place all initial documents on corner of the embedding space and the information need the opposite corner and show that,
5

---

Published as a conference paper at ICLR 2025
if there enough publishers, the utility of publisher given that all other publishers stick to their initial documents is not concave in her strategy. Finally, I77. = Ir. follows from the result of Even-dar et al. (2009) that socially-concave games subclass of concave games.
Theorem 2 together with the findings of Even- et al. (2009) that in vocially-coneavy games any no-regret dynamics converges, and the guarantee of Rosen (9655) that (strictly) concave games possess a (unique) NE, leads to the following result:
Let r be a PRF with activation function g. Then, if is concave, any no-regret learning dynamics in any publishers' game induced by converges. Moreover, any induced publishers' game possesses an NE, and if d is strictly bi-convex the NE is unique
Corollary 1.
The strict bi-convexity assumption on the semi-metric is satisfied, for instance, by the squared Euclidean norm, which is the semi-metric use in the simulations conducted in $5 Corollary [ implies that the system designer can readily guarantee convergence in average of no-regret dynamics, by simply choosing a concave activation function. While in S we empirically show that the selection of the specific activation function has a significant effect on various evaluation criteria, convergence of the average profile to an e-NE guaranteed for any concave activation.
Equilibrium strategy learning We now discuss a key practical implication of our main result for real-world platforms, such recommendation systems and search engines. As established, ranking with concave activation only ensures that the average document profile converges to equilibrium, which is weaker notion of convergence compared to the convergence of the final iteration's 's strategy profile. This may seem counter to the platform's goal of stability, where reducing fluctuations over time in publishers' content is a priority. However, from practical standpoint, our main result can be seen as a positive result regarding the learnability of an approximate NE from the publishers' perspective. Assume that each publisher has budget that allows her to hire SEO expert, who utilizes no-regret algorithm, for 7; time periods (determined, for example, by budget constraints). In Proposition | we establish that, under the assumption that the stopping times are not too far from each other, the publishers can learn an approximate NE.
Proposition 1. Let G be socially-concat publishers' game. Suppose each player i accumulates x.)) Rege Ti regret in the first T; rounds. Let x; = T: Et= x: Then x² (1 3..,, an e-NE
with 8 = Tam
1 EjEN
+ (1++X, 21) (Tmax - Tz)). where Tmax max T₃. Ti [Reg]]
This result, whose proof is deferred to Appendix B.3 implics that given that the stopping times are sufficiently large, and not too far apart, any publisher can efficiently learn an equilibrium strategy. This means that each publisher knows that she can play deterministically the strategy she learned, without expecting significant gains from deviating to any other strategy. Consequently, content creation becomes deterministic in the long run, eliminating fluctuations within the corpus and achieving stability Such a stability guarantee ensures predictability regarding the content available in the corpus for both the users and the ecosystem designer, which is crucial for the design of reliable search and recommendation ecosystems.
5 EXPERIMENTAL COMPARISON OF RANKING FUNCTIONS
In this section, present some PRFs 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 from (and complementary to) other lines of work that evaluate the dynamics of human publishers that may be prone to various biases, for example, Raifer et (2117. Therefore, chose to evaluate the ranking functions using a code simulation in which agents use the state-of-the-art no-regret algorithm of Farina et al. (2022). which designated for concave games as in our case.
In Appendix D characterize this NE and provide preliminary welfare analysis. *This also explains why convergence to a correlated equilibrium (CE) may be insufficient for stability. While it is well-known that no- regret dynamics converge to CE in general games (in the same "average" sense), such equilibria allow for non-deterministic actions, leading to the same issue of frequent content modifications over time.

---

Published as a conference paper at ICLR 2025
We compare three families of PRFs based some concave and decreasing functions activation functions.
The linear PRF family: 9tam (t) - t, where b > 1 is the intercept hyperparameter.
The root PRF f'amily: groot (1 t)", where
is the power hyperparameter. The logarithmic PRE family: Rog (t) = In(c - t), where e > 2 is the shift hyperparameter.
Let plin proot and plog be the PRFs induced by these activation functions, Unless stated otherwise. we use the default values of b = + 6, a 2 2 + 8, where 5 = 10-3
Simulation details Our simulations utilize the state-of-the- art no-regret algorithm presented in Farina et al. (2022), the Log- bog-Regglarized 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 7 to decide which action to play in the next round. The important property of LRL-OFTRL is the logarithmic increase in regret the dynamics progresses. Notably, the theoretical guarantee in Farina et al. (2022) applies only to concave games, and, to the best of our knowledge, there is currently games | 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. simulation is said to converge if the average profile has reached an c-NE. Throughouu all simulations, we used homogeneous X; = X for all E N, the squared Euclidean semi-metric d(x,, y) | yll2. learning rate 1/2 and E 10-1, all simulations, we consider uniform demand distributions over sample of E N information needs [T
algorithm in the literature that guarantees sub-linear regret for non-concave
Evaluation criteria To evaluate the performance of the different ranking functions, report three evaluation criteria: the publishers' welfare, the users' welfare and the convergence rate 12 The two welfare measures are defined similarly to previous work (Madmon et al. 2023 Yao et al. 2024b).
The publishers' welfare is defined to be the sum of publisher utilities:
n
U(x)= = Σ (1(x)) =1 > d(a, x/))
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; by 1- d(xx, x²), and expectation is taken over both the demand distribution p* and the distribution over the publishers r(z):
Vxx) = Eg- (1-d(z,,,2)) T((x)) 1 ExtaP-
Σ d(z,,z') ri(a))
(5)
These welfare measures can be evaluated at any strategy profile x E X, but we report the values obtained in the e-NE the dynamics converged to, 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 confidence level of 95% using bootstrap sample size of 500
'In Appendix C.2 we show that indeed under non-concave ranking, resulting dynamics when using LRL-OFTRL. need not be no-regret dynamics.
10 intterestingly, all of the simulations have converged not only in the average sense (which is guaranteed by our main result), but also in the stronger sense of last-iterate convergence.
Note that while we restrict our simulations to uniform demand distributions, any demand distribution can be approximated with large enough.
In addition to these three evaluation criteria, in Appendix C.1 we analyze empirically the effect of the ranking function on the average regret and discuss an interesting correlation with the convergence rate.
IIn Appendix
C.3 we relax the assumptions of uniformity and independence.
7

---

Published as a conference paper at ICLR 2025
1,200
Unear
Uneer
2003-
Linotr
Fublisher Welore
0.455
Usars: Willfare
0.52
oeganthres
603-
000
0.490
10.00
Converence
703-
0.085
0.80
0.375
200
100
08
06
Figure 1: The effect of the penalty factor X, with 3,
3 and l: 3.
Piiieerr Welfere
0.955
Ahm Root
Users Waiffare
Loganthees leot
Conver sgence Rate:
2799-
Roet
Logeriteni
0.200
0.50
2299
0.385
0.80
2750
6.400
3250
0.86
0.935
150
0.310
252
120
Figure 2: The effect of the number of publishers n, with A 0.5, and
5.1 COMPARISON BETWEEN RANKING FUNCTION FAMILIES
Figure 1 presents several interesting trends. A prominent phenomenon in the figure is 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 uniform ranking (i.e., F3s 1,), or, in other words, the ones which the impact of the publishers' content on the ranking is less significant. When ranking the documents using these functions, the publishers 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 [ 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 robust to changes in the ecosystem structure, such as changes the game parameters, and show how these changes affect our evaluation criteria.
less incentivized to create relevant content
The effect of the penalty factor À Figure I Iillustrates how X, the penalty factor, influences our evaluation criteria, showing similar trends those discussed in Madmon et al. (2023). One might expect an increase in À to harm the publishers' welfare, since a larger À imposes greater penalty on the publishers for providing content that differs from their initial documents. Yet, higher also incentivizes the publishers to adhere more closely to their initial documents, which increases the publishers' welfare. These two opposing forces explain the non-monotonic trend observed in Figure I for lower values of X, the publishers' welfare decreases À increases, until it reaches minimum point, after which keeps increasing. The trend in the users' welfare is simpler: it monotonically decreases À increases, likely because higher penalties lead less relevant content from publishers. Lastly, there is no significant impact of the penalty factor on the convergence rate.
The effect of the number of publishers n The influence of n on the welfare measures, as depicted in Figure 2 resembles that of X. Just like X, has two opposite effects the publishers' welfare. On
MTo elucidate this point, let us compare the activation functions gian and grost. Note that grout is a concave transformation of the linear activation function. When applying a square root to number in [0, 1]. the smaller it is the bigger the factor is increased by. Therefore, for any fixed profile, the ranking produced by froot is closer uniform distribution than that produced by ginn-
8

---

Published as a conference paper at ICLR 2025
1,200
Urear Lhuuthm
Uneer
2003-
Linotr
0.455
oeganthres
600-
Legerdlani:
0.52
000
0.440
Convergenc Gnveegence
703-
00.00
0.085
0.50
0.375
200
100
Figure 3: The effect of the demand distribution support size with X = 0.5, and 3.
1.000
2500
0.34
7253-
Pablghes were
0.325
foot
text
2000
0.400
0.985
2250
0.300
0.50
2003
0.06
500-
150
0.370
0.84
Figure 4: The effect of the embedding space dimension k. with 0.5, n 3 and 8 =
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 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 result, the publishers' welfare is not monotonous in n but rather has an internal minimum point. The users' welfare decreases in n since bigger n amplifies publishers' adherence their initial documents, which makes the content in the corpus less relevant to users. Lastly, more players result in slower convergence rate, which is surprising since is measured by the time taken for the last publisher to reach an e-NE.
The effect of the demand distribution support size As depicted in Figure increasing leads to an increase in the publishers' welfare and a decrease in the users' welfare, both trends eventually plateauing. A possible explanation that when increasing s while fixing n, fixed number of publishers compete for an increasing number of information needs, which makes it harder to maximize exposure. Recall that a publisher's utility from exposure the expected value of her exposure for different information needs, when player is unable to meet 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 increases, the publishers tend to focus on different information needs (the ones closest to their initial document), therefore get much simpler dynamics and faster convergence.
The effect of the embedding space dimension k Figure reveals that while & has negligible influence on the publishers' and users' welfare, its effect on the convergence rate is substantial. Specifically, as increases, the dynamics require more rounds 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.
5.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 results once again underscore the publisher- user trade-off discussed $5.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) the values that make the ranking function closer
9

---

Published as a conference paper at ICLR 2025
1,500
2003-
F1019h Welorr
0.455
0.52
Convergnne Rote
002
0.440
703-
0.50
0.385
0.80
0.355
200
100
02
Power typerparameter
Power typerparameter
Power hyperpermmeterr
Figure 5: The effect of in the root ranking function, with À 0.5, 3, and 3.
1.000
0.54
1003
0.225
900
Users Meelare
0.900
Converge-e
692
0.955
500
0.300
0.88
400
0.06
300
0.300
Intercest hyperparametor
Figure 6: The effect of in the linear ranking function, with = 0.5, 12 = 3, = and
1.200
Beiihers weleer
0.355
Usars Walffrr
0.52
0.300
0.50
genee
693
700
0.955
500
0.300
0.6
6.955
200
100
0.500
10
Shift hyperparametor
Shift hyperparametor
Shift Shithrpperrammttrr
Figure 7: The effect of e in the logarithmic ranking function, with À = 0.5, n 3, =3 and A: == 3.
uniform ranking. For example, decrease in the power parameter a of proot can be seen in Figure to correlate with an increase in publishers' and decrease in users' welfare, and indeed when the power parameter approaches O, the root PRF approaches uniform ranking. That is, rroot
0. Similarly, Figures 6 and demonstrate how both the intercept parameter of p and the shift parameter e of pdo are positively correlated with the publishers' welfare and negatively log as oc.
correlated with the users' welfare, as r + 1 as b + co and r
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 PRFs, which are ranking functions that are determined by a one-variable scalar activation function, and established full characterization of which PRFs induce socially-coneee -oncaave games and which induce concave games. We then conclude that any concave activation function guarantees the convergence of no-regret dynamics, therehy offering system designer a rich family of ranking functions that, under the assumption that publishers minimize their regret, guarantee the reach of the system to 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. We examined how these criteria are affected by the ranking function and by changes in the ecosystem structure. In Appendix A we discuss several limitations of our work, which believe can lead to significant future research directions in the field of learning dynamics of content creators within search and recommendation ecosystems.
10

---

Published as a conference paper at ICLR 2025
ETHICS AND REPRODUCIBILITY STATEMENT
The authors of this paper declare that they do not find any potential violations of the ICLR code of ethics] All theoretical results of this paper (stated and $4) are presented with clearly stating
any required assumptions. Rigorous proofs of all theoretical results can be found in Appendix B All of the empirical results are presented with bootstrap confidence intervals (as mentioned in $ The source code is available in the supplementary materials.
ACKNOWLEDGMENTS
This work was supported by funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation programme (grant agreement 740435). All authors contributed equally this work. We would like to thank the anonymous reviewers for their helpful comments.
REFERENCES
Ioannis Anagnostides, Ioannis Panageas, Gabriele Farina, and Tuomas Sandholm. On the convergence of no-regret learning dynamics in time-varying games. Advances in Neural Information Processing Systems, 36, 2024.
Ran Ben Basat, Moshe Tennenholtz, and Oren Kurland. The probability ranking principle is optimal in adversarial retrieval settings. In Proceedings of the 2015 International Conference on The Theory of Information Retrieval, pp. 51-60, 2015.
Ran Ben Basat, Moshe Tennenholtz, and Oren Kurland. game theoretic analysis of the adversarial retrieval setting. Journal of Artificial Intelligence Research, 10:1127-1164, 2017.
Omer Pen-Porat and Moshe Tennenholtz. Shapley facility location games. In Web and Internet Economics: 13th International Conference, WINE 2017, Bangalore, India, December 17-20, 2017,
Proceedings 13, pp. 58-73. Springer, 2017.
Omer Ben-Porat and Moshe Tennenholtz. A game-theoretic approach to recommendation systems with strategic content providers. Advances Neural Information Processing Systems, 31, 2018.
Omer Ben-Porat, Gregory Goren, Itay Rosenberg, and Moshe Tennenholtz. From recommendation systems to facility location games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 1772-1779, 2019a.
Omer Ben-Porat, Itay Rosenberg, and Moshe Tennenholtz. Convergence of learning dynamics in information retrieval games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 1780-1787, 2019b.
Avrim Blum, MohammadTaghi Hajiaghayi, Katrina Ligett, and Aaron Roth. Regret minimization and the price of total anarchy. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pp. 373-382, 2008.
Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. Heads-up limit hold' em poker is solved. Science, 347(6218): 2015.
Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418-422 2018.
Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. Advances in Neural Information Processing Systems, 34:27604-27616, 2021.
Ezra Einy, Ori Haimanko, and David Lagziel. Strong robustness to incomplete information and the uniqueness of a correlated equilibrium. Economic Theory, 73(1):91-119, 2022.

---

Published as a conference paper at ICLR 2025
Eyal Even-dar, Yishay Mansour, and Uri Nadav. On the convergence of regret minimization dynamics in concave games. In Proceedings of the Forty-First Anmual ACM Symposium on Theory of Comput- ing. STOC '09, pp. 523-532, Association for Computing Machinery, 2009. ISBN 9781605585 doi: 10.1 153646. URL
/tta:::/doo..rro
1536486
Gabriele Farina, Ioannis Anagnostides, Haipeng Luo, Chung-Wei Lee, Christian Kroer, and Tuo- mas Sandholm. Near-optimal no-regret learning dynamics for general convex games. In Ad- vances in Neural Information Processing Systems, volume 35, pp. 39076-39089, Curran Asso- oet.://aeecaasre..........o....a
ciates, Inc., 2022. URL ff22 htt.:/aaaaa0e1111c110eeeeeeeeeee ottp:///eaaacccccaoeeeeeeoeeoarr
files/paper/
Dean P Foster and Rakesh Vohra. Calibrated learning and correlated equilibrium. Games and Economic Behavior, 21(1-2):40, 1997.
Yoav Freund and Robert E Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29( (9)1-))79--,,,, 1999.
Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading correlated equilibrium. Econometrica, 1875)1112--1150, 2000.
Jiri Hron, Karl Krauth, Michael Jordan, Niki Kilbertus, and Sarah Dean. Modeling content creator incentives on algorithm-curated platforms. arXiv preprint arXiv:2206. 13/02, 2022.
Meena Jagadeesan, Nikhil Garg, and Jacob Steinhardt. Supply-side equilibria in recommender systems. arXiv preprint arXiv.2206. 13489, 2023.
Ehsan Asadi Kangarshahi, Ya-Ping Hsieh, Mehmet Fatih Sahin, and Volkan Cevher. Let's be honest: An optimal no-regret framework for zero-sum games. In International Conference Machine Learning, pp. 2498-2496. PMLR, 2018.
Oren Kurland and Moshe Tennenholtz. Competitive search. In Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 2838-2849, 2022.
Omer Madmon, Idan Pipano, Itamar Reinman, and Moshe Tennenholtz. The search for stability: Learning dynamics of strategic publishers with initial documents. arXiv preprint 1.Xii:2305.1669) 2023.
Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisy. Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no- no-limit poker. Science, 356(6337)5508 5110333388133,,00000 2017.
Kun Qian and Sanjay Jain. Digital content creation: An analysis of the impact of recommendation systems. Management Science, 2024.
Nimrod Raifer, Fiana Raiber, Moshe Tennenholtz, and Oren Kurland. Information retrieval meets game theory: The ranking competition between documents' authors. In Proceedings of the 40th International ACM SIGIR Conference Research and Development in Information Retrieval, pp. 465- 2017.
Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. Advances in Neural Information Processing Systems, 26, 2013.
Stephen E Robertson. The probability ranking principle in ir. Journal of documentation, 1977.
J Ben Rosen. Existence and uniqueness of equilibrium points for concave n-person games. Econo- metrica: Journal of the Econometric Society, pp. 520-534, 1965.
Tim Roughgarden. Intrinsic robustness of the price of anarchy. Journal of the ACM (JACM), 62(5): 1-42, 2015.
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence of regularized learning in games. Advances in Neural Information Processing Systems, 28, 2015.
12

---

Published as a conference paper at ICLR 2025
Takashi Ui. Correlated equilibrium and concave games. International Journal of Game Theory, 37 (1):1-13, 2008.
Fan Yao, Chuanhao Li, Denis Nekipelov, Hongning Wang, and Haifeng Xu. How bad is top-k recommendation under competing content creators? In Proceedings of the 40th International Conference on Machine Learning. volume 202 of Proceedings of Machine Learning Research, pp. 39674 39701. PMLR, 23-29 Jul 2023. URL httphttts///proeeeiiiii htg.://ceeccnngg..mm.p.srs////. 1yao23b.. htmll
Fan Yao, Chuanhao Li, Denis Nekipelov, Hongning Wang, and Haifeng Xu. Human vs. generative Al in content creation competition: Symbiosis or conflict? In Proceedings of the 41st International Conference on Machine Learning. volume 235 of Proceedings Machine Learning Research, pp. 56885-56915 PMLR, 21-27 Jul 2024a. URL ssttps://proceedinngg mlr pressssss/..p....s press/
#235/yao24B. html
Fan Yao, Chuanhao Li, Karthik Abinav Sankararaman, Yiming Liao, Yan Zhu, Qifan Wang, Hongning Wang, and Haifeng Xu. Rethinking incentives in recommender systems: Are monotone rewards always beneficial? Advances in Neural Information Processing Systems, 36, 2024b.
Fan Yao, Yiming Liao, Mingzhe Wu, Chuanhao Li, Yan Zhu, James Yang. Jingzhou Liu, Qifan Wang, Haifeng Xu, and Hongning Wang. User welfare optimization in recommender systems with competing content creators. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 244 pp. 3874-3885 New York, NY, USA, 2024c. Association for Computing Machinery. ISBN 9798400704991. doi: 10.1 0114452663752886722221
URL http//ttpee//oo..rrr/00111111/11
3672021
YouTube. Youtube partner program overview eligibility, 2023. URL httpss:/supporx:
google.com httele/ccooooootee//eeeeaea
Jingtao Zhan, Jiaxin Mao, Yiqun Liu, Min Zhang, and Shaoping Ma. Learning to retrieve: How to train a dense retrieval model effectively and efficiently. arXiv preprint arXiv:2010. 10469, 2020.
Wayne Xin Zhao, Jing Liu, Ruiyang Ren, and Ji-Rong Wen. Dense text retrieval based on pretrained language models: A survey, 2022.
A LIMITATIONS
We now discuss several limitations of our work. Although we prove convergence of no-regret dynamics whenever the activation function is concave, our approach provides no insights regarding convergence in the non-concave case. One major challenge studying no-regret dynamics under non-concave activation is the absence of algorithm that guarantees sub-linear regret in such games (see Appendix C.2 for further discussion). We assumed each publisher produces a single document, while in practice, they may publish multiple documents to compete across various information needs. We also assumed a specific cost function to model the cost publishers incur when deviating from their initial documents. Another limitation of our experiments that we drew 2i and xx i.i.d from uniform distribution, and the trends presented in our analysis are not guaranteed to hold for other ecosystem distributions. However, in Appendix C
experiment with several distributions that relax these assumptions. A theoretical convergence rate analysis remains out of scope. Finally, we acknowledge the gap between our theoretical guarantee of convergence in the average sense and the empirical observations of last-iterate convergence. We believe that addressing these limitations in future work can provide valuable insights and enhance the applicability of our findings.
B PROOFS
B. PROOF OF LEMMA 1
Proof. Let x* [0, 10. N, E X,. If induces socially-concat 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 x² is socially-concave game. So by condition A2, of the
13

---

Published as a conference paper at ICLR 2025
definition of social concavity, (x) =x;2x;")) x.. d(;, 26) is convex in 2-1. Since -2,, x()) fixed in 2 --z;, this implies that r. (2; x²) is convex in 2-4 <
First, notice that for every ranking function condition Al. of the definition of social concavity
holds with 03 L.
n
((x)
Σ 04
uz(x))
Σ n
(ri(1; de d(
==1
(6)
1
A 2(z
since Ei= (x; for any strategy profile X and information need x E [0, 1]k. Now, g(x) concave since for every
N and sh E 10, d(x,,=)) convex in v;. Regarding condition A2. it can be easily shown (using the linearity and monotonicity of expectation) that
the convexity (;( x*) x=; for any z; E X,,x* E [0, 1] implies that En--P- [r<(#; is convex in x- for any I2 E X,, Together with the fact that d(x;, =t) is fixed in T- we get that un (x) = EP [r: x²) x d(x,, 2/)) is convex in E- for any I, E X₃-
B.2 PROOF OF THEOREM 2
Proof. We prove the equivalence of the three conditions by showing that concavity of the activation function is sufficient for social concavity ( I.T.). then showing that if g is not concave then r
does not even induce concave games (7..
L. which wraps up the proof of the equivalence of IT.. since Even-dar et al. (2009) showed that any socially-concave game is a concave game
III. By Lemma| ! it is enough to show that for every information need x", for every publisher N and for every z; X4, (2,, x²) is convex as function of xf So let E N, x [0, 11 24 X, Denote C g(d(z;, and h(x_;) = Ejti 9 (d((x) x*)) So we need to show that the following function is convex in J-1i
g(d(I,,z") ((01, E)=1((((z),
C
C C++((=)))
By our assumption that d bi-convex, d(z,,z") is convex in Tj for any player j E N. Since is concave and decreasing, ((d(z,)=*)) concave in ry as a composition a concave and decreasing function on a convex function. So h(x=;) is concave x- as sum concave functions.
Now, define function é: IR + R follows: {(t) C+7 So:
( (1((=_))
>>> 0 guarantees that is convex and decreasing in R.. Therefore ([,,,==;;""" is convex in x- as composition of a convex and decreasing function on a concave function.
mT.
If g is not concave, there exists à E (0, 1) such that ga) > O. We now construct publishers' game instance G, with 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 A: = 1,
number of players n that satisfies n > 2g' (a)²
gd (a) + a one-hot (Dirac) distribution on the information
needs that places probability on x= = 0 and semi-metric d b) = |a b). We choose the initial documents of all players E N to be xr = Note that since all initial documents are located the only information need is located at O, the utilities are indeed twice differentiable, we assume in the sequel. Let f_1 be a strategy profile of all publishers but publisher 1 in which each of the other publishers/ + plays é = 0. Now, simple calculation (deferred to Appendix B.2. shows that the function f(11 == U1 (11, 1) satisfies (") > 0. Hence, 41 (I1, 1 is not concave in æ1, so by definition G is not concave game.
and
The above wrapped up the proof of the equivalence of the three conditions. We now proceed to prove the additional part of the Theorem, namely that if is strictly bi-convex, then induces strictly
14

---

Published as a conference paper at ICLR 2025
concave games if and only if is concave. Since we have already shown that if induces concave games then the activation is concave, it remains to show that if the activation concave, then r induces strictly concave games, which
prove
Let proportional ranking function with concave activation g. Let G be a game induced by r. We will show that G is strictly concave by definition fix some player i N and let z X-; be some strategy profile all players but i. We need to show that 4, x_;) is strictly concave in Zi. Let x² be an information need in the support of the demand distribution p of G. Since d is strictly bi-convex, d(z,,, x²) is strictly convex in I;. Also, g is concave, and recall that is assumed be strictly decreasing (see Definition 3). Therefore, g(d(z,, x:") xx") is strictly concave in 2; composition of a concave and strictly decreasing function with strictly convex function. Now, define the function:
M(I) ++ jjtt g(d(z;,
Note that since
> h is concave and strictly increasing function. Therefore,
g(d(z,,2")) プ {(((z,,
h(g(d(x,,2"))
(10)
is strictly concave in as a composition of concave and strictly increasing function strictly concave function. To sum up the proof, note that
uy (Ti x+)) PP [r;(x;"")] A; d(z;, 2b))
(11)
strictly concave in 2; since the first term is strictly concave expectation of strictly concave function and A d();,))) is strictly convex in 2; by the assumption that d is strictly bi-convex.
B.2.1 FULL DERIVATION OF INEQUALITY (a) FROM THE PROOF OF THEOREM 2
This appendix provides detailed derivation of the equation ("(ā) > 0 from the proof of the main result.
Proof. By the definition of the utility in publishers' games, and since in the game constructed the distribution over the information needs a one-hot distribution that places probability 1 on x = 0:
f(x1) in (#1.2_1) = -rr11111111 (2,, (21, -1) x1)
(12)
Recall that is proportional ranking function with activation function and that we chose d(a, b) = Ja b) and Jr] 1:
g(d(z1, 0)) f(x)) Ejt (d( + ((((x110)) A1 21)
(13)
Recalling that for all the other players j # we chose 2, 0 we get:
g(x1)
g(x1)
f(x1) Σjji 9()) + g(x1)
A1 -x1) (n - 1)g(0) + g(x))
\1 x1)
(14)
Let us denote C = (0))(000). So
g(x1) f(x1) C+ g(x1)
A1 x1)
(15)
Now let us calculate the second derivative of f. First, its first derivative is:
15

---

Published as a conference paper at ICLR 2025
(z1(
((
X
(16)
(C+ (C+)(())))
And f's second derivative is given by:
C
(x) (c+ g(x)))
(17)
Substituting 21 we get:
(a) (c + +(ā))
9 ("(a)(C - 22)
(18)
Now, recall that we chose à to satisfy (ā) > 0. Also, choice of n C²= (n 1)g(0)= 20'(a)² (a
2g (a) g'(a)g(0} + ensures that
Moreover, g is a positive function so (C+o(a))
0. We can use this
to bound (a) from below:
[((aa) 2 20(
("(a)> > (C + (()) (())()))
g²(à) + + - (g)
(19)
(C + g())) (()) >0
(20)
where the last incquality is since C, ga) and g(ā) are all strictly positive.
B.3 PROOF OF PROPOSITION 1
Proof. Recall that each player i engages with no-regret algorithm for T. timesteps and then plays 7, ΣT ( for all timestep > T. Consider { (t)) Tin
t=1 Theorem guarantees that the ayReg, and Qmin == minjeN Oij Tam
profile (Tma)) T
1 Eimy (+)) is e-NE with 1. ΣjEN
Oama
where {at) are the social-concavity parameters. However, note that the profile (Tmms exactly Icl, This is because adding the average of multi-set to the multi-set does not change its average. Formally, for any publisher i E N:
T
Fan
T m
Tmax
T
Tmux
(21)
T
T max
T.
T Tmax
Tmax
where the second equality is by our assumption that after T, timesteps publisher commits to xz Now, recall that we saw in the proof of Lemma I that any publishers' game satisfies condition A1. of social-concavity with a; ne Therefore, we can take a, and obtain that n is e-NE with
Reg
Tim
(22)
T
JEN
max
The result of the Proposition now follows from the following bound on Reg."" the regret of player including the phase where she is committed to the fixed strategy x1
16

---

Published as a conference paper at ICLR 2025
Tms
Tim
Reg Tam
Ug (zz.
Σ u (z(11)
max x;Ex;
Tj
Tua
Tan
Σ max
Ug (I))
+ max 2, 5,EX;
Σ t
Uy (z (1))
Σ us (x(1))
a;EX;
(23)
Time Σ 1=
Tim
= Regg T:
+ max x;Ex;
uy (1g), (3))
Σ U (x(((()) t=
< )eg T: + (Tmax Tī) - (Tmax -T}) (->p)
= Reg,
Ti (1 + Xn) (Tmax Tj)
The last inequality is because the utility function of player j is bounded in [->ş; 1].
C ADDITIONAL EXPERIMENTS
C. REGRET COMPARISON
To compare the regret incurred by publishers throughout the dynamics across different ranking functions and game parameters, we conduct additional simulations. Each these simulations runs for fixed number of rounds 7 100, rather than until convergence to e-NE, to ensure unbiased comparison (e.g., in cases where for a fixed c > O, some dynamics converge to c-NE faster than others) 15 At the end of each run, compute the regret for each publisher (normalized by T), and then average over all publishers. That is, the average regret is defined and computed as follows:
1 T
Σ Reg JEN
Figure illustrates how various game parameters impact the average regret of publishers. Sub- figures 8b. Sc and [d. strong correlation observed between the effect of game parameters on the average regret and their effect on the convergence rate, the latter of which is discussed in $5.1 This correlation is expected since slower convergence rate leads publishers to spend more time playing sub-optimally, resulting in higher average regret. It is worth noting that the effect of is more pronounced compared to n and s, indicated by the larger scale of the average regret axis in Sub-figure 3d
An exception for these trends agreement the effect of X, displayed in Sub-figure Sa While $5.1 indicates that À has no significant effect on the convergence rate, it is evident that the publishers average regret increases
increases. intuitive explanation is that with larger X, each publisher experiences greater regret for rounds played sub-optimally, as the penalty for deviating from their initial document is greater.
Figure 9 shows perfect correlation between the impact of the various ranking function hyperpa- rameters on the average regret and their effect on the convergence rate (the latter is discussed in $.2
C.2 BEYOND CONCAVE ACTIVATIONS: THE SOFTMAX RANKING FUNCTION
While our results provide strong theoretical guarantees for proportional ranking functions induced by concave activation functions, they not apply to any other proportional ranking scheme. One particularly interesting case is the softmax ranking scheme, which is the proportional ranking function obtained by setting an exponential activation function Jeap (t) = e -B where a hyperparameter
We use T = 100 rounds per simulation observed that the regret does not change significantly after the first 100 rounds.
17

---

Published as a conference paper at ICLR 2025
0.077
Unear
Linerr
0.026
Logantaenc
5.20
Logaritin
0.025
Roct
Rect
0.023
0.023
6.022
0.022
8.021
0.200
0.09
0.019
0.08
2.018
(a) The effect of the penalty fac- tor À the average regret of the publishers.
(h) The effect of the number of publishers the average regret the publishers.
0.027
Unear
0.026
Logankame Root
Logurbamk
0.025
8.025
Hest
Nverg
0.022
0.023
Averoge
0.03
0.021
0.020
0.0.9
3.005
(c) The effect of the demand dis- tribution support size on the erage regret of the publishers.
(d) The effect of the embedding space dimension the average regret of the publishers.
Figure 8: The effect of the different game parameters the average regret of the publishers, with default values of = 0.5, n 3, 8 3, and k 3.
0.927
0.827
0.627
0.026
0.526
0.026
g 0.022
0.032
8 0.025
20.024
20.004
20.00
8 6.023
0.023
0.023
0.0222
0.522
0.00
0.821
0.823
0.023
0.028
0.023
0.020
0.019
0.238
0.018
2
53 02 0.4 05 0. 03
3
Intercept hyperparametor
Power hyperparameter.
Shift hyperpaaaeeter
(a) The effect the intercept in the linear proportional ranking function.
(b) The effect the power a in the root proportional ranking function.
(c) The effect of shift in logarithmic proportional ranking function.
Figure 9: The effect of the ranking function hyperparameters on the average regret of the publishers, with À = 0.5, 3, 3, and k = 3.
we call the inverse temperature hyperparameter. One key question that arises is: do no-regret dynamics converge under non-concave activation functions, such as the softmax ranking function?
One major challenge in answering this question is that, to the best of our knowledge, there is no known algorithm that guarantees sub-linear regret in general, non-concave games. The LRL-OFTRL algorithm used in our simulations $5 guaranteed to provide sub-linear regret only when the game is concave. Nevertheless, we experimented with the exponential activation to determine whether, at least empirically, it could yield sub-linear regret.
When applying the LRL-OFTRL algorithm for various game configurations and various values of 3, we observed that the dynamics do converge, despite the non-concave activation. However, upon closer analysis, found that although the dynamies converge, the publishers' regret does not meet the conditions for no-regret dynamics. In many cases, the regret grows linearly over time, particularly as B increases.
Consequently, we excluded the softmax ranking function from our comparisons. Figure DirrrionnssFuuurroouulluttttttt i0lllustraesss the regret time for each publisher in random game instance induced by the exponential
18

---

Published as a conference paper at ICLR 2025
25
Experential:
Usean holiser]
Experential: Publishr?
Usean Rulther?
20
Exponentall: Publishr
Unean: Publiser
Regroe
25
50 75
100
125
150
175
200
Round
Figure 10: Publishers' regret over time in some random game instance using the softmax ranking function with 3 = 10 (solid lines), compared with the regret over time for the same game instance under linear activation (dashed lines). While the concave ranking results in sub-linear regret, the softmax ranking leads linear regret growth, demonstrating that LRL-OFTRL, does not yield regret dynamics in this case.
proportional ranking function with 3 10, compared the regret in the same game with the linear proportional ranking functionn! T6 is worth mentioning that the phenomenon presented in this figure specific this particular instance but was observed across wide range of instances.
C.3 BEYOND UNIFORM ECOSYSTEM DISTRIBUTIONS
In S we illustrated the performance of the different concave ranking functions in a simulative environment, in which instances were sampled uniformly i..d. In this section, provide some preliminary results beyond this case. We experiment with additional instance distributions, violating both the independence assumption and the marginal uniform distribution assumption.
We consider a family of instance distributions where all initial documents and information needs are sampled from multivariate normal distribution, truncated to [0, 1] the embedding space in model. For simplicity, we fix n = = 3. All entries of the initial documents and information needs are independent across coordinates. Within each coordinate, between initial documents and information needs, but introduce some correlation within the set of initial documents, and within the set of information needs. Specifically, the joint distribution of the 3 initial documents (in each coordinate E [k]) is given by the (truncated) multivariate normal distribution with mean and the following covariance matrix:
maintain independence
P1
p P1
Σ o
P1
1
Similarly, the joint distribution the s = 3 information needs (in each coordinate j E [k]) is given by the (truncated) multivariate normal distribution with mean 1 and the following covariance matrix:
1
P2
2
Σg
o3
P2 P2
P2
16ehe game instance is publishers' game with 3 publishers. embedding dimension of 3, demand distribution p Uni (00.55, 0.72, 0.60), (0.54, 0.42, 0.65), (0.44, 0.89, 0.96)). initial documents a1 (0.38, 0.79. 0.59), = (0.57, 0.93, 0.07), = (0.09, 0.02, 0.83), d(z, v) $ l| y/l the semi-metric d, and heterogencous integrity parameters 0.5.
19

---

Published as a conference paper at ICLR 2025
1,50
Jhsar Red
1.00
Jrear
1.000
Veltee
0.995
0.0.55
Aud
Ridd
0.85
0.005
0330
0310
0570
30
51
5.
035
04
2.6
07
08
05 10
50
51
02
0.5
04
5.6 0.7 08
60
61
02
25
24
6.6 0. 08
(a) P1
0.5, P2 0.5
(b) p1
0.5, p2
(c) = -0.5, pz = 0.5
1200
Unnor
1.000
Unaar
1.000
Unoar
PuNlieers Weltere.
0.300
00000
20000
B6465
0.000
0.000
0.77
0.75
0.975
30
21
62
03
04
3.4 07 06
06
50
6.1
02
03
32
35
266
0J
00
6.
61
02
33
34
4.5
6.6
07
3.
(d) P1 0, P2 0.5
(e)
P1
P2
0, P2 0.5
Jheur
Unnar
Unear
Wetre
6.95
thiic
0.595
Ligentheri
loganthen:
0.30
0.300
0.990
0.00
0:300
0.900
0.355
0.75
0
(g) PI 0.5, P2 0.5
P1 0.5, P2 0
P1 0.5, p2 0.5
Figure 11: The effect of the penalty factor À on the publishers' welfare, when initial documents and demand distributions are drawn from a normal distribution with Pl, E {-0.5, 0, 0.5) and
=s=k= k= 3.
where Pl, P2 E 1-1, are correlation parameters, and 01; 22 are scale parameters, used to ensure that the probability of the normal RVs being truncated is not significant. We fix 01 d2 0.2. Lastly, the demand distribution Pa over the s = 3 sampled information needs is still uniform.
To examine the robustness of our empirical findings to the instance distribution, now repeat the analysis of the effect of the penalty factor À on our three evaluation criteria: publishers' welfare, users' welfare, and convergence rate, using the instance distribution described above. To cover multiple possible correlation structures, we experiment with the nine different distributions obtained
by letting P1, P2 { 2. }]- We compare these results, shown in figures 11 12 and 13 to the
results obtained with a uniform i.i.d. instance distribution, presented in Figure I
Most importantly, the trade-off's between the three evaluation criteria and the relation between the three concave ranking functions we experiment with are robust to the change we introduced in the ecosystem distribution. The ranking functions that less uniform (in the sense discussed in $5.1) yield higher users' welfare, at the cost of lower publishers' welfare and slower convergence. This is the same trade-off between ranking functions we observed in $5.1
Regarding the effect of X, we note that some trends are preserved with respect to the uniform i.i.d case, while some new trends also emerge. The publishers' welfare and the users' welfare are preserved: the publishers' welfare still decreases in À until reaching some minimum and then increasing, and the users' welfare still decreases in X. The convergence rate, however, happens to be affected by the ecosystem distribution change. While in the uniform i.i.d case effect of À the convergence rate was observed, in the truncated normal distribution higher À values are generally correlated with slower convergence. We emphasize that while the change in the ecosystem distribution changed the effect of À on the convergence rate, the order relation between the different ranking functions was preserved in terms of the convergence rate (as well as in terms of the other evaluation criteria).
20

---

Published as a conference paper at ICLR 2025
3.61
LESEE Rod.
3.61
2.41-
Liner Foot
3.92
2.92
Voore Warfare
2.90
0.8
2.8
0.34
2.6
6/
01
02
10
02
03
54
03
01 05 04
P1
0.5, P2 -0.5
(b) p1
0.5, P2
(c) p1 0.5, P2 0.5
0.44
3.91
(npuuteerk
Lxputrerk
Lxguttork
Reir
Jiger Vetee
Userd Vetbre
Friet
0.00
2.00
Usere
0.89
3.88
2.89
284
184
60
01
02
033
96
05
06 6.7 1.0
63 011
0Z
0.3
96
05
05
0.7
1.0
91
02
0.3
06
077
0.8 05
(d) (1 0, 0 =-055 -0.5
(c)
P1 0, 0 0
(f)
0,
P2 0.5
0.94
Logerteen
Lagertone:
Unerg Weltrre
3.40
3.9
Uporst Wettrre
2.40
2.00
3.00
8.80
3.06
3.8
3.8
5.11
0. 01
02
0.5
26
05 56 5.7 0.5
1.0
0. 03.
02
0.5
24
05 05 0.r
05 21
02
03
04
05
05
0.7
(g) P1 = 0.5, P2 -0.5
(h) = 0.5, P2
i = 0.5, = 0.5
Figure 12: The effect of the penalty factor À on the users' welfare, when initial documents and demand distributions are drawn from normal distribution with Pt, P2 E (-5.5, 0, 0.5] and n = 3
D EQUILIBRIUM CHARACTERIZATION AND USERS' WELFARE ANALYSIS
Recall that Theorem 2 provides broad family of concave publishers' games; namely, any publishers' game whose ranking function r' is a proportional ranking function with concave activation is concave. The concavity of game facilitates the analysis of the Nash equilibria of the game, this section, we assume publishers' game with proportional ranking function r whose activation function g is concave. We will illustrate the characterization under several simplifying assumptions on the distance function and the demand distribution, but the main principle carries to more complex scenarios. We then use this characterization derive insights the behavior of the users' welfare in the case of symmetric publishers' games, as function of the game parameters.
shall see. In
By definition, profile "7 X is an NE in publishers' game if and only if for any publisher i E N, 2. E argmax,, ex; xI) ). As shown by Madmon et al. (2023). it can be assumed without loss of generality that each publisher chooses document I; contamed in the line segment
connecting x² with zQ. That is, for any player i, and for any profile of the other publishers z-i, we have argmax,,
(x) = argmax 4; (I), where L; = {-p + a, (x -x?) a; E [0, is the line segment connecting the information need x² with player i's initial document 2.. To use this observation,
focus on the case of a one-hot demand distribution Pa, with single information need x². In this case, x00 is NE if and only if:
x = 2 + a. (x" 2!)
s.t. at E argmax (x) - a (2'- 22) x2))
(24)
a.E(0.1)
Define ft (a) ui (a + a; (x* - x??) v-).. Here, x-; is implicitly function of a_ (that is, of {az))æ); it is the profile where each publisher j i plays xy = xg + aj (x" - ==9). Since
21

---

Published as a conference paper at ICLR 2025
1030
1050
Uiwer foot
1320
Uiver host
420-
Fook
Convorgenve sonce Rate
320
320
450-
320
220
250
130
120
120
00
C1
02
06
055
06 0.7
68
1.0
00
01
02
935
94
5.5 06 0.7
04
0.
0.
60
02
0.7 03
54
65
06
(a)
0.5, P2 0.5
(b) P1
0.5, P2 00
(c)
0.5, 0.5
1030-
Linear
1026-
Unwer
1320
Liner
Logutthmm
920-
Logattmii
910
Logarttre
032
foot
010
8:0
700-
710-
720-
620
620
520
535
550
300
420
420
335-
100
(d) P1 = 0, P2
P1
0, P2
(f) P1
0, P2 0.5
1635-
Libea
1026
Libear
1020
Lineer
Root
330
400
300
200
220
200
138
136
130
06 C1
62
03
02
35 06
07 68
10
00 01
02
33
34 45 05 07 01
0.
65
62
33
54
65
06
0. 08
PM 0.5,
P2
-05
(h) P1 0.5, p
( 0.5, pr 0.5
Figure 13: The effect of the penalty factor À on the convergence rate, when initial documents and demand distributions are drawn from normal distribution with Pl, E {-0.5, 0, 0.5) and n =
U; (Zi, x-)) ) is concave in x, for any 2-1, so is fi (a) concave in a for any fixed a-is because a concave function composed with linear transformation remains concave. Let write more explicitly:
(d (1f + (x" x2) .0xx))))))) ΣØ 9 (d (x) + aa (x" - x99) x²))
S1 (a)
Aed (ed + az (x* - -x²) x²?)
(25)
To keep the discussion general in terms of (except for the concavity assumption). let us fix semi-metric d. A natural choice would be the squared Euclidean norm, d (a, b) lle bl? which also the semi-metric used our empirical simulations in $5) Let us denote by C. = d the distance of player i's initial document from the information need. In this
have d (x. + a; (x* x²),,** xxxx) = (1 ax²² C₂ and similarly d (x! + ag (x* x!) x!) = a²C, Substituting this into 25 and differentiating, get:
an) g' ((11 Ci) 2 2(a; 11) ((1 (1-
aʃ: (a) da:
21,a.
(26)
Σラ ( c)))
Notice that for any a-is Bog admits a solution a eq E (0, 1). By the concavity in f. (a) in a,, we get that a is a maximizer in
8f: (1, a.)) <
8f. (0, a.)) and hence the equation 80; (a) 8a;
8f
(24) and hence, as mentioned in (24). the profile defined by x. = x.. + a equilibrium.
eq (x* =x?) is a Nash
22

---

Published as a conference paper at ICLR 2025
To sum up the discussion far, we have characterized the unique NE of the concave publishers' game as the solution of a system with n equation and n scalar variables, in the case where the demand distribution is one-hot and the distance function is the squared Euclidean distance.
The symmetric case To gain some more insight, let us further assume that the ecosystem admits the xy as well as homogeneous integrity parameters À X2 That is, all players have the same initial documents and care to the same extent about their integrity to that document. In this case, the game is symmetric game (meaning all players have the same set of strategies and the same utilities). It is well-known that symmetric games always admit a symmetric 8ff, NE. Therefore, the unique NE given by the solution of the system of equations da, (a) = 0 is symmetric, i.e. 01
symmetry =4 = x2
An-
0 022
eq
o and the system collapses to equation:
(n l) (a1 (1-ai) a1)² 1 - -1) (1- 21 =0 (27)
0f da1
(a) =
ng (1-
which simplifies the following equation:
0 n 19' (11 (1--11) (1-a1)²ci) a1 11011
(28)
n² (11
0n (1- 01)
That is, in the symmetric case, x = xf + ai (x* - 29), where af is a solution in [0, 1] of the scalar equation 28 is the unique NE of the game.
Some insights arise from 28 regarding the effect different game parameters on welfare. First note that in the equilibrium strategy all publishers play the same document and get the same payoff, which simplifies the discussion about the users' and publishers' welfare in the NE. Let us focus on the users' welfare. The users' welfare in equilibrium given by:
n
(xx9)= = Σ dd (z)))) a
(29)
Not surprisingly, the users' welfare increases with af", meaning that the closer the equilibrium strategies x; 24 x + aj (z* are to the information need, the more satisfied the users are. But how ai affected by the different game parameters? To answer this question rigorously, provide the following two Lemmata. The proof of the first is provided at the end of this Appendix and the proof of the second trivial and hence omitted.
Lemma 2. Denote by & (a1) m-1 g' (((1-a))) n (11001)ac.) (1-a1) + ACCia the RHS of 288 Then, W
is strictly increasing in [0, 1].
Lemma 3. Let 1, V2 10 + R be two strictly increasing functions that admit roots a1 a2 respectively. Suppose V 1 < 1/2 pointwise. Then a
02
Notice that increasing À makes L strictly bigger pointwise. Hence, recalling that aj is the root of V, we get by Lemma 3 that increasing À decreases at4, and therefore decreases the users' welfare. Importantly, this gives a formal justification, albeit in special case, to the effect of X observed empirically in Figure T
The exact same reasoning works for since 1-1 is strictly decreasing in n for 2 2 and since x² g' < O, which means that just like '₁ making n larger strictly increases pointwise. Hence, the users' welfare is decreasing in as seen empirically in Figure 2 Regarding k. the dimension of the embedding space, it can be seen that in this special case it provably does not affect the users' welfare, admit that the theoretical approach
which is in line with the flat line seen in Figure 4 Lastly, taken in this Appendix fails to determine the effect of s, as it assumes a one- hot demand distribution with single information need, i.e. s = 1.
23

---

Published as a conference paper at ICLR 2025
Perhaps more importantly, the approach described above help system designer understand how her choice the activation function 9 affects the ecosystem. To see how, take, for example, the family of root proportional ranking functions groot (t) (1 t)", where 0 < is the power hyperparameter. This is one of the three ranking function families studied empirically in $5 A simple calculation shows that
Froot
a
(30)
groot (t) t
It can be seen that when increasing the function Eoma(() (t) decreases pointwise in the range of interest
(roat!))
t (0, 1). Hence, increasing strictly decreases (ai) pointwise in the range dn E (0, 1). Hence by Lemma 3 increasing a increases mn and hence improves the users' welfare. This is in line with the empirical results of F
Going through the exact same arguments with (tog(t) = In(c t), where e > is the shift hyperparameter, and with giin (t) b b-tt, where b b> 1 the intercept hyperparameter, we get that the trends observed in and in 6 respectively, are theoretically justified. That is, decreasing the shift hyperparameter in Glog provably increases the users' welfare in the special case we study this Appendix, and so does decreasing the intercept hyperparameter of gisn
Notice that the above analysis of the effect of the activation function g on the users' welfare suggests that the property of g that matters is how pointwise large the function (Ing)' a' is. Our intuition for this mathematically interesting phenomenon is that L is a natural way to construct function y which is invariant under multiplication of the activation function by a constant, which is necessary 9( ((((x),,=)))
due to the structure of proportional ranking functions ri(o; Σj=1 9 (d(ay..*))
To conclude this Appendix, we mention that while a publishers' welfare analysis can be carried out along the exact same lines the users' welfare analysis provided above, this equilibrium-centric approach probably cannot yield insights regarding the convergence rate, and theoretical analysis of the latter evaluation criteria remains for future work.
Proof for Lemma
2
Notice that by the chain rule:
g' - a1) (1 a1) = 20, dai
d In (1
(31)
(11 (11-a)) (11-a1)20)
Now, recalling that is concave and decreasing and noticing that (1 - )² Ci is convex in 0n, we have that (1 - 2 Ci is concave in a1. Then, since In (+) is concave and increasing, we have that In (g) (1- a1)² C₁ is concave and hence its derivative is decreasing. Hence the first term in the definition of v is increasing. Striet increase is obtained by the second term
24


Reviews:
[{"review_id": "L6UteI6gOg", "reviewer": "Reviewer_WgNQ", "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.", "questions": "Please address my comments and concerns raised in the weakness.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 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.", "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. \n\n2. 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.\n\n3. Insufficient related work. This paper tries to study no-regret dynamics running on a proposed SEO game which is socially concave: \n- 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. \n- 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). \n- In addition, no-regret dynamics and their convergence in similar content publisher games are studied in [6]. \n\nOverall, 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. \n\n[1] The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization, Neurips 2018\n[2] Bandit learning in concave N-person games, Neurips 2018\n[3] On existence and uniqueness of equilibrium points for concave N-person games, Econometrica 48(1) 251.\n[4] Human vs. Generative AI in Content Creation Competition: Symbiosis or Conflict?, ICML 2024\n[5] User Welfare Optimization in Recommender Systems with Competing Content Creators, KDD 2024\n[6] How Bad is Top-K Recommendation under Competing Content Creators?, ICML 2023\n[7] Doubly optimal no-regret learning in monotone games, ICML 2023", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5ap8nyeEHU", "reviewer": "Reviewer_8mkE", "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. \nThe 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.", "questions": "**Questions:**\n\n(Q1) See (W1).\n\n(Q2) See (W2).\n\n(Q3) How do you choose publishers' initial document $x_0^i$ in simulations? \n\n(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. \n\n\n\n**Suggestions:**\n\n- Equation (4): is $d_i^0(x_i)$ equal to $d(x_i, x^i_0)$? \n\n- 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].\n\n[1] Dean & Morgenstern. Preference Dynamics under Personalized Recommendations. EC 2022.\n\n[2] Lin et al. User-Creator Feature Polarization in Recommender Systems with Dual Influence. 2024.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 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. \n\n(S2) The theoretical results are solid and not very straightforward. \n\n(S3) Writing is very clear.", "weaknesses": "However, I think there are some theoretical and experimental limitations in this work. \n\nTheoretical:\n\n(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? \n\n\nExperimental: \n\n(W2) Some parts of the simulation setup feel unnatural: \n\n(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$? \n\n(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).\n\nIt would be nice to include some experiments with continuous distributions and a larger number of publishers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VHsOoeyY2W", "reviewer": "Reviewer_YFmi", "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). \n\nIn 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. \n\nThe 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.", "questions": "None", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "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.", "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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)