# Learning Robust Sequential Recommenders through
Confident Soft Labels

Shiguang Wu  Shandong UniversityQingdaoChina<EMAIL_ADDRESS>,
Xin Xin  Shandong UniversityQingdaoChina<EMAIL_ADDRESS>,  Pengjie Ren
Shandong UniversityQingdaoChina<EMAIL_ADDRESS>,  Zhumin Chen  Shandong
UniversityQingdaoChina<EMAIL_ADDRESS>,  Jun Ma  Shandong
UniversityQingdaoChina<EMAIL_ADDRESS>,  Maarten de Rijke  University of
AmsterdamAmsterdamThe Netherlands<EMAIL_ADDRESS>and  Zhaochun Ren  Leiden
UniversityLeidenThe Netherlands<EMAIL_ADDRESS>
(2023)

###### Abstract.

Sequential recommenders that are trained on implicit feedback are usually
learned as a multi-class classification task through softmax-based loss
functions on one-hot class labels. However, one-hot training labels are sparse
and may lead to biased training and sub-optimal performance. Dense, soft
labels have been shown to help improve recommendation performance. But how to
generate high-quality and confident soft labels from noisy sequential
interactions between users and items is still an open question.

We propose a new learning framework for sequential recommenders, CSRec, which
introduces confident soft labels to provide robust guidance when learning from
user-item interactions. CSRec contains a teacher module that generates high-
quality and confident soft labels and a student module that acts as the target
recommender and is trained on the combination of dense, soft labels and
sparse, one-hot labels.

We propose and compare three approaches to constructing the teacher module:
(i) model-level,  (ii) data-level, and  (iii) training-level.  To evaluate the
effectiveness and generalization ability of CSRec, we conduct experiments
using various state-of-the-art sequential recommendation models as the target
student module on four benchmark datasets. Our experimental results
demonstrate that CSRec is effective in training better performing sequential
recommenders.

Sequential recommendation, Recommender systems, Soft labels, Robustness,
Implicit feedback

††journalyear: 2023††copyright: rightsretained††journal: TOIS††ccs:
Information systems Recommender systems††ccs: Information systems
Personalization††ccs: Information systems Retrieval models and ranking††ccs:
Information systems Novelty in information retrieval

##  1\. Introduction

Generating next-item recommendations from sequential implicit user feedback is
a widely adopted way of training recommender systems. It is common in
scenarios like e-commerce (Zhu et al., 2018), video platforms (Zhao et al.,
2019), and streaming music services (Takama et al., 2021). The problem of
learning sequential recommenders based on implicit feedback can be formulated
as a multi-class classification task where each candidate item corresponds to
a class. Then, a list of recommendations is generated by choosing items with
the highest classification logits.

Deep neural networks have been widely used to address such classification
tasks through softmax-based loss functions over one-hot class labels. We can
view the items that a user has interacted with as being labeled as 1s, while
all other items from the item catalogue are labeled as 0s (Tan et al., 2016a;
Yuan et al., 2019; Kang and McAuley, 2018; Li et al., 2017). Thus, the items a
user has interacted with are interpreted as the user’s positive preferences
and are pushed towards higher classification logits in the training process;
all other candidate items are assumed to capture negative user preferences.
However, one-hot training labels are sparse and can easily be corrupted (Zhou
et al., 2021; Song et al., 2022). For example, interactions with an item may
only be due to presentation bias (Chen et al., 2020, 2021) and an absent
interaction may be attributed to user unawareness since the item may not have
been exposed to this user (Vardasbi et al., 2020). Hence, simply promoting
high values for items labeled with a 1 and demoting other candidate items can
lead to a misunderstanding of user preferences.

Soft labels. Recent work (Liu et al., 2020a; Cheng et al., 2021) has shown
that compared with sparse one-hot training labels, _soft labels_ can help to
improve the recommendation performance. _Soft_ labels are labels that use
class probabilities produced by models instead of the hard one-zero
representation, i.e., one-hot labels. They can be seen as a dense distribution
over candidate items given the current sequence of items. Liu et al. (2020a)
propose a debiasing recommendation framework based on soft labels that
originate from knowledge distillation of uniform exposure data. Cheng et al.
(2021) use popularity-based or user-based soft labels to train recommenders.

Motivated by (Liu et al., 2020a; Cheng et al., 2021), we hypothesize that
_high-quality and confident soft labels can help to train more robust
sequential recommenders_. Here, a soft label is _confident_ if the supervision
signals that it provides reflect the real user preferences and have low
variance. And a sequential recommender is _robust_ if it is able to generate
recommendations that lead to a positive user experience even if the training
data is corrupted or contains noise. Unfortunately, the uniform exposure data
used in (Liu et al., 2020a) will always be limited and expensive to collect
since doing so may negatively affect the user experience by exposing
irrelevant items. And the soft labels used in (Cheng et al., 2021) can easily
get biased or corrupted by the training data and the teacher model itself.

(a) Yelp (b) Electronics

Figure 1. Performance of Base recommendation model and SoftRec method (Cheng
et al., 2021) on different groups of users. The items are divided into two
bins, 20% and 80%, based on the frequency. We then split users based on which
kind of items they choose as the next interactions, popular or niche items.
The two user groups are referred to as _popular-type_ and _niche-type_ users.
We evaluate the recommendation performance on each group separately. We choose
GRU4Rec (Tan et al., 2016a) as the Base recommendation model and SoftRec
(Cheng et al., 2021) as the comparison method on the (a) Yelp and (b)
Electronics dataset. The niche-type users receive worse recommendation results
after using the soft labels proposed in (Cheng et al., 2021).

As shown in Fig 1, niche-type users, who choose niche items as their next
selections, receive worse recommendation results after using the soft labels
proposed in (Cheng et al., 2021). The bias of soft labels used in (Cheng et
al., 2021) results in less exposure of niche items, which is not beneficial
for both users and merchants in the long run. Hence, how to create confident,
soft labels from noisy sequential interactions between users and items remains
an open question.

Recommendations with confident soft labels. We propose CSRec, a learning
framework to train robust sequential recommenders from implicit user feedback.
The core idea is to introduce confident, soft labels that complement the one-
hot labels during the learning process. CSRec comprises a teacher module that
generates confident, soft labels from noisy sequential interactions between
users and items, and a student module that can be seen as the target
recommender. We propose three methods for constructing the teacher module:
(i) model-level,  (ii) data-level, and  (iii) training-level.  These
alternatives are motivated as follows:

  * •

Recent research (Dodge et al., 2020; Yun and Wong, 2020) has shown that
different models, or even a set of instances of the same model initialized
with different random seeds, introduce different kinds of bias into model
outputs. Our model-level method constructs confident, soft labels from a
multi-model ensemble to reduce the bias and variance from the model itself.

  * •

Our data-level method reduces the bias or noisy signals coming from the data
by exploiting sub-sampling procedures to feed the teacher models with
different subsets of the data. The confident, soft labels are, again,
generated from a multi-data ensemble.

  * •

The model-level and data-level methods use ensemble methods to obtain
confident soft labels. Instead, the training-level method focuses on directly
training a teacher module in an end-to-end fashion. The key insight is to
minimize the Kullback-Leibler (KL) divergence between predictions of two
teacher models since confident, soft labels from different models should be
consistent to provide more robust guidance.

Given confident, soft labels from the teacher module, the target student
recommender is trained using a combination of dense, soft labels and sparse
one-hot labels. Although knowledge distillation also utilizes soft labels, the
motivation is quite different. Knowledge distillation aims to compress a large
neural network model into a relatively smaller model for more efficiency
inference, while we aim at utilizing robust soft labels to generate robust
recommendations from biased data, instead of speeding up the inference.
Besides, existing ensemble methods perform ensembles in both training and
inference, while our method involves multiple models to generate confident
soft labels in the training stage and only a single robust target recommender
is used during inference, thus achieving higher recommendation efficiency.

Experimental comparison. To assess the effectiveness and generalization
capability of recommender systems trained using the labels produced by CSRec,
we conduct experiments on four benchmark datasets using different kinds of
state-of-the-art sequential recommendation models as the target recommendation
module:  (i) the recurrent neural network (RNN)-based GRU4Rec (Tan et al.,
2016a),  (ii) the convolutional neural network (CNN)-based Nextitnet (Yuan et
al., 2019),  (iii) the attention-based NARM (Li et al., 2017), and  (iv) the
self-attentive SASRec (Kang and McAuley, 2018).  Experimental results
demonstrate the effectiveness and generalization capability of the CSRec
learning framework.

Contributions. Summarizing, the contributions of our work are:

  * •

We propose CSRec, a learning framework to enhance implicit feedback-based
sequential recommenders through a teacher module that provides confident, soft
labels and a target student recommender trained on sparse, one-hot labels and
dense, soft labels.

  * •

We propose three methods for constructing the teacher module:  (i) a model-
level method,  (ii) a data-level method, and  (iii) a training-level method,
all aimed at reducing the effect of bias and noisy interaction signals.

  * •

We evaluate CSRec with four kinds of state-of-the-art deep learning-based
sequential recommendation models and conduct experiments on four benchmark
datasets. The results demonstrate the effectiveness of the CSRec learning
framework.

##  2\. Related work

We review related work on sequential recommendation and learning from soft
labels.

###  2.1. Sequential recommendation

Early work on sequential recommendation mainly depends on factorization
methods (Wang et al., 2018; Wen and Zhang, 2020) or Markov chains (He and
McAuley, 2016; Yang et al., 2020). More recently, deep learning-based
sequential recommendations have attracted attention due to their learning
capacity. Deep learning-based sequential recommendation models can be
categorized into  (i) RNN-based models (Nelaturi and Devi, 2019; Tan et al.,
2016a; Hidasi and Karatzoglou, 2018),  (ii) CNN-based models (Tang and Wang,
2018), and  (iii) attention-based models (Luo et al., 2020; Kang and McAuley,
2018).  GRU4Rec (Tan et al., 2016a) is a representative RNN-based model that
uses gated recurrent units to learn sequential signals. Caser (Tang and Wang,
2018) and Nextitnet (Yuan et al., 2019) are CNN-based models that can capture
skip signals in the interaction sequence. NARM (Li et al., 2017) introduces an
attention mechanism to assign different degrees of importance to items that a
user interacts with in the item sequence. SASRec (Kang and McAuley, 2018) uses
self-attention and a transformer decoder (Vaswani et al., 2017) to perform
sequential recommendation. Unlike the causal decoding of SASRec, BERT4Rec (Sun
et al., 2019) uses the objective of masked language models to train the
recommender.

Conventional training of sequential recommenders with implicit feedback uses
the point-wise binary cross-entropy (BCE) loss or the pair-wise ranking loss
(e.g., BPR (Rendle et al., 2009)). Both need a negative sampling strategy to
sample negative instances from missing interactions. The sampling size and
distribution are likely to affect the recommendation performance (Caselles-
Dupré et al., 2018). Although there is work that focuses on non-sampling-based
training methods, they are limited because of their high computational costs
(Chen et al., 2022b) or their shallow linear models (Xin et al., 2018).

Deep learning-based approaches to sequential recommendation are often
formulated as multi-class classifiers where each candidate item corresponds to
a class. The deep models are then trained through a softmax classification
loss over the sparse one-hot class labels, in which items that users
interacted with are labeled as 1s, and all other candidate items are labeled
as 0s (Tan et al., 2016a; Yuan et al., 2019; Kang and McAuley, 2018; Li et
al., 2017; Sun et al., 2019; Chang et al., 2021). Such a solution assumes that
the items that users interacted with indicate positive user preferences while
all other candidate items reflect negative user preferences. This assumption
seldom holds for real-world cases (Vardasbi et al., 2020). Interactions may be
attributed to various kinds of presentation bias (Chen et al., 2020); and in
some cases, a lack of interaction may be attributed to the user’s unawareness.
Thus, sparse one-hot training labels can easily be corrupted and cannot
capture unobserved user-item interactions. Solving the sequential
recommendation task through sparse one-hot labels therefore leads to biased
training and sub-optimal performance (Chen et al., 2020; Liu et al., 2020a;
Zhou et al., 2021).

