A COUNTEREXAMPLE TO CONJECTURE “CATCH 22” WITH 3 PLAYERS, AND 5 OUTCOMES: 2
TERMINAL AND 3 CYCLIC

Bogdan Butyrin
National Research University Higher School of Economics (HSE), Moscow, Russia
<EMAIL_ADDRESS>
Vladimir Gurvich
National Research University Higher School of Economics (HSE), Moscow, Russia
<EMAIL_ADDRESS><EMAIL_ADDRESS>
Anton Lutsenko
National Research University Higher School of Economics (HSE), Moscow, Russia
<EMAIL_ADDRESS>
Mariya Naumova
Rutgers Business School, Rutgers University, Piscataway, NJ, United States
<EMAIL_ADDRESS>
Maxim Peskin
National Research University Higher School of Economics (HSE), Moscow, Russia
<EMAIL_ADDRESS>

Abstract: We construct a finite deterministic graphical (DG) game without Nash
equilibria in pure stationary strategies. This game has 3 players
$I=\\{1,2,3\\}$ and 5 outcomes: 2 terminal $a_{1}$ and $a_{2}$ and 3 cyclic.
Furthermore, for 2 players a terminal outcome is the best: $a_{1}$ for player
3 and $a_{2}$ for player 1. Hence, the rank vector $r$ is at most $(1,2,1)$.
Here $r_{i}$ is the number of terminal outcomes that are worse than some
cyclic outcome for the player $i\in I$. This is a counterexample to conjecture
“Catch 22” from the paper “On Nash-solvability of finite $n$-person DG games,
Catch 22” (2021) https://arxiv.org/abs/2111.06278, according to which, at
least 2 entries of $r$ are at least 2 for any NE-free game. However, Catch 22
remains still open for the games with a unique cyclic outcome, not to mention
a weaker (and more important) conjecture claiming that an $n$-person finite DG
game has a Nash equilibrium (in pure stationary strategies) when $r=(0^{n})$,
that is, all $n$ entries of $r$ are 0; in other words, when the following
condition holds:
($C_{0}$) any terminal outcome is better than every cyclic one for each
player.
A game is play-once if each player controls a unique position. It is known
that any play-once game satisfying ($C_{0}$) has a Nash equilibrium. We give a
new and very short proof of this statement. Yet, not only conjunction but
already disjunction of the above two conditions may be sufficient for Nash-
solvability. This is still open.
Keywords: $n$-person deterministic graphical games, Nash equilibrium, pure
stationary strategy, digraph, directed cycle, strongly connected component.

##  1 Introduction; main conjectures and examples

Our main example is given in graphical and normal forms in Figures 1 and 3,
respectively. Here we briefly describe its main properties postponing basic
definitions, which will be given later in Introduction. Figure 1 represents a
finite deterministic graphical game of 3 players, $I=\\{1,2,3\\}$, controlling
positions $V_{1}=\\{s_{1},u_{1},v_{1}\\};\;V_{2}=\\{u_{2},v_{2}\\}$ and
$V_{3}=\\{u_{3},v_{3}\\}$, respectively.

We restrict ourselves to finite games with perfect information and without
moves of chance, and the players to their pure stationary strategies. In our
example, player 1 has $3\times 2\times 2=12$ strategies, while players 2 and 3
have $2\times 2=4$ strategies, each. This game in the normal form is defined
by the table $X=X_{1}\times X_{2}\times X_{3}$ of size $12\times 4\times 4$,
the game form mappings $g:X\rightarrow\Omega$, and a triple of preference
relations $\succ=(\succ_{1},\succ_{2},\succ_{3})$ over $\Omega$, where
$\Omega=\\{a_{1},a_{2},c_{1},c_{2},c_{3}\\}$ is the set of outcomes. It
consists of 5 strongly connected components (SCCs) of the directed graph
(digraph) $G=(V,E)$ of the game. Two of them are the terminals: $a_{1}$ and
$a_{2}$, while 3 are cycles: $c_{1},c_{2},$ and $c_{3}$; see Figure 1. Note
that there is one more SCC in $G$, it consists of the initial position
$s_{1}$. Such an SCC, which is not terminal and does not contain a directed
cycle, is called transient; no outcome is assigned to it.

A digraph $G=(V,E)$ is partitioned into SCCs. This partition is unique and can
be constructed in time linear in its size of $G$, that is, $(|V|+|E|)$. This
partition has many important properties and applications; see, for
example,[38] and [37] for details. By contracting each SCC of $G$ to a single
vertex (and deleting every edge that belongs to an SCC) one obtains an acyclic
digraph $G^{*}$. One more application, to the DG games, was suggested in [19].
The main result of this paper is the Nash-solvability (in pure stationary
strategies) of the (finite) $2$-person ($n=2$) DG games. It follows from the
general result on Nash-solvability of tight game forms [14, 16]; see also [23,
24, 26]. For the zero-sum case, the saddle-point-solvability was proven even
earlier [12], see also [13].

However, this result cannot be extended to $n>2$. The first example of an NE-
free $4$-person DG game was constructed in [27]; see also [17]. Then a much
simpler $3$-person NE-free DG game was given in [8, Figure 3]. It has 4
outcomes: 3 terminal and a unique cycle. Furthermore, its digraph $G$ has two
transient SCCs, which are not associated with outcomes. Moreover, this game is
“almost play-once”: players 1 and 3 control a unique position each, only
player 2 controls two positions.

The remaining important part of a DG game is the payoff
$u:I\times\Omega\rightarrow\mathbb{R}$, where $u(i,\omega)$ is the profit of
player $i\in I$ in case outcome $\omega\in\Omega$ is realized in the game.
Studying NE, it is both correct and convenient to replace payoffs by
preferences. For each player $i\in I=\\{1,\dots,n\\}$, we introduce a linear
order $\succ_{i}$ over $\Omega$. Notation
$\omega^{\prime}\succ_{i}\omega^{\prime\prime}$ means that $i$ prefers
$\omega^{\prime}$ to $\omega^{\prime\prime}$. In particular, we assume that
there are no ties. It can be done without any loss of generality (wlog).
Indeed, making ties can create an NE, but cannot destroy it; see the
definition of Subsection 2.3. In particular, an NE-free DG game with payoff
$u$ remains NE-free after any sufficiently small perturbation of $u$. Thus,
one can replace a payoff $u$ by a close tie-free payoff $u^{\prime}$ and then,
in its turn, replace $u^{\prime}$ by the corresponding $n$-dimensional
preference profile $\succ=\\{\succ_{i}\mid i\in I\\}$, keeping the transformed
game NE-free all way.

Note also that merging arbitrarily the outcomes is an operation that respects
NE-existence; see for example, [14, 16]. In this paper, merging all cyclic
outcomes into a unique one, will play an important role.

In [6], among other results, it was shown that a play-once DG game has an NE
if the following additional condition hold:

CND$(C_{0})$: every terminal outcome is better than any cyclic one for each
player.

A very simple proof of this statement will be given in Subsection 3.2.

Clearly, CND$(C_{0})$ holds if and only if the rank $n$-vector $r$ is
$(0^{n})$, that is, all $n$ entries of $r$ equal 0.

However, it seems that conjunction of the above two conditions: the play-once
one and $(C_{0})$ is too strong. Can it be replaced by disjunction? No
counterexample is known, yet.

In [8, Section 6], it was shown that if an NE-free DG game satisfying
CND$(C_{0})$ exists, then there is also a DG game that has a unique NE-
outcome, which is cyclic. This conclusion holds even if the original game has
terminal outcomes and only one cyclic one. This looks like a paradox in view
of $(C_{0})$.

Although CND$(C_{0})$ looks “relaxable”, all attempts to construct an NE-free
example satisfying $(C_{0})$ fail yet. The following conjecture was suggested
in [20]:

CNJ$(C_{0})$: A DG game has an NE whenever CND$(C_{0})$ holds.

Let us merge all cyclic outcomes in one. Then, CND$(C_{0})$ (resp.
CNJ$(C_{0})$) is replaced by a stronger condition CND$(C^{\prime}_{0})$
(resp., by a weaker conjecture CNJ$(C^{\prime}_{0}))$.

Since attempts to disprove the weaker CNJ$(C^{\prime}_{0})$ fail too, we try
to weaken it further. Given the preference $\succ_{i}$ of a player $i\in I$,
let $r_{i}$ be the number of terminal outcomes for which there exists a
better, for player $i$, cyclic outcome. Thus every preference profile
$\succ=\\{\succ_{i}\mid i\in I\\}$ uniquely defines the rank $n$-vector
$r=(r_{i}\mid i\in I)$. For example, for the DG game from [8] we have
$r=(2,0,2)$. For many other NE-free DG games their rank vector has at least 2
entries equal to at least 2, each.

