# A note on graphs with purely imaginary per-spectrum111This work is supported
by Department of Science and Technology (Govt. of India) through project
DST/04/2019/002676.

Hitesh Wankhede<EMAIL_ADDRESS><EMAIL_ADDRESS>Department of Computer Science and Engineering,
Indian Institute of Technology Indore, India. Ranveer Singh
<EMAIL_ADDRESS>Department of Computer Science and Engineering, Indian
Institute of Technology Indore, India.

###### Abstract

In 1983, Borowiecki and Jóźwiak posed an open problem of characterizing graphs
with purely imaginary per-spectrum. The most general result, although a
partial solution, was given in 2004 by Yan and Zhang, who show that if a graph
contains no subgraph which is an even subdivision of $K_{2,3}$, then it has
purely imaginary per-spectrum. Zhang and Li in 2012 proved that such graphs
are planar and admit a pfaffian orientation. In this article, we describe how
to construct graphs with purely imaginary per-spectrum having a subgraph which
is an even subdivision of $K_{2,3}$ (planar and nonplanar) using coalescence
of rooted graphs.

Key words: Permanental Polynomial, Bipartite Graphs, Theta Graphs,
Coalescence.

AMS subject classification (2020): 05C05, 05C31, 05C50, 05C75, 05C76.

##  1 Introduction

We consider simple and undirected graphs. Let $V(G)$ and $E(G)$ denote the
vertex set and the edge set of a graph $G$, respectively. If two vertices
$i,j\in V(G)$ are adjacent, then we write $i\sim j$. The _adjacency matrix_
$A(G)=(a_{ij})$ of a graph $G$ with $V(G)=\\{1,\dots,n\\}$ is the $n\times n$
matrix in which $a_{ij}=1$ if $i\sim j$, and $0$ otherwise. The _determinant_
and the _permanent_ of $A(G)$, are defined as

$\det(A(G))=\sum_{\sigma\in
S_{n}}\operatorname{sgn}(\sigma)\prod_{i=1}^{n}a_{i,\sigma(i)},$
$\operatorname{per}(A(G))=\sum_{\sigma\in
S_{n}}\prod_{i=1}^{n}a_{i,\sigma(i)},$

respectively, where $S_{n}$ is the set of all permutation of the set
$\\{1,2,\dots,n\\}$ and $\operatorname{sgn}(\sigma)$ is the signature of the
permutation $\sigma$. The _characteristic polynomial_ and the _permanental
polynomial_ of graph $G$ are defined as

$\phi(G,x)=\det(xI-A(G)),$ $\pi(G,x)=\operatorname{per}(xI-A(G)),$

respectively, where $I$ is the identity matrix of order $n$. The set of all
the roots (counting multiplicities) of $\phi(G,x)$ and $\pi(G,x)$ is called
the _spectrum_ and the _per-spectrum_ of the graph $G$, respectively. Let
$\sigma(G)$ and $\sigma_{p}(G)$ denote the spectrum and per-spectrum of a
graph $G$, respectively. Two graphs are _cospectral_ if they have the same
spectrum and _per-cospectral_ if they have the same per-spectrum. Both the
spectrum and the per-spectrum are graph invariants. Because if two graphs are
isomorphic, then they must necessarily have the same spectrum and the per-
spectrum. The converse need not be true.

A graph is said to be _determined by its spectrum (per-spectrum)_ , if any
other graph which is cospectral (per-cospectral) to it is also isomorphic.
Haemers and van Dam have conjectured that ‘Almost all graphs are determined by
their spectrum’ [12, 23]. Much work has been done on studying graphs using the
characteristic polynomial and its roots in Spectral Graph Theory, but very
less using the permanental polynomial in comparison [17]. The eigenvalues of a
matrix are the roots of its characteristic polynomial, but the familiar Linear
Algebra is not much helpful when studying the permanent as it is a
combinatorial function. However, much work has been done on finding bounds on
the permanent [3, 26]. Further, the determinant and the permanent look quite
similar by definition, but computationally they are extremely different. The
determinant can be computed in polynomial time using LUP decomposition, while
computing permanent is a #P-complete problem [22]. The ‘Computation of
Determinant vs. Permanent’ is a significant problem in Computational
Complexity Theory [1, 2]. This computational dichotomy is also explored using
the general notion of immanants in [8]. Some numerical evidence suggests that
the permanental polynomial might be better than the characteristic polynomial
in distinguishing graphs [9, 18]. This tradeoff between computational hardness
and the graph characterizing power is an interesting area to study. For an
excellent survey on permanental polynomial, we refer to [17]. For some recent
work on permanental polynomial, we refer to [27, 13, 14, 15, 16, 24].

Let $K_{m,n}$ denote the _complete bipartite graph_ with partite sets of size
$m$ and $n$, respectively. In case $m=1$, we get a _star graph_ with $n$
pendent vertices. Let $K_{n}$, $P_{n}$, and $C_{n}$ denote the _complete
graph_ , the _path graph_ , and the _cycle graph_ on $n$ vertices,
respectively. Note that the spectrum is always real, but the per-spectrum may
not be real. H. Sachs (1978) had noted that if $G$ is a tree such that
$\sigma(G)=\\{\lambda_{1},\lambda_{2},\dots,\lambda_{n}\\}$, then
$\sigma_{p}(G)=\\{i\lambda_{1},i\lambda_{2},\dots,i\lambda_{n}\\}$. Borowiecki
(1985) [4] generalized this observation by showing that a bipartite graph $G$
contains no $C_{k}$ for any $k\equiv 0$ (mod $4$) if and only if
$\sigma(G)=\\{\lambda_{1},\lambda_{2},\dots,\lambda_{n}\\}$ and
$\sigma_{p}(G)=\\{i\lambda_{1},i\lambda_{2},\dots,i\lambda_{n}\\}$. Thus, if
$G_{1}$ and $G_{2}$ are two bipartite graphs without $C_{k}$ for any $k\equiv
0$ (mod $4$), then $G_{1}$ and $G_{2}$ are cospectral if and only if they are
per-cospectral. In other words, the permanental polynomial is not any more
useful than the characteristic polynomial in characterization of such graphs.
Earlier, Borowiecki and Jóźwiak (1983) had posed the following open problem.

######  Problem 1.1.

[6] Characterize graphs with purely imaginary per-spectrum.222Zero is also
considered to be a purely imaginary number. The per-spectrum is purely
imaginary if each of the roots of the permanental polynomial is purely
imaginary.

Let $\mathcal{G}$ denote the class of graphs with purely imaginary per-
spectrum. The subdivision of an edge $(i,j)$ is the operation of replacing
$(i,j)$ with a path $(i,k,j)$ through a new vertex $k$. Let
$G=G_{0},G_{1},G_{2},\dots,G_{k}$ be a sequence of graphs such that for each
$i$, $G_{i}$ can be obtained from $G_{i−1}$ by subdividing an edge twice.
Then, $G_{k}$ is said to be an even subdivision of $G$. Yan and Zhang (2004)
[25] have given the most general but a partial solution to this problem. They
showed that if $G$ is a bipartite graph containing no subgraph which is an
even subdivision of $K_{2,3}$, then there exists an orientation $G^{e}$ with
skew-adjacency matrix $A(G^{e})$ such that $\pi(G,x)=\text{det}(xI−A(G^{e}))$.
The converse was proved by Zhang and Li (2012) [27] along with showing that
such graphs are planar and the orientation is pfaffian. They also give a
linear time algorithm to determine whether a given bipartite graph contains no
even subdivision of $K_{2,3}$. Since the skew-adjacency matrix $A(G^{e})$ is
skew-symmetric matrix, it has purely imaginary eigenvalues. It follows that
the class of graphs containing no subgraph of an even subdivision of $K_{2,3}$
is a subset of $\mathcal{G}$. Thus, we have

Class of trees $\subseteq$ Class of bipartite graphs without $C_{k}$ for any
$k\equiv 0$ (mod $4$) $\subseteq$ Class of graphs without a subgraph which is
an even subdivision of $K_{2,3}$ $\subseteq$ $\mathcal{G}$.

In this article, we wish to study the following problem.

######  Problem 1.2.

Let $G$ be a bipartite graph containing a subgraph which is an even
subdivision of $K_{2,3}$. When does it admit purely imaginary per-spectrum?

The rest of paper is organised as follows. In Section 2, we recall some
definitions, known results, and compute permanental polynomial of rooted
trees. In Section 3, we describe a construction of graphs with purely
imaginary per-spectrum and demonstrate it for some special cases.

##  2 Preliminaries

The permanental polynomial of a graph $G$ can also be computed using its Sachs
subgraphs, that is, subgraphs whose components are either edges or cycles of
length at least 3.

######  Proposition 2.1.

[5] Let $G$ be a graph on $n$ vertices with
$\pi(G,x)=\sum_{k=0}^{n}b_{k}x^{n-k}$. Then,

$b_{k}=(-1)^{k}\sum_{U_{k}}2^{c(U_{k})},$

where the summation is taken over all Sachs subgraphs $U_{k}$ on $k$ vertices
of $G$, and $c(U_{k})$ denotes the number of components of $U_{k}$ which are
cycles.

As a consequence, we get the following.

######  Proposition 2.2.

[5, 4, 7] A graph $G$ is bipartite if and only if $b_{k}=0$ for each odd
$k\in\\{0,1,2,\dots,n\\}$

Next, we show that graphs with purely imaginary per-spectrum are bipartite.

######  Proposition 2.3.

If $G\in\mathcal{G}$, then $G$ is bipartite.

###### Proof.

Let $\sigma_{p}(G)=\\{i\lambda_{1},i\lambda_{2},\dots,i\lambda_{n}\\}$, then
$\pi(G,x)=(x-i\lambda_{1})(x-i\lambda_{2})\dots(x-i\lambda_{n})$. If $k$ is
odd, then $b_{k}$ has the factor $i$. But since $\pi(G,x)$ has all real
coefficients, $b_{k}$ must be zero whenever $k$ is odd. Proof follows from
Proposition 2.2. ∎

Zhang, Liu and Li give a characterization of bipartite graphs in terms of the
per-spectrum.

######  Theorem 2.4.

[28] Let $G$ be a graph. Then,

  1. 1.

$\pi(G,x)$ has no negative root.

  2. 2.

If all the roots of $\pi(G,x)$ are real, then $G$ is empty.

  3. 3.

If $G$ is bipartite, then $\pi(G,x)$ has no real root except $0$.

  4. 4.

$G$ is bipartite if and only if the per-spectrum is symmetric with respect to
the real and the imaginary axes.

As a consequence of Proposition 2.3 and Theorem 2.4(4), a graph
$G\in\mathcal{G}$ if and only if its permanental polynomial has the form

$\pi(G,x)=x^{n-2k}(x^{2}+c_{1})(x^{2}+c_{2})\dots(x^{2}+c_{k}),$

where $c_{i}>0$ for each $i$ for some $k$. Let $G-S$ denote the induced
subgraph on the vertex set $V(G)-S$ for some $S\subseteq V(G)$. In case
$S=\\{r\\}$, we denote it by $G-r$.

Next, we recall a recursive formula to compute $\pi(G,x)$ of a graph $G$.

######  Lemma 2.5.

[5] Let $G$ be a graph, $u\in V(G)$, and $\Gamma_{u}(G)$ denote the set of
cycles passing through $u$. Then,

$\pi(G,x)=x\pi(G-u,x)+\sum_{v\sim
u}\pi(G-u-v,x)+2\sum_{C\in\Gamma_{u}(G)}(-1)^{|V(C)|}\pi(G-V(C),x),$

where $V(C)$ is the set of vertices in cycle $C$.

Let $(T,r)$ denote a tree $T$ rooted at the vertex $r$. Let
$u_{1},u_{2},\ldots,u_{k}$ denote the children of the root $r$, and
$(T_{1},u_{1}),(T_{2},u_{2}),\ldots,(T_{k},u_{k})$ denote the corresponding
rooted subtrees for some $k\geq 0$. We write
$(T,r)=\mathcal{R}(T_{1},T_{2},\dots,T_{k},r)$. In case
$T_{1}=T_{2}=\dots=T_{k}$, let $T^{\prime}:=T_{i}$ and $u^{\prime}:=u_{i}$ for
each $i=1,\dots k$, then we write $(T,r)=\mathcal{R}(T^{\prime(k)},r)$. Next,
we give a recursive formula to compute permanental polynomial of rooted trees.

######  Proposition 2.6.

Consider a rooted tree $(T,r)=\mathcal{R}(T_{1},T_{2},\dots,T_{k},r)$. Then,

$\pi(T,x)=x\pi(T-r,x)+\sum_{i=1}^{k}\left(\pi(T_{i}-u_{i},x)\prod_{j=1,j\neq
i}^{k}\pi(T_{j},x)\right).$

In case $(T,r)=\mathcal{R}(T^{\prime(k)},r)$, then the expression simplifies
to

$\pi(T,x)=x\pi(T-r,x)+k\left(\pi(T^{\prime}-u^{\prime},x)\pi(T^{\prime},x)^{k-1}\right).$

###### Proof.

First, note that $T-r=\cup_{i=1}^{k}T_{i}$. Hence, for each $i=1,\dots k$, we
have

$\pi(T-r,x)=\prod_{i=1}^{k}\pi(T_{i},x),\text{and }\pi(T-r-
u_{i},x)=\pi(T_{i}-u_{i},x)\prod_{j=1,j\neq i}^{k}\pi(T_{j},x).$

Using Lemma 2.5, we get

$\displaystyle\pi(T,x)$ $\displaystyle=x\pi(T-r,x)+\sum_{i=1}^{k}\pi(T-r-
u_{i},x).$

Proof follows by substitutions, and the second statement follows as a
corollary. ∎

The permanental polynomial of star graphs and path graphs can be computed
directly using the following proposition.

######  Proposition 2.7.

  1. 1.