In this paper, we aim to learn sequential recommenders from implicit feedback
data by using confident, soft labels in addition to sparse one-hot labels.

###  2.2. Learning from soft labels

(a) Model-level CSRec (b) Data-level CSRec (c) Training-level CSRec

Figure 2. Framework of CSRec, with (a) model-level teachers, (b) data-level
teachers, and (c) training-level teachers.

Soft labels have been successfully exploited in computer vision (CV) and
natural language processing (NLP). Knowledge distillation (Hinton et al.,
2015) is a widely adopted learning framework aimed at compressing large
complex models into a simple model with a much smaller model size for faster
model inference. Knowledge distillation extracts the hidden knowledge from
large teacher networks in the form of soft labels to guide the training
process of a much smaller student network. Distillation using multi-models has
also been investigated in CV and NLP. A common way of multi-model distillation
is to use the average response from all teachers as part of the supervision
signals for the student (Gou et al., 2021; Zhang et al., 2018; You et al.,
2017). For example, You et al. (2017) average the outputs of different
teachers and reduce the dissimilarity between the student and teachers; Du et
al. (2020) use multi-objective optimization to determine the best direction
that accommodates different teachers; and Liu et al. (2020b) average the
outputs of teachers with weights generated from themselves.

Some recent work has exploited soft labels to improve recommendations. Even
though the prediction from a well-trained teacher model contains beneficial
knowledge and may be helpful for building additional supervision for student
models, naive distillation would bring unwanted bias and noisy signals. The
root cause lies in the fact that, compared with the data in CV and NLP, the
interaction data in recommendation contains more noise and biases. Chen et al.
(2022a) find the biased student phenomenon during model compression using
knowledge distillation. They propose a grouping method to specifically tackle
the popularity bias in the general recommendation system. Their method heavily
relies on prior knowledge of the bias. Besides, their method focuses on
improving the distillation process given biased soft labels, while our
research is aimed at inferring more robust and confident soft labels, which
works at different stages. Liu et al. (2020a) propose a debiasing framework
for recommendations based on soft labels learned from uniform interaction
data. However, uniform interaction data is always limited and expensive to
collect since it affects the user experience. Cheng et al. (2021) use
popularity-based and user-based soft labels to enhance sequential
recommenders. Unfortunately, their generated soft labels can easily be
corrupted by noisy implicit feedback.

To conclude, knowledge distillation in CV and NLP mainly focuses on using soft
labels to perform model compression or transfer learning. In recommender
systems, how to generate confident, soft labels from noisy implicit feedback
from users for robust sequential recommendation is still an open research
question. We address this question head on and provide a new learning
framework using soft labels to obtain robust sequential recommenders from
implicit feedback.

##  3\. method

In this section, we first share our notation and the task formulation. Then we
describe three ways of constructing a teacher module that provides confident,
dense, soft labels. Finally, we detail the training procedure of the target
student recommender.

###  3.1. Notation and task formulation

We focus on the task of learning sequential recommenders from implicit user
feedback. We denote the user set and the item set as $\mathcal{U}$ and
$\mathcal{I}$, respectively. Each user $u\in\mathcal{U}$ implicitly interacts
with a sequence of items
$\boldsymbol{s}_{u}=(i_{1},i_{2},\dots,i_{|\boldsymbol{s}_{u}|})$, sorted by
time. Ideally, the next interacted item is the one with the highest
probability in the real user preference distribution
$P(i\mid\boldsymbol{s}_{u})$. However, the observed next item
$i_{|\boldsymbol{s}_{u}|+1}$ can be corrupted by different kinds of noise
(bias), which can be formulated as:

(1)
$i_{|\boldsymbol{s}_{u}|+1}=\arg\max_{i\in\mathcal{I}}P(i\mid\boldsymbol{s}_{u})+\epsilon,$

where $\epsilon$ denotes the noisy signal. The task is to train a target
recommender $f$ that can approximate the real user preference as
$P_{f}(i\mid\boldsymbol{s}_{u})\approx P(i\mid\boldsymbol{s}_{u})$. During
model inference, recommendations can be generated as

(2) $\tilde{i}=\arg\max_{i\in\mathcal{I}}f(\boldsymbol{s}_{u}),$

where $f(\boldsymbol{s}_{u})$ denotes the output logits of recommender $f$.
This task can be formulated as a multi-class classification problem with
$\mathcal{I}$ being the candidate class set. Conventional methods that ignore
the noisy signal $\epsilon$ use a softmax-based cross-entropy loss to train
the recommender $f$ by minimizing the difference between $\tilde{i}$ and
$i_{|\boldsymbol{s}_{u}|+1}$. However, due to the existence of $\epsilon$,
$i_{|\boldsymbol{s}_{u}|+1}$ is not actually sampled from
$P(i\mid\boldsymbol{s}_{u})$, resulting in a discrepancy between the
potentially misdirected learned distribution $P_{f}(i\mid\boldsymbol{s}_{u})$
and the ideal unbiased distribution $P(i\mid\boldsymbol{s}_{u})$.

To address the above issue, the proposed CSRec framework treats the target
recommender $f$ as a student module and introduces a teacher module that
consists of a set of models $\left\\{g_{1},g_{2},\ldots,g_{m}\right\\}$. The
teacher module aims to generate confident, soft labels to  (i) provide dense
supervision signals of large amounts of missing interactions; and  (ii)
alleviate the effect of the noisy signal $\epsilon$.  Then, the student model
$f$ is trained on the combination of dense, soft labels and sparse data
observation of $i_{|\boldsymbol{s}_{u}|+1}$. Fig 2 shows three alternative
teacher modules for CSRec, which we detail next.

###  3.2. Confident teacher module

We describe the three alternative teacher modules for CSRec.

####  3.2.1. Model-level teachers

Recent research (Dodge et al., 2020; Yun and Wong, 2020) shows that different
models, or a set of the same models but with different random seeds, are able
to introduce different types of bias into model outputs. This suggests that
different models capture different aspects of $\epsilon$, as model-specific
noisy signals $\epsilon_{m}$. We propose to construct a confident teacher
module from multiple models to benefit from this insight. The key idea is to
take the average outputs of multiple teacher models. Thus, noisy signals
$\epsilon_{m}$ along with their models are averaged, which gives us a more
uniform error distribution and more robust predictions to generate soft
labels.

We use a set of models $\\{g_{1},g_{2},\ldots,g_{m}\\}$ that are based on the
same model architecture with the target student recommender $f$ but with
different random seeds as the teacher module. We train
$\\{g_{1},\dots,g_{m}\\}$ individually on the entire dataset using different
training seeds. We use the softmax-based cross-entropy as the training loss
function for the teacher models, denoted as $\ell_{ce}$. Then we take the
average of the outputs to generate soft labels to guide the student.

The training process of model-level teachers is described in Algorithm 1.
Model-level teachers are expected to alleviate bias or noise introduced by the
model itself, i.e., $\epsilon_{m}$.

Algorithm 1 Model-level teachers

1:$\\{g_{1},g_{2},\ldots,g_{m}\\}$: teacher models; $\eta$: learning rate;
$\ell_{ce}(\cdot)$: loss for teacher models; $\theta(\cdot)$: parameters; $D$:
training set

2:repeat

3: for all $\boldsymbol{s}_{u}\in D$ do

4:
$\theta(g_{k})\\!\leftarrow\\!\theta(g_{k})\\!-\\!\eta\cdot\nabla\ell_{ce}(\boldsymbol{s}_{u},g_{k},i_{|\boldsymbol{s}_{u}|+1})$$\triangleright$
$k=1,2,\dots,m$

5: end for

6:until converged

7:for all $\boldsymbol{s}_{u}\in D$ do

8: $\mathbf{e}_{u}\leftarrow\sum g_{k}(\boldsymbol{s}_{u})/m$ $\triangleright$
ensemble of $g_{k}$

9:end for

10:return  $\mathbf{e}_{u}$

####  3.2.2. Data-level teachers

Despite the noisy signal of $\epsilon_{m}$, which is reflected in the model-
level perspective, there may also be data-level bias, $\epsilon_{d}$, as a
part of the noisy signal $\epsilon$. We argue that $\epsilon_{d}$ is data-
specific and has different distributions across different data subsets. As a
result, a multi-data ensemble of models trained on different subsets of the
data would help us alleviate the effect of $\epsilon_{d}$ and provide more
robust guidance for the target student recommender.

To this end, we propose to construct the confident teacher module from the
data-level view. We perform subsampling with a uniform probability $p$ on the
entire data and generate different subsets. Then, teacher models
$\\{g_{1},g_{2},\ldots,g_{m}\\}$, which have the same model structure, are
trained to fit different data subsets. Then we fuse the outputs of
$\\{g_{1},g_{2},\ldots,g_{m}\\}$ to generate more robust teacher outputs.

The data-level teacher’s algorithm is described in Algorithm 2.

####  3.2.3. Training-level teachers

Model- and data-level teachers use ensemble-based methods to fuse multi-source
outputs, which can be referred to as post-training strategies. Training-level
methods aim to directly learn a robust teacher module without a post-training
ensemble. The key idea is based on two assumptions:

  1. (1)

confident, soft labels should be consistent with the latent real user
preference; and

  2. (2)

confident, soft labels from two models should be consistent.

Here, we introduce the main teacher model $g_{1}$ and a side teacher model
$g_{2}$. We then describe how to directly train a robust $g_{1}$ with the help
of $g_{2}$.

As discussed before, the output of $g_{1}$ and $g_{2}$ should be consistent
with each other if they are expected to generate confident, soft labels.
Therefore, given an item sequence $\mathbf{s}_{u}$, we aim to minimize their
KL divergence as

(3)
$\begin{split}\textrm{KL}(P_{g_{2}}(\cdot\mid\boldsymbol{s}_{u})\|P_{g_{1}}(\cdot\mid\boldsymbol{s}_{u}))=\mathbb{E}_{j\sim
P_{g_{2}}}[\log(P_{g_{2}}(j\mid\boldsymbol{s}_{u}))-\log(P_{g_{1}}(j\mid\boldsymbol{s}_{u}))],\end{split}$

where $j$ is a random variable representing the ideal user-preferred item that
cannot be directly observed. What we can observe from the data is
$i_{|\boldsymbol{s}_{u}|+1}$, which contains noise and bias. For simplicity,
in the following description we will use $i$ to denote
$i_{|\boldsymbol{s}_{u}|+1}$. Moreover, $\boldsymbol{s}_{u}$ will also be
omitted occasionally and $P(\cdot\mid\boldsymbol{s}_{u})$ is abbreviated as
$P$ if necessary.

Algorithm 2 Data-level teachers

1:$\\{g_{1},g_{2},\ldots,g_{m}\\}$: teacher models; $\eta$: learning rate;
$\ell_{ce}(\cdot)$: loss for teacher models; $\theta(\cdot)$: parameters; $D$:
training dataset

2:randomly sample $p$ percent of $D$ for $m$ times as $D_{1},\ldots,D_{m}$

3:repeat

4: for all $\boldsymbol{s}_{u}\in D_{k}$ do $\triangleright$ $k=1,2,\ldots,m$

5:
$\theta(g_{k})\leftarrow\theta(g_{k})-\eta\cdot\nabla\ell_{ce}(\boldsymbol{s}_{u},g_{k},i_{|\boldsymbol{s}_{u}|+1})$

