# Optimising Placement of Pollution Sensors
in Windy Environments

Sigrid Passano Hellan Christopher G. Lucas Nigel H. Goddard
School of Informatics
University of Edinburgh, UK
{s.p.hellan, c.lucas<EMAIL_ADDRESS>

###### Abstract

Air pollution is one of the most important causes of mortality in the world.
Monitoring air pollution is useful to learn more about the link between health
and pollutants, and to identify areas for intervention. Such monitoring is
expensive, so it is important to place sensors as efficiently as possible.
Bayesian optimisation has proven useful in choosing sensor locations, but
typically relies on kernel functions that neglect the statistical structure of
air pollution, such as the tendency of pollution to propagate in the
prevailing wind direction. We describe two new wind-informed kernels and
investigate their advantage for the task of actively learning locations of
maximum pollution using Bayesian optimisation.

Air pollution is one of the most important causes of death globally.
Particulate matter with diameter less than
$2.5\text{\,}\mathrm{\SIUnitSymbolMicro m}\text{/}$, PM2.5, is estimated to
cause 3-4 million deaths yearly [1, 2]. Through monitoring one can learn more
about the impact of air pollution on public health and identify areas
requiring intervention. Traditional monitoring networks consist of a few high-
quality reference sensors [3], but many low-cost pollution sensors are now
available, e.g. [4], which can be used to build higher-resolution models to
complement the traditional networks. This work aims to improve monitoring
networks by improving the placement of low-cost, potentially noisy sensors to
monitor average concentrations of PM2.5 and identify areas of high average
concentration, assuming that sensors can be placed incrementally. This problem
– of finding the maxima of a black-box function given sparse and noisy
observations – is well-matched to Bayesian optimisation (BO). Most machine
learning research on air pollution tends not to consider the problem of
efficient sensor placement, e.g. [5, 6, 7, 8, 9]. To our knowledge, previous
work on environmental sensing using BO and related methods, e.g. [10, 11, 12],
has not considered wind.

Wind is known to move pollutants downwind [13, p. 78-80], and work on gas
mapping has shown the importance of incorporating this effect [14, 15]. For
instance, [15] used a gas localisation task to show that a method
incorporating wind velocity outperforms BO using wind-insensitive kernels.
Because we are focusing on time-averaged pollution concentrations, detailed
wind information and fluid simulations are not essential: The covariance
structure of pollution is driven by the prevailing wind direction, which can
be characterised with a single parameter. The kernels presented here allow
such information to be incorporated into BO, and have the advantage that wind
need not be measured separately. This is desirable from a cost perspective, as
additional wind sensors are not needed.

The key question is whether these kernels improve our ability to find the
location(s) of highest pollution in an area, with a minimum number of sensor
placements, i.e., samples of time-averaged pollution concentrations. To answer
this question using real data, we used satellite images of nitrogen dioxide
(NO2) concentrations (see Supplementary Material for details). NO2 is a
health-related pollutant in its own right [16], and we assume that the
dispersion of PM2.5 is comparable. While satellite data cannot replace
surface-level sensor data, it provides a good testbed given the spatial
regularity and density of the observations, and it allows us to set aside
complex effects of urban topography.

##  1 Wind-informed kernels for Bayesian optimisation

In Bayesian optimisation [17] a probabilistic model, in our case a GP, is
fitted to the set of observed data points. This model is then used to compute
an acquisition function, and the next sample is taken at the point which
maximises this function. The new sample is added to the set of data points and
the process is repeated. In this paper, the upper confidence bound (UCB) [18]
was used as the acquisition function,
$\alpha{{}_{\mathrm{UCB}}}(\boldsymbol{x};\beta,\mathcal{D},M)~{}=~{}\mu(\boldsymbol{x};\mathcal{D},M)~{}+~{}\beta\sigma(\boldsymbol{x};\mathcal{D},M)$,
with $\beta=1$. $\mu(\boldsymbol{x};\mathcal{D},M)$ and
$\sigma(\boldsymbol{x};\mathcal{D},M)$ are the posterior mean and standard
deviation of a point $\boldsymbol{x}$ given data $\mathcal{D}$ and model $M$.
An entropy-based acquisition function [19] and other values of $\beta$ were
tested, without marked improvement. To compute $\mu(\cdot)$ and
$\sigma(\cdot)$, covariances need to be computed between the data points using
a kernel function. A thorough introduction to GPs can be found in [20].

The motivation for the wind-informed kernels is to exploit the directional
structure of wind-driven pollution transport. Intuitively, one would expect to
see the highest levels of pollution downwind from a source, and if one
recorded a high pollution concentration in a location one would expect to find
a source upwind from it. In this work we do not aim to locate sources, but to
look at concentrations, and so do not differentiate between upwind and
downwind movement.

The standard radial basis function (RBF) was modified to create the wind-
informed kernels. The RBF kernel calculates the covariance between two points
$\boldsymbol{x}_{i}$ and $\boldsymbol{x}_{j}$ as
$k_{R}(\boldsymbol{\tau};l,\sigma_{R})~{}\\!=\\!~{}\sigma_{R}^{2}\exp(-\boldsymbol{\tau}^{T}\boldsymbol{\tau}/l^{2})$
where $\boldsymbol{\tau}=\boldsymbol{x}_{i}-\boldsymbol{x}_{j}$, $l$ is the
length scale and $\sigma_{R}^{2}$ the signal variance. The new kernels
$k_{S}(\cdot)$, _Sum_ , and $k_{P}(\cdot)$, _Product_ , are given in Eqs. 1
and 2 and visualised in Fig. 1. The kernels are a combination of a standard
RBF kernel and another RBF kernel on the distance orthogonal to the wind
direction. This distance is given by
$\tilde{\tau}\left(\boldsymbol{\tau};\gamma\right)=||\boldsymbol{\tau}-\left(\boldsymbol{\tau}^{T}\boldsymbol{b}\right)\boldsymbol{b}||$
where $\boldsymbol{b}=[\cos(\gamma)\>\>\sin(\gamma)]^{T}$ and $\gamma$ is the
wind direction hyperparameter. Further, $l_{D}$ is the directional length
scale, $\sigma_{D}^{2}$ the directional signal variance, $\sigma_{P}^{2}$ the
signal variance for $k_{P}(\cdot)$,
$A~{}=~{}\begin{bmatrix}{}\sin(\gamma)^{2}&-\sin(\gamma)\cos(\gamma)\\\
-\sin(\gamma)\cos(\gamma)&\cos(\gamma)^{2}\end{bmatrix}$ and
$E=l_{D}^{2}/l^{2}\boldsymbol{\mathbb{I}}+A$. Finally,
$\theta_{S}=\\{l,l_{D},\sigma_{R},\sigma_{D},\gamma\\}$ and
$\theta_{P}=\\{l,l_{D},\sigma_{P},\gamma\\}$ denote sets of hyperparameters.
The kernel hyperparameters, together with the noise hyperparameter
$\sigma_{n}^{2}$, are fitted in the GP tuning step.

$\displaystyle k_{S}\\!\left(\boldsymbol{\tau};\theta_{S}\right)\\!=$
$\displaystyle
k_{R}\left(\boldsymbol{\tau};l,\sigma_{R}\right)\\!+\\!k_{R}\\!\left(\tilde{\tau}\left(\boldsymbol{\tau};\gamma\right);l_{D},\sigma_{D}\\!\right)\\!=\\!\sigma_{R}^{2}\exp\\!\left(\frac{-\boldsymbol{\tau}^{T}\boldsymbol{\tau}}{l^{2}}\\!\right)\\!+\\!\sigma_{D}^{2}\exp\\!\left(\frac{-\boldsymbol{\tau}^{T}A\boldsymbol{\tau}}{l_{D}^{2}}\\!\right)$
(1) $\displaystyle k_{P}\\!\left(\boldsymbol{\tau};\theta_{P}\right)\\!=$
$\displaystyle
k_{R}\left(\boldsymbol{\tau};l,\sigma_{P}\right)k_{R}\left(\tilde{\tau}\left(\boldsymbol{\tau};\gamma\right);l_{D},1\right)=\sigma_{P}^{2}\exp\left(\frac{-\boldsymbol{\tau}^{T}E\boldsymbol{\tau}}{l_{D}^{2}}\right)$
(2)

Figure 1: Visualisation of wind-informed kernels from Eqs. 1 and 2. The top
row shows covariance as function of distance, and the bottom row shows example
images sampled from the kernels. $\sigma_{D}^{2}=0.5$, $l=105$, $l_{D}=35$,
$\gamma=\pi/4$, $\sigma_{P}^{2}=1$, $\sigma_{n}^{2}=0.01$. For Sum
$\sigma_{R}^{2}=0.5$, for RBF $\sigma_{R}^{2}=1$.

These kernels are sums and products of RBF kernel functions that are valid for
all inputs, and are thus valid kernel functions themselves [20, p. 83,95].

##  2 Data

The data set consists of 1083 images of 28x28 pixels, with each pixel giving
the NO2 concentration in mol/m2 within a ca. 7x7km box on the ground reaching
the upper troposphere. The images are from October and November 2018 and cover
landmasses across the world. More information is given in the Supplementary
Material. We removed images with more than 10 % missing values, and split the
data into subsets. The split was done as NO2 concentrations varied greatly
between images, and locating peaks of high pollution is more important. Three
subsets were created as follows: the images were ordered by the highest NO2
concentration present, and the top, median and bottom 50 images put into sets
called ’Strong’, ’Median’ and ’Weak’, respectively. See Fig. 2. Three adjacent
sets of 10 images each were created for tuning and normalisation. A final set
of 100 images, dubbed ’Selection’, was created by picking every ninth of the
remaining ordered images. The first three subsets were created to inspect
performance on different degrees of difficulty, and the last to test the
overall performance.

Figure 2: Example NO2 concentration images from the Strong, Median and Weak
subsets. White pixels indicate missing data. Note the difference in scale
between the subsets, and the pollution plumes from point sources in two of the
examples. Such plumes were present in many images, particularly in the Strong
subset, and are what the wind-informed kernels are meant to capture.

##  3 Results

We used log concentrations rather than raw concentrations as our data – and
pollution concentrations in general [21] – are approximately log-normal,
satisfying the assumption of Gaussian marginal and residual distributions in
GP models. Images were normalised using means and standard deviations from the
associated tuning set. The rationale for this was that the true mean and
standard deviation for a deployment region would likely be unknown, but values
from similar areas available. The tuning sets were also used to develop priors
for the hyperparameters, except for $\gamma$ for which a uniform prior was
used. For each tuning image, gradient descent with 200 hyperparameter
initialisations was used to maximise the log marginal likelihood,
$\log(p(Y^{i}|M))$, where $M$ denotes the model, including kernel and
hyperparameter choices, and $Y^{i}$ is the pixel values in image $i$. A log
normal distribution was then fitted to these hyperparameter samples using the
maximum likelihood estimator and this was used as a prior. For the Selection
subset, the Median tuning set was used for normalisation and prior
computation. The models obtained on the tuning sets were compared using the
Bayesian information criterion (BIC) [22]. It was highest for the Sum kernel,
followed by the Product kernel, c.f. the Supplementary Material. This shows
that the wind-informed kernels are able to capture more of the structure of
the pollution in the images. For the Weak subset little difference was seen.

The kernels were evaluated on the task of locating the pixel with the maximum
pollution concentration. Results on two of the subsets, Strong and Selection,
are presented. For comparison, our baselines were (1) Bayesian optimisation
with an RBF kernel (RBF) and (2) a policy of choosing points uniformly at
random (Random). The latter was repeated 100 times per image and the mean
taken. The experiments were initiated with 10 randomly selected pixel values.
Fig. 3 shows the performance as a function of iterations done, showing the Sum
kernel performs better than the RBF kernel on the Strong subset. For the
selection subset, the Random baseline beats the RBF baseline. This indicates
that the problem is hard for BO, as would be expected from the example images
in Fig. 2. The Product kernel outperforms the other kernels on the distance
metric, while the ratio metric is very similar for all methods. Fig. 4 looks
more closely at the performance on the Selection subset as a function of the
maximum pollution concentration present in each image. It shows that the
performance improves with higher levels of pollution and also that over most
of the concentration values the Product kernel is better than the RBF.

Figure 3: Comparison of kernel performance on Strong and Selection subsets.
$\hat{x}$ is the estimated maximiser and $x^{*}$ the true maximiser. $\hat{y}$
and $y^{*}$ are the true concentration values at $\hat{x}$ and $x^{*}$,
respectively. Both metrics are shown as means with standard deviation of the
mean in dotted lines. The Sum kernel reaches slightly better values than the
RBF kernel on the Strong subset, and the Product kernel outperforms the other
kernels on the distance metric on the Selection subset. Figure 4: Inspection
of performance after 100 iterations over the range of concentrations in the
Selection subset. Each line shows the running average of the 20 previous
values. $\hat{x}$, ${x^{*}}$, $\hat{y}$ and $y^{*}$ as defined for Fig. 3. As
can be seen the Product kernel outperforms RBF across most concentration.

##  4 Discussion and future work

By augmenting a standard RBF kernel with a directional element that captures
the prevailing wind direction, we can better capture the covariance structure
in NO2 pollution, as indicated by the BIC scores. The results also show that
this better estimates pollution maxima and the locations of those maxima for
some of the images. The improvement was less clear than we expected from the
BIC scores. We hypothesise that this is due to the hyperparameter tuning,
which the results were sensitive to. For an example, see the Supplementary
Material. Therefore, we plan to improve our priors by basing them on a larger
tuning set and using hierarchical modelling. Additionally, the wind-informed
kernels should be tested on more data sets, and particularly on data sets of
urban air pollution. As wind is also important in moving air pollution over
short distances one would expect improvement, but this might be distorted by
other factors, like buildings. The approach used, of incorporating a data
transformation into the covariance function, can be extended to other kernels,
e.g. the set of Matérn kernels, or combined in other ways, e.g. a combination
of Sum and Product kernels.

## Acknowledgments and Disclosure of Funding

The authors would like to thank Dr Douglas Finch at the University of
Edinburgh for extracting the data and helpful correspondence.

This work was supported in part by the EPSRC Centre for Doctoral Training in
Data Science, funded by the UK Engineering and Physical Sciences Research
Council (grant EP/L016427/1) and the University of Edinburgh.

## References

## References

  * Cohen et al. [2017] Aaron J Cohen, Michael Brauer, Richard Burnett, H Ross Anderson, Joseph Frostad, Kara Estep, Kalpana Balakrishnan, Bert Brunekreef, Lalit Dandona, Rakhi Dandona, Valery Feigin, Greg Freedman, Bryan Hubbell, Amelia Jobling, Haidong Kan, Luke Knibbs, Yang Liu, Martin Randall, and Mohammad H Forouzanfar.  Estimates and 25-year trends of the global burden of disease attributable to ambient air pollution: an analysis of data from the Global Burden of Diseases Study 2015.  _The Lancet_ , 389(10082):1907–1918, May 2017\.  ISSN 0140-6736.  doi: 10.1016/S0140-6736(17)30505-6.  URL https://www.sciencedirect.com/science/article/pii/S0140673617305056.
  * Lelieveld et al. [2015] J. Lelieveld, J. S. Evans, M. Fnais, D. Giannadaki, and A. Pozzer.  The contribution of outdoor air pollution sources to premature mortality on a global scale.  _Nature_ , 525(7569):367–371, September 2015\.  ISSN 1476-4687.  doi: 10.1038/nature15371.  URL https://www.nature.com/articles/nature15371.  Number: 7569 Publisher: Nature Publishing Group.
  * Carminati et al. [2017] Marco Carminati, Giorgio Ferrari, and Marco Sampietro.  Emerging miniaturized technologies for airborne particulate matter pervasive monitoring.  _Measurement_ , 101:250–256, April 2017.  ISSN 0263-2241.  doi: 10.1016/j.measurement.2015.12.028.  URL http://www.sciencedirect.com/science/article/pii/S0263224115006880.
  * Liu et al. [2020] Xiaoting Liu, Rohan Jayaratne, Phong Thai, Tara Kuhn, Isak Zing, Bryce Christensen, Riki Lamont, Matthew Dunbabin, Sicong Zhu, Jian Gao, David Wainwright, Donald Neale, Ruby Kan, John Kirkwood, and Lidia Morawska.  Low-cost sensors as an alternative for long-term air quality monitoring.  _Environmental Research_ , 185:109438, June 2020.  ISSN 0013-9351.  doi: 10.1016/j.envres.2020.109438.  URL http://www.sciencedirect.com/science/article/pii/S0013935120303315.
  * Smith et al. [2019] Michael T. Smith, Joel Ssematimba, Mauricio A. Alvarez, and Engineer Bainomugisha.  Machine Learning for a Low-cost Air Pollution Network.  _NeurIPS 2019 Workshop on Machine Learning for the Developing World_ , December 2019.  URL http://arxiv.org/abs/1911.12868.  arXiv: 1911.12868.
  * Liu et al. [2016] Xiuming Liu, Teng Xi, and Edith Ngai.  Data Modelling with Gaussian Process in Sensor Networks for Urban Environmental Monitoring.  In _2016 IEEE 24th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS)_ , pages 457–462, September 2016.  doi: 10.1109/MASCOTS.2016.45.  ISSN: 2375-0227.
  * Liu et al. [2018] Hongbin Liu, Chong Yang, Mingzhi Huang, Dongsheng Wang, and ChangKyoo Yoo.  Modeling of subway indoor air quality using Gaussian process regression.  _Journal of Hazardous Materials_ , 359:266–273, October 2018.  ISSN 0304-3894.  doi: 10.1016/j.jhazmat.2018.07.034.  URL http://www.sciencedirect.com/science/article/pii/S0304389418305648.
  * Fei et al. [2020] Haolin Fei, Xiaofeng Wu, Chunbo Luo, and Yang Luo.  Accurate Air Quality Prediction: A Physical-Temporal Collection Model.  In _ICLR Workshop on AI for Earth Science_ , 2020.  URL https://www.researchgate.net/publication/341445468_ACCURATE_AIR_QUALITY_PREDICTION_A_PHYSICAL-_TEMPORAL_COLLECTION_MODEL_CONFERENCE_SUBMISSIONS.
  * Wen et al. [2019] Congcong Wen, Shufu Liu, Xiaojing Yao, Ling Peng, Xiang Li, Yuan Hu, and Tianhe Chi.  A novel spatiotemporal convolutional long short-term neural network for air pollution prediction.  _Science of The Total Environment_ , 654:1091–1099, March 2019.  ISSN 0048-9697.  doi: 10.1016/j.scitotenv.2018.11.086.  URL http://www.sciencedirect.com/science/article/pii/S0048969718344413.
  * Marchant and Ramos [2012] R. Marchant and F. Ramos.  Bayesian optimisation for Intelligent Environmental Monitoring.  In _2012 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , pages 2242–2249, October 2012.  doi: 10.1109/IROS.2012.6385653.
  * Morere et al. [2017] Philippe Morere, Roman Marchant, and Fabio Ramos.  Sequential Bayesian optimization as a POMDP for environment monitoring with UAVs.  In _2017 IEEE International Conference on Robotics and Automation (ICRA)_ , pages 6381–6388, May 2017.  doi: 10.1109/ICRA.2017.7989754.
  * Singh et al. [2010] A. Singh, F. Ramos, H. D. Whyte, and W. J. Kaiser.  Modeling and decision making in spatio-temporal processes for environmental surveillance.  In _2010 IEEE International Conference on Robotics and Automation_ , pages 5490–5497, May 2010.  doi: 10.1109/ROBOT.2010.5509934.
  * Samson [1988] Perry J Samson.  Atmospheric Transport and Dispersion of Air Pollutants Associated with Vehicular Emissions.  In Ann Y. Watson, Richard R. Bates, and Donald Kennedy, editors, _Air Pollution, the Automobile, and Public Health_. National Academies Press (US), 1988.  URL https://www.ncbi.nlm.nih.gov/books/NBK218142/.  Publication Title: Air Pollution, the Automobile, and Public Health.
  * Reggente and Lilienthal [2009] Matteo Reggente and Achim J. Lilienthal.  Using local wind information for gas distribution mapping in outdoor environments with a mobile robot.  In _2009 IEEE SENSORS_ , pages 1715–1720, October 2009.  doi: 10.1109/ICSENS.2009.5398498.  ISSN: 1930-0395.
  * Asenov et al. [2019] Martin Asenov, Marius Rutkauskas, Derryck Reid, Kartic Subr, and Subramanian Ramamoorthy.  Active Localization of Gas Leaks Using Fluid Simulation.  _IEEE Robotics and Automation Letters_ , 4(2):1776–1783, April 2019.  ISSN 2377-3766.  doi: 10.1109/LRA.2019.2895820.  Conference Name: IEEE Robotics and Automation Letters.
  * Luo et al. [2016] Kai Luo, Runkui Li, Wenjing Li, Zongshuang Wang, Xinming Ma, Ruiming Zhang, Xin Fang, Zhenglai Wu, Yang Cao, and Qun Xu.  Acute Effects of Nitrogen Dioxide on Cardiovascular Mortality in Beijing: An Exploration of Spatial Heterogeneity and the District-specific Predictors.  _Scientific Reports_ , 6(1):38328, December 2016\.  ISSN 2045-2322.  doi: 10.1038/srep38328.  URL https://www.nature.com/articles/srep38328.  Number: 1 Publisher: Nature Publishing Group.
  * Shahriari et al. [2016] Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P. Adams, and Nando de Freitas.  Taking the Human Out of the Loop: A Review of Bayesian Optimization.  _Proceedings of the IEEE_ , 104(1):148–175, January 2016.  ISSN 1558-2256.  doi: 10.1109/JPROC.2015.2494218.  Conference Name: Proceedings of the IEEE.
  * Srinivas et al. [2012] Niranjan Srinivas, Andreas Krause, Sham M. Kakade, and Matthias Seeger.  Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design.  _IEEE Transactions on Information Theory_ , 58(5):3250–3265, May 2012.  ISSN 0018-9448, 1557-9654.  doi: 10.1109/TIT.2011.2182033.  URL http://arxiv.org/abs/0912.3995.  arXiv: 0912.3995.
  * Hernández-Lobato et al. [2014] José Miguel Hernández-Lobato, Matthew W Hoffman, and Zoubin Ghahramani.  Predictive Entropy Search for Efficient Global Optimization of Black-box Functions.  _Advances in Neural Information Processing Systems 27_ , pages 918–926, 2014.
  * Rasmussen and Williams [2006] Carl Edward Rasmussen and Christopher K. I. Williams.  _Gaussian Processes for Machine Learning_.  MIT Press, 2006.
  * Cats and Holtslag [1980] GJ Cats and AAM Holtslag.  Prediction of air pollution frequency distribution—Part I. The lognormal model.  _Atmospheric Environment (1967)_ , 14:255–258, 1980.  URL https://www.sciencedirect.com/science/article/pii/0004698180902851.
  * Schwarz [1978] Gideon Schwarz.  Estimating the dimension of a model.  _The annals of statistics_ , 6(2):461–464, 1978\.

