# Do Concept Bottleneck Models Obey Locality?

Naveen Raman
Carnegie Mellon University
<EMAIL_ADDRESS>
&Mateo Espinosa Zarlenga
University of Cambridge
<EMAIL_ADDRESS>
Juyeon Heo
University of Cambridge
<EMAIL_ADDRESS>
&Mateja Jamnik
University of Cambridge
<EMAIL_ADDRESS>

###### Abstract

Concept-based learning improves a deep learning model’s interpretability by
explaining its predictions via human-understandable concepts. Deep learning
models trained under this paradigm heavily rely on the assumption that neural
networks can learn to predict the presence or absence of a given concept
independently of other concepts. Recent work, however, strongly suggests that
this assumption may fail to hold in Concept Bottleneck Models (CBMs), a
quintessential family of concept-based interpretable architectures. In this
paper, we investigate whether CBMs correctly capture the degree of conditional
independence across concepts when such concepts are localised both spatially,
by having their values entirely defined by a fixed subset of features, and
semantically, by having their values correlated with only a fixed subset of
predefined concepts. To understand locality, we analyse how changes to
features outside of a concept’s spatial or semantic locality impact concept
predictions. Our results suggest that even in well-defined scenarios where the
presence of a concept is localised to a fixed feature subspace, or whose
semantics are correlated to a small subset of other concepts, CBMs fail to
learn this locality. These results cast doubt upon the quality of concept
representations learnt by CBMs and strongly suggest that concept-based
explanations may be fragile to changes outside their localities.

##  1 Introduction

Concept-based learning is an interpretability paradigm that leverages human-
understandable concepts as a way to explain a deep learning model’s
predictions [1, 2, 3, 4]. Concept Bottleneck Models (CBMs) [2] are constructed
using this paradigm by first predicting concepts from an input sample and then
using these concepts to predict a downstream label of interest. This design
allows CBMs to: (1) provide concept-based explanations for their predictions
via their predicted sets of concepts, and (2) improve their test performance
when deployed in conjunction with experts via concept interventions [5, 6].

In this work, we investigate whether CBMs properly capture a task’s feature-
to-concept and concept-to-concept relationships through the lens of what we
will refer to as concept locality. Concept locality refers to the idea that,
for certain tasks, a concept’s value is a function of a subset of features and
concepts; modifications to features or concepts outside this should not impact
the concept’s prediction. For example, the concept of “bird beak colour”
should be predicted by focusing exclusively on the beak region of the image.

Recent work by Margeloiu et al. [7] has observed that features deemed
important for a CBM’s concept’s prediction may not be confined to features
known to fully define said concept. Here, we aim to build on this surprising
result by analysing the locality of a CBM’s learnt concept representations
when the training concepts are: (1) spatially localised, where values can be
perfectly predicted from a well-defined subset of input features, and (2)
semantically localised, where a concept’s value is independent of the value of
a well-defined subset of concepts. We select these two modes to reflect
varying granularities of features: spatial locality is related to changes in
individual features, such as pixels, while semantic locality is related to
changes to abstract-level groups of features (Figure 1).

(a)

(b)

Figure 1: CBMs fail to accurately reflect localities present in tasks. (a)
Changing pixels on the right side of the image modifies the prediction for the
shape on the left side from a triangle to a square. (b) Rotation and dilation
changes shape prediction from heart to circle.

Our contributions are the following: we (1) introduce spatial and semantic
locality for concept-based models, (2) assess a CBM’s ability to capture the
spatial locality and show this is inversely proportional to the CBM’s
capacity, and (3) analyse a CBM’s ability to properly capture a task’s
semantic locality and show that this is dependent on the task’s available
concept annotations.

##  2 Related Works

#### Concept Learning

Concept learning [1, 8, 9, 10, 11, 3] is a subfield of eXplainable Artificial
Intelligence (XAI) where a Deep Neural Network’s predictions are explained via
high-level units of information (i.e., “concepts”). Methods in this field can
vary from fully concept-supervised [2, 12, 4, 13], where one assumes access to
both task and concept labels during training, to concept-unsupervised methods
[9, 11, 14], where only task labels are available. In this paper, we explore
Concept Bottleneck Models (CBMs) [2] due to their importance and ubiquity [3,
4, 13, 14, 15].

#### Robustness of Concept-Based Models

Since Margeloiu et al. [7] showed, via the use of saliency maps [16, 17, 18],
that CBMs may construct their concept representations by possibly exploiting
spurious correlations between concepts and input features, several works have
studied this phenomenon [19, 20, 21, 22, 23, 24, 25]. Key amongst these, the
work by Mahinpei et al. [19] stands out by showing how CBMs are prone to
encoding undesired information in their learnt representations even when
concepts are completely independent (referred to as “concept leakage”). This
ignited several works attempting to understand how this leakage may be (1)
detected at inference [22], (2) measured at test-time [20], (3) affected by a
dataset’s inter-concept correlations [23], and (4) exploited for adversarial
attacks against CBMs [21]. Our work differentiates itself from these by being
the first to consider, to the best of our knowledge, how robust a CBM’s
concept’s prediction is to changes entirely outside its spatial and semantic
locality. Furthermore, we explore how elements often ignored during analysis,
like the capacity of a CBM’s concept predictor, may play an essential part in
the CBM’s robustness.

##  3 Introducing Locality

###  3.1 Concept Learning Setup

In the concept-supervised regime defined above, each training data point
$\mathbf{x}$ has an associated set of $k$ binary concepts
$\mathbf{c}\in\\{0,1\\}^{k}$. This set serves as a low-dimensional human-
understandable representation that is relevant for a downstream task of
interest. Formally, during training we are given a set of input data,
$X=\\{\mathbf{x}^{(i)}\in\mathbb{R}^{m}\\}_{i=1}^{n}$, task labels
$Y=\\{y^{(i)}\in\\{1,\cdots,L\\}\\}_{i=1}^{n}$, and concepts
$C=\\{\mathbf{c}^{(i)}\in\\{0,1\\}^{k}\\}_{i=1}^{n}$. For each data point,
$\mathbf{c}^{(i)}$ is a binary $k$-length vector where $\mathbf{c}^{(i)}_{j}$
denotes whether the $j$-th concept (e.g., “red fruit”) is present or not in
$\mathbf{x}^{(i)}$.

Concept learning can be used to develop interpretable architectures where
predictions are made using concepts. This is typically done through a Concept
Bottleneck Model (CBM) [2], a two-stage model consisting of a concept
predictor $g:\mathbf{x}\mapsto\hat{\mathbf{c}}$, and a label predictor
$f:\hat{\mathbf{c}}\mapsto\hat{y}$. CBMs allow for interpretability by
analysing concept values during prediction.

###  3.2 Defining Locality

#### Spatial Locality

To properly capture feature-to-concept relationships, it is desirable for a
CBM’s concept predictor to learn how a concept is “spatially localised” with
respect to input features. In this context, capturing spatial locality implies
that a CBM’s prediction $\hat{\mathbf{c}}^{(i)}_{j}$ of concept
$\mathbf{c}^{(i)}_{j}$’s activation value should depend only on a minimum set
of features $\mathcal{L}_{j}(\mathbf{x}^{(i)})\subseteq\\{1,\cdots,m\\}$. This
set of features, which we call the local region of concept $\mathbf{c}_{j}$
for $\mathbf{x}^{(i)}$, corresponds to the smallest set of input features that
an oracle would need to predict $\mathbf{c}^{(i)}_{j}$ from
$\mathbf{x}^{(i)}$. When properly captured, spatial locality implies that a
CBM’s concept’s prediction should be conditionally independent of features
outside the concept’s local region $\mathcal{L}_{j}(\mathbf{x}^{(i)})$.
Capturing spatial locality can ensure the robustness of a CBM’s explanation so
noise on spatially irrelevant features does not impact concept predictions.

#### Semantic Locality

A CBM’s prediction of concept $\mathbf{c}_{j}$ should be conditionally
independent of the other concepts which lack a semantic relationship with
$\mathbf{c}_{j}$. Correctly capturing this property, which we call semantic
locality, implies that a CBM predicts concepts using only relevant
relationships between concepts. For example, if a dataset contained examples
where both green background and green feathers were present, such a
correlation should not be embedded into the model unless it is semantically
meaningful. Models failing to capture semantic locality could have their
concept predictions impacted by irrelevant inter-concept relationships. For
example, changes to a bird’s background should not lead to changes in
prediction for bird species.

Semantic locality differs from spatial locality in its granularity; while
spatial locality is a property of how individual feature perturbations impact
concept predictions, semantic locality is a property of the inter-concept
relationships and is a reflection of a relationship between groups of
features.

###  3.3 Measuring Locality

We develop quantitative metrics for measuring how well a concept-based method
captures spatial and semantic localities in a set of concept representations.
We measure whether a model captures spatial locality by determining if a
concept prediction by a concept-based method can be arbitrarily modified
through targeted changes to input features outside that concept’s known local
region. Formally, for an input $\mathbf{x}^{(i)}$ and concept
$\mathbf{c}_{j}$, we perturb features outside of
$\mathcal{L}_{j}(\mathbf{x}^{(i)})$, that is,
$\\{1,\cdots,m\\}\setminus\mathcal{L}_{j}(\mathbf{x}^{(i)})$, to see if we can
flip the prediction of concept $j$. Specifically, we aim to find an
$\mathbf{x}^{\prime}\in\mathbb{R}^{m}$ so that $\forall
a\in\mathcal{L}_{j}(\mathbf{x}^{(i)}),\;\mathbf{x}^{\prime}_{a}=\mathbf{x}^{(i)}_{a}$
while $|g(\mathbf{x}^{\prime})_{j}-g(\mathbf{x}^{(i)})_{j}|$ is maximised. To
find such an $\mathbf{x}^{\prime}$, we use gradient ascent to maximise the
difference in concept prediction when getting $\mathbf{x}^{\prime}$ as an
input and compare it with its prediction for the same concept when receiving
$\mathbf{x}^{(i)}$ as an input. This metric, which we call the spatial
locality leakage $\mathcal{S}$, can be formally defined as

$\mathcal{S}\big{(}g,\mathbf{x}^{(i)}\big{)}:=\frac{1}{k}\sum_{j=1}^{k}\Bigg{(}\max_{\begin{subarray}{c}\mathbf{x}^{\prime}\in\mathbb{R}^{m}\text{
s.t. }\\\ \forall
a\in\mathcal{L}_{j}(\mathbf{x}^{(i)}),\;\mathbf{x}^{\prime}_{a}=\mathbf{x}^{(i)}_{a}\end{subarray}}|g(\mathbf{x}^{\prime})_{j}-g(\mathbf{x}^{(i)})_{j}|\Bigg{)}$
(1)

where $g(\mathbf{x}^{\prime})_{j}$ represents the prediction for concept $j$
for input $\mathbf{x}^{\prime}$. This value captures the ease of changing
concept predictions by modifying an input $x^{(i)}$. Large spatial locality
leakages imply modifications to irrelevant features could impact concept
predictions.

To explore semantic locality, we analyse the Concept Out-of-Distribution
Accuracy (CODA), which is the concept accuracy across data points when
training a CBM on only a subset of concept combinations. Ideally, the presence
or lack of semantically unrelated concepts should not impact the behaviour of
the concept predictor. To measure whether this assumption holds, we compute
the accuracy of the concept predictor for each concept $j$.

##  4 Spatial Locality Experiments

#### Experimental Setup

In this section, we evaluate whether spatial locality is correctly learned by
CBMs with the help of multiple variants of a synthetic dataset. We consider a
synthetic image dataset in which each sample is formed by $r\in\\{1,2,4\\}$
objects that are spatially localised (e.g., constrained to a subregion of the
input space) and can be either a “square” or a “triangle”. Concepts in this
situation refer to the presence of each shape in each localized region; for
example, one concept is whether a square is present in the top right corner.
We note that shapes in one region are independent of those in another, hence
enabling us to measure whether CBMs correctly capture spatial locality. Using
this dataset, we train CBMs while varying the concept predictor architecture
to determine if spatial locality can be captured by different concept
predictor models in a CBM. Specifically, we train CBMs that use either a
convolutional neural networks (CNN) or a multi-layer perception (MLP) as their
concept predictor $g$, and vary the size of these models (more details in
Appendix A).

#### Impact of Model Size

We investigate whether CBMs, trained on a simple 1-object synthetic dataset
with clear spatial locality in its concepts, can properly capture such
locality as one varies concept predictor capacity. In Figure 2(a) we see that
larger capacity concept predictors lead to more spatial locality leakage in
CBMs when the concept predictor is a CNN-based model. These results suggest
that increasing the number of layers, and hence increasing the model’s
capacity and parameters, may surprisingly lead to CBMs failing to correctly
capture a task’s spatial locality.

Figure 2:  In tasks with spatial locality, CBM models fail to obey this
locality. For the 1-object synthetic dataset, increasing the number of layers
results in models that are not spatially localised.

We analyse this trend in MLP models in Appendix B and find similar patterns
with model width, although the impact on a CBM’s ability to capture spatial
locality as we change the capacity of its MLP concept predictor is less clear.
To alleviate this problem, we find that pruning models then briefly retraining
improves spatial locality; we provide further details in Appendix C.