6: end for

7:until converged

8:for all $\boldsymbol{s}_{u}\in D$ do

9: $\mathbf{e}_{u}\leftarrow\sum{g_{k}}(\mathbf{s}_{u})/m$ $\triangleright$
ensemble of $g_{k}$

10:end for

11:return  $\mathbf{e}_{u}$

According to Bayes’ Theorem and the discussed assumption, we have

(4) $P_{g_{1}}(j\mid\boldsymbol{s}_{u})\sim
P(j\mid\boldsymbol{s}_{u})=\frac{P(i\mid\boldsymbol{s}_{u})P(j\mid
i,\boldsymbol{s}_{u})}{P(i\mid j,\boldsymbol{s}_{u})}.$

Substituting Eq. 4 into Eq. 3, we have

$\displaystyle\textrm{KL}(P_{g_{2}}\|P_{g_{1}})$
$\displaystyle{}\approx\mathbb{E}_{j\sim
P_{g_{2}}}\left[\log(P_{g_{2}}(j\mid\boldsymbol{s}_{u}))-\log\frac{P(i\mid\boldsymbol{s}_{u})P(j\mid
i,\boldsymbol{s}_{u})}{P(i\mid j,\boldsymbol{s}_{u})}\right]$ (5)
$\displaystyle{}=\textrm{KL}(P_{g_{2}}\|P)-\log(P(i\mid\boldsymbol{s}_{u}))+\mathbb{E}_{j\sim
P_{g_{2}}}[\log P(i\mid j,\boldsymbol{s}_{u})].$

If we rearrange Eq. 5, we have

(6)
$\begin{split}\textrm{KL}(P_{g_{2}}\|P)-\log(P(i\mid\boldsymbol{s}_{u}))\approx\textrm{KL}(P_{g_{2}}\|P_{g_{1}})-\mathbb{E}_{j\sim
P_{g_{2}}}[\log P(i\mid j,\boldsymbol{s}_{u})].\end{split}$

Due to the fact that $\textrm{KL}(P_{g_{2}}\|P)\geq 0$, the right-hand side of
Eq. 6 is an approximate upper bound of the negative logarithm likelihood. We
can regard $\mathbb{E}_{j\sim P_{g_{2}}}[\log P(i\mid j,\boldsymbol{s}_{u})]$
as a regularization term to adjust the agreement across $P_{g_{1}}$,
$P_{g_{2}}$ and $P$.

Through a similar derivation, we also have

(7)
$\begin{split}\textrm{KL}(P_{g_{1}}\|P)-\log(P(i\mid\boldsymbol{s}_{u}))\approx\textrm{KL}(P_{g_{1}}\|P_{g_{2}})-\mathbb{E}_{j\sim
P_{g_{1}}}[\log P(i\mid j,\boldsymbol{s}_{u})].\end{split}$

Combining the right-hand sides of both Eq. 6 and Eq. 7, we obtain the
following regularization term:

(8)
$\begin{split}\ell_{reg}=\;&\alpha\left\\{\textrm{KL}(P_{g_{2}}\|P_{g_{1}})-\mathbb{E}_{j\sim
P_{g_{2}}}[\log P(i\mid j,\boldsymbol{s}_{u})]\right\\}\\\
&+(1-\alpha)\left\\{\textrm{KL}(P_{g_{1}}\|P_{g_{2}})-\mathbb{E}_{j\sim
P_{g_{1}}}[\log P(i\mid j,\boldsymbol{s}_{u})]\right\\}.\end{split}$

Since our goal is to train the main teacher $g_{1}$ with the help of side
teacher $g_{2}$, the term $\mathbb{E}_{j\sim P_{g_{2}}}[P(i\mid
j,\boldsymbol{s}_{u})]$ has no contribution to the training of $g_{1}$, so we
omit it and change our regularization function to

(9)
$\begin{split}\ell_{1}=\alpha\textrm{KL}(P_{g_{2}}\|P_{g_{1}})+(1-\alpha)\textrm{KL}(P_{g_{1}}\|P_{g_{2}})-\mathbb{E}_{j\sim
P_{g_{1}}}[\log P(i\mid j,\boldsymbol{s}_{u})].\end{split}$

In practice, for simplicity, we assume that the observation of $i$ given the
real user-preferred item $j$ is conditionally independent with the item
sequence $\mathbf{s}_{u}$. This is a reasonable assumption since the
correlation between the observed item $i$ and the ideal item $j$ mainly
depends on the noisy signals. As a result, $P(i\mid j,\boldsymbol{s}_{u})$ can
be approximated through an auxiliary model $h$ as

(10) $h(i,j)\approx P(i|j)\approx P(i\mid j,\boldsymbol{s}_{u}).$

A concise solution to learn $h$ is to use matrix factorization and factorize
$h(i\mid j)$ as

(11) $[h]_{|\mathcal{I}|\cdot|\mathcal{I}|}=\mathcal{M}_{|\mathcal{I}|\cdot
d}\cdot\mathcal{N}_{d\cdot|\mathcal{I}|},$

where $d\ll\mathcal{I}$; $[h]$ can be viewed as a global noise matrix.
$\mathcal{M}$ and $\mathcal{N}$ are its low-rank factorization matrices.

To sum up, given an item sequence $\mathbf{s}_{u}$ and the observed next item
$i$ as the label, we have the training-level robust regularization

(12)
$\begin{split}\ell_{r}=\alpha\textrm{KL}(P_{g_{2}}\|P_{g_{1}})+(1-\alpha)\textrm{KL}(P_{g_{1}}\|P_{g_{2}})-\sum_{j\in\mathcal{I}}\log(h_{i,j})P_{g_{1}}(j\mid\mathbf{s}_{u}).\end{split}$

Finally, we combine the robust loss $\ell_{r}$ with the softmax cross-entropy
loss (i.e., $\ell_{ce}$) as the final loss function to construct the training-
level confident teacher module:

(13) $\ell_{t}=\ell_{r}+\ell_{ce}.$

We pretrain the side teacher model $g_{2}$ on a sub-sampled data split to
enhance the learning stability and further introduce data-level robustness.
The algorithmic process of training-level teachers is described in Algorithm
3.

Algorithm 3 Training-level teachers

1:$g_{1}$, $g_{2}$: two teacher models; $\eta$: learning rate;
$\ell_{ce}(\cdot)$: loss function for the side teacher $g_{2}$;
$\ell_{t}(\cdot)$: loss function for the main teacher $g_{1}$;
$\theta(\cdot)$: parameters; $D$: training dataset

2:randomly sample $p$ percent data $D^{\prime}$ from $D$.

3:repeat

4: for all $\boldsymbol{s}_{u}\in D^{\prime}$ do

5:
$\theta(g_{2})\leftarrow\theta(g_{2})-\eta\cdot\nabla\ell_{ce}(\boldsymbol{s}_{u},g_{2},i_{|\boldsymbol{s}_{u}|+1})$
$\triangleright$ pretrain $g_{2}$

6: end for

7:until converged

8:repeat

9: for all $\boldsymbol{s}_{u}\in D$ do

10:
$\theta(g_{1})\leftarrow\theta(g_{1})-\eta\cdot\nabla\ell_{t}(\boldsymbol{s}_{u},g_{1},i_{|\boldsymbol{s}_{u}|+1})$
$\triangleright$ train $g_{1}$

11: end for

12:until converged

13:for all $\boldsymbol{s}_{u}\in D$ do

14: $\mathbf{e}_{u}\leftarrow{g_{1}}(\mathbf{s}_{u})$

15:end for

16:return  $\mathbf{e}_{u}$

###  3.3. Learning of student recommenders

Given the input sequence $\mathbf{s}_{u}$ and dense logits $\mathbf{e}_{u}$
(see the output of Algorithm 1, 2, and 3) generated by the confident teacher
module, we define the soft labels for the student recommender $f$ as

(14)
$\mathbf{r}_{u}=\frac{1}{2}(\textrm{softmax}(\mathbf{e}_{u}/\mathcal{T})+\textrm{onehot}(i_{|\boldsymbol{s}_{u}|+1})),$

where $\mathcal{T}$ is a temperature smoothening the soft label distribution.
A larger $\mathcal{T}$ indicates smoother soft labels. When
$\mathcal{T}\rightarrow\infty$, the soft labels act as naive label smoothing.

Finally, the training loss for the target student recommender $f$ is defined
as

(15)
$\ell_{s}=(1-\beta)\ell_{\textrm{ce}}(\boldsymbol{s}_{u},f,i_{|\boldsymbol{s}_{u}|+1})+\beta\textrm{KL}(P_{f}(\cdot\mid\boldsymbol{s}_{u})\|\mathbf{r}_{u}).$

During inference, we use the student model $f$ to generate the list of
recommended items by selecting the top-$n$ items with the highest
classification logits.

###  3.4. Summary and remarks

We have proposed three strategies to learn a confident teacher module to
generate soft labels. All three methods leverage the collaboration of multiple
teachers but from different perspectives and in different stages of training.
The model-level and data-level strategies use collaboration after the training
of teachers, and the training of multiple teacher models is processed
individually. Averaging the outputs is an effective way of reducing errors and
making more robust soft labels. In contrast, the training-level strategy uses
the collaboration between the main teacher model and a side teacher model
during the training process. The main teacher model is directly trained to be
robust without post-training infusion. In the training-level strategy, we use
a pre-trained $g_{2}$ instead of training both models together because a pre-
trained model can dramatically accelerate the model collaboration. Note that
we use the sub-sampled data split during the pre-training of the side teacher
model $g_{2}$. This design can help the main teacher model $g_{1}$ to benefit
from the data-level randomness to generate more robust outputs.

##  4\. Experiments

In this section, we describe our experimental setup for assessing the
effectiveness of our proposed training method. We focus on the following
research questions:

  1. (RQ1)

What is the overall recommendation performance of the proposed CSRec learning
framework?

  2. (RQ2)

Does CSRec help to generate more robust sequential recommendations from
implicit user feedback?

  3. (RQ3)

How does the design of the teacher module affect the student performance?

###  4.1. Experimental settings

####  4.1.1. Datasets

We conduct experiments on four datasets:  (i)
Last.FM,111https://grouplens.org/datasets/hetrec-2011/ (ii)
Yelp,222https://www.yelp.com/dataset (iii) Amazon Electronics, and  (iv)
Amazon Movies and TV.333http://jmcauley.ucsd.edu/data/amazon/ Table 1 shows
the dataset statistics. We remove users and items with less than five
interactions for all datasets. Since we consider sequential recommendation
tasks, we split each user’s interactions into sequences with fixed lengths. If
the session is too short, we add padding tokens. If the session is longer, we
cut it into several sub-sessions.

####  4.1.2. Evaluation protocols

To evaluate the recommendation performance, we adopt the leave-one-out
evaluation procedure. The last item in a sequence is left as the test sample,
while the one but last item is used for validation. The remaining interactions
are used as the training set. We use the full item set as the candidate set
when performing the ranking. For evaluation, we use two ranking-based metrics:
(i) Recalland  (ii) Normalized Discounted Cumulative Gain(NDCG).  Recall@$n$
measures whether the ground-truth item occurs in the top-$n$ positions of the
list of recommendations. NDCG is a weighted version that attaches higher
importance to top positions.

To evaluate the robustness of the recommenders (i.e., whether the
recommendation can lead to higher user ratings given the noisy implicit
feedback), we also introduce filtered versions of these metrics on the two
Amazon datasets (since those contain rating information). The original Recall
is defined as
$\textrm{Recall}@n=\frac{1}{|\mathcal{U}|}\sum_{u\in\mathcal{U}}\mathbbm{1}(rank_{u}\leq
n)$, where $\textrm{rank}_{u}$ denotes the rank of the ground-truth item and
$\mathbbm{1}(\cdot)$ is the indicator function. For the _filtered version_ ,
which we denote as $\textrm{Recall}^{+}$, we have