##  Appendix A Supplementary Material

Supplementary material for _Optimising Placement of Pollution Sensors in Windy
Environments_ by Sigrid Passano Hellan, Christopher G. Lucas and Nigel H.
Goddard presented at the AI for Earth Sciences Workshop at NeurIPS 2020.

###  A.1 Data

The data were collected by the TROPOspheric Measuring Instrument (TROPOMI)
aboard the Sentinel 5P satellite,111Copernicus, https://www.copernicus.eu/en
and were extracted and shared with us by Dr Douglas Finch at the University of
Edinburgh. In the original data source, the NO2 data used is given in the
column labelled ’level 2 nitrogen dioxide tropospheric’. Images covering
mostly oceans were excluded.

###  A.2 BIC scores

The Bayesian information criterion (BIC) scores of the tuning sets referred to
in Section 3 are given in Table 1. The values are given as differences because
the obtained BIC scores varied a lot between problems, e.g. between 306 and
-1014 for the Sum kernel on the Strong subset. As can be seen, the relative
differences vary a lot less.

Table 1: Differences in Bayesian information criterion (BIC) scores obtained on tuning sets. Mean (standard deviation of mean). The wind-informed kernels were better able to explain the data for the Strong and Median subsets. There was little difference for the Weak subset, where the images were very noisy. | Sum - Product | Sum - RBF | Product - RBF
---|---|---|---
Strong tune | 13.43 (3.69) | 19.92 (3.44) | 6.49 (2.75)
Median tune | 2.69 (1.95) | 10.02 (4.30) | 7.33 (3.73)
Weak tune | 0.35 (0.58) | -1.12 (1.72) | -1.47 (1.34)