$\pi(K_{1,n},x)=x^{n-1}(x^{2}+n)$

  2. 2.

$\pi(P_{n},x)=x\pi(P_{n-1})+\pi(P_{n-2})$ where $\pi(P_{0})=1$,
$\pi(P_{1})=x$. Equivalently,

$\pi(P_{n},x)=\sum_{m=0}^{\lfloor n/2\rfloor}\binom{n-m}{n-2m}x^{n-2m}.$

###### Proof.

For the star graph, substitute $k=n$ and $T_{i}=K_{1}$, and for the path
graph, substitute $k=1$ and $T_{i}=P_{n-1}$ in Proposition 2.6. The recurrence
relation of the permenental polynomial of the path graph can be solved either
using generating series or using Proposition 2.1. ∎

We say that a rooted tree $(T,r)$ is starlike if
$(T,r)=\mathcal{R}(K_{1,l}^{(k)},r)$, and pathlike if
$(T,r)=\mathcal{R}(P_{l+1}^{(k)},r)$ for some $l\geq 0$. See Figure 1(a),
1(b). Note that for a rooted starlike tree $T$, the subtrees
$(K_{1,l},u^{\prime})$ are rooted at the central vertex of degree $l$. So
consequently $\pi(T^{\prime},x)=x^{l-1}(x^{2}+l)$, and
$\pi(T^{\prime}-u^{\prime})=\pi(lK_{1},x)=x^{l}$, where $lK_{1}$ denotes $l$
copies of $K_{1}$. For a rooted pathlike tree $T$, we have
$\pi(T^{\prime},x)=\pi(P_{l+1})$, and $\pi(T^{\prime}-u^{\prime})=\pi(P_{l})$.

$r$$u_{1}$$u_{3}$$u_{2}$ (a) Starlike tree $\mathcal{R}(K_{1,4}^{(3)},r)$

$r$$u_{1}$$u_{3}$$u_{2}$ (b) Pathlike tree $\mathcal{R}(P_{5}^{(3)},r)$

$u$$v$ (c) Theta graph $\Theta_{1,2,3}$

Figure 1:

Let $u$, $v$ be two vertices, and $a,b,c\geq 1$. A theta graph
$\Theta_{a,b,c}(u,v)$ is a graph on $a+b+c+2$ vertices such that there are
three disjoint paths from $u$ to $v$ of lengths $a+1$, $b+1$ and $c+1$. See
Figure 1(c). Any theta graph is a homeomorphic image of $K_{2,3}$ as it can be
obtained by repeated subdivisions of $K_{2,3}$ 333A recursive formula to
compute the characteristic polynomial of a theta graph in one of the
parameters was given by Sciriha and Fiorini [20].. For example, we have
$\Theta_{1,1,1}=K_{2,3}$. An even subdivision of $K_{2,3}$ is a theta graph
with all odd parameters. Note that after removing a vertex of degree $3$ from
a theta graph, we get a pathlike tree. Hence, we can obtain a formula for
$\pi(\Theta_{a,b,c},x)$ in terms of the permanental polynomial of path graphs
using Lemma 2.5.

Consider two rooted graphs $(G_{1},r_{1})$ and $(G_{2},r_{2})$. By identifying
$r_{1}$ in $G_{1}$ with $r_{2}$ in $G_{2}$, we construct a new graph
$G_{1}\cdot G_{2}$ called the coalescence of $G_{1}$ and $G_{2}$. Schwenk
(1974) proved the following relation which holds for both the characteristic
and the permanental polynomial.

######  Lemma 2.8.

[19] Let $(G_{1},r_{1})$ and $(G_{2},r_{2})$ be two rooted graphs, then

$\pi(G_{1}\cdot
G_{2},x)=\pi(G_{1},x)\pi(G_{2}-r_{2},x)+\pi(G_{1}-r_{1},x)\pi(G_{2},x)-x\pi(G_{1}-r_{1},x)\pi(G_{2}-r_{2},x).$

##  3 Construction

In this section, we describe a construction of graphs with purely imaginary
per-spectrum and demonstrate it for some special cases. First, we discuss some
examples.

The graphs containing no subgraph which is an even subdivision of $K_{2,3}$
are planar, but not all planar graphs are in $\mathcal{G}$. The smallest
example of a planar graph not in $\mathcal{G}$ is $K_{2,3}$ itself. The
smallest planar graph in $\mathcal{G}$ containing an even subdivision of
$K_{2,3}$ is a graph on $8$ vertices (denote this by $G_{8}$) obtained by
subdividing any edge of $K_{2,4}$ twice. The smallest nonplanar graph in
$\mathcal{G}$ containing an even subdivision of $K_{2,3}$ is a graph on $11$
vertices (denote this by $G_{11}$) obtained as follows. Consider $K_{3,3}$ and
$v\in V(K_{3,3})$. Take two edges adjacent to $v$ and subdivide each of them
twice. Now add a new vertex $u$ and draw an edge between $u$ and $v$. The
graph $G_{11}$ serves as a motivation for our construction using coalescence.
The smallest nonplanar graph, which is not in $\mathcal{G}$ is $K_{3,3}$. See
Figure 2 and 3 for these graphs. Their permanental polynomial and per-spectrum
are as follows.

  * •

$\pi(K_{2,3},x)=x(x^{4}+6x^{2}+12)$,
$\sigma_{p}(K_{2,3})=\\{0,z,\bar{z},iz,i\bar{z}\\}$ where $z=0.79+2.10i$
(approximated to two decimals),

  * •

$\pi(G_{8},x)=x^{2}(x^{6}+10x^{4}+33x^{2}+36)$,
$\sigma_{p}(G_{8})=\\{0,0,\pm 2i,\pm\sqrt{3}i,\pm\sqrt{3}i\\},$

  * •

$\pi(K_{3,3},x)=x^{6}+9x^{4}+36x^{2}+36$,
$\sigma_{p}(K_{3,3})=\\{-1.96i,1.96i,y,\bar{y},iy,i\bar{y}\\}$ where
$y=0.76+2.10i$ (approximated to two decimals),

  * •

$\pi(G_{11},x)=x(x^{10}+14x^{8}+72x^{6}+168x^{4}+172x^{2}+56)$,
$\sigma_{p}(G_{11})=\\{0,\pm i\sqrt{4+\sqrt{2}},\pm i\sqrt{2+\sqrt{2}},\pm
i\sqrt{4-\sqrt{2}},\pm i\sqrt{2},\pm i\sqrt{2-\sqrt{2}}\\}.$

$\mathcal{B}$$\mathcal{P}$$\mathcal{G}$$\mathcal{K}$$K_{2,3}$$G_{8}$$G_{11}$$K_{3,3}$
Figure 2: $\mathcal{B}$: Bipartite Graphs, $\mathcal{P}$: Planar Bipartite
Graphs, $\mathcal{G}$: Graphs with purely imaginary per-spectrum,
$\mathcal{K}$: Graphs without a subgraph which is an even subdivision of
$K_{2,3}$.

Figure 3: (Left to right) $K_{2,4}$, $G_{8}$, $K_{3,3}$ and $G_{11}$. By
subdividing the blue edge twice in $K_{2,4}$ we obtain $G_{8}$. By subdividing
the blue and the red edge twice in $K_{3,3}$, and drawing an edge between
their common vertex and the newly added vertex, we obtain $G_{11}$.

Next, we consider the coalescence of a rooted graph and a rooted tree.

######  Theorem 3.1.

Let $(G_{1},r_{1})$ be a rooted graph and
$(T,r_{2})=\mathcal{R}(T^{\prime(k)},r_{2})$ be a rooted tree. Their
coalescence $G=G_{1}\cdot T$ has purely imaginary per-spectrum if and only if
the polynomial

$\mathcal{H}(G_{1},T):=\pi(G_{1},x)\pi(T^{\prime},x)+k\pi(G_{1}-r_{1},x)\pi(T^{\prime}-u^{\prime},x)$

has purely imaginary roots.

###### Proof.

Applying Lemma 2.8, we get

$\displaystyle\pi(G,x)$
$\displaystyle=\pi(G_{1},x)\pi(T-r_{2},x)+\pi(G_{1}-r_{1},x)\pi(T,x)-x\pi(G_{1}-r_{1},x)\pi(T-r_{2},x)$
$\displaystyle=\pi(G_{1},x)\pi(T-r_{2},x)+\pi(G_{1}-r_{1},x)\left(\pi(T,x)-x\pi(T-r_{2},x)\right)$
$\displaystyle=\pi(G_{1},x)\pi(T^{\prime},x)^{k}+\pi(G_{1}-r_{1},x)\left(k\pi(T^{\prime}-u^{\prime},x)\pi(T^{\prime},x)^{k-1}\right)$
$\displaystyle=\pi(T^{\prime},x)^{k-1}\left(\pi(G_{1},x)\pi(T^{\prime},x)+k\pi(G_{1}-r_{1},x)\pi(T^{\prime}-u^{\prime},x)\right).$

In the third step, we use Proposition 2.6. We already know that a tree has
purely imaginary per-spectrum. Hence, we can ignore the common factor
$\pi(T^{\prime},x)^{k-1}$. ∎

In the remaining section, we take different examples of graph $G_{1}$, in
particular, $K_{2,3}$ rooted at a degree $3$ vertex, $K_{2,3}$ rooted at a
degree $2$ vertex, and a rooted $K_{3,3}$. As for the tree, we take $T$ to be
a rooted starlike or a rooted pathlike tree.

Consider the case when $G_{1}=K_{2,3}$, and $T$ is starlike.

######  Theorem 3.2.

The coalescence of $(K_{2,3},r_{1})$ such that $degree(r_{1})=3$ and rooted
starlike tree $\mathcal{R}(K_{1,l}^{(k)},r_{2})$ has purely imaginary per-
spectrum if and only if any of the following holds:

  1. 1.

$l+k\geq 4$ when $l\leq 3$,

  2. 2.

$k\geq 2l-4$ when $l\geq 4$.

###### Proof.

We have $\pi(K_{2,3},x)=x(x^{4}+6x^{2}+12)$ and
$\pi(K_{1,3},x)=x^{2}(x^{2}+3)$. Now consider the polynomial

$\displaystyle\mathcal{H}(G_{1},T)$
$\displaystyle=\pi(G_{1},x)\pi(T^{\prime},x)+k\pi(G_{1}-r_{1},x)\pi(T^{\prime}-u^{\prime},x)$
$\displaystyle=\pi(K_{2,3},x)\pi(K_{1,l},x)+k\pi(K_{1,3},x)\pi(lK_{1},x)$
$\displaystyle=x(x^{4}+6x^{2}+12)x^{l-1}(x^{2}+l)+kx^{2}(x^{2}+3)x^{l}$
$\displaystyle=x^{l}\left(x^{6}+(l+k+6)x^{4}+(6l+3k+12)x^{2}+12l\right).$

This polynomial has purely imaginary roots if and only if $l+k\geq 4$ when
$l\leq 3$ and $k\geq 2l-4$ when $l\geq 4$.444This is verified using SageMath
software [21]. Proof follows by Theorem 3.1. ∎

######  Example 1.

Let $k=n$ and $l=0$. Then we get a star $T=K_{1,n}$ is rooted at the central
vertex. Let $G_{n}$ be the coalescence of $K_{2,3}$ (rooted at a vertex of
degree $3$) and $K_{1,n}$ (rooted at a vertex of degree $n$), then it has
purely imaginary per-spectrum if and only if $n\geq 4$.

######  Example 2.

Let $k=1$ and $l=n-1$, then we get a star $T=K_{1,n}$ rooted a pendant vertex.
Let $G_{n}$ be the coalescence of $K_{2,3}$ (rooted at a vertex of degree $3$)
and $K_{1,n}$ (rooted at a vertex of degree $1$), then it has purely imaginary
roots if and only if $n=4$.

######  Remark 3.3.

In case when the rooted tree $T=\mathcal{R}(P_{l+1}^{(k)},r_{1})$ is pathlike,
substituting $\pi(T^{\prime},x)=\pi(P_{l+1},x)$ and
$\pi(T^{\prime}-u^{\prime})=\pi(P_{l},x)$, we get

$\mathcal{H}(G_{1},T)=x\left((x^{4}+6x^{2}+12)\pi(P_{l+1},x)+kx(x^{2}+3)\pi(P_{l},x)\right).$

There is no closed form for the set of all pairs $(k,l)$ such that the
polynomial has purely imaginary roots. But the first few $l$’s and the
corresponding $k$’s for which this happens are given as follows.

  1. 1.

$k\geq 4$ when $l=0$,

  2. 2.

$k\geq 3$ when $l=1,2,3,4$,

  3. 3.

$k\geq 13$ when $l=7$.

Next, we make a degree $2$ vertex of $K_{2,3}$ a root.

######  Theorem 3.4.

The coalescence of $(K_{2,3},r_{1})$ such that $degree(r_{1})=2$ with a rooted
starlike tree $\mathcal{R}(K_{1,l}^{(k)},r_{2})$ has purely imaginary per-
spectrum if and only if $l+k\geq 4$ and $l\leq 2$.

###### Proof.

We have $\pi(K_{2,3},x)=x(x^{4}+6x^{2}+12)$ and $\pi(C_{4},x)=(x^{2}+2)^{2}$.
Now consider the polynomial

$\displaystyle\mathcal{H}(G_{1},T)$
$\displaystyle=\pi(G_{1},x)\pi(T^{\prime},x)+k\pi(G_{1}-r_{1},x)\pi(T^{\prime}-u^{\prime},x)$
$\displaystyle=\pi(K_{2,3},x)\pi(K_{1,l},x)+k\pi(C_{4},x)\pi(lK_{1},x)$
$\displaystyle=x(x^{4}+6x^{2}+12)x^{l-1}(x^{2}+l)+k(x^{2}+2)^{2}x^{l}$
$\displaystyle=x^{l}\left(x^{6}+(l+k+6)x^{4}+(6l+4k+12)x^{2}+(12l+4k)\right).$