Prior work argued that larger models could memorise more spurious
correlations, which provides an intuition for why spatial locality is worse
with larger models [26]. Such an explanation might also apply to our scenario,
as the extra capacity allows concept predictor models to learn irrelevant
features. Nevertheless, as shown in Figure 6 of our Appendix, our synthetic
dataset is built so that concepts are localised to one and only one region
independently of concepts in different regions. Therefore, these results cast
a serious concern on what sorts of relationships and correlations a CBM’s
concept predictor may be capturing in practice when predicting a concept.
Perhaps more importantly, these results are not restricted to CBMs: in
Appendix G we show that training concept predictors independent of the
downstream task still lead to spatial locality leakage.

#### CUB Experiments

To understand if models are spatially localised in situations where a
concept’s local region is not always fully known/clear, we investigate how
concept predictions change when masking relevant and irrelevant features. We
run experiments masking various concepts using the Caltech-UC Davis Birds
(CUB) dataset [27], which consists of images of birds annotated with several
visual properties (i.e., “concepts”) as well as with the type of species they
belong to. The concepts in this dataset are different bird attributes, such as
beak colour, tail length, and wing colour. Each concept is part of a concept
group, which we denote $r(j)$: the group for concept $\mathbf{c}_{j}$; the
concepts “beak red colour” and “beak blue colour” are in the same concept
group. We are given the centre of each concept group for each data point,
which we denote as $t_{r(j)}(\mathbf{x})\in\mathbb{R}_{+}^{2}$. We consider
the local region for the concept to be within a distance $\epsilon$ of this
centre, where $\epsilon$ is normalised with respect to the image width. We
generate a mask within a distance $\epsilon$ of the centre and measure the
average change in concept predictions within the concept group as a result of
this mask (example in Figure 3).

(a)

(b)

(c)

Figure 3: We compare examples of full masking (a) and closest masking (b) for
the part “crown”, referring to the top of the bird’s head. We note that the
closest masking only covers the top of the bird’s head, while the full masking
covers other parts, such as parts of the feathers and neck. (c) Full masks
lead to larger concept changes than closest masks, so, for example, masking
out the neck of a bird impacts predictions for its head colour.

To investigate input-concept locality, we construct a spatial locality mask
$\mathbf{\mu}_{j}\in\\{0,1\\}^{m}$ for each concept $\mathbf{c}_{j}$ that
selects a combination of relevant and irrelevant features for its
corresponding concept. For simplicity, for all concepts $\mathbf{c}_{j}$ we
constrain $\mathbf{\mu}_{j}$ to be a circular mask with radius $\epsilon$,
selected as a hyperparameter, and a different centre selected via the
following policies:

  1. 1.

Full \- $\mathbf{\mu}_{j}$ is centred at $t_{r(j)}(\mathbf{x})$, the known
annotated centre of its concept group.

  2. 2.

Closest \- $\mathbf{\mu}_{j}$ is centred at $t_{r(j)}(\mathbf{x})$ but we
include only pixels that are closer to concept $\mathbf{c}_{j}$’s centre than
the centre of any other concept. That is, we select all points
$\mathbf{p}\in\mathbb{R}_{+}^{2}$ so that
$||\mathbf{p}-t_{r(j)}(\mathbf{x})||_{2}\leq\epsilon$ and $\forall
j^{\prime}\neq
j,\;||\mathbf{p}-t_{r(j)}(\mathbf{x})||_{2}\leq||\mathbf{p}-t_{r(j^{\prime})}(\mathbf{x})||_{2}$.

  3. 3.

Random \- $\mathbf{\mu}_{j}$ is centred at a random location.

Our results, shown in Figure 3(c), suggest that concepts learnt by a CBM are
not spatially localised to their respective part. While increasing the mask
radius $\epsilon$ results in changes for concept prediction, we see that using
full masking results in much larger changes to the concept prediction than
either the random or closest masks. The difference between full and closest
masking is that full masking covers pixels associated with other concept
groups, and so masking these pixels out results in a large change for the
concept predictions. For example, modifying pixels associated with the “neck”
part impacts the prediction for “crown colour”.

Essentially, modifying pixels closer to other concept groups, which represent
different body parts, leads to significantly different predictions for a given
concept. One consequence of these results is that partially occluded concepts
might leverage other independent regions to make predictions. These results
highlight that CBMs fail to capture spatial locality even in real-world tasks,
as their concept predictors may exploit pixels outside the spatially local
region.

##  5 Semantic Locality Experiments

#### Experimental Setup

To investigate whether CBMs capture semantic locality, we explore synthetic
tasks built using the dSprites dataset [28]. The dataset consists of various
semantically independent attributes, including “position”, “size”, “colour”,
and “shape”. We split each of these attributes into various concepts,
resulting in $288$ unique concept combinations, and use $20$ for training,
then evaluate across all combinations at test time (more details in Appendix
E).

#### Concept-to-concept Interactions

Figure 4:  Frequency of Hamming distances between a CBM’s concept predictions,
$\hat{\mathbf{c}}$, on the dSprites test set and the closest training concept
annotation $\mathbf{c}$. Smaller hamming distances indicate predictions are
closer to the training dataset. Predictions are closer to the training set
than concept annotations, showing that concept predictors struggle beyond the
training dataset.

To understand if semantically unrelated concepts can impact concept
predictions, we measure whether novel concept combinations in the testing set
lead CBMs to change their concept predictions. While concept predictors should
be able to make predictions dissimilar to concept combinations seen during
training, in Figure 4 we find that this is not true. CBMs tend to generate
concept combinations already seen in the training dataset, as most predictions
have a small Hamming distance to training data points. These results show the
tendency of CBM models to memorise training explanations, revealing a lack of
semantic locality. To account for confounding factors, we vary concept
predictor capacity and training set size in Appendix D, finding that larger
training sets improve concept accuracy slightly.

#### Model Generalisation

Figure 5:  PCA projection of images from the dSprites dataset and their labels
predicted by the SVM. Notice how the “Right Half” concept is linearly
separable while the “Heart” concept is not.

To better understand why concept combinations have these differences, we use
Principal Component Analysis (PCA) to project inputs into 2D [29] and use a
linear SVM to predict concepts. In Figure 5 we display concept predictions for
two concepts: one (“right half”) which has linear separability and is easier
to predict, while another (“heart shaped”) lacks linear separability and is
harder to predict. At an individual concept level, we see that the accuracy of
the SVM on the dimensionality-reduced dataset, which we denote PCA accuracy,
varies significantly amongst concepts. In Figure 9, we find that data which
results in higher PCA accuracy leads to better CODA, indicating that more
difficult concepts are harder to predict when faced with new concept
combinations (see Appendix F). This implies that the issues are with the
inability of concept predictors to learn meaningful relationships: even when
training these concept predictors independently, they only achieve 8% task
accuracy (see Appendix G). In future work, we plan to explore novel forms of
regularisation for concept predictors that encourage concept predictions to
better capture independence and semantic locality.

##  6 Conclusion and Future Work

In this paper, we explored whether CBMs can properly learn two types of
locality found in concept-annotated datasets: spatial and semantic. These
notions of locality capture whether a CBM learns to use only relevant feature-
to-concept and concept-to-concept relationships. We find that spatial locality
risks being miscaptured when a CBM’s concept predictor is overparameterised,
while semantic locality is impacted by the diversity of training concept
annotations. These findings demonstrate that small changes in the training set
and architecture can impact the quality of a CBM’s explanations. In future
work, we will explore whether recent methods developed for adversarial and
spurious robustness in CBMs [21, 23] can lead to CBMs capturing locality
better.

## Acknowledgements and Disclosure of Funding

The authors would like to thank Katie Collins, Andrei Margeloiu, Tennison Liu,
and Xiangjian Jiang for their suggestions and discussions on the paper.
Additionally, the authors would like to thank Zohreh Shams for their comments
on the paper, and from the NeurIPS XAI Workshop reviewers for their insightful
comments. During the time of this work, NR was supported by a Churchill
Scholarship, and NR additionally acknowledges support from the NSF GRFP
Fellowship. MEZ acknowledges support from the Gates Cambridge Trust via a
Gates Cambridge Scholarship. JH thanks support from Cambridge Trust
Scholarship. MJ is supported by the EPSRC grant EP/T019603/1.

## References

  * Kim et al. [2018] Been Kim, Martin Wattenberg, Justin Gilmer, Carrie Cai, James Wexler, Fernanda Viegas, et al.  Interpretability beyond feature attribution: Quantitative testing with concept activation vectors (tcav).  In _International conference on machine learning_ , pages 2668–2677. PMLR, 2018.
  * Koh et al. [2020] Pang Wei Koh, Thao Nguyen, Yew Siang Tang, Stephen Mussmann, Emma Pierson, Been Kim, and Percy Liang.  Concept bottleneck models.  In _International Conference on Machine Learning_ , pages 5338–5348. PMLR, 2020.
  * Espinosa Zarlenga et al. [2022] Mateo Espinosa Zarlenga, Pietro Barbiero, Gabriele Ciravegna, Giuseppe Marra, Francesco Giannini, Michelangelo Diligenti, Zohreh Shams, Frederic Precioso, Stefano Melacci, Adrian Weller, et al.  Concept embedding models: Beyond the accuracy-explainability trade-off.  _Advances in Neural Information Processing Systems_ , 35:21400–21413, 2022.
  * Yuksekgonul et al. [2022] Mert Yuksekgonul, Maggie Wang, and James Zou.  Post-hoc concept bottleneck models.  _arXiv preprint arXiv:2205.15480_ , 2022.
  * Chauhan et al. [2022] Kushal Chauhan, Rishabh Tiwari, Jan Freyberg, Pradeep Shenoy, and Krishnamurthy Dvijotham.  Interactive concept bottleneck models.  _arXiv preprint arXiv:2212.07430_ , 2022.
  * Shin et al. [2023] Sungbin Shin, Yohan Jo, Sungsoo Ahn, and Namhoon Lee.  A closer look at the intervention procedure of concept bottleneck models.  _arXiv preprint arXiv:2302.14260_ , 2023.
  * Margeloiu et al. [2021] Andrei Margeloiu, Matthew Ashman, Umang Bhatt, Yanzhi Chen, Mateja Jamnik, and Adrian Weller.  Do concept bottleneck models learn as intended?  _arXiv preprint arXiv:2105.04289_ , 2021.
  * Goyal et al. [2019] Yash Goyal, Amir Feder, Uri Shalit, and Been Kim.  Explaining classifiers with causal concept effect (cace).  _arXiv preprint arXiv:1907.07165_ , 2019.
  * Ghorbani et al. [2019] Amirata Ghorbani, James Wexler, James Y Zou, and Been Kim.  Towards automatic concept-based explanations.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Kazhdan et al. [2020] Dmitry Kazhdan, Botty Dimanov, Mateja Jamnik, Pietro Liò, and Adrian Weller.  Now you see me (cme): concept-based model extraction.  _arXiv preprint arXiv:2010.13233_ , 2020.
  * Yeh et al. [2020] Chih-Kuan Yeh, Been Kim, Sercan Arik, Chun-Liang Li, Tomas Pfister, and Pradeep Ravikumar.  On completeness-aware concept-based explanations in deep neural networks.  _Advances in Neural Information Processing Systems_ , 33:20554–20565, 2020.
  * Chen et al. [2020] Zhi Chen, Yijie Bei, and Cynthia Rudin.  Concept whitening for interpretable image recognition.  _Nature Machine Intelligence_ , 2(12):772–782, 2020.
  * Kim et al. [2023] Eunji Kim, Dahuin Jung, Sangha Park, Siwon Kim, and Sungroh Yoon.  Probabilistic concept bottleneck models.  _arXiv preprint arXiv:2306.01574_ , 2023.
  * Oikarinen et al. [2023] Tuomas Oikarinen, Subhro Das, Lam M Nguyen, and Tsui-Wei Weng.  Label-free concept bottleneck models.  _arXiv preprint arXiv:2304.06129_ , 2023.
  * Zarlenga et al. [2023] Mateo Espinosa Zarlenga, Zohreh Shams, Michael Edward Nelson, Been Kim, and Mateja Jamnik.  Tabcbm: Concept-based interpretable neural networks for tabular data.  _Transactions on Machine Learning Research_ , 2023.
  * Baehrens et al. [2010] David Baehrens, Timon Schroeter, Stefan Harmeling, Motoaki Kawanabe, Katja Hansen, and Klaus-Robert Müller.  How to explain individual classification decisions.  _The Journal of Machine Learning Research_ , 11:1803–1831, 2010.
  * Smilkov et al. [2017] Daniel Smilkov, Nikhil Thorat, Been Kim, Fernanda Viégas, and Martin Wattenberg.  Smoothgrad: removing noise by adding noise.  _arXiv preprint arXiv:1706.03825_ , 2017.
  * Sundararajan et al. [2017] Mukund Sundararajan, Ankur Taly, and Qiqi Yan.  Axiomatic attribution for deep networks.  In _International conference on machine learning_ , pages 3319–3328. PMLR, 2017.
  * Mahinpei et al. [2021] Anita Mahinpei, Justin Clark, Isaac Lage, Finale Doshi-Velez, and Weiwei Pan.  Promises and pitfalls of black-box concept learning models.  _arXiv preprint arXiv:2106.13314_ , 2021.
  * Espinosa Zarlenga et al. [2023] Mateo Espinosa Zarlenga, Pietro Barbiero, Zohreh Shams, Dmitry Kazhdan, Umang Bhatt, Adrian Weller, and Mateja Jamnik.  Towards Robust Metrics for Concept Representation Evaluation.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 37(10):11791–11799, June 2023.  doi: 10.1609/aaai.v37i10.26392.  URL https://ojs.aaai.org/index.php/AAAI/article/view/26392.
  * Sinha et al. [2023] Sanchit Sinha, Mengdi Huai, Jianhui Sun, and Aidong Zhang.  Understanding and enhancing robustness of concept-based models.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 37, pages 15127–15135, 2023.
  * Marconato et al. [2022a] Emanuele Marconato, Andrea Passerini, and Stefano Teso.  Glancenets: Interpretable, leak-proof concept-based models.  _Advances in Neural Information Processing Systems_ , 35:21212–21227, 2022a.
  * Heidemann et al. [2023] Lena Heidemann, Maureen Monnet, and Karsten Roscher.  Concept correlation and its effects on concept-based models.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , pages 4780–4788, 2023.
  * Havasi et al. [2022] Marton Havasi, Sonali Parbhoo, and Finale Doshi-Velez.  Addressing leakage in concept bottleneck models.  _Advances in Neural Information Processing Systems_ , 35:23386–23397, 2022.
  * Marconato et al. [2022b] Emanuele Marconato, Andrea Passerini, and Stefano Teso.  Glancenets: Interpretable, leak-proof concept-based models.  _Advances in Neural Information Processing Systems_ , 35:21212–21227, 2022b.
  * Sagawa et al. [2020] Shiori Sagawa, Aditi Raghunathan, Pang Wei Koh, and Percy Liang.  An investigation of why overparameterization exacerbates spurious correlations.  In _International Conference on Machine Learning_ , pages 8346–8356. PMLR, 2020.
  * Wah et al. [2011] Catherine Wah, Steve Branson, Peter Welinder, Pietro Perona, and Serge Belongie.  The caltech-ucsd birds-200-2011 dataset.  2011\.
  * Matthey et al. [2017] Loic Matthey, Irina Higgins, Demis Hassabis, and Alexander Lerchner.  dsprites: Disentanglement testing sprites dataset.  https://github.com/deepmind/dsprites-dataset/, 2017.
  * F.R.S. [1901] Karl Pearson F.R.S.  Liii. on lines and planes of closest fit to systems of points in space.  _The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science_ , 2(11):559–572, 1901.  doi: 10.1080/14786440109462720.
  * Tishby et al. [2000] Naftali Tishby, Fernando C. Pereira, and William Bialek.  The information bottleneck method, 2000.
  * Blalock et al. [2020] Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag.  What is the state of neural network pruning?  _Proceedings of machine learning and systems_ , 2:129–146, 2020.

