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

Thank you for the encouraging response, we are glad that you found our paper to be interesting and of practical value. As standard in the economic literature, our assumption that the publishers’ utilities are linear in the exposure reflect their risk neutrality [1,2], which is a plausible assumption that was also largely adopted within the recent literature on strategic content providers. We agree that studying other structures, such as convex/concave functions of the exposure (reflecting risk seek/aversion, resp.) is indeed an interesting future direction. A potential technical challenge would then be the fact that the concavity of the publishers' utility may no longer depend solely on the ranking function, but also on some external factors, which the system cannot control.

[1] Ozga, S. A., & Arrow, K. J. (1966). Aspects of the Theory of Risk-Bearing. Economica, 33(130), 251.

‏ [2] Hillson, D., & Murray-Webster, R. (2017). Understanding and managing risk attitude. Routledge.‏

Thanks for your response. I have gone through the other reviewers comments and the author responses to them. I share reviewer WgNQ's concern regarding convergence in average vs last iterate convergence, which is indeed a weakness. Despite this, I still strongly believe this is a good submission and I maintain my initial position.

Publishers' initial documents in the simulations (Q3)

In the simulations that appear in the main paper and appendices B1-B2 the initial documents are sampled uniformly i.d.d. In appendix B3 we provide additional simulations in which the uniformity and independence assumptions are relaxed, and we use a multivariate normal distribution to sample the initial documents and the information need, with possible correlations (see more details at the beginning of this appendix).

Equilibrium learning strategy and last-iterate convergence (Q4)

The goal of the paragraph on equilibrium learning strategy (and Proposition 1) is not to prove last-iterate convergence, but instead to motivate our result on average convergence. Here the story is as follows. Publisher $i$ hires an SEO agent that can engage for her in a no-regret algorithm for the first $T_i$ rounds (think of $T_i$ as determined e.g. by budget constraints). Proposition 1 shows that, given that those stopping times are not too far from each other and sufficiently large, each agent can simply play deterministically her average (i.e., the strategy her SEO agent learned for her) and this process results in an approximate NE. We find the interpretation of this story as particularly relevant, as indeed web pages owners might prefer not to engage with frequent content modifications themselves, and let an external expert do the hard work for them, under the guarantee that when the SEO agent concludes, the publisher’s cannot do much better then simply following the learned strategy for all future periods.

While it would indeed be ideal to also have some result on last-iterate convergence, we do not think your suggestion is sufficient to prove such a result. Even if the NE is unique, the resulting dynamics can be cyclic (i.e., the profile “jumps around” the equilibrium point), which means that the average convergence, but the last-iterate diverges. We also have an example for a particular game simulation in which this happens, but we also highlight that from a practical perspective, our simulations indicate that this is very rare as the vast majority of the simulations do converge in the last iteration. So, from a practical perspective, concave activation may induce even more robust ecosystems than guaranteed theoretically. We view both the theory and practice as fundamental in the study of stable recommendation systems design.

Suggestions:

• Thanks for noticing, this is a typo which is now resolved.
• We appreciate your suggestion for this very interesting future direction.

Thank you for your detailed response and helpful comments. We hope that our response below helps in addressing your questions and comments.

Welfare measures in equilibrium under concave activation (Q1)

We agree that a theoretical welfare characterization is an important and technically interesting question. A necessary step in order to answer this question, as we are interested in welfare in equilibrium, is characterization of the equilibrium points. We find this characterization of independent interest. The equilibrium characterization is rather simple as it follows naturally from the concavity of the game. In a new appendix that appears in the new version of the paper we uploaded, we derive the explicit form of the equation system defining the equilibrium, and also further simplify it for the symmetric publishers’ game case. As expected, the solution of these equations heavily depends on the specific activation function $g$, and understanding the effect of $g$ (as well as the other game parameters) on the welfare measures turns out to be non-trivial. We consider this a particularly relevant theoretical future direction.

Experimental setup (Q2)

We will add experimental results with a higher number of publishers and will add these to the camera ready version (and will do our best to attach them during the discussion period). As for the comment on the demand distribution support, it is worth noting that in many real-world applications, the user population is clustered and is usually represented by a finite number of cluster centroids. In the context of recommendation systems, user clustering is useful in efficiently storing user data, or improving model performance by reducing the complexity of demand representation (for instance, [1]). In information retrieval, the assumption on discrete information needs can be seen as subtopic retrieval (for instance, [2]).

Having said that, we will examine the option to perform some no-regret dynamics simulations with continuous distributions in order to incorporate additional results into the camera-ready version. Moreover, an interesting future direction could involve distinguishing between a continuous actual population distribution and a discrete centroid distribution observed by the platform and the publishers.