This polynomial has purely imaginary roots if and only if $l+k\geq 4$ and
$l\leq 2$. Proof follows by Theorem 3.1. ∎

######  Example 3.

Let $k=n$ and $l=0$, then we get a star $K_{1,n}$ rooted at the central
vertex. Let $G_{n}$ be the coalescence of $K_{2,3}$ (rooted at a vertex of
degree $2$) and $K_{1,n}$ (rooted at a vertex of degree $n$). It has purely
imaginary per-spectrum if and only if $n\geq 4$.

######  Remark 3.5.

Similarly, in case when the rooted tree $T=\mathcal{R}(P_{l+1}^{(k)},r_{1})$
is pathlike, we get

$\mathcal{H}(G_{1},T)=x(x^{4}+6x^{2}+12)\pi(P_{l+1},x)+k(x^{2}+2)^{2}\pi(P_{l},x).$

There is no closed form for the set of all pairs $(k,l)$ such that the
polynomial has purely imaginary roots. But the first few $l$’s and the
corresponding $k$’s for which this happens are given as follows.

  1. 1.

$k\geq 4$ when $l=0$,

  2. 2.

$k\geq 3$ when $l=1,2$,

  3. 3.

$k=3$ when $l=3$,

  4. 4.

$k\geq 19$ when $l=5$,

  5. 5.

$k\geq 9$ when $l=6$.

######  Remark 3.6.

The smallest connected bipartite graph in $\mathcal{G}$ which has an even
subdivision of $K_{2,3}$ is the graph $G_{8}$ (see Figure 3), and there are no
other such graphs on $8$ vertices in $\mathcal{G}$. On $9$ vertices, there are
$8$ graphs in $\mathcal{G}$ which contain an even subdivision of $K_{2,3}$
(see Figure 4). Note that $7$ of them can be obtained using the single
coalescence of either $K_{2,3}$ or $\Theta_{3,1,1}$ with a starlike or a
pathlike tree. The remaining example requires coalescences at two different
roots.

The graph $G_{1}$ | Coalescence of $G_{1}$ with rooted tree
---|---
$K_{2,3}$ rooted at a degree $3$ vertex |
$K_{2,3}$ rooted at a degree $2$ vertex |
$\Theta_{3,1,1}$ rooted at a degree $3$ vertex |
$\Theta_{3,1,1}$ rooted at a degree $2$ vertex |
$\Theta_{3,1,1}$ with two root vertices of degree $3$ each |
Figure 4: Connected bipartite graphs on $9$ vertices in $\mathcal{G}$ which
have an even subdivision of $K_{2,3}$ as a subgraph

Next, we consider the case when $G_{1}$ is $K_{3,3}$ to produce nonplanar
graphs with purely imaginary per-spectrum.

######  Theorem 3.7.

The coalescence of $K_{3,3}$ rooted at any vertex with a rooted starlike tree
$T=\mathcal{R}(K_{1,l}^{(k)},r_{2})$ has purely imaginary per-spectrum if and
only if $(k,l)\in\\{(5,1),(6,0),(7,0)\\}$. The coalescence of $K_{3,3}$ rooted
at any vertex with a rooted pathlike tree $T=\mathcal{R}(P_{l+1}^{(k)},r_{2})$
has purely imaginary per-spectrum if and only if
$(k,l)\in\\{(5,1),(6,0),(7,0)\\}$.

###### Proof.

First recall the useful facts $\pi(K_{3,3},x)=x^{6}+9x^{4}+36x^{2}+36$ and
$\pi(K_{2,3},x)=x(x^{4}+6x^{2}+12)$. When the tree is starlike, we have

$\displaystyle\mathcal{H}(G_{1},T)$
$\displaystyle=\pi(G_{1},x)\pi(T^{\prime},x)+k\pi(G_{1}-r_{1},x)\pi(T^{\prime}-u^{\prime},x)$
$\displaystyle=\pi(K_{3,3},x)\pi(K_{1,l},x)+k\pi(K_{2,3},x)\pi(lK_{1},x)$
$\displaystyle=(x^{6}+9x^{4}+36x^{2}+36)x^{l-1}(x^{2}+l)+kx(x^{4}+6x^{2}+12)x^{l}$
$\displaystyle=x^{l-1}\left(x^{8}+(k+l+9)x^{6}+(6k+9l+36)x^{4}+(12k+36l+36)x^{2}+36l\right).$

This polynomial has purely imaginary roots if and only if
$(k,l)\in\\{(5,1),(6,0),(7,0)\\}$. When the tree is pathlike, we have

$\displaystyle\mathcal{H}(G_{1},T)$
$\displaystyle=\pi(G_{1},x)\pi(T^{\prime},x)+k\pi(G_{1}-r_{1},x)\pi(T^{\prime}-u^{\prime},x)$
$\displaystyle=\pi(K_{3,3},x)\pi(P_{l+1},x)+k\pi(K_{2,3},x)\pi(P_{l},x)$
$\displaystyle=(x^{6}+9x^{4}+36x^{2}+36)\pi(P_{l+1},x)+kx(x^{4}+6x^{2}+12)\pi(P_{l},x).$

This polynomial has purely imaginary roots if and only if
$(k,l)\in\\{(5,1),(6,0),(7,0)\\}$. Proof follows by Theorem 3.1. ∎

##  4 Conclusion

There are various ways in which one can make use of the construction idea. The
graph $G_{1}$ in Theorem 3.1 can be taken to be any theta graph with odd
parameters or any graph containing it. One can also consider multiple
coalescences (see [10]) or a different definition of the rooted product (see
neighbourhood rooted product [11]). The second graph $T$ need not be only a
starlike or a pathlike tree. For example, the coalescence of the cycle $C_{6}$
and $K_{2,3}$ (rooted at a degree $3$ vertex) has purely imaginary per-
spectrum, but it is not obtainable using the construction described in this
article. Accounting for such cases is the subject of future study.

## References

  * [1] Manindra Agrawal.  Determinant versus permanent.  In Proceedings of the 25th International Congress of Mathematicians, ICM 2006, volume 3, pages 985–997, 2006.
  * [2] Frank Ban.  Permanent vs. determinant.  2014\.
  * [3] RB Bapat.  Recent developments and open problems in the theory of permanents.  The Mathematics student, 76(1):55, 2007.
  * [4] Mieczyslaw Borowiecki.  On spectrum and per-spectrum of graphs.  Publ. Inst. Math.(Beograd), 38:31–33, 1985.
  * [5] Mieczysław Borowiecki and T Józwiak.  Computing the permanental polynomial of a multigraph.  Discussiones Mathematicae, 5:9–16, 1982.
  * [6] Mieczysław Borowiecki and Tadeusz Jóźwiak.  A note on characteristic and permanental polynomials of multigraphs.  In Graph theory, pages 75–78. Springer, 1983.
  * [7] Andries E Brouwer and Willem H Haemers.  Spectra of graphs.  Springer Science & Business Media, 2011.
  * [8] Radu Curticapean.  A full complexity dichotomy for immanant families.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1770–1783, 2021.
  * [9] Matthias Dehmer, Frank Emmert-Streib, Bo Hu, Yongtang Shi, Monica Stefu, and Shailesh Tripathi.  Highly unique network descriptors based on the roots of the permanental polynomial.  Information Sciences, 408:176–181, 2017.
  * [10] CD Godsil and BD McKay.  A new graph product and its spectrum.  Bulletin of the Australian Mathematical Society, 18(1):21–28, 1978\.
  * [11] Chris D Godsil and Brendan D McKay.  Constructing cospectral graphs.  Aequationes Mathematicae, 25(1):257–268, 1982.
  * [12] Willem H Haemers.  Are almost all graphs determined by their spectrum.  Notices of the South African Mathematical Society, 47:42–45, 2016\.
  * [13] Wei Li.  Graphs whose characteristic and permanental polynomials have coefficients of the same magnitude.  Discrete Mathematics, 339(8):2127–2135, 2016.
  * [14] Wei Li.  On the skew-permanental polynomials of orientation graphs.  Discrete Applied Mathematics, 208:79–87, 2016.
  * [15] Wei Li.  The graphs whose permanental polynomials are symmetric.  Discussiones Mathematicae: Graph Theory, 38(1), 2018.
  * [16] Wei Li.  On the matching and permanental polynomials of graphs.  Discrete Applied Mathematics, 302:16–23, 2021.
  * [17] Wei Li, Shunyi Liu, Tingzeng Wu, and Heping Zhang.  On the permanental polynomials of graphs.  Graph Polynomials, pages 101–121, 2016.
  * [18] Shunyi Liu and Jinjun Ren.  Enumeration of copermanental graphs.  arXiv preprint arXiv:1411.0184, 2014.
  * [19] Allen J Schwenk.  Computing the characteristic polynomial of a graph.  In Graphs and combinatorics, pages 153–172. Springer, 1974.
  * [20] Irene Sciriha and Stanley Fiorini.  On the characteristic polynomial of homeomorphic images of a graph.  Discrete Mathematics, 174(1-3):293–308, 1997.
  * [21] The Sage Developers.  SageMath, the Sage Mathematics Software System (Version 9.7), 2022.  https://www.sagemath.org.
  * [22] Leslie G Valiant.  The complexity of computing the permanent.  Theoretical computer science, 8(2):189–201, 1979.
  * [23] Edwin R Van Dam and Willem H Haemers.  Which graphs are determined by their spectrum?  Linear Algebra and its applications, 373:241–272, 2003.
  * [24] Tingzeng Wu and Hong-Jian Lai.  Constructing graphs which are permanental cospectral and adjacency cospectral.  Graphs and Combinatorics, 34(6):1713–1721, 2018.
  * [25] Weigen Yan and Fuji Zhang.  On the permanental polynomials of some graphs.  Journal of mathematical chemistry, 35(3):175–188, 2004.
  * [26] Fuzhen Zhang.  An update on a few permanent conjectures.  Special Matrices, 4(1), 2016.
  * [27] Heping Zhang and Wei Li.  Computing the permanental polynomials of bipartite graphs by pfaffian orientation.  Discrete Applied Mathematics, 160(13-14):2069–2074, 2012.
  * [28] Heping Zhang, Shunyi Liu, and Wei Li.  A note on the permanental roots of bipartite graphs.  Discussiones Mathematicae: Graph Theory, 34(1), 2014.


#  The reduction of qualitative games

Monica Patriche  University of Bucharest Faculty of Mathematics and Computer
Science 14 Academiei Street 010014 Bucharest, Romania
<EMAIL_ADDRESS>
###### Abstract

We extend the study of the iterated elimination of strictly dominated
strategies (IESDS) from Nash strategic games to a class of qualitative games.
Also in this case, the IESDS process leads us to a kind of rationalizable
result. We define several types of dominance relation and game reduction and
establish conditions under which a unique and nonempty maximal reduction
exists. We generalize, in this way, some results due to Dufwenberg and
Stegeman (2002) and Apt (2007).

###### keywords:

dominance relation, iterated elimination of strictly dominated strategies,
maximal reduction of a game, qualitative games.

##  1 INTRODUCTION

Bernheim [3] and Pearce [16] studied the rationalizable strategic behavior in
the framework of non-cooperative strategic games introduced by Nash [14]. The
rational behavior of the players is a fundamental assumption in Game theory.
It implies that each strategic game can be characterized by a process of
iterated elimination of strictly dominated strategies (IESDS). The result of
this process is known as the maximal reduction of the game.

The iterated elimination of strictly dominated strategies has several
different definitions. We must refer to the approaches of Gilboa, Kalai and
Zemel [9,10], Milgrom and Roberts [13], Marx and Swinkels [12], Ritzberger
[17], Dufwenberg and Stegeman [8], Chen, Long and Luo [5], or Apt [1,2] as
some important ones in the literature. Osborne and Rubinstein [15] and
Rubinstein [18] also developed some topics concerning rationality.

The main problems concerning the IESDS procedure are related to the non-
emptiness and uniqueness of the limit game. In the case of infinite games, the
order of reductions is important, and the maximal reduction may not be unique
if different paths are considered. Dufwenberg and Stegeman [8] proved the
uniqueness and nonemptiness of the maximal reduction for a strategic game with
compact strategy sets and continuous payoff functions. Apt [1] treated the
various definitions of IESDS in a unitary way, specifying the games where the
definitions coincide. His approach is based on complete lattice and the study
of operators.

In order to develop the ideas concerning the rationality, we consider a model
which generalizes the strategic game. We consider the qualitative games which
have, for every player, a strategy set and a preference correspondence
constructed by using the utility functions. Nash’s equilibrium point is seen
in this framework as a maximal element. We also consider different types of
majorized correspondences, which generalize the well-known semicontinuous
ones. So, we work with U-majorized correspondences defined by Yuan and
Tarafdar [20], $Q_{\theta}-$majorized correspondences introduced by Liu and
Cai [11] and LS-majorized correspondences due to G. X. Yuan [19]. We use
theorems which prove the existence of maximal elements for qualitative games
having these types of considered correspondences. These results are due to
Ding [7], Liu and Cai [11], and Chang [4].

Our new approach wants to emphasize that the IESDS process leads to a kind of
${\acute{}}$rationalizable${\acute{}}$ result in the extended games. By
changing the context, we underline the idea of rationality, obtained in an
iterated process of elimination the unfitted strategies. We want to highlight
the concept, rather than the context where it was initially defined. We
introduce several types of dominance relation and game reduction and establish
conditions under which a unique and nonempty maximal reduction exists. In this
way, we generalize, some results due to Dufwenberg and Stegeman [8] and Apt
[1]. On the other hand, the examples of Dufwenberg and Stegeman [8] involve
games with discontinuous utility functions and this fact gives us the idea
that the problem of order independence can be raised for qualitative games,
which can also be generalizations of discontinuous strategic games.