##  Appendix A Synthetic Dataset Setup Details

Figure 6: We plot examples of the synthetic dataset with 1, 2, and 4 objects.
We note that for the 1-object synthetic dataset, the only relevant object for
concept predictors is on the left side, while the right side is essentially
noise.

We develop a synthetic dataset to understand spatial locality. For this
dataset, we define 3 sizes of images, of size $1$, $2$, and $4$, with the
1-object synthetic dataset containing 2 objects, but only having concept
information on the first concept. We set the same task label for all data
points, as we focus on concept predictors, and we want to avoid interference
between the label and concept predictors. We note that each concept
corresponds to an object, and so the relevant features for each concept
correspond to the region in which the object resides. For all spatial locality
experiments, we consider five trials for the input image $\mathbf{x}^{(i)}$
when computing the spatial locality leakage.

We find that all models learn the training data perfectly, achieving 100%
concept accuracy and label accuracy across the train and test datasets. We
train CBMs that use a convolutional neural network (CNN) as their concept
predictor $g$ and test the impact of depth upon spatial locality by varying
the number of convolutional layers in $\\{3,5,7\\}$. We additionally test CBMs
that use a multi-layer perceptron (MLP) model as their concept predictors $g$
while varying the number of hidden layers across $\\{1,2,3\\}$ and the layer
width across $\\{5,10,15\\}$. We consider the impact of other factors, such as
the optimizer, weighting of the concept and task loss terms, and the
introduction of noise to the dataset, and find that these factors do not
impact the presence of spatial locality. Across all experiments, we train all
models over three distinct random seeds and report the means and standard
deviations of all metrics of interest.

##  Appendix B MLP Model Size

Depth | Width | Leakage
---|---|---
1 | 5 | 0.67 $\pm$ 0.32
| 10 | 0.78 $\pm$ 0.32
| 15 | 0.90 $\pm$ 0.14
2 | 5 | 0.64 $\pm$ 0.26
| 10 | 0.61 $\pm$ 0.29
| 15 | 0.64 $\pm$ 0.26
3 | 5 | 0.61 $\pm$ 0.07
| 10 | 0.41 $\pm$ 0.07
| 15 | 0.97 $\pm$ 0.04
Table 1: Increasing the width of models leads to increases in spatial locality
leakage for depth 1 and 3 models, while there is no pattern in depth 2 models.
Additionally, no such pattern is seen when increasing the depth of models,
showing that the width of a model might be more responsible for spatial
locality leakage than its depth.

We study whether MLP models capture spatial locality, as they present a
controlled scenario where the parameter size, along with depth and width, can
be varied arbitrarily. For MLP-based concept predictors, we see that when
using a single hidden layer we observe an increase in spatial locality leakage
as we increase the width of the hidden layer (Table 1). This trend is similar
to the one exhibited in CNN concept predictors, where larger models lead to
more spatial locality leakage. However, unexpectedly, we also find that when
the model width is fixed, and the number of hidden layers is increased, the
amount of spatial locality leakage does not necessarily increase. The reason
for this is unclear; it might be due to the small hidden layer sizes creating
an information bottleneck [30], where information gets compressed when
travelling between layers.

##  Appendix C CNN Pruning Experiments

(a)

(b)

Figure 7: We prune CNN-based concept predictors using layer and weight pruning
without retraining. We find that for both pruning strategies, accuracy
significantly drops off before spatial locality leakage does, making it
difficult to remove spatial locality leakage simply through pruning.

If model size is responsible for spatially local leakage, then model pruning
offers a potential solution to reduce model size and address spatial locality
leakage. We consider two types of pruning: layer pruning and weight pruning
[31]. In layer pruning, we prune a constant percentage of the filters in each
layer, pruning filters that have the lowest weight, while in weight pruning,
we globally prune a constant percentage of the weights based on weight norm,
setting these to zero. We note that for each type of pruning, we don’t retrain
after pruning. In Figure 7, we see that increasing the pruning percentage
decreases accuracy and spatial locality leakage for both layer and weight
pruning. However, for both of these, we see that accuracy decreases before the
spatial locality leakage does. In other words, pruning CNN models results in
significantly decreased accuracy before spatial locality leakage is, and so
pruning large models into small ones isn’t a viable strategy to eliminate
spatial locality leakage.

Figure 8: Using weight pruning then retraining models for 1 epoch leads to
models with high accuracy and low spatial locality leakage. This presents a
viable strategy to remove spatial locality leakage in large models.

To improve accuracy while leveraging pruning, we retrain models for 1 epoch
after pruning. In Figure 8, we see that retraining models after weight pruning
leads to high accuracy with low spatial locality leakage. Pruning then
retraining provides a viable strategy to improve the spatial locality leakage
of models while preserving the accuracy, though provides additional training
burdens. We plan to investigate whether such trends hold when using non-
synthetic datasets.

##  Appendix D Concept Combinations

Concept Combinations | CODA
---|---
5 | 58% $\pm$ 0%
10 | 63% $\pm$ 0%
15 | 65% $\pm$ 0%
20 | 64% $\pm$ 1%
Table 2: Increasing the number of concept combinations leads to higher CODA,
though this increases at a slow, sublinear rate.

To better understand semantic locality, we vary the number of training concept
combinations (Table 2). We randomly select $5$, $10$, $15$, and $20$ concept
combinations, and train models based on these concept combinations. As
expected, more concept combinations lead to higher CODA. However, such a trend
is relatively slow, as changing the number of concept combinations from $5$ to
$20$, a 4x increase, only improves accuracy by $6\%$. Therefore, simply
increasing the size of the dataset is not sufficient to prevent this issue.

##  Appendix E Semantic Locality Dataset

We describe our semantic locality dataset and our setup for the semantic
locality experiments. We use the dSprites dataset for the semantic locality
experiments [28]. The dSprites dataset consists of images of an object with
varying locations, shapes, and sizes. We divide the location into 2 concepts
for the x position and 2 concepts for the y position. We additionally divide
the shape into 3 concepts, one each for “heart”, “circle”, and “square.” We
have one concept for the colour, as the colour is constant across all images.
We have four concepts for the rotation, and six concepts for the size,
resulting in 18 total concepts. The task is then to predict the base 2
representation of the concept, mod 100; essentially the task forces label
predictors to have perfect knowledge of concepts, as the label relies on all
concept values. We note that CBMs achieve perfect concept and task accuracy on
the training set.

##  Appendix F Further Analysis of Semantic Locality

Figure 9: We compute the PCA accuracy using SVM models on the dimensionality
reduced dSprites data for each concept, and compare it with the CODA, which is
the accuracy on the test set when training with only a subset of concept
combinations. We see that when the PCA accuracy is perfect, there also tends
to be perfect CODA, while imperfect concepts lead to poor generalization.

Concept predictor models tend to predict concept combinations already found in
training data, which is indicative of accuracy issues for concepts. In Figure
9, we compare the CODA, which is the performance of concept predictors across
all concept combinations, with the corresponding PCA accuracy, which is the
accuracy predicted just using the SVM on dimensionality-reduced testing
points. We see that concepts with perfect PCA accuracy when predicted using
dimensionality-reduced data, tend to have a high CODA, while those with
imperfect concept accuracies have CODA as low as $6\%$. This relationship
matches with intuition, as perfectly predicted concepts tend to not be
impacted by the predictions of other concepts, leading to a high CODA. Because
many concepts have a low CODA, the overall task accuracy is 3%; the low task
accuracy is in contrast to other concepts-based scenarios, as predicting task
labels accurately requires perfect knowledge of concepts, which isn’t true for
other concept-based datasets [27]. By constructing our dataset so concept
combinations in the training are not representative of testing, we reveal that
concept predictors erroneously pick up on relationships between semantically
independent concepts.

##  Appendix G Using Independent Models

We compare the locality properties when using independent models instead of
joint models when training CBMs. Independent models are trained by training
the concept predictor and label predictor separately, so that leakage between
the task label and concept label is prevented. By training with independent
models, we investigate whether leakage between the task label and concept
label is responsible for the lack of locality exhibited by some models in the
spatial and semantic locality scenarios.

With spatial locality, we find that the results are unchanged when using
independent models. We test out independent models on the $7$ layer concept
predictor. Originally, we found that all models had spatial locality leakage
of $1$ across all runs. We find that the same trend is repeated in the
independent model case; all models exhibit a spatial locality leakage of $1$ .

With the semantic locality case, we find that the overall task accuracy
improves from 3% to 8%. While this improvement is positive, CBM models are
still unable to consistently predict correct labels, which is reflective of
issues with the concept predictor. We intend to investigate this further in
future work.

##  Appendix H Masking experiment Details

We provide details on our experiment involves various masks with the CUB
dataset. We aim to see if the type of maksing impacts concept prediction. For
our concept predictor, we use a three-layer CNN, then construct a mask for
each concept, for each of three different seeds, and for $\epsilon$ across
$\\{3.3\%,6.6\%,10\%,13.3\%,16.6\%\\}$. We then compute the average concept
change for a given concept group $r(j)$, with a non-masked input $x$ and a
masked input $x^{\prime}$ as:

$\frac{1}{\sum_{j^{\prime}=1,r(j)=r(j^{\prime})}^{k}1}\sum_{j^{\prime}=1,r(j)=r(j^{\prime})}^{k}|g(x)_{j^{\prime}}-g(x^{\prime})_{j^{\prime}}|$
(2)

We then average this across all concept groups and random seeds.


# Collusion-resistant fingerprinting of parallel content channels

Basheer Joudeh, Boris Škorić

###### Abstract

The fingerprinting game is analysed when the coalition size $k$ is known to
the tracer, but the colluders can distribute themselves across $L$ TV
channels. The collusion channel is introduced and the extra degrees of freedom
for the coalition are made manifest in our formulation. We introduce a payoff
functional that is analogous to the single TV channel case, and is conjectured
to be closely related to the fingerprinting capacity. For the binary alphabet
case under the marking assumption, and the restriction of access to one TV
channel per person per segment, we derive the asymptotic behavior of the
payoff functional. We find that the value of the maximin game for our payoff
is asymptotically equal to $L^{2}/k^{2}2\ln 2$, with optimal strategy for the
tracer being the arcsine distribution, and for the coalition being the
interleaving attack across all TV channels, as well as assigning an equal
number of colluders across the $L$ TV channels.

