# A Game Theoretic Approach to a Problem in
Polymatroid Maximization

Lisa Hellerstein Department of Computer Science and Engineering, New York
University Tandon School of Engineering, New York, New York 11201,
<EMAIL_ADDRESS>Thomas Lidbetter Department of Management Science and
Information Systems, Rutgers Business School, Newark, NJ 07102,
<EMAIL_ADDRESS>
###### Abstract

We consider the problem of maximizing the minimum (weighted) value of all
components of a vector over a polymatroid. This is a special case of the
lexicographically optimal base problem introduced and solved by Fujishige. We
give an alternative formulation of the problem as a zero-sum game between a
maximizing player whose mixed strategy set is the base of the polymatroid and
a minimizing player whose mixed strategy set is a simplex. We show that this
game and three variations of it unify several problems in search, sequential
testing and queuing. We give a new, short derivation of optimal strategies for
both players and an expression for the value of the game. Furthermore, we give
a characterization of the set of optimal strategies for the minimizing player
and we consider special cases for which optimal strategies can be found
particularly easily.

Keywords: Game theory; search games; sequential testing; queuing

##  1 Introduction

A well understood problem in combinatorial optimization is that of maximizing
a linear function over a polymatroid. As shown in Edmonds, (1970), the
solution of the problem is given by a simple greedy algorithm whose output is
some vertex of the base of the polymatroid. A similar algorithm can be used to
minimize a linear function over a contrapolymatroid. (All concepts will be
defined precisely in Section 2).

Many optimization problems can be viewed as a special case of this problem.
The general approach is to associate some “performance vector” with each
possible choice of feasible solution to the problem in question, then to show
that the convex hull $\mathcal{B}$ of these vectors is the base of a
polymatroid or a contrapolymatroid. The objective function is then expressed
as a linear function over $\mathcal{B}$, so that it can be optimized using the
classic greedy algorithm.

One example of such a problem is the single machine scheduling problem
$1||\sum w_{j}C_{j}$ of choosing what order to process a finite set of jobs
with given processing times to minimize their weighted sum of completion
times: see Queyranne, (1993) and also Queyranne and Schulz, (1994). Agnetis et
al., (2009) showed that another scheduling problem, introduced by Stadje,
(1995), in which an unreliable machine sequentially processes a set of jobs,
can similarly be solved by maximizing a linear function over a polymatroid.
Kodialam, (2001) had previously studied this same polymatroid to solve a
different, but related problem in sequential testing. By considering so-called
conservation laws, Federgruen and Groenevelt, (1988) showed that the
performance space of several multiclass queueing systems have a polymatroid
structure, and this was extended to many other queueing problems by
Shanthikumar and Yao, (1992).

In this paper we focus on a max-min version of the classic problem of
maximizing a linear function over a polymatroid. This max-min problem is a
special case of the lexicographically optimal base problem, introduced and
solved by Fujishige, (1980). We equivalently view the max-min problem as a
zero-sum game between a maximizer whose pure strategies are the vertices of
the base of an $n$-dimensional polymatroid and a minimizer whose pure
strategies are the $n$ coordinate directions. Although the problem is already
solved, we give a new, concise derivation of the solution using our game
theoretic approach.

More importantly, we show that our problem provides a unifying framework for
many problems in search games, sequential testing and queueing; some known and
some new. Search games are two-person zero-sum games, where one player hides a
“target” which the other player must locate. (See Alpern and Gal, (2003) or
Hohzaki, (2016) for an overview on the search games literature.) In this paper
we solve a case of the weighted search game introduced by Yolmeh and Baykal-
Gürsoy, (2021), where a Searcher aims to minimize a weighted time to find a
target hidden among a finite number of locations with varying weights and
search times. We extend the weighted search game to incorporate the variable
speed search paradigm of Alpern and Lidbetter, (2014), and give a solution to
this problem too. We show that the solution of a search and rescue game
introduced by Lidbetter, (2020) also follows from a corollary of our main
results; furthermore we solve a more elaborate search and rescue game.

We show that our approach yields an alternative solution to a problem in
sequential testing previously solved by Kodialam, (2001) and Condon et al.,
(2009), in which operators sequentially perform tests on some tuples until
obtaining a negative test, and the objective is to find a randomized routing
of tuples to maximize throughput.

We also point out that our main problem can be used to address some max-min
(or min-max) multiclass queueing problems, which, as far as we know, have not
previously been considered in the literature. Although there are several
possible applications, we consider one concrete example of a multiclass
queueing problem in which one server processes jobs with exponentially
distributed service times that arrive according to a Poisson process. The
objective is to choose a randomized priority rule to minimize the maximum
expected holding cost of any job class in the steady state of the system. This
problem is a special case of our main problem.

In addition, we consider special cases of our main problem, where the payoff
function satisfies certain monotonicity properties that we define later.
Although these special cases are more limited than the main problem, they
include a number of particular problems, previously studied in the search
games and sequential testing literature, which admit simpler solutions than
the solutions to the main problem.

In Section 2 we review the notion of a polymatroid and the classic greedy
algorithm of Edmonds, (1970). We then describe our main problem, framing it as
a zero-sum game between a maximizer whose pure strategies are the set of
vertices $x$ of the base of a polymatroid and a minimizer whose pure
strategies are the coordinates $i$. The payoff of the game is $w_{i}x_{i}$ for
some fixed positive weights $w$ (in contrast to the classic problem of
Edmonds, (1970) where the objective is $w^{T}x$). We also describe three
variations of the game involving contrapolymatroids and min-max objectives.

In Section 3, we show that our problem and its variations unify several search
games. We also make a link to a sequential testing problem and discuss further
special cases of our problems in the field of queueing theory.

We give optimal strategies for both players in the main version of our game
and an expression for its value in Section 4. Our game theoretic angle on the
problem yields insights that were not captured in the work of Fujishige,
(1980) on the more general problem. We give a complete characterization of the
set of optimal strategies for Player 2. We also define special cases of the
problem where the payoff function of the game satisfies certain monotonicity
properties. While the value of the game and optimal strategies for both
players can always be found in strongly polynomial time (in the dimension of
the polymatroid), we show that in these special cases, the value of the game
can be found particularly quickly.

We discuss the three variations of our game in Section 5, and in Section 6 we
detail the implications of our results on the applications described in
Section 3. Finally, in Section 7, we further consider one of the special cases
of our game where the payoff function satisfies a monotonicity condition. For
this case, we give an efficient procedure that implements an optimal strategy
for Player 1. The support of this strategy is of exponential size, and the
procedure does not output an explicit representation of it as a convex
combination of pure strategies. Instead, the procedure can be used to
efficiently generate a pure strategy, drawn from the support of this optimal
strategy with the appropriate probability.

The results we give in Sections 4 and 7 for the special cases are inspired by
and generalize results in Condon et al., (2009) for particular sequential
testing problems.

##  2 Problem Statement

In this section we define and solve our main problem, then describe some
applications.

###  2.1 Review of Elementary Polymatroid Theory

Recall that a function $f:2^{V}\rightarrow\mathbb{R}$ is submodular if
$f(A)+f(B)\geq f(A\cup B)+f(A\cap B)$ for all $A,B\subseteq V$ and
$g:2^{V}\rightarrow\mathbb{R}$ is supermodular if $g(A)+g(B)\leq g(A\cup
B)+g(A\cap B)$ for all $A,B\subseteq V$ .

For the rest of this section we assume that $f:2^{V}\rightarrow\mathbb{R}_{+}$
is a non-negative, non-decreasing (with respect to set inclusion) submodular
function with $f(\emptyset)=0$, where $V=[n]\equiv\\{1,\ldots,n\\}$ for some
positive integer $n$. (We set $[n]=\emptyset$ if $n=0$.) We assume that the
values $f(S)$ are given by an oracle. Let $\mathcal{P}(f)$ be the polymatroid
associated with $f$, given by

$\mathcal{P}(f)=\\{x\in\mathbb{R}^{n}_{+}:x(S)\leq f(S)\text{ for all
}S\subseteq V\\},$

where $x(S)\equiv\sum_{j\in S}x_{j}$. We first review the problem of
maximizing a linear function $w^{T}x$ over $x\in\mathcal{P}(f)$, where
$w\in\mathbb{R}^{n}_{+}$ is a constant. Let $\sigma:V\rightarrow V$ be a
permutation (or bijection) of $V$ such that $w_{\sigma(1)}\geq\cdots\geq
w_{\sigma(n)}$. The classic solution to the problem, given in Edmonds, (1970)
is the point $x^{\sigma}$ given by

$\displaystyle
x^{\sigma}_{\sigma(j)}=f(\\{\sigma(1),\ldots,\sigma(j)\\})-f(\\{\sigma(1),\ldots,\sigma(j-1)\\}),~{}j=1,\ldots,n.$
(1)

Notice that for any $w$ and $\sigma$, we have $x^{\sigma}(V)=f(V)$, so an
equivalent problem is to maximize $w^{T}x$ over the base polyhedron
$\mathcal{B}(f)$ of $f$, given by

$\mathcal{B}(f)=\\{x\in\mathcal{P}(f):x(V)=f(V)\\}.$