The paper is organized in the following way: Section 2 contains preliminaries
concerning topological properties of correspondences and qualitative games.
The main results are presented in Section 3, after the subsections containing
the introduction of definitions, the problem of game reduction and order
independence and the conditions under which order independence is obtained.
The last subsection is dedicated to proving that the set of maximal elements
is preserved in any game by the process of iterated elimination of strictly
dominated strategies. Concluding remarks are presented at the end.

##  2 PRELIMINARIES AND NOTATIONS

###  2.1 TOPOLOGICAL PROPERTIES OF CORRESPONDENCES

Throughout this paper, we shall use the following notations and definitions:

Let $A$ be a subset of a topological space $X$. 2A denotes the family of all
subsets of $A$. cl $A$ denotes the closure of $A$ in $X$. If $A$ is a subset
of a vector space, co$A$ denotes the convex hull of $A$. If $F$, $T:$
$A\rightarrow 2^{X}$ are correspondences, then co$T$, cl $T$, $T\cap F$ $:$
$A\rightarrow 2^{X}$ are correspondences defined by $($co$T)(x)=$co$T(x)$,
$($cl$T)(x)=$cl$T(x)$ and $(T\cap F)(x)=T(x)\cap F(x)$ for each $x\in A$,
respectively. The graph of $T:X\rightarrow 2^{Y}$ is the set
Gr$(T)=\\{(x,y)\in X\times Y\mid y\in T(x)\\}\vskip 6.0pt plus 2.0pt minus
2.0pt$

We present the notion of a compactly open (compactly closed) set, introduced
by Ding [6].

###### Definition 1

(Ding, [6]) A nonempty subset $D$ of a topological space $X$ is said to be
compactly open (respectively, compactly closed), if for every nonempty compact
subset $C$ of $X$, $D\cap C$ is open (respectively, compactly closed) in $C$.
The compact interior of $D$ is defined by cint$D$ ={$G:G\subseteq D$ and $G$
is compactly open in $X$}. It is easy to see that cint$D$ is a compactly open
set in $X$ and for each nonempty compact subset $C$ of $X$ with $D\cap
C=\emptyset$, we have $($cint$D)\cap C=$int$C(D\cap C),$ where int$C(D\cap C)$
denotes the interior of $D\cap C$ in $C$. It is clear that a subset $D$ of $X$
is compactly open in $X$ if and only if cint$D=D$.

Several classical types of continuity for correspondences are given.

DEFINITION 1. Let $X$, $Y$ be topological spaces and $T:X\rightarrow 2^{Y}$ be
a correspondence

1\. $T$ is said to be upper semicontinuous if, for each $x\in X$ and each open
set $V$ in $Y$ with $T(x)\subset V$, there exists an open neighborhood $U$ of
$x$ in $X$ such that $T(y)\subset V$ for each $y\in U$.

2\. $T$ is said to be lower semicontinuous if, for each x$\in X$ and each open
set $V$ in $Y$ with $T(x)\cap V\neq\emptyset$, there exists an open
neighborhood $U$ of $x$ in $X$ such that $T(y)\cap V\neq\emptyset$ for each
$y\in U$.

3\. $T$ is said to have open lower sections if $T^{-1}(y):=\\{x\in X:y\in
T(x)\\}$ is open in $X$ for each $y\in Y.$

###  2.2 QUALITATIVE GAMES

Let $I$ be a non-empty set (the set of agents). For each $i\in I$, let $G_{i}$
be a non-empty topological vector space representing the set of actions, let
$P_{i}:\mathop{\textstyle\prod}_{i\in I}G_{i}\rightarrow 2^{G_{i}}$ be the
preference correspondence and $u_{i}:\mathop{\textstyle\prod}_{i\in
I}G_{i}\rightarrow\mathbb{R}$ be the utility function.

Notation. For each $i\in I,$ let us denote
$G_{-i}:=\mathop{\textstyle\prod}\nolimits_{j\in I\setminus\\{i\\}}G_{j}.$ If
$x\in\mathop{\textstyle\prod}_{i\in I}G_{i},$ we denote
$x_{-i}=(x_{1},...,x_{i-1},x_{i+1},...)\in G_{-i}.$ If $x_{i}\in G_{i}$ and
$x_{-i}\in G_{-i}$, we shall use the notation
$(x_{i},x_{-i})=(x_{1},...,x_{i-1},x_{i},x_{i+1},...)=x\in\mathop{\textstyle\prod}_{i\in
I}G_{i}.$

###### Definition 2

(Nash, [14]) The family $\Gamma=(G_{i},u_{i})_{i\in I}$ is said to be a
strategic game.

###### Definition 3

(Nash, [14]) An equilibrium for $\Gamma$ is defined as a point
$x^{\ast}\in\mathop{\textstyle\prod}_{i\in I}G_{i}$ such that for each $i\in
I$, $u_{i}(x^{\ast})\geq u_{i}(x_{i},x_{-i}^{\ast})$ for each $x_{i}\in
G_{i}$.

###### Definition 4

The family $G=(G_{i},P_{i})_{i\in I}$ is said to be a qualitative game.

###### Definition 5

A maximal element for $G$ is defined as a point
$x^{\ast}\in\mathop{\textstyle\prod}_{i\in I}G_{i}$ such that for each $i\in
I$, $P_{i}(x^{\ast})=\emptyset$.

A qualitative game $G=(G_{i},P_{i})_{i\in I}$ generalizes a strategic game
$\Gamma=(G_{i},u_{i})_{i\in I}$ by defining

$P_{i}(x)=\\{y_{i}\in G_{i}:u_{i}(y_{i},x_{-i})>u_{i}(x,x_{-i})\\}.$

###### Example 1

Let $\Gamma=(G_{i},u_{i})_{i\in I}$ be a strategic game, $I=\\{1,2\\},$
$G_{1}=G_{2}=[0,1],$ $u_{i}(x_{1},x_{2})=x_{i}$ $i=1,2.$ The point
$x^{\ast}=(1,1)$ is Nash equilibrium.

The qualitative game corresponding to $\Gamma$ is $G=(G_{i},P_{i})_{i\in I},$
where

$P_{1}(x_{1},x_{2})=\\{y_{1}\in[0,1]:u_{1}(y_{1},x_{2})>u_{1}(x_{1},x_{2})\\}=(x_{1},1]$
if $x_{1}\in[0,1)$ and $x_{2}\in[0,1]$ and

$P_{1}(1,x_{2})=\emptyset$ if $x_{2}\in[0,1];$

$P_{2}(x_{1},x_{2})=\\{y_{2}\in[0,1]:u_{2}(x_{1},y_{2})>u_{2}(x_{1},x_{2})\\}=(x_{2},1]$
if $x_{1}\in[0,1]$ and $x_{2}\in[0,1)$ and

$P_{2}(x_{1},1)=\emptyset$ if $x_{1}\in[0,1];$

$(x_{1},x_{2})=(1,1)$ is a maximal element: $P_{1}(1,1)=P_{2}(1,1)=\emptyset.$

Now we define a transitivity type of correspondences.

###### Definition 6

Let $\mathop{\textstyle\prod}_{i\in I}G_{i}$ be a product space and let
$P:\mathop{\textstyle\prod}_{i\in I}G_{i}\rightarrow 2^{G_{i}}$ be a
correspondence. We say that $P$ has the property $T$ if $y_{i}\in P(x)$
implies cl$P(y_{i},x_{-i})\subset P(x).$

###### Example 2

$P_{1}$ and $P_{2}$ from Example 1 have the property $T:$

if $y_{1}\in P_{1}(x),$ then $y_{1}\in(x_{1},1]$ and
cl$P_{1}(y_{1},x_{2})=[y_{1},1]\subset(x_{1},1]$

###### Definition 7

Let $\mathop{\textstyle\prod}_{i\in I}G_{i}$ be a product space and let
$P,Q:\mathop{\textstyle\prod}_{i\in I}G_{i}\rightarrow 2^{G_{i}}$ be
correspondences. We say that the pair $(P,Q)$ has the property $T$ if for each
$x\in\mathop{\textstyle\prod}_{i\in I}G_{i},$ $P(x)\subset Q(x)$ and $y_{i}\in
P(x)$ implies $Q(y_{i},x_{-i})\subset P(x).$

###### Example 3

If we take $Q=$cl$P$ in Example 2, we obtain that the pair $(P,Q)$ has the
property $T.\vskip 6.0pt plus 2.0pt minus 2.0pt$

###### Example 4

Let $P,Q:[0,2]\times[0,2]\rightarrow 2^{[0,2]}$ be defined by

$P(x_{1},x_{2})=\left\\{\begin{array}[]{c}(1,x_{2}]\text{ if
}x_{1}\in[0,1]\text{ and }x_{2}\in(1,2];\\\ \emptyset\text{ otherwise \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }\end{array}\right.$ and

$Q(x_{1},x_{2})=\left\\{\begin{array}[]{c}[x_{1},x_{2}]\text{ if }0\leq
x_{1}<x_{2}\leq 2;\\\ [x_{2},x_{1}]\text{ if }0\leq x_{2}<x_{1}\leq 2;\\\
\\{x_{1}\\}\text{ \ if\ \ }0\leq x_{1}=x_{2}\leq 2.\end{array}\right.$

We have that $P(x_{1},x_{2})\subset Q(x_{1},x_{2})$ for each
$(x_{1},x_{2})\in[0,2]\times[0,2]$ and if $y\in P(x_{1},x_{2}),$ it follows
that $x_{1}\in[0,1]$, $x_{2}\in(1,2]$ and $y\in(1,x_{2}]$ which implies
$Q(y,x_{2})=[y,x_{2}]\subset(1,x_{2}]=P(x_{1},x_{2}).$

We note that $x_{1}\in Q(x_{1},x_{2})$ for each
$(x_{1},x_{2})\in[0,2]\times[0,2]$ and $Q$ has convex closed values, so that
$Q$ verifies the assumptions stated in the hypothesis of the theorems from
Section 3.4

We introduce the following class of games.

Let $I$ be a non-empty set (the set of agents). For each $i\in I$, let $G_{i}$
be a non-empty topological vector space representing the set of actions, and
let $P_{i},Q_{i}:\mathop{\textstyle\prod}_{i\in I}G_{i}\rightarrow 2^{G_{i}}$
be correspondences $(P_{i}$ is the preference correspondence).

###### Definition 8

The family $G=(G_{i},P_{i},Q_{i})_{i\in I}$ is said to be a general
qualitative game with property $T$ if for each $i\in I,$ the pair
$(P_{i},Q_{i})$ satisfies the property $T.$.

###### Definition 9

A maximal element for the general qualitative game $G$ is defined as a point
$x^{\ast}\in\mathop{\textstyle\prod}_{i\in I}G_{i}$ such that for each $i\in
I$, $P_{i}(x^{\ast})=\emptyset$.

##  3 GAME REDUCTION

###  3.1 DEFINITIONS

This subsection gives preliminary definitions on parings and strict dominance
for qualitative games.

We introduce a relation of strict dominance for the qualitative games, which
generalizes the notion of dominance due to Dufwenberg and Stegeman [8].

###### Definition 10

A paring of $G=(G_{i},P_{i})_{i\in I}$ is
$H=(H_{i},P_{i|\mathop{\textstyle\prod}_{i\in I}H_{i}})_{i\in I},$ where
$H_{i}\subseteq G_{i}.$

###### Definition 11

Given a pairing $H$ of $G$, the strict dominance relation $\succ_{H}$ on
$G_{i}$ can be defined$:$

for $x_{i},y_{i}\in G_{i},$ $y_{i}\succ_{H}x_{i}$ if $H_{-i}\neq\emptyset$ and
$y_{i}\in P_{i}(x_{i},x_{-i})$ for each $x_{-i}\in H_{-i},$ which is
equivalent with $H_{-i}\neq\emptyset$ and $y_{i}\in\cap_{x_{-i}\in
H_{-i}}P_{i}(x_{i},x_{-i}).\vskip 6.0pt plus 2.0pt minus 2.0pt$

Let us consider parings $G,H$ with the property that $H_{i}\subseteq G_{i}$
for each $i\in I.$ We generalize, for qualitative games, the types of game
reduction used by Dufwenberg and Stegeman [8], in the following way.

###### Definition 12

i) We define the reduction $G\rightarrow H$ if for each $x_{i}\in
G_{i}\backslash H_{i}$, $\cap_{x_{-i}\in
G_{-i}}P_{i}(x_{i},x_{-i})\neq\emptyset.$

ii) the reduction $G\rightarrow H$ is called fast if $\cap_{x_{-i}\in
G_{-i}}P_{i}(x_{i},x_{-i})\neq\emptyset$ for some $x_{i}\in G_{i}$ implies
$x_{i}\notin H_{i}.$

iii) the reduction $G\rightarrow^{\ast}H$ is defined by the existence of
(finite or countable infinite) sequence of parings $R^{t}$ of $G,$
$t=0,1,2...$, such that $R^{0}=G,$ $R^{t}\rightarrow R^{t+1}$ fast for each
$t\geq 0$ and $H_{i}=\cap_{t}R_{i}^{t}$ for each $i\in I;$

iv) $H$ is said to be a maximal $(\rightarrow^{\ast})$-reduction of $G$ if
$G\rightarrow^{\ast}H$ and $H\rightarrow H^{\prime}$ only for
$H=H^{\prime}.\vskip 6.0pt plus 2.0pt minus 2.0pt$

Now, we consider the iterated elimination of strictly dominated strategies
which involves elimination of strategies that are strictly dominated by a
strategy from the currently considered game $H$ and not the initial game $G.$
We study the reductions of qualitative games in the form below and we
introduce the next definition which generalizes the one of Gilboa, Kalai and
Zemel [9] for qualitative games.

###### Definition 13

We say that $G^{\prime}=(H_{1},...,H_{n},P_{1}^{\prime},...P_{n}^{\prime})$ is
a restriction of a game $G=(G_{1},...G_{n},P_{1},...P_{n})$ if each $H_{i}$ is
a (possibly empty) subset of $X_{i}$ and $P_{i}^{\prime}=(P_{i}\cap
H_{i})_{|\mathop{\textstyle\prod}_{i=1}^{n}H_{i}}.$ If all $H_{i}$ are empty,
we call $H$ an empty restriction.