##  1 Introduction

###  1.1 Collusion resistant fingerprinting

Fingerprinting, also known as forensic watermarking, is a technique for
tracing the origin and distribution of digital content. Before distribution,
the content is modified by embedding an imperceptible watermark, which is
unique for each recipient. When an unauthorized copy of the content is
released, the watermark in this copy reveals information about the identities
of those who created the copy. A tracing algorithm (also called a decoder)
outputs a list of suspicious users. This procedure is known as forensic
watermarking or traitor tracing.

The most powerful attack against watermarking is the collusion attack, where
multiple users (the ‘coalition’) combine their differently watermarked
versions of the same content; the detected differences partly reveal the
locations of the hidden marks and allow for an informed attack. Various
collusion-resistant codes have been developed, most notably the class of bias-
based codes, introduced by G. Tardos in 2003 [17, 18]. For each watermarking
symbol position the tracer first generates a bias $w\in(0,1)$ drawn from a
distribution $f_{W}$ and then assigns to each user a watermark symbol ‘1’ with
probability $w$ and ‘0’ with probability $1-w$. Work on bias-based codes
includes improved analyses [2, 6, 7, 11, 16, 24, 23], code modifications [8,
13, 14], advanced decoders [1, 4, 12, 15, 5, 19, 20] and generalizations [3,
21, 22, 25]. Bias-based codes achieve the asymptotically optimal relationship
$n\propto k^{2}$, where $n$ is the sufficient code length, and $k$ is the
coalition size.

An important result was finding the asymptotic saddlepoint of the information-
theoretic maximin game [8, 10, 9] in the case of the Restricted Digit Model111
In the Restricted Digit Model, colluders must output a symbol that has been
received by at least one of them.  and joint decoding.

The saddlepoint is a pair (bias distribution $f_{W}$, attack strategy) such
that it is disadvantageous for either party to depart from their strategy.
With increasing $k$, the solution of the max-min game for the binary
fingerprinting alphabet gets closer to the combination222 This $f_{W}$ is
known as the arcsine distribution, $f_{W}(w){\rm d}w=\frac{1}{\pi}{\rm
d}\arcsin(2w-1)$.  ($f_{W}=\frac{1}{\pi\sqrt{w(1-w)}}$ , attack =
Interleaving). In the Interleaving attack the colluders output the symbol of
one colluder chosen uniformly at random.

Knowing the location of the saddlepoint allows the tracer to build a universal
decoder that works optimally against the saddlepoint attack and that works
well against all other attacks too. What is usually not considered in studies
of forensic watermarking is that most pirate decoder boxes observed in
practice give access to multiple TV channels in parallel. Hence, attackers
have an additional degree of freedom that has not yet been explored in the
academic literature: which TV channel to collude on at which point in time.
The information-theoretic maximin game has not yet been studied for multiple
TV channels attacks.

###  1.2 Contributions and outline

We study the information-theoretic maximin game for the binary fingerprinting
scenario with multiple parallel TV channels which are being attacked
simultaneously by a set of colluders under the Restricted Digit Model. We
consider the static case, as opposed to dynamic traitor tracing, i.e. we do
not allow the parties to adapt their strategy as a function of symbols
observed previously. We assume that each attacker can tune into merely one
channel, and furthermore we consider only attack strategies in which the
colluders take equal risk, and all TV channels are treated as being equally
important.

Under these restrictions we study the mutual information
$I(\hat{Y};\hat{Z},\hat{C}|\hat{W})$, which is a straightforward
generalisation of the single-channel figure of merit $I(Y;M|W)$. Here the hat
indicates a vector in which each entry comes from one TV channel; the $Y$ is
the colluders’ output, the $M$ stands for the coalition’s symbol tally in the
single TV channel case, while $(\hat{Z},\hat{C})$ represent the coalition’s
symbol tally in the multiple TV channel case, and $W$ is the bias. Although
the generalised figure of merit looks simple, the multiple TV channel maximin
game is more complicated than the single TV channel case. If a pirate is
active in one TV channel, then this excludes the possibility that they are
active in another TV channel. This exclusion causes a nontrivial dependence
between the TV channels, which complicates the analysis: it is not a priori
clear if the multi-channel attack can be treated as a set of independent
single-channel attacks.

  * •

We find the solution of the maximin game for the $k\to\infty$ limit of the
payoff function $I(\hat{Y};\hat{Z},\hat{C}|\hat{W})$, using the same technique
as Huang and Moulin [9]. The optimal bias distribution for the tracer is the
arcsine distribution, and the optimal colluder strategy within each channel is
Interleaving. Moreover, it is optimal for the attackers to spread evenly over
the channels. Although the result is far from surprising, the proof is less
simple than one would have hoped for. The proof needs some careful handling of
expressions with different orders in $1/k$ that arise from different attack
strategies for spreading out over the channels.

  * •

We present an alternative payoff functional, namely the mutual information
$I(\hat{Y};\hat{X}_{\cal K}|\hat{W})$. Here $\hat{X}_{\cal K}$ stands for the
part of the code matrices in all the TV channels that can potentially be tuned
into by the coalition $\cal K$. We argue that the two payoffs have the same
maximin game asymptotically, and this leads us to conjecture that the optimal
strategies hold for $I(\hat{Y};\hat{X}_{\cal K}|\hat{W})$ as well, and that
the fingerprinting capacity asymptotically behaves like $L^{2}/(k^{2}2\ln 2)$.

In Section 2 we introduce the multiple TV channels model and the payoff
function. In Section 3 we derive the maximin solution for the asymptotic
payoff. We discuss the alternative payoff and fingerprinting capacity in
Section 4. We summarize and suggest future work in Section 5. Before we
proceed, we introduce common notations used throughout the manuscript.

###  1.3 Notation

Let $m$ be the number of users;
$\mathcal{M}\overset{\Delta}{=}\\{1,2,\dots,m\\}$ the index set for all users;
$\mathcal{X}\overset{\Delta}{=}\\{0,1,\dots,q-1\\}$ denote the q-ary
fingerprinting alphabet; $n$ denote the code length;
$\mathcal{K}\overset{\Delta}{=}\\{j_{1},\dots,j_{K}\\}\subset\mathcal{M}$ the
index set of the coalition, where $K$ is the number of colluders; $k$ is the
nominal coalition size333In this work, we do not make a distinction between
$K$ and $k$, i.e. we assume the real number of colluders is known to the
tracer.; $L$ the number of TV channels;
$\mathcal{L}\overset{\Delta}{=}\\{1,2,\dots,L\\}$ the index set for all TV
channels; $\tilde{L}$ the number of TV channels a user can tune in to
simultaneously;
$(\cdot)_{\mathcal{K}}\overset{\Delta}{=}\\{(\cdot)_{j}:j\in\mathcal{K}\\}$;
vectors are denoted by boldface letters; $L-$tuples are denoted by
$\hat{(\cdot)}\overset{\Delta}{=}((\cdot)^{1},\dots,(\cdot)^{L})$; $|(\cdot)|$
denotes the $L^{1}$-norm of a vector or the cardinality of a set, depending on
the argument. We denote the Kronecker delta by $\delta(i,j)$, which is equal
to 1 when $i=j$, and 0 otherwise. We use the following notation for asymptotic
relations: Let $f(k)$ and $g(k)$ be two functions defined on the real numbers.
$f(k)=O(g(k))$ if $\exists c>0,k^{*}>0$ such that $f(k)\leq cg(k)$, $\forall
k\geq k^{*}$. $f(k)=o(g(k))$ if $f(k)/g(k)$ tends to 0. $f(k)=w(g(k))$ if
$f(k)/g(k)$ tends to $\infty$. $f(k)\sim g(k)$ if $f(k)/g(k)$ tends to a non-
zero constant. $f(k)\rightarrow g(k)$ if $f(k)/g(k)$ tends to 1.

##  2 Channel Model

###  2.1 Channel law

In the single channel case [9], the tracer produces codewords for $m$ users in
a random fashion. This is achieved as follows: for each of the $n$ segments a
bias vector $\mathbf{W}$ is drawn from a distribution $f_{\mathbf{W}}$ chosen
by the tracer, and $X_{j}\in\\{0,1,\dots,q-1\\}$ is assigned for user $j$
according to a categorical distribution with parameters
$\\{W_{i}\\}_{i=0}^{q-1}$:

$\mathbb{P}(X_{j}=x|\mathbf{W}=\mathbf{w})=w_{x}.$ (1)

The users are assigned their codewords independently by the tracer, and hence
we also have:

$\mathbb{P}(X_{1}=x_{1},\dots,X_{m}=x_{m}|\mathbf{W}=\mathbf{w})=\prod_{j=1}^{m}w_{x_{j}}.$
(2)

Note that we do not include a segment index since this procedure is repeated
for all segments independently, hence producing the codewords
$\\{\mathbf{X}_{j}\\}_{j=1}^{m}$, where
$\mathbf{X}_{j}=(X_{j,1},\dots,X_{j,n})$.

We now describe an analogous procedure for producing the codewords of $m$
users in the case of multiple TV channels. We adopt the same notation as in
the case of a single TV channel, and one can recover the single TV channel
description by setting $L=1$ in what follows. The tracer produces codewords
$\\{\hat{\mathbf{X}}_{1},\dots,\hat{\mathbf{X}}_{m}\\}$ with
$\mathbf{X}_{j}^{l}\in\\{0,1,\dots,q-1\\}^{n}$ denoting the $l$-th codeword
for user $j$. This is done by choosing $L$ i.i.d bias vectors at each segment,
and each segment is independent of other segments. That is, let
$\hat{\mathbf{W}}_{i}$ be the bias vectors at segment $i$, then:

$\displaystyle
f_{\hat{\mathbf{W}}_{1},\dots,\hat{\mathbf{W}}_{n}}(\hat{\mathbf{w}}_{1},\dots,\hat{\mathbf{w}}_{n})$
$\displaystyle=\prod_{i=1}^{n}f_{\hat{\mathbf{W}}_{i}}(\hat{\mathbf{w}}_{i})=\prod_{i=1}^{n}\prod_{l=1}^{L}f_{\mathbf{W}^{l}_{i}}(\mathbf{w}^{l}_{i})=\prod_{i=1}^{n}\prod_{l=1}^{L}f_{\mathbf{W}}(\mathbf{w}^{l}_{i}),$
(3)

For any $l\in\\{1,\dots,L\\}$ and $i\in\\{1,\dots,n\\}$,
$\\{X^{l}_{j,i}\\}_{j=1}^{m}$ are i.i.d and drawn from a categorical
distribution:

$\mathbb{P}(X^{l}_{1,i}=x_{1},\dots,X^{l}_{m,i}=x_{m}|\mathbf{W}^{l}_{i}=\mathbf{w})=\prod_{j=1}^{m}w_{x_{j}}.$
(4)

The pirates receive codewords $\hat{\mathbf{X}}_{\mathcal{K}}$, and produce
the output $\hat{\mathbf{Y}}$, where $\mathbf{Y}^{l}\in\mathcal{Y}^{n}$ (we
assume an RDM setting, i.e. $\mathcal{Y}=\mathcal{X}$), according to a pmf
$p_{\hat{\mathbf{Y}}|\hat{\mathbf{X}}_{\mathcal{K}},\hat{\mathbf{S}}}$, where
$\\{\hat{S}_{i}\\}_{i=1}^{n}$ is the assignment of pirates to channels at each
segment, i.e. $S^{l}_{i}$ is a random subset of $\mathcal{K}$ that we assume
is independent of $X^{l}_{\mathcal{K},i}$. Let $\tilde{L}$ be the maximum
number of channels a single user can simultaneously tune in to444We assume
pirates have the same accessability constraints as normal users, i.e. access
to the same hardware., then for any segment $i$ and TV channel $l$, a
realization $s^{l}_{i}$ is an assignment

$s^{l}_{i}:l\mapsto 2^{\mathcal{K}},$ (5)

that respects the following:

$\displaystyle s^{l}_{i}\neq\emptyset,$ (6)
$\displaystyle\bigcup_{l=1}^{L}s^{l}_{i}=\mathcal{K},$ (7)
$\displaystyle\bigcap_{l\in\tilde{\mathcal{L}}}s_{i}^{l}=\emptyset,\hskip
2.84526pt\forall\tilde{\mathcal{L}}\subseteq\mathcal{L},\
|\tilde{\mathcal{L}}|>\tilde{L}.$ (8)

Equation (8) states that a single pirate can not be assigned to more than
$\tilde{L}$ TV channels. We further assume memoryless-ness and no feedback of
the collusion channel, which implies:

$p_{\hat{\mathbf{Y}}|\hat{\mathbf{X}}_{\mathcal{K}},\hat{\mathbf{S}}}(\hat{\mathbf{y}}|\hat{\mathbf{x}}_{\mathcal{K}},\hat{\mathbf{s}})=\prod_{i=1}^{n}p_{\hat{Y}|\hat{X}_{\mathcal{K}},\hat{S}}(\hat{y}_{i}|\hat{x}_{\mathcal{K},i},\hat{s}_{i}),$
(9)