In [20], the corresponding condition and conjecture were denoted by
CND$(C_{22})$ and CNJ$(C_{22})$, respectively. Furthermore, after merging all
cyclic outcomes in one, we obtain CND$(C^{\prime}_{22})$ and
CNJ$(C^{\prime}_{22})$. CNJ$(C^{\prime}_{22})$, which is stronger than
CNJ$(C_{22})$, holds for NE-free DG games from [27, 8] and in many other
cases, as our computer analysis shows. Partial results were obtained in [26].

Our main example disproves CNJ$(C_{22})$ but not CNJ$(C^{\prime}_{22})$.
Indeed, consider the preference profile, given in Figure 1. There are 3 cyclic
and only 2 terminal outcomes. Furthermore, one of them is the best outcome,
for 2 players. In other words, $r=(1,2,1)$ However, an NE appears after
merging $c_{1},c_{2},$ and $c_{3}$.

To summarize, CNJ$(C_{22})$ is disproved, but CNJ$(C^{\prime}_{22})$ still
stays, along with CNJ$(C_{0})$ and CNJ$(C^{\prime}_{0})$.

A digraph is called symmetric if $(u,v)$ is its directed edge whenever $(v,u)$
is (unless $u$ is a terminal or $v$ is an initial position).

In [5, Theorem 2], it was shown that every $n$-person DG game on a symmetric
digraph is Nash-solvable; see also Theorem 3.

We assume, yet, that all cycles of any fixed SCC form the same outcome.
Another option is to wave this assumption and consider each cycle as a
separate outcome. Then, Nash-solvability becomes a rare phenomenon already for
the 2-person zero-sum games. Consider, for example, the digraph with two
vertices $s,v$ controlled by players 1 and 2, respectively, and 2 pairs of
directed edges: two from $s$ to $v$ and two from $v$ to $s$; its normal form
is the $2\times 2$ matrix game whose entries are four distinct outcomes; see
[9, Figure 1 (1)]. Thus, no saddle point exists if player 1 prefers the main
diagonal to the side one, while player 2 prefers vice versa.

A criterion of Nash-solvability for such two-person DG games on symmetric
digraphs is given by [9, Theorem 1, Corollaries 1 and 2].

##  2 Main concepts and definitions

###  2.1 Strongly connected components of directed graphs

Let $G=(V,E)$ be a directed graph (digraph). It may have parallel edges,
directed oppositely or similarly, and loops, at most one at each vertex.
Digraph $G$ is called strongly connected if for any $v,v^{\prime}\in V$ there
is a directed path from $v$ to $v^{\prime}$ (and, hence, from $v^{\prime}$ to
$v$, as well). By definition, the union of two strongly connected digraphs is
strongly connected if and only if they have a common vertex. A vertex-
inclusion-maximal strongly connected induced subgraph of G is called its
strongly connected component (SCC). Obviously, any digraph $G=(V,E)$ admits a
unique decomposition into SCCs: $G^{j}=G[V^{j}]=(V^{j},E^{j})$ for $j\in J$,
where $J$ is a set of indices and $V=\cup_{j\in J}V^{j}$ is a partition of
$V$, that is, $V^{j}\cap V^{j^{\prime}}=\emptyset$ whenever $j\neq j^{\prime}$
for a pair $j,j^{\prime}\in J$. This partition can be determined in time
linear in the size of $G$ (that is, in $(|V|+|E|))$ and has numerous
applications; see [38] and also [37] for more details. One more application,
to positional games, was suggested in [19].

Let $V_{T}\subseteq V$ denote the set of all the terminals of $G$, that is,
$v\in V_{T}$ if and only if there is no edge from $v$. Any such vertex forms a
maximal SCC, that is, $\\{v\\}=V^{j}$ for some $j\in J$. Denote by $J^{T}$ the
corresponding subset of $J$. For convenience, let us add a loop $e_{v}$ to
each $v\in V_{T}$ that does not have one yet. All loops in $V_{T}$ , old and
new, will be called terminal loops and all $v\in V_{T}$ will be still called
terminals.

The concepts of a directed path and a directed cycle (dicycle) are defined
standardly [37, 38]. An edge is a directed path of length 1; a loop is a
dicycle of length 1, a dicycle of length 2 is a pair of parallel oppositely
directed edges, a dicycle of length $|V|$ is called Hamiltonian. A digraph
without dicycles is called acyclic.

Let $J_{0}$ denote the subset of $J$ such that $V^{j}$ is a single vertex with
no loop it it. Obviously, $G^{j}$ contains a dicycle unless $j\in J_{0}$. By
our convention, $J_{T}\cap J_{0}=\emptyset$.

For each $j\in J$, let us contract $G^{j}$ into a single vertex $v^{j}$. Then,
all the edges of $E^{j}$ (in particular, loops) disappear and we obtain an
acyclic digraph $G^{*}=(V^{*},E^{*})$. It can be constructed in time linear in
$|V|+|E|$.

###  2.2 Modeling graphical games by digraphs

Given an arbitrary digraph $G=(V,E)$, we interpret it as a positional
structure in which $V$ and $E$ are positions and moves, respectively.
Furthermore, let us fix a partition $D:V=V_{1}\cup\dots\cup V_{n}\cup V_{T}$
in which $V_{i}$ are the sets of positions controlled by the players $i\in
I=\\{1,\dots,n\\}$, while $V_{T}$ is the set of all terminals.

The considered model is restricted to the games with perfect information and
without moves of chance. Also, we restrict all players $i\in I$ to their pure
stationary strategies $X_{i}$. Such a strategy $x_{i}\in X_{i}$ assigns a move
$(v,v^{\prime})\in E$ to every $v\in V_{i}$. Given an initial position
$v_{0}\in V\setminus V_{T}$, each strategy profile $x=(x_{1},\dots,x_{n})$
uniquely defines a walk in $G$ that begins in $v_{0}$ and in each position
follows the move chosen by the corresponding strategy. We denote this walk by
$p(x)$ and call it a play generated by $x$. Since all strategies of $x$ are
stationary, play $p(x)$ forms a “lasso”, that is, it consists of an initial
directed path, which can be empty, and a dicycle repeated infinitely.

For every $j\in J\setminus J_{0}$, let us identify all lassos whose dicycles
belong to $G_{j}$ and treat them as a single outcome $c_{j}$ of the game.
Then, $\Omega=\\{c_{j}\mid j\in J\setminus J_{0}\\}$ is the set of outcomes.

An outcome is called terminal if the corresponding SCC $G^{j}$ generates a
terminal vertex of $G^{*}$. Note that all terminals of $G$ are the terminals
$G^{*}$, but there may exist others. Any SCC such that each move from it does
not leave it, also forms a terminal of the considered game. Furthermore,
components $G^{j}$ for $j\in J_{0}$ are called transient. Each one consists of
a single vertex and does not form an outcome. Each remaining SCC, not terminal
and not transient, will be called inner. Clearly, each one has a cycle, which
may be a loop, and it forms an outcome, which will be called inner too.

Thus, given a digraph $G=(V,E)$ and partition $D$, we obtain mapping
$g:X\rightarrow\Omega$, where $X=X_{1}\times\dots\times X_{n}$ is the set of
strategy profiles, also called situations. In general, such a mapping $g$ is
called a game form.

Pair $(G,D)$ defines a DG game structure and $g=g(G,D)$ its normal form.

Given an $n$-person game form $g:X\rightarrow\Omega$, introduce a payoff
$u:I\times\Omega\rightarrow\mathbb{R}$. The value $u(i,\omega)$ is interpreted
as the profit of the player $i\in I=\\{1,\dots,n\\}$ in case the outcome
$\omega\in\Omega$ is realized. Pair $(g,u)$ is called the game in normal form.

The DG games were introduced by Washburn [40] in 1990 and since then are
frequent in the literature; see, for example, [2, 3, 4, 6, 9, 10, 11, 27].
Only 2-person zero-sum DG games were considered in [40] but the extension to
the $n$-person case is obvious.

###  2.3 Nash equilibrium (NE)