###### Definition 14

i) We define the reduction $G\Rightarrow H$ if for each $x_{i}\in
G_{i}\backslash H_{i}$, $\cap_{x_{-i}\in H_{-i}}P_{i}(x_{i},x_{-i})\cap
H_{i}\neq\emptyset.$

ii) the reduction $G\Rightarrow H$ is called fast if $\cap_{x_{-i}\in
H_{-i}}P_{i}(x_{i},x_{-i})\cap H_{i}\neq\emptyset$ implies $x_{i}\notin
H_{i}.$

iii) the reduction $G\Rightarrow^{\ast}H$ is defined by the existence of
(finite or countably infinite) sequence of parings $R^{t}$ of $G,$
$t=0,1,2...$, such that $R^{0}=G,$ $R^{t}\rightarrow R^{t+1}$ fast for each
$t\geq 0$ and $H_{i}=\cap_{t}R_{i}^{t}$ for each $i\in I;$

iv) $H$ is said to be a maximal $(\Rightarrow^{\ast})$-reduction of $G$ if
$G\Rightarrow^{\ast}H$ and $H\Rightarrow H^{\prime}$ only for
$H=H^{\prime}.\vskip 6.0pt plus 2.0pt minus 2.0pt$

We further generalize the definition considered by Milgrom and Roberts [13].

###### Definition 15

i) We define the reduction $G\rightarrowtail H$ if for each $x_{i}\in
G_{i}\backslash H_{i}$, $\cap_{x_{-i}\in
H_{-i}}P_{i}(x_{i},x_{-i})\neq\emptyset.$

ii) the reduction $G\rightarrowtail H$ is called fast if $\cap_{x_{-i}\in
H_{-i}}P_{i}(x_{i},x_{-i})\neq\emptyset$ implies $x_{i}\notin H_{i}.$

iii) the reduction $G\rightarrowtail^{\ast}H$ is defined by the existence of
(finite or countable infinite) sequence of parings $R^{t}$ of $G,$
$t=0,1,2...$, such that $R^{0}=G,$ $R^{t}\rightarrowtail R^{t+1}$ fast for
each $t\geq 0$ and $H_{i}=\cap_{t}R_{i}^{t}$ for each $i\in I;$

iv) $H$ is said to be a maximal $(\rightarrowtail^{\ast})$-reduction of $G$ if
$G\rightarrowtail^{\ast}H$ and $H\rightarrowtail H^{\prime}$ only for
$H=H^{\prime}.\vskip 6.0pt plus 2.0pt minus 2.0pt$

We have the following lemma.

###### Lemma 1

If we have $G\rightarrowtail^{\ast}H$ and $G\Rightarrow^{\ast}H^{\prime}$
maximal reductions such that $H_{i},H_{i}^{\prime}\neq\emptyset$ for each
$i\in I,$ then, $H_{i}\subseteq H_{i}^{\prime}$ for each $i\in I.$

Proof. Let us assume that the reduction $G\rightarrowtail^{\ast}H$ is defined
by the existence of (finite or countable infinite) sequence of parings $R^{t}$
of $G,$ $t=0,1,2...$, such that $R^{0}=G,$ $R^{t}\rightarrowtail R^{t+1}$ fast
for each $t\geq 0$ and $H_{i}=\cap_{t}R_{i}^{t}$ for each $i\in I.$ Assume
also that the reduction $G\Rightarrow^{\ast}H^{\prime}$ is defined by the
existence of (finite or countable infinite) sequence of parings $R^{\prime t}$
of $G,$ $t=0,1,2...$, such that $R^{\prime 0}=G,$ $R^{\prime t}\rightarrow
R^{\prime t+1}$ fast for each $t\geq 0$ and
$H_{i}^{\prime}=\cap_{t}R_{i}^{\prime t}$ for each $i\in I.$

Since for each $t,$ the reductions $R^{t}\rightarrowtail R^{t+1}$ and
$R^{\prime t}\rightarrow R^{\prime t+1}$ are fast, then, for each $t,$
$R^{t}\subseteq R^{\prime t}$.

We prove the last assertion by induction. Suppose the claim holds for all
$t\leq T$ and consider the induction step for $T+1.$ Let $i\in I$ be fixed and
let $x_{i}\in R_{i}^{T+1}$. Then, $x_{i}\in R_{i}^{T}\subseteq R_{i}^{\prime
T}$ and $\cap_{x_{-i}\in R_{-i}^{T}}P_{i}(x_{i},x_{-i})=\emptyset.$ Since
$R^{T}\subseteq R^{\prime T},$ we have that $\cap_{x_{-i}\in R_{-i}^{\prime
T}}P_{i}(x_{i},x_{-i})=\emptyset$ and $\cap_{x_{-i}\in R_{-i}^{\prime
T}}P_{i}(x_{i},x_{-i})\cap R_{i}^{\prime T+1}=\emptyset.$ Consequently,
$\cap_{x_{-i}\in R_{-i}^{\prime T+1}}P_{i}(x_{i},x_{-i})\cap R_{i}^{\prime
T+1}=\emptyset.$ Hence, $x_{i}\in R_{i}^{\prime T+1}$ and
$R_{i}^{T+1}\subseteq R_{i}^{\prime T+1}.$

Therefore, $\cap_{t}R_{i}^{t}\subseteq\cap_{t}R_{i}^{\prime t}$ for each $i\in
I$, that is $H_{i}\subseteq H_{i}^{\prime}$ for each $i\in I.$ $\square$

###  3.2 THE PROBLEM OF GAME REDUCTION AND ORDER INDEPENDENCE

We reconsider the iterative processes in which the dominated strategies are
removed and the limit of this process can be an empty or a nonempty set of
strategies. If, for the case of the strategic games, the remained strategies
are the rationalizable ones, it seems that the process itself deserves to be
studied and leads us to a kind of ´rationalizable´ result, also for the case
of generalized games. In order to better understand the problem and motivate
our demarche, we give several examples.

We first consider example 1 due to Dufwenberg and Stegeman [8] and its
generalization.

###### Example 5

Let $I=\\{1,2\\},$ $X_{1}=X_{2}=[0,1],$ $u_{i}:G_{i}\times
G_{j}\rightarrow\mathbb{R},$ where for each $i\in\\{1,2\\},$ $u_{i}$ is
defined in the following way

$u_{i}(x,y)=x$ if $x\in[0,1)$ and $y\in[0,1];$

$u_{i}(1,y)=0$ if $y\in[0,1);$

$u_{i}(1,1)=1$.

Then,

$P_{1}(x,y)=\\{x_{1}\in[0,1]:u_{1}(x_{1},y)>u_{1}(x,y)\\}=(x,1]$ if
$x\in[0,1),$ $y\in[0,1];$

$P_{1}(1,y)=\\{x_{1}\in[0,1]:u_{1}(x_{1},y)>u_{1}(1,y)\\}=[0,1)$ if
$y\in[0,1);$

$P_{1}(1,1)=\\{x_{1}\in[0,1]:u_{1}(x,1)>u_{1}(1,1)\\}=\emptyset.$

$P_{2}(x,y)=\\{y_{1}\in[0,1]:u_{2}(x,y_{2})>u_{2}(x,y)\\}=(y,1]$ if
$y\in[0,1),$ $x\in[0,1];$

$P_{2}(x,1)=\\{y_{2}\in[0,1]:u_{2}(x,y_{2})>u_{2}(x,1)\\}=[0,1)$ if
$x\in[0,1);$

$P_{2}(1,1)=\\{y_{2}\in[0,1]:u_{2}(1,y)>u_{2}(1,1)\\}=\emptyset.$

By eliminating $X_{i}\backslash\\{1,x\\}$ for $i\in\\{1,2\\}$ and $x\in[0,1),$
we have that

$H_{1}=H_{2}=\\{1,x\\}$

$P_{1}(1,1)=\emptyset;$ $P_{1}(1,x)=[0,1);$ $P_{1}(x,1)=(x,1]$ and
$P_{1}(x,x)=(x,1];$

$P_{2}(1,1)=\emptyset;$ $P_{2}(x,1)=[0,1);$ $P_{2}(1,x)=(x,1]$ and
$P_{2}(x,x)=(x,1].$

This game can not be $\rightarrow$ reduced. In this case, since $x$ is
arbitrary, the IESDS procedure is an order dependent one.

###### Example 6

We consider the game from example 2.

If $H_{i}=\\{x_{i}\\}$ $i\in\\{1,2\\},$ then
$P_{1}^{\prime}(x)=P_{1}(x)\cap\\{x_{1}\\}=(x_{1},1]\cap\\{x_{1}\\}=\emptyset;$

$P_{2}^{\prime}(x)=P_{2}(x)\cap\\{x_{2}\\}=(x_{2},1]\cap\\{x_{2}\\}=\emptyset.$

It follows that $(x_{1},x_{2})$ is a maximal element for the
$\Rightarrow^{\ast}$reduced game and that it is not a maximal element for the
initial game.

The example of Dufwenberg and Stegeman [8] involves games with discontinuous
utility functions. These authors let an open problem for researcers to find
classes of games for which order independence holds. As it can be seen in this
subsection, the problem of the existence of nonempty maximal reductions can be
reconsidered for qualitative games, which can also be generalizations of
discontinuous strategic games. The aim of this paper is mainly to generalize
the results obtained by Dufwenberg and Stegeman [8] and Apt [1].

###  3.3 CONDITIONS $C(t)$ AND $D(t)$

Let us consider a game reduction from $G$ to $H$, defined by a finite or
countable infinite sequence of parings $R^{t}$ of $G.$

We generalize the property $C(t)$ proposed by Apt [1]. It refers to the fact
that every strictly dominated strategy on each $R^{t}$ has an undominated
dominator.

###### Definition 16

We call Condition $C(t)$ the following property of the initial game: for all
$i\in I,$