The vertices of $\mathcal{B}(f)$ are given by all points $x^{\sigma}$ defined
by (1), as $\sigma$ ranges over the set $\Sigma\equiv\Sigma(V)$ of all
possible permutations of $V$.

Now let $g$ be an arbitrary non-decreasing, supermodular function with
$g(\emptyset)=0$. The contrapolymatroid $\mathcal{Q}(g)$ associated with $g$
is defined by

$\mathcal{Q}(g)\equiv\\{x\in\mathbb{R}^{n}:x(S)\geq g(S)\text{ for all
}S\subseteq V\\}.$

The base of $\mathcal{Q}(g)$ is given by

$\displaystyle\mathcal{B}(g)=\\{x\in\mathbb{R}^{n}:x(S)\geq g(S)\text{ for all
}S\subseteq V\text{ and }x(V)=g(V)\\}.$ (2)

Vertices $x^{\sigma}$ of $\mathcal{B}(g)$ are given analogously to (1).

Later, we will use the following fact, which is easy to verify.

###### Lemma 1

If $w_{i}>w_{j}$, then for any $x^{\sigma}$ that maximizes $w^{T}x$, there
exists some $\tilde{\sigma}$ such that $x^{\tilde{\sigma}}=x^{\sigma}$ and
$\tilde{\sigma}^{-1}(i)<\tilde{\sigma}^{-1}(j)$ (that is, $i$ precedes $j$ in
$\tilde{\sigma}$).

We note that in giving running times, we assume that it takes only constant
time to answer an oracle query.

###  2.2 The Main Problem

The problem we consider in this paper is that of finding some
$x\in\mathcal{B}(f)$ to maximize $\min_{j}w_{j}x_{j}$, where $f$ is an
arbitrary non-decreasing submodular function with $f(\emptyset)=0$. This is a
special case of the lexicographically optimal base problem, introduced by
Fujishige, (1980), where, subject to the minimum component being maximal, the
second-smallest component is maximized, and so on.

The special case that we study is equivalent to a zero-sum game in which a
pure strategy for Player 1 (the maximizer) is a permutation $\sigma$ of $V$
(or, equivalently, a vertex $x^{\sigma}$ of $\mathcal{B}(f)$) and a pure
strategy for Player 2 (the minimizer) is a direction $j\in V$. For a given
pair of pure strategies $\sigma$ and $j$, the payoff is given by

$P_{f,w}(\sigma,j)\equiv w_{j}x^{\sigma}_{j}.$

We will usually drop the $f$ and $w$ from the subscript of $P$. We denote this
game by $\Gamma_{\max}(\mathcal{B}(f),w)$. We will also consider a variation
of the game, which we denote by $\Gamma_{\max}(\mathcal{B}(f),w)$, which is
identical except that Player 1 is the minimizer and Player 2 is the maximizer.
Similarly, if $g$ is a non-decreasing supermodular function, we may consider
the games $\Gamma_{\max}(\mathcal{B}(g),w)$ and
$\Gamma_{\min}(\mathcal{B}(g),w)$, defined analogously.

A mixed strategy for Player 1 in $\Gamma_{\max}(\mathcal{B}(f),w)$ corresponds
to a point $x$ of $\mathcal{B}(f)$ and the expected payoff of such a strategy
against a pure strategy $j$ of Player 2 is $w_{j}x_{j}$.

A mixed strategy for Player 2 is a randomized choice of directions, where each
$j\in V$ is chosen with some probability $\theta_{j}\geq 0$, where
$\sum_{j=1}^{n}\theta_{j}=1$. For such a mixed strategy, the payoff against a
strategy $x$ of Player 1 is

$\sum_{j=1}^{n}\theta_{j}w_{j}x_{j}=x^{T}y,$

where $y=\sum_{j=1}^{n}\theta_{j}w_{j}e^{j}$, and $e^{j}$ is the $j$th
coordinate vector.

Equivalently, we may consider a mixed strategy for Player 2 as a point $y$ of
the simplex

$\displaystyle
C=\big{\\{}\sum_{j=1}^{n}\theta_{j}w_{j}e^{j}:\sum_{j=1}^{n}\theta_{j}=1\text{
and }\theta_{i}\geq 0\text{ for all }j=1,\ldots,n\big{\\}},$

so that a pure strategy for Player 2 is a vertex $w_{j}e^{j}$ of $C$. In a
small abuse of our notation, we write $P(x,y)$ for the expected payoff
$x^{T}y$ when Player 1 uses strategy $x$ and Player 2 uses strategy $y$. When
one player uses a pure strategy and the other uses a mixed strategy, we extend
the use of $P$ in the natural way.

Since each player has a finite number of pure strategies in each of its four
versions, the game has optimal mixed strategies and a value $v$, by the
minimax theorem for zero-sum games. For example, in the case of
$\Gamma_{max}(\mathcal{B}(f),w)$,

$v=\max_{x\in\mathcal{B}(f)}\min_{j}P(x,j)=\min_{y\in
C}\max_{\sigma\in\Sigma}P(\sigma,y).$

##  3 Applications

In this section we show how our main problem and its variations can be used to
model a number of search games as well as problems in sequential testing and
queuing.

###  3.1 Applications to Search Games

We begin by considering search games between a Searcher (Player 1) and a Hider
(Player 2), where $V$ corresponds to a set of hiding locations. In each
example, a Searcher pure strategy is a permutation $\sigma$ of $V$, where
$\sigma(i)$ is the location that is in position $i$ in the order of search and
a Hider pure strategy is a location $i\in V$ at which a target is hidden.

####  3.1.1 A weighted search game

Consider a game where the time to search location $i$ is given by $t_{i}>0$
and each location $i$ has a weight $d_{i}$, corresponding to the rate of
damage incurred at location $i$ while the target has not been found. The
payoff is given by $P(\sigma,i)=d_{i}C_{i}^{\sigma}$, for a permutation
$\sigma$ and $i\in V$, where

$C_{i}^{\sigma}=\sum_{\sigma^{-1}(j)\leq\sigma^{-1}(i)}t_{j}.$

This payoff is the total time to find the Hider multiplied by the rate of
damage. The Searcher is the minimizer and the Hider is the maximizer. This
game was considered by Yolmeh and Baykal-Gürsoy, (2021), who solved the
special case when the search times $t_{i}$ are all equal to 1, using a
polyhedral approach. (Yolmeh and Baykal-Gürsoy, (2021) also applied a column
and row generation approach to the game in a more general network setting,
with multiple searchers and targets.)

Condon et al., (2009) studied the special case of this game for
$d_{i}=1/c_{i}$, which they called the game theoretic multiplicative regret
game. This case was also studied by Angelopoulos et al., (2019). Implicit in
the results of Condon et al., (2009) is an optimal Player 1 (Searcher)
strategy and the value of the game for the general weighted search game with
arbitrary $d_{i}$.

Here we show how the game is a special case of
$\Gamma_{\min}(\mathcal{B}(g),w)$. The searching of locations is analogous to
the processing of jobs in single machine scheduling, and in the language of
scheduling theory, we can interpret the time $t_{i}$ as the processing time of
job $i$ and the time $C_{i}^{\sigma}$ as the completion time of job $i$ under
the schedule $\sigma$. We associate a Searcher pure strategy $\sigma$ with a
point $x^{\sigma}$ given by $x^{\sigma}_{i}=t_{i}C_{i}^{\sigma},~{}i\in V$. It
is well known from scheduling theory (see Queyranne and Schulz, (1994)) that
the set of vectors $x^{\sigma}$ are the vertices of $\mathcal{B}(g)$, where
$g$ is the supermodular function given by

$g(S)=\frac{1}{2}(t(S)^{2}+t^{2}(S)),$

and $t^{2}(S)=\sum_{i\in S}t_{i}^{2}$. The polyhedron $\mathcal{B}(g)$ is
known as the scheduling polyhedron and corresponds to the set of Searcher
mixed strategies in the search game. Let $w_{i}=d_{i}/t_{i}$. Then for a Hider
pure strategy $i$, the expected payoff against a Searcher mixed strategy given
by $x$ is $x_{i}w_{i}$. Hence, this is the game
$\Gamma_{\min}(\mathcal{B}(g),w)$.

####  3.1.2 A weighted search game with variable speeds

We can extend the model of the previous subsection by adopting the variable
speed network model, as considering by Alpern and Lidbetter, (2014). Suppose
that we think of the set of locations $V$ as endpoints of $n$ arcs, whose
other endpoint is a common point $O$. The Searcher successively travels from
$O$ to the end of each arc and back again, where the time to travel from $O$
to the end of arc $i$ is $a_{i}>0$ and the time to travel back again is
$b_{i}>0$. Let $t_{i}=a_{i}+b_{i}$ be the tour time of arc $i$. Similarly to
the previous subsection, the vector $\tilde{C}^{\sigma}$ is defined by

$\tilde{C}_{i}^{\sigma}=a_{i}+\sum_{\sigma^{-1}(j)<\sigma^{-1}(i)}t_{j}=C_{i}^{\sigma}-b_{i},$

and corresponds to the times the Searcher reaches each location under
$\sigma$.

We consider a weighted search game with a minimizing Searcher and a maximizing
Hider, whose payoff for a permutation $\sigma$ and $i\in V$ is given by
$d_{i}\tilde{C}_{i}^{\sigma}$. If $b_{i}=0$ for all $i$, then
$\tilde{C}^{\sigma}=C^{\sigma}$ and this is equivalent to the model of the
previous subsection.