###  A.3 Implementation notes

A small amount of noise was added to sampled values in the BO loop for
numerical stability. At each iteration in the BO loop 100 hyperparameter seeds
were sampled from the priors and used as starting points for the GP tuning.
The setting which maximised the posterior log marginal likelihood was then
used. When estimating the hyperparameter priors, Bessel’s correction was used
for the variance estimate.

###  A.4 Hyperparameter prior sensitivity

Fig. 5 shows the results on the Strong subset when a slightly different prior
was used for the hyperparameters, as referred to in Section 4 of the main
paper.

Figure 5: Comparison of kernel performance on Strong subsets, when biased
estimates of variances of hyperparameter priors are used, i.e. not using
Bessel’s correction. Compare to Fig. 3 in body of paper. With these settings,
the Product kernel performs best. Comparing the figures, the Product kernel
has improved but the RBF worsened. $\hat{x}$ is the estimated maximiser and
$x^{*}$ the true maximiser. $\hat{y}$ and $y^{*}$ are the true concentration
values at $\hat{x}$ and $x^{*}$, respectively.


# Background independence and field redefinitions in quantum gravity

Roberto Casadioab, Alexander Kamenshchikab, and Iberê Kuntzc

aDipartimento di Fisica e Astronomia, Università di Bologna
via Irnerio 46, 40126 Bologna, Italy

bI.N.F.N., Sezione di Bologna, I.S. FLAG
viale B. Pichat 6/2, 40127 Bologna, Italy

cDepartamento de Física, Universidade Federal do Paraná
PO Box 19044, Curitiba – PR, 81531-980, Brazil E-mail<EMAIL_ADDRESS>mail<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

It is generally believed that a full-fledged theory of quantum gravity should
exhibit background independence and diffeomorphism invariance. In its most
general form, the latter comprises field redefinitions, which are
diffeomorphisms in configuration space. We show that any path-integral
approach to quantum gravity leads to a tension between these properties, such
that they cannot hold simultaneously.

##  1 Introduction

Background independence and covariance are the basic building blocks of
general relativity. Both concepts are intertwined with the diffeomorphism
invariance of gravity and has led to a long history of confusion [1, 2, 3].
Anderson [3] was the first to put such concepts into a more precise language
by demarcating the differences of absolute and dynamical structures. Although
not free of inconsistencies [4], Anderson’s approach delineates the role
played by the diffeomorphism group in gravitational and non-gravitational
theories, which is a stepstone for defining covariance and background-
independence rigorously.

These concepts are also believed to play a fundamental role in the
quantization of gravity. The conventional perturbative approach of quantum
field theory singles out a background metric required for the vacuum structure
of the theory. Because this background is not dynamical, it violates the
background independence of general relativity. Allowing for this possibility,
but insisting on the invariance under diffeomorphisms, is the cornerstone of
string theory [5, 6]. Loop quantum gravity, on the other hand, has been
developed as a background-independent theory ab initio [7]. Nonetheless, the
absence of spacetime structures makes it difficult to recover well-tested
results of quantum field theory at low energies.

Quantum field theories of gravity can also be formulated, to some extent, in a
background-independent manner. This is indeed implemented with the background
field method [8], where a separation of quantum perturbations from (dynamical)
background fields is performed. The background field method was introduced as
a convenient way to deal with gauge theories, in such a way that the gauge
symmetry could be preserved at the background level while fixing the gauge for
the quantum perturbations. The resulting action is therefore gauge invariant,
which eases tremendously some calculations, such as the proof of
renormalizability.

The background field, despite its name, need not be chosen a priori. It need
not even satisfy the classical equations of motion. Indeed, the background
field should solve the effective equations of motion. It is in this sense that
a quantum field theory of gravity can be background independent [9].
Nonetheless, this construction requires the definition of the asymptotic
vacuum state, thus restricting the set of background metric solutions to the
ones with sufficient asymptotic symmetry. We stress, however, that it is the
asymptotic boundary conditions rather than the background metric that are
fixed beforehand.

When the background field is not chosen as a solution to the field equations,
the effective action turns out to depend on the gauge. One thus reaches an
impasse, where either a background is picked up a priori, violating the
background independence of general relativity but whose predictions are gauge-
independent, or the background is solved for a posteriori, which respects
background independence but suffers from gauge dependence. This issue is
solved within the Vilkovisky-DeWitt formalism [10, 11], where a Levi-Civita
connection in configuration space is introduced to cancel out the gauge-
dependence while maintaining the background fields (including the metric)
arbitrary. The cancellation of the gauge dependence also extends the
invariance of on-shell scattering amplitudes under field redefinitions to off-
shell correlation functions. We note that field redefinitions are nothing else
than diffeomorphisms in configuration space. In the remainder of this article,
covariance shall thus mean both spacetime and configuration-space covariance.

The purpose of this paper is to show that quantum field theories of gravity,
even within the formalism of Vilkovisky-DeWitt, cannot consistenly satisfy
both background-independence (absence of any non-dynamical structure) and
covariance (under spacetime diffeomorphisms and field redefinitions) at the
same time. As we shall show, the latter necessarily requires absolute
structures to be introduced, which in turn violates the former, whereas a
theory that satisfies the former does not possess the correct transformation
properties, thus violating the latter.

##  2 The geometrical effective action

A valuable property of quantum field theory regards the invariance of the
S-matrix under field redefinitions [12]. Scattering amplitudes are indeed the
observables of interest in Particle Physics, thus their invariance under field
reparameterizations seems to suggest some profound principle. Observables in
Astrophysics and Cosmology are, however, correlation functions and these do
not transform covariantly in the standard formulation of quantum field theory.
One could argue that this proves the absence of such a general principle.
Nonetheless, in a gauge theory, field-parameterization dependence induces
gauge dependence in the observables. The former is, therefore, a genuine
issue.

The origin of this gauge dependence is most easily seen by the naive effective
action

$\exp\left(\frac{i}{\hbar}\,\Gamma_{\text{N}}[\phi]\right)=\int\mathcal{D}\varphi\,\exp\left\\{\frac{i}{\hbar}\left[S[\varphi]+(\varphi^{i}-\phi^{i})\frac{\delta\Gamma_{\text{N}}}{\delta\phi^{i}}\right]\right\\}\
,$ (2.1)

where $\varphi^{i}=\varphi^{I}(x)$ collectively denotes an arbitrary set of
fields with classical action $S[\varphi]$ and $\phi^{i}$ is the mean field.
The set of all $\varphi^{i}$ is the configuration space, formally defined by
the infinite-dimensional space

$\mathcal{C}(M)=\prod_{x}\mathcal{N}(x)\ ,$ (2.2)

where $\mathcal{N}(x)$ denotes the finite-dimensional space formed by all
$\varphi^{I}(x)$ evaluated at the same spacetime point $x\in M$. Under gauge
transformations or field redefinitions, neither the path-integral measure nor
the second term within the curly brackets in Eq. (2.1) remains invariant. One
can impose invariance in the former by introducing a configuration-space
metric $G_{ij}$, whereas the latter calls for a configuration-space connection
$\Gamma^{k}_{ij}$ compatible with $G_{ij}$. This procedure results in the
Vilkovisky-DeWitt effective action [10, 11].

For the sake of simplicity, in this paper we shall omit the connection-
dependent term and focus on the functional measure 111For this reason, our
argument also applies to any construction of the path integral where a
functional measure is required, like in non-linear sigma models.. This is
justified because of the compatibility property of the aforementioned
connection, which then provides no additional absolute structures (to be
defined in Section 3) other than the already present metric $G_{ij}$, thus not
altering our argument of Section 4. The improved effective action shall then
be written as

$\exp\left(\frac{i}{\hbar}\Gamma_{\text{VD}}[\phi]\right)=\int\mathcal{D}\varphi\sqrt{\operatorname{Det}{G_{ij}}}\,\exp\left(\frac{i}{\hbar}S[\varphi]\right)\
,$ (2.3)

where $\operatorname{Det}$ denotes the functional determinant.

##  3 Background independence and covariance

In this section, we shall review Anderson’s efforts [3] to define covariance
rigorously. In the notations of [4], a theory’s equations of motion are
generally of the form

$\mathcal{F}(\gamma,\phi,\Sigma)=0\ ,$ (3.1)

where $\gamma$ denotes all structures defined by maps into spacetime (e.g. a
particle’s trajectory) and $\phi$ denotes collectively all structures
represented by maps from spacetime (e.g. fields). Here $\Sigma$ is a given
non-dynamical structure defined on the spacetime $M$ for which the equations
of motion (3.1) can be solved for $(\gamma,\phi)$. A theory is called
covariant iff, for every $f\in\text{Diff}(M)$,

$\mathcal{F}(f\cdot\gamma,f\cdot\phi,f\cdot\Sigma)=0\iff\mathcal{F}(\gamma,\phi,\Sigma)=0\
,$ (3.2)

where the dot product $f\cdot X$ denotes the action of $f$, by means of
pullback/pushforward, on the object $X$. On the other hand, a theory is said
to be invariant iff, for all $f\in\text{Diff}(M)$,

$\mathcal{F}(f\cdot\gamma,f\cdot\phi,\Sigma)=0\iff\mathcal{F}(\gamma,\phi,\Sigma)=0\
.$ (3.3)

The subtle difference lies on the transformation of the non-dynamical
structure $\Sigma$. Covariance is the requirement for the theory to be well-
defined geometrically, i.e. for the theory to live on $M$. Thus, when some
structure is transformed under a diffeomorphism, all other structures of the
theory are transformed along to counteract the differences and keep their
relation the same. Invariance, on the other hand, requires solutions of the
theory to be transformed into other solutions for the same $\Sigma$. The
latter is much more restrictive and constitutes an important guiding principle
in physics.