$\forall$ $x_{i}\in G_{i},$ $(\exists$ $y_{i}\in G_{i},$
$y_{i}\succ_{R^{t}}x_{i}\Rightarrow\exists x_{i}^{\ast}\in G_{i}$ $($
$x_{i}^{\ast}\succ_{R^{t}}x_{i}$ $\wedge$ $\nexists$ $y_{i}\in G_{i},$
$y_{i}\succ_{R^{t}}x_{i}^{\ast})$

which is equivalent with

$\forall$ $x_{i}\in G_{i},$ $R_{-i}^{t}\neq\emptyset$ and $\exists$ $y_{i}\in
P_{i}(x_{i},x_{-i})$ $\forall x_{-i}\in R_{-i}^{t}\Rightarrow\exists
x_{i}^{\ast}\in G_{i}$ such that $x_{i}^{\ast}\in P_{i}(x_{i},x_{-i})$
$\forall x_{-i}\in R_{-i}^{t}$ and $\cap_{x_{-i}\in
R_{-i}^{t}}P_{i}(x_{i}^{\ast},x_{-i})=\emptyset.\vskip 6.0pt plus 2.0pt minus
2.0pt$

###### Remark 1

For $H=G,$ we obtain the following:

for all $i\in I,$

$\forall$ $x_{i}\in G_{i},$ $(\exists$ $y_{i}\in G_{i},$
$y_{i}\succ_{G_{i}}x_{i}\Rightarrow\exists x_{i}^{\ast}\in G_{i}$ $($
$x_{i}^{\ast}\succ_{G_{i}}x_{i}$ $\wedge$ $\nexists$ $y_{i}\in G_{i},$
$y_{i}\succ_{G_{i}}x_{i}^{\ast}).\vskip 6.0pt plus 2.0pt minus 2.0pt$

The next property concerns the strict dominance in the reduction $R^{t}.$ It
is also an extension of Condition $D(t)$ considered by Apt [1].

###### Definition 17

Condition $D(t)$ states that each strategy $x_{i}$ strictly dominated in
$R^{t}$ is strictly dominated in $R^{t}$ by some strategy in $R^{t}.$
Formally, we can write that for all $i\in I:$

$\forall$ $x_{i}\in G_{i},$ $(\exists$ $y_{i}\in G_{i},$
$y_{i}\succ_{R^{t}}x_{i}\Rightarrow\exists x_{i}^{\ast}\in R_{i}^{t}$
$x_{i}^{\ast}\succ_{R^{t}}x_{i})$

which is equivalent with

$\forall$ $x_{i}\in G_{i},$ $R_{-i}^{t}\neq\emptyset$ and $\cap_{x_{-i}\in
R_{-i}^{t}}P_{i}(x_{i},x_{-i})\neq\emptyset$ $\Rightarrow\cap_{x_{-i}\in
R_{-i}^{t}}P_{i}(x_{i},x_{-i})\cap R_{i}^{t}\neq\emptyset$.

The next lemma states the relation between the two properties introduced
above.

###### Lemma 2

For each $t,$ the property $C(t)$ implies the property $D(t)$.

Proof. Let us consider $i\in I.$ Assume that $x_{i}\in G_{i},$
$x_{i}^{\prime}\in G_{i},$ $x_{i}^{\prime}\in P_{i}(x_{i},x_{-i})$ $\forall
x_{-i}\in R_{-i}^{t}.$ The Condition $C(t)$ implies that there exists
$x_{i}^{\ast}\in G_{i}$ such that $x_{i}^{\ast}\in P_{i}(x_{i},x_{-i})$
$\forall x_{-i}\in R_{i}^{t}$ and $\cap_{x_{-i}\in
R_{-i}^{t}}P_{i}(x_{i}^{\ast},x_{-i})=\emptyset.$ For each $s\leq t,$
$R_{i}^{t}\subseteq R_{i}^{s},$ then for each $s\leq t,$ $\cap_{x_{-i}\in
R_{-i}^{s}}P_{i}(x_{i}^{\ast},x_{-i})=\emptyset.$ It follows that
$x_{i}^{\ast}$ is a strategy of player $i$ in all restrictions $R^{s}$ for
$s\leq t,$ that is $x_{i}^{\ast}\in\cap_{s\leq t}R_{i}^{s}.$ Hence,
$x_{i}^{\ast}\in R_{i}^{t}$ and we can conclude that $x_{i}^{\ast}\in
P_{i}(x_{i},x_{-i})\cap R_{i}^{t}$ $\forall x_{-i}\in R_{-i}^{t}.$ $\square$

###### Theorem 3

If the property $D(t)$ is fulfilled for each $t$, then a non-empty maximal
$(\rightarrow^{\ast})$ reduction of $G$ is the unique maximal
$(\rightarrow^{\ast})$ reduction of $G,$ if the maximal reduction is defined
by a finite sequence of parings.

Proof. Let $M$ and $M^{\prime}$ be maximal $(\rightarrow^{\ast})-$ reductions
of $G,$ $M$ being nonempty. Let us consider $G\rightarrow^{\ast}M^{\prime}$
and $R^{t},$ $t=0,1,2,...,T_{0}$ be the implied finite sequence of parings. If
$M_{i}\nsubseteq M_{i}^{\prime}$ for some $i,$ it follows that
$M_{i}\nsubseteq R_{i}^{t},$ $\forall t>T$ for the largest $T$ such that
$R_{i}^{T+1}$ is well-defined and $M_{i}\subseteq R_{i}^{T}$ $\forall i\in I.$
Let us take $x_{i}\in M_{i}\backslash R_{i}^{T+1}$ for an $i$ fixed. We have
that $x_{i}\in R_{i}^{T}\backslash R_{i}^{T+1}$, so that there exists
$y_{i}\in R_{i}^{T}$ such that $y_{i}\in\cap_{x_{-i}\in
R_{i}^{T}}P_{i}(x_{i},x_{-i}).$ Since, in addition, $\emptyset\neq
M_{i}\subseteq R_{i}^{T}$ for each $i\in I,$ it follows that
$y_{i}\in\cap_{x_{-i}\in R_{i}^{T}}P_{i}(x_{i},x_{-i}).$ Let $M=R^{T_{0}}.$
According to property $D(T_{0}),$ there exists $z_{i}^{\ast}\in M_{i}$ such
that $z_{i}^{\ast}\in\cap_{x_{-i}\in M_{-i}}P_{i}(x_{i},x_{-i}),$ which
contradicts the fact that $M$ is a maximal $(\rightarrow^{\ast})-$reduction.
It remains that $M_{i}\subseteq M_{i}^{\prime}$ for each $i\in I$ and
therefore $M^{\prime}$ is nonempty. We can prove in the same way that
$M_{i}^{\prime}\subseteq M_{i}$ for each $i\in I,$ implying $M=M^{\prime}.$
$\square$

The next theorem states the relation between $(\rightarrowtail^{\ast})$ and
$(\Rightarrow^{\ast})-$ reductions of a game.

###### Theorem 4

Assume that the reduction $G\rightarrowtail^{\ast}H$ is defined by the
existence of (finite or countable infinite) sequence of parings $R^{t}$ of
$G,$ $t=0,1,2...$, and the reduction $G\Rightarrow^{\ast}H^{\prime}$ is
defined by the existence of (finite or countable infinite) sequence of parings
$R^{\prime t}$ of $G,$ $t=0,1,2...$

Assume that property $\mathit{D(}s)$ holds for each $s<t.$ Then,
$R^{t}=R^{\prime t}.$ In particular, if $\mathit{D(}t)$ holds for each $t,$
then, $H=H^{\prime};$ then, $G$ has a unique
$\mathit{(}\Rightarrow^{\ast})-$maximal reduction, if $G$ has a unique
$(\rightarrowtail^{\ast})-$maximal reduction.

Proof. We will first prove $R_{i}^{\prime t}\subseteq R_{i}^{t}$ by induction.
Suppose that D($s)$ for each $s<t+1.$

Let $x_{i}\in R_{i}^{\prime t+1}.$ Since $R^{\prime t}\rightarrow R^{\prime
t+1}$ is fast, $x_{i}\in R^{\prime t}$ and $\nexists x_{i}^{\prime}\in
R_{i}^{\prime t}$ such that $x_{i}^{\prime}\succ_{R^{\prime t}}x_{i}$.
According to property $D(t),$ $\nexists x_{i}^{\prime}\in G_{i}$ such that
$x_{i}^{\prime}\succ_{R^{\prime t}}x_{i}$. By the induction hypothesis,
$R_{i}^{\prime t}\subseteq R_{i}^{t},$ therefore, $\nexists x_{i}^{\prime}\in
G_{i}$ such that $x_{i}^{\prime}\succ_{R^{t}}x_{i}$ and $x_{i}\in R_{i}^{t}.$
We conclude that $x_{i}$ is a strategy in $R_{i}^{t+1}$ and then,
$R_{i}^{\prime t+1}\subseteq R_{i}^{t+1}.$ We also have from Lemma 1 that
$R_{i}^{t+1}\subseteq R_{i}^{\prime t+1}$ and it follows that
$R_{i}^{t+1}=R_{i}^{\prime t+1}.$ $\square$

###  3.4 THE MAIN RESULTS

We state the results concerning the iterated elimination of strictly dominated
strategies for several classes of qualitative games. The existence and
uniqueness of maximal reductions are proved.

Theorem 4 generalizes Lemma of Dufwenberg and Stegeman [8] by considering
qualitative games with $U-$majorized correspondences defined by Yuan and
Tarafdar. A proof of uniqueness of the maximal reduction of $G$ is given in
this case.

We first present the notion of $U$-majorized correspondence, which generalize
the classical upper semicontinuous correspondences.

###### Definition 18

(Yuan and Tarafdar, [20]). Let $X$ be a topological space and $Y$ be a non-
empty subset of a vector space $E,$ $\theta:X\rightarrow E$ a function and
$\,P:X\rightarrow 2^{Y}$ a correspondence.

1) $P$ is of class $U_{\theta}$ (or $U$) if:

i) for each $x\in X$, $\theta(x)\notin P(x)$ and

ii) $P$ is upper semicontinuous with closed convex values in $Y$;

2) A correspondence $P_{x}:X\rightarrow 2^{Y}$ is a $U_{\theta}$-majorant of
$P$ at $x$ if there exists an open neighborhood $N(x)$ of $x$ such that

i) for each $z\in V(x)$, $P(z)\subset P_{x}(z)$ and $\theta(z)\notin
P_{x}(z);$

ii) $P_{x}$ is upper semicontinuous with closed convex values;

3) $P$ is $U_{\theta}-$majorized if for each $x\in X$ with
$P(x)\neq\emptyset,$ there exists a $U$-majorant $P_{x}$ of $P$ at $x$.

The following theorem is Ding’s result on the existence of maximal elements of
qualitative games. The correspondences are $U-$majorized.

###### Theorem 5

(Ding, [7])Let $X$ be a nonempty subset of a Hausdorff locally convex
topological vector space and $D$ a non-empty compact subset of $X.$ Let
$P:X\rightarrow 2^{D}$ be a $U-$majorized correspondence. Then, there exists
$x^{\ast}\in$co$D$ such that $P(x^{\ast})=\emptyset.\vskip 6.0pt plus 2.0pt
minus 2.0pt$

###### Theorem 6

Let $I$ be a set of players, $G_{i}$ be a compact convex subset of a Hausdorff
locally convex topological vector space $\forall i\in I$ and the general
qualitative game $G=(G_{i},P_{i},Q_{i})_{i\in I}$ which satisfies the property
$T$, where $P_{i},Q_{i}:\mathop{\textstyle\prod}_{i\in I}G_{i}\rightarrow
2^{G_{i}}$ satisfies the following assumptions for each $i\in I:$

i) $y_{i}\in Q_{i}(y_{i},x_{-i})$ for each $x_{-i}\in G_{-i};$

ii) $Q_{i}$ has convex closed values;

iii) $P_{i}(.,x_{-i})$ is $U-$majorized on $G_{i}$ for each $x_{-i}\in
G_{-i}$.

Then,

a) If $G\rightarrow^{\ast}H$ is a game reduction and if there exists
$y_{i}\succ_{H}x_{i},$ for some $x_{i},y_{i}\in G_{i}$ and $i\in I,$ there
exists $x_{i}^{\ast}\in H_{i}$ such that
$z_{i}\nsucc_{H}x_{i}^{\ast}\succ_{H}x_{i}$ $\forall z_{i}\in G_{i};$

b) a non-empty maximal $(\rightarrow^{\ast})$ reduction of $G$ is the unique
maximal $(\rightarrow^{\ast})$ reduction of $G.$

Proof. a) Let $R^{t}$ be the sequence of parings of $G,$ $t=0,1,2...$, such
that $R^{0}=G,$ $R^{t}\rightarrow R^{t+1}$ for each $t\geq 0$ and
$H_{i}=\cap_{t}R_{i}^{t}$ for each $i\in I.$ Assume that there exists
$y_{i}\succ_{H}x_{i}.$ Let $Z_{i}=\cap_{x_{-i}\in H_{-i}}Q(y_{i},x_{-i}).$
According to i), we have that $Z_{i}\neq\emptyset.$ The set $Z_{i}$ is convex
and closed, so it is compact. Since $y_{i}\succ_{H}x_{i},$ we have that
$H_{-i}\neq\emptyset.$ Let $x_{-i}^{\ast}\in H_{-i}$ be fixed and
$F_{i}:Z_{i}\times\\{x_{-i}^{\ast}\\}\rightarrow 2^{Z_{i}},$
$F_{i}=P_{i|Z_{i}\times\\{x_{-i}^{\ast}\\}}.$ According to Ding’s Theorem,
there exists $x_{i}^{\ast}\in Z_{i}$ such that
$P_{i}(x_{i}^{\ast},x_{-i}^{\ast})=\emptyset.$

We have that $x_{i}^{\ast}\in Q_{i}(y_{i},x_{-i})$ for each $x_{-i}\in
H_{-i}$. The relation $y_{i}\succ_{H}x_{i}$ implies that $y_{i}\in
P_{i}(x_{i},x_{-i})$ $\forall x_{-i}\in H_{-i}$ and since the pair
$(P_{i},Q_{i})$ has the property $T$ on $\mathop{\textstyle\prod}_{i\in
I}H_{i}$, it follows that $x_{i}^{\ast}\in P_{i}(x_{i},x_{-i})$ $\forall
x_{-i}\in H_{-i}.$

If there exists $z_{i}\in P_{i}(x_{i}^{\ast},x_{-i})\subset
Q_{i}(x_{i}^{\ast},x_{-i})$ $\forall x_{-i}\in H_{-i},$ then $z_{i}\in Z_{i}$
and $z_{i}\in P_{i}(x_{i}^{\ast},x_{-i}^{\ast}),$ which is a contradiction.

Since $H_{-i}\subseteq R_{-i}^{t},$ $\cap_{x_{-i}\in
H_{-i}}P(x_{i}^{\ast},x_{-i})=\emptyset$ and then, $\cap_{x_{-i}\in
R_{-i}^{t}}P(x_{i}^{\ast},x_{-i})=\emptyset.$ We conclude that
$x_{i}^{\ast}\in R_{i}^{t}$ $\forall t\geq 0$ and $x_{i}^{\ast}\in H_{i}.$

b) Let $M$ and $M^{\prime}$ be maximal $(\rightarrow^{\ast})-$ reductions of
$G,$ $M$ being nonempty. Let us consider $G\rightarrow^{\ast}M^{\prime}$ and
$R^{t},$ t=0,1,2…, be the implied finite or infinite sequence of parings. If
$M_{i}\nsubseteq M_{i}^{\prime}$ for some $i,$ it follows that
$M_{i}\nsubseteq R_{i}^{t},$ $\forall t>T$ for the largest $T$ such that
$R_{i}^{T+1}$ is well-defined and $M_{i}\subseteq R_{i}^{T}$ $\forall i\in I.$
Let us take $x_{i}\in M_{i}\backslash R_{i}^{T+1}$ for an $i$ fixed. We have
that $x_{i}\in R_{i}^{T}\backslash R_{i}^{T+1}$, so that there exists
$y_{i}\in R_{i}^{T}$ such that $y_{i}\in\cap_{x_{-i}\in
R_{-i}^{T}}P_{i}(x_{i},x_{-i}).$ Since, in addition, $\emptyset\neq
M_{i}\subseteq R_{i}^{T}$ for each $i\in I,$ it follows that
$y_{i}\in\cap_{x_{-i}\in M_{-i}}P_{i}(x_{i},x_{-i}).$ According to i) there
exists $z_{i}^{\ast}\in M_{i}$ such that $z_{i}^{\ast}\in\cap_{x_{-i}\in
M_{-i}}P_{i}(x_{i},x_{-i}),$ which contradicts the fact that $M$ is a maximal
$(\rightarrow^{\ast})-$reduction. It remains that $M_{i}\subseteq
M_{i}^{\prime}$ for each $i\in I$ and therefore $M^{\prime}$ is nonempty. We
can prove that $M_{i}^{\prime}\subseteq M_{i}$ for each $i\in I,$ implying
$M=M^{\prime}.$ $\square\vskip 6.0pt plus 2.0pt minus 2.0pt$

We obtain the following corollary for qualitative games having upper
semicontinuous correspondences $P_{i},$ $i\in I.$

###### Corollary 7

Let $I$ be a set of players, $G_{i}$ be a compact convex subset of a Hausdorff
locally convex topological vector space $\forall i\in I$ and the general
qualitative game $G=(G_{i},P_{i},Q_{i})_{i\in I}$ which satisfies the property
$T$, where $P_{i},Q_{i}:\mathop{\textstyle\prod}_{i\in I}G_{i}\rightarrow
2^{G_{i}}$ satisfies the following assumptions for each $i\in I:$