[1] Zarzour, H., Al-Sharif, Z., Al-Ayyoub, M., & Jararweh, Y. (2018, April). A new collaborative filtering recommendation algorithm based on dimensionality reduction and clustering techniques. In 2018 9th international conference on information and communication systems (ICICS) (pp. 102-106). IEEE. ‏

[2] Zhai, C., Cohen, W. W., & Lafferty, J. (2015, June). Beyond independent relevance: methods and evaluation metrics for subtopic retrieval. In Acm sigir forum (Vol. 49, No. 1, pp. 2-9). New York, NY, USA: ACM.‏

We would like to thank you again for the your thoughtful and constructive comments. We would like to add upon our previous reponse.

Welfare

Following our previous response concerning equilibrium characterization, we have realized that indeed this characterization provides some valuable insights on users’ welfare in equilibrium. The entire analysis can be found in Appendix C in the version we have now uploaded and for completeness we summarize the main insights here.

For simplicity, our analysis restricts to the case of a single information need, but the main principle carries to more complex scenarios.

In the general case we characterize the equilibrium as the solution of an explicit system of equations (Eq 26). In a symmetric publishers’ game, we then establish that the symmetric equilibrium is a weighted average of the (homogeneous) initial document and the information need, where the weight of the information need is given by the solution of the following equation (Eq 28):

By noticing that as $\alpha_1^{eq}$ increases the users’ welfare increases, our main insights are:

• As $\lambda_1$ increases, the users’ welfare in equilibrium decreases.
• As $n$ increases, the users’ welfare in equilibrium decreases.
• As $\frac{g’}{g}$ increases (pointwise), the users’ welfare decreases.

While this analysis is made under some restrictive assumptions, it is worth mentioning that the above conclusions align with the trends displayed in our experimental setting, which is a more general setting.

Experiments with a larger number of publishers $n$

Following your suggestion, we have conducted experiments with $n = 25$ and $n = 50$, under the same experimental conditions as in Figure 2, and find that users’ welfare keeps decreasing with $n$. This strengthens (yet does not prove) our conclusion regarding the effect of $n$.

EDIT: in the revised paper we uploaded, Figure 2 (the effect of $n$) now contains experiments with large values of $n=25$, $n=50$, and $n=100$.

Related work

Thank you for the relevant references, which we view as relevant and complementary to our work. We discuss the similarities and differences between our and theirs below, and will be happy to incorporate this discussion into the camera-ready version if the paper is accepted.

[4] studies a novel model of content creation competition with GenAI, but does not allow for flexibility in the recommendation/ranking function, which plays a crucial role in our work. While they focus on particular incentive structures (exclusive/inclusive) and study the existence and characterization of NE (using the notion of monotone games), our model allows for a higher degree of flexibility in the ranking function selection, and the main result provides a characterization of those ranking function that induces a (socially-)concave game.

[5] also utilizes monotone games to establish the existence of NE (under some mild conditions) in a model in which the utility of the publisher is similar to the case of $g(t) = exp(\beta t)$ in our notations. Thereafter, they studied equilibrium welfare optimization using novel intervention mechanisms that induce structural publisher utilities different from those resulting from our PRFs. However, their model differs from ours in the way the incentives of the publishers can be controlled by the platform.

Perhaps closest to us, [6] indeed study no-regret dynamics, but then again they focus on a particular structure of the exposure/rewarding mechanism of the platform, which stands in contrast to the flexibility enabled by our general definition of PRFs. Moreover, [6] do not study the existence of or convergence to NE, but rather study average welfare over time.

We view our work as complementary, as unlike those discussed, it provides a model in which the recommendation/ranking mechanism is general, in the sense that the platform can choose any activation $g$. We thereafter provide a closed and intuitive characterization of those activation functions for which the induced game is (socially-)concave. Indeed, monotonicity is stronger than social-concavity, and last-iterate convergence is better than average convergence. But to obtain these (important) results, [4,5,6] studied models that are less general, as they often fix certain components of the publishers’ utility (such as the random-utility model, the softmax function, stronger assumptions on the distance function $d$, etc). In our view, this reflects a tradeoff between model generality and the strength of the results, both of which are crucial considerations. That being said, as we highlight in the previous point, we do believe that average convergence is a significant contribution with practical implications.

I really appreciate the author for the detailed clarification. I think your explanation about the soundness of Lemma 1 makes sense to me.