and in what follows, we drop the segment index on random variables. In this
work, we restrict to the case of each user having access to only one of the TV
channels at each segment, i.e. $\tilde{L}=1$ (and so $K\geq L$). In this case
$\\{s^{l}\\}_{l=1}^{L}$ form a partition of $\mathcal{K}$, or more precisely,
$\hat{s}$ defines a weak ordering of $\mathcal{K}$ where pirates assigned to
the same TV channel are tied. The size of the support for $\hat{S}$ (denoted
by $\hat{\mathcal{S}}$) is then given by555$\genfrac{\\{}{\\}}{0.0pt}{}{K}{L}$
counts the number of ways we can partition $\mathcal{K}$ into $L$ non-empty
subsets, while the $L!$ factor orders them across TV channels. Otherwise, it
can be viewed as putting $K$ distinguishable balls into $L$ distinguishable
bins.:

$\displaystyle|\hat{\mathcal{S}}|=L!\,\genfrac{\\{}{\\}}{0.0pt}{}{K}{L},$ (10)

where $\genfrac{\\{}{\\}}{0.0pt}{}{a}{b}$ denotes Stirling numbers of the
second kind. If we instead disregard the identity of the colluders assigned to
each channel, and only keep their numbers, the support size would shrink
to666It can be viewed as putting $K$ indistinguishable balls into $L$
distinguishable bins, which can be easily proved using stars and bars.
$\binom{K-1}{L-1}$. Furthermore, if we also disregard the TV channel labels,
the support size would become $P(K,L)$, which is the number of partitions of
$K$ into exactly $L$ parts. It is common in the literature to assume colluder
symmetry, i.e. all pirates share the risk equally. Furthermore, it is logical
to assume TV channel symmetry, i.e. all $L$ TV channels are equally important.
Therefore in practice, finding an optimal distribution over $\\{\hat{s}\\}$ is
the same as finding an optimal distribution over $P(K,L)$ partitions. Since
$\tilde{L}=1$, i.e. $\\{s^{l}\\}_{l=1}^{L}$ are disjoint, then we can simplify
equation (9) by writing:

$p_{\hat{\mathbf{Y}}|\hat{\mathbf{X}}_{\mathcal{K}},\hat{\mathbf{S}}}(\hat{\mathbf{y}}|\hat{\mathbf{x}}_{\mathcal{K}},\hat{\mathbf{s}})=\prod_{i=1}^{n}\prod_{l=1}^{L}p_{Y^{l}|X^{l}_{S^{l}},S^{l}}(y^{l}_{i}|x^{l}_{s^{l}_{i},i},s^{l}_{i}),$
(11)

i.e. colluders on different TV channels do not communicate after being
assigned. Applying TV channel symmetry to (11), i.e. removing any bias towards
a particular TV channel in the pirates’ strategy (it is true for the tracer,
i.e. $\\{X^{l}_{\mathcal{K}}\\}_{l=1}^{L}$ are i.i.d.), then we can write:

$p_{\hat{\mathbf{Y}}|\hat{\mathbf{X}}_{\mathcal{K}},\hat{\mathbf{S}}}(\hat{\mathbf{y}}|\hat{\mathbf{x}}_{\mathcal{K}},\hat{\mathbf{s}})=\prod_{i=1}^{n}\prod_{l=1}^{L}p_{Y|X_{S},S}(y^{l}_{i}|x^{l}_{s^{l}_{i},i},s^{l}_{i}).$
(12)

Given $x_{s}$ (a realization of $X_{S}$), we define the tally vector
$\mathbf{m}$ as the following:

$\displaystyle\mathbf{m}$
$\displaystyle\overset{\Delta}{=}(m_{0},\dots,m_{q-1}),$ (13) $\displaystyle
m_{\alpha}$ $\displaystyle\overset{\Delta}{=}|\\{j\in s:x_{j}=\alpha\\}|.$
(14)

Imposing colluder symmetry, we can write:

$p_{\hat{\mathbf{Y}}|\hat{\mathbf{X}}_{\mathcal{K}},\hat{\mathbf{S}}}(\hat{\mathbf{y}}|\hat{\mathbf{x}}_{\mathcal{K}},\hat{\mathbf{s}})=\prod_{i=1}^{n}\prod_{l=1}^{L}p_{Y|\mathbf{M}}(y^{l}_{i}|\mathbf{m}^{l}_{i}),$
(15)

where $\mathbf{m}^{l}_{i}$ is the tally vector received by the pirates
assigned to the $l$-th TV channel at segment $i$, and we assume
$p_{Y|\mathbf{M}}$ abides by the marking assumption. Note that unlike the
single TV channel777In the single channel case this would be equal to $K$,
which is usually unknown but constant. case ($L=1$),
$|\mathbf{M}^{l}|=|S^{l}|\overset{\Delta}{=}C^{l}$ is a random variable, which
is the number of colluders assigned to attack TV channel $l$. Another
implication of the TV channel symmetry condition is the following:

$p_{C^{l}}(c^{l})=p_{C}(c^{l}),$ (16)

i.e. the number of pirates assigned to attack different TV channels must be
identically distributed. This follows since $p_{\hat{C}}$ together with
$p_{Y|\mathbf{M}}$ form the pirates’ strategy. Figure 1 showcases the process
of producing the colluders outputs across the $L$ TV channels. Note that from
colluder symmetry, $p_{\hat{S}|\hat{C}}$ is specified by the rule:

$p_{\hat{S}|\hat{C}}(\hat{s}|\hat{c})=\begin{cases}\dfrac{1}{\binom{k}{c^{1},c^{2},\dots,c^{L}}},&|s^{l}|=c^{l},\
\forall l\in\mathcal{L}\\\ 0,&\mathrm{otherwise}\end{cases},$ (17)

where $\binom{k}{c^{1},c^{2},\dots,c^{L}}$ is the multinomial coefficient.

######  Lemma 1.

$\\{\mathbf{M}^{l}\\}_{l=1}^{L}$ are identically distributed.

###### Proof.

888Summations over $\mathbf{w}$ can be appropriately replaced by integrals in
the case of $f_{\mathbf{W}}$ being a density.

$\displaystyle
p_{\mathbf{M}^{l}}(\mathbf{m})=\sum_{\mathbf{w}}p_{\mathbf{M}^{l}|\mathbf{W}^{l}}(\mathbf{m}|\mathbf{w})f_{\mathbf{W}}(\mathbf{w})$
(18)
$\displaystyle=\sum_{c}\sum_{\mathbf{w}}p_{C^{l}}(c)p_{\mathbf{M}^{l}|\mathbf{W}^{l},C^{l}}(\mathbf{m}|\mathbf{w},c)f_{\mathbf{W}}(\mathbf{w})$
$\displaystyle=\sum_{c}\sum_{\mathbf{w}}p_{C}(c)p_{\mathbf{M}^{l}|\mathbf{W}^{l},C^{l}}(\mathbf{m}|\mathbf{w},c)f_{\mathbf{W}}(\mathbf{w})$
$\displaystyle\overset{\mathrm{(a)}}{=}\sum_{c}\sum_{\mathbf{w}}p_{C}(c)p_{\mathbf{M}|\mathbf{W},C}(\mathbf{m}|\mathbf{w},c)f_{\mathbf{W}}(\mathbf{w})=p_{\mathbf{M}}(\mathbf{m}),$

where in $\mathrm{(a)}$ we used the fact that
$p_{\mathbf{M}^{l}|\mathbf{W}^{l},C^{l}}$ is a multinomial distribution
regardless of $l$. ∎

######  Lemma 2.

$\\{Y^{l}\\}_{l=1}^{L}$ are identically distributed.

###### Proof.

$\displaystyle
p_{Y^{l}}(y^{l})=\sum_{\mathbf{m}^{l}}p_{Y^{l}|\mathbf{M}^{l}}(y^{l}|\mathbf{m}^{l})p_{\mathbf{M}^{l}}(\mathbf{m}^{l})=\sum_{\mathbf{m}^{l}}p_{Y|\mathbf{M}}(y^{l}|\mathbf{m}^{l})p_{\mathbf{M}}(\mathbf{m}^{l})=p_{Y}(y^{l}),$
(19)

where the equalities follow from Lemma 1 and TV channel symmetry
($p_{Y|\mathbf{M}}$ is part of the pirates’ strategy). ∎

Figure 1: A schematic diagram that shows the watermarking/collusion process.
Arrows indicate drawing realizations from a pmf, while straight lines indicate
use of those realizations. White boxes correspond to the tracer, while grey
boxes correspond to the coalition.

###  2.2 Payoff functional

For any $l\in\\{1,\dots,L\\}$, we define the single channel payoff as:

$\dfrac{I(Y^{l};\mathbf{M}^{l}|C^{l}=c,\mathbf{W}^{l})}{c}=\dfrac{I(Y;\mathbf{M}|C=c,\mathbf{W})}{c}\overset{\Delta}{=}\mathcal{I}_{c}(\mathbf{W},p_{Y|\mathbf{M},C=c}),$
(20)

where equality follows from Lemma 1, Lemma 2, and
$\\{\mathbf{W}^{l}\\}_{l=1}^{L}$ being i.i.d. In analogy to the single channel
case [9], we define the multi channel payoff as the following:

$J_{k,L}[f_{\mathbf{W}},p_{Y|\mathbf{M}},p_{\hat{C}}]\overset{\Delta}{=}\dfrac{I(\hat{Y};\hat{\mathbf{M}}|\hat{\mathbf{W}})}{k}.$
(21)

From here on, we restrict our attention to the binary alphabet case
$\mathcal{X}=\\{0,1\\}=\mathcal{Y}$, and we wish to evaluate
$J_{k,L}[f_{\mathbf{W}},p_{Y|\mathbf{M}},p_{\hat{C}}]$ for this case. We
define the random variables $\\{Z^{l}\\}_{l=1}^{L}$ by:

$\displaystyle Z^{l}\overset{\Delta}{=}\sum_{j\in S^{l}}X^{l}_{j},$ (22)

which counts the number of 1s received by the pirates assigned to the $l$-th
TV channel. Equation (16) and Lemma 1 imply that $\\{Z^{l}\\}_{l=1}^{L}$ and
$\\{C^{l}\\}_{l=1}^{L}$ are sets of identically distributed random variables.
Therefore, we can talk about $Z$ and $C$ with no reference to a TV channel
label. We also use the scalar bias $W$ instead of $\mathbf{W}$, which is the
probability of assigning a user the symbol 1. Using this notation, we define
the following:

$\displaystyle
p_{Z|C,W}(z|c,w)\overset{\Delta}{=}\alpha_{z}(w,c)=\begin{cases}\binom{c}{z}w^{z}(1-w)^{c-z},&0\leq
z\leq c\\\ 0,&\text{otherwise}\end{cases},$ (23) $\displaystyle
p_{Z,C|W}(z,c|w)=p_{C|W}(c|w)p_{Z|C,W}(z|c,w)=p_{C}(c)\alpha_{z}(c,w),$ (24)
$\displaystyle\pi_{z,c}\overset{\Delta}{=}p_{Y|Z,C}(1|z,c),\quad 0\leq z\leq
c.$ (25)

Note that $(Z^{l},C^{l})$ is a sufficient statistic for determining $Y^{l}$,
while $(W^{l},C^{l})$ is a sufficient statistic for determining $Z^{l}$,
therefore we have the following (keeping in mind that $\\{W^{l}\\}_{l=1}^{L}$
are i.i.d.):

$\displaystyle
p_{\hat{Y}|\hat{Z},\hat{C},\hat{W}}(\hat{y}|\hat{z},\hat{c},\hat{w})$
$\displaystyle=\prod_{l=1}^{L}p_{Y^{l}|Z^{l},C^{l}}(y^{l}|z^{l},c^{l})$ (26)
$\displaystyle=\prod_{l=1}^{L}p_{Y^{l}|Z^{l},C^{l},W^{l}}(y^{l}|z^{l},c^{l},w^{l})$
$\displaystyle=\prod_{l=1}^{L}p_{Y|Z,C,W}(y^{l}|z^{l},c^{l},w^{l}),$
$p_{\hat{Z}|\hat{C},\hat{W}}(\hat{z}|\hat{c},\hat{w})=\prod_{l=1}^{L}p_{Z^{l}|C^{l},W^{l}}(z^{l}|c^{l},w^{l})=\prod_{l=1}^{L}\alpha_{z^{l}}(w^{l},c^{l}).$
(27)

######  Lemma 3.

$p_{\hat{Y}|\hat{C},\hat{W}}(\hat{y}|\hat{c},\hat{w})=\prod_{l=1}^{L}p_{Y|C,W}(y^{l}|c^{l},w^{l})$.

###### Proof.