The special case when the rates of damage $d_{i}$ are all equal to 1 was
solved by Alpern and Lidbetter, (2014) in the more general setting of tree
networks, but the optimal Searcher strategy given had exponential support size
even in the case of no network structure. The case of arbitrary $d_{i}$ has
not been considered before.

Let $\tilde{x}^{\sigma}_{i}=t_{i}\tilde{C}_{i}^{\sigma}$ and let
$w_{i}=d_{i}/t_{i}$, so that the payoff for a Searcher strategy $\sigma$ and a
Hider strategy $i$ is $w_{i}\tilde{x}_{i}$. Note that we can write
$\tilde{x}^{\sigma}=x^{\sigma}-c$, where $x^{\sigma}$ is defined as in the
previous subsection and $c$ is given by $c_{i}=b_{i}t_{i}$. Therefore, the
convex hull of the vectors $\tilde{x}^{\sigma}$ is equal to
$\mathcal{B}(g)-c=\mathcal{B}(\tilde{g})$, where $\tilde{g}$ is the non-
decreasing supermodular function given by

$\tilde{g}(S)=g(S)-c(S)=\frac{1}{2}(t(S)^{2}+\sum_{j\in
S}(a_{j}-b_{j})t_{j}).$

Therefore, this is the game $\Gamma_{\min}(\mathcal{B}(\tilde{g}),w)$.

####  3.1.3 A search and rescue game

We now introduce a new search game in which we independently associate to
every $i\in V$ a probability $p_{i}$ that the Searcher does not get captured
when searching location $i$ and a probability $q_{i}$ that a target located at
$i$ is found if location $i$ is searched. The payoff of the game is the
probability the Searcher finds the target without getting captured herself.
This is a generalization of the game introduced by Lidbetter, (2020) in which
$q_{i}=1$ for all $i$.

More precisely, for a given permutation $\sigma$ and a given $i\in V$, the
payoff is $q_{i}\pi_{i}^{\sigma}$, where

$\pi_{i}^{\sigma}=\prod_{\sigma^{-1}(j)\leq\sigma^{-1}(i)}p_{j}.$

The Searcher is the maximizer and the Hider is the minimizer. Let
$x^{\sigma}_{i}=\frac{1-p_{i}}{p_{i}}\pi_{i}^{\sigma}$. It was shown by
Kodialam, (2001) and independently by Agnetis et al., (2009) that the set of
vectors $x^{\sigma}$ are the vertices of $\mathcal{B}(f)$ where $f$ is the
non-decreasing submodular function given by

$\displaystyle f(S)=1-\prod_{i\in S}p_{i}.$ (3)

Setting $w_{i}$ to be equal to $q_{i}p_{i}/(1-p_{i})$, we see that this is the
game $\Gamma_{\max}(\mathcal{B}(f),w)$.

###  3.2 Relation to Sequential Testing

In this section we show that a sequential testing problem studied in Condon et
al., (2009) and Kodialam, (2001) is equivalent to the “minimization” version
of the game considered in Subsection 3.1.3.

Suppose some items, or tuples must be routed in some order through a set $V$
of operators, each of which tests whether the tuple satisfies some predicate
(or filter) of a conjunction. To spread the load on the operators, different
tuples may be routed in different orders. There is a known probability $p_{i}$
that a tuple will pass the test of operator $i$, and the tuple is routed
through the operators until it fails one of the tests (and is eliminated) or
it passes all of them. The problem here is to maximize the rate of flow of
tuples routed through the operators, subject to the constraint that operator
$i$ has a maximum flow rate of $r_{i}$. More precisely, the problem is given
by the following linear program, where we denote the set of permutations of
$V$ by $\Sigma(V)$.

$\displaystyle\text{max }\sum_{\sigma\in\Sigma(V)}\lambda_{\sigma}\quad\text{
s.t.
}\quad\sum_{\sigma\in\Sigma(V)}\lambda_{\sigma}\prod_{\sigma^{-1}(j)<\sigma^{-1}(i)}p_{j}$
$\displaystyle\leq r_{i}\text{ for all }i\in V,$
$\displaystyle\lambda_{\sigma}$ $\displaystyle\geq 0\text{ for all
}\sigma\in\Sigma(V).$

The variables $\lambda_{\sigma}$ here can be interpreted as the rate that
tuples are routed through the operators in the order given by the permutation
$\sigma$. We adopt the terminology of Condon et al., (2009) and call this the
max-throughput problem. The problem was solved in both Condon et al., (2009)
and Kodialam, (2001), the latter paper exploiting the polymatroid structure of
a space associated with the problem and the former giving a more efficient
combinatorial algorithm with no reference to polymatroids.

Let $q_{i}=1/(p_{i}r_{i})$ and recall the notation
$\pi_{i}^{\sigma}=\prod_{\sigma^{-1}(j)\leq\sigma^{-1}(i)}p_{j}$ of the
previous section. Let $v=1/(\sum_{\sigma\in\Sigma(V)}\lambda_{\sigma})$ and
let $\theta_{\sigma}=v\lambda_{\sigma}$. Then the max-throughput problem is
equivalent to the following LP

$\displaystyle\text{min }v\text{ s.t.
}\sum_{\sigma\in\Sigma(V)}\theta_{\sigma}q_{i}\pi_{i}^{\sigma}$
$\displaystyle\leq v\text{ for all }i\in V,$
$\displaystyle\sum_{\sigma\in\Sigma(V)}\theta_{\sigma}$ $\displaystyle=1,$
$\displaystyle\theta_{\sigma}$ $\displaystyle\geq 0\text{ for all
}\sigma\in\Sigma(V).$

This is the problem of finding an optimal strategy for Player 1 in the game
$\Gamma_{\min}(\mathcal{B}(f),w)$, where $f$ is given by (3) and
$w_{i}=q_{i}p_{i}/(1-p_{i})=r_{i}/(1-p_{i})$.

The derivation of the equivalence of these two problems closely follows the
derivation in Condon et al., (2009) of the equivalence of the game theoretic
multiplicative regret problem and an artificial problem they called the
cumulative cost limit problem.

###  3.3 Applications to Queueing Theory

As mentioned in the Introduction, the performance space of several multiclass
queueing systems have been shown in Federgruen and Groenevelt, (1988) and
Shanthikumar and Yao, (1992) to have a polymatroid structure. Possible
performance measures of interest include the expected delay of the first $m$
jobs, the expected number of type $i$ jobs in the system at time $t$ or the
expected number of job completions by time $t$. Depending on the context, the
objective may be to maximize or minimize the performance measure and many such
problems can be regarded as a special case of maximizing or minimizing a
linear function over the base of a polymatroid.

For every maximization or minimization problem of this type we can consider a
max-min or min-max variant. If we have an oracle for the submodular or
supermodular function that defines the polymatroid or contrapolymatroid
associated with a problem (in particular, if the function can be expressed in
closed form), then the solution of the max-min or min-max problem follows from
the results of this paper. We discuss one such problem here as an example
rather than giving an exhaustive list of problems.

Coffman Jr and Mitrani, (1980) consider a queueing system with a single server
with $n$ classes $V$ of jobs whose arrival times follow a Poisson process and
whose service times are exponentially distributed (that is, a $M/M/1$ system).
Jobs in class $i$ arrive at rate $\lambda_{i}$ and are serviced at rate
$\mu_{i}$. The traffic intensity of jobs of class $i$ is
$\rho_{i}=\lambda_{i}/\mu_{i}$. It is assumed that
$\rho(V)\equiv\sum_{i=1}^{n}\rho_{i}<1$, which ensures the existence of a
stationary distribution for the number of jobs in the system. The expected
time that jobs of class $i$ spend in the system in the steady state is denoted
$W_{i}$, and depends on the scheduling strategy chosen.

Let $x\in\mathbb{R}^{n}$ be defined by $x_{i}=\rho_{i}W_{i}$. It is shown in
Coffman Jr and Mitrani, (1980) that the space of feasible vectors $x$ is the
base $\mathcal{B}(g)$ of the contrapolymatroid given by the supermodular
function

$g(S)=\frac{\sum_{i\in S}\rho_{i}/\mu_{i}}{1-\rho(S)}.$

Each vertex $x^{\sigma}$ of $\mathcal{B}(g)$ corresponds to a priority rule
that assigns jobs to the server based on some fixed priority ordering of the
job classes (given by the permutation $\sigma$). A non-vertex point
$x=\sum_{\sigma\in\Sigma(V)}\theta_{\sigma}x^{\sigma}\in\mathcal{B}(g)$ can be
interpreted as a randomized priority rule where in each busy period the
priority rule $\sigma$ is chosen with probability $\theta_{\sigma}$.

A well known consequence is that if the objective is to minimize some weighted
sum $\sum_{i=1}^{n}c_{i}W_{i}$ of expected number of jobs in the system (where
$c_{i}$ may correspond to the holding cost per unit time of jobs of class
$i$), we can simply use the greedy algorithms of Edmonds, (1970) to minimize
$w^{T}x$ with $w_{i}=c_{i}/\rho_{i}$. The solution is a priority rule that
corresponds to some vertex of $\mathcal{B}(g)$.