Given the game $(g,u)$ defined by a game form $g:X\rightarrow\Omega$ and
payoff $u:I\times\Omega\rightarrow\mathbb{R}$, a situation
$x=(x_{1},\dots,x_{n})\in X_{1}\times\dots X_{n}=X$ is called a NE if for each
player $i\in I$ inequality $u(i,g(x))\geq u(i,g(x^{\prime}))$ holds for every
situation $x^{\prime}\in X$ that may differ from $x$ only in entry $i$, that
is, equality $x_{j}=x^{\prime}_{j}$ holds for all $j\neq i$. In other words,
no player $i\in I$ can improve the result $u(i,g(x))$ replacing the strategy
$x_{i}$ by $x^{\prime}_{i}$ provided all other players keep their strategies
unchanged. This concept was introduced by John Nash [34, 35]. He proved that
any matrix game has a NE in mixed strategies. Here we study Nash-solvability
in pure strategies; see, for example, [1-9,12-33,36,40].

A game form $g$ is called Nash-solvable if for an arbitrary payoff $u$, the
corresponding game $(g,u)$ has an NE.

Since tie-breaking can only destroy NE, but cannot create one, studying Nash-
solvability, we can assume wlog that payoff $u$ has no ties and then replace
$u$ by a preference $\succ=(\succ_{1},\dots,\succ_{n})$ assuming that
$\omega\succ_{i}\omega^{\prime}$ if and only if
$u(i,\omega)>u(i,\omega^{\prime})$ for any $\omega,\omega^{\prime}\in\Omega$.

Recall also that merging outcomes of a game form respects its Nash-
solvability.

##  3 Partial results

###  3.1 Nash-solvability of $n$-person DG games for $n=2$ and $n>2$

######  Theorem 1.

([19]) Every 2-person DG game has an NE.

This result is derived from a general criterion of Nash-solvability of
2-person game forms [14, 16]. The zero-sum case was considered even earlier by
Edmonds and Fulkerson [12]; see also [13]. In [16] it was shown that the zero-
sum- and Nash-solvability are equivalent properties of a 2-person game form
$g$. Furthermore, both are equivalent with the tightness of $g$. Tightness of
the DG game forms was shown in [6] for the special case, when all inner cyclic
outcomes are merged, and verified in general in [19]. However, tightness is
not related (neither necessary, nor sufficient) to Nash-sovability of
$n$-person game forms with $n>2$ [16]. Moreover, an $n$-person DG game is
tight for all $n$, yet, may be not Nash-solvable when $n>2$; see [27] for
$n=3$ and [8] for $n=4$.

NE-free DG games are sparse. We can add some extra conditions and enforce
Nash-solvability. For example, it holds for all $n$ in case of symmetric
digraphs [5].

Extra conditions CND$(C_{0})$, CND$(C^{\prime}_{0})$, CND$(C_{22})$,
CND$(C^{\prime}_{22})$ and the corresponding conjectures on Nash-solvability,
CNJ$(C_{0})$, CNJ$(C^{\prime}_{0})$, CNJ$(C_{22})$, CNJ$(C^{\prime}_{22})$,
were considered in [20]. Here we disprove CNJ$(C_{22})$, while 3 others remain
open.

###  3.2 Play-once $n$-person DG games and condition CND$(C_{0})$

The following two conditions are sufficient for the existence of a NE.

######  Proposition 1.

An $n$-person DG game has an NE if (i) it is play-once and (ii) CND$(C_{0})$
holds.

This statement follows from the results of [6]. Here we give a simple direct
proof. Let us note, however, that not only conjunction but, perhaps, already
disjunction of (i) and (ii) is sufficient for Nash-solvability. At least, we
have no counterexample.

So conjecture CNJ($C_{22}$) is disproved, but to conjectures CNJ($C_{0}$),
CNJ($C^{\prime}_{0}$) and CNJ($C^{\prime}_{22}$) we can add one more.

######  Conjecture 1.

A play-once $n$-person DG game is Nash-solvable.

Although a NE exists whenever conditions (i) and (ii) holds, yet, improvement
cycles can exist too; see [2, Figure 5 and Section 2] for definitions and more
details.

Proof of Proposition. Note first that each (finite) digraph $G$ has a terminal
SCC, since its SCC digraph $G^{*}$ is finite and acyclic.

Assume for contradiction that a DG game $\mathcal{G}=(G,D,\succ)$ is NE-free
but satisfies (i) and (ii). Moreover, assume that it is a minimal such game.
Wlog, assume that every vertex (and arc) of $G$ is reachable from the initial
position $s$. Indeed, one can simply delete from $G$ the vertices not
reachable from $s$, thus, reducing $G$.

Deleting bad terminal moves. Suppose there are two terminal moves $v,t$ and
$v,t^{\prime}$. Wlog we assume that $v$ is controlled by a player $i\in I$ and
that $t\succ_{i}t^{\prime}$. Then, one can delete arc $(v,t^{\prime})$ and,
obviously, no NE appears. Thus, we can assume that in every position $v$ there
exists at most one terminal move. Furthermore, clearly, there is at least one
non-terminal move in $v$. More generally, $\mathcal{G}$ has no forced move.
Indeed, in contradiction with minimality of $G$, one can contract such a move
keeping the normal normal form of the game and, in particular, the set of its
Nash equilibria.

Choose a shortest terminal play $p$ and fix the following situation: on $p$
follow $p$, out of $p$ choose a non-terminal move. By (i) and (ii), this is a
NE situation. ∎

######  Remark 1.

Recall that each finite DG game has a terminal and a terminal play. Indeed,
the game may have no terminal positions but it always has a terminal SCC,
since its SCC graph is finite and acyclic. In the original graph, one can
contract a terminal SCC replacing it by a single vertex (or by a loop).

######  Example 1.