$\displaystyle
p_{\hat{Y}|\hat{C},\hat{W}}(\hat{y}|\hat{c},\hat{w})=\sum_{\hat{z}}p_{\hat{Y}|\hat{C},\hat{Z},\hat{W}}(\hat{y}|\hat{c},\hat{z},\hat{w})p_{\hat{Z}|\hat{C},\hat{W}}(\hat{z}|\hat{c},\hat{w})$
(28)
$\displaystyle=\sum_{z^{1}}\cdots\sum_{z^{L}}\prod_{l=1}^{L}p_{Y^{l}|Z^{l},C^{l},W^{l}}(y^{l}|z^{l},c^{l},w^{l})p_{Z^{l}|C^{l},W^{l}}(z^{l}|c^{l},w^{l})$
$\displaystyle=\sum_{z^{1}}\cdots\sum_{z^{L}}\prod_{l=1}^{L}p_{Y,Z|C,W}(y^{l},z^{l}|c^{l},w^{l})=\prod_{l=1}^{L}p_{Y|C,W}(y^{l}|c^{l},w^{l}).$

∎

######  Lemma 4.

$I(\hat{Y};\hat{Z}|\hat{C}=\hat{c},\hat{W})=\sum_{l=1}^{L}c^{l}\mathcal{I}_{c^{l}}(W,\bm{\pi}_{c^{l}})$,
$\bm{\pi}_{c}\overset{\Delta}{=}(\pi_{0,c},\cdots,\pi_{c,c})$.

###### Proof.

$\displaystyle
I(\hat{Y};\hat{Z}|\hat{C}=\hat{c},\hat{W}=\hat{w})\overset{\mathrm{(a)}}{=}H(\hat{Y}|\hat{C}=\hat{c},\hat{W}=\hat{w})-H(\hat{Y}|\hat{Z},\hat{C}=\hat{c},\hat{W}=\hat{w})$
(29)
$\displaystyle\overset{\mathrm{(b)}}{=}H(\hat{Y}|\hat{C}=\hat{c},\hat{W}=\hat{w})-\sum_{\hat{z}}p_{\hat{Z}|\hat{C},\hat{W}}(\hat{z}|\hat{c},\hat{w})H(\hat{Y}|\hat{Z}=\hat{z},\hat{C}=\hat{c},\hat{W}=\hat{w})$
$\displaystyle\overset{\mathrm{(c)}}{=}\sum_{l=1}^{L}H(Y|C=c^{l},W=w^{l})$
$\displaystyle-\sum_{\hat{z}}\left(\prod_{l^{\prime}=1}^{L}p_{Z|C,W}(z^{l^{\prime}}|c^{l^{\prime}},w^{l^{\prime}})\right)\sum_{l=1}^{L}H(Y|Z=z^{l},C=c^{l},W=w^{l})$
$\displaystyle\overset{\mathrm{(d)}}{=}\sum_{l=1}^{L}H(Y|C=c^{l},W=w^{l})-\sum_{l=1}^{L}\sum_{z^{l}}p_{Z|C,W}(z^{l}|c^{l},w^{l})H(Y|Z=z^{l},C=c^{l},W=w^{l})$
$\displaystyle\overset{\mathrm{(e)}}{=}\sum_{l=1}^{L}I(Y;Z|C=c^{l},W=w^{l}),$

where $\mathrm{(a)}$ and $\mathrm{(b)}$ follow from the definitions of
conditional mutual information and conditional entropy; $\mathrm{(c)}$ follows
from equations (26), (27), and Lemma 3; $\mathrm{(d)}$ follows by direct
computation; $\mathrm{(e)}$ follows from the definition of conditional mutual
information. Finally, it is straightforward to confirm that

$I(\hat{Y};\hat{Z}|\hat{C}=\hat{c},\hat{W})=\sum_{l=1}^{L}I(Y;Z|C=c^{l},W).$
(30)

∎

######  Lemma 5.

$\mathcal{I}_{c}(W,\bm{\pi}_{c})$ coincides with the single channel payoff for
$c$ pirates as defined in [9].

###### Proof.

The pirate strategy consists of $p_{\hat{C}}$, as well as the vectors
$\\{\bm{\pi}_{c^{\prime}}\\}_{c^{\prime}=1}^{k-L+1}$. Note that
$\mathcal{I}_{c}(W,\bm{\pi}_{c})$ is independent of $p_{\hat{C}}$ and all
$\\{\bm{\pi}_{c^{\prime}}:c^{\prime}\neq c\\}$, i.e. it only depends on
$f_{W}$ and $\bm{\pi}_{c}$. ∎

######  Lemma 6.

$2\ln 2\hskip 1.42262ptc^{2}\mathcal{I}_{c}(W,\bm{\pi}_{c})\geq
4\left[{\int}_{0}^{1}\dfrac{dw}{f_{W}(w)w(1-w)}\right]^{-1}$.

###### Proof.

This follows from Theorem 7 in [9]. ∎

##  3 Asymptotic Theorem

We wish to obtain the asymptotic behavior of the payoff given in equation (21)
(for $q=2,\tilde{L}=1$), as well as the solution to the asymptotic maximin
game in analogy to the single TV channel case. For the single TV channel case
[9], this is referred to as the asymptotic saddle point value, which is the
limit of the maximin value of the payoff as the number of pirates is sent to
infinity. This is also accompanied by the asymptotic optimal strategies for
both tracer and pirates, which are the asymptotic solutions to the maximin
game. However, as this makes logical sense in terms of taking the limit of the
maximin game, this is usually not solved in the same way as it is formulated.
Instead of taking the limit of a sequence of optimal payoffs (and optimal
strategies), which is not possible given no closed form solution exists for
either, the payoff is approximated for large number of pirates and solved in
the limit. This can be justified if the optimal payoff converges uniformly in
the limit, which is usually glossed over in the literature. Nevertheless, we
shall adopt the same approach and write down an expansion of our payoff
function. In analogy to the single channel case, we make the following
regularity assumptions:

  * •

For any $c\in\\{1,\dots,k-L+1\\}$, there exists a bounded, twice
differentiable function $g_{c}(x)$ for $x\in[0,1]$ with $g(0)=0$ and $g(1)=1$
such that:

$\displaystyle\pi_{z,c}=g_{c}\left(\dfrac{z}{c}\right),\quad\forall
z\in\\{0,\dots,c\\},$
$\displaystyle\lim_{k\to\infty}g_{c}(x)\overset{\Delta}{=}g(x),\hskip
5.69054ptc\in w(1).$ (31)

######  Lemma 7.

Let $G[g_{c}(w)]\overset{\Delta}{=}\arccos\left[1-2g_{c}(w)\right]$, and
$\mathcal{J}[g_{c}(w)]\overset{\Delta}{=}w(1-w)\left[G^{\prime}(w)\right]^{2}$,
where the derivative is w.r.t $w$. Let
$\bar{\mathcal{J}}[g_{c}(W)]\overset{\Delta}{=}\mathbb{E}_{f_{W}}\left[\mathcal{J}\left[g_{c}(W)\right]\right]$
then we can write:

$\mathcal{I}_{c}(W,\bm{\pi}_{c})=\dfrac{1}{c^{2}2\ln
2}\bar{\mathcal{J}}[g_{c}(W)]+o\left(\dfrac{1}{c^{2}}\right).$ (32)

###### Proof.

This follows from Theorem 8 in [9]. ∎

######  Lemma 8.

$\bar{\mathcal{J}}[g(W)]\geq\pi^{2}\left[{\int}_{0}^{1}\dfrac{dw}{f_{W}(w)w(1-w)}\right]^{-1}$,
with equality iff $g(w)=g_{\mathrm{opt}}(w)$ given by:

$g_{\mathrm{opt}}(w)=\dfrac{1}{2}\left[1-\cos\left(\dfrac{\pi{\int}_{0}^{w}\dfrac{dv}{f_{W}(v)v(1-v)}}{{\int}_{0}^{1}\dfrac{dv}{f_{W}(v)v(1-v)}}\right)\right].$
(33)

###### Proof.

This is Lemma 7 in [9]. ∎

For $q=2,\tilde{L}=1$, we can rewrite equation (21) as:

$\displaystyle J_{k,L}[f_{W},p_{Y|Z,C},p_{\hat{C}}]$
$\displaystyle=k^{-1}I(\hat{Y};\hat{Z}|\hat{C},\hat{W})+k^{-1}I(\hat{Y};\hat{C}|\hat{W})$
(34)
$\displaystyle=k^{-1}\sum_{\hat{c}}p_{\hat{C}}(\hat{c})\sum_{l=1}^{L}c^{l}\mathcal{I}_{c^{l}}(W,\bm{\pi}_{c^{l}})+k^{-1}I(\hat{Y};\hat{C}|\hat{W})$
$\displaystyle=k^{-1}L\sum_{c}p_{C}(c)c\mathcal{I}_{c}(W,\bm{\pi}_{c})+k^{-1}I(\hat{Y};\hat{C}|\hat{W}),$

where the second equality follows from Lemma 4, and the third equality follows
from $\\{C^{l}\\}_{l=1}^{L}$ having the same marginal, as dictated by
$p_{\hat{C}}$ being symmetric under permutations (TV channel symmetry), i.e.
$C$ denotes the number of pirates assigned to any TV channel.

######  Lemma 9.

Let
$\tilde{J}_{k,L}[f_{W},p_{Y|Z,C},p_{C}]\overset{\Delta}{=}\sum_{c}p_{C}(c)\dfrac{c}{k}\mathcal{I}_{c}(W,\bm{\pi}_{c})$,
then an asymptotically optimal999An asymptotically optimal sequence of
strategies for the pirates is one that produces the lowest value for the
payoff in the limit. $p_{C}$ for $\tilde{J}$ must obey:

$\lim_{k\to\infty}\dfrac{p_{C}(c)k^{\alpha}}{c^{\alpha}}<\infty,$ (35)

for some $\alpha\geq 1$, and $\tilde{J}$ optimally decays like $1/k^{2}$.

###### Proof.

We know that $c$ can at most grow as a fraction of $k$, that is, the value
$q\overset{\Delta}{=}c/k$ can only belong to $[0,1]$ in the limit. That is, we
can divide the summation in $\tilde{J}$ as follows:

$\displaystyle\tilde{J}=$ $\displaystyle\sum_{c\sim
k}p_{C}(c)\dfrac{c}{k}\left(\dfrac{1}{c^{2}2\ln
2}\bar{\mathcal{J}}[g_{c}(W)]+o\left(\dfrac{1}{c^{2}}\right)\right)$ (36)
$\displaystyle+\sum_{c\in w(1)\cap
o(k)}p_{C}(c)\dfrac{c}{k}\left(\dfrac{1}{c^{2}2\ln
2}\bar{\mathcal{J}}[g_{c}(W)]+o\left(\dfrac{1}{c^{2}}\right)\right)$
$\displaystyle+\sum_{c\in
O(1)}p_{C}(c)\dfrac{c}{k}\mathcal{I}_{c}(W,\bm{\pi}_{c}),$

where note that $\bar{\mathcal{J}}$ is bounded in the limit. For non-decaying
measure $p_{C}(c)$, we can see from (36) that the first term decays like
$1/k^{2}$, the second term decays like $1/kc$ where $c$ is sub-linear in $k$,
and the last term decays like $1/k$. Therefore if $p_{C}(c)$ in the last two
terms is not small enough in the limit, the payoff will decay slower than
$1/k^{2}$. Any strategy that assigns asymptotically small enough measure in
the last two terms will hence produce a lower value for the payoff given large
enough $k$, nevertheless, the first term will always decay like $1/k^{2}$. ∎

######  Lemma 10.

$\mathbb{E}_{p_{C}}\left[\dfrac{C}{k}\right]=\dfrac{1}{L}$.

###### Proof.

$\displaystyle\sum_{c}p_{C}(c)\dfrac{c}{k}=\dfrac{1}{L}\sum_{l=1}^{L}\sum_{c}p_{C}(c)\dfrac{c}{k}=\dfrac{1}{L}\sum_{l=1}^{L}\sum_{c^{l}}p_{C}(c^{l})\dfrac{c^{l}}{k}$
(37)
$\displaystyle=\dfrac{1}{L}\sum_{c^{1},\dots,c^{L}}p_{C^{1},\dots,C^{L}}(c^{1},\dots,c^{L})\dfrac{c^{1}+\dots+c^{L}}{k}=\dfrac{1}{L}.$

∎

######  Lemma 11.

$\sum_{c}p_{C}(c)\dfrac{k}{c}\geq L$, with equality iff $p_{C}(k/L)=1$.

###### Proof.

$\mathbb{E}_{p_{C}}\left[\dfrac{k}{C}\right]=k\mathbb{E}_{p_{C}}\left[\dfrac{1}{C}\right]\geq
k\dfrac{1}{\mathbb{E}_{p_{C}}\left[C\right]}=\dfrac{1}{\mathbb{E}_{p_{C}}\left[\dfrac{C}{k}\right]}=L,$
(38)

which is an application of Jensen’s inequality to a strictly convex function.
∎

######  Lemma 12.

Let $\alpha\geq 1$, then $\sum_{c\sim k}p_{C}(c)\dfrac{k}{c}\geq L+\cdots$,
where terms in ellipsis go to zero in the limit $k\to\infty$.

###### Proof.