(16)
$\textrm{Recall}^{+}@n=\frac{1}{\sum_{u\in\mathcal{U}}\mathbbm{1}(r_{u}\geq\delta)}\sum_{u\in\mathcal{U}}\mathbbm{1}(r_{u}\geq\delta\wedge
rank_{u}\leq n),$

where $r_{u}$ is the rating of the ground-truth item. $\delta$ is a threshold
value set to 4 (ratings range from 0 to 5). Such a filtered metric measures
whether the recommended items can lead to real positive user preferences.
Similarly, we have a filtered version NDCG+ of the NDCG metric. Note that
ratings are only used in the evaluation stage to verify the robustness. For
training, we only use binary implicit user feedback (i.e., items that a user
interacted with are labeled as positive, and the others are missing
interactions).

Table 1. Statistics of datasets. Dataset | #users | #items | #interactions | length
---|---|---|---|---
Last.FM | 1,090 | 3,646 | 52,551 | 20
Yelp | 30,431 | 20,033 | 316,354 | 10
Electronics | 83,427 | 29,351 | 684,449 | 10
Movies & TV | 47,966 | 21,035 | 625,813 | 10

####  4.1.3. Baselines

To assess the effectiveness of training recommenders with CSRec, we use the
following models as the student model described in Section 3:

  * •

GRU4Rec (Tan et al., 2016a) uses a GRU to model sequential user behavior, and
we use an improved version by Tan et al. (2016b).

  * •

NextItNet (Yuan et al., 2019) is a simple yet effective CNN-based model that
is capable of learning both short- and long-range dependencies.

  * •

SASRec (Kang and McAuley, 2018) is based on the transformer decoder (Vaswani
et al., 2017), which uses multi-head self-attention to capture user
preference.

  * •

NARM (Li et al., 2017) uses an attention mechanism to capture the intention of
users; then, it computes the recommendation score with a bi-linear matching
based on the latent representation.

Each student recommendation model is trained with the following methods:

  * •

Base denotes the standard training framework by optimizing the cross-entropy
between the output and the sparse one-hot label;

  * •

SoftRec denotes the item-based method proposed by Cheng et al. (2021), which
uses a popularity-based teacher model to generate soft labels;

  * •

CSRec-M is our proposed framework that uses the model-level teacher module to
produce the confident, soft labels;

  * •

CSRec-D is our proposed framework that uses the data-level teachers to provide
confident, soft labels; and

  * •

CSRec-T is our proposed framework that uses the training-level teachers to
generate confident, soft labels.

####  4.1.4. Implementation details

We use the implementations from Recbole (Zhao et al.,
2020),444https://github.com/RUCAIBox/RecBole for the four baseline models
listed above. The embedding size of all models, including $d$ in the training-
level method, is fixed to $64$ for a fair comparison. Both $\alpha$ and
$\beta$ in Eq. 12 and Eq. 15 are chosen in $\\{0.25,0.5,0.75\\}$, and the
temperature $\mathcal{T}$ in Eq. 15 is chosen in $\\{1,3,6,9\\}$. For CSRec-M
and CSRec-D, the number of teachers (i.e., $m$) is set to 2. For CSRec-D, the
sub-sampling ratio $p$ is set to 0.8. For GRU4Rec, the number of layers is set
to $2$ on all datasets. The dropout rate is $0.5$. For NextItNet, the kernel
size is set to 3, the block number is $5$ on four datasets, and the dilations
are set to $1$ after tuning. For SASRec, the number of layers is set to $2$,
the head number is $2$, and the dropout rate is $0.3$. For NARM, the hidden
size is $128$, and the number of layers is 1. We use Adam (Kingma and Ba,
2015) as the training optimizer, setting the learning rate to $0.001$. For
CSRec, we use the same model architecture for the teacher models $g$ as for
the student models $f$ for a fair comparison.555The code and data used are
available at https://github.com/Furyton/CSRec/.

Table 2. Comparison of the top-$n$ recommendation performance of different models ($n=10$) on four datasets. RC is short for Recall@10. NG is short for NDCG@10. Boldface denotes the highest score. $**$ and $*$ indicate significant improvements over the corresponding SoftRec baseline ($p<0.05$ and $p<0.1$, respectively). |  | GRU4Rec | NextItNet | NARM | SASRec
---|---|---|---|---|---
Dataset |  Method | RC(%) | NG(%) | RC(%) | NG(%) | RC(%) | NG(%) | RC(%) | NG(%)
Last.FM |  Base | 16.683 | 10.081 | 15.456 | 11.564 | 20.260 | 13.204 | 20.350 | 11.432
SoftRec | 17.427 | 10.624 | 15.473 | 11.826 | 20.486 | 12.826 | 20.746 | 11.951
CSRec-M |  18.165* | 10.678 | 16.466* | 12.472** | 20.819* | 13.050 | 20.874 | 11.976
CSRec-D | 18.607* | 10.992* |  16.201* | 12.055 |  20.739* | 12.960 | 21.131* | 12.256*
CSRec-T |  18.180** |  10.764** | 15.681 | 12.007 | 20.697 | 12.875 | 21.047 | 12.009
Yelp |  Base | 5.812 | 3.512 | 8.077 | 5.742 | 8.587 | 5.641 | 8.523 | 5.329
SoftRec | 6.108 | 3.584 | 8.303 | 5.923 | 8.108 | 5.024 | 9.459 | 5.882
CSRec-M |  6.405** |  3.822** |  8.587* |  6.175* | 8.900** | 5.778** | 9.485* | 5.902*
CSRec-D | 6.237 | 3.646 | 8.501 | 6.101 |  8.723** |  5.489** | 9.484 |  5.898**
CSRec-T | 6.526** | 3.894** | 8.589* | 6.177* |  8.700** |  5.530** | 9.421 | 5.888
Electronics |  Base | 5.178 | 2.855 | 4.900 | 3.217 | 5.211 | 3.051 | 6.932 | 4.000
SoftRec | 5.431 | 3.046 | 5.204 | 3.429 | 5.490 | 3.197 | 6.963 | 4.081
CSRec-M |  5.545** |  3.132** | 5.666** | 3.789** |  5.787** |  3.432** | 6.737 | 3.944
CSRec-D |  5.515** |  3.104** |  5.308* |  3.507** |  5.846** |  3.486** |  6.729* | 3.923
CSRec-T | 5.595* | 3.168** |  5.356** |  3.583** | 5.905** | 3.523** | 7.001* | 4.107*
Movies & TV |  Base | 8.413 | 4.772 | 7.377 | 4.448 | 9.383 | 5.514 | 11.191 | 6.716
SoftRec | 9.541 | 5.365 | 8.228 | 4.976 | 9.402 | 5.451 | 10.908 | 6.547
CSRec-M | 9.638 |  5.521* | 8.744** | 5.302** | 9.999** | 5.880** | 11.198** |  6.701**
CSRec-D | 9.458 |  5.426** | 8.367 | 5.029 |  9.754** |  5.718** |  11.195* | 6.717*
CSRec-T | 9.704** | 5.522** |  8.461** |  5.116** |  9.876** |  5.777** |  11.195* | 6.703

##  5\. Results and analysis

###  5.1. Overall performance comparison (RQ1)

Table 2 compares the recommendation performance of all models under different
training regimes. Training with the three proposed CSRec methods (i.e.,
CSRec-M, CSRec-D, and CSRec-T) consistently leads to improved recommendation
performance on four datasets and four student models, especially the model-
level and the training-level methods, which achieve significant improvements
over the SoftRec method in most cases.

If we break down the results by dataset, we see that training with CSRec-D
sometimes leads to higher recommendation performance than training with the
other two proposed methods on the Last.FM dataset. On the other three
datasets, training with either CSRec-M or CSRec-T results in the highest
scoring recommendation performance in most cases. The reason could be that the
interactions in Last.FM are much denser than in the other three datasets. As
the data-level teachers drop parts of the samples, more variations and
randomness are produced so that CSRec-D can capture a more robust signal from
the data. Training with CSRec-T consistently leads to good recommendation
performance on the Yelp and Electronics datasets, which are both relatively
sparse. We thus infer that the CSRec-D is suitable for training on dense
datasets while CSRec-T fits training on sparse datasets. In addition, CSRec-M
can be used in more general cases.

If we break down the results by student model, we see that RNN-based and CNN-
based models, i.e., GRU4Rec and NextItNet, enjoy the most notable improvements
when being trained with CSRec, while the SASRec model equipped with a self-
attention mechanism has a relatively small improvement. Recent research
(Hendrycks et al., 2020; Xu et al., 2021) has shown that pre-trained
transformers are far more effective at handling noisy examples than CNN or
RNN-based models. Similar conclusions have been found concerning computer
vision (Bhojanapalli et al., 2021). However, in most cases, training with the
proposed CSRec still leads to significant improvements in the performance of
SASRec.

In summary, the proposed learning framework CSRec helps to effectively and
significantly improve the performance of diverse recommenders compared with
the normal training regime and SoftRec. We can choose different teacher
modules based on different dataset characteristics to achieve the best
performance.

###  5.2. Robustness performance (RQ2)

####  5.2.1. Evaluation on the real positive user preference

We use the filtered evaluation metrics on the two Amazon datasets to determine
whether training with CSRec yields recommenders that lead to real positive
user preferences (i.e., higher ratings). The results are shown in Table 3. The
results demonstrate that our proposed training methods outperform the base
training and SoftRec on the two Amazon datasets. Most CSRec results achieve
significant improvements, indicating that our methods can effectively capture
real user preferences even though the training dataset contains noisy training
instances (i.e., items a user interacted with but with low ratings). Moreover,
the high performance resulting from training with CSRec-M and CSRec-T also
shows the generalization capability of our proposed methods.

####  5.2.2. Effect on reducing the popularity bias

We examine the popularity bias of the student module in Fig 3. The
recommendation performance is improved on the tail items with a small cost of
decreasing on the most popular ones. On the Yelp dataset, we even have large
improvements for both popular-type and niche-type users. This indicates that
our training methods can alleviate popularity bias and focus more on niche
items, which is beneficial for the long-term profits of service providers.

For a deeper analysis, popularity bias is not always harmful for the
recommender according to Zhao et al. (2021), popular items sometimes do
reflect the general user interests. A single teacher model trained separately
(e.g., SoftRec (Cheng et al., 2021)) can contain both harmful biases and
beneficial general interests, and thus enhance the popularity bias. However,
the proposed CSRec can mitigate harmful bias through the collaboration of
multiple teacher modules, and it keeps the beneficial general interests. The
reason is that the beneficial general user interests should be consistent
among all the models and thus can be reserved during model collaboration.

####  5.2.3. Effect of sequence length and data sparsity

We also study how the sequence length of the user-item interactions affects
the methods in Figure 4(a). Users with more interaction histories will not
necessarily get a more satisfied recommendation according to (Ji et al.,
2022). However, training with our proposed methods leads to increased
resilience to the length of interaction history. This observation indicates
that the proposed CSRec can consistently improve the recommendation
performance given different lengths of the interaction sequences.

Sparsity is often a concern in the recommendation literature, and we conduct
an experiment, in Figure 4(b), to show that training with our methods is
relatively robust to different levels of sparsity. Training with CSRec-M
outperforms the others settings across all the different levels of sparsity.
Even though do not preserve their performance at $\text{sparsity}=97.3\%$, our
other two training methods, i.e., CSRec-D and CSRec-T, still show more
promising results than the Base model and SoftRec on other sparsity settings.