Now suppose we wish to minimize the (weighted) maximum expected holding cost
of any class of jobs. That is, we wish to find a performance vector
$x\in\mathcal{B}(g)$ that minimizes $\max_{i}w_{i}x_{i}$. This is a special
case of $\Gamma_{max}(\mathcal{B}(g),w)$.

##  4 Solution and Special Cases

In this section we solve our main problem and its variations, and consider
some special cases.

###  4.1 Solution to Main Problem

We first note that for a given mixed strategy $y$ of Player 2 in the game
$\Gamma_{\max}(\mathcal{B}(f),w)$, the problem of finding a best response for
Player 1 is that of choosing $x\in\mathcal{B}(f)$ to maximize $x^{T}y$. This
is the classical problem solved in Edmonds, (1970) of maximizing a linear
function over $\mathcal{B}(f)$. With this observation, it follows that an
optimal strategy for Player 1 can be computed in polynomial time (in $n$)
using the ellipsoid algorithm (see e.g., Hellerstein et al., (2019)).
Fujishige, (1980) showed that his (unique) solution to the lexicographically
optimal base problem (and therefore an optimal Player 1 strategy) could be
found in strongly polynomial time. We give a new proof that this solution is
an optimal Player 1 strategy. Our proof of optimality follows almost
immediately from a duality approach.

For a subset $S\subseteq V$, $S\neq\emptyset$, denote $\sum_{i\in S}1/w_{i}$
by $w^{-1}(S)$. Consider the Player 2 mixed strategy

$y^{S}=\sum_{i\in
S}\left(\frac{w_{i}^{-1}}{w^{-1}(S)}\right)w_{i}e^{i}=\frac{1}{w^{-1}(S)}\sum_{i\in
S}e^{i}.$

For a Player 1 strategy $x\in\mathcal{B}(f)$, the expected payoff against
$y^{S}$ is

$P(x,y^{S})=\sum_{i\in
S}x_{i}\frac{1}{w^{-1}(S)}=\frac{x(S)}{w^{-1}(S)}\leq\frac{f(S)}{w^{-1}(S)},$

by definition of $\mathcal{B}(f)$. We summarize this in the following lemma.

###### Lemma 2

If Player 2 uses the strategy $y^{S}$ for some $S\neq\emptyset$, the expected
payoff is at most $f(S)/w^{-1}(S)$.

We will show in Theorem 4 that the strategy $y^{S}$ is optimal for Player 2,
where $S$ is chosen to minimize $f(S)/w^{-1}(S)$. A minimizing set $S$ can be
found in strongly polynomial time, using a parametric search (see Iwata et
al., (1997) [Section 6] for a parametric search algorithm for minimizing the
ratio of a submodular function to a non-negative supermodular function). This
relies on an algorithm for minimizing a submodular function. The fastest known
strongly polynomial algorithm for submodular function minimization is that of
Orlin, (2009), whose runtime is $O(n^{6})$, so that the minimization of
$f(S)/w^{-1}(S)$ takes time $O(n^{7})$.

Before stating and proving the theorem, we define a strategy which will be
optimal for Player 1. To do this, we recursively define a partition of $V$
into subsets $S_{1},\ldots,S_{r}$.

######  Definition 3 ($f$-$w$ decomposition)

Set $S_{0}=\emptyset$ and suppose $S_{0},\ldots,S_{j}$ have already been
defined for some $j\geq 0$. Then if $S^{j}\equiv S_{1}\cup\cdots\cup S_{j}$ is
equal to $V$, set $r=j$. If not, we define $S_{j+1}$ to be any set $S\subseteq
V\setminus S^{j}$ that minimizes $h_{S^{j}}(S)$, where

$h_{T}(S)\equiv\frac{f(T\cup S)-f(T)}{w^{-1}(S)}.$

We call $\mathcal{S}\equiv(S_{1},\ldots,S_{r})$ an $f$-$w$ decomposition of
$V$.

Note that the function $h_{T}$ is the ratio of a submodular function and a
modular function, therefore, as remarked earlier, it can be minimized in
strongly polynomial time. Since $h_{T}$ is defined in terms of $f$ and $w$, a
more informative notation is $h^{f,w}_{T}$, but we omit the superscripts in
general when they are clear from the context.

We now define the Player 1 strategy $x^{\mathcal{S}}$ by

$x^{\mathcal{S}}_{i}=w_{i}^{-1}h_{S^{j-1}}(S_{j})\text{ for all }i\in
S_{j},j=1,\ldots,r.$

To show that $x^{\mathcal{S}}$ it is indeed a strategy, we need to prove that
it lies in $\mathcal{B}(f)$. Let $T\subseteq V$ be arbitrary and let
$T_{j}=T\cap S_{j}$ for $j=0,1,\ldots,r$. Also set $T^{j}=\cup_{i\leq
j}T_{i}$. Then

$x^{\mathcal{S}}(T)=\sum_{j=1}^{r}\sum_{i\in
T_{j}}w_{i}^{-1}h_{S^{j-1}}(S_{j})=\sum_{j=1}^{r}w^{-1}(T_{j})h_{S^{j-1}}(S_{j})\leq\sum_{j=1}^{r}f(S^{j-1}\cup
T_{j})-f(S^{j-1}),$

by definition of $S_{j}$. Since $f$ is submodular, $f(S^{j-1}\cup
T_{j})+f(T^{j-1})\leq f(S^{j-1})+f(T^{j})$, so

$x^{\mathcal{S}}(T)\leq\sum_{j=1}^{r}f(T^{j})-f(T^{j-1})=f(T).$

Hence, $x^{\mathcal{S}}\in\mathcal{P}(f)$. It is also easy to see that
$x^{\mathcal{S}}(V)=f(V)$, so that $x^{\mathcal{S}}\in\mathcal{B}(f)$.

It is elementary to show that the strategy $x^{\mathcal{S}}$ is actually the
same for any $f$-$w$ decomposition, and is equivalent to Fujishige’s solution
to the lexicographically optimal base problem.

###### Theorem 4

Suppose $S^{*}$ is a non-empty set that minimizes $f(S)/w^{-1}(S)$. Then the
value of the game $\Gamma_{\max}(\mathcal{B}(f),w)$ is equal to
$f(S^{*})/w^{-1}(S^{*})$. An optimal strategy for Player 2 is $y^{S^{*}}$. An
optimal strategy for Player 1 is $x^{\mathcal{S}}$, where
$\mathcal{S}=(S_{1},\ldots,S_{r})$ is any $f$-$w$ decomposition.

Proof. By Lemma 2, the value of the game is at most $f(S^{*})/w^{-1}(S^{*})$.
To complete the proof, we will show that $x^{\mathcal{S}}$ ensures a payoff at
least $f(S^{*})/w^{-1}(S^{*})=h_{\emptyset}(S_{1})$ against any Player 2
strategy. Note that for a pure strategy $i$ of Player 2 with $i\in S_{j}$, the
expected payoff against $x^{\mathcal{S}}$ is

$P(x^{\mathcal{S}},i)=w_{i}x^{\mathcal{S}}_{i}=h_{S^{j-1}}(S_{j}).$

So it is sufficient to show that $h_{S^{j-1}}(S_{j})$ is non-decreasing in
$j$. By definition of $S_{j}$, we have

$\displaystyle\frac{f(S^{j})-f(S^{j-1})}{w^{-1}(S_{j})}\leq\frac{f(S^{j+1})-f(S^{j-1})}{w^{-1}(S_{j}\cup
S_{j+1})},$ (4)

for $j=1,\ldots,r-1$. Writing $w^{-1}(S_{j}\cup
S_{j+1})=w^{-1}(S_{j})+w^{-1}(S_{j+1})$ and rearranging yields

$w^{-1}(S_{j})(f(S^{j+1})-f(S^{j}))\geq w^{-1}(S_{j+1})(f(S^{j})-f(S^{j-1})).$

This is equivalent to $h_{S^{j}}(S_{j+1})\geq h_{S^{j-1}}(S_{j})$, and the
proof is complete. $\Box$

Any given mixed strategy $y$ of Player 2 can be expressed uniquely as a convex
combination of his pure strategies (that is, vertices of $w_{j}e^{j}$ of $C$)
simply by taking $\theta_{i}=y_{j}/w_{j}$. A given mixed strategy $x$ of
Player 1 can be written as a convex combination of at most $n$ of her pure
strategies $x^{\sigma}$, by Carathéodory’s Theorem. In general, as discussed
in Hoeksma et al., (2014), such a representation can be found in strongly
polynomial time by combining the generic approach of Grötschel et al., (2012)
with the algorithm of Fonlupt and Skoda, (2009) for finding the intersection
of a line with a polymatroid. The runtime of this algorithm is $O(n^{9})$. For
particular problems it is possible to exploit the structure of
$\mathcal{B}(f)$ in order to find a more efficient algorithm for representing
a Player 1 mixed strategy as a convex combination of at most $n$ of her pure
strategies.

In general, both players have multiple optimal strategies. For Player 2, we
can characterize these strategies.