i) $y_{i}\in Q_{i}(y_{i},x_{-i})$ for each $x_{-i}\in G_{-i};$

ii) $Q_{i}$ has convex closed values;

iii) for each $x\in G_{i}$, $x_{i}\notin P_{i}(x)$ and

iv) $P_{i}$ is upper semicontinuous with closed convex values in $G_{i}$;

Then,

a) If $G\rightarrow^{\ast}H$ is a game reduction and if there exists
$y_{i}\succ_{H}x_{i},$ for some $x_{i},y_{i}\in G_{i}$ and $i\in I,$ there
exists $x_{i}^{\ast}\in H_{i}$ such that
$z_{i}\nsucc_{H}x_{i}^{\ast}\succ_{H}x_{i}$ $\forall z_{i}\in G_{i};$

b) a non-empty maximal $(\rightarrow^{\ast})$ reduction of $G$ is the unique
maximal $(\rightarrow^{\ast})$ reduction of $G.$

Liu and Cai [11] defined the correspondences of class $Q$ and the
$Q$-majorized correspondences.

###### Definition 19

(Liu and Cai, [11]) Let $X$ be a topological space and $Y$ be a non-empty
subset of a vector space $E$, $\theta:X\rightarrow E$ a function and
$\,P:X\rightarrow 2^{Y}$ a correspondence.

1) $P$ is of class $Q_{\theta}$ (or $Q$) if:

i) for each $x\in X$, $\theta(x)\notin$cl$P(x)$ and

ii) $P$ is lower semicontinuous with open and convex values in $Y$;

2) A correspondence $P_{x}:X\rightarrow 2^{Y}$ is a $Q_{\theta}$-majorant of
$P$ at $x,$ if there exists an open neighborhood $N(x)$ of $x$ such that:

i) for each $z\in N(x)$, $P(z)\subset P_{x}(z)$ and
$\theta(z)\notin$cl$P_{x}(z);$

ii) $P_{x}$ is lower semicontinuous with open convex values;

3) $P$ is $Q_{\theta}$-majorized if for each $x\in X$ with
$P(x)\neq\emptyset,$ there exists a $Q_{\theta}$-majorant $P_{x}$ of $P$ at
$x$.

The next result is also due to Liu and Cai and states the maximal element
existence for qualitative games with $Q_{\theta}-$majorized correspondences.

###### Theorem 8

(Liu, Cai, [11]). Let $X$ be a convex paracompact subset of a locally convex
Hausdorff topological vector space $E,$ let $D$ be a nonempty compact
metrizable subset of $X.$ Let $P:X\rightarrow 2^{D}$ be a
$Q_{\theta}-$majorized correspondence. Then, there exists $x^{\ast}\in X$ such
that $P(x^{\ast})=\emptyset.\vskip 6.0pt plus 2.0pt minus 2.0pt$

Theorem 6 concerns the games with $Q_{\theta}-$majorized correspondences.

###### Theorem 9

Let $I$ be a set of players, $G_{i}$ be a compact convex subset of a Hausdorff
locally convex topological vector space $\forall i\in I$ and the general
qualitative game $G=(G_{i},P_{i},Q_{i})_{i\in I}$ which satisfies the property
$T$, where $P_{i},Q_{i}:\mathop{\textstyle\prod}_{i\in I}G_{i}\rightarrow
2^{G_{i}}$ satisfy the following assumptions for each $i\in I:$

i) $y_{i}\in Q_{i}(y_{i},x_{-i})$ for each $x_{-i}\in G_{-i};$

ii) $Q_{i}$ has convex closed values;

iii) $P_{i}(.,x_{-i})$ is $Q_{\theta}-$majorized on $G_{i}$ for each
$x_{-i}\in G_{-i}$.

Then,

a) If $G\rightarrow^{\ast}H$ is a a game reduction and if there exists
$y_{i}\succ_{H}x_{i},$ for some $x_{i},y_{i}\in G_{i}$ and $i\in I,$ there
exists $x_{i}^{\ast}\in H_{i}$ such that
$z_{i}\nsucc_{H}x_{i}^{\ast}\succ_{H}x_{i}$ $\forall z_{i}\in G_{i};$

b) a non-empty maximal $\rightarrow^{\ast}$reduction of $G$ is the unique
maximal reduction of $G.\vskip 6.0pt plus 2.0pt minus 2.0pt$

Since a correspondence of class $Q$ is $Q$-majorized, we obtain the following
corollary.

###### Corollary 10

Let $I$ be a set of players, $G_{i}$ be a compact convex subset of a Hausdorff
locally convex topological vector space $\forall i\in I$ and the general
qualitative game $G=(G_{i},P_{i},Q_{i})_{i\in I}$ which satisfies the property
$T$, where $P_{i},Q_{i}:\mathop{\textstyle\prod}_{i\in I}G_{i}\rightarrow
2^{G_{i}}$ satisfy the following assumptions for each $i\in I:$

i) $y_{i}\in Q_{i}(y_{i},x_{-i})$ for each $x_{-i}\in G_{-i};$

ii) $Q_{i}$ has convex closed values;

iii) for each $x_{i}\in G_{i}$, $x_{i}\notin$cl$P_{i}(x)$ and

iv) $P_{i}$ is lower semicontinuous with open and convex values in $G_{i}$;

Then,

a) If $G\rightarrow^{\ast}H$ is a a game reduction and if there exists
$y_{i}\succ_{H}x_{i},$ for some $x_{i},y_{i}\in G_{i}$ and $i\in I,$ there
exists $x_{i}^{\ast}\in H_{i}$ such that
$z_{i}\nsucc_{H}x_{i}^{\ast}\succ_{H}x_{i}$ $\forall z_{i}\in G_{i};$

b) a non-empty maximal $\rightarrow^{\ast}$reduction of $G$ is the unique
maximal reduction of $G.\vskip 6.0pt plus 2.0pt minus 2.0pt$

We present here the notion of $L_{S}-$majorized correspondence.

Let $X$ be a topological space and $I$ be an index set. For each $i\in I,$ let
$Y_{i}$ be a non-empty convex subset of a topological vector space $E_{i}.$
Let $Y=\mathop{\textstyle\prod}\limits_{i\in I}Y_{i}$ and $S:Y\rightarrow X$
be a function. For each $i\in I,$ let $P_{i}:X\rightarrow 2^{Y_{i}}$ be a
correspondence.

###### Definition 20

(Yuan, [19]). $P_{i}$ is said to be:

1) of class $L_{S}$ if:

i) $P_{i}$ has convex values;

ii) $y_{i}\notin P_{i}(S(y))$ for each $y\in Y$, and

iii) $P_{i}^{-1}(y_{i})=\\{x\in X:y_{i}\in P_{i}(x)\\}$ is open in $X$ for
each $y_{i}\in Y_{i}.$

2) $L_{S}$-majorized if for each $x\in X,$ there exists an open neighborhood
$N(x)$ of $x$ in $X$ and a correspondence with convex values
$B_{x}:X\rightarrow 2^{Y_{i}}$ such that:

i) $P_{i}(z)\subset B_{x}(z)$ for each $z\in N(x);$

ii) $y_{i}\notin B_{x}(S(y))$ for each $y\in Y$ and

iii) $B_{x}^{-1}(y_{i})$ is open in $X$ for each $y_{i}\in Y_{i}.\vskip 6.0pt
plus 2.0pt minus 2.0pt$

We also have the following theorem due to Chang [4] on non-compact spaces.

###### Theorem 11

(Chang, [4]) Let $X$ be a convex subset of a Hausdorff topological vector
space $E$ and let $P:X\rightarrow 2^{X}$ be a $L_{S}-$majorized
correspondence. Suppose that there exists a compact set $D$ in $X$ such that,
for each finite subset $S$ of $X,$ there exists a convex compact set $K,$
which contains $S$ and which satisfies $K\backslash\cup_{x\in
K}P^{-1}(x)\subset D.$ Then, there exists $x^{\ast}\in D$ such that
$P(x^{\ast})=\emptyset.\vskip 6.0pt plus 2.0pt minus 2.0pt$

The following result is a consequence of Chang’s Theorem.

###### Theorem 12

Let $I$ be a set of players, $G_{i}$ be a compact convex subset of a Hausdorff
locally convex topological vector space $\forall i\in I$ and the general
qualitative game $G=(G_{i},P_{i},Q_{i})_{i\in I},$ which satisfies the
property $T,$ where $P_{i},Q_{i}:\mathop{\textstyle\prod}_{i\in
I}G_{i}\rightarrow 2^{G_{i}}$ satisfy the following assumptions for each $i\in
I:$

i) $y_{i}\in Q_{i}(y_{i},x_{-i})$ for each $x_{-i}\in G_{-i};$

ii) $Q_{i}$ has convex closed values;

iii) $P_{i}(.,x_{-i})$ is $L_{S}-$majorized on $G_{i}$ for each $x_{-i}\in
G_{-i}$.

Then,

a) If $G\rightarrow^{\ast}H$ is a a game reduction and if there exists
$y_{i}\succ_{H}x_{i},$ for some $x_{i},y_{i}\in G_{i}$ and $i\in I,$ there
exists $x_{i}^{\ast}\in H_{i}$ such that
$z_{i}\nsucc_{H}x_{i}^{\ast}\succ_{H}x_{i}$ $\forall z_{i}\in G_{i};$

b) a non-empty maximal $\rightarrow^{\ast}$reduction of $G$ is the unique
maximal reduction of $G.\vskip 6.0pt plus 2.0pt minus 2.0pt$

Since a correspondence of class $L$ is $L_{S}$-majorized, we obtain the
following corollary.

###### Corollary 13

Let $I$ be a set of players, $G_{i}$ be a compact convex subset of a Hausdorff
locally convex topological vector space $\forall i\in I$ and the general
qualitative game $G=(G_{i},P_{i},Q_{i})_{i\in I},$ which satisfies the
property $T,$ where $P_{i},Q_{i}:\mathop{\textstyle\prod}_{i\in
I}G_{i}\rightarrow 2^{G_{i}}$ satisfy the following assumptions for each $i\in
I:$

i) $y_{i}\in Q_{i}(y_{i},x_{-i})$ for each $x_{-i}\in G_{-i};$

ii) $Q_{i}$ has convex closed values;

iii) $P_{i}$ has convex values;

iv) $x_{i}\notin P_{i}(x)$ for each $x\in\mathop{\textstyle\prod}_{i\in
I}G_{i}$;

v) $P_{i}^{-1}(y_{i})=\\{x\in\mathop{\textstyle\prod}_{i\in I}G_{i}:y_{i}\in
P_{i}(x)\\}$ is open in $\mathop{\textstyle\prod}_{i\in I}G_{i}$ for each
$y_{i}\in G_{i}.$

Then,

a) If $G\rightarrow^{\ast}H$ is a a game reduction and if there exists
$y_{i}\succ_{H}x_{i},$ for some $x_{i},y_{i}\in G_{i}$ and $i\in I,$ there
exists $x_{i}^{\ast}\in H_{i}$ such that
$z_{i}\nsucc_{H}x_{i}^{\ast}\succ_{H}x_{i}$ $\forall z_{i}\in G_{i};$

b) a non-empty maximal $\rightarrow^{\ast}$reduction of $G$ is the unique
maximal reduction of $G.\vskip 6.0pt plus 2.0pt minus 2.0pt$

###### Remark 2

For $H=G,$ we obtain that under the conditions of Corollary 3, we have the
following:

if there exists $y_{i}\succ_{G}x_{i},$ for some $x_{i},y_{i}\in G_{i}$ and
$i\in I,$ there exists $x_{i}^{\ast}\in G_{i}$ such that
$z_{i}\nsucc_{G}x_{i}^{\ast}\succ_{G}x_{i}$ $\forall z_{i}\in G_{i};\vskip
6.0pt plus 2.0pt minus 2.0pt$

The next theorem is a generalization of Theorem 1 of Dufwenberg and Stegeman
[8] for the class of qualitative games.

###### Theorem 14

Let $G=(G_{i},P_{i},Q_{i})_{i\in I}$ be a general qualitative game, where for
each $i\in I,$ $G_{i}$ is a non-empty compact subset of a Hausdorff
topological vector space and $P_{i}:\mathop{\textstyle\prod}_{i\in I}G_{i}$
such that:

i) $P_{i}$ has compactly open lower sections and convex values;

ii) $x_{i}\notin P_{i}(x)$ $\forall x\in\mathop{\textstyle\prod}_{i\in
I}G_{i};$

iii) $y_{i}\in Q_{i}(y_{i},x_{-i})$ for each $x_{-i}\in G_{-i};$

iv) $Q_{i}$ has convex closed values;

Then, $G$ has a unique maximal $\rightarrow^{\ast}$reduction $M.$ Further,
$\forall i\in I,$ $M_{i}$ is nonempty, compact and $P_{i|M}$ has compactly
open lower sections.

Proof. We will prove further that $G$ has a nonempty maximal reduction.The
proof of its uniqueness is a consequence of Corollary 3.

1) We first establish that if $G\rightarrow H$ is fast and $H$ is compact,
$H_{i}$ is compact and nonempty. Choose $i$ such that $H_{i}\neq G_{i}.$ Then,
$y_{i}\succ_{G}x$ for some $x,y\in G_{i}$ and then the set $H_{i}$ is
nonempty.

We will prove that $H_{i}$ is compact. Let $y_{i}\in H_{i}$ and
$Z(y_{i})=C_{X}P_{i}^{-1}(y_{i}),$ where $X=\mathop{\textstyle\prod}_{i\in
I}G_{i}.$ According to the assumption ii), $Z(y_{i})\neq\emptyset$ and
according to i), $Z(y_{i})$ is closed in the compact set
$\mathop{\textstyle\prod}_{i\in I}G_{i},$ and therefore it is compact.

