# Conditional Generation from Unconditional Diffusion Models using Denoiser
Representations

Alexandros Graikos Srikar Yellapragada Dimitris Samaras
{agraikos, myellapragad<EMAIL_ADDRESS>
Stony Brook University
NY, USA

###### Abstract

Denoising diffusion models have gained popularity as a generative modeling
technique for producing high-quality and diverse images. Applying these models
to downstream tasks requires conditioning, which can take the form of text,
class labels, or other forms of guidance. However, providing conditioning
information to these models can be challenging, particularly when annotations
are scarce or imprecise. In this paper, we propose adapting pre-trained
unconditional diffusion models to new conditions using the learned internal
representations of the denoiser network. We demonstrate the effectiveness of
our approach on various conditional generation tasks, including attribute-
conditioned generation and mask-conditioned generation. Additionally, we show
that augmenting the Tiny ImageNet training set with synthetic images generated
by our approach improves the classification accuracy of ResNet baselines by up
to 8%. Our approach provides a powerful and flexible way to adapt diffusion
models to new conditions and generate high-quality augmented data for various
conditional generation tasks.

##  1 Introduction

Denoising diffusion models have recently gained significant attention in the
generative modeling literature due to their impressive results on various
synthesis tasks, including image, audio, and molecule synthesis [26, 7, 4, 20,
14, 11]. Providing conditioning information can improve the sample quality of
diffusion models, effectively guiding the model towards generating more
diverse and representative samples [8, 19, 3].

While text-based conditioning has been widely used in image generation tasks,
due to the wide availability of image-caption pairs, it is not always the best
approach, as the scale at which the sampling guidance is applied can vary
between tasks. For instance, sampling images with a dense per-pixel condition,
such as a semantic mask, cannot be adequately substituted with a text
condition, no matter how detailed. Additionally, it is often infeasible to
provide finer annotations on the image or pixel level due to the large scale
of the data used to train diffusion models. Thus, adapting pre-trained
diffusion models to new conditions using the learned intermediate
representations of the denoiser network is an attractive alternative.

In this paper, we propose a method to adapt pre-trained unconditional
diffusion models to new conditions using the internal representations of the
denoiser network. We show that the learned representations are inherently
robust to noisy inputs, allowing us to provide guidance during sampling while
utilizing a noisy estimate of the final image $\mathbf{x}_{0}$. Whereas
previous methods relied on training large-scale guidance classifiers on the
intermediate noisy steps, our method can efficiently learn from a small set of
examples by exploiting the existing parameters of the denoiser network. We
demonstrate the effectiveness of our approach on various conditional
generation tasks, including attribute-conditioned generation and mask-
conditioned generation.

When we are presented with more data but not enough to train a conditional
diffusion model from scratch, we demonstrate that we can combine the learned
unconditional model representations with the fine-tuning of the model. In
particular, we focus on synthetic data augmentation, where we generate
augmented data using a conditional diffusion model fine-tuned on Tiny ImageNet
[15]. We use the internal representations of the unconditional U-Net [24]
denoiser network to train a rejection classifier. This classifier is used to
reject low-quality samples generated by the fine-tuned conditional diffusion
model, which helps to improve the overall quality of the generated images. We
then use the augmented data to train a classification model and evaluate its
performance on the Tiny ImageNet dataset. Our contributions are as follows:

  * •

We demonstrate how the internal representations of an unconditional diffusion
denoiser network can be used to adapt to new conditions with limited examples.

  * •

We verify the effectiveness of our approach on various conditional generation
tasks such as attribute-conditioned generation and mask-conditioned
generation.

  * •

We show how augmenting the Tiny ImageNet training set with synthetic images
generated by our approach significantly improves the classification accuracy
over ResNet [6] baselines.

##  2 Related Work

###  2.1 Conditional diffusion models

Similar to other generative models, conditional diffusion models perform
better than their unconditional counterparts, showing impressive results in
text-conditioned generation [20, 23]. Apart from text-to-image models, in [4],
the authors demonstrate how exploiting the denoiser network as a learned score
function can be used with an auxiliary classifier trained on noisy samples to
guide inference with class labels. In [5], the authors show that diffusion
models can perform conditional generation by minimizing an energy function
defined using the learned denoiser and any auxiliary constraint on the
inferred sample.

###  2.2 Conditioning of unconditional diffusion models

Few-shot conditioning settings have utilized latent diffusion models in the
past. In [25, 21], the authors propose learning an expressive latent
representation that can be utilized to condition diffusion models on a small
set of labeled examples. The idea behind their approach is that the compressed
latent representation can be efficiently used to adapt to new conditions. More
recently, [18, 36] showcase faster and more efficient adaptation of diffusion
models to new conditions, but both require a large number of data to train
with.

###  2.3 Diffusion as a pre-training task

In [1], the authors introduced the idea of utilizing the learned
representations of a denoiser network for downstream tasks by training a
segmentation network on top of the denoiser features with as few as 20 labels.
Similarly, in [2] and [30], the denoising task is exploited as a pre-training
task for learning semantically meaningful features that can be easily adapted
for performing downstream dense prediction tasks.

##  3 Background

A Gaussian diffusion process [26, 7] can be viewed as a latent variable model
of the form

$p_{\theta}(\mathbf{x}_{0})=\int
p(\mathbf{x}_{T})\prod_{t=1}^{T}p_{\theta}^{(t)}(\mathbf{x}_{t-1}\mid\mathbf{x}_{t})d\mathbf{x}_{1}d\mathbf{x}_{2}\dots
d\mathbf{x}_{T}$ (1)

where $\mathbf{x}_{0}$ is the data, $\mathbf{x}_{1},\dots,\mathbf{x}_{T-1}$
are intermediate latent variables that represent noisy versions of
$\mathbf{x}_{0}$, and $\mathbf{x}_{T}$ is the terminal state with
$\mathbf{x}_{T}\sim\mathcal{N}(\mathbf{0},\mathbf{I})$. The forward process
gradually adds Gaussian noise to the data and is defined by a noise schedule
$\alpha_{t}$

$q(\mathbf{x}_{t}\mid\mathbf{x}_{t-1}):=N(\mathbf{x}_{t};\sqrt{a_{t}}\mathbf{x}_{t-1},(1-a_{t})\mathbf{I}).$
(2)

The reverse process is defined by learned Gaussian transitions and gradually
denoises the data, starting from
$\mathbf{x}_{T}:=\mathcal{N}(\mathbf{x}_{T};\mathbf{0},\mathbf{I})$

$p_{\theta}(\mathbf{x}_{t-1}\mid\mathbf{x}_{t}):=N(\mathbf{x}_{t-1};\boldsymbol{\mu}_{\theta}(\mathbf{x}_{t},t),\boldsymbol{\Sigma}_{\theta}(\mathbf{x}_{t},t)).$
(3)

A property of the forward process is that it allows sampling of any
intermediate $\mathbf{x}_{t}$ given $\mathbf{x}_{0}$, as

$q(\mathbf{x}_{t}\mid\mathbf{x}_{0})=N(\mathbf{x}_{t};\sqrt{\bar{a}_{t}}\mathbf{x}_{0},(1-\bar{a}_{t})\mathbf{I})$
(4)

or equivalently

$\mathbf{x}_{t}=\sqrt{\bar{a}_{t}}\mathbf{x}_{0}+\sqrt{1-\bar{a}_{t}}\boldsymbol{\epsilon},\
\text{where}\ \boldsymbol{\epsilon}\sim N(\mathbf{0},\mathbf{I}).$ (5)

with $\bar{a}_{t}=\prod_{i=1}^{t}a_{i}$. To approximate the reverse process,
it is common to fix the variance
$\boldsymbol{\Sigma}_{\theta}=\sigma_{t}\mathbf{I}$ and learn a function that
predicts the noise added at each intermediate $\mathbf{x}_{t}$ by minimizing

$\mathbb{E}_{\mathbf{x}_{0},t}\left[w(t)\lVert\epsilon-\epsilon_{\theta}(\sqrt{\bar{a}_{t}}\mathbf{x}_{0}+\sqrt{1-\bar{a}_{t}}\boldsymbol{\epsilon},t)\rVert^{2}\right].$
(6)

The original DDPM [7] formulation introduced sampling from a Gaussian
diffusion model by sequentially applying the predicted noise

$\displaystyle\mathbf{x}_{t-1}=\frac{1}{\sqrt{a_{t}}}\left(\mathbf{x}_{t}-\frac{1-\alpha_{t}}{\sqrt{1-\bar{\alpha}_{t}}}\boldsymbol{\epsilon}_{\theta}(\mathbf{x}_{t},t)\right)+\sigma_{t}\mathbf{z},\
\mathbf{z}\sim\mathcal{N}(\mathbf{0},\mathbf{I})$ (7)

starting from a random $\mathbf{x}_{T}\sim N(\mathbf{0},\mathbf{I})$.
Alternatively, in DDIM [27], the authors proposed utilizing Eq. 5 to sample
$\mathbf{x}_{t-1}$ from $\mathbf{x}_{t}$ by first estimating $\mathbf{x}_{0}$
and then using the known forward process to ’point-back’ towards
$\mathbf{x}_{t}$, as

$\displaystyle\mathbf{x}_{t-1}=$
$\displaystyle\sqrt{\bar{\alpha}_{t-1}}\underbrace{\left(\frac{\mathbf{x}_{t}-\sqrt{1-\bar{\alpha}_{t}}\boldsymbol{\epsilon}_{\theta}(\mathbf{x}_{t},t)}{\sqrt{\bar{\alpha}_{t}}}\right)}_{\text{estimated
}x_{0}}+\underbrace{\sqrt{1-\bar{\alpha}_{t-1}-\sigma_{t}^{2}}\boldsymbol{\epsilon}_{\theta}(\mathbf{x}_{t},t)}_{\text{direction
pointing to }\mathbf{x}_{t}}+\underbrace{\sigma_{t}\mathbf{z}}_{\text{random
noise}}.$

A denoiser $\boldsymbol{\epsilon}_{\theta}(\mathbf{x}_{t},t)$ can be
interpreted as a learned score function of the noise-perturbed
$\mathbf{x}_{t}$ [4, 28]

$\nabla_{\mathbf{x}_{t}}\log
p_{\theta}(\mathbf{x}_{t})=-\frac{1}{\sqrt{1-\bar{\alpha}_{t}}}\boldsymbol{\epsilon}_{\theta}(\mathbf{x}_{t},t).$
(8)

For a conditioning variable $\mathbf{y}$, the score of the posterior
$p(\mathbf{x}_{t}\mid\mathbf{y})\propto
p(\mathbf{x}_{t})p(\mathbf{y}\mid\mathbf{x}_{t})$ can be expressed as

$\displaystyle\nabla_{\mathbf{x}_{t}}\log p(\mathbf{x}_{t}\mid\mathbf{y})$
$\displaystyle=\nabla_{\mathbf{x}_{t}}\log
p(\mathbf{x}_{t})+\nabla_{\mathbf{x}_{t}}\log p(\mathbf{y}\mid\mathbf{x}_{t})$
$\displaystyle=-\frac{1}{\sqrt{1-\bar{\alpha}_{t}}}\boldsymbol{\epsilon}_{\theta}(\mathbf{x}_{t},t)+\nabla_{\mathbf{x}_{t}}\log
p(\mathbf{y}\mid\mathbf{x}_{t}).$ (9)

Thus by modifying the predicted noise $\boldsymbol{\epsilon}_{\theta}$ at
every step using the gradient of the log-likelihood w.r.t. $\mathbf{x}_{t}$ we
can draw samples from the posterior distribution
$p(\mathbf{x}_{0}\mid\mathbf{y})$

$\hat{\boldsymbol{\epsilon}}_{\theta}(\mathbf{x}_{t},t)=\boldsymbol{\epsilon}_{\theta}(\mathbf{x}_{t},t)-\lambda\sqrt{1-\bar{\alpha}_{t}}\nabla_{\mathbf{x}_{t}}\log
p(\mathbf{y}\mid\mathbf{x}_{t})$ (10)

where $\lambda$ is a tunable hyperparameter.

##  4 Methodology

In this section, we describe how we can utilize the learned intermediate
representations of the denoiser network to conditionally generate and improve
results from an unconditional diffusion model.

###  4.1 Learning the guidance signal using denoiser representations

To provide conditional guidance during inference, we can compute the gradient
of the log-likelihood of a condition $\mathbf{y}$ w.r.t. $\mathbf{x}_{t}$.
Recent works employed a separate classifier $p(\mathbf{y}\mid\mathbf{x}_{t})$
trained on noisy samples $\mathbf{x}_{t}$ to provide semantic guidance, in the
form of class labels. This work argues that retraining the guidance network
from scratch is unnecessary. Instead, we propose using the intermediate
denoiser representations, with the estimate of $\mathbf{x}_{0}$ at every step,
to guide sampling.

Recall that from Eq. 5 we can compute an estimate of the final sample
$\mathbf{x}_{0}$ from

$\hat{\mathbf{x}}_{0}=\frac{\mathbf{x}_{t}-\sqrt{1-\bar{\alpha}_{t}}\boldsymbol{\epsilon}_{\theta}(\mathbf{x}_{t},t)}{\sqrt{\bar{\alpha}_{t}}}.$
(11)

Using this point estimate
$p(\mathbf{x}_{0}\mid\mathbf{x}_{t})=\delta(\mathbf{x}_{0}-\hat{\mathbf{x}}_{0})$
we can rewrite the likelihood as

$\displaystyle p(\mathbf{y}\mid\mathbf{x}_{t})$
$\displaystyle=\sum_{\mathbf{x_{0}}}p(\mathbf{y}\mid\mathbf{x}_{t},\mathbf{x}_{0})p(\mathbf{x}_{0}\mid\mathbf{x}_{t})$
(12)
$\displaystyle=\sum_{\mathbf{x_{0}}}p(\mathbf{y}\mid\mathbf{x}_{0})p(\mathbf{x}_{0}\mid\mathbf{x}_{t})$
(cond. ind.) $\displaystyle=p(\mathbf{y}\mid\hat{\mathbf{x}}_{0})$ (point
estimate)

and plug-in Eq. 10 to get

$\hat{\boldsymbol{\epsilon}}_{\theta}(\mathbf{x}_{t},t)=\boldsymbol{\epsilon}_{\theta}(\mathbf{x}_{t},t)-\sqrt{1-\bar{\alpha}_{t}}\nabla_{\mathbf{x}_{t}}\log
p(\mathbf{y}\mid\mathbf{x}_{0}(\mathbf{x}_{t})).$ (13)

By expressing the likelihood in terms of an estimate of $\mathbf{x}_{0}$, we
allow our guidance network to be trained only on ’clean’ samples, thus
reducing the overall complexity of the post-hoc adaptation process. However,
this assumes that the estimates $\hat{\mathbf{x}}_{0}$ perfectly follow the
marginal distribution $p_{\theta}(\mathbf{x}_{0})$, which is not true, notably
for the first few estimates in the denoising process. In practice, the
guidance network $p(\mathbf{y}\mid\hat{\mathbf{x}}_{0})$ will initially steer
the sample $\mathbf{x}_{t}$ towards the wrong directions, which in most cases
cannot be mitigated by the following denoising updates.

By using the unconditional denoiser network as a feature extractor, we can
both provide guidance that is robust to the initial inaccurate estimates of
$\mathbf{x}_{0}$ and quickly learn the guidance directions from a small set of
labeled samples. The denoiser network is trained with varying noise levels in
its inputs and has learned to extract features of different scales at
different timesteps. Additionally, the intermediate features of the denoiser
U-Net are shown to contain important information for downstream tasks [1].
Therefore, we argue that apart from robustness, using the denoiser features
enables us to learn the conditioning models with a small set of examples.

Figure 1: Synthetic images from the fine-tuned class conditional sampling
(first row) vs Classifier-free guided sampling (second row) vs. our model with
rejection (third row). Samples are from class 9: Golden Retriever on the Tiny-
Imagenet. Our method generated more realistic and diverse images compared to
others.

###  4.2 Combining adaptation with denoiser representations

When presented with more data, we can combine model adaptation methods with
the unconditional denoiser features to generate higher-quality and diverse
images. We begin by fine-tuning the unconditional diffusion model on the
labeled examples we are given by naively adding the conditioning connections
to the pre-trained model. It is important to note that here we assume that the
image-label pairs that are provided do not cover the entirety of the dataset,
which would make the task trivial.

Even with more image-condition pairs, the conditional model fails to generate
realistic images, as demonstrated in Fig. 1. We use the unconditional denoiser
representations to train a classifier of the labels of the given samples and
improve the results by applying rejection sampling. The classifier model
decides whether to accept a generated sample using the predicted probability
value.

We find this method preferable to just providing guidance during sampling
since tuning the weight of the guidance becomes increasingly difficult, with
an inherent trade-off between quality and diversity that becomes infeasible to
hand-tune. We leave the problem of controlling the guidance during sampling to
future work.

##  5 Experiments

###  5.1 Few-shot guidance for face attributes

We first demonstrate how we can generate conditional samples with a limited
number of image-attribute pairs. We utilize an unconditional diffusion model
trained on the CelebA-64 [17] dataset. Similarly to [25], we train an
attribute classifier by giving 50 positive and 50 negative examples of a
single attribute, such as blonde or male.

To train the classifier, we extract the bottleneck and second upsampling block
features from the denoiser U-Net at $T=700$. The classifier network is a
simple 3-layer convolutional network trained for 100 steps. During sampling,
we apply classifier guidance with a weight of $\lambda=1$. The results for the
conditional generation of images with the attributes male, female, blond, and
non-blond are shown in Table 1.

In order to compare with D2C [25] and DiffAE [21], we train a classifier using
the latent representation of each and generate samples by unconditionally
sampling from the model and applying rejection sampling. When comparing with
DiffAE and D2C, we show that we can provide meaningful guidance and achieve
comparable FID scores without requiring to compress the entire image into a
latent representation and without rejection, which significantly increases the
computation needed. For DDIM-I, we use our approach for providing guidance
with an estimate of $\hat{\mathbf{x}}_{0}$, but now using a separately trained
classifier network trained only on “clean” images. The subpar performance
validates the assumption that the intermediate denoiser representations are
more robust to the initial inaccurate estimates of the final image. All FID
scores are computed using the images of the CelebA-64 test set with the target
attribute.

Class | Ours | DiffAE [21] | D2C [25] | DDIM-I | NVAE [31]
---|---|---|---|---|---
Male | 15.34 | 11.52 | 13.44 | 29.03 | 41.07
Female | 9.94 | 7.29 | 9.51 | 15.17 | 16.57
Blond | 13.07 | 16.10 | 17.61 | 29.09 | 31.24
Non-Blond | 10.97 | 8.48 | 8.94 | 19.76 | 16.73
Table 1: FID scores for attribute-conditioned generation on the CelebA-64
dataset.

###  5.2 Few-shot guidance for semantic segmentations

We also demonstrate how we can generate conditional samples with a small set
of paired images and segmentation masks. We utilize the dataset of [1] and an
unconditional diffusion model trained on FFHQ-256 [12]. In this setting, we
train on 20 images and their corresponding segmentation masks to generate
realistic-looking, semantically accurate images.

We again train a per-pixel classifier network using intermediate U-Net
representations extracted at $T=500$ from decoder upsampling blocks. The
classifier is a simple per-pixel multi-layer perceptron trained for 50 steps.
During sampling, we apply classifier guidance of $\lambda=2\times 10^{-4}$,
which is significantly lower than for the single attribute case of 5.1, which
we attribute to the finer per-pixel adjustments that we now have to make.

In Table 2, we provide the results of generating images conditioned on
segmentation masks taken from CelebA-Mask [16]. We compute the mIoU over all
classes between the generated images and input segmentations using a
separately trained Oracle segmentation model on a test set of 500 CelebA-Mask
images. We also compute the FID scores between the two. When comparing to the
naive approach of using a separately trained segmentation network to provide
guidance using the estimates of $\hat{\mathbf{x}}_{0}$, we see that although
we get slightly correct semantic results, the quality is reduced. On the
contrary, when using the DiffAE latent to train a segmentation network and
sample with rejection sampling, we can improve the quality at the loss of
semantic correctness and speed. The latent representation compresses the image
information in that case and thus cannot accurately project the segmentation
onto the entire image. Our method provides more diverse and high-quality
samples without sacrificing semantic correctness. We also note that we run our
method with only ten denoising steps to make the comparison to the faster
DiffAE fair. If we can perform more steps, the results can improve, as shown
in Fig. 2.

Mask | Image | DDIM-I |  DiffAE [21] | Ours | Ours - 100 steps
---|---|---|---|---|---
|  |  |  |  |
Figure 2: Example of segmentation-conditioned generated images for each method. Model | mIoU $\uparrow$ | FID $\downarrow$
---|---|---
DDIM-I | 0.28 | 106.90
DiffAE [21] | 0.23 | 87.68
Ours | 0.31 | 74.74
Table 2: Mean Intersection over Union and FID on the 500-image CelebA-Mask
test set for a segmentation-conditioned generation.

###  5.3 Synthetic data augmentation

####  5.3.1 Setup

To evaluate the effectiveness of our proposed approach, we conduct experiments
on Tiny Imagenet [29]. It has 200 object categories and 100,000 images, with
500 images per category for training and 10,000 images for validation. The
images are of size 64x64 pixels.

We start with an unconditional DDPM trained on Imagenet images with a cosine
noise schedule and fine-tune it as a class-conditioned diffusion model by
adding a classifier embedding as proposed in [19]. The classifier embedding
layer weights are randomly initialized, and we train this model for 150,000
steps with a batch size of 128 and a learning rate of 0.0001.

Since the Tiny Imagenet dataset is much smaller than Imagenet, the resulting
conditional model fails to generate realistic images, as seen in Figure 1. As
a solution, we also train a rejection classifier to improve the quality and
diversity of generated images. We extract Tiny-Imagenet features from the
unconditional DDPM’s U-Net bottleneck layer. Two feature vectors extracted at
timestep $T=300$ and $T=800$ are concatenated to obtain a $1024\times 4\times
4$ embedding. The rejection classifier is a 4-layer CNN with 1.2M parameters
built on top of the U-Net features. We set a threshold of 0.2 and discard any
generated image for which the classifier predicts a probability lower than the
threshold.

We use classifier-free guidance sampling [9] to generate images from our class
conditional model, taking a linear combination of unconditional and
conditional estimates. We use a low guidance weight of 0.01 to encourage
higher diversity and generate additional synthetic images for the classes in
Tiny-Imagenet to construct training datasets with $100,000-400,000$ synthetic
images. Figure 3 shows sample images generated by our approach.

####  5.3.2 Classification Accuracy Score

Classification Accuracy Score (CAS) [22] can be a better proxy than Inception
and FID for measuring the quality of synthetic datasets. CAS was originally
designed for Imagenet; we adopted it for Tiny-Imagenet by computing the Top-1
accuracy on the Tiny-Imagenet validation set using a classifier trained on the
synthetic data.

Table 3 reports the CAS for our synthetic data. In all cases, we train a
ResNet-18 model for 40 epochs with a batch size of 256 using the Adam
optimizer [13] on the different data sources. The learning rate was 0.001 for
20 epochs and reduced to 1/0th at epochs 20 and 30. We generate synthetic data
using the fine-tuned class conditional DDPM (Improved DDPM), combining the
unconditional and conditional models (Classifier-free guidance), and using our
method. The classifier trained on our synthetic data achieves a validation
accuracy of 45.09 %, significantly more than the other baselines, showcasing
our capability to generate more diverse and higher-quality data.

Data type | Data Source | Top-1 accuracy (%)
---|---|---
Real | Tiny-Imagenet | 52.24
Synthetic | Improved DDPM [19] | 35.37
Synthetic | Classifier-free guidance [10] | 36.12
Synthetic | Ours | 45.09
Table 3: Classification Accuracy scores of a Resnet-18 on synthetic data.
Results indicate rejection is critical in making our synthetic data effective.
Figure 3: Tiny-Imagenet samples generated by our method. The classes are 28:
German Shepherd, 30: Tabby Cat, 36: Ladybug, and 52: Gazelle. Our model can
generate diverse images across different classes, proving the effectiveness of
rejection sampling.

####  5.3.3 Combining real and synthetic data

Having verified the quality of our synthetic data, we also try improving the
baseline classification accuracy on Tiny-Imagenet by augmenting the real data
with increasing amounts of diffusion-generated synthetic data. We follow the
same training procedure as 5.3.2 , using three network architectures:
ResNet-18, Wide-ResNet-50 [34], and ResNeXt-50 [32]. Results can be found in
Table 4.

We observe that augmenting the training set with our synthetic images improves
the accuracy of ResNet baselines by up to 8%. ResNeXt-50 performs the best,
improving accuracy from 53.98% with real data only to 63.15% with the
additional augmented data. We see that performance continues to improve as we
increase the amount of synthetic data, with the expected diminishing returns.
The improvement is also consistent across all three network architectures,
which validates the effectiveness of our data generation method.

####  5.3.4 Comparison with image level augmentations

To evaluate the effectiveness of our synthetic data compared to image-level
augmentation methods, we conducted experiments on Tiny Imagenet using Mixup
[35] and Cutmix [33] techniques. We applied Mixup and Cutmix with a
probability of 0.5 on all images in the training set (both real and
synthetic), following the same training procedure from 5.3.3. The results of
these experiments are summarized in Table 4.

Our observations reveal that Mixup and Cutmix techniques further enhance the
accuracy of ResNet baselines. This improvement is consistent across all the
network architectures and different amounts of synthetic data. These findings
demonstrate that our augmentation approach complements image-level
augmentations and can be effectively combined to achieve even better
performance.

| Mixup + |  | Real + | Real + | Real +
---|---|---|---|---|---
Architecture | Cutmix | Real only | 1x Generated | 2x Generated | 3x Generated
Resnet-18 | No | 52.24 | 56.13 | 58.13 | 59.37
| Yes | 52.9 | 58.9 | 62.01 | 62.75
Wide-resnet-50 | No | 53.27 | 58.57 | 61.71 | 62.82
| Yes | 56.56 | 62.71 | 66.42 | 66.82
ResNeXt-50 | No | 53.98 | 59.33 | 62.27 | 63.15
| Yes | 57.98 | 64.4 | 66.85 | 67.05
Table 4: Comparison of Top-1 Accuracy (%) with our synthetic data. When
“Mixup+Cutmix” is indicated as“Yes,” it signifies that Mixup and Cutmix
augmentation techniques were applied to the entire training set with a
probability of 0.5. We can see that our augmentation approach complements
image-level augmentations.

####  5.3.5 Diminishing returns

When progressing from 3x generated data (300k synthetic images) to 7x (700k
images), we observed diminishing returns in the improvement of validation
accuracy, as depicted in Figure 4. Initially, incorporating more synthetic
images led to a notable increase in validation accuracy, indicating the
benefits of augmented data. However, as we further scaled up, the extent of
improvement diminished, suggesting a saturation point where additional
synthetic data yielded diminishing gains, possibly indicating a limit to the
model’s ability to extract valuable information from the augmented samples.

Figure 4: Improvement in Top-1 Accuracy (%) with synthetic data. The X-axis
represents the number of synthetic images used, scaled by a factor of 100k,
with 0 indicating the utilization of only real images. As anticipated, the
graph demonstrates diminishing returns as synthetic data increases.

##  6 Conclusion

In this paper, we proposed a method for adapting pre-trained unconditional
diffusion models to new conditions using the internal learned representations
of the denoiser network. The effectiveness of the proposed approach is
demonstrated by providing guidance for attribute-conditioned generation and
mask-conditioned generation, as well as filtering samples for synthetic data
augmentation. We showed that augmenting the Tiny ImageNet training set with
synthetic images generated by our approach significantly improves the
classification accuracy over ResNet baselines. This result highlights the
potential of our approach to improving the performance on datasets with
limited labels by using a generative diffusion model as a pre-training task or
feature extractor.

## References

  * [1] D. Baranchuk, A. Voynov, I. Rubachev, V. Khrulkov, and A. Babenko.  Label-efficient semantic segmentation with diffusion models.  In ICLR. OpenReview.net, 2022.
  * [2] E. A. Brempong, S. Kornblith, T. Chen, N. Parmar, M. Minderer, and M. Norouzi.  Denoising pretraining for semantic segmentation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4175–4186, 2022.
  * [3] T. Chen, R. Zhang, and G. Hinton.  Analog bits: Generating discrete data using diffusion models with self-conditioning, 2022.
  * [4] P. Dhariwal and A. Q. Nichol.  Diffusion models beat gans on image synthesis.  In NeurIPS, pages 8780–8794, 2021.
  * [5] A. Graikos, N. Malkin, N. Jojic, and D. Samaras.  Diffusion models as plug-and-play priors.  In Thirty-Sixth Conference on Neural Information Processing Systems, 2022.
  * [6] K. He, X. Zhang, S. Ren, and J. Sun.  Deep residual learning.  Image Recognition, 7, 2015.
  * [7] J. Ho, A. Jain, and P. Abbeel.  Denoising diffusion probabilistic models.  In NeurIPS, 2020.
  * [8] J. Ho, C. Saharia, W. Chan, D. J. Fleet, M. Norouzi, and T. Salimans.  Cascaded diffusion models for high fidelity image generation.  J. Mach. Learn. Res., 23:47:1–47:33, 2022.
  * [9] J. Ho and T. Salimans.  Classifier-free diffusion guidance.  In NeurIPS 2021 Workshop on Deep Generative Models and Downstream Applications, 2021.
  * [10] J. Ho and T. Salimans.  Classifier-free diffusion guidance, 2022.
  * [11] E. Hoogeboom, V. G. Satorras, C. Vignac, and M. Welling.  Equivariant diffusion for molecule generation in 3d.  In ICML, volume 162 of Proceedings of Machine Learning Research, pages 8867–8887. PMLR, 2022.
  * [12] T. Karras, S. Laine, and T. Aila.  A style-based generator architecture for generative adversarial networks.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 4401–4410, 2019.
  * [13] D. P. Kingma and J. Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [14] Z. Kong, W. Ping, J. Huang, K. Zhao, and B. Catanzaro.  Diffwave: A versatile diffusion model for audio synthesis.  In ICLR. OpenReview.net, 2021.
  * [15] Y. Le and X. Yang.  Tiny imagenet visual recognition challenge.  CS 231N, 7(7):3, 2015.
  * [16] C.-H. Lee, Z. Liu, L. Wu, and P. Luo.  Maskgan: Towards diverse and interactive facial image manipulation.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2020.
  * [17] Z. Liu, P. Luo, X. Wang, and X. Tang.  Deep learning face attributes in the wild.  In Proceedings of International Conference on Computer Vision (ICCV), December 2015.
  * [18] C. Mou, X. Wang, L. Xie, J. Zhang, Z. Qi, Y. Shan, and X. Qie.  T2i-adapter: Learning adapters to dig out more controllable ability for text-to-image diffusion models.  arXiv preprint arXiv:2302.08453, 2023.
  * [19] A. Q. Nichol and P. Dhariwal.  Improved denoising diffusion probabilistic models.  In ICML, volume 139 of Proceedings of Machine Learning Research, pages 8162–8171. PMLR, 2021.
  * [20] A. Q. Nichol, P. Dhariwal, A. Ramesh, P. Shyam, P. Mishkin, B. McGrew, I. Sutskever, and M. Chen.  GLIDE: towards photorealistic image generation and editing with text-guided diffusion models.  In ICML, volume 162 of Proceedings of Machine Learning Research, pages 16784–16804. PMLR, 2022.
  * [21] K. Preechakul, N. Chatthee, S. Wizadwongsa, and S. Suwajanakorn.  Diffusion autoencoders: Toward a meaningful and decodable representation.  In CVPR, pages 10609–10619. IEEE, 2022.
  * [22] S. Ravuri and O. Vinyals.  Classification accuracy score for conditional generative models.  Advances in neural information processing systems, 32, 2019.
  * [23] R. Rombach, A. Blattmann, D. Lorenz, P. Esser, and B. Ommer.  High-resolution image synthesis with latent diffusion models.  In CVPR, pages 10674–10685. IEEE, 2022.
  * [24] O. Ronneberger, P. Fischer, and T. Brox.  U-net: Convolutional networks for biomedical image segmentation.  Medical Image Computing and Computer-Assisted Intervention (MICCAI), 2015.
  * [25] A. Sinha, J. Song, C. Meng, and S. Ermon.  D2C: diffusion-decoding models for few-shot conditional generation.  In NeurIPS, pages 12533–12548, 2021.
  * [26] J. Sohl-Dickstein, E. A. Weiss, N. Maheswaranathan, and S. Ganguli.  Deep unsupervised learning using nonequilibrium thermodynamics.  In F. R. Bach and D. M. Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, volume 37 of JMLR Workshop and Conference Proceedings, pages 2256–2265. JMLR.org, 2015.
  * [27] J. Song, C. Meng, and S. Ermon.  Denoising diffusion implicit models.  In ICLR. OpenReview.net, 2021.
  * [28] Y. Song, J. Sohl-Dickstein, D. P. Kingma, A. Kumar, S. Ermon, and B. Poole.  Score-based generative modeling through stochastic differential equations.  In ICLR. OpenReview.net, 2021.
  * [29] Tiny ImageNet.  https://www.kaggle.com/c/tiny-imagenet, 2017.
  * [30] N. Tursynbek and M. Niethammer.  Unsupervised discovery of 3d hierarchical structure with generative diffusion features.  arXiv preprint arXiv:2305.00067, 2023.
  * [31] A. Vahdat and J. Kautz.  NVAE: A deep hierarchical variational autoencoder.  In NeurIPS, 2020.
  * [32] S. Xie, R. Girshick, P. Dollár, Z. Tu, and K. He.  Aggregated residual transformations for deep neural networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1492–1500, 2017.
  * [33] S. Yun, D. Han, S. J. Oh, S. Chun, J. Choe, and Y. Yoo.  Cutmix: Regularization strategy to train strong classifiers with localizable features.  In Proceedings of the IEEE/CVF international conference on computer vision, pages 6023–6032, 2019.
  * [34] S. Zagoruyko and N. Komodakis.  Wide residual networks.  arXiv preprint arXiv:1605.07146, 2016.
  * [35] H. Zhang, M. Cisse, Y. N. Dauphin, and D. Lopez-Paz.  mixup: Beyond empirical risk minimization.  arXiv preprint arXiv:1710.09412, 2017.
  * [36] L. Zhang and M. Agrawala.  Adding conditional control to text-to-image diffusion models.  arXiv preprint arXiv:2302.05543, 2023.


# On the Convergence of No-Regret Dynamics in Information Retrieval Games with
Proportional Ranking Functions††thanks: Equal authors contribution.

Omer Madmon, Idan Pipano, Itamar Reinman, Moshe Tennenholtz  Faculty of Data
and Decision Sciences, Technion - Israel Institute of Technology,
<EMAIL_ADDRESS>Faculty of Data and Decision Sciences,
Technion - Israel Institute of Technology<EMAIL_ADDRESS>Faculty of Data and Decision Sciences, Technion - Israel Institute of
Technology<EMAIL_ADDRESS>Faculty of Data and Decision
Sciences, Technion - Israel Institute of Technology<EMAIL_ADDRESS>
###### Abstract

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

##  1 Introduction

In the era of digital content consumption, recommender systems play an
essential role in shaping user experiences and engagement on various
platforms, including search engines, streaming services, social networks, and
more. The core task of a recommender system is to match users with relevant
content, created by content creators. By that, the system induces an ecosystem
in which content providers compete for exposure and often engage in strategic
behavior to maximize visibility [QJ24]. 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
[KT22].

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

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

##### Our contribution

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

###  1.1 Related work

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

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

More recent studies on strategic behavior within recommendation and search
ecosystems have adapted several modeling assumptions that reflect the use of
deep learning and dense representations [HKJ+22, JGS23, YLS+24, MPRT24].
Unlike earlier studies, these recent efforts assume that content is
represented within a continuous embedding space, rather than a discrete set of
”topics”. In contrast to [YLS+24], 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 [HKJ+22, JGS23] and the study of
better-response dynamics convergence [MPRT24] under specific recommendation or
ranking mechanisms. In contrast, this work characterizes a rich and intuitive
family of mechanisms that guarantee the convergence of _no-regret dynamics_.

The fundamental connections between no-regret learning and game-theoretic
solution concepts [FV97, FS99, HMC00, BHLR08, Rou15] have made the regret-
minimization framework very appealing to the machine learning and artificial
intelligence communities [RS13, BBJT15, SALS15, MSB+17, BS18, KHSC18, DFG21,
FAL+22, APFS24]. In particular, the notion of concave games [Ros65] and its
connection to the convergence of no-regret dynamics showed by [EdMN09] plays a
crucial role in our analysis.

##  2 Preliminaries

##### Game theory

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

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

##### No-regret dynamics

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

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

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

##### Concave games

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

######  Definition 1.

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

  1. A1.

There exist strictly positive coefficients $\alpha_{1},...\alpha_{n}>0$, such
that $\sum_{i=1}^{n}\alpha_{i}=1$ and the function
$g(x)\coloneqq\sum_{i=1}^{n}\alpha_{i}\cdot u_{i}(x)$ is concave in $x$.

  2. A2.

The utility function of each player $i$ is convex in the actions of all other
players. That is, $\forall i\in N,\forall x_{i}\in X_{i}$, the function
$f(x_{-i})\coloneqq u_{i}(x_{i},x_{-i})$ is convex in $x_{-i}$.

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

##  3 The model

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

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

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

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

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

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

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

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

######  Definition 2.

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

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

######  Lemma 1.

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

In the sequel, we restrict our attention to the very natural class of
_proportional ranking functions_ :

######  Definition 3.

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

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

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

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

##  4 Main result

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

######  Theorem 1.

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

  1. I.

The activation function $g$ is concave

  2. II.

$r$ induces concave games

  3. III.

$r$ induces socially-concave games

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

###### Proof.

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

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

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

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

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

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

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

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

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

######  Corollary 1.

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

##  5 Experimental comparison of ranking functions

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

  * •

The linear proportional ranking function family: $g_{lin}(t)=b-t$, where $b>1$
is the intercept hyperparameter.

  * •

The root proportional ranking function family: $g_{root}(t)=(1-t)^{a}$, where
$0<a<1$ is the power hyperparameter.

  * •

The logarithmic proportional ranking function family: $g_{log}(t)=\ln(c-t)$,
where $c>2$ is the shift hyperparameter.

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

###  5.1 Simulation details

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

##### Evaluation criteria

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

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

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

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

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

###  5.2 Simulations results

####  5.2.1 Comparison between ranking function families

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

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

##### The effect of the penalty factor $\lambda$

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

Figure 1:  The effect of the penalty factor $\lambda$, with $n=3,s=3$ and
$k=3$.  Figure 2: The effect of the number of publishers $n$, with
$\lambda=0.5$, $s=3$ and $k=3$.

##### The effect of the number of publishers $n$

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

##### The effect of the demand distribution support size $s$

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

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

##### The effect of the embedding space dimension $k$

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

Figure 3: The effect of the demand distribution support size $s$, with
$\lambda=0.5,n=3$ and $k=3$. Figure 4: The effect of the embedding space
dimension $k$, with $\lambda=0.5$, $n=3$ and $s=3$.

####  5.2.2 Comparison within ranking function families

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

##  6 Discussion

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

##### Limitations

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

## Acknowledgments

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

## References

  * [APFS24] 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.
  * [BBJT15] Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin.  Heads-up limit hold’em poker is solved.  Science, 347(6218):145–149, 2015.
  * [BBTK15] Ran Ben Basat, Moshe Tennenholtz, and Oren Kurland.  The probability ranking principle is not optimal in adversarial retrieval settings.  In Proceedings of the 2015 International Conference on The Theory of Information Retrieval, pages 51–60, 2015.
  * [BHLR08] 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, pages 373–382, 2008.
  * [BPGRT19] 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, pages 1772–1779, 2019.
  * [BPRT19] 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, pages 1780–1787, 2019.
  * [BPT17] Omer Ben-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, pages 58–73. Springer, 2017.
  * [BPT18] Omer Ben-Porat and Moshe Tennenholtz.  A game-theoretic approach to recommendation systems with strategic content providers.  Advances in Neural Information Processing Systems, 31, 2018.
  * [BS18] Noam Brown and Tuomas Sandholm.  Superhuman ai for heads-up no-limit poker: Libratus beats top professionals.  Science, 359(6374):418–424, 2018.
  * [BTK17] Ran Ben Basat, Moshe Tennenholtz, and Oren Kurland.  A game theoretic analysis of the adversarial retrieval setting.  Journal of Artificial Intelligence Research, 60:1127–1164, 2017.
  * [DFG21] 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.
  * [EdMN09] Eyal Even-dar, Yishay Mansour, and Uri Nadav.  On the convergence of regret minimization dynamics in concave games.  In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC ’09, page 523–532. Association for Computing Machinery, 2009.
  * [EHL22] 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.
  * [FAL+22] Gabriele Farina, Ioannis Anagnostides, Haipeng Luo, Chung-Wei Lee, Christian Kroer, and Tuomas Sandholm.  Near-optimal no-regret learning dynamics for general convex games.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 39076–39089. Curran Associates, Inc., 2022.
  * [FS99] Yoav Freund and Robert E Schapire.  Adaptive game playing using multiplicative weights.  Games and Economic Behavior, 29(1-2):79–103, 1999.
  * [FV97] Dean P Foster and Rakesh V Vohra.  Calibrated learning and correlated equilibrium.  Games and Economic Behavior, 21(1-2):40, 1997.
  * [HKJ+22] Jiri Hron, Karl Krauth, Michael I Jordan, Niki Kilbertus, and Sarah Dean.  Modeling content creator incentives on algorithm-curated platforms.  arXiv preprint arXiv:2206.13102, 2022.
  * [HMC00] Sergiu Hart and Andreu Mas-Colell.  A simple adaptive procedure leading to correlated equilibrium.  Econometrica, 68(5):1127–1150, 2000.
  * [JGS23] Meena Jagadeesan, Nikhil Garg, and Jacob Steinhardt.  Supply-side equilibria in recommender systems.  arXiv preprint arXiv.2206.13489, 2023.
  * [KHSC18] 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 on Machine Learning, pages 2488–2496. PMLR, 2018.
  * [KT22] Oren Kurland and Moshe Tennenholtz.  Competitive search.  In Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 2838–2849, 2022.
  * [MPRT24] Omer Madmon, Idan Pipano, Itamar Reinman, and Moshe Tennenholtz.  The search for stability: Learning dynamics of strategic publishers with initial documents.  arXiv preprint arXiv:2305.16695, 2024.
  * [MSB+17] Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisỳ, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling.  Deepstack: Expert-level artificial intelligence in heads-up no-limit poker.  Science, 356(6337):508–513, 2017.
  * [QJ24] Kun Qian and Sanjay Jain.  Digital content creation: An analysis of the impact of recommendation systems.  Management Science, 2024.
  * [Rob77] Stephen E Robertson.  The probability ranking principle in ir.  Journal of documentation, 1977.
  * [Ros65] J Ben Rosen.  Existence and uniqueness of equilibrium points for concave n-person games.  Econometrica: Journal of the Econometric Society, pages 520–534, 1965.
  * [Rou15] Tim Roughgarden.  Intrinsic robustness of the price of anarchy.  Journal of the ACM (JACM), 62(5):1–42, 2015.
  * [RRTK17] 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 on Research and Development in Information Retrieval, pages 465–474, 2017.
  * [RS13] Sasha Rakhlin and Karthik Sridharan.  Optimization, learning, and games with predictable sequences.  Advances in Neural Information Processing Systems, 26, 2013.
  * [SALS15] 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.
  * [Ui08] Takashi Ui.  Correlated equilibrium and concave games.  International Journal of Game Theory, 37(1):1–13, 2008.
  * [YLS+24] 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, 2024.
  * [You23] YouTube.  Youtube partner program overview & eligibility, 2023.
  * [ZLRW22] Wayne Xin Zhao, Jing Liu, Ruiyang Ren, and Ji-Rong Wen.  Dense text retrieval based on pretrained language models: A survey, 2022.
  * [ZML+20] 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.

##  Appendix A Proofs

###  A.1 Proof of Lemma 1

###### Proof.

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

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

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

###  A.2 Full derivation of inequality $f^{\prime\prime}(\hat{a})>0$ from the
main proof

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

###  A.3 Proof that if $d$ is strictly bi-convex and $g$ is concave then $r$
induces strictly concave games

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

###### Proof.

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

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

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

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

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

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

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

∎

##  Appendix B Hyperparameters comparison figures

Figure 5: The effect of the intercept $b$ in the linear proportional ranking
function, with $\lambda=0.5$, $n=3,s=3$ and $k=3$. Figure 6: The effect of the
power $a$ in the root proportional ranking function, with $\lambda=0.5$,
$n=3,s=3$ and $k=3$. Figure 7: The effect of the shift $c$ in the logarithmic
proportional ranking function, with $\lambda=0.5$, $n=3,s=3$ and $k=3$.