The structure $\Sigma$ is called an absolute structure if it is a field that
either is not dynamical or whose solutions are all locally diffeomorphic to
each other. One can then define a background-independent theory as a theory
which contains no absolute structure. Notice that, in this case, covariance
equals invariance.

In special relativity, for instance, the absolute structure is the Minkowski
metric $\Sigma=\\{\eta_{\mu\nu}\\}$. The passage to general relativity is
characterized by making the metric dynamical $\eta_{\mu\nu}\to g_{\mu\nu}$.
Now $g_{\mu\nu}$ is not given, thus $\Sigma=\varnothing$, but is found a
posteriori as a solution of Einstein’s field equations, hence
$\phi=\\{g_{\mu\nu}\\}$.

As we anticipated in the Introduction, Anderson’s definitions are not
flawless. To see this, one can write the dynamics of a scalar field in special
relativity in a diffeomorphism-invariant form as

$\displaystyle g^{\mu\nu}\,\nabla_{\mu}\nabla_{\nu}\Phi$ $\displaystyle=0\ ,$
(3.4) $\displaystyle R_{\mu\nu\rho\sigma}$ $\displaystyle=0\ .$ (3.5)

According to Anderson’s definitions, this would also make special relativity
background independent, which is an obvious flaw. First of all, Anderson’s
definition of an absolute structure does not entail the action-reaction
principle. While $\eta_{\mu\nu}$ is obtained dynamically, thereby acting on
$\Phi$, it is not acted upon by $\Phi$. A fully dynamical field should have a
symmetrical role where it acts on and is also acted upon by other fields.
Interactions are indeed always symmetric.

The source of the problem lies in the fact that Eq. (3.5) is not a dynamical
equation, but rather a constraint. In fact, the most general solution
$g_{\mu\nu}=\alpha\,\eta_{\mu\nu}$, for any non-zero constant $\alpha$, does
not contain enough integration constants to fully account for the initial
conditions, hence the Cauchy evolution is ill-defined. Furthermore, Eq. (3.5)
does not follow from any diffeomorphism-invariant action unless a Lagrange
multiplier is introduced, which stresses the fact that this equation is a
constraint.

In view of the above issues, we shall refine the definitions of covariance,
invariance and background independence. Rather than basing our definitions on
the equations of motion, our proposal shall be performed at the level of the
effective action. This not only avoids the issues outlined above, but
generalises the discussion to the quantum realm, which is our main concern.
Moreover, the equations of motion do not capture important physical effects
contained in the boundary terms (vide black hole entropy). The effective
action, on the other hand, contains information about all physics at classical
or quantum scales.

We shall define an absolute structure $\Sigma$ as any local object that does
not contain a corresponding kinetic term in the effective action. A theory is
then called covariant iff, for every $f\in\text{Diff}(\mathcal{C}(M))$, the
effective action transforms as

$\Gamma[f\cdot\phi,f\cdot\Sigma]=\Gamma[\phi,\Sigma]\ ,$ (3.6)

whereas we say that it is invariant iff, for every
$f\in\text{Diff}(\mathcal{C}(M))$, we have 222More generally, a symmetry group
$G\subset\text{Diff}(\mathcal{C}(M))$ of some
$\text{Diff}(\mathcal{C}(M))$-covariant theory is the group that leaves the
absolute structure $\Sigma$ invariant. An invariant theory is thus invariant
under the largest symmetry group $G=\text{Diff}(\mathcal{C}(M))$.

$\Gamma[f\cdot\phi,\Sigma]=\Gamma[\phi,\Sigma]\ .$ (3.7)

Because we are interested in a fundamental theory, where all interactions are
entirely described with fields, we have not included $\gamma$ in our
definitions. We should also stress that, like in Anderson’s formulation,
$\Sigma$ is really any non-dynamical object, not necessarily a spacetime
object. A theory is then said to be background independent whenever
$\Sigma=\varnothing$.

We stress that some absolute global framework shall always be needed in order
to define a workable mathematical theory of physical phenomena. For instance,
the spacetime $(M,g_{\mu\nu})$ should be globally hyperbolic in order to give
rise to well-posed Cauchy problems in classical general relativity [13], and
similarly in (classical or quantum) field theories, although such restrictions
are sometimes lifted or overlooked. This means that properties like the
dimension, topology, and differential structures of the spacetime (or field
space) must be fixed to some extent from the onset when describing specific
systems. In practical terms, our discussion of background independence will
therefore concern the existence of a fixed (local) metric at some level of
mathematical abstraction, as we will further clarify in the following.

Before we proceed, it is important to recall that observables in general
relativity are mathematically given by scalars built out of (pairs of) tensors
pertaining to the quantity to be measured and the measuring apparatus
(observer). 333This is the main idea behind the “relational” approach to
(quantum) physics (see [14] and references therein). The prototype is given by
the energy of a particle, which is obtained by the contraction of the
particle’s 4-velocity $u^{\mu}$ with the observer’s 4-velocity $U^{\mu}$, that
is

$\displaystyle E=-g_{\mu\nu}\,u^{\mu}\,U^{\nu}\ ,$ (3.8)

where $g_{\mu\nu}$ is the background metric tensor. Similarly, one might
notice that fields in configuration space have no direct physical meaning.
This makes fields like spacetime coordinates but also as tensor quantities in
spacetime: proper observables, like scattering cross sections, are built out
of fields by (more or less) involved “scalarizations” involving the measuring
apparatus.

##  4 Background independence and field redefinitions

At the level of the naive effective action
$\Gamma^{(0)}[\phi]\equiv\Gamma_{\text{N}}[\phi]$, no absolute structure
exists, thus $\Sigma=\varnothing$ and the covariance (3.6) collapses into
invariance (3.7). However, like we saw in Section 2, $\Gamma^{(0)}[\phi]$
depends on the field parameterization and, therefore, does not satisfy
invariance (3.7).

This can be amended by the introduction of a configuration-space metric
$G_{ij}$, which is used to define an invariant path-integral measure and
ultimately results in the Vilkovisky-DeWitt effective action
$\Gamma^{(1)}[\phi,\Sigma]\equiv\Gamma_{\text{VD}}[\phi,G]$. Although
$\Gamma^{(1)}[\phi,\Sigma]$ satisfies invariance (3.7), we now have an
absolute structure $\Sigma=\\{G_{ij}\\}$ that renders the theory background
dependent.

Let us make the theory background independent by promoting $G_{ij}$ to a
dynamical structure. On assuming ultralocality,

$G_{ij}=G_{IJ}\,\delta(x,x^{\prime})\ ,$ (4.1)

one could envisage doing so by introducing the action

$S=\int\mathrm{d}^{n}x\sqrt{-g}\,\mathcal{L}(G_{IJ},R_{IJMN})\ ,$ (4.2)

where $R_{IJMN}$ is the Riemann tensor of the finite-dimensional space
$\mathcal{N}$ and $\mathcal{L}(G_{IJ},R_{IJMN})$ is some Lagrangian invariant
under spacetime and configuration-space diffeomorphisms. The precise form of
the action for $G_{IJ}$ is not essential to our argument as the only crucial
point to the following is the existence of dynamics (regardless of the
particular kind of evolution). One could, for example, assume that such a
Lagrangian takes the Einstein-Hilbert form

$\mathcal{L}(G_{IJ},R_{IJMN})=G^{IJ}R_{IJ}\ ,$ (4.3)

where $R_{IJ}=G^{MN}R_{MINJ}$ is the configuration-space Ricci tensor.

With a dynamical configuration space, there is no other absolute structure
present, thus the theory recovers its background independence
$\Sigma=\varnothing$. However, this came at the cost of introducing the
additional degree of freedom $G_{ij}$ in the theory, which must be quantised
along with $\varphi^{i}$. In the absence of external sources, the quantum
theory then reads

$\exp\left(\frac{i}{\hbar}\,\Gamma^{(2)}[\phi]\right)=\int\mathcal{D}\phi\mathcal{D}G_{ij}\,\sqrt{\operatorname{Det}G_{ij}}\exp\left(\frac{i}{\hbar}\,S[\phi,G]\right)\
,$ (4.4)

The functional measure

$\mathcal{D}\phi\,\mathcal{D}G_{ij}\,\sqrt{\operatorname{Det}G_{ij}}=\prod_{x,\,I<J}\mbox{${\rm
d}$}\phi\,\mbox{${\rm d}$}G_{IJ}\sqrt{\det G_{IJ}}$ (4.5)

does not transform covariantly. To see this, it is sufficient to perform an
infinitesimal field redefinition

$G_{ij}\to G^{\prime}_{ij}=G_{ij}+\xi_{ij}(G)\ ,$ (4.6)

under which the functional measure transforms as

$\mathcal{D}G^{\prime}_{ij}\sqrt{\operatorname{Det}G^{\prime}_{ij}}=\mathcal{D}G_{ij}\sqrt{\operatorname{Det}G_{ij}}\left(1+G^{mn}\xi_{mn}+\frac{\delta\xi_{mn}}{\delta
G_{mn}}\right)\ .$ (4.7)

Promoting $G_{ij}$ to a dynamical field thus brings back the violation of
invariance under field redefinitions. To correct this, one unavoidably needs
to introduce some absolute structure $\mathcal{S}^{(2)}$ that transforms in
such a way that 444Should the geometrical construction be maintained,
$\mathcal{S}^{(2)}=\sqrt{\operatorname{Det}G^{(2)}_{i_{2}j_{2}}}$ would
correspond to the determinant of a second-order functional metric
$G^{(2)}_{i_{2}j_{2}}$ defined on a second-order configuration space
$\mathcal{C}^{(2)}(M)$, where now the indices $i_{2},j_{2}$ include the new
field $G_{ij}$.

$\mathcal{D}\phi\mathcal{D}G^{\prime}_{ij}\sqrt{\operatorname{Det}G^{\prime}_{ij}}\,\mathcal{S}^{(2)^{\prime}}=\mathcal{D}\phi\mathcal{D}G_{ij}\sqrt{\operatorname{Det}G_{ij}}\,\mathcal{S}^{(2)}\
,$ (4.8)

which recovers background dependence since $\Sigma=\\{\mathcal{S}^{(2)}\\}$.
We thus see that promoting $\mathcal{S}^{(n)}$ to a dynamical field requires,
upon quantization, that an absolute structure
$\Sigma=\\{\mathcal{S}^{(n+1)}\\}$ be introduced, hence the effective action
$\Gamma^{(n)}[\phi,\Sigma]$ can never satisfy invariance (3.7) and background
independence $\Sigma=\varnothing$ at the same time.

In summary, although we have been able to recover background independence by
making $G_{ij}$ dynamical, we lost invariance in the full quantum theory where
$G_{ij}$ belongs to the spectrum. To regain invariance we would need to
include another layer of abstraction (a sort of über-field space) with yet
another higher-order absolute structure, which would then face the problems
with background dependence and so on and so forth. This process continues ad
infinitum, proving the existence of a tension between background independence
and covariance in quantum gravity.

##  5 Conclusions

In this paper, we have considered extended notions of diffeomorphism
invariance and background independence related to the (non) existence of some
fixed metric structure at the quantum level. In this context, diffeomorphism
invariance also comprises invariance of observables under field redefinitions,
which are required to enforce gauge independence in the correlation functions.
Likewise, a metric structure in field space is naturally introduced by any
given dynamical theory.