$\displaystyle\left[\sum_{c^{\prime}\sim
k}p_{C}(c^{\prime})\right]^{-1}\sum_{c\sim
k}p_{C}(c)\dfrac{c}{k}=\dfrac{1}{L}\left[\sum_{c^{\prime}\sim
k}p_{C}(c^{\prime})\right]^{-1}-\left[\sum_{c^{\prime}\sim
k}p_{C}(c^{\prime})\right]^{-1}\sum_{c\nsim k}p_{C}(c)\dfrac{c}{k},$ (39)

and so applying Jensen’s inequality, we get:

$\displaystyle\left[\sum_{c^{\prime}\sim
k}p_{C}(c^{\prime})\right]^{-1}\sum_{c\sim
k}p_{C}(c)\dfrac{k}{c}\geq\left[\dfrac{1}{L}\left[\sum_{c^{\prime}\sim
k}p_{C}(c^{\prime})\right]^{-1}-\left[\sum_{c^{\prime}\sim
k}p_{C}(c^{\prime})\right]^{-1}\sum_{c\nsim
k}p_{C}(c)\dfrac{c}{k}\right]^{-1},$ (40)

and if we multiply both sides by $\sum_{c^{\prime}\sim k}p_{C}(c^{\prime})$,
we arrive at:

$\sum_{c\sim
k}p_{C}(c)\dfrac{k}{c}\geq\left[\dfrac{1}{L}\left[\sum_{c^{\prime}\sim
k}p_{C}(c^{\prime})\right]^{-2}-\left[\sum_{c^{\prime}\sim
k}p_{C}(c^{\prime})\right]^{-2}\sum_{c\nsim
k}p_{C}(c)\dfrac{c}{k}\right]^{-1},$ (41)

or simply:

$\displaystyle\sum_{c\sim k}p_{C}(c)\dfrac{k}{c}\geq
L\dfrac{\left[\sum_{c^{\prime}\sim
k}p_{C}(c^{\prime})\right]^{2}}{1-L\sum_{c\nsim
k}p_{C}(c)\dfrac{c}{k}}=L\dfrac{\left[1-\sum_{c^{\prime}\nsim
k}p_{C}(c^{\prime})\right]^{2}}{1-L\sum_{c\nsim k}p_{C}(c)\dfrac{c}{k}}$ (42)
$\displaystyle=L\dfrac{\left[1-\sum_{c^{\prime}\nsim
k}\bar{p}_{C}(c^{\prime})\left(\dfrac{c}{k}\right)^{\alpha}\right]^{2}}{1-L\sum_{c\nsim
k}\bar{p}_{C}(c)\left(\dfrac{c}{k}\right)^{\alpha+1}},$

where we write
$\bar{p}_{C}(c)\overset{\Delta}{=}p_{C}(c)\dfrac{k^{\alpha}}{c^{\alpha}}$,
which is bounded in the limit. For $\alpha\geq 1$ and $c\nsim k$, we have
$c^{\alpha}/k^{\alpha}\rightarrow 0$. ∎

######  Lemma 13.

For $\alpha=1$, $\tilde{p}_{C}(c)\overset{\Delta}{=}\dfrac{p_{C}(c)k}{c}$, and
up to $o(1/k^{2})$, we have the following lower bound for $\tilde{J}$:

$\displaystyle\tilde{J}_{\alpha=1}\geq\dfrac{\pi^{2}L}{k^{2}2\ln
2}\left[\int_{0}^{1}\dfrac{dw}{f_{W}(w)w(1-w)}\right]^{-1}\left(1+L^{-1}\sum_{c\in
w(1)\cap o(k)}\tilde{p}_{C}(c)+\dfrac{4L^{-1}}{\pi^{2}}\sum_{c\in
O(1)}\tilde{p}_{C}(c)\right).$ (43)

###### Proof.

For $\alpha=1$, all terms in $\tilde{J}$ become of order $1/k^{2}$, and we can
write:

$\displaystyle\tilde{J}_{\alpha=1}=$ $\displaystyle\sum_{c\sim
k}\tilde{p}_{C}(c)\left(\dfrac{1}{k^{2}2\ln
2}\bar{\mathcal{J}}[g_{c}(W)]+o\left(\dfrac{1}{k^{2}}\right)\right)$ (44)
$\displaystyle+$ $\displaystyle\sum_{c\in w(1)\cap
o(k)}\tilde{p}_{C}(c)\left(\dfrac{1}{k^{2}2\ln
2}\bar{\mathcal{J}}[g_{c}(W)]+o\left(\dfrac{1}{k^{2}}\right)\right)+\sum_{c\in
O(1)}\tilde{p}_{C}(c)\dfrac{c^{2}}{k^{2}}\mathcal{I}_{c}(W,\bm{\pi}_{c})$
$\displaystyle=\dfrac{1}{k^{2}2\ln 2}\Bigg{(}\sum_{c\sim
k}\tilde{p}_{C}(c)\bar{\mathcal{J}}[g_{c}(W)]+\sum_{c\in w(1)\cap
o(k)}\tilde{p}_{C}(c)\bar{\mathcal{J}}[g_{c}(W)]$ $\displaystyle+\sum_{c\in
O(1)}\tilde{p}_{C}(c)2\ln
2\,c^{2}\mathcal{I}_{c}(W,\bm{\pi}_{c})\Bigg{)}+o\left(\dfrac{1}{k^{2}}\right),$

where note that $\tilde{p}_{C}(c)=\dfrac{p_{C}(c)k}{c}$ is bounded in the
limit. We can replace $\bar{\mathcal{J}}[g_{c}(W)]$ in the first two terms by
$\bar{\mathcal{J}}[g(W)]$, and the remainder will still decay faster than
$1/k^{2}$. That is, up to $o(1/k^{2})$, we have the following:

$\displaystyle\dfrac{1}{k^{2}2\ln 2}\left(\sum_{c\sim
k}\tilde{p}_{C}(c)\bar{\mathcal{J}}[g(W)]+\sum_{c\in w(1)\cap
o(k)}\tilde{p}_{C}(c)\bar{\mathcal{J}}[g(W)]+\sum_{c\in
O(1)}\tilde{p}_{C}(c)2\ln 2\,c^{2}\mathcal{I}_{c}(W,\bm{\pi}_{c})\right)$ (45)
$\displaystyle=\dfrac{1}{k^{2}2\ln 2}\left(\bar{\mathcal{J}}[g(W)]\sum_{c\in
w(1)}\tilde{p}_{C}(c)+\sum_{c\in O(1)}\tilde{p}_{C}(c)2\ln
2\,c^{2}\mathcal{I}_{c}(W,\bm{\pi}_{c})\right)\geq$
$\displaystyle\dfrac{1}{k^{2}2\ln
2}\left(\pi^{2}\left[\int_{0}^{1}\dfrac{dw}{f_{W}(w)w(1-w)}\right]^{-1}\sum_{c\in
w(1)}\tilde{p}_{C}(c)+4\left[\int_{0}^{1}\dfrac{dw}{f_{W}(w)w(1-w)}\right]^{-1}\sum_{c\in
O(1)}\tilde{p}_{C}(c)\right)$ $\displaystyle=\dfrac{1}{k^{2}2\ln
2}\left[\int_{0}^{1}\dfrac{dw}{f_{W}(w)w(1-w)}\right]^{-1}\pi^{2}\left(\sum_{c\in
w(1)}\tilde{p}_{C}(c)+\dfrac{4}{\pi^{2}}\sum_{c\in
O(1)}\tilde{p}_{C}(c)\right),$

where the inequality follows from Lemma 6 and Lemma 8. Finally, applying Lemma
12, we obtain the desired bound. ∎

######  Lemma 14.

For $\alpha>1$, we have the following lower bound for $\tilde{J}$:

$\tilde{J}_{\alpha>1}\geq\dfrac{L}{k^{2}2\ln
2}\left[\int_{0}^{1}\dfrac{dw}{f_{W}(w)w(1-w)}\right]^{-1}\pi^{2}+o\left(\dfrac{1}{k^{2}}\right),$
(46)

with conditions for equality being:

$\displaystyle g(w)=g_{\mathrm{opt}}(w),$ (47)
$\displaystyle\lim_{k\to\infty}p_{C}(k/L)=1,$ (48)

where $g_{\mathrm{opt}}(w)$ is given by equation (33).

###### Proof.

Note that in equation (44), for any choice of $\alpha>1$, the second two terms
will decay faster than $1/k^{2}$, while the first term will dominate since it
decays as $1/k^{2}$ for any value of $\alpha$. Therefore choosing $\alpha>1$
makes the contribution from $c\nsim k$ negligible in the limit, and so
repeating the same steps as in the proof of Lemma 13, we obtain:

$\displaystyle\tilde{J}_{\alpha>1}\geq\dfrac{1}{k^{2}2\ln
2}\left[\int_{0}^{1}\dfrac{dw}{f_{W}(w)w(1-w)}\right]^{-1}\pi^{2}\sum_{c\sim
k}p_{C}(c)\dfrac{k}{c}+o\left(\dfrac{1}{k^{2}}\right)$ (49)
$\displaystyle\geq\dfrac{L}{k^{2}2\ln
2}\left[\int_{0}^{1}\dfrac{dw}{f_{W}(w)w(1-w)}\right]^{-1}\pi^{2}+o\left(\dfrac{1}{k^{2}}\right).$

Conditions for equality follow from Lemma 8 and Lemma 11. ∎

######  Lemma 15.

$\alpha>1$, $g_{\mathrm{opt}}(w)$ and
$p^{*}_{C}(c)\overset{\Delta}{=}\delta(c,k/L)$ are asymptotically optimal for
$\tilde{J}$.

###### Proof.

This follows directly from Lemma 9, Lemma 13, and Lemma 14. Note that the
lower bound for $\tilde{J}_{\alpha=1}$ given in Lemma 13 is asymptotically
larger than the lower bound for $\tilde{J}_{\alpha>1}$ given in Lemma 14, and
since $g_{\mathrm{opt}}(w)$ and $p^{*}_{C}(c)$ achieve this lower bound for
$\tilde{J}_{\alpha>1}$, we conclude that the optimal sequence of pirate
strategies must have $\alpha>1$ with its limit being
$(g_{\mathrm{opt}}(w),p^{*}_{C})$. ∎

######  Lemma 16.

$\left[{\int}_{0}^{1}\dfrac{dw}{f_{W}(w)w(1-w)}\right]^{-1}\pi^{2}\leq 1$,
with equality iff $f_{W}$ is the arcsine distribution:
$f^{*}_{W}(w)\overset{\Delta}{=}\left(\pi\sqrt{w(1-w)}\right)^{-1}$.

###### Proof.

This is Lemma 4 in [9]. ∎

######  Lemma 17.

$f^{*}_{W}$ is asymptotically optimal for $\tilde{J}$.

###### Proof.

From Lemma 14 and Lemma 15, the asymptotically optimal $f_{W}$ is the
maximiser of $\dfrac{L}{k^{2}2\ln
2}\left[{\int}_{0}^{1}\dfrac{dw}{f_{W}(w)w(1-w)}\right]^{-1}\pi^{2}$, which is
$f^{*}_{W}$ by Lemma 16. ∎

######  Lemma 18.

The payoff function $\tilde{J}_{k,L}$ has the following asymptotic behavior:

$\max_{f_{W}}\min_{\\{\pi\\},p_{{C}}}\tilde{J}_{k,L}\rightarrow\dfrac{L^{2}}{k^{2}2\ln
2},$ (50)

with asymptotically optimal strategies being $(f^{*}_{W},g^{*},p^{*}_{{C}})$,
where $g^{*}(w)\overset{\Delta}{=}w$ is the interleaving attack.

###### Proof.

This follows directly from Lemma 14, Lemma 15, and Lemma 17. ∎

We are now in a position to present the main result of the work, concerning
the asymptotic behavior of our payoff function as defined in equation (34). To
this end, we define the following degenerate distribution:

$p^{*}_{\hat{C}}(\hat{c})\overset{\Delta}{=}\prod_{l=1}^{L}\delta(c^{l},k/L)=\begin{cases}1,&\hat{c}=(k/L,k/L,\dots,k/L)\\\
0,&\mathrm{otherwise}\end{cases},$ (51)

which corresponds to the strategy where the pirates equally populate the $L$
TV channels.

######  Theorem 1.

The payoff function in equation (34) has the following asymptotic behavior:

$\max_{f_{W}}\min_{\\{\pi\\},p_{\hat{C}}}{J}_{k,L}\rightarrow\dfrac{L^{2}}{k^{2}2\ln
2},$ (52)

with asymptotically optimal strategies being
$(f^{*}_{W},g^{*},p^{*}_{\hat{C}})$.

###### Proof.

From equation (34), we can see that
$J=L\tilde{J}+k^{-1}I(\hat{Y};\hat{C}|\hat{W})$, and the second term has zero
as its minimum. For any $f_{W}$ and $g$, this is achieved when $\hat{C}$ is
deterministic, i.e. as in $p^{*}_{\hat{C}}$. Optimality of
$(f^{*}_{W},g^{*},p^{*}_{\hat{C}})$ follows from Lemma 18, as well as the
asymptotic value. ∎