Table 3. Comparison of the top-$n$ recommendation performance of different models ($n=10$) on two rating datasets using the filtered metrics described in Section 4.1.2. RC+ is short for Recall+@10. NG+ is short for NDCG+@10. Boldface denotes the highest score. $**$ and $*$ denote significant improvements over the corresponding SoftRec baseline ($p<0.05$ and $p<0.1$, respectively). |  | GRU4Rec | NextItNet | NARM | SASRec
---|---|---|---|---|---
Dataset | Method |  RC+(%) |  NG+(%) |  RC+(%) |  NG+(%) |  RC+(%) |  NG+(%) |  RC+(%) |  NG+(%)
Electronics | Base | 5.577 | 3.074 | 5.111 | 3.344 | 5.575 | 3.262 | 7.394 | 4.279
SoftRec | 5.812 | 3.267 | 5.484 | 3.608 | 5.902 | 3.435 | 7.434 | 4.359
CSRec-M |  5.937** |  3.358** | 5.946** | 3.968** |  6.195** |  3.673** | 7.235 | 4.239
CSRec-D |  5.901* |  3.319** | 5.555 |  3.665** |  6.250** |  3.720** | 7.207 | 4.209
CSRec-T | 5.975** | 3.381* |  5.635** |  3.752** | 6.329** | 3.769** | 7.453 | 4.388
Movies and TV | Base | 8.603 | 4.927 | 7.554 | 4.588 | 9.712 | 5.794 | 11.608 | 7.071
SoftRec | 9.818 | 5.599 | 8.388 | 5.120 | 9.727 | 5.705 | 11.296 | 6.874
CSRec-M |  9.925** |  5.743** | 8.992** | 5.503** | 10.361** | 6.190** |  11.641** |  7.076**
CSRec-D |  9.738* |  5.656* | 8.558 | 5.190 |  10.079** |  6.015** | 11.641* | 7.087*
CSRec-T | 9.958** | 5.749** |  8.643** |  5.265** |  10.175** |  6.051** | 11.604 | 7.045

(a) Yelp (b) Electronics

Figure 3. Performance of SoftRec and the three proposed training methods,
i.e., CSRec-M, CSRec-D, and CSRec-T, on different groups of users. Similar
settings to Fig. 1 are adopted. We choose GRU4Rec (Tan et al., 2016a) as the
base model on the (a) Yelp and (b) Electronics dataset.

(a) Effect of sequence length. (b) Effect of dataset sparsity.

Figure 4. Performance of Base model and the three proposed training methods,
i.e., CSRec-M, CSRec-D, and CSRec-T, on Last.FM dataset with (a) different
lengths, and (b) different levels of sparisty. We control the sparsity by
randomly removing different proportions of users. The sparsity is 96.1%,
96.7%, 97.1% and 97.3% respectively. We choose GRU4Rec (Tan et al., 2016a) as
the base model.

To conclude, our proposed training methods not only lead to improved
performance in standard evaluation scenarios but also to better outcomes on
the positive user preference evaluation. The teacher module of CSRec can
effectively help the student recommender generate recommendations that lead to
real positive user preferences given corrupted training data and thus improve
the robustness of the student module. Besides, the proposed CSRec also shows
promising improvements in alleviating the popularity bias and provides robust
performance in different settings of sequence lengths and sparsity levels.

(a) Electronics (b) Movies and TV

CSRec-M

(c) Electronics (d) Movies and TV

CSRec-D

Figure 5. Effect of the number of teacher models using NARM as the student
model.

###  5.3. Ablation study

In this section, we study how the design of the teacher module affects the
performance of students. Since both CSRec-M and CSRec-D use an ensemble of
multiple teachers, we first look into the effect of the number of teachers
(i.e., $m$). We report the results using NARM as the student model on two
Amazon datasets, as shown in Figure 5. Results for other student models show
similar trends. From the results, we can see that the performance is improved
when the number of teachers is increased from 1 to 2, which means the student
can benefit from multiple teachers. However, further increasing the number of
teachers introduces little improvement, which means that more teachers are not
necessarily giving us better soft labels and recommendation results.

For CSRec-D, we also investigate the effect of the sub-sampling ratio. The
result of using NARM as the student model is shown in Figure 6. A large
sampling ratio (i.e., $p>0.8$) will not always give us better students. Larger
sub-datasets have more overlapping samples, making the teacher modules more
similar to each other and sharing the same data-level bias and noise. However,
a sampling ratio that is too small introduces too much randomness and also
downgrades the performance. $p=0.8$ is a safe and robust choice.

Finally, for CSRec-T, we investigate the effect of the robust training loss
$\ell_{r}$ (Eq. 12). Since $\ell_{r}$ is similar to the regular distillation
loss except for the term
$-\sum_{j\in\mathcal{I}}\log(h_{i,j})P_{g_{1}}(j\mid\mathbf{s}_{u})$, we thus
check the effectiveness of this expectation term and report the results in
Figure 7, using NARM as the student model. We see that the expectation term
significantly improves the student’s performance, which demonstrates the
effectiveness of our proposed methods.

##  6\. Conclusions

We have proposed a new learning framework, CSRec, to train a robust sequential
recommender from noisy, implicit feedback. The key idea is to introduce
confident, soft labels to provide robust guidance in the learning process. We
have presented three teacher modules, i.e., model-level, data-level, and
training-level, for generating high-quality and confident, soft labels from
noisy user-item interactions. We have conducted extensive experiments to
assess the effectiveness of the proposed learning framework.

Experimental results on four datasets and diverse student models demonstrate
that training with the proposed learning framework CSRec helps to improve the
recommendation performance. It can be applied to various deep-learning-based
sequential recommendation models.

The broader implications of our work are that we have demonstrated the
potential of soft labels for training sequential recommender systems, which we
believe should further investigated and developed as a generic framework for
producing better soft label guidance for a broader set of recommendation
tasks.

(a) Electronics (b) Movies and TV

Figure 6. Effect of the sub-sampling ratio $p$ in CSRec-D, using NARM as the
student model.

(a) Electronics (b) Movies and TV

Figure 7. Effect of the term
$-\sum_{j\in\mathcal{I}}\log(h_{i,j})P_{g_{1}}(j\mid\mathbf{s}_{u})$ in the
robust loss $\ell_{r}$ of CSRec-T. Here, “with” and “without” denote whether
the term is used or not. The student model used is NARM.

Limitations of our work concern the inefficiency of the whole training
framework pipeline due to the required multiple well-trained teacher models.
The lack of exploration of different ensemble methods for further analysis and
comparison is also one of the limitations.

As to future work, we see a number of promising directions. First, more
intuitive and general teacher modules could be designed beyond the ones we
considered in this paper, perhaps targeting specific types of noise or bias
present in logged interaction data. Second, we aim to develop a more in-depth
analysis to see how soft labels intrinsically affect the student model
learning.

###### Acknowledgements.

This research was funded by the Natural Science Foundation of China (62272274,
61972234, 62072279, 62102234, 62202271), Meituan, the Natural Science
Foundation of Shandong Province (ZR2022QF004), the Key Scientific and
Technological Innovation Program of Shandong Province (2019JZZY010129),
Shandong University multidisciplinary research and innovation team of young
scholars (No. 2020QNQT017), the Tencent WeChat Rhino-Bird Focused Research
Program (JR-WXG2021411), the Fundamental Research Funds of Shandong
University, the Hybrid Intelligence Center, a 10-year program funded by the
Dutch Ministry of Education, Culture and Science through the Netherlands
Organization for Scientific Research, https://hybrid-intelligence-centre.nl,
project LESSEN with project number NWA.1389.20.183 of the research program NWA
ORC 2020/21, which is (partly) financed by the Dutch Research Council (NWO),
and the FINDHR (Fairness and Intersectional Non-Discrimination in Human
Recommendation) project that received funding from the European Union’s
Horizon Europe research and innovation program under grant agreement No
101070212. All content represents the opinion of the authors, which is not
necessarily shared or endorsed by their respective employers and/or sponsors.