We have then shown that diffeomorphism invariance and background independence,
in the extended sense of the absence of any fixed metric structure at any
level, cannot coexist. While the former is unavoidable for any sensible
physical theory, the latter does not seem to be rooted in any physical
property other than an aesthetic appeal (to some). Therefore, one possible and
natural implication of our finding is that quantum gravity is actually
background dependent (at some level in the hierarchy of mathematical
structures described at the end of the last section). On the other hand,
should background independence be revealed as an intrinsic aspect of Nature,
models of quantum gravity based on quantum field theory, such as asymptotic
safety and causal dynamical triangulation, would become effective rather than
fundamental theories.

## Acknowledgments

R.C. and A.K. are partially supported by the INFN grant FLAG. The work of R.C.
has also been carried out in the framework of activities of the National Group
of Mathematical Physics (GNFM, INdAM).

## References

  * [1] J. D. Norton, Rep. Prog. Phys. 56 791 (1993) 791.
  * [2] O. Pooley, Einstein Stud. 13 (2017) 105 [arXiv:1506.03512 [physics.hist-ph]].
  * [3] J. L. Anderson, “Principles of Relativity Physics”, Academic Press, 1967\.
  * [4] D. Giulini, Lect. Notes Phys. 721 (2007) 105. [arXiv:gr-qc/0603087 [gr-qc]].
  * [5] J. Polchinski, “String theory. Vol. 1: An introduction to the bosonic string,” Cambridge University Press, 2007.
  * [6] J. Polchinski, “String theory. Vol. 2: Superstring theory and beyond,” Cambridge University Press, 2007.
  * [7] C. Rovelli, “Quantum gravity,” Cambridge University Press, 2004.
  * [8] L. F. Abbott, Acta Phys. Polon. B 13 (1982), 33 CERN-TH-3113.
  * [9] M. Reuter, Phys. Rev. D 57 (1998) 971 [arXiv:hep-th/9605030 [hep-th]]; M. Becker and M. Reuter, Phys. Rev. D 102 (2020) 125001 [arXiv:2008.09430 [gr-qc]]; Phys. Rev. D 104 (2021) 125008 [arXiv:2109.09496 [hep-th]].
  * [10] G. A. Vilkovisky, Nucl. Phys. B 234 (1984) 125.
  * [11] B. S. DeWitt, “The effective action”, in Batalin, I.A. (Ed.) et al.: Quantum field theory and quantum statistics, Vol. 1, 191-222.
  * [12] A. Rebhan, Nucl. Phys. B 298 (1988) 726.
  * [13] K. Landsman, “Reopening the Hole Argument,” [arXiv:2206.04943 [gr-qc]].
  * [14] C. Rovelli, “The Relational Interpretation of Quantum Physics,” [arXiv:2109.09170 [quant-ph]].


∎

11institutetext: Julian Nickerl 22institutetext: University of Ulm
Tel.: +49 (0)731 50 24256
Fax: +49 (0)731 50 1224101
22email<EMAIL_ADDRESS>
# The Minimum Tollbooth Problem in
Atomic Network Congestion Games with Unsplittable Flows

Julian Nickerl

(24 June 2019)

###### Abstract

This work analyzes the minimum tollbooth problem in atomic network congestion
games with unsplittable flows. The goal is to place tolls on edges, such that
there exists a pure Nash equilibrium in the tolled game that is a social
optimum in the untolled one. Additionally, we require the number of tolled
edges to be the minimum. This problem has been extensively studied in non-
atomic games, however, to the best of our knowledge, it has not been
considered for atomic games before.

By a reduction from the weighted CNF SAT problem, we show both the NP-hardness
of the problem and the W[2]-hardness when parameterizing the problem with the
number of tolled edges. On the positive side, we present a polynomial time
algorithm for networks on series-parallel graphs that turns any given state of
the untolled game into a pure Nash equilibrium of the tolled game with the
minimum number of tolled edges.

###### Keywords:

Atomic Network Congestion Games Minimum Tollbooth Problem Series-Parallel
Graph Social Optimum Unsplittable Flow Weighted CNF SAT

##  1 Introduction

A class of games that are guaranteed to admit at least one pure Nash
equilibrium are congestion games, as introduced by Rosenthal
rosenthal1973class . However, several well-known results (for example
presented by Christodoulou and Koutsoupias christodoulou2005price  or
Roughgarden and Tardos roughgarden2002bad ) indicate, that playing a Nash
equilibrium rarely leads to a state that is socially beneficial. Especially in
network congestion games, an approach to push the players towards a social
optimum is the levy of tolls on edges of the network. The goal of these tolls
is to turn a social optimum of the untolled game into a pure Nash equilibrium
of the tolled game. The application of such tolls was shown to be highly
beneficial (bilo2016dynamic ; cole2006much ). If we allow the number of
players to be infinite, each routing an infinitesimal amount of flow through
the network, it is well known that tolls fulfilling the property exist and can
be efficiently computed (beckmann1956studies ; cole2003pricing ;
fleischer2004tolls ; pigou1932economics ).

Games with a finite number of players are called atomic. The use of tollbooths
in atomic games has a comparably short history. One of the main differences to
the previous problem is that the strategy change of a single player has a
substantial impact on all other players. Additionally, for the non-atomic
games, it can be assumed that the resulting pure Nash equilibrium is unique,
requiring only light restrictions, see, e.g., Roughgarden and Tardos
roughgarden2002bad . As shown by Orda, Rom, and Shimkin, orda1993competitive
this is not necessarily the case in atomic games.

Further differentiating the problem leads to the question: Does it suffice
that there is at least one Nash equilibrium that corresponds to a social
optimum, or must all Nash equilibria correspond to a social optimum? Fotakis,
Karakostas, and Kolliopoulos analyzed whether tolls fulfilling the desired
properties exist. They conclude in fotakis2010existence  that in the latter
case the existence cannot be guaranteed even for simple parallel-link
networks. On the other hand, for the former case, they can confirm the
existence of tolls in games where all players share the same source node and
give a polynomial time algorithm calculating the tolls. Other work on this
topic is, e.g., Fotakis and Spirakis fotakis2008cost  or Caragiannis,
Kaklamanis, and Kanellopoulos caragiannis2006taxes . Another line of research
allows the players to split up their flow (cominetti2009impact ;
swamy2007effectiveness ). We focus on games with unsplittable flows; therefore
we do not go into detail with this other branch.

Several papers have focused on special cases of the above problem,
restricting, e.g., the height of the tolls (bonifaci2011efficiency ), the set
of tollable edges (harks2015computing ), or knowledge about the number of
players (colini2018demand ). We consider here the minimum tollbooth problem,
first introduced by Hearn and Ramana hearn1998solving . In this problem, we
additionally try to minimize the number of tolled edges. Work on this topic is
mainly restricted to non-atomic games, with several heuristics as a result
(e.g., bai2010heuristic ; bai2009combinatorial ; bai2008evolutionary ;
harwood2005genetic ; stefanello2017minimization ). The NP-hardness of the non-
atomic case with multiple commodities was shown by Bai, Hearn, and
Lawphongpanich in bai2010heuristic  and later for the single commodity case by
Basu, Lianeas, and Nikolova in basu2015new . On the positive side, Basu,
Lianeas, and Nikolova give a polynomial time algorithm, if the network is a
series-parallel graph basu2015new .

### Contribution:

In this work, we analyze the complexity of the minimum tollbooth problem for
atomic network congestion games with unsplittable flows. As mentioned before,
it is already known that such tolls may not exist considering the case in
which every pure Nash equilibrium of the tolled game must correspond to a
social optimum of the original one fotakis2010existence . Therefore, we focus
on the problem in which it is only required that there exist a pure Nash
equilibrium that corresponds to a social optimum of the untolled game. By a
reduction from the weighted CNF SAT problem, we show that the problem is NP-
hard. Furthermore, we also prove that the parameterized problem considering
the number of tollbooths as the parameter is W[2]-hard, giving evidence that
the parameterized problem is not in FPT. An additional spin-off result
originates in the nature of the reduction: Finding a social optimum in atomic
network congestion games with unsplittable flows is hard, supporting and
extending existing results (see, e.g., Chakrabarty, Mehta, and Nagarajan
chakrabarty2005fairness  or Meyers and Schulzmeyers2008complexity ).

We also show that for a non-trivial graph class, it is possible to efficiently
calculate a solution with the smallest possible number of toll booths. Based
on the algorithm by Basu, Lianeas, and Nikolova from basu2015new , we
construct a polynomial time algorithm on games based on series-parallel graphs
that turns any given state of the untolled game into a pure Nash equilibrium
of the tolled game with the minimum number of tolled edges.

##  2 Preliminaries

This section introduces essential general definitions. In an attempt to
shorten some statements, we will sometimes use the expression $[d]$ for the
set $\\{1,...,d\\}$ for any natural number $d$ throughout the work.

###### Definition 1

An atomic network congestion game is a tuple

$\Gamma=(G,N,(c_{e})_{e\in E},(s_{i},t_{i})_{i\in N})$

with $G=(V,E)$ being an undirected graph, $N=\\{1,...,n\\}$ a set of players,
$c_{e}$ non-negative, monotonically increasing cost functions from the set of
possible states of the game to the real numbers, and $(s_{i},t_{i})$ source-
sink pairs with $s_{i},t_{i}\in V$. The strategies for a player $i$ are the
paths from $s_{i}$ to $t_{i}$. The game is called symmetric, if $s_{i}=s_{j}$
and $t_{i}=t_{j}$ for all players $i$ and $j$. It is called single-source
(single-sink) if all players share the same source (sink). A state
$S=(S_{1},...,S_{n})$ is a vector of strategies of players ($S_{i}$ is a
strategy of player $i$). The congestion $n_{e}(S)$ on an edge $e$ is the
number of players using that edge in their strategy in state $S$. The cost of
a player in state $S$ is $\gamma_{i}(S)=\sum_{e\in S_{i}}c_{e}(n_{e}(S))$,
where $S_{i}$ is the strategy of player $i$ in $S$. The social cost of a state
is the sum of the costs of all players. A social optimum is a state with
minimum social cost. A state $S$ is a pure Nash equilibrium, if for every
player $i$ and every state $S^{\prime}$,
$\gamma_{i}(S)\leq\gamma_{i}((S^{\prime}_{i},S_{-i}))$. Hereby, the state
$(S^{\prime}_{i},S_{-i})$ denotes player $i$ playing his strategy from
$S^{\prime}$ and all other players remaining on their strategy of state $S$.

###### Definition 2

The minimum tollbooth problem (MINTB) on atomic network congestion games is
the task of finding tolls for the edges of the network such that a social
optimum of the untolled game is a pure Nash equilibrium in the tolled game
while tolling only the minimum necessary number of edges. The tolls are
depicted by a toll vector $\theta=(t_{e_{1}},...,t_{e_{|E|}})$, with
$t_{i}\in\mathbb{R}^{+}_{0}$. An edge $e_{i}$ is called tolled if
$t_{e_{i}}>0$, and untolled otherwise.

We say a state $S$ is implemented in an atomic network congestion game
$\Gamma^{\theta}$ if $\theta$ is a toll vector such that
$\Gamma^{\theta}=(G,N,(c_{e}^{\theta})_{e\in E},(s_{i},t_{i})_{i\in{N}})$ with
$c_{e}^{\theta}(S)=c_{e}(S)+t_{e}$ has $S$ as a pure Nash equilibrium. The
state is optimally implemented if for this purpose the minimum necessary
number of edges is tolled.

##  3 Atomic MINTB is Hard

This section gives the reduction of the weighted CNF SAT problem to the atomic
MINTB problem. We consider formulas in conjunctive normal form (CNF).