Let $\mathcal{F}=\mathcal{F}(f)$ be the family of sets $S\neq\emptyset$ that
minimize $f(S)/w^{-1}(S)$, so that the value $v$ of the game is equal to
$f(S)/w^{-1}(S)$ for any $S\in\mathcal{F}$. We also set
$f(\emptyset)/w^{-1}(\emptyset)$ to be equal to $v$, so that
$\emptyset\in\mathcal{F}$. It is useful to note that $\mathcal{F}$ is a
lattice. Indeed, suppose $S,T\in\mathcal{F}$. In the following calculation, we
use the observation that for any $a,b,c,d>0$, if $a/b,c/d\geq v$ then
$(a+c)/(b+d)\geq v$, where the second inequality is tight if the first is also
tight. We have

$v=\frac{f(S)+f(T)}{w^{-1}(S)+w^{-1}(T)}\geq\frac{f(S\cup T)+f(S\cap
T)}{w^{-1}(S\cup T)+w^{-1}(S\cap T)}\geq v,$

where the equality and second inequality follow from our observation and the
first inequality follows from the submodularity of $f$. Therefore, the two
inequalities hold with equality, and ${S\cup T,S\cap T\in\mathcal{F}}$.

###### Theorem 5

A Player 2 strategy $y$ is optimal if and only if it is in the convex hull of
${\\{y^{S}:S\in\mathcal{F}(f)\\}}$.

Proof. By Theorem 4, each element of $\\{y^{S}:S\in\mathcal{F}\\}$ is optimal,
so any convex combination of such points is also optimal.

For the opposite direction, suppose that $y^{*}$ is an optimal Player 2
strategy. By relabeling, let us assume that $y^{*}_{1}\geq\cdots\geq
y^{*}_{n}$. Then recalling that $y^{S}=(\sum_{i\in S}e^{i})/w^{-1}(S)$ for
$S\subseteq V$ and setting $y^{*}_{n+1}=0$, we can write $y^{*}$ as

$y^{*}=\sum_{i=1}^{n}y^{*}_{i}e^{i}=\sum_{i=1}^{n}e^{i}\sum_{j=i}^{n}(y^{*}_{j}-y^{*}_{j+1})=\sum_{j=1}^{n}(y^{*}_{j}-y^{*}_{j+1})\sum_{i=1}^{j}e^{i}=\sum_{j=1}^{n}\lambda_{j}y^{[j]},$

where $\lambda_{j}=(y^{*}_{j}-y^{*}_{j+1})w^{-1}([j])$. Note that

$\sum_{j=1}^{n}\lambda_{j}=\sum_{j=1}^{n}(y^{*}_{j}-y^{*}_{j+1})\sum_{i=1}^{j}w_{i}^{-1}=\sum_{i=1}^{n}w_{i}^{-1}\sum_{j=i}^{n}(y^{*}_{j}-y^{*}_{j+1})=\sum_{j=1}^{n}y^{*}_{j}/w_{j}=1,$

where the final equality follows from the fact that $y^{*}\in C$. So $y^{*}$
is a convex combination of the strategies $y^{[j]}$. We claim that if
$\lambda_{k}>0$ for some $k$ then $[k]\in\mathcal{F}$, so that $y^{*}$ is in
fact a convex combination of strategies $y^{S}$ with $S\in\mathcal{F}$.
Indeed, suppose that $\lambda_{k}>0$, so that $y^{*}_{k}>y^{*}_{k+1}$. Since
any pure strategy best response $x$ to $y^{*}$ maximizes $x^{T}y^{*}$, by
Lemma 1, we can express $x$ as a point $x^{\sigma}$ such that the first $k$
terms of $\sigma$ are $[k]$ in some order. So by definition of $x^{\sigma}$,

$\displaystyle\sum_{i=1}^{k}x_{i}=f([k]).$ (5)

Equation (5) also holds for any mixed strategy $x$ which is a best response to
$y^{*}$ (since $x$ must be a mixture of pure best responses to $y^{*}$). In
particular, it holds for $x=x^{\mathcal{S}}$, where $\mathcal{S}$ is any
$f$-$w$ decomposition of $V$ whose first element $S_{1}$ is the maximal
element $\cup_{S\in\mathcal{F}}S$ of $\mathcal{F}$.

We claim that $[k]\subseteq S_{1}$. Let $i\in[k]$ and suppose $i\in S_{j}$ for
some $j>1$. Since $y^{*}_{i}\geq y^{*}_{k}>y^{*}_{k+1}\geq 0$ and any Player 2
pure strategy in the support of $y^{*}$ that is played with positive
probability must be a best response to $x^{\mathcal{S}}$, it follows that
strategy $i$ is a best response to $x^{\mathcal{S}}$. But by the maximality of
$S_{1}$, inequality (4) with $j=1$ is strict, and rearranging gives
$h_{\emptyset}(S_{1})<h_{S^{1}}(S_{2})$. Since $h_{\emptyset(S^{j-1}}(S_{j}))$
is non-decreasing, for any $i^{\prime}\in S_{1}$,

$P(x^{\mathcal{S}},i^{\prime})=h_{\emptyset}(S_{1})<h_{S^{j-1}}(S_{j})=P(x^{\mathcal{S}},i),$

so $i$ cannot be a best response to $x^{\mathcal{S}}$, a contradiction. Hence,
$i\in S_{1}$ so $[k]\subseteq S_{1}$.

Now, by definition of $x^{\mathcal{S}}$,

$\sum_{i=1}^{k}x^{\mathcal{S}}_{i}=\sum_{i=1}^{k}\frac{w_{i}^{-1}f(S_{1})}{w^{-1}(S_{1})}=w^{-1}([k])v,$

where $v$ is the value of the game. Combining this with (5) yields
$f([k])/w^{-1}([k])=v$, so $[k]\in\mathcal{F}$. This completes the proof.
$\Box$

###  4.2 Special Cases

To find optimal strategies in the game $\Gamma_{\max}(\mathcal{B}(f),w)$, it
is necessary to minimize the function $h_{T}(S)=(f(T\cup S)-f(T))/w^{-1}(S)$.
As previously remarked, there is a strongly polynomial time algorithm for this
problem with runtime $O(n^{7})$. To calculate an optimal Player 1 strategy,
this algorithm must be run at most $n$ times, so the overall runtime is
$O(n^{8})$. For some functions $f$, this minimization can be performed much
faster, as we show in the remainder of this section.

###### Definition 6

We say that the payoff $P=P_{f,w}$ is $\zeta$-decreasing if there exists
$\zeta\in\mathbb{R}^{n}_{+}$ such that for any $\sigma\in\Sigma(V)$ and any
$i,j\in V$ with $\sigma^{-1}(i)<\sigma^{-1}(j)$,

$\displaystyle\frac{P(\sigma,i)}{P(\sigma,j)}\geq\frac{\zeta_{i}}{\zeta_{j}}.$
(6)

If $\frac{P(\sigma,i)}{P(\sigma,j)}\leq\frac{\zeta_{i}}{\zeta_{j}}$ we say $P$
is $\zeta$-increasing. If $\zeta_{i}=1$ for all $i$, then we say $P$ is
decreasing (or respectively increasing).

If the payoff is $\zeta$-decreasing (or increasing) we assume that the values
$\zeta_{i}$ are given as part of the input of the problem.

###### Lemma 7

Suppose $P=P_{f,w}$ is $\zeta$-decreasing. Then
$S^{*}\equiv\cup_{S\in\mathcal{F}}S$ is equal to $\\{i\in V:\zeta_{i}\leq
r\\}$ for some $r>0$.

Proof. It is sufficient to show that if $P$ is $\zeta$-decreasing and $i\in
S^{*}$ and $j\notin S^{*}$, then $\zeta_{i}<\zeta_{j}$. Let $x^{\mathcal{S}}$
be any optimal Player 1 strategy such that the first set in the partition
$\mathcal{S}$ is $S^{*}$, and write
$x^{\mathcal{S}}=\sum_{\sigma\in\Sigma}\theta_{\sigma}x^{\sigma}$ as a convex
combination of pure strategies. Since $y^{S^{*}}_{i}>0=y^{S^{*}}_{j}$, for any
best response $\sigma$ to $y^{S^{*}}$, we can write
$x^{\sigma}=x^{\tilde{\sigma}}$, where
$\tilde{\sigma}^{-1}(i)<\tilde{\sigma}^{-1}(j)$, by Lemma 1. Since every pure
strategy in the support of $x^{\mathcal{S}}$ must be a best response to
$y^{S^{*}}$, we can assume that if $\theta_{\sigma}>0$ then
$\sigma^{-1}(i)<\sigma^{-1}(j)$. It follows from (6) that if $i\in S^{*}$ and
$j\notin S^{*}$, then

$\displaystyle\frac{P(x^{\mathcal{S}},i)}{\zeta_{i}}=\sum_{\sigma\in\Sigma}\frac{\theta_{\sigma}P(x^{\sigma},i)}{\zeta_{i}}\geq\sum_{\sigma\in\Sigma}\frac{\theta_{\sigma}P(x^{\sigma},j)}{\zeta_{j}}=\frac{P(x^{\mathcal{S}},j)}{\zeta_{j}}.$
(7)

By Theorem 5, every element of $S^{*}$ (in particular, $i$) is in the support
of some optimal Player 2 strategy and $j$ cannot be in the support of any
Player 2 strategy. Therefore, $i$ must be a best response to $x^{\mathcal{S}}$
and $j$ cannot be a best response, so that