In fact, after a closer look at the proof of Lemma 2.2 in [8], I realize that I indeed missed a key point, that is, in any socially-concave game, condition A1 and A2 already imply the fact that each player's utility is concave in her own action (which is exactly what Lemma 2.2 in [8] was trying to prove). That said, I should thank the reviewer again for resolving a latent misunderstanding about the property of socially-concave games.

For the authors' justification about the significance of stability guarantee, it makes a reasonable sense to me. My criticism is mainly from a theoretical perspective, as convergence in average is a weak concept. However, in this specific application context, I agree it is meaningful. However, I'm still curious about whether under certain conditions the publisher game under no-regret dynamics could end up in cycling (i.e., the joint strategy will neither converge nor diverge, but cycles around a NE). It would be very interesting if the author could come up with an example showing that such a pattern can indeed happen. If such example is hard to construct, adding a short discussion to acknowledge the gap between a relatively weaker theoretical guarantee and a strong empirical observation would also strengthen the paper.

Overall I think the author response is satisfactory and refreshes my understanding about the value of this work. I decide to increase my scores (Contribution: 1: poor -> 3: good, and Rating: 3 -> 6 ) and lean towards acceptance.

Thank you for your detailed response and helpful comments. We hope that our response below helps in addressing your questions and comments.

Correctness of our theoretical results

We believe that our theoretical result is indeed valid. First, notice that:

(a) [8] proved that any socially-concave game is concave; and -

(b) In our publisher games, the first condition of social-concavity (A1 in definition 1) is always satisfied (proved in the proof of Lemma 1), as we assume that $d$ is bi-convex. This means that, in our publisher games, satisfying the second condition of social-concavity (A2 in Definition 1) implies that the game is concave.

This aligns with the fact that for concave and monotonically decreasing $g$, the function $r_i(x_i,x_{-i})$ is indeed concave in $x_i$ for any fixed $x_{-i}$ (the monotonicity assumption of the activation function $g$ is stated in the definition of a PRF, L. 230, and its purpose is to ensure documents that are closer to the information need $x^*$ are exposed with higher probability). To see why, fix $C=\sum_{j \neq i} d(x_j,x^*)$, and denote:

$d(x_i) = d(x_i,x^*)$

$f(x_i) = g(d(x_i))$

$h(t) = \frac{t}{t+C}$

Then, we want to show that the following function is concave:

$r_i(x_i,x_{-i}) = h(f(x_i))$

Now we use the fact $h$ is non-decreasing and our assumption that $g$ is decreasing (this assumption is stated in the paper and its purpose is to ensure documents that are closer to the information need get a better ranking):

(a) $g$ is concave and non-increasing, and $d$ is convex, implying that $f$ is concave.

(b) $h$ is concave and non-decreasing (in $R_+$, which contains the image of $f$), and $f$ is concave, implying that $r_i$ is concave.

Significance of our stability guarantee

While we acknoledge that last-iterate convergence is of strong interest, we would like to suggest that the average convergence guarantee also holds significant value in real-worl applications. Such a practical implication is discussed (and perhaps should be clarified) in the paragraph on equilibrium learning strategy.

Here the story is as follows. Publisher $i$ hires an SEO agent that can engage for her in a no-regret algorithm for the first $T_i$ rounds (think of $T_i$ as determined e.g. by budget constraints). As we highlighted in the introduction, no-regret serves as a suitable framework to describe the strategic behavior employed in SEO.

Proposition 1 shows that, given that those stopping times are not too far from each other and sufficiently large, each agent can simply play deterministically her average (i.e., the strategy her SEO agent learned for her) and this process results in an approximate NE.

We find the interpretation of this story as particularly relevant, as indeed web pages owners might prefer not to engage with frequent content modifications themselves, and let an external expert do the hard work for them, under the guarantee that when the SEO agent concludes, the publisher’s cannot do much better then simply following the learned strategy for all future periods. This holds, of course, under the assumption that all publishers use these SEO services, which we find plausible.

From a practical perspective, we highlight that in all of the simulations we run to establish the empirical results of the paper, the dynamics also converged in the last-iteratation sense. Only when we significantly increase $\lambda$ we are able to find instances in which dynamics converge in the average sense but diverge in the last-iterate sense. Importantly, these anecdotal and rare examples are highly non representative. So, from a practical perspective, concave activations may induce even more robust ecosystems than guaranteed theoretically. We view both the theory and practice as fundamental in the study of stable recommendation systems design.

[8] Even-Dar, E., Mansour, Y., & Nadav, U. (2009, May). On the convergence of regret minimization dynamics in concave games. In Proceedings of the forty-first annual ACM symposium on Theory of computing (pp. 523-532).‏