###### Definition 3

A Boolean formula $F$ is in CNF if $F=C_{1}\wedge...\wedge C_{n}$. Hereby,
$C_{i}$ is called clause and must have the form $C_{i}=(u_{i,1}\vee...\vee
u_{i,k_{i}})$. The $u_{i,j}$ are called literals, with
$u_{i,j}\in\\{x_{1},...,x_{n}\\}\cup\\{\overline{x_{1}},...,\overline{x_{n}}\\}$.
The $x_{i}$ are called variables, with $x_{i}\in\\{0,1\\}$.

###### Definition 4

weighted CNF SAT:

Input: | A Boolean formula $F$ in CNF
---|---
Parameter: | A positive integer $k$
Question: | Does $F$ have a satisfying assignment with weight $k$?

The weight of an assignment is its Hamming weight, i.e., the number of
variables with value 1.

It is well known, that weighted CNF SAT is a W[2]-complete problem, see, e.g.,
chapter 12 of downey2012parameterized  or chapter 13 of cygan2015parameterized
. This gives evidence that the problem does not lie in the class FPT.

###### Definition 5

Let $\mathcal{A}$ be a parameterized problem with parameter $k$. We say that
$\mathcal{A}$ is fixed-parameter tractable (FPT), if there exists an algorithm
solving $\mathcal{A}$ with running time in $\mathcal{O}(p(n)\cdot f(k))$.
Here, $p(n)$ is a polynomial that depends on the problem size of $\mathcal{A}$
but not on the parameter $k$, and $f(k)$ is any function that only depends on
the parameter $k$.

For more information on parameterized problems, we highly recommend
downey2012parameterized  by Downey and Fellows or cygan2015parameterized  by
Cygan et al.

We will reduce weighted CNF SAT to atomic MINTB in such a way, that the
minimum number of necessary tollbooths is exactly the minimum weight of a
satisfying assignment of the formula. We will construct an atomic network
congestion game $\Gamma_{F}$ based on formula $F$, where $F$ is in CNF with
$n$ variables $x_{1},...,x_{n}$ and $m$ clauses $C_{1},...,C_{m}$. We will
call $\Lambda^{0}_{x_{i}}$ ($\Lambda^{1}_{x_{i}}$) the number of occurrences
of variable $x_{i}$ in $F$ in negative (positive) form,
$\Lambda_{x_{i}}=\Lambda^{0}_{x_{i}}+\Lambda^{1}_{x_{i}}$ and
$\Lambda=\sum_{i=1}^{n}\Lambda_{x_{i}}$. The game will be played by a total of
$m+\Lambda+n$ players, each fulfilling a specific role. The $m$ players,
called clause players, will each try to find a strategy that can be identified
as satisfying a different clause. This will be done by each player choosing
the occurrence of a literal in the clause in order to satisfy it. The
$\Lambda$ players, or occurrence players, will ensure that while satisfying
the clauses, a variable cannot be assigned both value 0 and 1. Lastly, the $n$
players are the variable players, that will state which edges have to be
tolled to optimally implement a social optimum. Most players will have both
different sources and different sinks.

For the reduction to be correct, the game $\Gamma_{F}$ has to fulfill the
following properties:

  1. I)

Each clause player chooses a strategy that represents the satisfaction of a
different clause.

  2. II)

If two clause players choose the same variable as a representative, they both
choose either its positive or its negative form, but not a mixture.

  3. III)

Optimally implementing a social optimum requires at least $k$ toll stations,
where $k$ is the weight of the minimum satisfying assignment of $F$.

  4. IV)

From the tolled edges, the minimum satisfying assignment can be reconstructed
in polynomial time.

We start by constructing a graph for a game that satisfies property I). Only
the clause players play this game.

Let $G_{1}(V_{1},E_{1})$ be the undirected graph with

$\begin{array}[]{rcl}V_{1}&=&\\{s\\}\\\
&\cup&\\{v_{i},v_{i}^{0},v_{i}^{1}|i\in[n]\\}\\\
&\cup&\\{l^{0}_{x_{i},j,k},r^{0}_{x_{i},j,k},z^{0}_{x_{i},j}|i\in[n],j\in[\Lambda^{0}_{x_{i}}],k\in[\Lambda^{1}_{x_{i}}]\\}\\\
&\cup&\\{l^{1}_{x_{i},j,k},r^{1}_{x_{i},j,k},z^{1}_{x_{i},j}|i\in[n],j\in[\Lambda^{1}_{x_{i}}],k\in[\Lambda^{0}_{x_{i}}]\\}\\\
&\cup&\\{c_{i}|i\in[m]\\},\\\
E_{1}&=&\\{\\{s,v_{i}\\},\\{v_{i},v_{i}^{0}\\},\\{v_{i},v_{i}^{1}\\}|i\in[n]\\}\\\
&\cup&\\{\\{v_{i}^{0},l^{0}_{x_{i},j,1}\\},\\{l^{0}_{x_{i},j,k},r^{0}_{x_{i},j,k}\\},\\{r^{0}_{x_{i},j,k},l^{0}_{x_{i},j,k+1}\\}|i\in[n],j\in[\Lambda^{0}_{x_{i}}],\\\
&&\hskip 199.16928ptk\in[\Lambda^{1}_{x_{i}}]\\}\\\
&\cup&\\{\\{v_{i}^{1},l^{1}_{x_{i},j,1}\\},\\{l^{1}_{x_{i},j,k},r^{1}_{x_{i},j,k}\\},\\{r^{1}_{x_{i},j,k},l^{1}_{x_{i},j,k+1}\\}|i\in[n],j\in[\Lambda^{1}_{x_{i}}],\\\
&&\hskip 199.16928ptk\in[\Lambda^{0}_{x_{i}}]\\}\\\
&\cup&\\{\\{r^{0}_{x_{i},j,\Lambda^{1}_{x_{i}}},z_{x_{i},j}\\},\\{z_{x_{i},j},c_{k}\\}|i\in[n],j\in[\Lambda^{0}_{x_{i}}],\\\
&&\hskip 120.92421ptk\mbox{ is the }j\mbox{th smallest index s.t.
}\overline{x_{i}}\in C_{k}\\}\\\
&\cup&\\{\\{r^{1}_{x_{i},j,\Lambda^{0}_{x_{i}}},z_{x_{i},j}\\},\\{z_{x_{i},j},c_{k}\\}|i\in[n],j\in[\Lambda^{1}_{x_{i}}],\\\
&&\hskip 120.92421ptk\mbox{ is the }j\mbox{th smallest index s.t. }x_{i}\in
C_{k}\\}.\end{array}$

The cost functions for the edges are a constant $7$ for each
$\\{v_{i},v_{i}^{1}\\}$ edge, a constant $2$ for each $\\{v_{i},v_{i}^{0}\\}$
edge and a constant $0$ for each $\\{s,v_{i}\\}$ edge. All other edges have
cost $0$ for one, and $\infty$ (symbolizing a very large number) for any other
number of players. As mentioned before, the game is played by the $m$ clause
players. Each clause player $i$ has $s$ as source and $c_{i}$ as sink.
Clearly, every node $c_{i}$ is reached by precisely one player, representing
the satisfaction of property I). This is forced by every player having a
different clause as their sink. Property I) could have been satisfied with a
far simpler structure; however, this complex construction is necessary to
fulfill the other properties in the upcoming steps. Also, the reason behind
the choice of the cost functions will shortly become clear.

Figure 1 displays this construction for the simple satisfiable formula
$F=A\wedge(\overline{A}\vee B)$. For simplification, the names of the $l,r$
and $z$ nodes are shortened.

$s$$A$$A^{0}$$A^{1}$$B$$B^{0}$$B^{1}$$l$$r$$z$$l$$r$$z$$l$$r$$z$$\\{A\\}$$\\{\overline{A},B\\}$$0$$0$$7$$0|\infty$$0|\infty$$0|\infty$$0|\infty$$2$$0|\infty$$0|\infty$$0|\infty$$0|\infty$$7$$0|\infty$$0|\infty$$0|\infty$$0|\infty$$2$
Figure 1: The game on graph $G_{1}$ of formula $F=A\wedge(\overline{A}\vee B)$
played by two clause players. The red arrows indicate the social optimum of
the game. Variable $A$ is assigned both $0$ and $1$ in the social optimum.

From now on, we call a path from a node $x_{i}^{1}$ to $z_{x_{i}}^{1}$ a
1-Path, and from node $x_{i}^{0}$ to $z_{x_{i}}^{0}$ a 0-path. Similarly, we
say a player assigns $1$ ($0$) to variable $x_{i}$ if he chooses the
respective 1-Path (0-Path).

A path from a player from $s$ to an (unsatisfied) clause node $c_{j}$ chooses
the positive or negative occurrence of a variable in $C_{j}$ in order to
satisfy the clause. However, currently, it is possible that two clauses are
reached over the same variable, while once in its negative and once in its
positive form, i.e., property II) is not satisfied. This is the case in the
example of Fig. 1. The red lines indicate the social optimum. The social
optimum satisfies clause $\\{\overline{A},B\\}$ by assigning $0$ to $A$ even
though 1 was already assigned to $A$. We extend our game to fulfill property
II). In addition to the clause players, the game will now be played by the
occurrence players as well.

Let $G_{2}(V_{2},E_{2})$ be the undirected graph with

$\begin{array}[]{rcl}V_{2}&=&V_{1}\\\
&\cup&\\{o^{0}_{i,j}|i\in[n],j\in[\Lambda_{x_{i}}^{0}]\\}\\\
&\cup&\\{o^{1}_{i,j}|i\in[n],j\in[\Lambda_{x_{i}}^{1}]\\}\\\ E_{2}&=&E_{1}\\\
&\cup&\\{\\{o^{0}_{x_{i},j},z^{0}_{x_{i},j}\\}|i\in[n],j\in[\Lambda^{0}_{x_{i}}]\\}\\\
&\cup&\\{\\{o^{0}_{x_{i},j},l^{1}_{x_{i},1,j}\\}|i\in[n],j\in[\Lambda^{0}_{x_{i}}]\\}\\\
&\cup&\\{\\{o^{1}_{x_{i},j},z^{1}_{x_{i},j}\\}|i\in[n],j\in[\Lambda^{1}_{x_{i}}]\\}\\\
&\cup&\\{\\{o^{1}_{x_{i},j},l^{0}_{x_{i},1,j}\\}|i\in[n],j\in[\Lambda^{1}_{x_{i}}]\\}\\\
&\cup&\\{\\{r^{0}_{x_{i},j,k},l^{0}_{x_{i},j+1,k}\\}|i\in[n],j\in[\Lambda^{0}_{x_{i}}],k\in[\Lambda^{1}_{x_{i}}]\\}\\\
&\cup&\\{\\{r^{1}_{x_{i},j,k},l^{1}_{x_{i},j+1,k}\\}|i\in[n],j\in[\Lambda^{1}_{x_{i}}],k\in[\Lambda^{0}_{x_{i}}]\\}\\\
&\cup&\\{\\{r^{0}_{x_{i},\Lambda^{0}_{x_{i}},k},c_{j}\\}|i\in[n],k\in[\Lambda^{1}_{x_{i}}],j\mbox{
is the }k\mbox{th smallest index s.t. }x_{i}\in C_{j}\\}\\\
&\cup&\\{\\{r^{1}_{x_{i},\Lambda^{1}_{x_{i}},k},c_{j}\\}|i\in[n],k\in[\Lambda^{0}_{x_{i}}],j\mbox{
is the }k\mbox{th smallest index s.t. }\overline{x_{i}}\in
C_{j}\\}.\end{array}$