##  4 Alternative payoff and fingerprinting capacity

The maximin game of our payoff given by equation (21) (or equation (34) for
the binary alphabet case) is a direct generalization of the single TV channel
payoff in [9], i.e. if we set $L=1$ for the maximin game, we recover the
single TV channel payoff that defines the fingerprinting capacity, which is
asymptotically equal to $\big{(}k^{2}2\ln 2\big{)}^{-1}$ in the binary
alphabet case [9]. Nevertheless, this is not the only generalization that
reduces to the single TV channel payoff when setting $L=1$. If we consider the
payoff $R_{k,L}\overset{\Delta}{=}k^{-1}I(\hat{Y};\hat{X}_{\cal
K}|\hat{\mathbf{W}})$, the maximin game will also reduce to the single TV
channel case when $L=1$. This payoff is generally smaller than our payoff
$J_{k,L}$, and the difference term (up to $k$) is
$I(\hat{Y};\hat{S}|\hat{X}_{\mathcal{K}})=I(\hat{Y};\hat{\mathbf{M}}|\hat{X}_{\mathcal{K}})$,
i.e. we can write:

$I(\hat{Y};\hat{X}_{\cal
K}|\hat{\mathbf{W}})=kJ_{k,L}-I(\hat{Y};\hat{S}|\hat{X}_{\mathcal{K}})=kJ_{k,L}-I(\hat{Y};\hat{\mathbf{M}}|\hat{X}_{\mathcal{K}})=I(\hat{Y};\hat{\mathbf{M}}|\hat{\mathbf{W}})-I(\hat{Y};\hat{\mathbf{M}}|\hat{X}_{\mathcal{K}}).$
(53)

$R_{k,L}$ could possibly have different asymptotic behavior compared to
$J_{k,L}$. However, since it can not be larger than $J_{k,L}$, we can write
(in the binary alphabet case):

$\max_{f_{W}}\min_{\\{\pi\\},p_{\hat{C}}}{R}_{k,L}\rightarrow\dfrac{N^{2}}{k^{2}2\ln
2},$ (54)

for some $N\leq L$. It is plausible that $N$ is in fact equal to $L$, and the
asymptotic maximin games for both $R_{k,L}$ and $J_{k,L}$ are identical. This
is motivated by the fact that the difference term
$I(\hat{Y};\hat{S}|\hat{X}_{\mathcal{K}})$ extracts information about the
choice of pirates assigned to the different TV channels from their outputs
$\hat{Y}$, and asymptotically we expect likely realizations of
$\hat{X}_{\mathcal{K}}$ to be insensitive to who the pirates choose to assign
for the different TV channels. That is, as long as they choose large enough
numbers of pirates to populate the TV channels, we expect that knowing
$\hat{S}$ will not be significant if we already know $\hat{X}_{\mathcal{K}}$.
This of course hinges on the argument that the pirates should assign large
numbers to all $L$ TV channels, which is also in line of what one would
expect. This leads us to the following conjecture:

######  Conjecture 1.

For the binary alphabet case, and $\tilde{L}=1$, the payoff functional
$R_{k,L}$ given by:

$R_{k,L}=J_{k,L}-\dfrac{1}{k}I(\hat{Y};\hat{S}|\hat{X}_{\mathcal{K}})$ (55)

has the following asymptotic behavior:

$\max_{f_{W}}\min_{\\{\pi\\},p_{\hat{C}}}{R}_{k,L}\rightarrow\dfrac{L^{2}}{k^{2}2\ln
2},$ (56)

with optimal strategies $f_{W}^{*}(w)=\left(\pi\sqrt{w(1-w)}\right)^{-1}$,
$g^{*}(w)=w$, and $p^{*}_{\hat{C}}(\hat{c})=\prod_{l=1}^{L}\delta(c^{l},k/L)$.

The payoffs $J_{k,L}$ and $R_{k,L}$ are the most natural generalizations of
the single TV channel payoff in [9]. Assuming Conjecture 1 holds, then by
Theorem 1, and Corollary 7 in [9], the asymptotic maximin value for both
$J_{k,L}$ and $R_{k,L}$ is the same as the asymptotic fingerprinting capacity
in the single TV channel case ($L=1$). This prompts the question of whether
this holds also for any $L$, i.e. if our payoff defines the fingerprinting
capacity for multiple TV channels. Since the pirates choose $\hat{S}$
independently of the watermarking procedure, and once $\hat{S}$ is known the
problem reduces to $L$ independent single TV channels that abide by the
assumptions used in [9], our direct generalization of the single TV channel
payoff can very possibly define the capacity (in the limit $k\to\infty$) in
this case as its maximin value, and this leads us to the following conjecture:

######  Conjecture 2.

The binary fingerprinting capacity in the multiple TV channels scenario (with
$\tilde{L}=1$) $C_{\rm fp}^{\rm binary}(k,L)$ has the asymptotic behavior:

$\max_{f_{W}}\min_{\\{\pi\\},p_{\hat{C}}}C_{\rm fp}^{\rm
binary}(k,L)\rightarrow\dfrac{L^{2}}{k^{2}2\ln 2}$ (57)

with optimal strategies $f_{W}^{*}(w)=\left(\pi\sqrt{w(1-w)}\right)^{-1}$,
$g^{*}(w)=w$, and $p^{*}_{\hat{C}}(\hat{c})=\prod_{l=1}^{L}\delta(c^{l},k/L)$.

##  5 Discussion

We have shown that when $k$ colluders attack $L$ TV channels simultaneously,
the maximin value of the payoff defined in equation (34) has the asymptotic
value $\big{(}(k/L)^{2}2\ln 2\big{)}^{-1}$ with asymptotically optimal
strategies being $f_{W}^{*}(w)=\left(\pi\sqrt{w(1-w)}\right)^{-1}$,
$g^{*}(w)=w$, and $p^{*}_{\hat{C}}(\hat{c})=\prod_{l=1}^{L}\delta(c^{l},k/L)$.
This is exactly the same as having $L$ independent single TV channels [9] with
$k/L$ colluders on each TV channel. This is expected as the payoff is
independent of the identity of the pirates assigned to the TV channels, i.e.
it is only sensitive to the number of colluders assigned to the different TV
channels. The identity dependence is present in $I(\hat{Y};\hat{X}_{\cal
K}|\hat{W})$, namely in the difference term
$I(\hat{Y};\hat{S}|\hat{X}_{\mathcal{K}})$, which possibly lowers the value of
the payoff by virtue of allowing the identity of the pirates assigned to a TV
channel to be chosen uniformly randomly given they know the numbers
$\\{c^{l}\\}_{l=1}^{L}$.

We have presented arguments that strongly suggest that this liberty the
pirates enjoy, although it can be significantly advantageous for finite $k$,
does become of less value asymptotically and the asymptotic maximin games of
$I(\hat{Y};\hat{X}_{\cal K}|\hat{W})$ and $I(\hat{Y};\hat{Z},\hat{C}|\hat{W})$
are the same. It remains an open question to prove Conjecture 1, which is left
for future work. Furthermore, we have argued that our payoff does predict how
the fingerprinting capacity behaves asymptotically, and that it is indeed
plausible that its maximin value can be replaced by the fingerprinting
capacity in Theorem 1.

It is important to note that we have not used any saddle point property of the
payoff (c.f. [9]) as it is simply not needed. That is, we make no claims of
the maximin game yielding the same value for the payoff as the minimax game
(applicability of Sion’s theorem) for any of the payoffs discussed in this
work. Although this is very possible, i.e. the strategies we found could be an
equilibrium point, one still needs to show that the payoff considered is
jointly convex in the pirates’ strategies, e.g. if future directions require
solving the maximin game numerically.

As other potential follow-up work, there remains the generalization to non-
binary alphabet, the case where users can tune in to more than one TV channel
simultaneously, i.e. $\tilde{L}\neq 1$, dynamic tracing, and perhaps most
practically useful, the study of decoders and score functions suitable for
multiple TV channel attacks.

### Acknowledgements

Part of this work was supported by NWO grant CS.001 (Forwardt).

## References

  * [1] E. Amiri and G. Tardos.  High rate fingerprinting codes and the fingerprinting capacity.  In SODA 2009, pages 336–345, 2009.
  * [2] O. Blayer and T. Tassa.  Improved versions of Tardos’ fingerprinting scheme.  Designs, Codes and Cryptography, 48(1):79–103, 2008.
  * [3] A. Charpentier, C. Fontaine, T. Furon, and I.J. Cox.  An asymmetric fingerprinting scheme based on Tardos codes.  In Information Hiding 2011, volume 6958 of LNCS, pages 43–58. Springer, 2011.
  * [4] A. Charpentier, F. Xie, C. Fontaine, and T. Furon.  Expectation maximization decoding of Tardos probabilistic fingerprinting code.  In SPIE Media Forensics and Security 2009, page 72540, 2009.
  * [5] T. Furon and M. Desoubeaux.  Tardos codes for real.  In IEEE Workshop on Information Forensics and Security (WIFS) 2014, 2014.
  * [6] T. Furon, A. Guyader, and F. Cérou.  On the design and optimization of Tardos probabilistic fingerprinting codes.  In Information Hiding 2008, volume 5284 of LNCS, pages 341–356. Springer, 2008.
  * [7] T. Furon, L. Pérez-Freire, A. Guyader, and F. Cérou.  Estimating the minimal length of Tardos code.  In Information Hiding 2009, volume 5806 of LNCS, pages 176–190, 2009.
  * [8] Y.-W. Huang and P. Moulin.  Capacity-achieving fingerprint decoding.  In IEEE Workshop on Information Forensics and Security (WIFS) 2009, pages 51–55, 2009.
  * [9] Y.-W. Huang and P. Moulin.  On the saddle-point solution and the large-coalition asymptotics of fingerprinting games.  IEEE Transactions on Information Forensics and Security, 7(1):160–175, 2012.
  * [10] Ye.-W. Huang and P. Moulin.  On fingerprinting capacity games for arbitrary alphabets and their asymptotics.  In IEEE International Symposium on Information Theory (ISIT) 2012, pages 2571–2575, 2012.
  * [11] T. Laarhoven and B. de Weger.  Optimal symmetric Tardos traitor tracing schemes.  Designs, Codes and Cryptography, pages 1–21, 2012.
  * [12] P. Meerwald and T. Furon.  Towards Joint Tardos Decoding: The ‘Don Quixote’ Algorithm.  In Information Hiding 2011, pages 28–42, 2011.
  * [13] K. Nuida.  Short collusion-secure fingerprint codes against three pirates.  In Information Hiding 2010, volume 6387 of LNCS, pages 86–102. Springer, 2010.
  * [14] K. Nuida, S. Fujitsu, M. Hagiwara, T. Kitagawa, H. Watanabe, K. Ogawa, and H. Imai.  An improvement of discrete Tardos fingerprinting codes.  Designs, Codes, and Cryptography, 52(3):339–362, 2009.
  * [15] J.-J. Oosterwijk, B. Škorić, and J. Doumen.  Optimal suspicion functions for Tardos traitor tracing schemes.  In ACM Information Hiding and Multimedia Security Workshop (IH&MMSec) 2013, pages 19–28, 2013.
  * [16] A. Simone and B. Škorić.  Accusation probabilities in Tardos codes: beyond the Gaussian approximation.  Designs, Codes and Cryptography, 63(3):379–412, 2012.
  * [17] G. Tardos.  Optimal probabilistic fingerprint codes.  In ACM Symposium on Theory of Computing (STOC) 2003, pages 116–125, 2003.
  * [18] G. Tardos.  Optimal probabilistic fingerprint codes.  J. ACM, 55(2):1–24, 2008.
  * [19] B. Škorić.  Tally-based simple decoders for traitor tracing and group testing.  IEEE Transactions on Information Forensics and Security, 10(6):1221–1223, 2015.
  * [20] B. Škorić and W. de Groot.  Generalized tally-based decoders for traitor tracing and group testing.  In IEEE Workshop on Information Forensics and Security (WIFS) 2015, 2015.
  * [21] B. Škorić, S. Katzenbeisser, and M.U. Celik.  Symmetric Tardos fingerprinting codes for arbitrary alphabet sizes.  Designs, Codes and Cryptography, 46(2):137–166, 2008.
  * [22] B. Škorić, S. Katzenbeisser, H.G. Schaathun, and M.U. Celik.  Tardos Fingerprinting Codes in the Combined Digit Model.  IEEE Transactions on Information Forensics and Security, 6(3):906–919, 2011.
  * [23] B. Škorić and J.-J. Oosterwijk.  Binary and q-ary Tardos codes, revisited.  Designs, Codes, and Cryptography, July 2013.
  * [24] B. Škorić, T.U. Vladimirova, M.U. Celik, and J.C. Talstra.  Tardos Fingerprinting is Better Than We Thought.  IEEE Transactions on Information Theory, 54(8):3663–3676, 2008\.
  * [25] F. Xie, T. Furon, and C. Fontaine.  On-off keying modulation and Tardos fingerprinting.  In Multimedia & Security (MM&Sec) 2008, pages 101–106. ACM, 2008.