## References

  * (1)
  * Bhojanapalli et al. (2021) Srinadh Bhojanapalli, Ayan Chakrabarti, Daniel Glasner, Daliang Li, Thomas Unterthiner, and Andreas Veit. 2021.  Understanding Robustness of Transformers for Image Classification. In _2021 IEEE/CVF International Conference on Computer Vision (ICCV)_. 10211–10221.
  * Caselles-Dupré et al. (2018) Hugo Caselles-Dupré, Florian Lesaint, and Jimena Royo-Letelier. 2018.  Word2vec Applied to Recommendation: Hyperparameters Matter. In _Proceedings of the 12th ACM Conference on Recommender Systems, RecSys 2018, Vancouver, BC, Canada, October 2-7, 2018_. ACM, 352–356.
  * Chang et al. (2021) Jianxin Chang, Chen Gao, Y. Zheng, Yiqun Hui, Yanan Niu, Yang Song, Depeng Jin, and Yong Li. 2021.  Sequential Recommendation with Graph Neural Networks. In _Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval_. 378–387.
  * Chen et al. (2022b) Chong Chen, Weizhi Ma, Min Zhang, Chenyang Wang, Yiqun Liu, and Shaoping Ma. 2022b.  Revisiting Negative Sampling vs. Non-Sampling in Implicit Recommendation.  _ACM Trans. Inf. Syst._ (2022), Article No. 12.  Issue 1.
  * Chen et al. (2022a) Gang Chen, Jiawei Chen, Fuli Feng, Sheng Zhou, and Xiangnan He. 2022a.  Unbiased Knowledge Distillation for Recommendation.  _ArXiv_ abs/2211.14729 (2022).
  * Chen et al. (2020) Jiawei Chen, Hande Dong, Xiang Wang, Fuli Feng, Meng Wang, and Xiangnan He. 2020.  Bias and Debias in Recommender System: A Survey and Future Directions.  _ArXiv_ abs/2010.03240 (2020).
  * Chen et al. (2021) Jiawei Chen, Xiang Wang, Fuli Feng, and Xiangnan He. 2021.  Bias Issues and Solutions in Recommender System: Tutorial on the RecSys 2021. In _Fifteenth ACM Conference on Recommender Systems_. 825–827.
  * Cheng et al. (2021) Mingyue Cheng, Fajie Yuan, Qi Liu, Shenyang Ge, Zhi Li, Runlong Yu, Defu Lian, Senchao Yuan, and Enhong Chen. 2021.  Learning Recommender Systems with Implicit Feedback via Soft Target Enhancement. In _Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval_. ACM, New York, NY, USA, 575–584.
  * Dodge et al. (2020) Jesse Dodge, Gabriel Ilharco, Roy Schwartz, Ali Farhadi, Hannaneh Hajishirzi, and Noah A. Smith. 2020.  Fine-Tuning Pretrained Language Models: Weight Initializations, Data Orders, and Early Stopping.  _ArXiv_ abs/2002.06305 (2020).
  * Du et al. (2020) Shangchen Du, Shan You, Xiaojie Li, Jianlong Wu, Fei Wang, Chen Qian, and Changshui Zhang. 2020.  Agree to Disagree: Adaptive Ensemble Knowledge Distillation in Gradient Space. In _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_. 12345–12355.
  * Gou et al. (2021) Jianping Gou, Baosheng Yu, Stephen J. Maybank, and Dacheng Tao. 2021.  Knowledge Distillation: A Survey.  _Int. J. Comput. Vision_ 129, 6 (2021), 1789–1819.
  * He and McAuley (2016) Ruining He and Julian McAuley. 2016.  Fusing Similarity Models with Markov Chains for Sparse Sequential Recommendation. In _2016 IEEE 16th International Conference on Data Mining (ICDM)_. 191–200.
  * Hendrycks et al. (2020) Dan Hendrycks, Xiaoyuan Liu, Eric Wallace, Adam Dziedzic, Rishabh Krishnan, and Dawn Song. 2020.  Pretrained Transformers Improve Out-of-Distribution Robustness. In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_. ACL, 2744–2751.
  * Hidasi and Karatzoglou (2018) Balázs Hidasi and Alexandros Karatzoglou. 2018.  Recurrent Neural Networks with Top-k Gains for Session-based Recommendations. In _Proceedings of the 27th ACM International Conference on Information and Knowledge Management_. 843–852.
  * Hinton et al. (2015) Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. 2015.  Distilling the Knowledge in a Neural Network.  _arXiv preprint arXiv:1503.02531_ (2015).
  * Ji et al. (2022) Yitong Ji, Aixin Sun, Jie Zhang, and Chenliang Li. 2022.  Do Loyal Users Enjoy Better Recommendations? Understanding Recommender Accuracy from a Time Perspective. In _Proceedings of the 2022 ACM SIGIR International Conference on Theory of Information Retrieval_ (Madrid, Spain) _(ICTIR ’22)_. Association for Computing Machinery, New York, NY, USA, 92–97.
  * Kang and McAuley (2018) Wang-Cheng Kang and Julian McAuley. 2018.  Self-Attentive Sequential Recommendation. In _2018 IEEE International Conference on Data Mining (ICDM)_. 197–206.
  * Kingma and Ba (2015) Diederik P. Kingma and Jimmy Ba. 2015.  Adam: A Method for Stochastic Optimization. In _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_.
  * Li et al. (2017) Jing Li, Pengjie Ren, Zhumin Chen, Zhaochun Ren, Tao Lian, and Jun Ma. 2017.  Neural Attentive Session-based Recommendation. In _Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, CIKM 2017, Singapore, November 06 - 10, 2017_. ACM, 1419–1428.
  * Liu et al. (2020a) Dugang Liu, Pengxiang Cheng, Zhenhua Dong, Xiuqiang He, Weike Pan, and Zhong Ming. 2020a.  A General Knowledge Distillation Framework for Counterfactual Recommendation via Uniform Data. In _Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval, SIGIR 2020, Virtual Event, China, July 25-30, 2020_. ACM, 831–840.
  * Liu et al. (2020b) Yuang Liu, Wei Zhang, and Jun Wang. 2020b.  Adaptive Multi-teacher Multi-level Knowledge Distillation.  _Neurocomputing_ 415 (2020), 106–113.
  * Luo et al. (2020) Anjing Luo, Pengpeng Zhao, Yanchi Liu, Fuzhen Zhuang, Deqing Wang, Jiajie Xu, Junhua Fang, and Victor S. Sheng. 2020.  Collaborative Self-Attention Network for Session-based Recommendation. In _Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020_. ijcai.org, 2591–2597.
  * Nelaturi and Devi (2019) Naresh Nelaturi and Golagani Devi. 2019.  A Product Recommendation Model Based on Recurrent Neural Network.  _Journal Européen des Systèmes Automatisés_ 52, 5 (2019), 501–507.
  * Rendle et al. (2009) Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, and Lars Schmidt-Thieme. 2009.  BPR: Bayesian Personalized Ranking from Implicit Feedback.  _arXiv preprint arXiv:1205.2618_ (2009).
  * Song et al. (2022) Hwanjun Song, Minseok Kim, Dongmin Park, and Jae-Gil Lee. 2022.  Learning from Noisy Labels with Deep Neural Networks: A Survey.  _IEEE Transactions on Neural Networks and Learning Systems_ 34 (2022), 8135–8153.  Issue 11.
  * Sun et al. (2019) Fei Sun, Jun Liu, Jian Wu, Changhua Pei, Xiao Lin, Wenwu Ou, and Peng Jiang. 2019.  BERT4Rec: Sequential Recommendation with Bidirectional Encoder Representations from Transformer. In _Proceedings of the 28th ACM International Conference on Information and Knowledge Management, CIKM 2019, Beijing, China, November 3-7, 2019_. ACM, 1441–1450.
  * Takama et al. (2021) Yasufumi Takama, Jing-cheng Zhang, and Hiroki Shibata. 2021.  Context-aware Music Recommender System Based on Implicit Feedback.  _Transactions of the Japanese Society for Artificial Intelligence_ 36, 1 (2021), WI2–D_1–10.
  * Tan et al. (2016a) Yong Kiam Tan, Xinxing Xu, and Yong Liu. 2016a.  Improved Recurrent Neural Networks for Session-based Recommendations. In _Proceedings of the 1st Workshop on Deep Learning for Recommender Systems_ _(DLRS 2016)_. ACM, New York, NY, USA, 17–22.
  * Tan et al. (2016b) Yong Kiam Tan, Xinxing Xu, and Yong Liu. 2016b.  Improved Recurrent Neural Networks for Session-based Recommendations. In _Proceedings of the 1st Workshop on Deep Learning for Recommender Systems_ (Boston, MA, USA) _(DLRS 2016)_. ACM, New York, NY, USA, 17–22.
  * Tang and Wang (2018) Jiaxi Tang and Ke Wang. 2018.  Personalized Top-N Sequential Recommendation via Convolutional Sequence Embedding. In _Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, WSDM 2018, Marina Del Rey, CA, USA, February 5-9, 2018_. ACM, 565–573.
  * Vardasbi et al. (2020) Ali Vardasbi, Harrie Oosterhuis, and Maarten de Rijke. 2020.  When Inverse Propensity Scoring does not Work: Affine Corrections for Unbiased Learning to Rank. In _CIKM 2020: 29th ACM International Conference on Information and Knowledge Management_. ACM, 1475–1484.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017.  Attention is All you Need. In _Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA_. 5998–6008.
  * Wang et al. (2018) Pengfei Wang, Jiansheng Chen, and Shaozhang Niu. 2018.  CFSH: Factorizing Sequential and Historical Purchase Data for Basket Recommendation.  _PLoS One_ 13, 10 (2018), e0203191.
  * Wen and Zhang (2020) Nuan Wen and Fang Zhang. 2020.  Extended Factorization Machines for Sequential Recommendation.  _IEEE Access_ 8 (2020), 41342–41350.
  * Xin et al. (2018) Xin Xin, Fajie Yuan, Xiangnan He, and Joemon M. Jose. 2018.  Batch IS NOT Heavy: Learning Word Representations From All Samples. In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_. ACL, 1853–1862.
  * Xu et al. (2021) Keyang Xu, Tongzheng Ren, Shikun Zhang, Yihao Feng, and Caiming Xiong. 2021.  Unsupervised Out-of-Domain Detection via Pre-trained Transformers. In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_. 1052–1061.
  * Yang et al. (2020) Yeongwook Yang, Hong Jun Jang, and Byoungwook Kim. 2020.  A Hybrid Recommender System for Sequential Recommendation: Combining Similarity Models With Markov Chains.  _IEEE Access_ 8 (2020), 190136–190146.
  * You et al. (2017) Shan You, Chang Xu, Chao Xu, and Dacheng Tao. 2017.  Learning from Multiple Teacher Networks. In _Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_. 1285–1294.
  * Yuan et al. (2019) Fajie Yuan, Alexandros Karatzoglou, Ioannis Arapakis, Joemon M. Jose, and Xiangnan He. 2019.  A Simple Convolutional Generative Network for Next Item Recommendation. In _Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, WSDM 2019, Melbourne, VIC, Australia, February 11-15, 2019_. ACM, 582–590.
  * Yun and Wong (2020) Stone Yun and Alexander Wong. 2020.  Where Should We Begin? A Low-Level Exploration of Weight Initialization Impact on Quantized Behaviour of Deep Neural Networks.  _arXiv preprint arXiv:2011.14578_ (2020).
  * Zhang et al. (2018) Ying Zhang, Tao Xiang, Timothy M. Hospedales, and Huchuan Lu. 2018.  Deep Mutual Learning.  _2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition_ (2018), 4320–4328.
  * Zhao et al. (2020) Wayne Xin Zhao, Shanlei Mu, Yupeng Hou, Zihan Lin, Yushuo Chen, Xingyu Pan, Kaiyuan Li, Yujie Lu, Hui Wang, Changxin Tian, Yingqian Min, Zhichao Feng, Xinyan Fan, Xu Chen, Pengfei Wang, Wendi Ji, Yaliang Li, Xiaoling Wang, and Ji-Rong Wen. 2020.  RecBole: Towards a Unified, Comprehensive and Efficient Framework for Recommendation Algorithms.  _arXiv preprint arXiv:2011.01731_ (2020).
  * Zhao et al. (2021) Zihao Zhao, Jiawei Chen, Sheng Zhou, Xiangnan He, Xuezhi Cao, Fuzheng Zhang, and Wei Wu. 2021.  Popularity Bias Is Not Always Evil: Disentangling Benign and Harmful Bias for Recommendation.  _CoRR_ abs/2109.07946 (2021).  arXiv:2109.07946
  * Zhao et al. (2019) Zhe Zhao, Lichan Hong, Li Wei, Jilin Chen, Aniruddh Nath, Shawn Andrews, Aditee Kumthekar, Maheswaran Sathiamoorthy, Xinyang Yi, and Ed H. Chi. 2019.  Recommending What Video to Watch Next: A Multitask Ranking System. In _Proceedings of the 13th ACM Conference on Recommender Systems, RecSys 2019, Copenhagen, Denmark, September 16-20, 2019_. ACM, 43–51.
  * Zhou et al. (2021) Xiong Zhou, Xianming Liu, Chenyang Wang, Deming Zhai, Junjun Jiang, and Xiangyang Ji. 2021.  Learning with Noisy Labels via Sparse Regularization.  _2021 IEEE/CVF International Conference on Computer Vision (ICCV)_ (2021), 72–81.
  * Zhu et al. (2018) Jinghua Zhu, Xu Guo, and Shengchao Ma. 2018.  Attentive Neural Network Recommendation for E-Commerce Based on Various Implicit Feedback. In _2018 IEEE 9th International Conference on Software Engineering and Service Science (ICSESS)_. 889–892.


# Shapley-Based Core-Selecting Payment Rules

Vitor Bosshard, Department of Informatics, University of Zurich
Sven Seuken, Department of Informatics, University of Zurich and ETH AI Center
<EMAIL_ADDRESS>
(First version: July 2, 2021
This version: July 2, 2021)

###### Abstract

In this research note, we lay some groundwork for analyzing the manipulability
of core-selecting payment rules in combinatorial auctions. In particular, we
focus on payment rules based on the bidders’ Shapley values. We define a
sensitivity metric, and provide analytical results for this metric in LLG, for
six different payment vectors used as reference points for minimum-revenue
core-selecting payment rules. We furthermore show how this sensitivity affects
the derivative of the resulting payment rules.

##  1 Introduction

Combinatorial auctions (CAs) are used in settings where heterogeneous,
indivisible goods are auctioned off to multiple bidders, allowing them to
express non-linearities in their valuations of bundles of goods. The
strategyproof VCG mechanism has many undesirable properties in this setting
[Ausubel and Milgrom, 2006], so finding a CA payment rule that leads to good
auction outcomes is an open problem. Rules that are not strategyproof are most
often used in practice, but predicting the equilibria they produce is not
straightforward [Bosshard et al., 2020]. If we could quantify how manipulable
different rules are, this would enable us to make proper tradeoffs between
manipulability, revenue, and other desiderata, and also propose new rules with
better properties along those dimensions. We suspect that the partial
derivatives of a payment rule are good indicators of manipulability and can
thus be used to estimate the auction’s equilibrium outcomes, a link we aim to
establish more precisely in future work.