The costs of edges from $E_{1}$ remain unchanged. The new edges
$\\{r_{x_{i},j,k},c_{l}\\}$, $\\{o^{1}_{x_{i},j},z^{1}_{x_{i},j}\\}$, and
$\\{o^{0}_{x_{i},j},z^{0}_{x_{i},j}\\}$ have cost $6$ for one player and
$\infty$ otherwise. All other edges have cost $0$ for one player and $\infty$
for any other number of players. The cost of $6$ ensures that a clause player
cannot use the edge as a shortcut: Without using the new edge, his maximal
cost is $7$, and the minimum cost with the edge is at least $8$. A total of
$m+\Lambda$ players play the game on this graph. Each of the $\Lambda$ players
represents the occurrence of a variable $x_{i}$ in clause $C_{j}$. If the
occurrence is positive, the player has the source $o^{1}_{x_{i},j}$, and
$o^{0}_{x_{i},j}$ if the occurrence is negative. In both cases, the sink is
$c_{j}$.

The graph in Fig. 2 is the result of creating the construction for the formula
$F=A\wedge(\overline{A}\vee
B)\wedge(\overline{A}\vee\overline{B}\vee\overline{C})$, while focusing only
on the section concerning variable $A$. In an attempt to make the graph
clearer, some nodes appear multiple times in the graph; however they all
represent one single node. Nodes with this property are displayed as
rectangles. If they have the same name, they represent the same single node.

$s$$A$$A^{1}$$A^{0}$$o^{1}_{A,1}$$o^{1}_{A,1}$$o^{0}_{A,2}$$o^{0}_{A,2}$$o^{0}_{A,1}$$o^{0}_{A,1}$$l$$r$$l$$r$$z$$l$$r$$z$$l$$r$$z$$c_{1}$$\\{A\\}$$c_{1}$$c_{2}$$\\{\overline{A},B\\}$$c_{2}$$c_{3}$$\\{\overline{A},\overline{B},\overline{C}\\}$$c_{3}$
Figure 2: The segment of the graph $G_{2}$ of formula
$F=A\wedge(\overline{A}\vee
B)\wedge(\overline{A}\vee\overline{B}\vee\overline{C})$ concerning variable
$A$. Depicted are the strategies of one clause player (red arrows) and three
occurrence players (green arrows) in the social optimum.

The red path indicates a clause player satisfying $C_{1}$ by assigning 1 to
$A$. The green edges encompass three occurrence players, each trying to reach
another clause. The intention of this construction is to fix an assignment to
a variable. If not hindered, an occurrence player will try to reach a clause
by going straight to the $z$ node. However, if there is a player that wants to
satisfy the corresponding clause (e.g., by assigning the value 1 to it), the
edge $z-C$ cannot be used by the occurrence player as well. Instead, he takes
the detour via the zigzag path, blocking all 0-paths of this variable,
therefore satisfying property II).

A last problem with the construction is that the desired state reached when
all players follow their intended strategies is a pure Nash equilibrium. Since
the state is a Nash equilibrium already, no tolls are necessary to implement
the social optimum, hence violating property III). A last small change solves
this problem. From now on, the variable players join the game.

Let $G_{3}(V_{2},E_{3})$ be the undirected graph with

$\begin{array}[]{rcl}E_{3}&=&E_{2}\ \cup\
\\{\\{v_{i}^{0},v_{i}^{1}\\}|i\in[n]\\}.\end{array}$

The cost function of all edges from $E_{2}$ remain the same. The cost function
for a new edge $e=\\{v_{i}^{0},v_{i}^{1}\\}$ is $c_{e}(x)=2x$, where $x$ is
the number of players that use edge $e$. Now all $m+\Lambda+n$ players take
part in the game. A variable player $i$ has $v_{i}^{0}$ as source and
$v_{i}^{1}$ as sink.

Figure 3 illustrates the new component.

$A$$A^{1}$$A^{0}$$7$$2$$2x$$A$$A^{1}$$A^{0}$$7$$2$$2x$$A$$A^{1}$$A^{0}$$7$$2$$2x+2$
Figure 3: A demonstration of the effect of the variable player (blue arrow).
The clause player (red arrow) leaves the social optimum (left graph) for the
pure Nash equilibrium (center graph). Tolling an edge prevents this defection
(right graph).

The red edges correspond to a clause player, the blue edge to a variable
player. The state on the left is the social optimum. However, it is not a pure
Nash equilibrium, because the clause player can find a cheaper path, reducing
his cost by 1 but also increasing the social cost by 1, displayed in the
center state. The state on the right is a pure Nash equilibrium that coincides
with the social optimum of the original graph. It is the result of tolling
edge $\\{A^{0},A^{1}\\}$ with 2.

To optimally implement the social optimum, placing this toll is necessary if
and only if a clause player satisfies a clause by assigning 1 to a variable,
and at most once per variable. Since assigning 1 to a variable is more
expensive than assigning 0, the least number of variables will be assigned
value 1, forcing the placement of the toll station. Tolling such an edge
corresponds to assigning $1$ to the respective variable in the Boolean
formula. Therefore, the minimal satisfying assignment for the original formula
can be constructed from the placed toll stations efficiently. Additionally, if
the social optimum can be optimally implemented with at most $k$ tollbooths,
then there exists a satisfying assignment for the original formula with weight
at most $k$. Graph $G_{3}$ therefore finally satisfies all four properties.
From these reductions follows Theorem 3.1.

###### Theorem 3.1

Solving atomic MINTB is NP-hard and W[2]-hard with the number of required toll
booths as the parameter.

To know where to place the tollbooths and therefore the minimal satisfying
assignment of the original formula, it suffices to know the social optimum. A
direct consequence is that finding a social optimum must be hard.

###### Corollary 1

Finding a social optimum of a game $\Gamma$ is NP-hard. Additionally, finding
a social optimum that can be implemented in $\Gamma$ with at most $k$
tollbooths is W[2]-hard, with $k$ being the parameter.

##  4 Optimally Implementing a State in Polynomial Time

This section presents an algorithm that optimally implements a state $S$ in an
atomic network congestion game based on a series-parallel graph in polynomial
time. We base the procedure on a similar approach from Basu, Lianeas, and
Nikolova, who show the same result in basu2015new  for non-atomic games.
Starting at the simple base case of parallel-link networks, we inductively
decide on the number of tolled edges for larger components, based on the
optimality of the smaller ones. We do so by exploiting the recursive structure
of series-parallel graphs.

###### Definition 6

A graph $G$ with source $s$ and sink $t$ is called series-parallel, if

  1. i)

it consists of only a single edge.

  2. ii)

it is the result of combining two series-parallel graphs in series.

  3. iii)

it is the result of combining two series-parallel graphs in parallel.

A combination of graphs $G_{1}$ and $G_{2}$ in series means declaring the
source of $G_{1}$ as the new global source, and the sink of $G_{2}$ as the new
global sink. Additionally, the sink of $G_{1}$ and the source of $G_{2}$ are
identified as one node in the new graph.

Combining $G_{1}$ and $G_{2}$ in parallel means identifying both sources as
one node and setting it as the new global source, and respectively identifying
both sinks as the new global sink.

A series-parallel parse tree of a series-parallel graph is the representation
of the graph as a tree, where every leaf stands for a single edge, and every
inner node represents either a combination of its two children in series or
parallel. For simplicity, in this paper, the leaves will represent parallel-
link networks, i.e., networks consisting of two nodes connected by possibly
several edges.

Given an atomic network congestion game on a series-parallel network, let $T$
be the parse tree representation of that network, and $S$ a given state that
is to be implemented in that game. For each node of $T$, we will create a list
of tuples $(\eta,\lambda)$ with the following meaning. While ensuring that all
players follow their strategy in $S$, by tolling at most $\eta$ edges,
$\lambda$ is the highest cost we can force on a new player entering the
network represented by the regarded node. The values for $\eta$ range from the
minimum necessary to guarantee that all player follow their strategy from $S$
to the minimum necessary to toll all paths through the network. Additionally,
we will remember a single value $\lambda_{0}$, indicating the lowest cost a
new player can have, while ensuring that $S$ is implemented.

Algorithm 1 creates the list for a leaf of the tree, which is a parallel-link
network. For simplicity, we denote by $l_{e}=c_{e}(n_{e}(S))$, and by
$l_{e}^{+}=c_{e}(n_{e}(S)+1)$.

Data: Graph $G=(V,E)$ represented by leaf $v$ of the parse tree, state $S$

1 Set $list_{v}=[]$;

2 Set $l_{\max}=\max\\{l_{e}|\ e\in E\\}$;

3 Set $\eta_{\min}=|\\{e\ |\ e\in E\mbox{ and }l_{e}^{+}<l_{\max}\\}|$;

4 Set $\eta_{\max}=|E|$;

5 Set $\lambda_{0}=\max\\{\max\\{l_{e}\\},\min\\{l_{e^{\prime}}^{+}\\}\ |\
e,e^{\prime}\in E\\}$

6for  _$\eta=\eta_{\min}\mbox{ to }\eta_{\max}$_ do

7 Let $e_{1},...,e_{k}$ be all edges, and $l_{1}^{+}\leq...\leq l_{k}^{+}$

8

9 $\lambda=\infty$;

10 if  _$\eta\neq\eta_{\max}$_ then

11 $\lambda=l_{\eta+1}^{+}$;

12

13 Append $(\eta,\lambda)$ to $list_{v}$;

14

Algorithm 1 ParallelLink

Lines 2 and 3 of Algorithm 1 ensure, that at least the minimum number of edges
necessary to implement the given state $S$ in the parallel-link network is
tolled. Line 10 calculates the highest cost enforceable on a new player
entering the network. Since the $\eta$ cheapest edges are tolled, the highest
cost we could force on a newly entering player is the cost of the $\eta+1$
cheapest edge. Only when all edges are tolled, we can guarantee an arbitrarily
high cost, marked by the $\infty$ symbol. Thus, the tuple
$(\eta_{\max},\infty)$ forms the last element of the list.

Since the list is ordered with respect to the values of $\eta$, we will
address elements from the list by index, so, e.g., $\eta_{1}$ refers to
$\eta_{\min}$, and $\lambda_{i}$ is the cost enforceable by $\eta_{i}$ edges.
Whenever we refer to the last element of a list, we use $\max$ as the index.

Following an inductive argument, we now show how to correctly form these lists
for the inner nodes of the parse tree, assuming that the lists for the
children are already correctly formed. To differentiate between the two
children of the inner node $r$, we address one of them by $v$, and the other
one by $w$. Some values will be labeled with $r,v$ or $w$ accordingly. A tuple
for the list of $r$ will originate from two tuples, one for each child node.
We add two pointers, $idx_{v}$ and $idx_{w}$, to each new tuple, referencing
their origin.

### Series composition:

The minimum number of edges that need to be tolled in the parent node $r$ is
simply the sum of the minimum necessary number of edges from the children, so
$\eta_{1}^{r}=\eta_{1}^{v}+\eta_{1}^{w}$. Similarly, the maximum
$\eta_{\max^{r}}^{r}$ can be calculated by
$\eta_{\max^{r}}^{r}=\min\\{\eta_{1}^{v}+\eta_{\max^{w}}^{w},\eta_{\max^{v}}^{v}+\eta_{1}^{w}\\}$.
To complete the list, we have to add a tuple for every $\eta_{i}^{r}$ with
$1<i<\max^{r}$. The corresponding costs are
$\lambda_{i}^{r}=\max\\{\lambda_{a}^{v}+\lambda_{b}^{w}\ |\
\eta_{i}^{r}=\eta_{a}^{v}+\eta_{b}^{w}\\}$, for all $i\in[\max^{r}]$.
Accordingly, we set $\lambda_{0}^{r}=\lambda_{0}^{v}+\lambda_{0}^{w}$.

