# Reference-Free Image Quality Metric for Degradation and Reconstruction
Artifacts

Han Cui, Alfredo De Goyeneche, Efrat Shimron, Boyuan Ma, Michael Lustig
University of California, Berkeley
{louiscuihan2018, asdegoyeneche, efrat.s, boyuan.ma<EMAIL_ADDRESS>
###### Abstract

Image Quality Assessment (IQA) is essential in various Computer Vision tasks
such as image deblurring and super-resolution. However, most IQA methods
require reference images, which are not always available. While there are some
reference-free IQA metrics, they have limitations in simulating human
perception and discerning subtle image quality variations. We hypothesize that
the JPEG quality factor is representatives of image quality measurement, and a
well-trained neural network can learn to accurately evaluate image quality
without requiring a clean reference, as it can recognize image degradation
artifacts based on prior knowledge. Thus, we developed a reference-free
quality evaluation network, dubbed ”Quality Factor (QF) Predictor”, which does
not require any reference. Our QF Predictor is a lightweight, fully
convolutional network comprising seven layers. The model is trained in a self-
supervised manner: it receives JPEG compressed image patch with a random QF as
input, is trained to accurately predict the corresponding QF. We demonstrate
the versatility of the model by applying it to various tasks. First, our QF
Predictor can generalize to measure the severity of various image artifacts,
such as Gaussian Blur and Gaussian noise. Second, we show that the QF
Predictor can be trained to predict the undersampling rate of images
reconstructed from Magnetic Resonance Imaging (MRI) data.

##  1 Introduction

In recent decades, Computer Vision research has shown remarkable progress. A
large body of work has demonstrated the powerful capabilities of Deep Learning
(DL), especially Convolutional Neural Networks (CNNs), for various computer
vision tasks. Studies demonstrated that neural networks could recognize both
local and global features in images and understand the semantic relationship
between objects and the background [1], thus exhibiting strong performance in
challenging Computer Vision tasks such as object detection[2] and instance
segmentation[3].

The development of DL models requires Image Quality Assessment (IQA) metrics,
as these metrics play a crucial role in the training process of the models.
Two examples for such metrics are the Mean Square Error (MSE) and Structural
Similarity Index (SSIM)[4]. These pixel-wise metrics are widely used in many
applications[5, 6, 7]. However, their use is limited in two aspects. First,
computing such metrics requires a ground-truth image for comparison, but in
many cases, such ground-truth data are not available. For example, in Magnetic
Resonance Imaging (MRI), such ground truth images are difficult to obtain due
to long scan time. Secondly, such metrics sometimes do not correlate well with
human perception. For example, the Peak-Signal-to-Noise-Ration (PSNR) metric
is typically used to measure image quality, where a higher PSNR score
indicates better quality. However, in the example shown in Figure 1, the PSNR
metric assigns a higher score to the left image compared with the middle
image. In contrast, human perception can immediately discern that the middle
image is sharper and of better quality.

Figure 1: Examples that illustrate the discrepancy between PSNR values and
human perception, adopted from[8]. Given the original image for reference, the
left image has a higher metric score but a lower perceptual quality. On the
contrary, the middle image has a lower metric score but a higher perceptual
quality.

To address these limitations, we explore the development of a reference-free
DL-based IQA model. The major contributions of this work are:

  1. 1.

We develop a Deep Learning method for reference-free IQA, employing a self-
supervised training approach with JPEG compression QF to avoid the need for a
massive amount of manual data annotation.

  2. 2.

We design a network that learns to identify subtle JPEG compression artifacts,
enabling it to differentiate nuances between fine-quality images and high-
quality images.

  3. 3.

Our lightweight, CNN-based model can generalize to estimate the severity of
other (non-JPEG) image degradation artifacts, including blurring, additive
Gaussian noises, and imperfections in Magnetic Resonance (MR) images
reconstructed from under-sampled data.

Figure 2: Showcase of JPEG Compression artifacts within different QFs.[9]

##  2 Related Work

Deep IQA. Given the versatility of DL in various Computer Vision domains,
researchers have already begun incorporating Deep Learning methodologies for
automated IQA. These methods demonstrate excellent performance in quantifying
the similarity between images[10, 11], and modeling subjective human
evaluations of image quality[12, 13], particularly in the context of pairwise
comparisons[14]. Most of these contributions focus on perceptual image
quality. However, they can produce misleading results for slightly corrupted
images. Also, many of these studies are based on very large neural networks,
which perform optimally only when a substantial amount of manually annotated
data is available.

Self-Supervised Learning. To reduce the need for large training datasets,
researchers investigate methods for generating labels from the data itself, an
approach known as Self-Supervised Learning. Many studies demonstrate that
carefully crafted self-supervision training enables network to acquire high-
level knowledge and features without human annotation. Examples include
training networks to solve jigsaw puzzles[15], to colorize grayscale
images[16], and to predict the angle of image rotations[17]. Specifically,
networks trained for the latter task show superior performance in downstream
classification tasks compared to state-of-the-art algorithms, while also
requiring significantly less training data.

JPEG-Compression. JPEG compression attracted substantial research interest, as
JPEG is one of the most widely used compression techniques. JPEG compression
builds upon the Discrete Cosine Transformation (DCT) and uses the variable
quality factor based on Quantization to control the compression ratio.
Although effective for compression, JPEG also introduces some artifacts. As
shown in Figure 2, it generally produces a complex combination of blurring,
blocking artifacts, and ringing effects[18]. Moreover, numerous studies,
including both digital image processing techniques[19, 20] and DL-based
approaches[21, 22], have focused on the restoration of low-quality JPEG
compressed images and the reduction of severe JPEG compression artifacts.

Medical Image Restoration. Medical images generally contain many detailed
textures and require high image quality for diagnosis. Consequently,
significant research efforts were dedicated to image restoration, focusing on
the tasks of medical image denoising[23, 24] and reconstruction[25, 26].
Specifically, medical image reconstruction is the process of generating a
high-quality and accurate image from a series of acquired measurements.

A widely used architecture used for medical image restoration is the
U-Net[27], a convolutional neural network originally designed for image
segmentation, which has been adapted for various biomedical restoration tasks
due to its ability to capture both local and global features in the input
images. A different, more advanced architecture is physics-guided unrolled
neural networks. Such networks unroll an optimization algorithm and iterate
between data consistency blocks and denoising blocks. One notable example of
an unrolled reconstruction network is Model-based Deep Learning (MoDL)[28],
which was developed for MRI reconstruction. MoDL has shown a great capability
to reconstruct high-quality images from under-sampled k-space data.

##  3 Approach

###  3.1 Methodology Overview

The goal of this work is to develop a Deep Learning method capable of
evaluating IQA metrics in a reference-free manner. Our model is trained using
a self-supervised approach as follows: we apply the JPEG compression to each
input image with a random target Quality Factor (QF), which produces the
compressed image. The network takes in the compressed input image, and outputs
the predicted QF, which should be as close as possible to the target QF. This
forms a simple optimization objective:

$\displaystyle\min_{\theta}$
$\displaystyle\frac{1}{N}\sum_{i=1}^{N}{loss(y_{i},y^{\prime}_{i})}$ (1) s.t.
$\displaystyle X^{\prime}=J(X,y)$ $\displaystyle
y^{\prime}_{i}=F(X^{\prime}|\theta)$

In this formulation, $J(.)$ denotes the JPEG Compression process, $X$ is the
original image, $y$ is the target QF, $X^{\prime}$ is the compressed input
image, $F(X^{\prime}|\theta)$ represents the network output given $X^{\prime}$
as input, $\theta$ are the network parameters, and $y^{\prime}$ is the
predicted QF. Our general formulation enables using different loss functions,
such as the Cross-Entropy Loss for a classification problem or the Mean Square
Error (MSE) for a regression problem.

In Figure 3, we show a simplified version of our training pipeline. The input
image can be either an RGB image or a gray-scale MR image. In order to train
the network with one specific image shape but be able to run inference tasks
with different image sizes, we built the network in a fully convolutional way.
In our setup, the desired output is a map of QFs, with a size smaller than the
input image. Each value in the QF map represents the QF prediction for a
specific region in the original image. Specifically, each value of the output
QF map has an approximate field of view (FOV) of 11 pixels in the input image.

Figure 3: Training pipeline for QF Predictor

###  3.2 Network Architecture and JPEG QF Values

In this project, we aim to develop a compact model. Therefore, we built a
simple DNN with a small number of parameters, which has only seven convolution
layers, as shown in Figure 4. In the first several convolution layers, we
incorporated two max-pooling layers to reduce the size of tensors and the
computational complexity. In between every two layers, we included batch
normalization and ReLU activation to introduce non-linearity. Among these
seven layers, the last two layers utilize 1x1 convolutions to reduce the
number of channels.

The range of possible JPEG compression QF values is [0, 100], where 0
indicates the maximum compression level, and 100 indicates the minimum level.
To make the optimization problem described in equation (1) compatible with
general Machine Learning loss functions, which usually receive values in the
range of 0 to 1, we re-scaled the JPEG QF range to [0.0, 1.0]. To avoid
negative QF output, we introduced an extra Sigmoid activation level after the
final convolution layer; this enforces the [0.0, 1.0] range. The network can
automatically scale with the Sigmoid function, which does not harm the overall
performance.

Figure 4: QF Predictor Architecture

###  3.3 Datasets

As mentioned earlier, we want the network to capture the perceived image
quality from a human observer’s perspective and find indistinct imperfections
in high-quality images. For this purpose, we need high-quality datasets for
training. Our interest lies in estimating the artifact level for both general
RGB images and MR images reconstructed from under-sampled data. Thus, we
trained two networks: an RGB QF Predictor and a grayscale QF Predictor.

The RGB QF Predictor was trained on the Flickr1024 [29], a high-resolution
dataset originally used for large-scale Stereo Super Resolution task. The
grayscale QF Predictor was trained on FastMRI[30], a large database of raw MRI
data. We utilized the knee dataset of FastMRI, as it offers high-quality
ground truth images. Additionally, we also run generalization experiments on
ImageNet[31], a large-scale and widely-used dataset designed for training and
benchmarking various machine learning and computer vision algorithms, and
LIVE[32], a comprehensive IQA dataset consisting of a variety of distortion
types, including JPEG and JPEG2000 compression, Gaussian blur, and additive
white Gaussian noise.

Our work requires the network to identify small details in the images.
Therefore, rather than feeding the whole image into the network, we randomly
cropped small patches for training to ensure our network is sensitive to
artifacts present at the patch size level. This can also be regarded as a data
augmentation method to provide more randomness in the training procedure.

Figure 5: Examples of activation maps extracted from the last convolution
layer. These results indicate that the network over-emphasizes the grid-like
patterns in the corrupted images, which leads to biased results toward low
QFs.  Figure 6: Weighted distribution for high-quality focusing training

##  4 Exploration of Training Approaches

In this section, we describe the various approaches and engineering choices
that were examined, along with an analysis of the rationale behind these
decisions. In all the experiments described here, our RGB QF Predictor was
tested on the validation data from Flickr1024.

###  4.1 Training with a weighted QF distribution

As noted earlier, we apply JPEG compression to image patches compressed with a
randomly selected QF, and then train the network to predict the ground truth
QF. In our first set of experiments, the random QFs were drawn from the range
[0, 100] using a random-uniform distribution. However, we observed that this
design resulted in a model that exhibited proficient performance for low QF
values, in the range of [0, 40] and suboptimal performance for QFs in the
range of [80, 100]. To examine the reasons, we plot the model’s activation
maps, which were extracted from the last convolution layer (Figure 5). As
indicated in the literature [18], JPEG compression generally produces a
complex combination of different artifacts. However, we observed that the
blocking artifacts become dominant for low QFs (Figure 5). Because these
artifacts are trivial for the network to identify, that leads to _biased
results_ , where the QF is predicted accurately mostly for the low QFs regime.
To solve this problem, we replaced the uniform distribution with a non-uniform
one, shown in Figure 6. This distribution was generated by assigning
probability based on the logarithmic value of QFs. It therefore assigns higher
weights to QFs in the range of [80, 100]; as a result, during training, QF
values were mostly drawn from this range. This forces the network to focus on
learning rare artifacts that appear mostly in slightly-compressed images,
while still being exposed to blocking artifacts (that appear for highly
compressed images) as early-stage guidance. As a result, we achieve our goal
of differentiating nuances between high-quality images and lossless images.

###  4.2 Classification vs. Regression

(a) Curves for Cross-Entropy

(b) Curves for MSE

Figure 7: Training and Validation curves for two loss choices.

(a) Confusion Matrix for Cross Entropy validation data

(b) Pair Value Analysis for MSE validation data

Figure 8: Extra Visualizations for two loss choices.

As mentioned earlier, the choice of the loss function in Equation (1) might be
an important engineering choice in the project. As a first step, we formulated
the problem as a classification task with the Cross-Entropy loss as the
following: we only select QFs from [0, 20, 40, 60, 80], with more training
examples focusing on the case where QF = 60 or 80. We can treat each QF as a
class category and treat the optimization problem as a classification problem
with five categories, where class 0 corresponds to QF 0, class 1 corresponds
to QF 20, and so on. This setup forms a simple experiment that can help us
understand the network’s capacity and tweak hyperparameters, such as the size
of the image patch and the learning rate. However, treating the problem as a
classification task poses a potential issue: the network is not required to
learn sophisticated knowledge to distinguish between examples with QF = 60 and
those with QF = 80, which hinders its sensitivity to the subtle differences
between fine-quality and high-quality images.

(a) Grayscale examples

(b) RGB examples

Figure 9: Validation Examples with ground truth and predicted QFs.

Therefore, we decided to reformulate the problem. Instead of treating the QF
prediction as a classification task, we decided to address it as a regression
task. The regression task covers a broader range of QFs, introducing increased
randomness into the training process and resulting in a more robust model. In
other words, instead of predicting QF values into groups, we decided to train
the network to predict the QF value on a continuous axis. As mentioned above,
we rescaled QF values from [0, 100] to [0.0, 1.0]. In this experiment, we used
the same architecture as before (Figure 4), and trained the network utilizing
the Mean Square Error (MSE) loss, with the same training data from Flickr1024.

The training and validation curves for both the classification experiment
(Cross-Entropy loss) and regression experiment (MSE loss) are shown in Figure
7. Even though the validation curves oscillate more severely than the training
curves in both scenarios, the overall training converges approximately after
500 epochs. Note that for the regression problem with the MSE loss, the
accuracy in the graph is calculated as follows: the case is considered correct
only if $|y_{i}-y_{i}^{\prime}|<=0.02$ where $y_{i}$ is the ground truth QF
and $y_{i}$ is the predicted QF. Intuitively the regression problem is much
more difficult than the classification problem, which explains the lower
accuracy.

For more straightforward visualizations, we include a confusion matrix for
Cross-Entropy data in 8(a), and a pair value analysis graph for MSE data in
8(b). In both examples, the network exhibits uncertainty about data with
Quality Factors 40 to 60 due to the lack of training. However, the prediction
for high-quality data, i.e. data that has QF of 80-100, exhibits a low error
rate and low variance because of more training examples, which indicates the
network performs accurately with a high confidence level on these high-quality
data. In Figure 9, we include some examples from the validation data evaluated
by these two pre-trained models. These results show that the network has a
stable performance and predicts close QFs to the ground truth for individual
examples in both datasets.

##  5 Experiments

For the following inference experiments, we employ two pre-trained networks:
RGB QF Predictor, trained using the MSE loss and the Flickr1024 dataset, and
the grayscale QF Predictor, trained using the same loss and the FashMRI
dataset.

###  5.1 Generalization Test to other Artifacts

Figure 10: Inference pipeline for RGB QF Predictor

(a) Blurring artifacts on LIVE [32] dataset

(b) ”Salt & Pepper” artifacts on Flickr1024 [29] dataset

Figure 11: Examples for blur and noise artifacts used in the generalization
test.

(a) Correlation curves for blurring artifacts

(b) Correlation curves for noise artifacts

Figure 12: Correlation curves between the severity of the corruption artifacts
and the QF prediction from the pre-trained network.

As described in section 2, JPEG compression introduces various artifacts such
as blurring, blocking, and ringing artifacts. Therefore, we anticipate that
our QF Predictor, trained on JPEG-compressed data, can generalize to other
types of corruption. To test this hypothesis, we apply the pre-trained RGB QF
Predictor to images corrupted by Gaussian Blur and ”Salt & Pepper” noise. The
input data preparation process is as follows: we extract a patch from the
image, introduce different levels of artifacts to the patch, and feed the
corrupted patch to the QF Predictor as illustrated in Figure 10. For each
image, we extracted patches from certain randomly-selected locations so that
the QF Predictor consistently observes the same region. This approach
guarantees a fair comparison, with the only changing factor being the degrees
of artifacts rather than the image content. In Figure 11, we present some
examples of inference tasks with different levels of artifacts. We expect that
the predicted QF will decrease with the corruption.

In Figure 12, we show the correlation curves depicting the relationship
between the change in corruption level and the corresponding QF predictions.
In most cases, the QF decreases as the level of corruption increases. In each
graph, the first half of the curve (where the artifacts are not apparent)
shows a steeper decrease with lower variance compared to the latter half. This
aligns with our assumption and demonstrates that our network is highly
susceptible to subtle artifacts in nearly perfect images, as intended.

There is one exception observed in the LIVE dataset in 12(b), where the
addition of noises seems to slightly boost the QF prediction initially. One
possible explanation for this is that original data in LIVE naturally have a
low image quality. This phenomenon introduces another exciting task: use our
model to measure the quality of various current image datasets.

Table (1) summarizes the application of our QF Predictor to every image in the
LIVE, Flickr1024, and ImageNet datasets to estimate the average image quality
across each dataset. Our results indicate that the average predicted QF for
the LIVE data is significantly lower than the other two, suggesting that it is
a low-quality image dataset. This finding holds significance considering that
images in LIVE are already slightly corrupted by various distortion types,
including JPEG2000[32]. The validation of our results and the observed
differences between datasets reinforce the versatility and reliability of our
QF Predictor.

LIVE | Flickr1024 | ImageNet
---|---|---
$0.7800\pm 0.054$ | $0.9518\pm 0.043$ | $0.9705\pm 0.017$
Table 1: Predicted average QF for the whole dataset, indicating that images in
LIVE generally have a lower quality than Flickr1024 and ImageNet. Figure 13:
Inference pipeline for grayscale QF Predictor Figure 14: Correlation curves
between the under-sampling rate and the QF prediction from the pre-trained
network.

(a) R=3 central patch map

(b) R=5 central patch map

(c) R=8 central patch map

(d) R=10 central patch map

(e) R=3 whole image map

(f) R=5 whole image map

(g) R=8 whole image map

(h) R=10 whole image map

Figure 15: First row: QF predictions mapped to the central patches; Second
row: QF predictions mapped to the whole images.

###  5.2 Generalization Test to Under-sampling Rate

Having pre-trained the grayscale QF Predictor on the FastMRI knee data
(Authors13), our natural curiosity led us to explore whether the network can
contribute to improving MRI reconstruction. To achieve this, we first
investigate whether the model can predict the under-sampling rate $R$ of the
MRI reconstruction. We employ MoDL [28] as the MRI reconstruction network,
which generally produces outputs with a low Normalized Root Mean Square Error
(NRMSE) and high quality based on SSIM and PSNR metrics. Identifying artifacts
in reconstructed MR images can be challenging for individuals without
specialized training, except in cases of high under-sampling rates such as
$R\geq 10$. However, we anticipate that our QF Predictors, trained with JPEG
compression, can generalize to discern subtle imperfections in high-quality
MoDL output data.

As shown in Figure 13, we followed a similar pipeline to the RGB inference
task. We fed the under-sampled data generated by the Fourier domain mask with
varying under-sampling rates into the MoDL network and ran the pre-trained QF
Predictor on the high-quality reconstructed data. Note that the output of the
MoDL is a complex-value image data, and we need to calculate the corresponding
magnitude value to obtain the appropriate image for the QF Predictor. Similar
to the RGB generalization test, we expected the QF predictions to decrease as
the under-sampling rate increases. However, as shown in Figure 14, although
the results were consistent with low variance for the central patch, the
performance for whole images exhibited instability with significant
uncertainty.

In Figure 15, we examined the QF Predictor outputs mapped to both the central
patch and the whole image. The first row demonstrates that the network can
capture subtle corruptions caused by increased under-sampling rates,
particularly around the edges of the joint area, in central patches rich with
detailed textures. However, in the second row, where we present results for
the whole image, the network predominantly focuses on the knee areas and
assigns low QF values to near-black background regions. These low values in
the 20 to 50 range bias the statistics in the correlation curves displayed in
Figure 14, which indicates the limitations of our estimation on the whole
image level for MRI reconstruction.

Figure 16: Pipeline for using QF Predictor as a loss function integrated into
the image reconstruction networks. Figure 17: Showcase of input and output
pairs, from training with both L1 loss and QF loss term. First row: examples
from the grayscale experiments; Second row: examples from the RGB experiments.

###  5.3 Application as a Perceptual Loss Function

In recent Computer Vision research, researchers have often incorporated
perceptual loss terms, such as SSIM, into their models to generate more
visually pleasing results. As shown previously, our QF Predictor can capture
subtle differences between perfect-quality and high-quality images that are
sometimes challenging for humans to perceive. This observation has inspired us
to utilize the Quality Factor network as a deep perceptual loss function to
train an image reconstruction network in cases where ground truth data is
unavailable. For our artifact removal task, we used the SR-CNN[33] and AR-
CNN[34] as the backbone networks. As this task can be applied to both RGB and
grayscale images, we employed pre-trained grayscale and RGB QF predictors to
estimate the image quality of the reconstruction output for different types of
images. As shown in Figure 16, we incorporated both a data consistency loss
term between the input and the output of the image reconstruction network and
a perceptual term based on quality factor estimations.

Figure 17 shows several examples from both RGB and grayscale experiments. The
graph illustrates that the QF loss in the grayscale artifacts removal task
resulted in some minor improvements, such as sharpening edges and reducing
general noise levels, but it did not lead to noticeable visual quality
enhancement. However, in the corresponding artifacts removal task on RGB
images, the QF loss term introduced some additional inconsistencies, such as
the changes in color tones and the emergence of generative artifacts, such as
the purple dots in the first RGB pair and yellow dots in the second RGB pair.
This suggests that the QF Predictor somehow overrides the image
reconstructor’s prior knowledge and focuses solely on image quality without
considering data consistency. Achieving a balance point between the data
consistency loss term and the QF term becomes crucial, requiring meticulous
and rigorous weightings to prevent erosion of reconstruction quality.

##  6 Conclusions

This work presents a self-supervision method based on JPEG compression for a
reference-free deep quality metric prediction model. Our proposed model does
not rely on extensive training datasets, yet it is capable of capturing
perceived image quality similar to humans and distinguishing small nuances
between near-perfect and lossless images. We have demonstrated that a network
with only seven convolution layers can be trained and achieve convergence
within a short training period, providing accurate predictions with low
variance on RGB and grayscale validation data. Furthermore, we have showcased
the model’s ability to generalize to other tasks, such as predicting
corruption levels induced by Gaussian blur and ”Salt & Pepper” noise, as well
as estimating the under-sampling rate of high-quality MRI reconstruction
network outputs for detailed regions.

However, when applying the model as a loss term to visually improve the output
of image artifact removal networks, we observed sub-optimal performance. This
is attributed to the tradeoff between an increase in image quality, and the
potential risk of compromising data consistency and introducing generative
artifacts. Therefore, careful consideration and rigorous weighting between the
data consistency loss term and the quality factor term are necessary to strike
a balance that ensures both image quality improvement and preservation of
reconstruction accuracy.

##  7 Acknowledgements

This project is under the guidance of Alfredo De Goyeneche, Efrat Shimron, and
Michael (Miki) Lustig. We also thank Ke Wang and Stella X. Yu for their
insightful advice.

## References

  * [1] Shervin Minaee, Yuri Boykov, Fatih Porikli, Antonio Plaza, Nasser Kehtarnavaz, and Demetri Terzopoulos.  Image segmentation using deep learning: A survey.  CoRR, abs/2001.05566, 2020.
  * [2] Zhong-Qiu Zhao, Peng Zheng, Shou tao Xu, and Xindong Wu.  Object detection with deep learning: A review.  2019\.
  * [3] Abdul Mueed Hafiz and Ghulam Mohiuddin Bhat.  A survey on instance segmentation: State of the art.  CoRR, abs/2007.00047, 2020.
  * [4] Zhou Wang, A.C. Bovik, H.R. Sheikh, and E.P. Simoncelli.  Image quality assessment: from error visibility to structural similarity.  IEEE Transactions on Image Processing, 13(4):600–612, 2004.
  * [5] Sarah A. Barman, Roshan A. Welikala, Alicja R. Rudnicka, and Christopher G. Owen.  Chapter 8 - image quality assessment.  pages 135–155, 2019.
  * [6] Kalpana Seshadrinathan, Thrasyvoulos N. Pappas, Robert J. Safranek, Junqing Chen, Zhou Wang, Hamid R. Sheikh, and Alan C. Bovik.  Chapter 21 - image quality assessment.  pages 553–595, 2009.
  * [7] Zhou Wang, Alan C. Bovik, and Eero P. Simoncelli.  8.3 - structural approaches to image quality assessment.  pages 961–974, 2005.
  * [8] Aliaksei Mikhailiuk.  Deep image quality assessment.  2021\.  Medium, Towards Data Science.
  * [9] Jpeg image deblocking using deep learning.  2019\.  MathWorks, MATLAB & Simulink Example.
  * [10] Fei Gao, Yi Wang, Panpeng Li, Min Tan, Jun Yu, and Yani Zhu.  Deepsim: Deep similarity for image quality assessment.  2017\.  Neurocomputing, Volume 257, Pages 104-114.
  * [11] Richard Zhang, Phillip Isola, Alexei A. Efros, Eli Shechtman, and Oliver Wang.  The unreasonable effectiveness of deep features as a perceptual metric.  2018\.  IEEE/CVF Conference on Computer Vision and Pattern Recognition(CVPR).
  * [12] Jongyoo Kim and Sanghoon Lee.  Deep learning of human visual sensitivity in image quality assessment framework.  2017\.  IEEE Conference on Computer Vision and Pattern Recognition (CVPR).
  * [13] Jinjin Gu, Haoming Cai, Haoyu Chen, Xiaoxing Ye, Jimmy Ren, and Chao Dong.  Pipal: a large-scale image quality assessment dataset for perceptual image restoration.  2020\.  European Conference on Computer Vision (ECCV).
  * [14] Ekta Prashnani, Hong Cai, Yasamin Mostofi, and Pradeep Sen.  Pieapp: Perceptual image-error assessment through pairwise preference.  2018\.  IEEE Conference on Computer Vision and Pattern Recognition (CVPR).
  * [15] Mehdi Noroozi and Paolo Favaro.  Unsupervised learning of visual representations by solving jigsaw puzzles.  2017\.
  * [16] Richard Zhang, Phillip Isola, and Alexei A. Efros.  Colorful image colorization.  2016\.
  * [17] Spyros Gidaris, Praveer Singh, and Nikos Komodakis.  Unsupervised representation learning by predicting image rotations.  2018\.  International Conference on Learning Representations.
  * [18] Dong Chao, Deng Yubin, Loy Chen Change, and Tang Xiaoou.  Compression artifacts reduction by a deep convolutional network.  2015\.  IEEE International Conference on Computer Vision (ICCV).
  * [19] A. M. Raid, W. M. Khedr, M. A. El-dosuky, and Wesam Ahmed.  Jpeg image compression using discrete cosine transform - a survey.  2014\.
  * [20] Sukhpal Singh.  Reduction of blocking artifacts in JPEG compressed image.  CoRR, abs/1210.1192, 2012.
  * [21] Xiao-Jiao Mao, Chunhua Shen, and Yu-Bin Yang.  Image restoration using convolutional auto-encoders with symmetric skip connections.  2016\.
  * [22] Jingyun Liang, Jiezhang Cao, Guolei Sun, Kai Zhang, Luc Van Gool, and Radu Timofte.  Swinir: Image restoration using swin transformer.  2021\.
  * [23] Lovedeep Gondara.  Medical image denoising using convolutional denoising autoencoders.  pages 241–246, 2016.
  * [24] P.V.V. Kishore, K.L. Mallika, M.V.D. Prasad, and K.L. Narayana.  Denoising ultrasound medical images with selective fusion in wavelet domain.  Procedia Computer Science, 58:129–139, 2015.  Second International Symposium on Computer Vision and the Internet (VisionNet’15).
  * [25] Yan Yang, Jian Sun, Huibin Li, and Zongben Xu.  Admm-net: A deep learning approach for compressive sensing mri.  2017\.
  * [26] Kalyan Ram Ayyalasomayajula, Filip Malmberg, and Anders Brun.  PDNet: Semantic segmentation integrated with a primal-dual network for document binarization.  Pattern Recognition Letters, 121:52–60, apr 2019.
  * [27] Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-net: Convolutional networks for biomedical image segmentation.  CoRR, abs/1505.04597, 2015.
  * [28] M. Jacob H. K. Aggarwal, M. P. Mani.  Modl: Model-based deep learning architecture for inverse problems.  2019\.  IEEE Transactions on Medical Imaging, vol. 38, no. 2, pp. 394-405.
  * [29] Yingqian Wang, Longguang Wang, Jungang Yang, Wei An, and Yulan Guo.  Flickr1024: A large-scale dataset for stereo image super-resolution.  2019\.  International Conference on Computer Vision Workshops.
  * [30] Jure Zbontar, Florian Knoll, Anuroop Sriram, Matthew J. Muckley, Mary Bruno, Aaron Defazio, Marc Parente, Krzysztof J. Geras, Joe Katsnelson, Hersh Chandarana, Zizhao Zhang, Michal Drozdzal, Adriana Romero, Michael G. Rabbat, Pascal Vincent, James Pinkerton, Duo Wang, Nafissa Yakubova, Erich Owens, C. Lawrence Zitnick, Michael P. Recht, Daniel K. Sodickson, and Yvonne W. Lui.  fastmri: An open dataset and benchmarks for accelerated MRI.  2018\.  Clinical Orthopaedics and Related Research(CoRR).
  * [31] Kaiyu Yang, Klint Qinami, Li Fei-Fei, Jia Deng, and Olga Russakovsky.  Towards fairer datasets: Filtering and balancing the distribution of the people subtree in the imagenet hierarchy.  2020\.  Conference on Fairness, Accountability, and Transparency.
  * [32] Hamid R Sheikh, Muhammad F Sabir, and Alan C Bovik.  A statistical evaluation of recent full reference image quality assessment algorithms.  2006\.  IEEE Transactions on image processing.
  * [33] Chao Dong, Chen Change Loy, Kaiming He, and Xiaoou Tang.  Image super-resolution using deep convolutional networks.  CoRR, abs/1501.00092, 2015.
  * [34] Chao Dong, Yubin Deng, Chen Change Loy, and Xiaoou Tang.  Compression artifacts reduction by a deep convolutional network.  pages 576–584, 2015.


# Search and Rescue on a poset

Jan-Tino Brethouwer and Robbert Fokkink  Institute of Applied Mathematics
Delft University of Technology
Mekelweg 4
2628 CD Delft, The Netherlands
ORCiD: 0000-0003-1644-7483 0000-0001-8347-4110<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

A Search and Rescue game (SR game) is a new type of game on a graph that has
quickly found applications in scheduling, object detection, and adaptive
search. In this paper, we broaden the definition of SR games by putting them
into the context of ordered sets and Bayesian networks, extending known
solutions of these games and opening up the way to further applications.

###### Key words and phrases:

partially ordered set, search game, win-lose game, game on a graph, Bayesian
network.

###### 2010 Mathematics Subject Classification:

91A05,91A43, 06A07

This research was supported by grant N19/007 of the Dutch Ministry of Defence.

##  1\. Introduction

A search-and-rescue game, or SR game, is a two-player win-lose game that which
is played on a _finite_ set $X$ of locations. Hider chooses $h\in X$ and
Searcher chooses a permutation $\sigma$ of $X$, which we call a _search_. If
$\sigma(j)=h$ then $\\{\sigma(i)\colon i\leq j\\}$ is the set of _searched
locations_. For each $x\in X$ there is a Bernoulli random variable $\beta_{x}$
with known distribution to both players. Searcher wins (rescues) if the
product of $\beta_{x}$ over the searched locations is equal to one, and
otherwise she loses. In particular, the search halts as soon as $\beta_{x}=0$.
Searcher’s payoff $\Pi(\sigma,h)$ is the probability that she wins, which we
call the _rescue probability_. Hider wins if he is not rescued, i.e., we have
a suicidal Hider.

SR games were first defined by Lidbetter in [14] and quickly proved to be a
fruitful avenue of new study. It has been applied to scheduling problems [1,
2], object detection [4], rendezvous problems [13], and adaptive search [15].
For such applications it is natural to impose an order on the set of
locations, as some jobs can be performed only if other jobs have finished. In
our paper, we therefore consider SR games on a partially ordered set $X$. A
search now has to respect the order and is only allowed if
$\sigma(i)<\sigma(j)$ implies $i<j$. For instance, if $m\in X$ is a maximal
element for which $x<m$ for all $x\not=m$, then a search halts in $m$. We call
this an ordered search-and-rescue game, or simply an OSR game. We also
consider the stronger restriction that $\sigma$ is only allowed if $i<j$
implies $\sigma(i)<\sigma(j)$. A function with this property is called a
_chain_ [21] and we say that this game is a chained SR game, or simply a CSR
game. If we represent the partial order by a Hasse diagram, then we get a
search game on a (directed) graph, which is a topic of its own [10]. A search
is a path on the Hasse diagram in which Searcher may skip some vertices but is
not allowed to backtrack. She can either search a node or skip it without
turning back. This appears to be a new game on a graph.

The original SR game as defined by Lidbetter is a game on an (undirected)
graph. Searcher chooses a path and Hider chooses a vertex $h$. Searcher’s
payoff is the product of all $\beta_{v}$ over all vertices $v$ in the path
prior to $h$. More specifically, let the path be a walk along the vertices
$v_{1},v_{2},\ldots,v_{n}$ and let $v_{j}$ be the first vertex that is equal
to $h$. Then Searcher’s payoff is the expected value of

$\prod_{x\in\\{v_{1},\ldots,v_{j}\\}}\beta_{x},$

i.e., the product of the success probabilities. Note that
$\\{v_{1},\ldots,v_{j}\\}$ is a multi-set. Searcher is allowed to backtrack.
Even if $x$ occurs twice or more in the multi-set, then still $\beta_{x}$ is
only sampled once. If the graph is a rooted tree and if Searcher can only
start from the root, then Hider selects a leaf because all internal nodes of
the tree are dominated. Lidbetter proves that an optimal search consists of a
mix of depth-first searches. For instance, consider the following example from
[14] of a rooted tree with three leaves $a,b,c$ and one internal node. The
depth first searches in terms of arrivals at the leaves are $abc,bac,cab,cba$.

1/2r3/5i1/3a1/2b2/3c Figure 1. A tree with three leaves $a,b,c$ root $r$ and
internal node $i$. Success probabilities displayed in the nodes.

If $h=a$ and the depth-first search is $abc$ then Searcher’s payoff is
$\frac{1}{10}$. If the depth-first search is $bac$ then the payoff is
$\frac{1}{20}$.

In our approach, this SR game on a tree in Fig. 1 can be defined as an OSR
game on the unordered set $X=\\{a,b,c\\}$ with correlated random variables
$\beta_{a},\beta_{b},\beta_{c}$. The nodes $r,i$ correspond to events that
determine whether or not Searcher rescues. For instance, let $r$ be the event
“no storm” and let $i$ be the event“high visibility”. A rescue in $a$ and $b$
requires no storm and high visibility. A rescue in $c$ only requires no storm.
On top of that, the locations $a,b,c$ each have particular rescue
probabilities, dependent on these events $r,i$. In this approach the tree is a
_Bayesian network_ [12, 18] in which $r,i$ are latent variables. More
formally, let $Pr(x)=Pr(\beta_{x}=1)$ be the probability of a _successful
search_ of location $x$. If we put
$Pr(a)=\frac{1}{10},Pr(b)=\frac{3}{20},Pr(c)=\frac{1}{3}$ and we put the
conditional probabilities
$Pr(b|a)=\frac{1}{2},Pr(c|a)=Pr(c|b)=Pr(c|b,a)=\frac{2}{3}$, then we the
probability distribution is determined. We retrieve Lidbetter’s game on a
tree, in which Searcher can only search the leaves. The probabilities of the
internal nodes correspond to the correlations between the events $a,b,c$.

What happens to Lidbetter’s depth-first search theorem if we replace the
Bernoulli random variables by other random variables? Can we find effective
bounds on the value of the game? What happens if the search is ordered? These
are the motivating questions for this study.

The paper is organized as follows. We first introduce notation and
terminology. We then solve the CSR and OSR games on a poset for uncorrelated
Bernoulli random variables. Suprisingly, despite having a more restricted
strategy space, the CSR game is more difficult to solve. We then consider
correlated random variables, extending the work of Lidbetter in [14] and
linking the SR game to Bayesian networks. We are able to give bounds on the
value of the SR game, but we can only solve it for simple posets under
restrictions on the probability distribution of the Bernoulli random
variables. In the final section we discuss some further generalizations of SR
games.

##  2\. Definitions and notation

In this paper we consider games on a partially ordered set (poset) $(X,<)$
with an associated collection of Bernoulli random variables $\beta_{x}$
indexed by $X$. An SR game is an example of a _search game_ between an
immobile hider and a mobile searcher on a finite set of locations [3, Ch 3].
The strategy space of player II (Hider) is the set of locations $X$ and the
strategy space of player I (Searcher) are permutations of subsets of $X$.
Usually, in a search game the payoff is measured in duration or costs and
Hider is the maximizer. In an SR game, payoff is measured in probability and
Hider is the minimizer.

Throughout the paper we need some basic notions and results on posets, for
which [21] is a standard reference. The set $\\{1,\ldots,n\\}$ with its
standard total order is denoted $[n]$. A function $f\colon[n]\to X$ is order-
reflecting if $f(i)<f(j)$ implies $i<j$. We consider injective functions only.
Locations can be searched only once. The function is a chain if $i<j$ implies
$f(i)<f(j)$, in which case the image $f([n])$ is a totally ordered subset of
$X$. We associate functions with searches and denote them by $\sigma$ instead
of $f$.

We have a collection of Bernoulli random variables $\beta_{x}$ with $x\in X$.
These random variables may be _dependent_. We write $Pr(S)$ for the
probability that $\beta_{x}=1$ for all $x\in S$. If $S$ contains just one or
two elements, we write $Pr(x)$ or $Pr(x,y)$. $Pr(X)$ is the probability that
all searches are successful.

Hider selects a single element $h\in X$. Searcher selects an order-reflecting
function $\sigma$. Let $k$ be the minimal number such that $h\in\sigma([k])$.
If there is no such $k$ then Searcher receives $0$ and Hider receives $1$.
Otherwise Searcher’s payoff is

(1) $\Pi(\sigma,h)=Pr(\sigma([k]))$

and Hider’s payoff is the complementary probability. There is an abundance of
P’s: $\Pi$ is payoff and $Pr$ is probability. We say that this is an _OSR
game_. It models a process of progressive search. Once $x$ is searched all
unsearched $y<x$ become inaccessible. We have a _CSR game_ if Searcher is
limited to chains. It models a process of urgently progressive search. Once
$x$ is searched all $y<x$ and all $y$ that are unrelated to $x$ become
inaccessible. We denote the value of an SR game by $V(X)$. It will be clear
from the context what type of SR game we consider.

Both players face a decision problem in which they weigh their options. Ratios
of probabilities play a role and therefore it is convenient to consider the
_odds_ of events. For $x\in X$ we denote the odds of failure by

$o_{x}=\frac{1-Pr(x)}{Pr(x)}.$

If $Pr(x)=0$ then Hider will hide in $x$ and cannot be rescued. We require
that $Pr(x)>0$ for all $x\in X$ so the odds are well-defined. For $S\subset X$
we denote the sum of the odds by

$O_{S}=\sum_{x\in S}o_{x}.$

It is a quantity that often turns up in decision problems [5].

Lidbetter proved that an optimal search and rescue on a tree can be described
by weighed coin tosses, as in a behavior strategy [16]. It goes as follows.
Suppose $i$ is an internal node with children $a$ and $b$. Let $S\subset X$ be
the leaves that are descendants of $i$ and let $A$ and $B$ be the descendants
of $a$ and $b$. In particular, $S=A\cup B$. Let $V(A)$ be the value of the
subgame on the tree with root $a$, and let $V(B)$ be the value for $b$.
Searcher flips a coin with odds

(2) $\frac{1}{V(A)}-\frac{Pr(B)}{V(B)}\colon\frac{1}{V(B)}-\frac{Pr(A)}{V(A)}$

to decide between $a$ and $b$. After reaching a leaf, Searcher continues by
backtracking as in depth-first search. Note that $V(A)$ is the probability of
rescue in subgame $A$, which is greater than or equal to $Pr(A)$, the
probability of successful search of all locations. Therefore
$\frac{1}{V(A)}\geq 1$ and $\frac{Pr(B)}{V(B)}\leq 1$, so these odds are well-
defined. Also note that the odds favor the subgame with the smaller rescue
probability. An optimal search is most likely to start in the most difficult
subset first.

Hider can also select $h$ optimally by tossing coins and going down the tree.
At node $i$ the odds of choosing between $A$ and $B$ are

(3) $\frac{1-Pr(A)}{V(A)}\colon\frac{1-Pr(B)}{V(B)}.$

A suicidal Hider obviously has a preference for the set with the least rescue
probability and the largest probability of failure of the search.

##  3\. Uncorrelated Search and Rescue

In this section the random variables $\beta_{x}$ are uncorrelated.

######  Lemma 1.

Suppose $(X,\prec)$ is an extension of $(X,<)$, i.e., $x<y$ implies $x\prec
y$. Then $V(X,\prec)\leq V(X,<)$ for the OSR game and $V(X,\prec)\geq V(X,<)$
for the CSR game.

###### Proof.

If a map is order-reflecting for $\prec$, then it also is order-reflecting for
$<$. In the OSR game, the strategy space for Searcher does not decrease if we
replace $\prec$ by $<$. Therefore, the value of the OSR game does not decrease
if we replace $\prec$ by $<$. If a map is a chain for $<$, then it also is a
chain for $\prec$. By the same argument, the value of the CSR game does not
decrease if we replace $<$ by $\prec$. ∎

Unordered $X$. Suppose that the partial order on $X$ is trivial, i.e., the
only order relation is $x=x$. Chains are singletons and in the CSR game
Searcher can only search a single location. The payoff matrix is diagonal with
probabilities $Pr(x)$ on the diagonal. It is optimal for both players to
select $x$ with probability inversely proportional to $Pr(x)$. The value of
the CSR game can be expressed neatly in terms of the cardinality of $X$ plus
the sum of the odds of failure:

(4) $\frac{1}{|X|+O_{X}}.$

In the OSR game every search is allowed. This game is one of the motivating
examples that led Lidbetter to define SR games. It is related to single
machine scheduling, see [14]. Hider chooses $x$ with probability proportional
to $o_{x}$. Searcher starts a search in $x$ with probability proportional to
$o_{x}$, and continues randomly. The value of the OSR game is equal to

(5) $\frac{1-Pr(X)}{O_{X}}.$

In the degenerate case when $Pr(X)=1$ the rescue is always successful and the
odds of failure add up to zero. In this case the value of the game is equal to
1.

Totally ordered $X$. If $X$ is totally ordered, then an order-reflecting
function is a chain, which means that the CSR game and the OSR game are the
same. We can identify $X$ with $\\{1,\ldots,n\\}$. A search halts as soon as
it reaches the greatest element $n$. Suppose Searcher limits herself to
searches in which she starts in $i$ and searches the remaining locations in
increasing order. Then Hider and Searcher both have $n$ pure strategies and
the payoff matrix $M$ is triangular.

(6)
$M=\left[\begin{array}[]{rrrrl}p_{1}&p_{1}p_{2}&p_{1}p_{2}p_{3}&\cdots&p_{1}p_{2}p_{3}\cdots
p_{n}\\\ 0&p_{2}&p_{2}p_{3}&\cdots&p_{2}p_{3}\cdots p_{n}\\\
0&0&p_{3}&\cdots&p_{3}\cdots p_{n}\\\ \vdots&\vdots&\vdots&\ddots&\vdots\\\
0&0&0&\cdots&p_{n}\end{array}\right]$

The optimal Searcher strategy in this restricted game is to start from $i>1$
with probability proportional to $o_{i}$ and to start from $1$ with
probability inversely proportional to $p_{1}$. The optimal Hider strategy is
to choose location $i<n$ with a probability proportional to $o_{i}$ and
location $n$ with probability inversely proportional to $p_{n}$. The value of
the game with matrix $M$ is equal to

(7) $\frac{1}{1+O_{X}}.$

Now we limited Searcher’s strategies, but notice that Hider’s strategy remains
the same if we reorder the locations $1,\ldots,n-1$ in a random way. Hider’s
strategy remains optimal in the full game and therefore we have solved the
game.

######  Lemma 2.

The value of the OSR game on a poset $(X,<)$ with uncorrelated Bernoulli
random variables is contained in the interval
$\left[\frac{1}{1+O_{X}},\frac{1-Pr(X)}{O_{X}}\right].$ The value of the CSR
game is contained in the interval
$\left[\frac{1}{|X|+O_{X}},\frac{1}{1+O_{X}}\right].$

Note that $Pr(X)$ is small and $O_{X}$ is large for large $X$. The bounds on
the value of the OSR game produce a narrow interval if $X$ is large. We will
return to this lemma in the next section for correlated random variables.

###### Proof.

The value of the OSR game on an unordered $X$ is equal to
$\frac{1-Pr(X)}{O_{X}}$, which by lemma 1 puts an upper bound on the value.
For the lower bound, consider any extension of $(X,<)$ to a total order. This
restricts Searcher and gives the lower bound. For the CSR game, the same
argument works in the opposite direction by lemma 1. ∎

The multi-stage OSR game. Let $X=X_{1}\cup\cdots\cup X_{n}$ be a union of
disjoint sets and put $x<y$ if and only if $x\in X_{i}$ and $y\in X_{j}$ for
$i<j$. In other words, $X$ is an ordinal sum of unordered subsets, see [21, p
100]. We say that $X_{j}$ is _stage_ $j$. Once a search enters a stage it
cannot continue in an earlier stage. The game on this poset is very similar to
the game on a total order. Note that it is optimal to end with a full search
of the final stage. Searching an extra location cannot decrease the rescue
probability.

Let $V_{j}$ be the value of the OSR game restricted to $X_{j}$, which is
unordered. We write $P_{j}=Pr(X_{j})$ and $O_{j}=O_{X_{j}}$. By equation 5 we
have $V_{j}=\frac{1-P_{j}}{O_{j}}$. As in the game on a total order, suppose
Searcher limits herself to searches of consecutive stages $j,j+1,\ldots,n$.
Within each $X_{i}$ her search is optimal for the restricted game on this set.
Under this restriction, Searcher essentially only selects the initial stage
$j$ and therefore has $n$ strategies. In response, Hider also selects a stage
and applies his optimal strategy, so he essentially has $n$ strategies as
well. The payoff matrix $L$ is very similar to the matrix for the total order.

$L=\left[\begin{array}[]{rrrrl}V_{1}&P_{1}V_{2}&P_{1}P_{2}V_{3}&\cdots&P_{1}P_{2}P_{3}\cdots
V_{n}\\\ 0&V_{2}&P_{2}V_{3}&\cdots&P_{2}P_{3}\cdots V_{n}\\\
0&0&V_{3}&\cdots&P_{3}\cdots V_{n}\\\ \vdots&\vdots&\vdots&\ddots&\vdots\\\
0&0&0&\cdots&V_{n}\end{array}\right]$

The solution of this restricted game is similar to that of the total order.
Hider chooses stage $j<n$ with probability proportional to
$\frac{1-P_{j}}{V_{j}}=O_{j}$ and stage $n$ with probability proportional to
$\frac{1}{V_{n}}=\frac{O_{n}}{1-P_{n}}$. Note that $V_{n}=1$ if $P_{n}=1$.
Searcher starts in stage $j>1$ with probability proportional to
$\frac{1}{V_{j}}-\frac{P_{j-1}}{V_{j-1}}$ and starts in stage $1$ with
probability inversely proportional to $V_{1}$. In this way, Searcher makes
sure that she searches stage $j$ with probability proportional to
$\frac{1}{V_{j}}$. The value of the game with matrix $L$ is

(8) $\frac{1}{\frac{P_{n}O_{n}}{1-P_{n}}+O_{X}}.$

We need to argue that Searcher cannot do better than this. Suppose we combine
$X_{j-1}\cup X_{j}$ for $j<n$, then the number of stages goes down by one
which gives more freedom to Searcher, but we argue that Hider’s optimal
strategy does not change. In the game with $n$ stages, Hider selects stage
$j<n$ with probability proportional to $O_{j}$. He then selects $x\in X_{j}$
with probability proportional proportional to $o_{x}$. This is the same as
first selecting stage $X_{j-1}\cup X_{j}$ with probability proportional to
$O_{j-1}+O_{j}$ and then tossing a coin with odds $O_{j-1}\colon O_{j}$ to
select from $X_{j}$. We can combine or split up stages without affecting the
optimal Hider strategy. The game is equivalent to the two-stage game on the
ordinal sum $(X\setminus X_{n})\cup X_{n}$. All searches that start in
$X\setminus X_{n}$ and end with a full search of $X_{n}$ have expected
probability of rescue given by equation 8.

An element $m\in X$ is a _maximum_ if there are no $x>m$. Let $M\subset X$ be
the subset of maxima. An optimal search always ends in $M$. If $\sigma$ does
not end in $M$, then it can be extended by some $m\in M$ without decreasing
the probability of rescue. Since there is no order relation between different
elements of $M$, an optimal search ends with a full search of $M$.

######  Theorem 3.

Let $M\subset X$ be the subset of maxima. Let $P_{M}$ be the product of all
success probabilities over $m\in M$ and let $O_{M}$ be the sum of the odds
over $M$. The value of the OSR game on $X$ is equal to

(9) $\frac{1}{\frac{P_{M}O_{M}}{1-P_{M}}+O_{X}}.$

###### Proof.

Let $(X\setminus M)\cup M$ be the ordinal sum of two unordered subsets. The
value of the OSR game on this poset is given by equation 9. By lemma 1 this
puts an upper bound on the value of the OSR game on $X$. Conversely, extend
the partial order of $X\setminus M$ to a total order and consider the OSR game
on the resulting poset. By lemma 1 the value of the game on this poset puts a
lower bound. This is a multi-stage game that ends in $M$ such that all
previous stages are singletons. The value of this game is again given by
equation 9 and the lower bound equals the upper bound. ∎

This theorem settles OSR games and we now turn our attention to CSR games. Our
next lemmas sharpen the bounds of lemma 2.

######  Lemma 4.

Let $M\subset X$ be the subset of maxima. If Hider hides in $m\in M$ with
probability inversely proportional to $Pr(m)$ and in $x\in X\setminus M$ with
probability proportional to $o_{x}$, then the rescue probability is at most

$\frac{1}{|M|+O_{X}}$

for any search. This puts an upper bound on the value of the game.

###### Proof.

For any chain $x_{1},x_{2},\ldots,x_{k}$ that ends in $x_{k}\in M$, the
expected rescue probability is

$\frac{(1-Pr(x_{1}))+Pr(x_{1})(1-Pr(x_{2}))+\cdots+Pr(x_{1})\cdots
Pr(x_{k-1})}{|M|+O_{X}}=\frac{1}{|M|+O_{X}}.$

If the chain does not end in a maximum, then the rescue probability is less. ∎

An antichain is a subset $S\subset X$ such that any two elements of $S$ are
incomparable. The _width_ of $X$ is the size of its largest antichain. By
Dilworth’s theorem [6], it equals the minimum number of disjoint chains into
which the set can be partitioned

######  Lemma 5.

Let $w$ be the width of $X$. There exists a mixed Searcher strategy with
rescue probability at least

$\frac{1}{w+O_{X}}.$

This puts a lower bound on the value of the game.

###### Proof.

Consider the following strategy for Searcher. She decomposes $X$ into $w$
disjoint chains and selects a random $x\in X$ to start the search. The search
proceeds along the unique chain that contains it. Searcher selects initial
elements $x$ with probability inversely proportional to $Pr(x)$ and all other
elements with probability proportional to $o_{x}$. Suppose Hider selects $h$
and let $S=\\{x_{1},\ldots,x_{k}\\}$ be the chain that contains $h$ with
$x_{j}=h$. Within this subset $S$ we have the game on a total order in which
Searcher applies the optimal strategy. The rescue probability is the same for
all elements. Hider is indifferent between all elements of $X$. ∎

In particular, we have solved the game if $M$ is a maximal antichain of $X$.
For instance, if the Hasse diagram is a tree. The upper bound on the game
depends on $|M|$ which can be computed in linear time by depth-first search.
The lower bound on the game depends on $w$ which can be computed in polynomial
time [8].

The multi-stage CSR game. We reconsider the ordinal sum $X=X_{1}\cup\cdots\cup
X_{n}$ of unordered subsets, this time for the CSR game, in which Searcher can
only search one location from each $X_{i}$. In the OSR game, Searcher can
search all locations from $X_{i}$. As before, we write $O_{j}$ for the sum of
the odds over the elements in the stage $X_{j}$ for $i$ and we write $O_{\leq
j}$ for the sum of the odds over all stages $\leq j$. Let $k$ be such that
$|X_{k}|+O_{\leq k}$ is _maximal_. By lemma 4 Hider can limit the rescue
probability to

$\frac{1}{|X_{k}|+O_{\leq k}}$

by choosing $h$ from the first $j$ stages only. We show that Searcher can
actually achieve this rescue probability.

We add an initial node $s$ at stage zero and a terminal node $t$ at stage
$n+1$ with $Pr(s)=Pr(t)=1$. This does not change the game as $s$ and $t$ can
be searched for free and therefore Hider will not select these nodes. We
represent the search strategy as a network flow on the Hasse diagram of this
order, which has a single source $s$ and a single sink $t$. Searcher starts
from $s$ with probability one. We need to prove that Searcher achieves a
rescue probability $\geq\frac{1}{|X_{k}|+O_{\leq k}}$ at each node. Instead of
probability one, we give Searcher a total weight of $|X_{k}|+O_{\leq k}$ at
node $s$. Now she needs to make sure that the rescue probability is $\geq 1$
for each node. The inflow $I_{x}$ at each node $x$ has to be
$\geq\frac{1}{Pr(x)}$ which is needed to achieve rescue probability one.
Excess flow can skip the node. The rescue fails with probability $1-Pr(x)$ and
therefore takes away $o_{x}$ from the flow. The outflow is $I_{x}-o_{x}$. The
entire stage $j$ takes away $O_{j}$ from the flow. After $j<k$ stages the
total flow is reduced to $O_{\leq k}-O_{\leq j}+|X_{k}|$. The next stage
requires an inflow of $O_{j+1}+|X_{j+1}|$ which can be satisfied since

$O_{\leq k}-O_{\leq j}+|X_{k}|\geq O_{j+1}+|X_{j+1}|$

by the fact that $O_{\leq i}+|X_{i}|$ is maximal at $k$. After $k$ stages, the
outflow is equal to $|X_{k}|$. The required inflow for a stage $j>k$ is equal
to $O_{j}+|X_{j}|$ and this stage takes away $O_{j}$ from the flow. Since we
have

$|X_{k}|-O_{k+1}-\ldots-O_{j}\geq|X_{j}|$

the required inflow can always be met. This guarantees a rescue probability
$\geq 1$ for each node and if we normalize the probability than we find that
the value of the game is $\frac{1}{O_{k}+|X_{k}|}$.

An antichain $A\subset X$ is _maximal_ if for every $x\in X$ there is an $a\in
A$ such that either $a\leq x$ or $x\leq a$. A maximal antichain partitions the
poset $X$ into $A^{-}=\\{x\colon\exists a\in A,x\leq a\\}$ and
$A^{+}=\\{x\colon\exists a\in A,a<x\\}$. In other words, $A$ is a cut. The
elements of $A$ are maximal in the poset $A^{-}$ with the order inherited from
$X$. Hider can guarantee a rescue probability $\leq O_{A^{-}}+|A|$ by hiding
in $x\in A^{-}$ with probability $o_{x}$ if $x\not\in A$ and probability
inversely proportional to $Pr(x)$ if $x\in A$.

######  Theorem 6.

Let $A$ be a maximal antichain that maximizes $O_{A^{-}}+|A|$. The value of
the CSR game on $X$ is equal to

$\frac{1}{O_{A^{-}}+|A|}.$

###### Proof.

Hider can achieve this rescue probability. We need to prove that Searcher can
achieve it as well. We add a source $s$ and a sink $t$ with rescue probability
one, with $s<x<t$ for all $x\in X$. Searcher’s task is to find a network flow
such that the inflow $I_{x}\geq\frac{1}{Pr(x)}$ for all nodes. Each node
reduces the flow by $o_{x}$. We have a network flow problem but unlike the
standard max-flow min-cut problem it is max-cut min-flow and the flow is
dissipative. However, it is possible to modify the proof of the max-flow min-
cut theorem for this problem. We have adapted the proof given by Trevisan [24,
Ch 15].

Let $E$ be the edge set and let $f_{xy}$ be the flow on $(x,y)\in E$. There
are two constraints at each $x\in X$: inflow at least
$\frac{1}{Pr(x)}=o_{x}+1$ to guarantee rescue probability one, and dissipation
(inflow minus outflow) is at least $o_{x}$ to guarantee a full search of the
node.

$\begin{array}[]{ll@{}ll}\text{minimize}&\displaystyle\sum\limits_{(s,x)\in
E}f_{sx}&\\\ \text{subject to }\forall x\in X\\\ &\displaystyle\sum_{(v,x)\in
E}f_{vx}&\ \geq o_{x}+1,\\\ &\displaystyle\sum_{(v,x)\in
E}f_{vx}-\displaystyle\sum\limits_{(x,w)\in E}f_{xw}&\ \geq o_{x},\\\
\end{array}$

where all $f_{xy}\geq 0$. The dual problem has two variables for the two
constraints at each $x\in X$ and has one constraint for each $(v,x)\in E$.

$\begin{array}[]{ll@{}ll}\text{maximize}&\displaystyle\sum_{x\in
X}(o_{x}+1)g_{x}+o_{x}h_{x},&\\\ \text{subject to }\\\ &g_{x}+h_{x}\leq
1,&\forall(s,x)\in E,\\\ &g_{x}+h_{x}-h_{v}\leq 0,&\forall(v,x)\in E,\
v\not=s,\\\ \end{array}$

where all $g_{x},h_{x}\geq 0$. If we put $g_{a}=1$ for all $a\in A$ a maximal
antichain and $h_{b}=1$ for all $b<A$, and zero elsewhere, then the
constraints of the dual problem are satisfied. This choice is feasible and in
this case

$\sum\limits_{x\in X}(o_{x}+1)g_{x}+o_{x}h_{x}=O_{A^{-}}+|A|.$

We need to show that this is a solution of the dual problem for some
antichain, because then the minimax theorem implies that Searcher has a
feasible flow that achieves the required rescue probability.

Let $g_{x}$ and $h_{x}$ be a feasible solution of the dual problem. Pick
$0\leq T\leq 1$ uniformly at random and put $\bar{h}_{x}=1$ if $h_{x}\geq T$
and $\bar{g}_{x}=1$ if $h_{x}+g_{x}\geq T>h_{x}$. For all other $x$ we set
$\bar{h}_{x}=\bar{g}_{x}=0$. This implies that $\bar{h}_{x}+\bar{g}_{x}\leq 1$
and if $\bar{h}_{x}+\bar{g}_{x}=1$ then $\bar{h}_{v}=1$ for all $(v,x)\in E$.
Therefore $\bar{g}_{x}$ and $\bar{h}_{x}$ are feasible. We claim that
$A=\\{x\colon\bar{g}_{x}=1\\}$ is a (random) antichain. In other words, there
is no path between any $a,b\in A$. To see this, notice that $h_{a}<T$ and by
the second constraint $g_{x}+h_{x}<T$ for all successors of $a$. If
$g_{b}+h_{b}\geq T$ then $b$ is not a successor of $a$ and $A$ is indeed an
antichain.

The value of $\displaystyle\sum_{x\in X}(o_{x}+1)\bar{g}_{x}+o_{x}\bar{h}_{x}$
is equal to $O_{A^{-}}+|A|$, since all $x\in A^{-}$ either have
$\bar{g}_{x}=1$ or $\bar{h}_{x}=1$ and all $x\in A$ have $\bar{g}_{x}=1$. The
expected value is equal to

$\displaystyle\sum_{x\in X}(o_{x}+1)Pr(g_{x}+h_{x}\geq T>h_{x})+\sum_{x\in
X}Pr(h_{x}\geq T)=\displaystyle\sum_{x\in X}(o_{x}+1)g_{x}+\sum_{x\in
X}h_{x},$

which is maximal. Therefore, there must be an antichain such that
$O_{A^{-}}+|A|$ equals the solution of the dual problem, as required. ∎

The optimal Searcher strategy is a feasible solution of an LP problem and can
therefore be computed in polynomial time in terms of $|X|$. The optimal Hider
strategy can also be computed in polynomial time, by solving the dual problem
and random rounding.

##  4\. Correlated Search and Rescue

In this section the random variables $\beta_{x}$ are correlated. This makes
the games much more difficult to solve. We are only able to solve the games
for simple posets under strong restrictions on the distribution of the
Bernoulli random variables.

We first consider the OSR game on an unordered $X$: any permutation of $X$ is
an admissible search. If there are only two locations $X=\\{a,b\\}$ we have a
simple symmetric matrix game

$\begin{pmatrix}Pr(a)&Pr(a,b)\\\ Pr(a,b)&Pr(b)\end{pmatrix},$

which is easy to solve. For three locations the game is already much more
elaborate.

######  Definition 7.

For three locations $x,y,z$ we say that $x$ and $y$ are conditionally
independent with respect to $z$ if

$Pr(x,y|z)=Pr(x|z)Pr(y|z).$

It is denoted $(x\perp\\!\\!\\!\perp y|z)$.

The common way to define conditional independence is for events, which in our
case are successful searches of locations. We note that if $A,B,C$ are three
events such that $A\perp\\!\\!\\!\perp B|C$, then it does not necessarily hold
that $A\perp\\!\\!\\!\perp B|\overline{C}$, where $\overline{C}$ denotes the
complementary event of $C$.

Conditional independence is often interpreted in terms of learning [18]. An
equivalent way to define $(x\perp\\!\\!\\!\perp y|z)$ is $Pr(x|z,y)=Pr(x|z)$.
In terms of learning: if we learn that $z$ has happened, then the probability
of $x$ gets a Bayesian update $Pr(x|z)$, but if we then learn that $y$ has
also happened, we learn nothing new. In the SR game on three locations
$\\{a,b,c\\}$ in Fig. 1 we have that $Pr(c|a)=Pr(c|b)=Pr(c|b,a)$ and therefore
both $a\perp\\!\\!\\!\perp c|b$ and $b\perp\\!\\!\\!\perp c|a$.

The OSR game on three unordered locations. Let $X=\\{a,b,c\\}$ and suppose
that both $a\perp\\!\\!\\!\perp c|b$ and $b\perp\\!\\!\\!\perp c|a$. We build
a graphical model of this probability distribution in Fig. 2 in analogy of the
SR game on a tree in Fig. 1.

qra$Pr(a|b)$b$Pr(b|a)$$\frac{Pr(b|c)}{Pr(b|a)}$c$Pr(c|b)$$\frac{Pr(c)}{Pr(c|b)}$
Figure 2. The tree of Fig. 1 revisited as a network with events $a,b,c$ and
internal nodes $q,r$. The events $a,b,c$ represent successful rescue in these
three locations. The weights of the directed edges are ratios of conditional
probabilities.

The three leaves of the graphical model are labeled by the three locations.
Contrary to Fig 1, the internal nodes $q,r$ do not necessarily correspond to
events. The edge weights are _ratios_ of conditional probabilities, which may
be larger than one, which is why we say this is a _pseudo-Bayesian network_.
In Bayesian networks, nodes correspond to events and edge weights are
conditional probabilities, which are at most one. To compute the rescue
probability of a leaf, multiply the edge weights of the path to that leaf.
More generally, to compute $Pr(S)$ for $S\subset\\{a,b,c\\}$ multiply the edge
weights of its spanning tree. For instance,

$Pr(a,c)=\frac{Pr(c)}{Pr(c|b)}\cdot\frac{Pr(b|c)}{Pr(b|a)}\cdot Pr(c|b)\cdot
Pr(a|b)=\frac{Pr(b,c)\cdot Pr(a)}{Pr(b)}$

which is equal to $Pr(c|b)\cdot Pr(a)=Pr(c|a)\cdot Pr(a)$, for this tree. This
is indeed equal to $Pr(a,c)$.

In this setup, searching a leaf requires the probabilities of the path leading
up to it, as in Lidbetter’s SR game. If all edge weights are bounded by one,
then we are back at the original SR game on a tree. In fact, there is no need
to bound the weight $\frac{Pr(c)}{Pr(c|b)}$ of the first incoming edge. It is
a common divisor of all rescue probabilities. It is a sunk cost that can be
replace by one, without changing the optimal strategies of the players. then
we multiply all payoffs by $\frac{Pr(c|b)}{Pr(c)}$ and the game remains
essentially the same.

Suppose Searcher first successfully searches $b$. The probabilities of the two
remaining locations are now updated to $Pr(a|b)$ and $Pr(c|b)$. The Bayesian
factors for these updates satisfy

$\frac{Pr(c|b)}{Pr(c)}\leq\frac{Pr(a|b)}{Pr(a)}$

because the paths of $a$ and $b$ have more edges in common than the paths of
$c$ and $b$. The weights of these edges are taken out by the update, which is
why the Bayes factor for $a$ is larger and hence the incentive to now search
$a$ is stronger. This is a Bayesian interpretation of depth-first search.

In order to extend this example from three to more locations, we need some
further terminology. First of all, conditional independence extends from three
events as in definition 7 to collections of random variables. It is a central
topic of study in probabilistic learning [23]. We will need a rather special
notion that is tailored to SR games.

######  Definition 8 (co-independence).

Let $X=A\cup B$ be a partition into disjoint sets such that for any
$A^{\prime}\subset A,B^{\prime}\subset B$ and any $a\in A,b\in B$ it holds
that $Pr(A^{\prime}|B^{\prime})=Pr(A^{\prime}|b)$ and
$Pr(B^{\prime}|A^{\prime})=Pr(B^{\prime}|a)$. Furthermore,
$Pr(A^{\prime}|a,b)=Pr(A^{\prime}|a)$ and
$Pr(B^{\prime}|a,b)=Pr(B^{\prime}|b)$. Then we say that $A$ and $B$ are _co-
independent_ , denoted $X=A\|B$ or simply $A\|B$.

Informally speaking, each element of $A$ teaches us the same about $B$ and any
element from $B$ teaches us more about $B$ than all of $A$.

######  Definition 9.

Let $X$ be a set of two locations or more. We say that $X$ is _reducible_ if
it admits a partition $X=A\cup B$ into disjoint non-empty subsets $A\|B$. We
say that it is _completely reducible_ if every subset $Y\subset X$ containing
two elements or more is reducible.

In particular, if $X$ is completely reducible then $X=A_{0}\|A_{1}$, which can
be partitioned into $A_{0}=A_{00}\|A_{01}$ and $A_{1}=A_{10}\|A_{11}$ etc. In
the SR game on a tree, the probability distribution on the leaves is
completely reducible. For instance, in the SR game of Fig. 1 we have
$\\{a,b\\}\|{c}$ and $\\{a\\}\|\\{b\\}$.

######  Lemma 10.

If $X=A\|B$ then the Bayes factor

$\frac{Pr(A^{\prime}|B^{\prime})}{Pr(A^{\prime})}$

is the same for any nonempty $B^{\prime}\subset B$ and $A^{\prime}\subset A$.

###### Proof.

Let $a\in A$ and $b\in B$. By co-independence and the properties of
conditional probability

$\frac{Pr(A^{\prime}|B^{\prime})}{Pr(A^{\prime})}=\frac{Pr(A^{\prime}|b)}{Pr(A^{\prime})}=\frac{Pr(b|A^{\prime})}{Pr(b)}=\frac{Pr(b|a)}{Pr(b)},$

which does not depend on $A^{\prime}$ and $B^{\prime}$. ∎

######  Theorem 11.

Suppose that $X$ is completely reducible such that $X=A_{0}\|A_{1}$ and each
subsequent $A_{w}=A_{w0}\|A_{w1}$ for a binary word $w$. Then the probability
distribution can be represented by a pseudo-Bayesian tree with nodes $A_{w}$
and root $X$, which has an incoming edge without an initial node. Each $A_{w}$
has sibling $A_{\bar{w}}$, such that $w$ and $\bar{w}$ have common prefix $v$
and only differ in the last digit. In particular, $A_{v}$ is the parent of
$A_{w}$. The incoming edge of $A_{w}$ has weight

$\frac{Pr(a_{w0}|a_{\bar{w}})}{Pr(a_{w0}|a_{w1})},$

for arbitrary elements $a_{w}\in A_{w}$. The incoming edge of the root has
weight $\frac{Pr(a_{0})}{Pr(a_{0}|a_{1})}$, because the root has no sibling.
If $T$ is the spanning tree of $S\subset X$ then $Pr(S)$ is the product of the
weights of the edges in $T$.

###### Proof.

By induction, the conditional distribution $Pr(\cdot|a_{i})$ on $A_{i}$ for
$i\in\\{0,1\\}$ can be represented by pseudo-Bayesian trees. These are the two
subtrees that spring from the root $X$. Let $S_{i}=S\cap A_{i}$ for
$i\in\\{0,1\\}$. Then

$Pr(S)=Pr(S_{1}|S_{0})Pr(S_{0})=Pr(S_{1}|a_{0})Pr(S_{0}).$

By induction $Pr(S_{1}|a_{0})$ equals the product of the weights for its
spanning tree $T_{1}$ in the pseudo-Bayesian subtree for $A_{1}$. By lemma 10

$Pr(S_{0})=Pr(S_{0}|a_{1})\cdot\frac{Pr(a_{0})}{Pr(a_{0}|a_{1})}$

the right-hand side of which is equal to the product of the weights over the
spanning tree $T_{0}$ and the weight of the incoming edge at $X$. ∎

Note that we may switch the labels $0$ and $1$ and therefore
$\frac{Pr(a_{w0}|a_{\bar{w}})}{Pr(a_{w0}|a_{w1})}=\frac{Pr(a_{w1}|a_{\bar{w}})}{Pr(a_{w1}|a_{w0})}$.
Indeed, this is a consequence of co-independence, since

$\frac{Pr(a_{w0}|a_{\bar{w}})}{Pr(a_{w1}|a_{\bar{w}})}=\frac{Pr(a_{\bar{w}}|a_{w0})Pr(a_{w0})}{Pr(a_{\bar{w}}|a_{w1})Pr(a_{w1})}=\frac{Pr(a_{w0})}{Pr(a_{w1})}=\frac{Pr(a_{w0}|a_{w1})}{Pr(a_{w1}|a_{w0})}.$

If all weights are bounded by one (with the possible exception of the incoming
edge of the root, which is a sunk cost), then we have a proper Bayesian
network of events. In this case, the game is equivalent to an SR game on a
tree.

######  Corollary 12.

Lidbetter’s solution of the SR game on a tree extends to the OSR game for a
completely reducible distribution on an unordered $X$ provided that all
Bayesian factors $\frac{Pr(a_{w0}|a_{\bar{w}})}{Pr(a_{w0}|a_{w1})}\leq 1$.

If the weights are not $\leq 1$ then depth-first search need not be optimal
and we were unable to find a general solution for this game. We conjecture
that the optimal search is backjumping [25] in the opposite case when all
factors are $\geq 1$. Under backjumping, once the search reaches a leaf of the
tree, it continues at an unsearched node that is closest to the root. In this
respect it is the opposite of depth-first-search which continues at the
unsearched node that is closest to the leaf.

######  Conjecture 13.

Optimal search in the OSR game for a completely reducible distribution on an
unordered $X$ is backjumping if all Bayesian factors are $\geq 1.$

To specify this conjecture, suppose that a node $x$ has two children $a$ and
$b$ with offspring $A$ and $B$. If a search first visits a leaf in $A$ then it
does not re-enter $A$ before visiting a leaf of $B$. The backjump is maximal.
Backjump search is well-studied in AI and automatic theorem proving [19].

######  Corollary 14.

Let $X$ be unordered and completely reducible such that all weights on the
pseudo-Bayesian network are $\leq 1$ including the weight on the incoming edge
at the root. The OSR game on $X$ has value $V(X)\leq\frac{1-Pr(X)}{O_{X}}$.

###### Proof.

Let the decomposition of $X$ begin with $A\|B$ and let $w$ be the weight of
the incoming edge at the root. Searcher either starts with an exhaustive
search of $A$ followed by $B$, or vice versa. Hider hides in $A$ or in $B$.
Essentially we have a $2\times 2$ payoff matrix

$\begin{pmatrix}wV(A)&wPr(A)V(B)\\\ wPr(B)V(A)&wV(B)\end{pmatrix},$

where $V(A),V(B)$ are the values of the subgames on the two trees that spring
from the root and $Pr(A),Pr(B)$ are the products of the weights of these two
trees. Searcher incurs the cost $w$ and flips a coin as in equation 2. The
value of the game is

$\frac{w(1-Pr(A)Pr(B))}{\frac{1-Pr(A)}{V(A)}+\frac{1-Pr(B)}{V(B)}}.$

By induction the denominator is $\geq O_{A}+O_{B}=O_{X}$. We also have
$Pr(X)=w\cdot Pr(A)\cdot Pr(B)$. Therefore, the denominator is $w-Pr(X)\leq
1-Pr(X)$ by our assumption that $w\leq 1$. ∎

This bound is equal to the upper bound for uncorrelated random variables that
we found in lemma 2. It is possible to extend that lemma to correlated
Bernoulli random variables, under a restriction on their distribution.

######  Definition 15.

We say that the probability distribution on $X$ is _positively correlated_ if
$Pr(A|B)\geq Pr(A)$ for all $A,B\subset X$. We say that it is _negatively
correlated_ if $Pr(A|B)\leq Pr(A)$.

This property extends to arbitrary random variables for which it is known as
positive or negative _association_ [7]. Note that a completely reducible
distribution on $X$ with all weights $\leq 1$ is positively correlated. It is
negatively correlated if all weights are $\geq 1$. For positively correlated
$X$ the search gets progressively easier, which is a general assumption in
search games [9]. For negatively correlated $X$ it gets progressively more
difficult, which may be a more natural assumption for a rescue operation.

######  Lemma 16.

The value of the OSR game on a positively correlated poset $X$ is
$\geq\frac{1}{1+O_{X}}.$ The value of the CSR game on a negatively correlated
poset $X$ is contained in the interval
$[\frac{1}{|X|+O_{X}},\frac{1}{1+O_{X}}].$

In particular, the value of the OSR game on a completely reducible $X$ with
all weights $\leq 1$ is contained in the interval
$[\frac{1}{1+O_{X}},\frac{1-Pr(X)}{O_{X}}]$.

###### Proof.

For a positively correlated distribution we have that

$Pr(A)=Pr(A\setminus\\{a\\}|a)\cdot Pr(a)\geq Pr(A\setminus\\{a\\})P(a)$

for any $a\in A.$ By induction, $Pr(A\setminus\\{a\\})\geq\prod_{b\in
A\setminus\\{a\\}}Pr(b)$. Therefore, the payoff matrix is bounded from below
by the matrix for the uncorrelated SR game. By lemma 2 we conclude that
$V(X)\geq\frac{1}{1+O_{X}}$ for the OSR game. For a negatively correlated
distribution we have the opposite signs and we conclude that
$V(X)\leq\frac{1}{1+O_{X}}$ for the CSR game. The worst case CSR game is an
unordered $X$ in which Searcher can only search one location. The payoff
matrix is diagonal with entries $Pr(a)$. This game has value
$\frac{1}{|X|+O_{X}}$. ∎

So far we mainly considered unordered $X$, which is the least restrictive for
Searcher in the OSR game. A total order is most restrictive and we are only
able to solve that game in a limited case. Before doing that, we first exhibit
some examples to show that the solution of the OSR game is not trivial.

The OSR game on a total order. Let $X=\\{a,b,c\\}$ be a total order $a<b<c$.
The payoff matrix of the game is

$\begin{pmatrix}Pr(a)&Pr(a,b)&Pr(a,b,c)\\\ Pr(a)&0&Pr(a,c)\\\
0&Pr(b)&Pr(b,c)\\\ 0&0&Pr(c)\end{pmatrix}.$

We write $\bar{x}$ for the event that the search in $x$ is unsuccessful. A
straightforward but tedious computation shows that the solution of the game
depends on the Bayes factor

(10) $\frac{Pr(a|\bar{b},c)}{Pr(a|b)}.$

If it is more than one, Searcher’s optimal strategy mixes the searches in rows
$2,3,4$. If it is less than one, she mixes the searches in rows $1,3,4$.

The CSR game on a star. Let $X=U\cup\\{*\\}$ where $U$ is unordered and $u<*$
for all $u\in U$. The Hasse diagram of this poset is a star graph. A search
either consists of $*$ or of $\\{u,*\\}$. Suppose that $*$ is independent of
$U$, i.e., $Pr(u,*)=Pr(u)\cdot Pr(*)$. If Searcher selects $\\{u,*\\}$ with
probability proportional to $\frac{1}{Pr(u)}$, then Hider is indifferent
between all locations in $U$. The rescue probability in $*$ is proportional to
$|U|\cdot Pr(*)$. If $Pr(*)>\frac{1}{|U|}$ then Hider does not hide in $*$.
The game reduces to the CSR game on $U$ with value $\frac{1}{O_{U}+|U|}$. Not
all Hider strategies are active.

If $Pr(*)<\frac{1}{|U|}$ then Searcher includes the search $\\{*\\}$ with
probability proportional to $\frac{1}{Pr(*)}-|U|$ to make Hider indifferent.
Under this strategy the rescue probability is $\frac{1}{O_{X}+1}$ for all
locations. If Hider hides in $u$ with probability proportional to
$\frac{1-Pr(u)}{Pr(u)}$ and in $*$ with probability proportional to
$\frac{1}{Pr(*)}$, then the rescue probability is $\frac{1}{O_{X}+1}$. This is
the value of the game.

The CSR game on a star falls apart in two separate cases. Now consider an OSR
game on a total order $X=\\{1,2,\ldots,n\\}$. such that $Pr(A)=0$ for all sets
of cardinality $>1$ except for sets $A=\\{j,n\\}$. This is the CSR game on a
star, again illustrating that the OSR game on a total order falls apart into
different cases.

######  Theorem 17.

Let $X=\\{1,2,\ldots,n\\}$ be a negatively correlated total order such that
$n$ is independent of the other locations, i.e., $Pr(A|n)=Pr(A)$ for all
$A\subset X\setminus\\{n\\}$, and such that $Pr(n)\leq\frac{1}{n-1}$. Then the
value of the game is $V(X)=\frac{1}{O_{X}+1}$.

###### Proof.

By lemma 16 we know that $V(X)\leq\frac{1}{O_{X}+1}$. It suffices to find a
Searcher strategy that guarantees this rescue probability. Suppose Searcher
limits herself to a search of only one or two locations, one of which is $n$.
Then we have the SR game on a star with uncorrelated random variables, which
by the example above has the required value. ∎

##  5\. Further generalizations of SR games

There are several ways to generalize SR games that may deserve further study.
We discuss some of them here, without going into a full analysis.

General random variables. The most straightforward generalization is to
replace the $\\{0,1\\}$-valued random variables by arbitrary non-negative
random variables. Let’s denote the set of locations by $[n]=\\{1,\ldots,n\\}$
with partial order $\prec$ so that we can denote the random variable of
location $i$ by $X_{i}$. A possible interpretation of $X_{i}$ is that the
rescue comes with a certain (random) reward that depends on the location. For
example, an adversarial Hider that is out to do damage can be more or less
detrimental, depending on the location. In this setting it is natural to
replace $\\{0,1\\}$-valued variables by weighted variables. In analogy of
equation 1 we now have a zero-sum game with payoff equal to the expected value
of the product over the visited locations:

$\Pi(\sigma,h)=\mathbf{E}[X_{i_{1}}\cdot X_{i_{2}}\cdots X_{i_{k}}],$

where $i_{1},i_{2},\ldots,i_{k-1}$ are the searched locations before arriving
at the hideout $h=i_{k}$. If the random variables are independent and the
expected values are $\leq 1$, then the payoff matrix for this game is
equivalent to a payoff matrix for Bernoulli random variables. Our results from
section 2 carry over to this case.

If the expected values are not bounded by one, then the game gets more
difficult to solve. We illustrate that for the OSR game on a total order $[n]$
with expected values $e_{i}=E[X_{i}]$. If we limit Searcher to searches of
consecutive locations, then we get the payoff matrix of equation 6:

$A=\left[\begin{array}[]{rrrrl}e_{1}&e_{1}e_{2}&e_{1}e_{2}e_{3}&\cdots&e_{1}e_{2}e_{3}\cdots
e_{n}\\\ 0&e_{2}&e_{2}e_{3}&\cdots&e_{2}e_{3}\cdots e_{n}\\\
0&0&e_{3}&\cdots&e_{3}\cdots e_{n}\\\ \vdots&\vdots&\vdots&\ddots&\vdots\\\
0&0&0&\cdots&e_{n}\end{array}\right]$

We say that a subset of consecutive locations $i,i+1,\ldots,j$ is a _run_ if
all cumulative products $e_{i},e_{i}e_{i+1},\ldots,e_{i}e_{i+1}\cdots e_{j}$
are $\geq 1$. For a run we have that row $i$ of the matrix dominates the
following rows from $i+1$ up to $j+1$. We can delete these rows from the
matrix. If $j$ happens to be the final location $n$, then we only delete rows
up to $j$. Columns $i$ up to $j+1$ (or $n$) in the remaining matrix are
multiples of column $i$ by factors
$1,e_{i+1},e_{i+1}e_{i+2},\ldots,e_{i+1}e_{i+2}\cdots e_{j+1}$. The column
with the minimum multiple dominates the others, which can be deleted, so that
the resulting matrix is again triangular. Let $k$ be the location of the
remaining column. If Searcher searches $k$, then she also searches the
locations from $i$ up to $k$, so we can replace $X_{k}$ by $X_{i}\cdots
X_{k}$. Similarly, we can replace $X_{j+2}$ by $X_{k+1}\cdots X_{j+2}$.
Essentially, we have an OSR game on a total order, with a reduced number of
locations. By removing the runs, we end up with a game in which only the final
location possibly has expected value $>1$. The previous solution of the OSR
game with uncorrelated Bernoulli random variables carries over to this
situation.

Random rescue sets. Let $X$ denote the poset of locations, as before. A draw
from $\\{0,1\\}$-valued random variables $\beta_{x}$ corresponds to a random
subset $R\subset X$, which we call the _rescue set_. It is selected by Nature.
The players do not know which $R$ is drawn, but they do know Nature’s
probability distribution on the family of subsets $2^{X}$. For instance,
weather conditions could limit the search to $k$ out of $n$ locations, but it
is impossible to predict which locations will have bad weather. In this
example Nature draws draws uniformly from the subsets of cardinality $k$. If
$k=1$ then we have the special case of a CSR game on an unordered $X$ in which
every location has rescue probability $\frac{1}{n}$. If $k=n$ then all
locations can be searched and the only restriction is the order. This is an
example of the hypergraph incidence game [20].

In an SR game the search halts once it reaches a location $x\not\in R$. Bad
weather may prevent a successful rescue in a certain location, but it does not
stop the operation. A search can continue even if it visits a location that is
not in $R$. Let $S\subset X$ be the set of searched locations, i.e., the image
of $\sigma$. Then the payoff is one if $h\in R\cap S$ and zero otherwise. This
is an extension of the hypergraph incidence game, in which Searcher chooses an
edge $S$, Hider chooses a location $h$, and Searcher wins if $h\in S$.

Search and Recovery. In 2009 Air France Flight AF 447 disappeared on its way
from Rio to Paris over the middle of the Atlantic. After several unsuccessful
search operations, the wreckage was recovered two years later using Bayesian
search [22]. In this approach, the probability distribution of the location of
the wreckage (the prior) is updated after a search by a Bayesian factor that
compensates for the probability of detection. We can easily adapt SR games to
this situation, by interpreting $\beta_{x}$ as the probability of detection
instead of the probability of successful search. As in the case of rescue sets
in the previous example, a search is allowed to continue if $\beta_{x}$ is
equal to zero. This is Bayesian search against a worst-case prior
distribution. If Hider can move once search is over and before a new search
begins, then the game models a manhunt or a hunt for prey. Similar games have
been studied by Owen and McCormick [17] and Gal and Casas [11].

##  6\. Conclusion

We have presented a new type of Search and Rescue game on partially ordered
sets. We were able to solve the game in polynomial time in terms of the number
of locations for uncorrelated random variables. We showed that the SR game on
a tree can be interpreted as a game with correlated random variables, for
which the distribution is completely reducible. This game was solved by
Lidbetter under the restriction that Bayesian factors are bounded by one. The
solution of the game for general Bayesian factors remains open, but we did
find general bounds on the value of the game, and we conjecture that optimal
search is backjumping if all factors are at least equal to one. We hope that
our extension of SR games to posets and Bayesian networks provides a fruitful
avenue of further research and applications.

## References

  * [1] A. Agnetis, B. Hermans, R. Leus, and S. Rostami, Time-critical testing and search problems, European J. Oper. Res., 296 (2022), pp. 440–452.
  * [2] A. Agnetis and T. R. Lidbetter, The largest-z-ratio-first algorithm is 0.8531-approximate for scheduling unreliable jobs on m parallel machines, Oper. Res. Lett., 48 (2020), pp. 405–409.
  * [3] S. Alpern and S. Gal, The theory of search games and rendezvous, vol. 55, Springer Science & Business Media, 2006.
  * [4] A. Balaska and J. Rife, Defining time-varying metrics of task conflict in human/robot teams using simulated agents, in 2022 IEEE International Symposium on Technologies for Homeland Security (HST), IEEE, 2022, pp. 1–7.
  * [5] F. T. Bruss, Sum the odds to one and stop, Ann. Probab., (2000), pp. 1384–1391.
  * [6] R. P. Dilworth, A decomposition theorem for partially ordered sets, Classic papers in combinatorics, (1987), pp. 139–144.
  * [7] J. D. Esary, F. Proschan, and D. W. Walkup, Association of random variables, with applications, Ann. Math. Stat., 38 (1967), pp. 1466–1474.
  * [8] S. Felsner, V. Raghavan, and J. Spinrad, Recognition algorithms for orders of small width and graphs of small dilworth number, Order, 20 (2003), pp. 351–364.
  * [9] R. Fokkink, K. Kikuta, and D. Ramsey, The search value of a set, Ann. Oper. Res., 256 (2017), pp. 63–73.
  * [10] S. Gal, Search games: a review, Search theory: a game theoretic perspective, (2013), pp. 3–15.
  * [11] S. Gal and J. Casas, Succession of hide–seek and pursuit–evasion at heterogeneous locations, J. R. Soc. Interface, 11 (2014), p. 20140062.
  * [12] S. L. Jensen and T. D. Nielsen, Bayesian Networks and Decision Graphs, Springer, Berlin, 2007.
  * [13] P. Leone, J. Buwaya, and S. Alpern, Search-and-rescue rendezvous, European J. Oper. Res., 297 (2022), pp. 579–591.
  * [14] T. R. Lidbetter, Search and rescue in the face of uncertain threats, European J. Oper. Res., 285 (2020), pp. 1153–1160.
  * [15] T. R. Lidbetter and Y. Xie, The search and rescue game on a cycle, Theor. Comput. Sci., (2023), p. 114016.
  * [16] M. Maschler, S. Zamir, and E. Solan, Game theory, Cambridge University Press, 2020.
  * [17] G. Owen and G. H. McCormick, Finding a moving fugitive, a game theoretic representation of search, Comput. Oper. Res., 35 (2008), pp. 1944–1962.
  * [18] J. Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan kaufmann, 1988.
  * [19] A. Ramos, P. Van Der Tak, and M. J. Heule, Between restarts and backjumps, in Theory and Applications of Satisfiability Testing-SAT 2011: 14th International Conference, Ann Arbor, MI, USA., Springer, 2011, pp. 216–229.
  * [20] E. R. Scheinerman and D. H. Ullman, Fractional graph theory: a rational approach to the theory of graphs, Courier Corporation, 2011.
  * [21] R. P. Stanley, Enumerative combinatorics, Cambridge University Press, Cambridge, UK, 1999.
  * [22] L. D. Stone, C. M. Keller, T. M. Kratzke, and J. P. Strumpfer, Search for the wreckage of air france flight af 447, Stat. Sci., 29 (2014), pp. 69–80.
  * [23] M. Studeny, Probabilistic conditional independence structures, Springer Science & Business Media, 2006.
  * [24] L. Trevisan, Combinatorial optimization: exact and approximate algorithms, Stanford University, (2011).
  * [25] P. Van Beek, Backtracking search algorithms, in Foundations of Artificial Intelligence, vol. 2, Elsevier, 2006, pp. 85–134.