$\displaystyle P(x^{\mathcal{S}},i)<P(x^{\mathcal{S}},j).$ (8)

Combining (7) and (8) yields $\zeta_{i}<\zeta_{j}$. $\Box$

It is worth pointing out that although the definition of $\zeta$-decreasing
and the proof of Lemma 7 are given in game theoretic terms, the lemma is not
exactly a game theoretic result, and could be stated without reference to the
game $\Gamma(\mathcal{B}(f),w)$. Indeed, it is easy to see that $P_{f,w}$ is
$\zeta$-decreasing if and only if there exists
$\zeta^{\prime}\in\mathbb{R}^{n}_{+}$ such that

$\displaystyle\frac{f(S\cup\\{i\\})-f(S)}{f(T\cup\\{j\\})-f(T)}\geq\frac{\zeta^{\prime}_{i}}{\zeta^{\prime}_{j}},$
(9)

for any $S\subset T$ with $i\notin S,j\notin T$.

Lemma 7 implies that for games $\Gamma_{\max}(\mathcal{B}(f),w)$ with a
$\zeta$-decreasing payoff function, the set $S^{*}=\cup_{S\in\mathcal{F}}S$
can be found in time $O(n\log n)$, simply by relabeling the the elements of
$V$ so that they are in non-decreasing order of the index $\zeta_{i}$,
computing $f([k])/w^{-1}([k])$ for each $k\in[n]$ and choosing the largest $k$
that minimizes this function. (Note that these $n$ computations can done in
time $O(n)$ by keeping a record of $w^{-1}([k])$ each time and adding
$w^{-1}_{k+1}$ to obtain $w^{-1}([k+1])$.) Therefore the value of the game
$f(S^{*})/w^{-1}(S^{*})$ and the optimal Player 2 strategy $y^{S^{*}}$ can be
found in time $O(n\log n)$.

In order to compute the optimal Player 1 strategy $x^{\mathcal{S}}$ it is
necessary to calculate an $f$-$w$ decomposition $\mathcal{S}$, which involves
at most $n$ minimizations of functions of the form $h_{T}(S)$. It is easy to
check that if $P(f,w)$ is $\zeta$-decreasing, then so is the function
$P(f_{T},w)$, where

$f_{T}(S)=f(T\cup S)-f(S).$

It follows that an $f$-$w$ decomposition can be found in time $O(n^{2})$.
(However, expressing $x^{\mathcal{S}}$ as a convex combination of at most $n$
pure strategies takes additional computation in general.)

We conclude this section by showing that when the payoff is decreasing, the
solution of the game is particularly simple.

###### Lemma 8

If $P=P_{f,w}$ is decreasing then $f(S)/w^{-1}(S)$ is non-increasing in $S$
and the value of the game is $f(V)/w^{-1}(V)$. The strategy $x^{\mathcal{S}}$
is optimal for Player 1, where $\mathcal{S}$ consists only of the set $V$, and
$y^{V}$ is optimal for Player 2.

Proof. Let $S\neq\emptyset$ be a proper subset of $V$, and without loss of
generality, assume that ${S=\\{1,\ldots,k\\}}$ for some $k$. Let $j\notin S$
and let $\sigma$ be any permutation of $V$ that starts with
$(1,2,\ldots,k,j)$. Since $P$ is decreasing, for any $i\in S$,

$w_{j}(f(S\cup\\{j\\})-f(S))=P(\sigma,j)\leq
P(\sigma,i)=w_{i}(f([i])-f([i-1])).$

Then setting $\theta_{i}=w_{i}^{-1}/w^{-1}(S)$, we obtain

$\displaystyle\frac{f(S)}{w^{-1}(S)}$
$\displaystyle=\sum_{i=1}^{k}\theta_{i}w_{i}(f([i])-f([i-1]))$
$\displaystyle\geq\sum_{i=1}^{k}\theta_{i}w_{j}(f(S\cup\\{j\\})-f(S))$
$\displaystyle=w_{j}(f(S\cup\\{j\\})-f(S)).$

Rearranging yields

$f(S\cup\\{j\\})w^{-1}(S)\leq f(S)w^{-1}(S\cup\\{j\\}),$

or equivalently,

$\frac{f(S\cup\\{j\\})}{w^{-1}(S\cup\\{j\\})}\leq\frac{f(S)}{w^{-1}(S)}.$

This proves that $f(S)/w^{-1}(S)$ is non-increasing in $S$, so the value of
the game is
$\min_{S\subseteq V}f(S)/w^{-1}(S)=f(V)/w^{-1}(V)$.

The optimality of the stated strategies is immediate from Theorem 4. $\Box$

##  5 Other Variations of the Game