### Parallel composition:

In the parallel composition a player from one component may be able to reduce
his cost by joining the other component. Let $c_{\max}$ be the highest cost of
a player in both $v$ and $w$, if all players play according to the state $S$.
Without loss of generality, let it be a player from $v$ that has this cost
$c_{\max}$. To determine the minimum necessary number of tolled edges, it
suffices to check how many edges in $w$ have to be tolled to force a joining
player to have cost at least $c_{\max}$. That means,
$\eta_{1}^{r}=\eta_{1}^{v}+\min\\{\eta^{w}_{i}\ |\ \lambda^{w}_{i}\geq
c_{\max},i>0\\}$, and
$\eta_{\max^{r}}^{r}=\eta_{\max^{v}}^{v}+\eta_{\max^{w}}^{w}$. Again, we add a
tuple for every $\eta_{i}^{r}$ with $1<i<\max^{r}$. The corresponding costs
are $\lambda_{i}^{r}=\max\\{\min\\{\lambda_{a}^{v},\lambda_{b}^{w}\\}\ |\
\eta_{i}^{r}=\eta_{a}^{v}+\eta_{b}^{w}\\}$, for all $i\in[\max^{r}]$. We set
$\lambda_{0}^{r}=\max\\{c_{\max},\min\\{\lambda_{0}^{v},\lambda_{0}^{w}\\}\\}$.
Once the lists for all nodes are created, we can choose the tuple in the root
node with the minimum number of edges. We can retrace the creation of the
tuple to the leaf nodes of the tree, where we can decide which edges are to be
tolled with which value. Algorithm 2 is a recursive algorithm that tolls the
edges accordingly. For simplicity, we assume the lists of each node to be
globally accessible. The algorithm is initially called with $r$ being the root
node of the parse tree and $c_{in}=\lambda_{0}^{r}$, since optimally
implementing $S$ requires tolling $\eta_{1}^{r}$ edges.

Data: Parse Tree $T$, current node $r$, cost $c_{in}$

1 if  _$r$ is a leaf node_ then

2 Let $(V,E)$ be the parallel-link network represented by $r$;

3 for  _each edge $e\in E$ with $l_{e}^{+}<c_{in}$_ do

4 set toll $t_{e}=c_{in}-l_{e}^{+}$;

5

6 return

7

8Let $v=$ left child of $r$;

9 Let $w=$ right child of $r$;

10 Set $i=\arg\min_{i}\\{\lambda_{i}^{r}\geq c_{in}\ |\ i>0\\}$;

11 Let $j$ be the $idx_{v}$ of tuple $(\eta_{i}^{r},\lambda_{i}^{r})$;

12 Let $k$ be the $idx_{w}$ of tuple $(\eta_{i}^{r},\lambda_{i}^{r})$;

13

14if  _$r$ is a series composition_ then

15 Set $c_{out}^{v}$ and $c_{out}^{w}$, s.t.:

16 $\ -\ \ c_{out}^{v}+c_{out}^{w}=c_{in},$

17 $\ -\ \ c_{out}^{v}>\lambda_{j-1}^{v}$ if $j>1$, else
$c_{out}^{v}\geq\lambda_{0}^{v},$

18 $\ -\ \ c_{out}^{w}>\lambda_{k-1}^{w}$ if $k>1$, else
$c_{out}^{w}\geq\lambda_{0}^{w}$;

19

20else

21 Set $c_{out}^{v}=\max\\{c_{in},\lambda_{0}^{v}\\}$;

22 Set $c_{out}^{w}=\max\\{c_{in},\lambda_{0}^{w}\\}$;

23

24

25Call PlaceTolls$(T,v,c_{out}^{v})$;

26 Call PlaceTolls$(T,w,c_{out}^{w})$;

27

Algorithm 2 PlaceTolls

Lines $1$ to $5$ toll the edges in the parallel-link networks at the leaves of
the parse tree. Lines $11$ to $15$ consider the case when $r$ is a series
composition. Here the input cost is feasibly divided into two components. By
this division, it is both possible and necessary to implement $S$ with the
number of edges indicated by the $idx$ pointer. Lines $16$ to $18$ do the same
for the parallel composition. This way, it is always possible to toll the rest
of the network feasibly while only using $\eta_{1}^{r}$. It ensures, that the
state gets properly implemented in all components of the series-parallel
graph, and a new player joining the network has cost at least the initial
$c_{in}$.

### Runtime:

Let $m$ be the number of edges in the original network. The parse tree can be
created in $\mathcal{O}(m)$ time, and also has size $\mathcal{O}(m)$. Creating
the list at a leaf node is possible in $\mathcal{O}(m)$ time. For an inner
node, we have to check at most $\mathcal{O}(m^{2})$ combinations of elements
from the children’s lists. Therefore, creating the list for every node is
possible in $\mathcal{O}(m^{3})$ time. The computation time on each node in
Algorithm 2 is bounded by $\mathcal{O}(m)$. The algorithm visits every node of
the parse tree exactly once, leading to a runtime of $\mathcal{O}(m^{2})$. In
total, the runtime of the algorithm is $\mathcal{O}(m^{3})$.

###### Theorem 4.1

Optimally implementing a state $S$ in an atomic network congestion game based
on a series-parallel graph with $m$ edges is possible in runtime
$\mathcal{O}(m^{3})$.

##  5 Conclusion

This work analyses the complexity of the minimum tollbooth problem in atomic
network congestion games with unsplittable flows.

By a reduction from the weighted CNF SAT problem, we show both the NP-hardness
of the problem and, more importantly, the W[2]-hardness of a parameterized
version. The parameter in the latter case is the number of necessary
tollbooths to turn a social optimum of the untolled game into a pure Nash
equilibrium of the tolled one.

A restriction to networks that are series-parallel graphs yields a polynomial
time algorithm. The algorithm gives tolls, such that a given state is a pure
Nash equilibrium of the tolled game while using the minimum number of toll
booths. This algorithm is based on a similar method presented by Basu,
Lianeas, and Nikolova in basu2015new , who consider non-atomic games,
exploiting the recursive structure of series-parallel graphs.

## References

  * (1) Bai, L., Hearn, D.W., Lawphongpanich, S.: A heuristic method for the minimum toll booth problem.  Journal of Global Optimization 48(4), 533–548 (2010)
  * (2) Bai, L., Rubin, P.A.: Combinatorial benders cuts for the minimum tollbooth problem.  Operations research 57(6), 1510–1522 (2009)
  * (3) Bai, L., Stamps, M.T., Harwood, R.C., Kollmann, C.J.: An evolutionary method for the minimum toll booth problem: The methodology.  Journal of Management Information and Decision Sciences (2008)
  * (4) Basu, S., Lianeas, T., Nikolova, E.: New complexity results and algorithms for the minimum tollbooth problem.  In: International Conference on Web and Internet Economics, pp. 89–103. Springer (2015)
  * (5) Beckmann, M., McGuire, C.B., Winsten, C.B.: Studies in the economics of transportation.  Yale University Press (1956)
  * (6) Bilò, V., Vinci, C.: Dynamic taxes for polynomial congestion games.  In: Proceedings of the 2016 ACM Conference on Economics and Computation, pp. 839–856. ACM (2016)
  * (7) Bonifaci, V., Salek, M., Schäfer, G.: Efficiency of restricted tolls in non-atomic network routing games.  In: International Symposium on Algorithmic Game Theory, pp. 302–313. Springer (2011)
  * (8) Caragiannis, I., Kaklamanis, C., Kanellopoulos, P.: Taxes for linear atomic congestion games.  In: ESA, pp. 184–195. Springer (2006)
  * (9) Chakrabarty, D., Mehta, A., Nagarajan, V.: Fairness and optimality in congestion games.  In: Proceedings of the 6th ACM Conference on Electronic Commerce, pp. 52–57. ACM (2005)
  * (10) Christodoulou, G., Koutsoupias, E.: The price of anarchy of finite congestion games.  In: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pp. 67–73. ACM (2005)
  * (11) Cole, R., Dodis, Y., Roughgarden, T.: Pricing network edges for heterogeneous selfish users.  In: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pp. 521–530. ACM (2003)
  * (12) Cole, R., Dodis, Y., Roughgarden, T.: How much can taxes help selfish routing?  Journal of Computer and System Sciences 72(3), 444–467 (2006)
  * (13) Colini-Baldeschi, R., Klimm, M., Scarsini, M.: Demand-independent optimal tolls (2018)
  * (14) Cominetti, R., Correa, J.R., Stier-Moses, N.E.: The impact of oligopolistic competition in networks.  Operations Research 57(6), 1421–1437 (2009)
  * (15) Cygan, M., Fomin, F.V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized algorithms, vol. 3.  Springer (2015)
  * (16) Downey, R.G., Fellows, M.R.: Parameterized complexity.  Springer (1999)
  * (17) Fleischer, L., Jain, K., Mahdian, M.: Tolls for heterogeneous selfish users in multicommodity networks and generalized congestion games.  In: Proceedings of the fourty-fifth annual IEEE symposium on Foundations of Computer Science, pp. 277–285. IEEE (2004)
  * (18) Fotakis, D., Karakostas, G., Kolliopoulos, S.G.: On the existence of optimal taxes for network congestion games with heterogeneous users.  In: International Symposium on Algorithmic Game Theory, pp. 162–173. Springer (2010)
  * (19) Fotakis, D., Spirakis, P.G.: Cost-balancing tolls for atomic network congestion games.  Internet Mathematics 5(4), 343–363 (2008)
  * (20) Harks, T., Kleinert, I., Klimm, M., Möhring, R.H.: Computing network tolls with support constraints.  Networks 65(3), 262–285 (2015)
  * (21) Harwood, R.C., Kollmann, C.J., Stamps, M.T.: A genetic algorithm for the minimum tollbooth problem (2005)
  * (22) Hearn, D.W., Ramana, M.V.: Solving congestion toll pricing models.  In: Equilibrium and advanced transportation modelling, pp. 109–124. Springer (1998)
  * (23) Meyers, C.A., Schulz, A.S.: The complexity of congestion games.  Massachusetts Institute of Technology, Cambridge pp. 1–16 (2008)
  * (24) Orda, A., Rom, R., Shimkin, N.: Competitive routing in multiuser communication networks.  IEEE/ACM Transactions on Networking (ToN) 1(5), 510–521 (1993)
  * (25) Pigou, A.C.: The economics of welfare.  McMillan&Co., London (1920)
  * (26) Rosenthal, R.W.: A class of games possessing pure-strategy nash equilibria.  International Journal of Game Theory 2(1), 65–67 (1973)
  * (27) Roughgarden, T., Tardos, É.: How bad is selfish routing?  Journal of the ACM (JACM) 49(2), 236–259 (2002)
  * (28) Stefanello, F., Buriol, L.S., Hirsch, M.J., Pardalos, P.M., Querido, T., Resende, M.G., Ritt, M.: On the minimization of traffic congestion in road networks with tolls.  Annals of Operations Research 249(1-2), 119–139 (2015)
  * (29) Swamy, C.: The effectiveness of stackelberg strategies and tolls for network congestion games.  In: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 1133–1142. Society for Industrial and Applied Mathematics (2007)