In this research note, we focus on _reference point rules_ [Bünz et al.,
2018], a class of payment rules that is built by choosing a reference point in
the space of possible payments, and then projecting onto the _minimum revenue
core_ from there to derive the final payments. We define a _sensitivity_ of
each reference point, and show that this metric can be used to determine the
derivative of the corresponding reference point rule in the LLG domain. We
investigate several such rules, finding that a reference point based on
bidders’ Shapley values in the coalitional value game [Shapley, 1953] is less
sensitive than the widely used VCG-nearest rule. The implied low
manipulability of this rule is consistent with previous findings based on
numerical simulation [Bünz et al., 2018].

##  2 Preliminaries

###  2.1 Formal Model

A combinatorial auction (CA) is a mechanism used to sell a set
$M=\\{1,2,\ldots,m\\}$ of goods to a set $N=\\{1,2,\ldots,n\\}$ of bidders.
Each bidder $i$’s preferences over bundles are captured via the bidder’s
_valuation_ $v_{i}$. Specifically, for each bundle of goods $K\subseteq M$, we
let $v_{i}(K)\in\mathbb{R}_{\geq 0}$ denote bidder $i$’s value for bundle $K$.

Each bidder submits a bid $b_{i}$ to the auction, which is a (possibly non-
truthful) declaration of her whole valuation. The bid profile
$b=(b_{1},\ldots,b_{n})$ is the vector of all bids from all bidders. The bid
profile of every bidder except bidder $i$ is denoted $b_{{\textrm{-}i}}$.
Similarly with $b_{-K}$ for a set of bidders $K$. We also express the
combination of multiple bid profiles $b$ and $b^{\prime}$, by
$(b_{K},b^{\prime}_{-K})$, where each bidder’s bid is taken from $b$ resp.
$b^{\prime}$.

For an arbitrary subset $K$ of bidders, we define the coalitional value
$V_{K}$ as

$V_{K}(b):=\sum_{j\in K}b_{j}(X_{j}(b_{K},0_{-K})),$

i.e., the joint value this set of bidders would obtain from the goods if all
other bidders were excluded from the auction (or equivalently, their bids set
to $0$). Thus, $V_{N}$ is the social welfare obtainable under $b$.

The CA has an allocation rule $X$, determining an allocation $x=X(b)$, where
$x_{i}=X_{i}(b)$ denotes the bundle assigned to bidder $i$. We require the
resulting allocation to be _feasible_ , i.e., $\forall i,j\in N:x_{i}\cap
x_{j}=\emptyset$, and we let $\mathcal{A}$ denote the set of all feasible
allocations. We only consider _efficient_ allocation rules, i.e., rules that
produce an allocation that maximizes _reported social welfare_ (which is the
sum of bidders’ reported values). The CA also has a payment rule $p$ which is
a function assigning a payment $p_{i}(b)\in\mathbb{R}_{\geq 0}$ to each bidder
$i$. Together, the allocation $x$ and the payment vector $p$ are called the
auction _outcome_.

###  2.2 The Core

Informally, a payment vector $p$ is said to be _outside the_ _core_ if a
coalition of bidders is willing to pay more for the goods than what the
mechanism currently charges the winners. To avoid such outcomes, Day and
Milgrom (2008) introduced the idea of _core-selecting payment_ rules that
restrict payments to be in the core.

To define the core, we will need to define the welfare achieved by a subset of
bidders $K$, when goods are allocated efficiently among all bidders (and not
just among the subset $K$ as was the case with $V_{K}$):

$W_{K}(b):=\sum_{j\in K}b_{j}(X_{j}(b)).$

######  Definition 1.

Given allocation rule $X$ and a bid profile $b$, an auction outcome is in the
_core_ if $X$ is efficient and the payments $p(b)$ satisfy the individual
rationality constraints and the following additional core constraints:

$\forall L\subseteq N:\sum_{j\in N\setminus L}p_{j}(b)\geq V_{L}(b)-W_{L}(b).$
(1)

Each of the sets $L$ is called a _blocking coalition_ , and it requires that
the joint payment of the remaining bidders $N\setminus L$ is at least as large
as the joint loss of welfare incurred by $L$ due to the presence of
$N\setminus L$. Among all payment vectors in the core, the _minimum revenue
core (MRC)_ is the set of payment vectors with smallest $L_{1}$ norm, i.e.,
which minimize the sum of the payments of all bidders.

###  2.3 The LLG Domain

In this note, we restrict our attention to the Local-Local-Global (LLG) domain
[Ausubel and Milgrom, 2006]. LLG is one of the smallest examples of an auction
where combinatorial interactions between bidders arise. There are three
bidders, with bidders 1 and 2 being local, interested in two different single
goods, and bidder 3 being global, interested in the package of both goods.

In this note, we do not consider the possibility of the local bidders engaging
in _complex bidding_ , i.e., making an additional bundle bid on the global
bundle $\\{1,2\\}$, even though such manipulations have shown to be beneficial
[Beck and Ott, 2013, Bosshard and Seuken, 2020]. Instead, we assume that each
bidder only bids on their bundle of interest. Thus, we will keep the notation
simple and denote the bid profile $b$ as a vector $(A,B,G)$, where
$A:=b_{1}(\\{1\\}),B:=b_{2}(\\{2\\})$, and $G:=b_{3}(\\{1,2\\})$.

The global bidder is known to have a dominant strategy to bid truthfully under
most payment rules, namely those who are minimum revenue core selecting [Beck
and Ott, 2013]. Thus, we will focus our analysis on the two local bidders.

###  2.4 Definitions of Reference Points

We next introduce a series of payment rules. While some of these rules are
used as-is in practice, in this note we consider them as reference points from
which a projection to the minimum-revenue core is done. This method of
contructing payment rules has been proposed as a promising design approach in
the literature [Bünz et al., 2018].

######  Definition 2 (First Price).

Given a bid vector $b$, the first price payment rule is given by

$p_{i}(b):=b_{i}(X_{i}(b)).$

######  Definition 3 (VCG).

Given a bid vector $b$, the VCG payment rule is given by

$p_{i}(b):=V_{N\setminus\\{i\\}}(b)-W_{N\setminus\\{i\\}}(b).$

######  Definition 4 (Shapley payoffs/payments without Auctioneer).

Given a bid vector $b$, the Shapley payoffs (without auctioneer) are given by

$\pi_{i}(b):=\sum_{S\subseteq
N\setminus\\{i\\}}\frac{|S|!\cdot(|N|-|S|-1)!}{|N|!}(V_{S\cup\\{i\\}}(b)-V_{S}(b)),$

and the Shapley payments (without auctioneer) are given by

$p_{i}(b):=v_{i}(X_{i}(b))-\pi_{i}(b).$

######  Definition 5 (Shapley payoffs/payments with Auctioneer).

Given a bid vector $b$, the Shapley payoffs (with auctioneer) are given by

$\pi_{i}(b):=\sum_{S\subseteq
N\setminus\\{i\\}}\frac{(|S|+1)!\cdot(|N|-|S|-1)!}{(|N|+1)!}(V_{S\cup\\{i\\}}(b)-V_{S}(b)),$

and the Shapley payments (with auctioneer) are given by

$p_{i}(b):=v_{i}(X_{i}(b))-\pi_{i}(b).$

The only difference between the last two rules are the weights assigned to
each coalition. This is because the latter considers the auctioneer as an
agent in the coalitional value game on which the definition of Shapley payoffs
is based. Clearly, when the auctioneer is not part of the coalition, the value
achieved is 0. Thus, in the latter version of the Shapley payoffs, the set $S$
should be thought of as always including the auctioneer. The half of subsets
for which this doesn’t hold can be excluded from the sum, as they don’t
contribute anything to bidders’ payoffs. We believe that the Shapley payments
without seller is the more natural variant, as it has the desirable property
that it always lies below the MRC, and never above it, at least in LLG.

##  3 Results

###  3.1 Sensitivity of Reference Points