Let $g^{\\#}$ be the dual of $g$, given by $g^{\\#}(S)=g(V)-g(V\setminus S)$.
It is easy to show that $g^{\\#}$ is submodular and non-decreasing with
$g^{\\#}(\emptyset)=0$ and $\mathcal{B}(g)=\mathcal{B}(g^{\\#})$. Moreover,
$P_{g,w}$ is $\zeta$-increasing if and only if $P_{g^{\\#},w}$ is
$\zeta$-decreasing. Therefore, the game $\Gamma_{\max}(\mathcal{B}(g),w)$ is
equivalent to $\Gamma_{\max}(\mathcal{B}(g^{\\#}),w)$, and the solution
follows immediately from Theorems 4 and 5. Versions of Lemmas 7 and 8 also
hold.

The minimization version $\Gamma_{\min}(\mathcal{B}(f),w)$ of the game does
not seem to be equivalent to the maximization version, but the solution and
analysis are almost identical. We briefly describe the solutions here and
leave the proofs as an exercise.

Analogously to an $f$-$w$ decomposition for submodular $f$, for supermodular
$g$ we define a $g$-$w$ max-decomposition $\mathcal{S}=(S_{1},\ldots,S_{r})$
as follows. Set $S_{0}=\emptyset$ and suppose $S_{0},\ldots,S_{j}$ have
already been defined for some $j\geq 0$. Then if $S^{j}\equiv
S_{1}\cup\cdots\cup S_{j}$ is equal to $V$, set $r=j$. If not, we define
$S_{j+1}$ to be any set $S\subseteq V\setminus S^{j}$ that maximizes
$h^{g,w}_{S^{j}}(S)$. This time, the function $h^{g,w}_{T}$ is the ratio of a
supermodular function and a modular function and can be maximized by using the
procedure of Iwata et al., (1997) to minimize the inverse ratio. Then the
Player 1 strategy $x^{\mathcal{S}}$ is defined in precisely the same way as in
the original version of the game.

###### Theorem 9

Let $f$ be a non-decreasing submodular function with $f(\emptyset)=0$ and let
$g$ be a non-decreasing supermodular function with $g(\emptyset)=0$. Then the
solutions to the games $\Gamma_{\max}(\mathcal{B}(f),w)$,
$\Gamma_{\max}(\mathcal{B}(g),w)$, $\Gamma_{\min}(\mathcal{B}(g),w)$ and
$\Gamma_{\min}(\mathcal{B}(g),w)$ are given in Table 1. The value and an
optimal Player 1 strategy are indicated in the second and third columns of the
table. In each case, the set of optimal Player 2 strategies is the convex hull
of the set of $y^{S^{*}}$ where $S^{*}$ ranges over all possible values as
given in the second column of the table. The fourth column gives a condition
on the payoff for the set $S^{*}$ to have the form given in the fifth column.
The sixth column gives a condition for $S^{*}$ to be equal to $V$.

Table 1: Solutions to four versions of the game with submodular $f$ and supermodular $g$ |  |  $\mathcal{S}$ for optimal | Condition |  $S^{*}$, if condi- | Condition
---|---|---|---|---|---
Game | Value | Player 1 | on payoff | tion on | on payoff
|  | strategy $x^{\mathcal{S}}$ |  | payoff holds |  for $S^{*}=V$
$\Gamma_{\max}(\mathcal{B}(f),w)$ | $\frac{f(S^{*})}{w^{-1}(S^{*})}=$ |  $f$-$w$ |  $\zeta$-decreasing | $\\{i:\zeta_{i}\leq r\\}$ | decreasing
| $\min_{S\subseteq V}\frac{f(S)}{w^{-1}(S)}$ | decomposition |  |  |
$\Gamma_{\max}(\mathcal{B}(g),w)$ | $\frac{g^{\\#}(S^{*})}{w^{-1}(S^{*})}=$ |  $g^{\\#}$-$w$ |  $\zeta$-increasing | $\\{i:\zeta_{i}\leq r\\}$ | increasing
| $\min_{S\subseteq V}\frac{g^{\\#}(S)}{w^{-1}(S)}$ | decomposition |  |  |
$\Gamma_{\min}(\mathcal{B}(g),w)$ | $\frac{g(S^{*})}{w^{-1}(S^{*})}=$ |  $g$-$w$ max- |  $\zeta$-increasing | $\\{i:\zeta_{i}\geq r\\}$ | increasing
| $\max_{S\subseteq V}\frac{g(S)}{w^{-1}(S)}$ | decomposition |  |  |
$\Gamma_{\min}(\mathcal{B}(f),w)$ | $\frac{f^{\\#}(S^{*})}{w^{-1}(S^{*})}=$ |  $f^{\\#}$-$w$ max- |  $\zeta$-decreasing | $\\{i:\zeta_{i}\geq r\\}$ | decreasing
| $\max_{S\subseteq V}\frac{f^{\\#}(S)}{w^{-1}(S)}$ | decomposition |  |  |

##  6 Implications for our Applications

We now discuss the implication of our results for the applications described
in Section 3.

###  6.1 Weighted Search Games

The solution of the weighted search game described in Subsection 3.1.1 follows
from Theorem 9. The value of the game is

$\max_{S\subseteq V}\frac{g(S)}{w^{-1}(S)}=\max_{S\subseteq
V}\frac{(t(S)^{2}+t^{2}(S))/2}{\sum_{i\in S}t_{i}/d_{i}}.$

It is easy to see that the payoff $P(\sigma,i)$ is $\zeta$-increasing where
$\zeta=d$. Hence, by Theorem 9, the value and optimal strategies can be found
in time $O(n\log n)$. To express the optimal Searcher strategy as a mixture of
at most $n$ pure strategies, one can use the strongly polynomial time
decomposition algorithm of Hoeksma et al., (2014).

We note that two different solutions of the special case when the rates of
damage $d_{i}$ are all equal to 1 were given by Lidbetter, (2013) and Alpern
and Lidbetter, (2013), though in each solution the size of the support of the
optimal Searcher strategy was exponential in $n$. Condon et al., (2009) also
considered this special case, calling it the game theoretic total cost
problem. They found an optimal Searcher strategy of support size $n$. Theorem
9 implies an alternative polynomial time algorithm for finding an optimal
Searcher strategy with support size $n$. Furthermore, the payoff is increasing
in this case, so Theorem 9 implies that the optimal Hider strategy given by
Lidbetter, (2013) and Alpern and Lidbetter, (2013) is unique.

The solution of the more general weighted search game with variable speeds of
Subsection 3.1.2 also follows from Theorem 9. The value of the game is

$\max_{S\subseteq V}\frac{g(S)}{w^{-1}(S)}=\max_{S\subseteq
V}\frac{(t(S)^{2}+\sum_{j\in S}(a_{j}-b_{j})t_{j})/2}{\sum_{i\in
S}t_{i}/d_{i}}.$

Again, the payoff function here is $\zeta$-increasing for $\zeta=d$, so the
value and optimal strategies can be found in time $O(n\log n)$. Also, since
$\mathcal{B}(\tilde{g})$ is simply a translation of $\mathcal{B}(g)$ by $-c$,
we can again use the decomposition theorem of Hoeksma et al., (2014) for
$\mathcal{B}(g)$ to write an optimal mixed Searcher strategy
$x\in\mathcal{B}(\tilde{g})$ as a convex combination of at most $n$ pure
strategies.

For the special case considered in Alpern and Lidbetter, (2014) where
$d_{i}=1$ for all $i$, our solution here improves upon the optimal Searcher
strategy of exponential support size. Also, since the payoff is increasing,
Theorem 9 implies that the optimal Hider strategy is unique.

###  6.2 The Search and Rescue Game

By Theorem 4, the value of the search and rescue game of Subsection 3.1.3 is

$\min_{S\subseteq V}\frac{f(S)}{w^{-1}(S)}=\min_{S\subseteq
V}\frac{1-\prod_{i\in S}p_{i}}{\sum_{i\in S}(1-p_{i})/(q_{i}p_{i})}.$

The payoff is easily seen to be $\zeta$-decreasing where $\zeta_{i}=q_{i}$ (or
indeed where $\zeta_{i}=q_{i}/p_{i}$). It follows from Theorem 9 that the
value and optimal strategies can be found in time $O(n\log n)$.

Kodialam, (2001) gave a strongly polynomial algorithm with runtime
$O(n^{3}\log n)$ for representing a point in $\mathcal{B}(f)$ as a convex
combination of at most $n$ vertices, and we can use this to express the
optimal Searcher strategy as a mixture of at most $n$ pure strategies.

In the special case considered by Lidbetter, (2020) where $q_{i}=1$ for all
$i$, a solution was given but the size of the support of the optimal Searcher
strategy was exponential in $n$. This approach gives an optimal strategy with
support size $n$. Since the payoff is decreasing in this case, the optimal
Hider strategy given in Lidbetter, (2020) is unique.

###  6.3 Sequential Testing

The solution to the sequential testing problem of Subsection 3.2 follows from
Theorem 9. The algorithm of Kodialam, (2001) is essentially a special case of
the algorithm given in the proof of Theorem 4.

###  6.4 Queuing Theory

A solution to the queuing problem posed in Subsection 3.3 is given by Theorem
9 of this paper, and the value of the min-max expected holding cost is

$\max_{S\subseteq V}\frac{g(S)}{w^{-1}(S)}=\max_{S\subseteq V}\frac{\sum_{i\in
S}\rho_{i}/\mu_{i}}{(1-\rho(S))\sum_{i\in S}\rho_{i}/c_{i}}.$

##  7 Finding Optimal Strategies when the Payoff is Monotone

As mentioned in Section 2, expressing an optimal Player 1 strategy $x^{S}$ as
a convex combination of pure strategies relies on an algorithm whose runtime
is $O(n^{9})$, in general. We have also seen that for particular polymatroids,
this runtime can be reduced. In this section we show that if $f$ is submodular
and $P_{f,w}$ is decreasing, then an optimal Player 1 strategy can be
efficiently implemented. More particularly, we show that a random pure
strategy can be drawn from the (exponentially-sized) support of this optimal
strategy, with appropriate probability, in time $O(n)$.

###### Theorem 10

Suppose $f$ is submodular and $P_{f,w}$ is decreasing. Then there is an
optimal Player 1 strategy $x$ for $\Gamma_{\max}(\mathcal{B}(f),w)$ such that
a random pure strategy $x^{\sigma}$ for Player 1, drawn from the distribution
on pure strategies defined by $x$, can be generated in $O(n)$ time. An
analogous result holds for $\Gamma_{\min}(\mathcal{B}(g),w)$ if $g$ is
supermodular and $P_{g,w}$ is increasing.

Proof. First, we introduce some notation. For $A\subseteq V$, let
$f_{A}:2^{V\setminus A}\rightarrow\mathbb{R}_{+}$ be given by
$f_{A}(S)=f(S\cup A)-f(A)$. We also write $f|_{A}$ for the function $f$
restricted to subsets of $A$ and $w|_{A}$ for the vector $w$ restricted to
elements in $A$. It is easy to show that $f_{A}$ and $f|_{A}$ are submodular
and the payoffs $P_{f|_{A},w|_{A}}$ and $P_{f_{A},w|_{A}}$ are decreasing.

We begin by constructing an optimal strategy for $P_{f,w}$. We construct the
strategy recursively. If $n=1$, only one strategy is available, which is
optimal. Suppose $n\geq 2$ and we have a construction for games such that the
number of Player 2 strategies is $n-1$ and let $V^{\prime}=V\setminus\\{n\\}$.
Define

  1. (i)

$\Gamma_{1}\equiv\Gamma_{\min}(\mathcal{B}(f|_{V^{\prime}}),w|_{V^{\prime}})$,

  2. (ii)

$\Gamma_{2}\equiv\Gamma_{\min}(\mathcal{B}(f_{\\{n\\}}),w|_{V^{\prime}})$,

whose values are $V_{1}\equiv f(V^{\prime})/w^{-1}(V^{\prime})$ and
$V_{2}\equiv(f(V)-f(\\{n\\}))/w^{-1}(V^{\prime})$, respectively, by Lemma 8.
By induction, we have a construction for an optimal strategy for both of these
games. Denote these optimal strategies $x^{1}$ and $x^{2}$, respectively. We
now define two new strategies $\tilde{x}^{1}$ and $\tilde{x}^{2}$ for
$\Gamma_{\min}(\mathcal{B}(f),w)$ as follows. The strategy $\tilde{x}^{1}$ is
obtained by replacing each pure strategy $x^{\sigma}$ in $x^{1}$ with
$x^{\sigma^{\prime}}$, where $\sigma^{\prime}$ is $\sigma$ followed by element
$n$. The strategy $\tilde{x}^{2}$ is obtained by replacing each pure strategy
$x^{\sigma}$ in $x^{2}$ with $x^{\sigma^{\prime\prime}}$, where
$\sigma^{\prime\prime}$ is $\sigma$ preceded by element $n$.

Table 2 displays the payoff of the strategies $\tilde{x}^{1}$ and
$\tilde{x}^{2}$ against the element $n$ and against any element of
$V^{\prime}$.

Table 2: Expected payoffs $P(\tilde{x}^{1},i)$ and $P(\tilde{x}^{2},i)$ for $i=n$ and $i\in V^{\prime}$. | $i=n$ | $i\in V^{\prime}$
---|---|---
$\tilde{x}^{1}$ | $w_{n}(f(V)-f(V^{\prime}))$ | $V_{1}$
$\tilde{x}^{2}$ | $w_{n}f(\\{n\\})$ | $V_{2}$

The function $f(S)/w^{-1}(S)$ is non-increasing, by Lemma 8. Hence,

$w_{n}f(\\{n\\})=\frac{f(\\{n\\})}{w^{-1}_{n}}\geq\frac{f(V)}{w^{-1}(V)}=\frac{f(V)}{w^{-1}(V^{\prime})+w^{-1}_{n}}.$

Rearranging, we obtain

$w_{n}f(\\{n\\})\geq\frac{f(V)-f(\\{n\\})}{w^{-1}(V^{\prime})}=V_{2}.$

Also,

$\frac{f(V^{\prime})}{w^{-1}(V^{\prime})}\geq\frac{f(V)}{w^{-1}(V)}=\frac{f(V)}{1/w_{n}+w^{-1}(V^{\prime})}.$

Rearranging gives

$w_{n}(f(V)-f(V^{\prime}))\leq f(V^{\prime})/w^{-1}(V^{\prime})=V_{1}.$

It follows that by mixing appropriately between strategies $\tilde{x}^{1}$ and
$\tilde{x}^{2}$, Player 1 can construct a strategy $x$ whose expected payoff
against against any pure strategy (and therefore also any mixed strategy) of
Player 2 is equal to some constant $c$. Therefore, by definition of the
optimal Player 2 strategy, $y^{V}$,

$c=P(x,y^{V})=\frac{f(V)}{w^{-1}(V)},$

so $c$ is the value $f(v)/w^{-1}(V)$ of the game and $x$ is optimal.

We note that, because each recursive call mixes between two strategies, the
support of the final constructed strategy $x$ has size $2^{n}$.

We now describe how to generate a random pure strategy $x^{\sigma}$ from the
distribution on pure strategies defined by $x$, without actually constructing
$x$. The procedure is similar to the recursive construction above. However, in
each recursive call, we do not recursively generate optimal strategies for
both $\Gamma_{1}$ and $\Gamma_{2}$. Instead, we first generate the payoffs in
Table 2 and calculate the mixing probabilities for $x^{1}$ and $x^{2}$, call
them $p^{\prime}$ and $p^{\prime\prime}$ (=$1-p^{\prime}$). We then randomly
choose between recursively generating a pure strategy for $\Gamma_{1}$ or for
$\Gamma_{2}$, choosing the first with probability $p^{\prime}$ and the second
with probability $p^{\prime\prime}$. Denote by $x^{\sigma}$ the pure strategy
that is generated. If it was generated for $\Gamma_{1}$, we return
$x^{\sigma^{\prime}}$, where $\sigma^{\prime}$ is produced from $\sigma$ by
appending element $n$. If it was generated for $\Gamma_{2}$, we return
$x^{\sigma^{\prime\prime}}$ where $\sigma^{\prime\prime}$ is produced from
$\sigma$ by prepending element $n$. It is clear that this procedure generates
a random pure strategy with the appropriate probability.

It remains to verify that this procedure can be implemented to run in time
$O(n)$. Recall that we assume that each oracle query can be answered in
constant time. The procedure makes $O(n)$ recursive calls. The only non-
trivial part of the analysis is the computation of the mixing probailities
$p^{\prime}$ and $p^{\prime\prime}$ in a recursive call. These are computed
from the four entries in Table 2. The entries in the first column of the table
can be computed in constant time. The entries in the second column, $V_{1}$
and $V_{2}$, are equal to $f(V^{\prime})/w^{-1}(V^{\prime})$ and
$f(V)/w^{-1}(V^{\prime})$ respectively. Computing these values from scratch in
each recursive call would take linear time per recursive call. However, using
the fact that $w^{-1}(V)=1/w_{n}+w^{-1}(V^{\prime})$, we can easily reduce the
computation in each recursive call to take constant time, by taking advantage
of the computation done in the previous recursive call. Thus the runtime is
$O(n)$.

An analogous result for $\Gamma_{\max}(\mathcal{B}(g),w)$ can be proved
similarly. $\Box$

##  8 Conclusion

We have shown that a number of natural games that arise in different research
areas can be understood and analyzed through a single unifying framework,
allowing us to gain new insight into existing results and to prove new
results. There are many related problems in search theory and sequential
testing that do not fall under this framework, including problems involving
networks and multiple targets. A promising avenue for future research could be
to explore polyhedral approaches to such problems.

### Acknowledgements

This material is based upon work supported by the National Science Foundation
under Grant Numbers IIS-1909335 and IIS-1909446.

## References

  * Agnetis et al., (2009) Agnetis, A., Detti, P., Pranzo, M., and Sodhi, M. S. (2009).  Sequencing unreliable jobs on parallel machines.  Journal of Scheduling, 12(1):45.
  * Alpern and Gal, (2003) Alpern, S. and Gal, S. (2003).  The theory of search games and rendezvous, volume 55.  Kluwer, Boston.
  * Alpern and Lidbetter, (2013) Alpern, S. and Lidbetter, T. (2013).  Mining coal or finding terrorists: The expanding search paradigm.  Operations Research, 61(2):265–279.
  * Alpern and Lidbetter, (2014) Alpern, S. and Lidbetter, T. (2014).  Searching a variable speed network.  Mathematics of Operations Research, 39(3):697–711.
  * Angelopoulos et al., (2019) Angelopoulos, S., Dürr, C., and Lidbetter, T. (2019).  The expanding search ratio of a graph.  Discrete Applied Mathematics, 260:51–65.
  * Coffman Jr and Mitrani, (1980) Coffman Jr, E. G. and Mitrani, I. (1980).  A characterization of waiting time performance realizable by single-server queues.  Operations Research, 28(3-part-ii):810–821.
  * Condon et al., (2009) Condon, A., Deshpande, A., Hellerstein, L., and Wu, N. (2009).  Algorithms for distributional and adversarial pipelined filter ordering problems.  ACM Transactions on Algorithms (TALG), 5(2):1–34.
  * Edmonds, (1970) Edmonds, J. (1970).  Submodular functions, matroids and certain polyhedra.  In Combinatorial structures and their applications, pages 69–87. Gordan and Breach, New York.  R. Guy, H. Hanani, N. Sauer and J. Shonheim, eds.
  * Federgruen and Groenevelt, (1988) Federgruen, A. and Groenevelt, H. (1988).  Characterization and optimization of achievable performance in general queueing systems.  Operations Research, 36(5):733–741.
  * Fonlupt and Skoda, (2009) Fonlupt, J. and Skoda, A. (2009).  Strongly polynomial algorithm for the intersection of a line with a polymatroid.  In Research Trends in Combinatorial Optimization, pages 69–85. Springer.
  * Fujishige, (1980) Fujishige, S. (1980).  Lexicographically optimal base of a polymatroid with respect to a weight vector.  Mathematics of Operations Research, 5(2):186–196.
  * Grötschel et al., (2012) Grötschel, M., Lovász, L., and Schrijver, A. (2012).  Geometric algorithms and combinatorial optimization, volume 2.  Springer Science & Business Media.
  * Hellerstein et al., (2019) Hellerstein, L., Lidbetter, T., and Pirutinsky, D. (2019).  Solving zero-sum games using best-response oracles with applications to search games.  Operations Research, 67(3):731–743.
  * Hoeksma et al., (2014) Hoeksma, R., Manthey, B., and Uetz, M. (2014).  Decomposition algorithm for the single machine scheduling polytope.  In International Symposium on Combinatorial Optimization, pages 280–291. Springer.
  * Hohzaki, (2016) Hohzaki, R. (2016).  Search games: Literature and survey.  Journal of the Operations Research Society of Japan, 59(1):1–34.
  * Iwata et al., (1997) Iwata, S., Murota, K., and Shigeno, M. (1997).  A fast parametric submodular intersection algorithm for strong map sequences.  Mathematics of Operations Research, 22(4):803–813.
  * Kodialam, (2001) Kodialam, M. S. (2001).  The throughput of sequential testing.  In International Conference on Integer Programming and Combinatorial Optimization, pages 280–292. Springer.
  * Lidbetter, (2013) Lidbetter, T. (2013).  Search games with multiple hidden objects.  SIAM Journal on Control and Optimization, 51(4):3056–3074.
  * Lidbetter, (2020) Lidbetter, T. (2020).  Search and rescue in the face of uncertain threats.  European Journal of Operational Research, 285(3):1153–1160.
  * Orlin, (2009) Orlin, J. B. (2009).  A faster strongly polynomial time algorithm for submodular function minimization.  Mathematical Programming, 118(2):237–251.
  * Queyranne, (1993) Queyranne, M. (1993).  Structure of a simple scheduling polyhedron.  Mathematical Programming, 58(1-3):263–285.
  * Queyranne and Schulz, (1994) Queyranne, M. and Schulz, A. S. (1994).  Polyhedral approaches to machine scheduling.  TU, Fachbereich 3, Berlin.
  * Shanthikumar and Yao, (1992) Shanthikumar, J. G. and Yao, D. D. (1992).  Multiclass queueing systems: Polymatroidal structure and optimal scheduling control.  Operations Research, 40(3-supplement-2):S293–S299.
  * Stadje, (1995) Stadje, W. (1995).  Selecting jobs for scheduling on a machine subject to failure.  Discrete Applied Mathematics, 63(3):257–265.
  * Yolmeh and Baykal-Gürsoy, (2021) Yolmeh, A. and Baykal-Gürsoy, M. (2021).  Weighted network search games with multiple hidden objects and multiple search teams.  European Journal of Operational Research, 289(4):338–349.