Let $\mathcal{G}$ consists of the following moves $(s,v)$, $(s,t)$,
$(v,t^{\prime})$, $(v,t^{\prime\prime})$. Furthermore, $s$ is an initial
position, while $t^{\prime},t^{\prime\prime}$, and $t$ are terminal. The
terminal payoffs are (2,3) in $t$, (3,2) in $t^{\prime}$, and (1,1) in
$t^{\prime\prime}$. It is easy to verify that this game has two NE. The
standard “backward induction” NE: $x^{\prime}=\\{(s,v),(v,t^{\prime})\\}$
resulting in (3,2) and the blackmail NE:
$x^{\prime\prime}=\\{(s,t),(v,t^{\prime\prime})$ resulting in (2,3). Player 2
threatens by move $(v,t^{\prime\prime})$, which is the worst for both, thus,
pushing player 1 to move to $t$ which is better for 2 than $t^{\prime}$.
Consider two terminal moves $(v,t^{\prime})$ and $(v,t^{\prime\prime})$ of
player 2. The first is better than the second. Delete the bad move
$(v,t^{\prime\prime})$ from the digraph. By doing so, we destroy the second
NE. Only the first NE remains.

##  4 Main example

The following example disproves CNJ$(C_{22})$. However, 3 weaker conjectures,
CNJ$(C^{\prime}_{22})$, CNJ$(C_{0})$ and CNJ$(C^{\prime}_{0})$ remain open.

The digraph $G=(V,E)$ is given in Figure 1. It has 3 distinct cyclic outcomes
$c_{1},c_{2},c_{3}$ and only 2 terminals $a_{1},a_{2}$. The preferences of the
players are also given Figure 1. We see that $a_{1}$ and $a_{2}$ are top
outcomes of players 3 and 1, respectively and, thus, the rank vector is
$r=(1,2,1)$ and condition CND$(C_{22})$ fails. Nevertheless, we will show that
the game is NE-free, in contradiction with CNJ$(C_{22})$.

$s_{1}$$u_{1}$$u_{2}$$v_{1}$$u_{3}$$v_{2}$$v_{3}$$a_{1}$$a_{2}$$c_{1}$$c_{2}$$c_{3}$
Figure 1: Graphical form

Three players $I=\\{1,2,3\\}$ control positions $(s_{1},u_{1},v_{1})$,
$(u_{2},v_{2})$, $(u_{3},v_{3})$, respectively, and have $|X_{1}|=3\times
2\times 2=12$ and $|X_{2}|=|X_{3}|=2\times 2=4$ strategies. The initial
position is $s_{1}$. To specify a strategy of a player $i$ we fix how (s)he
moves in each position. The normal form is given in Figure 3. For every
situation $x\in X$ we provide the outcome
$\omega(x)\in\Omega=\\{a_{1},a_{2},c_{1},c_{2},c_{3}\\}$ with the superscripts
showing each player $i$ who can improve $x$ by replacing $x_{i}$ with
$x^{\prime}_{i}$ such that $\omega(x^{\prime})\succ_{i}g(x)$. In some
situations there are more than one superscript, yet, for each situation there
exists at least one. This exactly means that the obtained game is NE-free.
Yet, condition CND$(C_{22})$ of the conjecture CNJ$(C_{22})$ fail.

However, if we merge cyclic outcomes $c_{1},c_{2},c_{3}$ then an NE will
appear. Thus, a weaker conjecture CNJ$(C^{\prime}_{22})$ is not disproved, as
well as conjectures CNJ$(C_{0})$ and CNJ$(C^{\prime}_{0})$, since the
corresponding conditions CND$(C_{0})$ and CND$(C^{\prime}_{0})$ do not hold.

Preferences $\prec_{1},\prec_{2},\prec_{3}$:

$\text{player 1:
}c_{1}\prec_{1}a_{1}\prec_{1}c_{2}\prec_{1}c_{3}\prec_{1}a_{2}$ $\text{player
2: }a_{2}\prec_{2}c_{1}\prec_{2}c_{2}\prec_{2}a_{1}\prec_{2}c_{3}$
$\text{player 3:
}c_{3}\prec_{3}c_{1}\prec_{3}a_{2}\prec_{3}c_{2}\prec_{3}a_{1}$

3-d player: $(v_{2}\to v_{1},w_{2}\to w_{1})$

1st player | 2nd player |  |  |
---|---|---|---|---
| $(u_{2}\to u_{1},$ |  |  |
$v_{2}\to v_{3})$ | $(u_{2}\to u_{1},$ |  |  |
$v_{2}\to a_{1})$ | $(u_{2}\to u_{3},$ |  |  |
$v_{2}\to v_{3})$ | $(u_{2}\to u_{3},$ |  |  |
$v_{2}\to a_{1})$ |  |  |  |
$(s\to u_{2},u_{1}\to u_{2},v_{1}\to v_{2})$ | $c_{1}^{1,2}$ |  $c_{1}^{1,2}$ | $c_{2}^{1}$ | $c_{2}^{3}$
$(s\to u_{2},u_{1}\to u_{2},v_{1}\to w_{1})$ | $c_{1}^{1,2}$ |  $c_{1}^{1,2}$ | $c_{3}^{3}$ | $a_{2}^{1,2}$
$(s\to u_{2},u_{1}\to v_{1},v_{1}\to v_{2})$ | $c_{2}^{1}$ |  $c_{2}^{3}$ | $c_{2}^{1}$ | $c_{2}^{3}$
$(s\to u_{2},u_{1}\to v_{1},v_{1}\to w_{1})$ | $c_{3}^{3}$ |  $a_{2}^{1,2}$ | $c_{3}^{3}$ | $a_{2}^{1,2}$
$(s\to v_{1},u_{1}\to u_{2},v_{1}\to v_{2})$ | $c_{2}^{1}$ |  $c_{2}^{3}$ | $c_{2}^{1}$ | $c_{2}^{3}$
$(s\to v_{1},u_{1}\to u_{2},v_{1}\to w_{1})$ | $c_{3}^{3}$ |  $a_{2}^{1,2}$ | $c_{3}^{3}$ | $a_{2}^{1,2}$
$(s\to v_{1},u_{1}\to v_{1},v_{1}\to v_{2})$ | $c_{2}^{1}$ |  $c_{2}^{3}$ | $c_{2}^{1}$ | $c_{2}^{3}$
$(s\to v_{1},u_{1}\to v_{1},v_{1}\to w_{1})$ | $c_{3}^{3}$ |  $a_{2}^{1,2}$ | $c_{3}^{3}$ | $a_{2}^{1,2}$
$(s\to w_{1},u_{1}\to u_{2},v_{1}\to v_{2})$ | $c_{3}^{3}$ |  $a_{2}^{1,2}$ | $c_{3}^{3}$ | $a_{2}^{1,2}$
$(s\to w_{1},u_{1}\to u_{2},v_{1}\to w_{1})$ | $c_{3}^{3}$ |  $a_{2}^{1,2}$ | $c_{3}^{3}$ | $a_{2}^{1,2}$
$(s\to w_{1},u_{1}\to v_{1},v_{1}\to v_{2})$ | $c_{3}^{3}$ |  $a_{2}^{1,2}$ | $c_{3}^{3}$ | $a_{2}^{1,2}$
$(s\to w_{1},u_{1}\to v_{1},v_{1}\to w_{1})$ | $c_{3}^{3}$ |  $a_{2}^{1,2}$ | $c_{3}^{3}$ | $a_{2}^{1,2}$

3-d player: $(v_{2}\to v_{1},w_{2}\to a_{2})$

1st player | 2nd player |  |  |
---|---|---|---|---
| $(u_{2}\to u_{1},$ |  |  |
$w_{1}\to w_{2})$ | $(u_{2}\to u_{1},$ |  |  |
$w_{1}\to a_{1})$ | $(u_{2}\to v_{2},$ |  |  |
$w_{1}\to w_{2})$ | $(u_{2}\to v_{2},$ |  |  |
$w_{1}\to a_{1})$ |  |  |  |
$(s\to u_{2},u_{1}\to u_{2},v_{1}\to v_{2})$ | $c_{1}^{1,2}$ |  $c_{1}^{1,2}$ | $c_{2}^{1}$ | $c_{2}^{3}$
$(s\to u_{2},u_{1}\to u_{2},v_{1}\to w_{1})$ | $c_{1}^{1,2}$ |  $c_{1}^{1,2}$ | $a_{1}^{2}$ | $a_{2}^{1}$
$(s\to u_{2},u_{1}\to v_{1},v_{1}\to v_{2})$ | $c_{2}^{1}$ |  $c_{2}^{3}$ | $c_{2}^{1}$ | $c_{2}^{3}$
$(s\to u_{2},u_{1}\to v_{1},v_{1}\to w_{1})$ | $a_{1}^{2}$ |  $a_{2}^{1}$ | $a_{1}^{2}$ | $a_{2}^{1}$
$(s\to v_{1},u_{1}\to u_{2},v_{1}\to v_{2})$ | $c_{2}^{1}$ |  $c_{2}^{3}$ | $c_{2}^{1}$ | $c_{2}^{3}$
$(s\to v_{1},u_{1}\to u_{2},v_{1}\to w_{1})$ | $a_{1}^{2}$ |  $a_{2}^{1}$ | $a_{1}^{2}$ | $a_{2}^{1}$
$(s\to v_{1},u_{1}\to v_{1},v_{1}\to v_{2})$ | $c_{2}^{1}$ |  $c_{2}^{3}$ | $c_{2}^{1}$ | $c_{2}^{3}$
$(s\to v_{1},u_{1}\to v_{1},v_{1}\to w_{1})$ | $a_{1}^{2}$ |  $a_{2}^{1}$ | $a_{1}^{2}$ | $a_{2}^{1}$
$(s\to w_{1},u_{1}\to u_{2},v_{1}\to v_{2})$ | $a_{1}^{2}$ |  $a_{2}^{1}$ | $a_{1}^{2}$ | $a_{2}^{1}$
$(s\to w_{1},u_{1}\to u_{2},v_{1}\to w_{1})$ | $a_{1}^{2}$ |  $a_{2}^{1}$ | $a_{1}^{2}$ | $a_{2}^{1}$
$(s\to w_{1},u_{1}\to v_{1},v_{1}\to v_{2})$ | $a_{1}^{2}$ |  $a_{2}^{1}$ | $a_{1}^{2}$ | $a_{2}^{1}$
$(s\to w_{1},u_{1}\to v_{1},v_{1}\to w_{1})$ | $a_{1}^{2}$ |  $a_{2}^{1}$ | $a_{1}^{2}$ | $a_{2}^{1}$

3-d player: $(v_{2}\to w_{2},w_{2}\to w_{1})$

1st player | 2nd player |  |  |
---|---|---|---|---
| $(u_{2}\to u_{1},$ |  |  |
$w_{1}\to w_{2})$ | $(u_{2}\to u_{1},$ |  |  |
$w_{1}\to a_{1})$ | $(u_{2}\to v_{2},$ |  |  |
$w_{1}\to w_{2})$ | $(u_{2}\to v_{2},$ |  |  |
$w_{1}\to a_{1})$ |  |  |  |
$(s\to u_{2},u_{1}\to u_{2},v_{1}\to v_{2})$ | $c_{1}^{1,2}$ |  $c_{1}^{1,2}$ | $c_{3}^{3}$ | $a_{2}^{2}$
$(s\to u_{2},u_{1}\to u_{2},v_{1}\to w_{1})$ | $c_{1}^{1,2}$ |  $c_{1}^{1,2}$ | $c_{3}^{3}$ | $a_{2}^{2}$
$(s\to u_{2},u_{1}\to v_{1},v_{1}\to v_{2})$ | $c_{3}^{3}$ |  $a_{2}^{2}$ | $c_{3}^{3}$ | $a_{2}^{2}$
$(s\to u_{2},u_{1}\to v_{1},v_{1}\to w_{1})$ | $c_{3}^{3}$ |  $a_{2}^{2}$ | $c_{3}^{3}$ | $a_{2}^{2}$
$(s\to v_{1},u_{1}\to u_{2},v_{1}\to v_{2})$ | $c_{3}^{3}$ |  $a_{2}^{2}$ | $c_{3}^{3}$ | $a_{2}^{2}$
$(s\to v_{1},u_{1}\to u_{2},v_{1}\to w_{1})$ | $c_{3}^{3}$ |  $a_{2}^{2}$ | $c_{3}^{3}$ | $a_{2}^{2}$
$(s\to v_{1},u_{1}\to v_{1},v_{1}\to v_{2})$ | $c_{3}^{3}$ |  $a_{2}^{2}$ | $c_{3}^{3}$ | $a_{2}^{2}$
$(s\to v_{1},u_{1}\to v_{1},v_{1}\to w_{1})$ | $c_{3}^{3}$ |  $a_{2}^{2}$ | $c_{3}^{3}$ | $a_{2}^{2}$
$(s\to w_{1},u_{1}\to u_{2},v_{1}\to v_{2})$ | $c_{3}^{3}$ |  $a_{2}^{2}$ | $c_{3}^{3}$ | $a_{2}^{2}$
$(s\to w_{1},u_{1}\to u_{2},v_{1}\to w_{1})$ | $c_{3}^{3}$ |  $a_{2}^{2}$ | $c_{3}^{3}$ | $a_{2}^{2}$
$(s\to w_{1},u_{1}\to v_{1},v_{1}\to v_{2})$ | $c_{3}^{3}$ |  $a_{2}^{2}$ | $c_{3}^{3}$ | $a_{2}^{2}$
$(s\to w_{1},u_{1}\to v_{1},v_{1}\to w_{1})$ | $c_{3}^{3}$ |  $a_{2}^{2}$ | $c_{3}^{3}$ | $a_{2}^{2}$

3-d player: $(v_{2}\to w_{2},w_{2}\to a_{2})$

1st player | 2nd player |  |  |
---|---|---|---|---
| $(u_{2}\to u_{1},$ |  |  |
$w_{1}\to w_{2})$ | $(u_{2}\to u_{1},$ |  |  |
$w_{1}\to a_{1})$ | $(u_{2}\to v_{2},$ |  |  |
$w_{1}\to w_{2})$ | $(u_{2}\to v_{2},$ |  |  |
$w_{1}\to a_{1})$ |  |  |  |
$(s\to u_{2},u_{1}\to u_{2},v_{1}\to v_{2})$ | $c_{1}^{1}$ |  $c_{1}^{1}$ | $a_{1}^{2,3}$ | $a_{1}^{2,3}$
$(s\to u_{2},u_{1}\to u_{2},v_{1}\to w_{1})$ | $c_{1}^{1}$ |  $c_{1}^{1}$ | $a_{1}^{2}$ | $a_{1}^{2,3}$
$(s\to u_{2},u_{1}\to v_{1},v_{1}\to v_{2})$ | $a_{1}^{3}$ |  $a_{1}^{3}$ | $a_{1}^{3}$ | $a_{1}^{3}$
$(s\to u_{2},u_{1}\to v_{1},v_{1}\to w_{1})$ | $a_{1}^{2}$ |  $a_{2}^{1}$ | $a_{1}^{2}$ | $a_{1}^{2,3}$
$(s\to v_{1},u_{1}\to u_{2},v_{1}\to v_{2})$ | $a_{1}^{3}$ |  $a_{1}^{3}$ | $a_{1}^{3}$ | $a_{1}^{3}$
$(s\to v_{1},u_{1}\to u_{2},v_{1}\to w_{1})$ | $a_{1}^{2}$ |  $a_{2}^{1}$ | $a_{1}^{2}$ | $a_{2}^{1}$
$(s\to v_{1},u_{1}\to v_{1},v_{1}\to v_{2})$ | $a_{1}^{3}$ |  $a_{1}^{3}$ | $a_{1}^{3}$ | $a_{1}^{3}$
$(s\to v_{1},u_{1}\to v_{1},v_{1}\to w_{1})$ | $a_{1}^{2}$ |  $a_{2}^{1}$ | $a_{1}^{2}$ | $a_{2}^{1}$
$(s\to w_{1},u_{1}\to u_{2},v_{1}\to v_{2})$ | $a_{1}^{2}$ |  $a_{2}^{1}$ | $a_{1}^{2}$ | $a_{2}^{1}$
$(s\to w_{1},u_{1}\to u_{2},v_{1}\to w_{1})$ | $a_{1}^{2}$ |  $a_{2}^{1}$ | $a_{1}^{2}$ | $a_{2}^{1}$
$(s\to w_{1},u_{1}\to v_{1},v_{1}\to v_{2})$ | $a_{1}^{2}$ |  $a_{2}^{1}$ | $a_{1}^{2}$ | $a_{2}^{1}$
$(s\to w_{1},u_{1}\to v_{1},v_{1}\to w_{1})$ | $a_{1}^{2}$ |  $a_{2}^{1}$ | $a_{1}^{2}$ | $a_{2}^{1}$

Figure 3: Normal form

##  5 NE-free DG $n$-person games and satisfiability

Constructing NE-free $n$-person DG games requires a computer. The problem is
reduced to satisfiability and solved by a SAT-solver. The CNF corresponding to
a DG game is ”bipolar”: part of its clauses are positive, no negated
variables, while the remaining clauses are negative, all variables are
negated.

Introduce $\frac{1}{2}nk(k-1)$ variables $y_{\omega,\omega^{\prime}}^{i}$, for
all $i\in I=\\{1,\dots,n\\}$ and distinct pairs
$\omega,\omega^{\prime}\in\Omega$; here $k=|\Omega|$. We set
$y_{\omega,\omega^{\prime}}^{i}=1$ when $\omega\succ_{i}\omega^{\prime}$ and,
respectively, $y_{\omega,\omega^{\prime}}^{i}=0$ when
$\omega^{\prime}\succ_{i}\omega$. Thus,
$y_{\omega,\omega^{\prime}}^{i}=\bar{y}_{\omega^{\prime},\omega}^{i}$ holds by
definition. Consider CNF
$C_{-}=\bigwedge(\bar{y}_{\omega,\omega^{\prime}}^{i}\vee\bar{y}_{\omega^{\prime},\omega^{\prime\prime}}^{i}\vee\bar{y}_{\omega^{\prime\prime},\omega}^{i})$,
where conjunction is taken over all players $i\in I$ and all pairwise distinct
triplets $\omega,\omega^{\prime},\omega^{\prime\prime}\in\Omega$. All
variables of $C_{-}$ are negated. It is not difficult to see that $C_{-}$ is
satisfied if and only if it corresponds to an acyclic preference of player $i$
over $\Omega$. Indeed, 2-dicycles obviously are not possible, since
$y_{\omega,\omega^{\prime}}^{i}=\bar{y}_{\omega^{\prime},\omega}^{i}$.
Furthermore, it is well-known that any tournament that has a dicycle, has a
3-dicycle; see, for example, [39]. Finally, it is not difficult to assign a
positive CNF $C_{+}$ to a game such that the game is NE-free if and only if
CNF $C_{i}\wedge C_{+}$ is satisfyable. Although it is exponential in the size
of digraph $G$, but its structure is clear. Then, by the above construction,
an NE-free preference $\succ$ for the considered DG $n$-person game structure
corresponds to a satisfying assignments of the CNF $C_{-}\wedge C_{+}$. Using
a powerful SAT-solver we can analyze many games and find NE-free ones among
them.

### Acknowledgement

The paper was prepared within the framework of the HSE University Basic
Research Program.

## References

  * [1] H. Ackermann, H. Röglin, and B. Vöcking, Pure Nash equilibria in player-specific and weighted congestion games, Theoretical Computer Science, Internet and Network Economics 410 (17) (2009) 1552–1563.
  * [2] D. Anderson, V. Gurvich, and T. Hansen, On acyclicity of games with cycles, Discrete Applied Math. 158:10 (2010) 1049–1063.
  * [3] D. Andersson, K. Hansen, P. Miltersen, and T. Sorensen, Deterministic graphical games, revisited, J. Logic and Computation 22:2 (2012) 165–178; Preliminary version in Fourth Conference on Computability in Europe (CiE-08), Lecture Notes in Computer Science 5028 (2008) 1–10.
  * [4] E. Boros, K. Elbassioni, V. Gurvich, and K. Makino, On Nash equilibria and improvement cycles in pure positional strategies for Chess-like and Backgammon-like n-person games, Discrete Math. 312:4 (2012) 772–788.
  * [5] E. Boros, P. G. Franciosa, V. Gurvich, and M. Vyalyi, Deterministic $n$-person shortest path and terminal games on symmetric digraphs have Nash equilibria in pure stationary strategies, arxiv.org/abs/2202.11554 (2022) 25 pp., Int. J. Game Theory, online since 10 October 2023 DOI10.1007/s00182-023-00875-y; SharedIt link: https://rdcu.be/dofOK.
  * [6] E. Boros and V. Gurvich, On Nash solvability in pure stationary strategies of positional games with perfect information which may have cycles, Mathematical Social Sciences 46 (2003) 207–241.
  * [7] E. Boros and V. Gurvich, Why Chess and Backgammon can be solved in pure positional uniformly optimal strategies, RUTCOR Research Report, RRR-21-2009, Rutgers University.
  * [8] E. Boros, V. Gurvich, M. Milanic, V. Oudalov, and J. Vicic, A three-person deterministic graphical game without Nash equilibria, Discrete Applied Math. 243 (2018) 21–38.
  * [9] E. Boros, V. Gurvich, K. Makino, and S. Wei, Nash-solvabile two-person symmetric cycle game forms, Discrete Applied Math. 159:15 (2011) 1461–1487.
  * [10] A. Condon, The complexity of stochastic games, Information and Computation 96 (1992) 203–224.
  * [11] V. I. Danilov and A. I. Sotskov, Social Choice Mechanisms, in “Studies of Economic Design”, Springer, Berlin-Heidelberg, 2002.
  * [12] J. Edmonds and D.R. Fulkerson, Bottleneck extrema, J. Combin. Theory 8:3 (1970) 299–306.
  * [13] V. Gurvich, To theory of multi-step games, USSR Comput. Math. and Math Phys. 13:6 (1973) 143–161.
  * [14] V. Gurvich, Solution of positional games in pure strategies, USSR Comput. Math. and Math. Phys. 15:2 (1975) 74–87.
  * [15] V. Gurvich, A stochastic game with complete information and without equilibrium situations in pure stationary strategies, Russian Math. Surveys 43:2 (1988) 171–172.
  * [16] V. Gurvich, Equilibrium in pure strategies, Soviet Math. Dokl. 38:3 (1989) 597–602.
  * [17] V. Gurvich, A four-person chess-like game without Nash equilibria in pure stationary strategies, Business Informatics 1:31 (2015) 68–76.
  * [18] V. Gurvich, Generalizing Gale’s theorem on backward induction and domination of strategies (2017) 16 pp. http://arxiv.org/abs/1711.11353.
  * [19] V. Gurvich, Backward induction in presence of cycles, Oxford Journal of Logic and Computation 28:7 (2018) 1635–1646.
  * [20] V. Gurvich, On Nash-solvability of finite $n$-person deterministic graphical games, Catch 22 https://arxiv.org/abs/2111.06278 (2021) 4 pp.
  * [21] V. Gurvich, On Nash-solvability of finite n-person shortest path games, bi-shortest path conjecture, http://arxiv.org/abs/2111.07177 (2021) 5 pp.
  * [22] V. Gurvich and G. Koshevoy, Monotone bargaining is Nash-solvable, Discrete Appl. Math. 250 (2018) 1–15.
  * [23] V. Gurvich and M. Naumova, Lexicographically maximal edges of dual hypergraphs and Nash-solvability of tight game forms, Annals of Mathematics and Artificial Intelligence, 92 (1) (2024) 49–57.
  * [24] V. Gurvich and M. Naumova, On Nash-solvability of n-person graphical games under Markov’s and a-priori realizations, Annals of Operations Research, 336:3 (2024) 1905–1927.
  * [25] V. Gurvich and M. Naumova, Computing lexicographically safe Nash equilibria in finite two-person games with tight game forms given by oracles, Discr. Appl. Math. 340:3 (2023) 53–68.
  * [26] V. Gurvich and M. Naumova, On Nash-solvability of finite two-person tight vector game forms, https://arxiv.org/abs/2204.10241 (2022) 17 pp.
  * [27] V. Gurvich and V. Oudalov, A four-person chess-like game without Nash equilibria in pure stationary strategies https://arxiv.org/abs/1411.0349 (2014) 17 pp.
  * [28] C. A. Holt and A. E. Roth, The Nash equilibrium: A perspective. Proceedings of the National Academy of Sciences 101 (2004) 3999–4002.
  * [29] R. Holzman and N. Law-Yone, Strong equilibrium in congestion games, Games and Economic Behavior, 21 (1) (1997) 85–101.
  * [30] N. S. Kukushkin, I. S. Men’shikov, O. R. Men’shikova, and V. V. Morozov, Resource allocation games, Computational Mathematics and Modeling, 1 (4) (1990) 433.
  * [31] I. Milchtaich, Congestion models of competition, The American Naturalist, 147 (5) (1996) 760–783.
  * [32] I. Milchtaich, Congestion games with player-specific payoff functions, Games and Economic Behavior, 13 (1) (1996) 111–124.
  * [33] D. Monderer and L. S. Shapley, Potential games, Games and Economic Behavior, 14 (1) (1996) 124–143.
  * [34] J. F. Nash Jr., Equilibrium points in n-person games, Proceedings of the National Academy of Sciences 36:1 (1950) 48–49.
  * [35] J. F. Nash Jr., Non-cooperative Games, Annals of Math. 54:2 (1951) 286–295.
  * [36] R. W. Rosenthal, A class of games possessing pure-strategy Nash equilibria, International Journal of Game Theory, 2 (1973) 65–67.
  * [37] M. Sharir, A strong-connectivity algorithm and its application in data flow analysis, Comput. Math. Appl. 7 (1981) 67–72.
  * [38] R. E. Tarjan, Depth-first search and linear graph algorithms, SIAM J. Computing 1:2 (1972) 146–160.
  * [39] A. Thomason, Paths and cycles in tournaments, Transactions of AMS 296:1 (1986) 167–180.
  * [40] A. R. Washburn, Deterministic graphical games, J. Math. Analysis and Applications 153 (1990) 84–-96.


[a, b]Leandro Abaroa

#  XMM-Newton observations of the extragalactic microquasar S26 and their
implications for PeV cosmic rays

Gustavo E. Romero  Giulio C. Mancuso  Florencia N. Rizzo

###### Abstract

The extragalactic microquasar S26 has the most powerful jets observed in
accreting binaries, with a kinetic luminosity of $L_{\rm jet}\sim
10^{40}\,{\rm erg\,s^{-1}}$. According to the jet-disk symbiosis model, this
implies that the accretion power to the stellar black hole at the core of the
system should be very super-Eddington, on the order of $L_{\rm acc}\sim L_{\rm
jet}$. However, the observed X-ray flux of this system, measured by the
Chandra and XMM-Newton telescopes, indicates an apparent very sub-Eddington
accretion luminosity of $L_{\rm X}\approx 10^{37}\,{\rm erg\,s^{-1}}$, orders
of magnitude smaller than the jet power. We present here a preliminary
investigation of the relationship between jet and disk power, analyze an X-ray
observation of S26 obtained with XMM-Newton, and propose an explanation for
the emission. We also examine the acceleration and distribution of the
particles to discuss the feasibility of microquasars as potential PeVatron
sources, exploring their ability to produce cosmic rays with energies of about
1 PeV or higher.

##  1 Introduction

S26 is a microquasar (MQ) located in the galaxy NGC 7793, at a distance of 3.9
Mpc [1], whose nebula has a size of $\sim 350\times 185\,{\rm pc}$ [2].
According to observations in the optical/X-ray band, [3] showed that this MQ
has the most powerful jets in accreting binaries, with a mechanical luminosity
of $L_{\rm jet}\sim 5\times 10^{40}\,{\rm erg\,s^{-1}}$, and identified
nonthermal X-rays produced in the core of the system. On the other hand, [4]
resolved the radio lobe structure, and suggested that the radio emission from
the terminal region of the jets is consistent with synchrotron radiation. They
also analyzed X-ray observations from Chandra space telescope, identifying
X-ray hotspots $\approx 20\,{\rm pc}$ farther out than the peak of the radio
intensity in the lobes, and argued that this emission is most likely of
thermal origin.

A key parameter to characterize MQs is the accretion rate of matter onto the
compact object, which proceeds in three basic regimes, depending on the
relation of the actual accretion rate to the Eddington rate. In super-
Eddington regimes, the inner part of the disk launches powerful winds with
mass-loss rates similar to the accretion rate [5]. Following the jet-disk
symbiosis model [6], the kinetic luminosity of the jet of S26 estimated by [3]
implies that the accretion luminosity onto the compact object should be highly
super-Eddington, of the order of $L_{\rm acc}\sim L_{\rm jet}$. However, the
observed X-ray flux from the core of the system, measured by Chandra and XMM-
Newton telescopes, indicates an apparent very sub-Eddington luminosity of
$L_{\rm X}\sim 10^{37}\,{\rm erg\,s^{-1}}$, orders of magnitude smaller than
the jet power.

In this preliminary work, we hypothesize that the compact object is a black
hole of 10 solar masses, accreting at super-Eddington rates, and that its
actual accretion power is a few times $10^{40}\,{\rm erg\,s^{-1}}$ (the
Eddington luminosity for this black hole is $\sim 10^{39}\,{\rm
erg\,s^{-1}}$). We suggest that some energy should also be extracted from the
ergosphere of the spinning black hole to provide enough power for the jet [7].
The emission from the disk is reprocessed in the dense wind of the disk and is
not observable in X-rays. We first analyze the XMM-Newton observation and then
describe our theoretical model for particle acceleration and distribution. We
present our results in Sect. 4 and conclude with some final remarks.

##  2 X-ray observation

We analyzed the XMM-Newton data from obsID 0748390901 obtained on December 10,
2014. The observation was performed in the full frame mode. The data reduction
was done using the Science Analysis System (SAS) software package version
20.0.0 and the High Energy Astrophysics Software (HEASoft). We calibrated,
filtered, and cleaned the event lists by applying the tasks epproc and emproc,
for PN and MOS respectively, using the most up-to-date calibration files. We
then identified and removed periods dominated by high particle background,
defined as a count rate greater than 0.35 ${\rm cts\,s^{-1}}$ for MOS and 0.4
${\rm cts\,s^{-1}}$ for PN.

We selected a circular region of radius 15 arcsec (which corresponds to a
physical distance of $\sim$ 284 pc at the source), centered on
$\alpha$=23h58m00s, $\delta$=–32°33’21” to extract the source spectrum. To
account for the background emission, photons were selected from a source-free
30 arcsec circular region on the same chip as the source. We used the task
evselect to retain source events for spectra with FLAG == 0 and single and
double events with PATTERN <= 4 for the PN camera, and PATTERN <= 12 for the
MOS cameras. We then generated the response matrix file (rmf) and ancillary
response file (arf) using the tasks rmfgen and arfgen, respectively.

We performed the spectral analysis using the XSPEC software v.20.0.0 in the
0.5–6.0 keV energy range. We binned the spectra to have a minimum of 16 counts
per bin to allow for Gaussian statistics in the fit using the specgroup tool.
We applied a model consisting of a power-law and a blackbody component
affected by photoelectric absorption (const*tbabs*(powerlaw + bbody) in
XSPEC). We linked the model parameters across the spectra except for $N_{\rm
H}$, which was frozen to $1.2\times 10^{20}$ cm-2, and the constant factor,
which was fixed to one for PN but allowed to vary freely for the MOS cameras.
The spectrum is shown in Fig. 1 (left plot). This model gave a good fit to the
observed emission, with $\chi^{2}=16.44$ for 19 degrees of freedom. Overall,
the parameters obtained with the PN and MOS cameras are consistent with each
other within errors. The model fit yielded a power-law photon index $\Gamma$
and a blackbody temperature $kT_{\rm bb}$ which are consistent with the values
reported in previous X-ray studies [4]. We obtained a 0.5–6.0 keV unabsorbed
flux of $1.9^{+0.2}_{-0.3}\times 10^{-14}$ $\rm erg\,cm^{-2}\,s^{-1}$, which
corresponds to an unabsorbed luminosity of $\sim 10^{37}$ $\rm erg\,s^{-1}$
for a distance of $d=3.9$ Mpc [1].

Our model suggests that the emission from S26 could have two possible origins,
one thermal and one non-thermal. This is consistent with the results reported
by [4], who showed that the X-ray spectrum of S26 can be modeled by a
combination of thermal and nonthermal components, where the former is
associated with the lobes and the latter with the emission from the core.

##  3 Disk and jet models

We assume that the compact object is a black hole (BH) of mass $M_{\rm
BH}=10\,M_{\odot}$ and accretes matter at a super-Eddington rate at the outer
part of the disk, $\dot{m}=\dot{M}_{\rm input}/\dot{M}_{\rm Edd}\gg 1$, where
$\dot{M}_{\rm input}$ is the input of mass per unit of time. The Eddington
rate is given by $\dot{M}_{\rm{Edd}}=L_{\rm{Edd}}/\eta c^{2}\approx 2.2\times
10^{-8}M_{\rm BH}\,{\rm yr^{-1}}=1.4\times
10^{18}MM_{\odot}^{-1}\,\rm{g\,s^{-1}}$, with $L_{\rm Edd}$ the Eddington
luminosity (defined as the luminosity required to balance the attractive
gravitational pull of the BH by radiation pressure), $\eta\approx 0.1$ the
accretion efficiency, and $c$ the speed of light. The self-regulation of the
inner accretion disk to the Eddington rate results in a total mass-loss rate
in winds $\dot{M}_{\rm w}$ that is approximately equal to the accretion input,
$\dot{M}_{\rm w}\approx\dot{M}_{\rm input}\gg\dot{M}_{\rm Edd}$. In this
supercritical scenario, the disk will be completely covered by the opaque wind
(whose photosphere extends to $z_{\rm photo}\approx 10^{11}\,{\rm cm}$, e.g.,
[8]), so the radiation of the disk can not reach the observer because it is
absorbed and reprocessed in the wind and shifted to lower energies. The
accretion power at a radius $r_{\rm d}$ is given by $L_{\rm acc}(r_{\rm
d})\approx\dot{M}_{\rm acc}(r_{\rm d})\,c^{2}$, where $\dot{M}_{\rm
acc}(r_{\rm d})=\dot{M}_{\rm input}r_{\rm d}/r_{\rm crit}$, with $r_{\rm
crit}\approx 40\dot{m}r_{\rm g}$ the critical radius. This radius corresponds
to the distance to the BH at which the outer standard disk changes to the
inner disk dominated by radiation.

Two jets are generated near the BH in opposite directions, perpendicular to
the orbital plane of the binary system. Following the disk-jet coupling
hypothesis of [6], the kinetic power of each jet, $L_{\rm j}$, is assumed to
be proportional to the accretion power at the magnetically-saturated radius,
$r_{\rm ms}$ (where the poloidal magnetic flux becomes dynamically important),
$L_{\rm j}=q_{\rm j}\,L_{\rm acc}(r_{\rm ms})$, with $q_{\rm j}$ the
efficiency in the transfer of power from the disk to the jet. We assume that
the disk is saturated at a distance from the black hole of $r_{\rm
ms}=100\,r_{\rm g}$. At this radius, the accretion rate is $\dot{M}_{\rm
acc}(r_{\rm ms})=2.5\dot{M}_{\rm Edd}=3.5\times 10^{19}\,{\rm g\,s^{-1}}$, so
the accretion power is $L_{\rm acc}(r_{\rm ms})=3.15\times 10^{40}\,{\rm
erg\,s^{-1}}$. This luminosity is not enough to explain the jet power in S26;
therefore, some energy should also be extracted from the ergosphere of the
spinning black hole [7]. Considering that the jet kinetic luminosity of S26
estimated by [3] is $L_{\rm j}=5\times 10^{40}\,{\rm erg\,s^{-1}}$, then the
efficiency factor in the transformation of accretion into jet power should be
$q_{\rm j}=L_{\rm j}/L_{\rm acc}\approx 1.58$.

We assume that the jets are launched at a distance $z_{0}=100\,r_{\rm g}$ from
the BH with a typical semi-opening angle of $\theta_{\rm j}\approx
5.7^{\circ}$, so the radius-to-height relation at any point is estimated to be
$r_{\rm j}\approx 0.1\,z_{\rm j}$. A fraction $q_{\rm rel}=0.1$ of the jet
power is in the form of relativistic particles, $L_{\rm rel}=q_{\rm
rel}\,L_{\rm j}$, and we include both hadronic and leptonic content, $L_{\rm
rel}=L_{\rm p}+L_{\rm e}$. We assume a hadronic-dominant scenario at the
terminal regions of the jet, $L_{\rm p}=100\,L_{\rm e}$.

Since nonthermal X-rays are detected from the core of S26, recollimation
shocks should take place near the base of the jet, but above the photosphere
of the disk-driven wind to account for the emission, $z_{\rm recoll}>z_{\rm
photo}$. From an order-of-magnitude analysis of the available power, this jet-
disk model may explain the core X-ray luminosity inferred from observations
$(10^{37}\,{\rm erg\,s^{-1}})$ and the jet power $(10^{40}\,{\rm
erg\,s^{-1}})$. The full calculations of the nonthermal processes will be
presented in a forthcoming paper.

At the head of the jet two more shocks are generated: a forward radiative
shock that propagates into the interstellar medium (ISM), and a reverse
adiabatic shock that propagates to the jet and forms the thermal cocoon. In
adiabatic shocks, particles can be accelerated to relativistic energies and
produce nonthermal emission. In radiative shocks, the gas emits large amounts
of thermal radiation. The radii of the shock regions are taken from [3] (we
refer to section 3.3 of [5] for characterization of shocks). In what follows,
we concentrate only on the backward shock region at the head of the jets
–where the radio hotspots were identified by [4]– because we are interested in
MQs as cosmic ray generators.

Figure 1: Left: XSPEC constant*tbabs*(bbody+powerlaw) fitting model of the
spectrum of S26 using XMM-Newton observation 0748390901. The black, red, and
green colors represent the PN, MOS1, and MOS2 cameras, respectively. Right:
power-law distribution of protons that are accelerated in the lobes and escape
from the system. Their maximum energy is of the order of 10 PeV.

##  4 Particle acceleration and distribution

Particles accelerated in the reverse shocks at jet terminal regions of the jet
can cool through different processes and produce nonthermal radiation. The
diffusive acceleration rate of the particles is given by
$t^{-1}_{\rm{acc}}=\eta_{\rm acc}~{}e~{}Z~{}c~{}B/E$, where $e$ is the
electric charge, $Z$ the atomic number, $c$ the speed of light, $B=10\,\mu{\rm
G}$ the magnetic field (which corresponds to that of the compressed ISM), $E$
is the energy of the particle, and $\eta_{\rm acc}=10^{-1}$ the acceleration
efficiency. The maximum energy for each kind of particle can be inferred by
looking at the point where the acceleration rate is equal to the total cooling
or escape rate.

Our model is lepto-hadronic, and so we calculate the following cooling
processes numerically: synchrotron (interaction of protons and electrons with
the ambient magnetic field), inverse Compton (IC, collision of relativistic
electrons with photons of the ambient radiation field), Bremsstrahlung
(Coulombian interactions between relativistic electrons and cold matter),
photo-hadronic interactions (interaction of highly relativistic protons with
photons of the ambient radiation field), and proton-proton (collision of
relativistic protons with cold matter). The number density of cold protons is
$n_{\rm p}\approx 0.7\,{\rm cm^{-3}}$ [3].

We then investigate the evolution of particles that are accelerated at the
reverse shocks in the jet lobes and injected into the ISM. The relativistic
particles have a distribution given by ${\rm d}N=n(\vec{r},E,t){\rm d}E{\rm
d}V$, where $n$ is the number density of particles, $t$ the time, $\vec{r}$
the position, $V$ the volume, and $E$ the energy. The evolution of this
distribution is determined by the transport equation [see e.g., 9]. We solve
this equation numerically in steady state and in the one-zone approximation:
$\partial/\partial E[{\rm d}EN(E)/{{\rm d}t}]+N(E)/t_{\rm esc}=Q(E)$, where
$t_{\rm esc}$ is the escape time, and the particle injection function,
$Q(E)=Q_{0}E^{-p}\exp{(-E/E_{\rm max})}$ is a power-law in the energy with an
exponential cutoff and a spectral index $p=2$, which is characteristic of the
Fermi first-order acceleration mechanism.

Timescales of particles of the reverse shock in the lobes show synchrotron as
the dominant cooling mechanism for leptons, whereas proton-proton interaction
is the dominant cooling mechanism for hadrons. The power-law distribution of
protons is shown in Fig. 1 (right plot). Electrons reach a maximum energy of 5
PeV, while protons are accelerated up to 10 PeV energies. These ultra-
relativistic protons will be injected in the ISM and will in turn spread
through the intergalactic medium, populating with cosmic rays the whole
galaxy.

##  5 Conclusions

We have reduced and analyzed XMM-Newton data of the microquasar S26 and found
that the X-ray emission fits well with a two-component model: black body (soft
emission) plus power-law (hard emission). This is in agreement with previous
analysis of X-ray observations [3, 4]. The detected nonthermal component of
the X-ray radiation could have originated from synchrotron emission from the
core, produced by electrons accelerated at the base of the jet, whereas the
thermal component could be explained with radiation produced by non-
relativistic Bremsstrahlung in the forward shock at the jet-lobes.

We have also proposed that the three-order-of-magnitude difference between the
jet and apparent disk luminosities in S26 is caused by the complete absorption
of the disk radiation by the wind ejected from the super-Eddington disk.
Moreover, we suggest that some of the energy to power the jet must be
extracted from the ergosphere of the spinning black hole. The observed soft
X-ray flux should be then produced near the base of the jet but above the wind
photosphere.

One of the main results of this preliminary work is that protons accelerated
downstream in the lobes reach energies close to 10 PeV and are cooled by $pp$
interactions. These ultra-relativistic protons will in turn spread through the
intergalactic medium, populating with cosmic rays the whole galaxy. Super-
Eddington MQs could be thus considered as potential PeVatron sources.

The cooling timescales, the spectral energy distributions for each radiative
process involved in this system – and their comparison with the observed data
–, as well as a more detailed examination of S26 will be presented in a near-
future work.

## Acknowledgments

LA acknowledges the UNLP and the HEPRO VIII organizers. GER was funded by
PID2022-136828NB-C41/AEI/10.13039/501100011033/ and through the “Unit of
Excellence María de Maeztu 2020-2023” award to the Institute of Cosmos
Sciences (CEX2019-000918-M). Additional support came from PIP 0554 (CONICET).

## References

  * [1] I.D. Karachentsev, E.K. Grebel, M.E. Sharina, A.E. Dolphin, D. Geisler, P. Guhathakurta et al., _Distances to nearby galaxies in Sculptor_ , _aap_ 404 (2003) 93 [astro-ph/0302045].
  * [2] M.A. Dopita, J.L. Payne, M.D. Filipović and T.G. Pannuti, _The physical parameters of the microquasar S26 in the Sculptor Group galaxy NGC 7793_ , _mnras_ 427 (2012) 956 [1208.3500].
  * [3] M.W. Pakull, R. Soria and C. Motch, _A 300-parsec-long jet-inflated bubble around a powerful microquasar in the galaxy NGC 7793_ , _nat_ 466 (2010) 209.
  * [4] R. Soria, M.W. Pakull, J.W. Broderick, S. Corbel and C. Motch, _Radio lobes and X-ray hotspots in the microquasar S26_ , _mnras_ 409 (2010) 541 [1008.0394].
  * [5] L. Abaroa, G.E. Romero and P. Sotomayor, _Supercritical colliding wind binaries_ , _aap_ 671 (2023) A9 [2301.08635].
  * [6] H. Falcke and P.L. Biermann, _The jet-disk symbiosis. I. Radio to X-ray emission models for quasars._ , _aap_ 293 (1995) 665 [astro-ph/9411096].
  * [7] R.D. Blandford and R.L. Znajek, _Electromagnetic extraction of energy from Kerr black holes._ , _mnras_ 179 (1977) 433.
  * [8] L. Abaroa and G.E. Romero, _Super Winds and Radio Emission in X-ray Binary Systems_ , _arXiv e-prints_ (2023) arXiv:2311.15050 [2311.15050].
  * [9] V.L. Ginzburg and S.I. Syrovatskii, _The Origin of Cosmic Rays. Oxford: Pergamon Press._ (1964).