We used Python with the symbolic solver Sympy [Meurer et al., 2017] to compute
expressions for the various reference points of interest defined above. Our
code is freely available and can be found at
( https://github.com/marketdesignresearch/Shapley_MRC). To perform our
analysis in a clean way, we split the set of possible bid profiles $b=(A,B,G)$
into four cases:

  1. 1.

Both local bidders make weak bids: $A<G$, $B<G$,

  2. 2.

The first local bidder makes a strong bid: $B<G<A$,

  3. 3.

The second local bidder makes a strong bid: $A<G<B$,

  4. 4.

Both local bidders make strong bids: $G<A$, $G<B$.

Between these four cases lie the boundaries where the optimal allocations of
some subsets of bidders change. The payments change smoothly over those
boundaries, but the coalitional value functions that make up the VCG and
Shapley payment rules take on different functional forms on different sides of
the boundary.

The analytical expressions for the reference points are given in Table 3.1.

In this note, we study a quantity that we denote the _sensitivity_ of a
reference point.

######  Definition 6.

Let $p=p(b)$ be a payment rule. In the LLG domain, the _sensitivity_ of $p$ to
bidder 1’s bid $A$ is given by

$\mathrm{sens}_{1}(p(b)):=\frac{\partial p_{1}(b)}{\partial A}-\frac{\partial
p_{2}(b)}{\partial A}.$

We define this in terms of bidder 1, with the definition for bidder 2
obviously being symmetric. The sensitivities of the reference points we study
are given as analytical expressions in Table 3.1 as well. These quantities
determine how core-selecting rules using this reference point behave, as will
become clear in the next subsection.

Case |  First Price | VCG |  Shapley payment w/o seller |  Shapley payoff w/o seller |  Shapley payment w/ seller |  Shapley payoff w/ seller
---|---|---|---|---|---|---
locals weak | $p_{1}$ | $\displaystyle A$ | $\displaystyle-B+G$ | $\displaystyle\frac{A}{6}-\frac{B}{3}+\frac{G}{3}$ | $\displaystyle\frac{5\cdot A}{6}+\frac{B}{3}-\frac{G}{3}$ | $\displaystyle\frac{7\cdot A}{12}-\frac{B}{4}+\frac{G}{4}$ | $\displaystyle\frac{5\cdot A}{12}+\frac{B}{4}-\frac{G}{4}$
$p_{2}$ | $\displaystyle B$ | $\displaystyle-A+G$ | $\displaystyle-\frac{A}{3}+\frac{B}{6}+\frac{G}{3}$ | $\displaystyle\frac{A}{3}+\frac{5\cdot B}{6}-\frac{G}{3}$ | $\displaystyle-\frac{A}{4}+\frac{7\cdot B}{12}+\frac{G}{4}$ | $\displaystyle\frac{A}{4}+\frac{5\cdot B}{12}-\frac{G}{4}$
$\frac{\partial}{\partial A}$ | $\displaystyle\left(1,0\right)$ | $\displaystyle\left(0,-1\right)$ | $\displaystyle\left(\frac{1}{6},-\frac{1}{3}\right)$ | $\displaystyle\left(\frac{5}{6},\frac{1}{3}\right)$ | $\displaystyle\left(\frac{7}{12},-\frac{1}{4}\right)$ | $\displaystyle\left(\frac{5}{12},\frac{1}{4}\right)$
$sens_{1}(p(b))$ | $\displaystyle 1$ | $\displaystyle 1$ | $\displaystyle\frac{1}{2}$ | $\displaystyle\frac{1}{2}$ | $\displaystyle\frac{5}{6}$ | $\displaystyle\frac{1}{6}$
local 1 strong | $p_{1}$ | $\displaystyle A$ | $\displaystyle-B+G$ | $\displaystyle-\frac{B}{3}+\frac{G}{2}$ | $\displaystyle A+\frac{B}{3}-\frac{G}{2}$ | $\displaystyle\frac{A}{2}-\frac{B}{4}+\frac{G}{3}$ | $\displaystyle\frac{A}{2}+\frac{B}{4}-\frac{G}{3}$
$p_{2}$ | $\displaystyle B$ | $\displaystyle 0$ | $\displaystyle\frac{B}{6}$ | $\displaystyle\frac{5\cdot B}{6}$ | $\displaystyle\frac{7\cdot B}{12}$ | $\displaystyle\frac{5\cdot B}{12}$
$\frac{\partial}{\partial A}$ | $\displaystyle\left(1,0\right)$ | $\displaystyle\left(0,0\right)$ | $\displaystyle\left(0,0\right)$ | $\displaystyle\left(1,0\right)$ | $\displaystyle\left(\frac{1}{2},0\right)$ | $\displaystyle\left(\frac{1}{2},0\right)$
$sens_{1}(p(b))$ | $\displaystyle 1$ | $\displaystyle 0$ | $\displaystyle 0$ | $\displaystyle 1$ | $\displaystyle\frac{1}{2}$ | $\displaystyle\frac{1}{2}$
local 2 strong | $p_{1}$ | $\displaystyle A$ | $\displaystyle 0$ | $\displaystyle\frac{A}{6}$ | $\displaystyle\frac{5\cdot A}{6}$ | $\displaystyle\frac{7\cdot A}{12}$ | $\displaystyle\frac{5\cdot A}{12}$
$p_{2}$ | $\displaystyle B$ | $\displaystyle-A+G$ | $\displaystyle-\frac{A}{3}+\frac{G}{2}$ | $\displaystyle\frac{A}{3}+B-\frac{G}{2}$ | $\displaystyle-\frac{A}{4}+\frac{B}{2}+\frac{G}{3}$ | $\displaystyle\frac{A}{4}+\frac{B}{2}-\frac{G}{3}$
$\frac{\partial}{\partial A}$ | $\displaystyle\left(1,0\right)$ | $\displaystyle\left(0,-1\right)$ | $\displaystyle\left(\frac{1}{6},-\frac{1}{3}\right)$ | $\displaystyle\left(\frac{5}{6},\frac{1}{3}\right)$ | $\displaystyle\left(\frac{7}{12},-\frac{1}{4}\right)$ | $\displaystyle\left(\frac{5}{12},\frac{1}{4}\right)$
$sens_{1}(p(b))$ | $\displaystyle 1$ | $\displaystyle 1$ | $\displaystyle\frac{1}{2}$ | $\displaystyle\frac{1}{2}$ | $\displaystyle\frac{5}{6}$ | $\displaystyle\frac{1}{6}$
locals strong | $p_{1}$ | $\displaystyle A$ | $\displaystyle 0$ | $\displaystyle\frac{G}{6}$ | $\displaystyle A-\frac{G}{6}$ | $\displaystyle\frac{A}{2}+\frac{G}{12}$ | $\displaystyle\frac{A}{2}-\frac{G}{12}$
$p_{2}$ | $\displaystyle B$ | $\displaystyle 0$ | $\displaystyle\frac{G}{6}$ | $\displaystyle B-\frac{G}{6}$ | $\displaystyle\frac{B}{2}+\frac{G}{12}$ | $\displaystyle\frac{B}{2}-\frac{G}{12}$
$\frac{\partial}{\partial A}$ | $\displaystyle\left(1,0\right)$ | $\displaystyle\left(0,0\right)$ | $\displaystyle\left(0,0\right)$ | $\displaystyle\left(1,0\right)$ | $\displaystyle\left(\frac{1}{2},0\right)$ | $\displaystyle\left(\frac{1}{2},0\right)$
$sens_{1}(p(b))$ | $\displaystyle 1$ | $\displaystyle 0$ | $\displaystyle 0$ | $\displaystyle 1$ | $\displaystyle\frac{1}{2}$ | $\displaystyle\frac{1}{2}$

Table 1: Analytical expressions in LLG for six different payment rules used as
reference points. The analysis is split into four cases depending on the
relative strength of the bids $A,B$ and $G$.

###  3.2 Application to Core-Selecting Payment Rules

As explained in the preliminaries, many payment rules are defined by taking
the reference point and projecting onto the point of the MRC that has the
smallest distance in some metric such as $L_{2}$. For all such _minimum-
revenue core-selecting (MRCS)_ rules, we can characterize how manipulable they
are (locally), only needing to know the sensitivity of the reference point and
the position of the reference point relative to the individual rationality
constraints.

######  Lemma 1.

Let $p$ be a payment rule, and $\mathrm{proj}(p)$ a MRCS payment rule which
uses $p$ as a reference point, i.e., it selects the point on the minimum-
revenue core closest to $p$ according to the $L_{c}$ metric for some $c>1$.

Then, we have that

$\frac{\partial\mathrm{proj}(p)_{1}}{\partial
A}=\left\\{\begin{array}[]{ll}1&\mathrm{\ if\ }p_{1}>p_{2}-G+2A\\\ 0&\mathrm{\
if\ }p_{1}<p_{2}+G-2B\\\ \mathrm{sens}(p)_{1}/2&\mathrm{\ otherwise\ }\\\
\end{array}\right.$ (2)

Figure 1: The core in LLG. The projections of different reference points to
the minimum-revenue core are shown in blue. The core projection reacts
differently to changes in the reference point, depending on which side of the
given inequalities the reference point is located.

Condition (2) of the lemma distinguishes three cases (see Figure 1). In the
first case, bidder 2’s IR constraint is binding, so bidder 1 cannot affect his
payment (locally). In the second case, the projection to the MRC hits bidder
1’s IR constraint, so any change to $b_{1}(A)$ immediately moves the payment
by the same amount. If neither of these two constraints are binding, the
payment varies based on the sensitivity of the reference point.

###### Proof.

In LLG, when the local bidders win, the minimum revenue core is given by the
global constraint $p_{1}+p_{2}\geq G$, capped at each end by the local
bidders’ IR constraints, and there are no other core constraints to consider.

For any $L_{c}$ norm with $c>1$, and any point $p$, the closest point to $p$
that lies on this global core constraint can be calculated as follows: we take
the amount missing to exactly satisfy the constraint, i.e., $G-p_{1}-p_{2}$,
and split it evenly among the local bidders. The inequalities given in the
first two cases characterize exactly if this projection reaches the MRC, or if
one of the two IR constraints become binding.

In the first two cases, the location of the reference point does not matter at
all, as the intersection of the global constraint and the corresponding IR
constraint is always chosen as the solution. Thus, the derivative of the
payment depends only on how a change in bidder 1’s bid affects the IR
constraint itself, which is 1 if it is the same bidders’ IR constraint, and 0
if it is the other bidders’.

In the third case, bidder 1’s payment, as argued above, is

$\mathrm{proj}(p)_{1}=p_{1}+\frac{G-p_{1}-p_{2}}{2}=\frac{G+p_{1}-p_{2}}{2},$
(3)

and the derivative follows trivially. ∎

(a) Projection onto MRC from VCG (i.e., VCG-nearest).

(b) Projection onto MRC from Shapley payments (without seller).

(c) Projection onto MRC from Shapley payments (with seller).

Figure 2: Derivatives of three MRCS payment rules in the LLG domain. The MRC
projections are done with any $L_{c}$ metric for $c>1$. The derivatives are
taken w.r.t. to bidder 1’s bid $A$, and they depend on the bids $A$ and $B$ of
both local bidders, as well as on the global bidder’s bid $G$. The bidding
space is divided into four cases as shown by the red lines. In the white area,
the local bids sum up to less than $G$, so the global bidder wins both goods.

Based on Lemma 1, we can now fully characterize many MRC payment rules in LLG.
In this note, we show three examples, VCG-nearest and Shapley-nearest (based
on Shapley payments with and without the seller).

The VCG reference point always falls into case 3 of the Lemma, as can be
easily verified by hand using the analytical expressions from Table 3.1. Thus,
the derivative of VCG-nearest is exactly half the sensitivity of VCG, i.e.,
either $1/2$ or $0$, depending on bidder 1’s bid (Figure 2(a)).

For Shapley-nearest, the inequalities from (2) hold under the following
conditions:

| Shapley payments (without seller) | Shapley payments (with seller)
---|---|---
| $p_{1}>p_{2}-G+2A$ | $p_{1}<p_{2}+G-2B$ | $p_{1}>p_{2}-G+2A$ | $p_{1}<p_{2}+G-2B$
weak locals | $3A+B<2G$ | $A+3B<2G$ | $7A+5B<6G$ | $5A+7B<6G$
strong local 1 | never holds | $A>3B$ | never holds | $A>7B$
strong local 2 | $3A<G$ | never holds | $7A<G$ | never holds
strong locals | never holds | never holds | never holds | never holds

The situation is summarized graphically in Figures 2(b) and 2(c). As we can
see, in most cases, the local manipulability is much lower than for VCG-
nearest, except when $A$ is very low compared to $G$. This plausibly explains
the experimental findings of [Bünz et al., 2018] that this payment rule has
better incentive properties than VCG-nearest in LLG under incomplete
information: while it is not monotonically better according to our metric, it
is better when the corresponding bidder’s value is high, and this case is more
relevant to overall utility for that bidder.

##  4 Discussion

In this note, we presented some preliminary results pointing at a possible
explanation why certain reference point rules are more manipulable than
others. Even though the VCG-nearest payment rule is widely used in practice
[Ausubel and Baranov, 2017], our analysis shows that it has a relatively high
susceptibility to being manipulated. With the VCG point having a sensitivity
of $1$, VCG-nearest behaves as an even mixture between the first price and VCG
payment rules (in the appropriate sub-case), as has been shown previously
[Bosshard and Seuken, 2020].

In contrast, we characterize payment rules based on the Shapley reference
point as being surprisingly resistant to manipulations, at least in the LLG
domain.

In future work, we aim to generalize the notion of sensitivity to larger
domains of arbitrary dimensionality, to analyze the behavior of reference
point rules in those domains, and to use those insights to better predict a
bidder’s behavior when acting under incomplete information.

## References

  * [Ausubel and Baranov, 2017] Ausubel, L. and Baranov, O. (2017).  A practical guide to the combinatorial clock auction.  The Economic Journal, 127(605).
  * [Ausubel and Milgrom, 2006] Ausubel, L. and Milgrom, P. (2006).  The lovely but lonely Vickrey auction.  In Cramton, P., Shoham, Y., and Steinberg, R., editors, Combinatorial Auctions. MIT Press.
  * [Beck and Ott, 2013] Beck, M. and Ott, M. (2013).  Incentives for overbidding in minimum-revenue core-selecting auctions.  Annual Conference 2013 (Duesseldorf): Competition Policy and Regulation in a Global Economic Order.
  * [Bosshard et al., 2020] Bosshard, V., Bünz, B., Lubin, B., and Seuken, S. (2020).  Computing bayes-nash equilibria in combinatorial auctions with verification.  Journal of Artificial Intelligence Research, 69:531–570.
  * [Bosshard and Seuken, 2020] Bosshard, V. and Seuken, S. (2020).  The cost of simple bidding in combinatorial auctions.  Working Paper, University of Zurich.
  * [Bünz et al., 2018] Bünz, B., Lubin, B., and Seuken, S. (2018).  Designing core-selecting payment rules: A computational search approach.  In Proceedings of the 19th ACM Conference on Electronic Commerce (EC), Ithaca, NY, USA.
  * [Meurer et al., 2017] Meurer, A., Smith, C. P., Paprocki, M., Čertík, O., Kirpichev, S. B., Rocklin, M., Kumar, A., Ivanov, S., Moore, J. K., Singh, S., et al. (2017).  Sympy: symbolic computing in python.  PeerJ Computer Science, 3:e103.
  * [Shapley, 1953] Shapley, L. S. (1953).  A value for n-person games.  Contributions to the Theory of Games, 2(28):307–317.