Define $Z_{i}(y_{i}):=$pr${}_{i}Z(y_{i}).$ We have that $Z(y_{i})$ is a non-
empty closed set in $G_{i}$ with $y_{i}\in Z_{i}(y_{i}).$

Now, we prove that $H_{i}=\cap_{y_{i}\in H_{i}}Z_{i}(y_{i}).$ In order to show
that $H_{i}\subseteq\cap_{y_{i}\in H_{i}}Z_{i}(y_{i}),$ we consider $z_{i}\in
G_{i}.$ If for every $y_{i}\in H_{i},$ $z_{i}\notin Z(y_{i}),$ it follows that
$y_{i}\in P_{i}(z_{i},x_{-i})$ $\forall x_{-i}\in G_{-i},$ then $z_{i}\notin
H_{i}$ and therefore $C_{G_{i}}(\cap_{y_{i}\in H_{i}}Z_{i}(y_{i}))\subset
C_{G_{i}}H_{i},$ which implies $H_{i}\subseteq\cap_{y_{i}\in
H_{i}}Z_{i}(y_{i}).$ Now, we want to show that $\cap_{y_{i}\in
H_{i}}Z_{i}(y_{i})\subset H_{i},$ that is $C_{G_{i}}H_{i}\subseteq
C_{G_{i}}(\cap_{y_{i}\in H_{i}}Z_{i}(y_{i})).$

If $z_{i}\notin H_{i},$ then there exists $x_{i}\in G_{i}$ such that $x_{i}\in
P_{i}(z_{i},x_{-i})$ $\forall x_{-i}\in G_{-i}.$

According to Remark 2, there exists $x_{i}^{\ast}\in G_{i}$ such that
$x_{i}^{\ast}\in P_{i}(z_{i},x_{-i})$ $\forall x_{-i}\in G_{-i}.$ It follows
that $z_{i}\notin Z_{i}(x_{i}^{\ast}),$ therefore $z_{i}\notin\cap_{y_{i}\in
X_{i}}Z_{i}(y_{i}),$ and, hence, $C_{G_{i}}H_{i}\subseteq
C_{G_{i}}(\cap_{y_{i}\in H_{i}}Z_{i}(y_{i})).$ Since $H_{i}=\cap_{y_{i}\in
Y_{i}}Z_{i}(y_{i}),$ $H_{i}$ is closed in $G_{i}$ and compact.

2) Let $R^{t},$ $t=0,1,...$ denote the unique sequence of games of $G$ such
that $R^{0}=G$ and $R^{t}\rightarrow R^{t+1}$ is fast $\forall t.$ Result 1
implies that $R^{t}$ is compact and nonempty $\forall t,$ so that
$M_{i}=\cap_{t}R_{i}^{t}$ is compact and nonempty. According to i), it follows
that $P_{i}^{-1}(y_{i})$ is open in $M_{i}.$ We still have to show that $M$ is
a maximal $\rightarrow^{\ast}$reduction of $G.$

Let’s consider $i\in I$ and $x_{i}\in M_{i}.$ We will prove that $x_{i}$ is
not dominated by any $y_{i}\in M_{i}$. Let $y_{i}\in M_{i},$and let
$A=C_{X_{-i}}B,$ where $B=\\{x_{-i}\in G_{-i}:y_{i}\in
P_{i}(x_{i},x_{-i})\\}.$ Then $A=C_{X_{-i}}\\{x_{-i}\in
X_{-i}:(x_{i},x_{-i})\in P_{i}^{-1}(y_{i})\\}.$

If $A\cap R_{-i}^{t}=\emptyset$ for every $t$ such that $R^{t}\neq M,$ then
$y_{i}\in P_{i}(x_{i},x_{-i})$ for each $x_{-i}\in R_{-i}^{t},$ that is
$y_{i}\succ_{R^{t}}x_{i}$ , which contradicts $x_{i}\in M_{i}.$ Therefore
$A\cap R_{-i}^{t}$ is nonempty and compact for every $t,$ such that $R^{t}\neq
M.$ This fact implies $A\cap M_{-i}$ is nonempty and then, $y_{i}\notin
P_{i}(x_{i},x_{-i})$ $\forall x_{-i}\in M_{-i},$ that is
$y_{i}\nsucc_{M}x_{i}.$ $\square$

###  3.5 MAXIMAL ELEMENTS FOR QUALITATIVE GAMES

This subsection is meant to prove that the set of maximal elements is
preserved in any game by the process of iterated elimination of strictly
dominated strategies.

###### Theorem 15

Let $G=(G_{i},P_{i},Q_{i})_{i\in I}$ be a general qualitative game which
satisfies property $T$ and $x_{i}\notin P_{i}(x_{i},x_{-i})$ for each
$x_{-i}\in\mathop{\textstyle\prod}_{i\in I}G_{i}.$ Let us assume that for each
$x\in\mathop{\textstyle\prod}_{i\in I}G_{i},$ there exists
$z^{\ast}\in\mathop{\textstyle\prod}_{i\in I}G_{i}$ such that $z_{i}^{\ast}\in
Q_{i}(z_{i},x_{-i})$ for all $z\in\mathop{\textstyle\prod}_{i\in I}G_{i}$ and
$i\in I.$ If $H$ is a $(\Rightarrow^{\ast})-$reduction of $G,$ then games $G$
and $H$ have the same maximal elements.

Proof. Let $R^{t},$ $t=0,1,...$ denote the unique sequence of games of $G$
such that $R^{0}=G,$ $R^{t}\Rightarrow R^{t+1}$ is fast $\forall t$ and
$H_{i}=\cap_{t}R_{i}^{t}$ for each $i\in I.$ Suppose that
$x^{\ast}\in\mathop{\textstyle\prod}_{i\in I}G_{i}$ is a maximal element in
the game $G,$ that is $P_{i}(x^{\ast})=\emptyset$ and then, $x_{i}^{\ast}$ is
never eliminated in the sequence $R^{t}$ $\forall i\in I.$ It follows that
$x^{\ast}\in\mathop{\textstyle\prod}_{i\in I}H_{i},$ so that
$P_{i|\mathop{\textstyle\prod}_{i\in I}H_{i}}(x^{\ast})=\emptyset$ and,
therefore, $P_{i|\mathop{\textstyle\prod}_{i\in I}H_{i}}(x^{\ast})\cap
H_{i}=\emptyset$ and $x$ is also a maximal element in game $H.$

Conversely, let $x^{\ast}\in\mathop{\textstyle\prod}_{i\in I}H_{i}$ be a
maximal element in game $H$ $(P_{i}(x^{\ast})\cap H_{i}=\emptyset$ for each
$i\in I)$ and consider $z^{\ast}$ as in the hypothesis:
$z^{\ast}\in\mathop{\textstyle\prod}_{i\in I}G_{i}$ such that $z_{i}^{\ast}\in
Q_{i}(z,x_{-i}^{\ast})$ for all $z\in\mathop{\textstyle\prod}_{i\in I}G_{i}.$
We will prove that $P_{i}(z_{i}^{\ast},x_{-i}^{\ast})=\emptyset.$ If we
assume, on the contrary, that there exists $x_{i}^{\prime}\in
P_{i}(z_{i}^{\ast},x_{-i}^{\ast}),$ it follows, according to property T,
$Q_{i}(x_{i}^{\prime},x_{-i}^{\ast})\subset
P_{i}(z_{i}^{\ast},x_{-i}^{\ast}).$ However, $z_{i}^{\ast}\in
Q_{i}(z,x_{-i}^{\ast})$ for all $z\in\mathop{\textstyle\prod}_{i\in I}G_{i},$
particularly $z_{i}^{\ast}\in Q_{i}(x_{i}^{\prime},x_{-i}^{\ast})$and then,
$z_{i}^{\ast}\in P_{i}(z_{i}^{\ast},x_{-i}^{\ast}),$ which contradicts the
hypothesis. Since $P_{i}(z_{i}^{\ast},x_{-i}^{\ast})=\emptyset,$
$z_{i}^{\ast}$ is never eliminated in the sequence $R^{t}$ $\forall i\in I,$
and $z^{\ast}\in\mathop{\textstyle\prod}_{i\in I}H_{i}.$ The last assertion
implies $z_{i}^{\ast}\in Q_{i}(z_{i},x_{-i}^{\ast})\cap H_{i}$ for all
$z\in\mathop{\textstyle\prod}_{i\in I}G_{i}.$ We will prove that
$P_{i}(x^{\ast})=\emptyset.$ Let us assume, on the contrary, that there exists
$x^{\prime}\in\mathop{\textstyle\prod}_{i\in I}G_{i}$ such that
$x_{i}^{\prime}\in P_{i}(x^{\ast})$ for each $i\in I.$ Then, according to
Property $T,$ we have that $Q_{i}(x_{i}^{\prime},x_{-i}^{\ast})\subset
P_{i}(x^{\ast}).$ However, we have that $z_{i}^{\ast}\in
Q_{i}(x_{i}^{\prime},x_{-i})$ from hypothesis, so that $z_{i}^{\ast}\in
P_{i}(x^{\ast}).$ In addition, $z_{i}^{\ast}\in H_{i}$ and, then,
$z_{i}^{\ast}\in P_{i}(x^{\ast})\cap H_{i},$ which contradicts the fact that
$P_{i}(x^{\ast})\cap H_{i}=\emptyset.$ In conclusion, $P_{i}(x^{\ast})$ must
be the empty set and $x^{\ast}$ is a maximal element for game $G.$
$\square\vskip 6.0pt plus 2.0pt minus 2.0pt$

For the $(\rightarrow^{\ast})-$reductions of a game, we obtain the following
corollary.

###### Corollary 16

Let $G=(G_{i},P_{i},Q_{i})_{i\in I}$ be a general qualitative game which
satisfies property $T$ and $x_{i}\notin P_{i}(x_{i},x_{-i})$ for each
$x_{-i}\in\mathop{\textstyle\prod}_{i\in I}G_{i}.$ Let us assume that for each
$x\in\mathop{\textstyle\prod}_{i\in I}G_{i},$ there exists
$z^{\ast}\in\mathop{\textstyle\prod}_{i\in I}G_{i}$ such that $z_{i}^{\ast}\in
Q_{i}(z_{i},x_{-i})$ for all $z\in\mathop{\textstyle\prod}_{i\in I}G_{i}$ and
$i\in I.$ If $H$ is a $(\rightarrow^{\ast})-$reduction of $G,$ then games $G$
and $H$ have the same maximal elements.

##  4 CONCLUDING REMARKS

Dufwenberg and Stegeman [8] let an open problem for researchers, that is to
find classes of games for which order independence holds. We reconsidered the
problem of the existence of nonempty maximal reductions for qualitative games,
which can be generalizations of discontinuous strategic games. We generalized
the results obtained by Dufwenberg and Stegeman [8] and Apt [1].

## References

  * [1] K. Apt, The Many Faces of Rationalizability, The B.E. Journal of Theoretical Economics, 7(1), (2007), Article 18, 38 pages.
  * [2] K. Apt, Order Independence and Rationalizability, Proc. of the 10th conference on Theoretical Aspects of Rationality and Knowledge (TARK X), pp. 22-38 (2005)
  * [3] B. D. Bernheim, Rationalizable strategic behavior, Econometrica (1984), 52, pp. 1007–1028.
  * [4] S. Y. Chang, Noncompact qualitative games with application to equilibria. Nonlinear Analysis, 65 (2006), 593-600.
  * [5] Y.-C. Chen, N. V. Long, and X. Luo, Iterated strict dominance in general games. Games and Economic Behavior 61 (2007), 219-315.
  * [6] [11] X.P. Ding, New H-KKM theorems and their applications to geometric property, coincidence theorems, minimax inequality and maximal elements, Indian J. Pure Appl. Math. 26 (1995) 1–19.
  * [7] X. P. Ding, Equilibria of noncompact generalized games with U-majorized preference correspondences. Appl. Math. Lett., 11 (1998), 5, 115-119.
  * [8] M. Dufwenberg and M. Stegeman, Existence and uniqueness of maximal reductions under iterated strict dominance, Econometrica (2002), 70, pp. 2007–2023.
  * [9] I. Gilboa, E. Kalai and E. Zemel, On the order of eliminating dominated strategies, Operation Research Letters, 9 (1990), pp. 85–89.
  * [10] I. Gilboa, E. Kalai and E. Zemel, The complexity of eliminating dominated strategies, Mathematics of Operation Research, 18 (1993), 553-565.
  * [11] X. Liu, H. Cai, Maximal Elements and Equilibrium of Abstract Economy. Appl. Math. Mech., 22 (2001), 10, 1225-1230.
  * [12] L. Marx and J. Swinkels, Order independence for iterated weak dominance, Games and Economic Behavior, 18 (1997), 219-245.
  * [13] P. Milgrom and J. Roberts, Rationalizability, learning and equilibrium in games with strategic complementarities. Econometrica, 58 (1996), 1255-1278.
  * [14] J. F. Nash, Equilibrium points in n-person games. Proc. Nat. Acad. Sci. U. S. A., 36, (1950), 1, 48-49.
  * [15] M. J. Osborne and A. Rubinstein, A Course in Game Theory, The MIT Press, Cambridge, Massachusetts, 1994.
  * [16] D. G. Pearce, Rationalizable strategic behavior and the problem of perfection, Econometrica, 52 (1984), pp. 1029–1050.
  * [17] K. Ritzberger, Foundations of Non-cooperative Game Theory, Oxford University Press, Oxford (2001).
  * [18] A. Rubinstein, Modelling Bounded Rationality, The MIT Press Cambridge, Massachusetts London, England, 1998.
  * [19] X. Z. Yuan, The Study of Minimax inequalities and Applications to Economies and Variational inequalities. Memoirs of the American Society, 132 (1988).
  * [20] X. Z. Yuan, E. Tarafdar, Maximal elements and equilibria of generalized games for U-majorized and condensing correspondences. Internat. J. Math. Sci., 1 (1996), 179-189.