# The Möbius game and other Bell tests for relativity

Eleftherios-Ermis Tselentis  Institute for Quantum Optics and Quantum
Information (IQOQI-Vienna), Austrian Academy of Sciences, 1090 Vienna, Austria
Faculty of Physics, University of Vienna, 1090 Vienna, Austria  Ämin Baumeler
Facoltà di scienze informatiche, Università della Svizzera italiana, 6900
Lugano, Switzerland  Facoltà indipendente di Gandria, 6978 Gandria,
Switzerland

###### Abstract

We derive multiparty games that, if the winning chance exceeds a certain
limit, prove the incompatibility of the parties’ causal relations with any
partial order. This, in turn, means that the parties exert a back-action on
the causal relations; the causal relations are dynamical. The games turn out
to be representable by directed graphs, for instance by an orientation of the
Möbius ladder. We discuss these games as device-independent tests of
spacetime’s dynamical nature in general relativity. To do so, we design a
relativistic setting where, in the Minkowski spacetime, the winning chance is
bound to the limits. In contrast, we find otherwise tame processes with
classical control of causal order that win the games deterministically. These
suggest a violation of the bounds in gravitational implementations. We obtain
these games by uncovering a “pairwise central symmetry” of the correlations in
question. This symmetry allows us to recycle the facets of the acyclic
subgraph polytope studied by Grötschel, Jünger, and Reinelt in the mid-80s for
combinatorial optimization. In addition, we derive multiparty games in a
scenario where the polytope dimension grows only linearly in the number of
parties. Here, exceeding the limits not only proves the dynamical nature of
the causal relations, but also that the correlations are incompatible with any
global causal order.

##  I Introduction

Bell [1], in his seminal work, showed that quantum correlations are causally
inexplicable [2]. Such nonlocal correlations arise as the spontaneous
spacelike separated creation of fresh albeit strongly correlated data [3]. Any
tentative causal explanation of these correlations—without regressing to the
formalism of quantum theory [4]—necessitates an infinite speed of
communication [5, 6, 7] and infinite precision [8]; a clash with relativity.
In order to show his result, Bell employed a device-independent technique. He
derived limits on correlations—expressed via inequalities—from assumptions on
the observed data only, without invoking any specifics of any theory. If
experimental observations exceed these limits i.e., a Bell inequality is
violated, then one is forced to reject one of the assumptions. This is known
as Bell test. Bell inequalities are commonly expressed as collaborative
multiparty games with a bound on the winning probability. Bell’s discovery is
not only considered as one of the most fascinating in quantum theory, but also
substantially boosted the development of quantum information [9, 10]: The
informational abstraction and simplification of quantum mechanics as a theory
of qubits. In this work, we extend Bell’s reasoning to relativity, and obtain
Bell tests to certify the dynamical nature of causal relations. In addition,
this might—similar to the quantum case—aid in the development of a theory of
“gravity information.”

###  I.1 Dynamical and indefinite causal order

Quantum nonlocal correlations, as mentioned above, indicate the central rôle
of causality in unifying quantum theory with relativity. As pointed out by
Hardy [11], there is a complementary aspect that hints at the same. On the one
hand, general relativity is a deterministic theory equipped with a dynamical
spacetime: The causal relations among events depend on the mass-energy
distribution. On the other, quantum theory is a probabilistic theory equipped
with a static spacetime. Therefore, it is expected that a theory of quantum
gravity features indefinite causal order, e.g., by extending quantum
superposition to causal relations [12, 13, 14, 15, 16].

Exemplary, indefinite causal order arises from the celebrated quantum switch
[14] (see Fig. 1). Here, the causal relation between two experiments, Bob’s
and Charlie’s, is coherently controlled by Alice’s experiment in their common
causal past.

AliceBobCharlie Figure 1: The quantum switch: Depending on whether Alice
prepares a control qubit in the state $|0\rangle$ or $|1\rangle$, a target
system $|\psi\rangle$ traverses Bob’s laboratory before Charlie’s or vice
versa. If Alice prepares the control qubit in a superposition state, then the
trajectory of the target system is entangled with the control qubit: The
causal relation between Bob and Charlie is indefinite.

More specifically, Alice may perform an experiment such that Bob’s experiment
is performed before Charlie’s, or another such that Bob’s experiment is
performed after Charlie’s. The causal relation between Bob’s and Charlie’s
experiment is dynamical. If Alice, however, performs both experiments in
superposition, then quantum indefiniteness is injected into the causal
relations, and dynamical causal order is turned into quantum indefinite causal
order. It is well-known [17, 18, 19] that no Bell test can certify the quantum
indefinite causal order as exhibited by the quantum switch and its
generalizations [19]—unless additional assumptions are invoked [16, 20, 21].
This is natural for the following reason. In stark contrast to the Bell
scenario [1] where nonsignaling correlations are established, here, the limits
of communication are of relevance. But in unrestricted settings, all quantum
communication can always be simulated classically.

###  I.2 The Möbius game

In this work, we devise Bell tests for dynamical causal order. Events obey a
non-dynamical, or static, causal order whenever the parties’ actions, which
constitute the events, do not alter the causal relations. In other words,
events obey static causal order whenever the causal relations form a partial
order. A violation of the presented inequalities, that bound the correlations
to respect a static causal order, implies then that the parties altered the
causal relations. These inequalities are—as we will see later—also violated by
the quantum switch. While, as mentioned above, the quantum indefinite nature
of the causal relations in the quantum switch cannot be certified, the
dynamical part indeed can.

These inequalities are the facets of the partial-order-correlation polytope.
It turns out that the minimum of a single output bit suffices to obtain such
Bell test. In fact, the dimension of the polytope grows only quadratically as
$2n(n-1)$ in the number of parties $n$. We find that a projection of the
polytope is the polytope of directed acyclic graphs (DAGs). The latter has
been studied by Grötschel, Jünger, and Reinelt [22] in the mid-80s in the
context of discrete optimization. Moreover, we find that we can lift the
facet-defining inequalities of this DAG polytope to obtain the relevant Bell
games. The key insight for this step is that the polytope of interest is what
we call “pairwise centrally symmetric;” a symmetry that reflects the
possibility of the parties to relabel the output bit.

An example of such a Bell test is represented by a directed Möbius ladder (see
Fig. 2).

Figure 2: A directed Möbius ladder [23]. This graph represents a Bell game for
ten or more parties with which dynamical causal order is detected.

As a preview, the Möbius game is the following. Each vertex on the graph
represents a party. A referee picks at random an arc $(s,r)$ from the graph,
and a bit $x$. Then, the referee broadcast the chosen arc to all parties, and
the bit $x$ to the “sender” $s$ only. The game is won whenever the “receiver”
$r$ outputs $x$. If the winning probability exceed $11/12$, then the parties’
causal arrangement is incompatible with any partial order or mixtures thereof,
and we must conclude that the parties’ actions influenced the causal
relations. In addition to the Möbius game, we find other games represented by
directed graphs. The Möbius game, however, has a clear advantage. The bound of
$11/12$ holds for any finite number of parties involved. In contrast, the
bounds of the other games approach one for an increasing number of parties.
This favorable situation renders the tests reliable, and show that the feature
of dynamical causal order is non-vanishing, as it is the case for nonlocality
[24, 25] and noncausality [26].

###  I.3 Relativity

We apply our results to relativity. Here, we find an arrangement of events,
defined by the crossing of worldlines, such that the derived inequalities are
never violated within special relativity. If the games were played in a
gravitational setting, however, the dynamical spacetime of general relativity
may be certified. In this work, we do not carry out general-relativistic
calculations, but support our claim via the description of classically well-
behaved processes that win these games deterministically. Moreover, these
processes are conservative in the following sense: An event can only influence
its causal future, including the causal relations among the events within its
causal future. Such processes were recently investigated in detail due to
their affinity for physical implementations [19]. If a displacement of matter
in general relativity alters the causal relations of events within the future
lightcone, then these processes may be implemented in general relativity, and
the back-action of matter to the spacetime structure can be certified.

###  I.4 Outline

We start with a description of our notation, and necessary basics on convex
polytopes and graphs. Thereafter, we provide the definition and derive
properties of what we call pairwise centrally symmetric polytopes. This
symmetry refines central symmetry, and is our key-method for the projection
and lifting of the polytopes (in particular, see Theorem 4). After that, we
describe the correlations of interest, and compute the facet-defining Bell
games (see Theorem 9). This is followed by a shorter part where the scenario
is further simplified. While the resulting polytope grows only linearly as
$2n$ in the number of parties $n$, we show that the derived Bell game cannot
distinguish between partial-order and causal correlations (see Theorem 11).
The latter describes correlations where the parties may alter the causal
relations of all parties in their future. Then, we introduce the framework of
processes and causal models, and show how these games are won
deterministically therein (see Theorem 14). This is followed by a discussion
of the results in the context of special and general relativity. We end this
work with conclusions and a series of open questions.

##  II Notation, polytopes, and graphs

We use $[n]$ for the set $\\{0,1,\dots,n-1\\}$, and $[n]^{2}_{\neq}$ for the
set of all distinct pairs over $[n]$, i.e.,
$[n]\times[n]\setminus\\{(k,k)\\}_{k\in[n]}$. Lowercase letters will usually
be used to express values, calligraphic letters sets, and bold letters
matrices and vectors. We simplify the common notation of $P_{A\mid X}$ for a
conditional probability distribution of $A$ given $X$, and $P_{A\mid X}(a|x)$
for the conditional probability that $A$ takes value $a$ with $X$ having value
$x$, by only referring to the probability-density function, e.g., $p(a|x)$. We
may always index the entries of a $d$-dimensional vector $\bm{v}$ with the
natural numbers in $[d]$, i.e., $\bm{v}=(v_{i})_{i\in[d]}$. The vector
$\bm{0}$ is the all-zero vector, $\bm{e}_{i}$ is $\bm{0}$ with a one in
dimension $i$, and $\bm{1}$ is the all-one vector. The dimension of these
vectors is always understood from the context. The symbol $\oplus$ is used for
element-wise addition modulo two. For a collection
$\\{\Delta_{k}\\}_{k\in[n]}$ of objects labeled by $[n]$ and a set
$\mathcal{S}\subseteq[n]$, we use $\Delta_{\mathcal{S}}$ to denote the natural
composition of the elements $\\{\Delta_{k}\\}_{k\in\mathcal{S}}$, e.g., the
expression
$(a_{k})_{k\in\mathcal{S}}\in\bigtimes_{k\in\mathcal{S}}\mathcal{A}_{k}$ may
equally be written as $a_{\mathcal{S}}\in\mathcal{A}_{\mathcal{S}}$. We use
the underlined symbol $\underline{\Delta}$ whenever the set of labels is
$[n]$, and we may write $\underline{a}\in\underline{\mathcal{A}}$. Also, we
use the subscript $\setminus\mathcal{T}$, where $\mathcal{T}\subseteq[n]$ is a
set, for the natural composition over $[n]\setminus\mathcal{T}$. We further
extend this notation in relation to a partial order $\preceq_{\sigma}$ over
$[n]$: The expression $\Delta_{\preceq_{\sigma}k}$ for some $k\in[n]$ denotes
the natural composition over the elements in $\\{i\in[n]\mid
i\preceq_{\sigma}k\\}$, and similarly in the non-reflexive case
$\prec_{\sigma}$.

In this work, we employ the theory of convex polytopes [27]. A convex polytope
$\mathcal{P}\subseteq\mathbb{R}^{d}$ is the convex hull of a finite set of
vectors $\mathcal{S}\subseteq\mathbb{R}^{d}$, denoted by
$\mathcal{P}=\operatorname{conv}(\mathcal{S})$. This is known as its
$V$-representation. Equivalently, $\mathcal{P}$ is the intersection of a
finite set of halfspaces
$\mathcal{P}=\\{\bm{x}\in\mathbb{R}^{d}\mid\bm{A}\bm{x}\leq\bm{z}\\}$ for a
set of $m$ inequalities given by $\bm{A}\in\mathbb{R}^{m\times
d},\bm{z}\in\mathbb{R}^{m}$. This is known as the $H$-representation. Since we
always consider convex polytopes, we sometimes omit the term convex in the
remaining of this work. The dimension $\dim(\mathcal{P})$ of $\mathcal{P}$ is
the dimension of its affine hull $\operatorname{aff}(\mathcal{P})$. The
polytope $\mathcal{P}\in\mathbb{R}^{d}$ is full-dimensional if it is
$d$-dimensional, i.e., if its affine hull is the ambient space. If
$\mathcal{P}$ is full-dimensional, then there exists a unique (up to
multiplication) $H$-representation. A vector $\bm{p}\in\mathcal{P}$ is
extremal if
$\bm{p}\not\in\operatorname{conv}(\mathcal{P}\setminus\\{\bm{p}\\})$. The set
of extremal vectors of $\mathcal{P}$ is $\operatorname{ext}(\mathcal{P})$. If
$\operatorname{ext}(\mathcal{P})\subseteq\\{0,1\\}^{d}$, then $\mathcal{P}$ is
called a $0/1$ polytope. A linear inequality $\bm{w}\cdot\bm{x}\leq c$, with
$\bm{w}\in\mathbb{R}^{d}$ and $c\in\mathbb{R}$, is valid for $\mathcal{P}$
whenever $\forall\bm{p}\in\mathcal{P}:\bm{w}\cdot\bm{p}\leq c$. We represent
inequalities as pairs $(\bm{w},c)$. An inequality $(\bm{w},c)$ is trivial if
$\bm{w}$ contains at most a single nonzero entry, and non-negative if all
entries of $\bm{w}$ are non-negative. If $(\bm{w},c)$ is valid for
$\mathcal{P}$, then
$\mathcal{F}:=\mathcal{P}\cap\\{\bm{p}\in\mathbb{R}^{d}\mid\bm{w}\cdot\bm{p}=c\\}$
is a face of $\mathcal{P}$. Faces of dimension $\dim(\mathcal{P})-1$ are
called facets, and inequalities that give rise to facets are called facet
defining. If
$\bm{c}+\bm{\delta}\in\mathcal{P}\Leftrightarrow\bm{c}-\bm{\delta}\in\mathcal{P}$
for some center $\bm{c}\in\mathcal{P}$, then $P$ is called centrally
symmetric.

We also make extensive use of graph theory [28]. A graph
$G=(\mathcal{V},\mathcal{E})$ consists of a finite and non-empty set of
vertices $\mathcal{V}$ and a set of edges
$\mathcal{E}\subseteq\\{\\{u,v\\}\mid u,v\in\mathcal{V}\\}$. For two graphs
$G$ and $G^{\prime}=(\mathcal{V}^{\prime},\mathcal{E}^{\prime})$, the
Cartesian product $G\times G^{\prime}$ is the graph with the vertices
$\mathcal{V}\times\mathcal{V}^{\prime}$, and
$\\{(u,u^{\prime}),(v,v^{\prime})\\}$ is an edge if and only if either $u=v$
and $(u^{\prime},v^{\prime})\in\mathcal{E}^{\prime}$, or
$u^{\prime}=v^{\prime}$ and $(u,v)\in\mathcal{E}$. Each region bounded by the
edges of a planar graph, i.e., a graph drawn on the plane, is called a face. A
face surrounded by edges is called internal face. A directed graph (digraph
for short) $D=(\mathcal{V},\mathcal{A})$ is a graph where the edges have a
direction, i.e., $\mathcal{V}$ is a finite and non-empty set of vertices, and
$\mathcal{A}\subseteq\mathcal{V}\times\mathcal{V}$ is a set of ordered pairs
called arcs. The order $\operatorname{ord}(G)$ of a graph (digraph) is the
cardinality $|\mathcal{V}|$ of its vertex set. A bipartite graph (digraph) is
two-colorable, i.e., each vertex can be colored with one out of two colors
such that adjacent vertices have different colors. A digraph $D$ is an
orientation of a graph $G$ if there exists an ordering of the elements in each
edge $o(\mathcal{E})$, such that $\mathcal{A}=o(\mathcal{E})$. In a digraph, a
directed path is a sequence of connected arcs
$((v_{0},v_{1}),(v_{1},v_{2}),\dots)$ where no vertex is revisited, and a
directed cycle is a directed path where the last vertex coïncides with the
first. A directed cycle with $k$ arcs is a $k$-cycle. A digraph $D$ is simple
if it does not contain self-loops, i.e., $\forall
v\in\mathcal{V}:(v,v)\not\in\mathcal{A}$. A simple digraph is a directed
acyclic graph (DAG for short), if it does not contain any directed cycles. The
set of all DAGs of order $n$ is $\operatorname{DAG}_{n}$, and the set of all
DAGs is $\operatorname{DAG}$. If
$D^{\prime}=(\mathcal{V}^{\prime},\mathcal{A}^{\prime})$ with
$\mathcal{V}^{\prime}\subseteq\mathcal{V}$ and
$\mathcal{A}^{\prime}\subseteq\mathcal{A}$, then $D^{\prime}$ is a subdigraph
of $D$, and we write $D^{\prime}\subseteq D$. A simple digraph
$D=(\mathcal{V},\mathcal{A})$ of order $n$ may be represented by its adjacency
vector
$\bm{\alpha}(D):=(\alpha_{u,v})_{(u,v)\in[n]^{2}_{\neq}}\subseteq\\{0,1\\}^{n(n-1)}$,
where $\alpha_{u,v}$ is one if $(u,v)\in\mathcal{A}$, and zero otherwise.

Basic graphs are the line graph $L_{n}$ with vertices $[n]$ and edges
$\\{\\{i,i+1\\}\mid i\in[n-1]\\}$, and the complete bipartite graph $K_{m,n}$
with vertices $\\{0\\}\times[m]\cup\\{1\\}\times[n]$ and edges
$\\{\\{(0,u),(1,v)\\}\mid u\in[m],v[n]\\}$. Basic digraphs are the complete
digraph $K^{\text{{d}i}}_{n}$ with vertices $[n]$ and arcs $[n]^{2}_{\neq}$,
and the $k$-cycle digraph $C_{k}$ with vertices $[n]$ and arcs $\\{(i,i+1)\mid
i\in[n-1]\\}\cup\\{(i-1,0)\\}$.

##  III Pairwise central symmetry

As key-method to establish our results, we introduce and study pairwise
centrally symmetric 0/1 polytopes. Pairwise central symmetry is a specific
form of central symmetry in which the dimensions are paired, and the polytope
has a center per pair. For instance, if we pair the first two dimensions, then
there exists a vector $\bm{c}$ in the polytope such that $\bm{c}+(x,y,\bm{0})$
is in the polytope if and only if $\bm{c}-(x,y,\bm{0})$ is. These polytopes
contain a “redundancy” as the manifestation of relabelings.

######  Definition 1 (Pairwise central symmetry).

A 0/1 polytope $\mathcal{P}\subseteq\mathbb{R}^{2d}$ is pairwise centrally
symmetric if and only if there exists a permutation of the dimensions such
that

$\displaystyle\begin{split}&\bm{p}=(\bm{p}_{0},\bm{p}_{1})\in\operatorname{ext}(\mathcal{P})\implies\\\
\forall
i\in[d]:\,&(\bm{p}_{0}\oplus\bm{e}_{i},\bm{p}_{1}\oplus\bm{e}_{i})\in\operatorname{ext}(\mathcal{P})\,.\end{split}$
(1)

By a permutation of the dimensions we mean the following. For each
$2d$-dimensional vector $\bm{p}=(p_{i})_{i\in[2d]}$, we write the entries of
$\bm{p}$ in a specific order $(p_{v_{0}},p_{v_{1}},\dots,p_{v_{2d-1}})$. The
$d$-dimensional constituents $\bm{p}_{0}$ and $\bm{p}_{1}$ are then
$(p_{v_{0}},p_{v_{1}},\dots,p_{v_{d-1}})$ and
$(p_{v_{d}},p_{v_{d+1}},\dots,p_{v_{2d}})$, respectively.

In the following, whenever we refer to a pairwise centrally symmetric
polytope, we understand that the dimensions are permuted in the described way.

We start by showing two basic facts of such polytopes.

######  Lemma 1 (Extension).

The 0/1 polytope $\mathcal{P}\subseteq\mathbb{R}^{2d}$ is pairwise centrally
symmetric if and only if

$\displaystyle\begin{split}&\bm{p}=(\bm{p}_{0},\bm{p}_{1})\in\operatorname{ext}(\mathcal{P})\Longleftrightarrow\\\
\forall\bm{z}\in\\{0,1\\}^{d}:\,&(\bm{p}_{0}\oplus\bm{z},\bm{p}_{1}\oplus\bm{z})\in\operatorname{ext}(\mathcal{P})\,.\end{split}$
(2)

###### Proof.

Iteratively apply Eq. (1). ∎

######  Lemma 2 (Central symmetry).

If $\mathcal{P}\subseteq\mathbb{R}^{2d}$ is a pairwise centrally symmetric 0/1
polytope, then it is also centrally symmetric.

###### Proof.

Let $\bm{c}:=1/2\cdot\bm{1}$ be the center, $\bm{\delta}\in\\{\pm
1/2\\}^{2d}$, and define the vectors
$\bm{p}^{\pm}:=\bm{c}\pm\bm{\delta}\in\\{0,1\\}^{2d}$. Now, we have the
identity $\bm{p}^{+}\oplus\bm{1}=\bm{p}^{-}$: Flipping all bits is equivalent
to subtracting instead of adding $\bm{\delta}$ to the center. Finally, by
Lemma 1 we have
$\bm{p}^{+}\in\operatorname{ext}(\mathcal{P})\Leftrightarrow\bm{p}^{+}\oplus\bm{1}\in\operatorname{ext}(\mathcal{P})$.
∎

Pairwise centrally symmetric 0/1 polytopes have a natural projection.

######  Definition 2 (Projection).

Let $\mathcal{P}\subseteq\mathbb{R}^{2d}$ be a pairwise centrally symmetric
0/1 polytope. We define the corresponding projection map $\pi_{d}$ as

$\displaystyle\pi_{d}:\\{0,1\\}^{2d}$ $\displaystyle\rightarrow\\{0,1\\}^{d}$
(3) $\displaystyle(\bm{v}_{0},\bm{v}_{1})$
$\displaystyle\mapsto\bm{v}_{0}\oplus\bm{v}_{1}\,.$ (4)

The projected polytope is
$\mathcal{Q}:=\operatorname{conv}(\pi_{d}(\operatorname{ext}(\mathcal{P})))$.

This projection cancels the multitude of the extremal vectors which arises
from the arbitrary vectors $\bm{z}$ in Eq. (2).111Pairwise central symmetry
can also be understood through the equivalence relation
$\bm{p}\sim\bm{p}^{\prime}$ defined by
$\bm{p}_{0}\oplus\bm{p}_{1}=\bm{p}^{\prime}_{0}\oplus\bm{p}^{\prime}_{1}$. The
extremal vectors of the natural projection are then representatives of the
equivalence classes.  In fact, all the “information” of $\mathcal{P}$ is
contained in the projection $\mathcal{Q}$:

######  Lemma 3 (Lifting polytope).

Define the parametrized lifting map $\lambda_{\bm{z}}$ for
$\bm{z}\in\\{0,1\\}^{d}$ as

$\displaystyle\lambda_{\bm{z}}:\\{0,1\\}^{d}$
$\displaystyle\rightarrow\\{0,1\\}^{2d}$ (5) $\displaystyle\bm{q}$
$\displaystyle\mapsto(\bm{q}\oplus\bm{z},\bm{z})\,.$ (6)

If $\mathcal{P}\subseteq\mathbb{R}^{2d}$ is a pairwise centrally symmetric 0/1
polytope, and $\mathcal{Q}$ the corresponding projected polytope, then
$\mathcal{P}$ is recovered from $\mathcal{Q}$ via

$\displaystyle\operatorname{ext}(\mathcal{P})=\bigcup_{\bm{z}\in\\{0,1\\}^{d}}\lambda_{\bm{z}}(\operatorname{ext}(\mathcal{Q}))\,.$
(7)

###### Proof.

By Def. 2, the extremal vectors of $\mathcal{Q}$ are
$\pi_{d}(\operatorname{ext}(\mathcal{P}))$. To prove the $\subseteq$
direction, let $\bm{p}=(\bm{p}_{0},\bm{p}_{1})$ be an element in
$\operatorname{ext}(\mathcal{P})$. Now, by taking $\bm{z}=\bm{p}_{1}$, we get
that the right-hand side contains
$\lambda_{\bm{z}}(\pi_{d}(\bm{p}))=\lambda_{\bm{p}_{1}}(\bm{p}_{0}\oplus\bm{p}_{1})=\bm{p}$.
For the reverse direction $\supseteq$, let $\bm{r}=(\bm{r}_{0},\bm{r}_{1})$ be
an element of the right-hand side. This vector arises from some
$\bm{p}=(\bm{p}_{0},\bm{p}_{1})\in\mathcal{P}$ and some $\bm{z}$ through the
identities $\bm{r}_{0}=\bm{p}_{0}\oplus\bm{p}_{1}\oplus\bm{z}$ and
$\bm{r}_{1}=\bm{z}$. Due to Lemma 1 and by setting
$\bm{y}:=\bm{p}_{1}\oplus\bm{z}$, the vector $\bm{r}$ is also an element of
the left-hand side because $(\bm{r}_{0}\oplus\bm{y},\bm{r}_{1}\oplus\bm{y})$
is. ∎

Our main result on pairwise centrally symmetric polytopes is that the facets
of the projected polytope can be recycled:

######  Theorem 4 (Lifting facets).

Let $\mathcal{P}\subseteq\mathbb{R}^{2d}$ be a pairwise centrally symmetric
0/1 polytope, and $\mathcal{Q}$ the corresponding projected polytope. If
$\mathcal{P}$ and $\mathcal{Q}$ are full-dimensional, and if $(\bm{w},c)$ is a
non-negative and non-trivial facet-defining inequality of $\mathcal{Q}$, then
$((\bm{w},-\bm{w}),c)$ is a non-trivial facet-defining inequality of
$\mathcal{P}$.

###### Proof.

First, we show that the lifted inequality is valid for $\mathcal{P}$. Thanks
to Lemma 3, each vector $\bm{p}\in\operatorname{ext}(\mathcal{P})$ can be
expressed as $\lambda_{\bm{z}}(\bm{q})$ for some $\bm{q}\in\mathcal{Q}$ and
some $\bm{z}$, thus

$\displaystyle(\bm{w},-\bm{w})\cdot(\bm{q}\oplus\bm{z},\bm{z})$
$\displaystyle=\sum_{i\in[d]}w_{i}(q_{i}\oplus z_{i}-z_{i})$ (8)
$\displaystyle=\sum_{i\in[d]:z_{i}=0}w_{i}q_{i}+\Delta\,.$ (9)

Since $(\bm{w},c)$ is non-negative, we have $\Delta\leq 0$, and validity is
inherited from the validity of $(\bm{w},c)$ for $\mathcal{Q}$.

In the following, we find $2d$ affinely independent vectors in
$\operatorname{ext}(\mathcal{P})$ that saturate the lifted inequality. These
vectors define a $(2d-1)$ dimensional face of $\mathcal{P}$, a facet of
$\mathcal{P}$. First, note that $(\bm{v},c)$ is facet defining for
$\mathcal{Q}$. Therefore, there exists a family
$\mathcal{T}=\\{\bm{q}_{i}\\}_{i\in[d]}$ of $d$ affinely independent vectors
that saturate the inequality. These vectors lifted with the parameter $\bm{0}$
generate the family
$\mathcal{S}:=\\{\lambda_{\bm{0}}(\bm{q}_{i})\\}_{i\in[d]}=\\{(\bm{q}_{i},\bm{0})\\}_{i\in[d]}$
of $d$ affinely independent vectors in $\mathcal{P}$. These vectors trivially
saturate the lifted inequality: For all $i\in[d]$, we have

$\displaystyle(\bm{w},-\bm{w})\cdot(\bm{q}_{i},\bm{0})=\bm{w}\cdot\bm{q}_{i}=c\,.$
(10)

Now, we need $d$ such vectors in addition. These are obtained by an
appropriate lifting of the extremal vectors. Towards that, we use the
implication which holds for all vectors
$\bm{q}=(q_{i})_{i\in[d]}\in\mathbb{R}^{d}$

$\displaystyle
q_{j}=0\implies\bm{w}\cdot\bm{q}=(\bm{w},-\bm{w})\cdot(\lambda_{\bm{e}_{j}}(\bm{q}))\,;$
(11)

if some $\bm{q}$ has a zero entry in dimension $j$, then lifting that vector
with parameter $\bm{e}_{j}$ yields a vector that produces the same value for
the lifted inequality as $\bm{q}$ for the original. This implication is
immediate:

$\displaystyle(\bm{w},-\bm{w})\cdot(\bm{q}\oplus\bm{e}_{j},\bm{e}_{j})=\sum_{i\in[d]\setminus\\{j\\}}w_{i}q_{i}=\bm{w}\cdot\bm{q}\,.$
(12)

This means that whenever $\bm{q}\in\operatorname{ext}(\mathcal{Q})$ saturates
$(\bm{w},c)$ and has a zero entry in dimension $j$, then
$\lambda_{\bm{e}_{j}}(\bm{q})$ saturates $((\bm{w},-\bm{w}),c)$. Suppose now
there exists a sequence of the vectors in $\mathcal{T}$, such that the $k$th
vector has a zero in dimension $k$, i.e., suppose there exists a function
$f:[d]\rightarrow[d]$, such that $(\bm{q}_{f(k)})_{k}=0$. Then, the additional
$d$ vectors we are looking for are easily obtained:

$\displaystyle\mathcal{S}^{\prime}:=\\{\lambda_{\bm{e}_{k}}(\bm{q}_{f(k)})\\}_{k\in[d]}=\\{(\bm{q}_{f(k)}\oplus\bm{e}_{k},\bm{e}_{k})\\}_{k\in[d]}\,.$
(13)

These vectors saturate the lifted inequality due to Eq. (11), and are affinely
independent (also with respect to $\mathcal{S}$), because each of the vectors
contributes to an otherwise untouched dimension.

What remains to show is that such a function $f$ exists for $\mathcal{T}$.
Towards a contradiction, suppose no such $f$ exists. This means that there
exists a dimension $\ell$ such that $\forall\bm{t}\in\mathcal{T}:t_{\ell}=1$.
Without loss of generality, we take $\ell$ to be the first dimension, i.e.,
$\ell=0$, and we have
$\forall\bm{v}\in\operatorname{aff}(\mathcal{T}):v_{0}=1$. Since
$\operatorname{aff}(\mathcal{T})$ is $(d-1)$-dimensional and the first
dimension is fixed to take value $1$, the vector $(1,\bm{0})$ and every vector
from $\\{(1,\bm{e}_{k})\\}_{k\in[d-1]}$ is in
$\operatorname{aff}(\mathcal{T})$. Moreover, note that $(\bm{w},c)$ is
saturated by any affine combination of the vectors in $\mathcal{T}$. From this
we get that for all $k\in[d-1]$:

$\displaystyle c=\bm{w}\cdot(1,\bm{0})=\bm{w}\cdot(1,\bm{e}_{k})\,,$ (14)

and the inequality $(\bm{w},c)$ must be trivial. ∎

##  IV Bell games

Consider the following general scenario. For $n$-parties $[n]$, each party
$k\in[n]$ receives an input $x_{k}\in\mathcal{X}_{k}$, for some input space
$\mathcal{X}_{k}$, and immediately produces an output
$a_{k}\in\mathcal{A}_{k}$, for some output space $\mathcal{A}_{k}$. The
realization of $a_{k}$ is the physical event $E_{k}$. An input-output behavior
of these parties is described by the conditional probability distribution
$p(\underline{a}|\underline{x})$. We assume that the causal order of the
parties is static, i.e., the events $\\{E_{k}\\}_{k\in[n]}$ form a partial
order $\preceq_{\sigma}$. This means that if $j\not\preceq_{\sigma}i$, then
the output $a_{i}$ is independent of $x_{j}$. In general, the partial order
among the events may depend on some initial randomness, e.g., a coin flip.
This leads to the following definition.222In fact, this definition is
equivalent in asking $p(\underline{a}|\underline{x})$ to decompose with total
orders instead of partial orders.

######  Definition 3 (Partial-order correlations).

The $n$-party correlations $p(\underline{a}|\underline{x})$ are partial-order
correlations if and only if there exists a probability distribution
$p(\sigma)$ over partial orders $\preceq_{\sigma}$ and a family of conditional
probability distributions
$\\{p_{k,\sigma}(a_{k}|a_{\prec_{\sigma}k},x_{\preceq_{\sigma}k})\\}_{k,\sigma}$,
such that

$\displaystyle
p(\underline{a}|\underline{x})=\sum_{\sigma}p(\sigma)\prod_{k\in[n]}p_{k,\sigma}(a_{k}|a_{\prec_{\sigma}k},x_{\preceq_{\sigma}k})\,.$
(15)

###  IV.1 Single-output scenario

We simplify the general scenario to the minimal case of a single bit of
output. The party who produces this single bit of output, however, is selected
by the input.

######  Definition 4 (Single-output scenario).

For $n\geq 2$ parties $[n]$, the input space of party $k\in[n]$ is
$\mathcal{X}_{k}:=[n]^{2}_{\neq}\times\mathcal{Z}_{k}$, where the space
$\mathcal{Z}_{k}$ depends on the input to the $[n]^{2}_{\neq}$ part.
Similarly, the output space $\mathcal{A}_{k}$ depends on the input to the
$[n]^{2}_{\neq}$ part. For $(s,r)\in[n]^{2}_{\neq}$,

$\displaystyle\mathcal{Z}_{k}=\begin{cases}[2]&\text{if }k=s,\\\
\emptyset&\text{otherwise,}\end{cases}\quad\mathcal{A}_{k}=\begin{cases}[2]&\text{if
}k=r,\\\ \emptyset&\text{otherwise.}\end{cases}$ (16)

The input $(s,r)\in[n]^{2}_{\neq}$ is shared with all parties.

Note that the above definition could also be formulated with fixed input
spaces and a special symbol to denote “no input.” Also, one could define the
output space to be the binary space $[2]$ for all parties, and then
marginalize over the non-relevant outputs. Such a definition, however, would
be redundant. Also, note that the shared input space $[n]^{2}_{\neq}$ has an
intuitive rôle: If the shared input is $(s,r)$, then party $s$ has the
additional binary input space and party $r$ has the binary output space; party
$s$ is the “sender” and party $r$ is the “receiver.” It is important to note,
however, that the parties without output are thought of producing a trivial
output. This renders the above-mentioned events $\\{E_{k}\\}_{k\in[n]}$ well-
defined.

In this single-output scenario, the input-output behavior is some conditional
probability distribution $p(a|s,r,x)$ where the pair $(s,r)$ is an input to
every party, $x$ is the binary input to party $s$, and $a$ is the binary
output of party $r$. Such correlations $p(a|s,r,x)$, according to Def. 3, are
partial-order correlations whenever there exists a distribution $p(\sigma)$
over all partial orders, and a family of conditional probability distributions
$\\{p_{r,\sigma}^{\preceq}(a|s,r,x),p_{r,\sigma}^{\not\preceq}(a|s,r)\\}_{r,\sigma}$,
such that they decompose as

$\displaystyle\begin{split}p(a|s,r,x)&=\sum_{\sigma:s\preceq\sigma
r}p(\sigma)p_{r,\sigma}^{\preceq}(a|s,r,x)\\\
+&\quad\sum_{\sigma:s\not\preceq\sigma r}p(\sigma)p_{r,\sigma}^{\not\preceq
r}(a|s,r)\,;\end{split}$ (17)

the output $a$ of the “receiver” $r$ may depend on the bit $x$ only if the
“sender” $s$ is before $r$.

######  Definition 5 (Single-output partial-order correlations).

For $n\geq 2$ parties, the set $\mathcal{C}_{n}$ is the set of all conditional
probability distributions $p(a|s,r,x)$ that decomposed as in Eq. (17).

###  IV.2 Geometric representation

In order to derive the limits on partial-order correlations, we represent the
attainable correlations geometrically. The facet-defining inequalities of the
resulting polytope correspond to the respective Bell games (see Fig. 3).

$\bm{p}$ Figure 3: Schematic of a polytope with a facet-defining inequality.
The shaded region represents the polytope $\mathcal{P}_{n}$ of partial-order
correlations. The line indicates a facet-defining inequality. Every point left
to or on that line satisfies the inequality. In contrast, point $\bm{p}$
violates the inequality. This violation proves $\bm{p}\not\in\mathcal{P}_{n}$.

The geometric representation is obtained by expressing the conditional
probability distributions from the set $\mathcal{C}_{n}$ as vectors. Thanks to
total probability, the characteristic vector of some $p\in\mathcal{C}_{n}$ is
the $2n(n-1)$-dimensional vector of the probability that $a=0$ for each input,
i.e., each $p\in\mathcal{C}_{n}$ is represented by $\bm{\chi}(p)$ with

$\displaystyle\bm{\chi}:\mathcal{C}_{n}$
$\displaystyle\rightarrow\mathbb{R}^{2n(n-1)}$ (18) $\displaystyle p$
$\displaystyle\mapsto(p(0|s,r,x))_{(s,r,x)\in[n]^{2}_{\neq}\times[2]}\,.$ (19)

We state and show some immediate facts.

######  Lemma 5 (Partial-order-correlations polytope $\mathcal{P}_{n}$).

For $n\geq 2$ parties, the set
$\mathcal{P}_{n}:=\bm{\chi}(\mathcal{C}_{n})\subseteq\mathbb{R}^{2n(n-1)}$ is
a full-dimensional 0/1 polytope. We call this set the $n$-party partial-order-
correlations polytope.

###### Proof.

That $\mathcal{P}_{n}$ is a convex 0/1 polytope follows from the fact that
$\bm{\chi}$ is linear, $\mathcal{C}_{n}$ is convex, and any conditional
probability distribution that satisfies Eq. (17) can be written as a convex
combination of deterministic ones. Finally, that $\mathcal{P}_{n}$ is full
dimensional follows from observing that $\mathcal{P}_{n}$ contains the zero
vector and all unit vectors in $\mathbb{R}^{2n(n-1)}$. ∎

Since the parties may arbitrarily relabel the output, the polytope
$\mathcal{P}_{n}$ of interested is moreover pairwise centrally symmetric.

######  Lemma 6 (Pairwise central symmetry).

For $n\geq 2$, the polytope $\mathcal{P}_{n}$ is pairwise centrally symmetric.

###### Proof.

Let $\bm{p}=(p_{s,r,x})_{s,r,x}\in\operatorname{ext}(\mathcal{P}_{n})$, and
partition the vector $\bm{p}$ into the two $n(n-1)$ dimensional vectors
$\bm{p}_{b}=(p_{s,r,x=b})_{s,r}$ by restricting the input $x$ to zero or one.
If for some arbitrary $(\hat{s},\hat{r})\in[n]_{\neq}^{2}$ party $\hat{r}$
flips the output bit $a$, then the resulting vector is as $\bm{p}$ but where
the entries at the coordinates $(\hat{r},\hat{s},0),(\hat{r},\hat{s},1)$ are
flipped. ∎

###  IV.3 Projection of $\mathcal{P}_{n}$

Since the polytope $\mathcal{P}_{n}$ is pairwise centrally symmetric, we know
from Theorem 4 that we can find its facet-defining inequalities by computing
the facets of the projected polytope (see Def. 2)

$\displaystyle\mathcal{Q}_{n}:=\operatorname{conv}(\pi_{n(n-1)}(\operatorname{ext}(\mathcal{P}_{n})))\,.$
(20)

As it turns out, the extremal vectors of $\mathcal{Q}_{n}$ have a simple form.
This allows us to refer to $\mathcal{Q}_{n}$ as the DAG polytope.

######  Lemma 7 (DAG).

For $n\geq 2$, the set of extremal vectors of $\mathcal{Q}_{n}$ equals the set
of the adjacency vectors of all DAGs of order $n$, i.e.,
$\operatorname{ext}(\mathcal{Q}_{n})=\bm{\alpha}(\operatorname{DAG}_{n})$.

###### Proof.

Both sets consist of $(n(n-1))$-dimensional vectors. For the $\subseteq$
inclusion, let $\bm{q}=(q_{s,r})_{s,r}:=\pi_{n(n-1)}(\bm{p})$ for some
extremal vector
$\bm{p}=(\bm{p}_{0},\bm{p}_{1})\in\operatorname{ext}(\mathcal{P}_{n})$. The
vectors $\bm{p}_{b}$ for $b\in\\{0,1\\}$ are $(p_{s,r,x=b})_{(s,r)}$. The
entry $p_{s,r,x}\in\\{0,1\\}$ is the probability that party $r$ outputs $a=0$
on input $(s,r)$ to all parties, and on the additional input $x$ to party $s$.
By the projection $\pi_{n(n-1)}$, the entry $q_{s,r}$ is $p_{s,r,0}\oplus
p_{s,r,1}$; it is zero if the output $a$ is independent of $x$, and $1$
otherwise. Therefore, $\bm{q}$ is the adjacency vector of the digraph
$D=([n],\mathcal{A})$, where $(s,r)\in\mathcal{A}$ if and only if the output
$a$ of the “receiver” $r$ depends on the input $x$ of the “sender” $s$. Since
$\bm{p}$ is the vector representation $\bm{\chi}(p)$ of the partial-order
correlations $p\in\mathcal{C}_{n}$, the $n$ parties that establish these
correlations form a partial order. Now, for any partial order, it is
impossible that the parties influence each other in a cyclic way: The graph
$D$ is a DAG.

For the reverse direction $\supseteq$, let $D=([n],\mathcal{A})$ be a DAG. In
the following, we construct partial-order correlations $p\in\mathcal{C}_{n}$,
such that the corresponding vector $\bm{q}$ is $\bm{\alpha}(D)$. First, we
find a partial order $\preceq_{\sigma}$, such that $D$ is compatible with
$\preceq_{\sigma}$ in the following sense: if $(u,v)\in\mathcal{A}$, then
$u\preceq_{\sigma}v$. Such a partial order can, for instance, be obtained from
the transitive closure of the arcs. Now, the strategies of the parties are: On
input $(u,v)$, the “receiver” $v$ outputs $a=0$ whenever
$(u,v)\not\in\mathcal{A}$, and $a=x$ otherwise. In the former case, the
“receiver” $v$ outputs $a=0$ even if $u\preceq_{\sigma}v$—the receiver simply
ignores any potential information on $x$. In the latter case, the arc $(u,v)$
implies that the “sender” $u$ is in the causal past of $v$, and therefore, $u$
might communicate the value of $x$ to $v$. These strategies yield the vector
$\bm{p}=(p_{u,v,x})_{u,v,x}$ with

$\displaystyle p_{u,v,x}=\begin{cases}1&(u,v)\not\in\mathcal{A}\,,\\\
1&(u,v)\in\mathcal{A}\wedge x=0\,,\\\ 0&(u,v)\in\mathcal{A}\wedge
x=1\,.\end{cases}$ (21)

Therefore, the parity $p_{u,v,0}\oplus p_{u,v,1}$ is one if
$(u,v)\in\mathcal{A}$, and zero otherwise:
$\bm{q}=\pi_{n(n-1)}(\bm{p})=\bm{\alpha}(D)$. ∎

###  IV.4 The acyclic-subdigraph polytope

The (unweighted) acyclic-subdigraph problem in combinatorial optimization is
the following: Given a digraph $D=(\mathcal{V},\mathcal{A})$, find a DAG
subdigraph $D^{\prime}$ of $D$ which maximizes the number of arcs. The dual of
this problem is known as the minimum-feedback-arc-set problem. Algorithms to
these problems are of practical relevance in e.g., voting, ranking, and task
scheduling [29, p. 57–61]. One can associate to every instance of such a
problem a polytope with the solutions as extremal points. The representation
of the polytope in terms of linear inequalities allows for the application of
linear-programming techniques. The polytope for the acyclic-subdigraph problem
is as follows:

######  Definition 6 (Acyclic-subdigraph polytope [22]).

Given a digraph $D=(\mathcal{V},\mathcal{A})$, the acyclic-subdigraph polytope
is

$\displaystyle\operatorname{AC}(D):=\operatorname{conv}(\\{\bm{\alpha}(D^{\prime})\mid\operatorname{DAG}\ni
D^{\prime}\subseteq D\\})\,.$ (22)

Thus, the polytope $\mathcal{Q}_{n}$ of our interest is
$\operatorname{AC}(K_{n}^{\text{di}})$, and we have

$\displaystyle\operatorname{ext}(\mathcal{Q}_{n})=\operatorname{ext}(\operatorname{AC}(K_{n}^{\text{di}}))=\bm{\alpha}(\operatorname{DAG}_{n})\,.$
(23)

Grötschel, Jünger, and Reinelt [22] derive a series of facet-defining
inequalities for $\operatorname{AC}(D)$, and hence, also for
$\mathcal{Q}_{n}$. Before we restate these inequalities, we define two classes
of digraphs. Note that the graphs in both classes are bipartite.

$(0,0)$$(1,0)$$(0,1)$$(1,1)$$(0,2)$$(1,2)$$(0,3)$$(1,3)$$(0,4)$$(1,4)$ Figure
4: The $5$-fence digraph with its two-coloring.
$(0,0)$$(1,0)$$(0,2)$$(1,2)$$(0,4)$$(1,4)$$(0,1)$$(1,1)$$(0,3)$$(1,3)$ Figure
5: The $5$-Möbius digraph with its two-coloring.

######  Definition 7 ($k$-fence and $k$-Möbius digraph).

The  $k$-fence digraph for $k\geq 2$ (see Fig. 4) is the orientation of
$K_{k,k}$ where $\\{(0,i),(1,i)\\}$ is oriented as $((0,i),(1,i))$, and all
remaining edges are oriented as $((1,i),(0,j))$, i.e., it has the vertex set
$\\{0,1\\}\times[k]$, and the arcs

$\displaystyle\Big{\\{}((0,i),(1,i)),((1,i),(0,j))\,\Big{|}\,(i,j)\in[k]^{2}_{\neq}\Big{\\}}\,.$
(24)

The  $k$-Möbius digraph (see Fig. 5) is defined for odd $k\geq 3$ only, and it
is the orientation of the $k$-ladder $L_{2}\times L_{k}$ such that
$\\{(0,0),(1,0)\\}$ is oriented as $((0,0),(1,0))$, the arcs adjacent to every
internal face form a four-cycle, and has the “crossing” arcs
$\\{((1,0),(0,k-1)),((1,k-1),(0,0))\\}$ in addition, i.e., it has the vertex
set $\\{0,1\\}\times[k]$ and the arcs

$\displaystyle\begin{split}&\Big{\\{}\big{(}(x,i+\gamma y),(y,i+\gamma(x\oplus
1))\big{)}\,\Big{|}\,\\\ &\quad i\in[k],i\text{
odd},x,y\in\\{0,1\\},\gamma\in\\{\pm 1\\}\Big{\\}}\;\cup\\\
&\Big{\\{}((1,0),(0,k-1)),((1,k-1),(0,0))\Big{\\}}\,.\end{split}$ (25)

Note that the $2$-fence digraph is isomorphic to the $4$-cycle digraph, and
that the $3$-fence digraph is isomorphic to the $3$-Möbius digraph. Also, the
$k$-Möbius digraph is an orientation of the $2k$-Möbius ladder defined in Ref.
[23].

For the following theorem, we need the notion of trivial embedding. Let
$D=(\mathcal{V}\subseteq[n],\mathcal{A})$ be some digraph. We can always embed
$D$ in a digraph $D^{\uparrow n}:=([n],\mathcal{A})$ of order $n$ by extending
the set of vertices from $\mathcal{V}$ to $[n]$, and by keeping the set of
arcs $\mathcal{A}$.

######  Theorem 8 (Facet-defining inequalities [22]).

For $n\geq 2$, let $D=(\mathcal{V}\subseteq[n],\mathcal{A})$ be some digraph.

If $D$ is isomorphic to the $k$-cycle digraph $C_{k}$, then the  $k$-cycle
inequality $(\bm{\alpha}(D^{\uparrow n}),k-1)$ is facet-defining for
$\mathcal{Q}_{n}$.

If $D$ is isomorphic to the $k$-fence digraph, then the  $k$-fence inequality
$(\bm{\alpha}(D^{\uparrow n}),k^{2}-k+1)$ is facet-defining for
$\mathcal{Q}_{n}$.

If $D$ is isomorphic to the $k$-Möbius digraph, then the  $k$-Möbus inequality
$(\bm{\alpha}(D^{\uparrow n}),(5k-1)/2)$ is facet-defining for
$\mathcal{Q}_{n}$.

Many variations of these facet-defining inequalities are known (see Ref. [30]
for a list). While Theorem 4 holds for all facet-defining inequalities of the
polytope $Q_{n}$, we only focus on these simple forms.

We briefly discuss these inequalities. For the digraph
$D=([3],\\{(0,1),(1,0),(2,0),(2,1)\\})$ (see Fig. 6(a)),

$2$$0$$1$ (a)

$0$$4$$2$$3$$1$$5$ (b)

Figure 6: (a) The digraph $D$ on top of the $2$-cycle digraph $C_{2}$. (b) A
weighted digraph (dotted arcs have weight 1/2) on top of the $3$-fence
digraph.

the vector $\bm{\alpha}(D)$ is not in the polytope $\mathcal{Q}_{3}$
(obviously, $D$ is not a DAG), because the $2$-cycle inequality is violated:

$\displaystyle\bm{\alpha}(C_{2}^{\uparrow 3})\cdot\bm{\alpha}(D)=2>1\,.$ (26)

The scalar product in the evaluation of the inequality corresponds to counting
the number of the arcs simultaneously present in both digraphs. For another
illustration, let $\bm{v}$ be the vector that corresponds to the uniform
mixture of two digraphs $(\bm{\alpha}(D_{0})+\bm{\alpha}(D_{1}))/2$, where
$D_{0}$ is isomorphic to the $3$-fence digraph, shown in Fig. 6(b), and
$D_{1}$ is the same digraph with the vertical arcs $\\{(0,3),(1,4),(2,5)\\}$
missing.333The vector $\bm{v}$ can be understood as the adjacency vector of a
weighted digraph. First, note that $\bm{v}$ violates the $3$-fence inequality:

$\displaystyle\bm{\alpha}(D_{0})\cdot\bm{v}=7.5>7\,.$ (27)

However, the vector $\bm{v}$ does not violate any $k$-cycle inequality. For
instance, consider digraph $\hat{C}$ with the arcs
$\\{(0,3),(3,1),(1,4),(4,0)\\}$ and vertices $\\{0,1,\dots,5\\}$. When we
evaluate the corresponding $4$-cycle inequality, we obtain

$\displaystyle\bm{\alpha}(\hat{C})\cdot\bm{v}=3\leq 3\,;$ (28)

the inequality is satisfied. This illustrates that the $k$-cycle inequalities
are insufficient to single out the DAG polytope $\mathcal{Q}_{n}$. For $0/1$
vectors $\bm{v}\in\\{0,1\\}^{n(n-1)}$ the $k$-cycle inequalities are—by
definition—sufficient to detect whether $\bm{v}$ corresponds to the adjacency
vector of a DAG or not. This insufficiency for non-$0/1$ vectors means that
the DAG polytope has additional structure that emerges with increasing order
(see also Refs. [22, 29]).

###  IV.5 Partial-order inequalities

We introduce the concept of a digraph game:

######  Definition 8 (Digraph game).

For $n$ parties $[n]$ and a digraph $D=(\mathcal{V}\subseteq[n],\mathcal{A})$,
the digraph game $\Gamma(n,D)$ is as follows. First, a referee picks at random
an arc $(s,r)$ from $\mathcal{A}$, and a bit $x\in\\{0,1\\}$. Then, the
referee announces $(s,r)$ to all parties $[n]$, and in addition, distributes
$x$ to party $s$. We say that the $n$ parties win the game $\Gamma(n,D)$
whenever the output of party $r$ equals $x$, and denote this event by
$\mathcal{W}(\Gamma(n,D))$.

We may now combine all previous lemmas with Theorem 8, and obtain Bell games
with which dynamical causal relations among the parties are detected.

######  Theorem 9 (Bell games).

Consider $n$ parties $[n]$ and a digraph
$D=(\mathcal{V}\subseteq[n],\mathcal{A})$. If $(\bm{\alpha}(D^{\uparrow
n}),c)$ is a facet-defining inequality of $\operatorname{DAG}_{n}$, then the
maximum winning probability of the game $\Gamma(n,D)$ with partial-order
correlations is bounded by

$\displaystyle\max_{p\in\mathcal{C}_{n}}\Pr[\mathcal{W}(\Gamma(n,D))]\leq\frac{1}{2}+\frac{c}{2|\mathcal{A}|}\,.$
(29)

In particular, if $D$ is isomorphic to the $k$-cycle digraph, then the bound
is $1-\frac{1}{2k}$, if $D$ is isomorphic to the $k$-fence digraph, then the
bound is $1-\frac{k-1}{2k^{2}}$, and if $D$ is isomorphic to the $k$-Möbius
digraph, then the bound is $1-\frac{k+1}{12k}$. Each of these inequalities is
facet defining for the partial-order-correlations polytope $\mathcal{P}_{n}$.

###### Proof.

The set of single-output correlations among $n$ partially ordered parties
forms a polytope $\mathcal{P}_{n}$ (Lemma 5) which is pairwise centrally
symmetric (Lemma 6). By applying the natural projection (Def. 2), we obtain
the polytope $\mathcal{Q}_{n}$ where all extremal vectors are the adjacency
vectors of DAGs (Lemma 7). From Theorem 8, we get the facet-defining
inequalities for $\mathcal{Q}_{n}$. All these inequalities are non-trivial and
non-negative, and the lifting theorem (Theorem 4) is applicable. Therefore, in
the respective cases where $D^{\uparrow n}$ is the trivial embedding of a
$k$-cycle, $k$-fence, or $k$-Möbius digraph, we have as facet-defining
inequalities for $\mathcal{P}_{n}$ the $k$-cycle inequality
$((\bm{\alpha}(D^{\uparrow n}),-\bm{\alpha}(D^{\uparrow n})),k-1)$, the
$k$-fence inequality $((\bm{\alpha}(D^{\uparrow n}),-\bm{\alpha}(D^{\uparrow
n})),k^{2}-k+1)$, and the $k$-Möbius inequality $((\bm{\alpha}(D^{\uparrow
n}),-\bm{\alpha}(D^{\uparrow n})),(5k-1)/2)$.

Now, let $p\in\mathcal{C}_{n}$ be some single-output partial-order
correlations, set $\bm{p}$ as its characteristic vector, and let
$((\bm{\alpha}(D^{\uparrow n}),-\bm{\alpha}(D^{\uparrow n})),c)$ be a facet-
defining inequality from above. In evaluating the inequality with respect to
$\bm{p}$, we get

$\displaystyle(\bm{\alpha}(D^{\uparrow n}),-\bm{\alpha}(D^{\uparrow
n}))\cdot\bm{p}$ (30)
$\displaystyle=\sum_{(s,r)\in\mathcal{A}}p(0|s,r,0)-\sum_{(s,r)\in\mathcal{A}}p(0|s,r,1)$
(31)
$\displaystyle=\sum_{(s,r)\in\mathcal{A}}\left(p(0|s,r,0)-(1-p(1|s,r,1))\right)$
(32) $\displaystyle=\sum_{\begin{subarray}{c}x\in\\{0,1\\}\\\
(s,r)\in\mathcal{A}\end{subarray}}p(x|s,r,x)-|\mathcal{A}|\leq c\,.$ (33)

By moving $|\mathcal{A}|$ to the right side, and by multiplying the inequality
with the uniform probability for the referee announcing $(s,r)$ and $x$, we
get

$\displaystyle\Pr[a=x]\leq\frac{|\mathcal{A}|+c}{2|\mathcal{A}|}\,.$ (34)

Finally, we obtain the stated bounds by noting that the $k$-cycle digraph has
$|\mathcal{A}|=k$, the $k$-fence digraph has $|\mathcal{A}|=k^{2}$, and the
$k$-Möbius digraph has $|\mathcal{A}|=3k$. ∎

Note that for increasing $k$, the bounds for the $k$-cycle and the $k$-fence
games approach one; they may be won with partial-order correlations. In
contrast, the winning chance of the $k$-Möbius game under the same conditions
never exceeds $11/12$. This elevates the $k$-Möbius game as a preferred and
robust test for dynamical causal order, and shows that dynamical causal order
might be unlimited: That feature does not vanish for large numbers of events.
The same quality has been observed for nonlocal correlations [24, 25] and non-
causal correlations [26].

###  IV.6 Partial-order and causal inequalities

Causal inequalities, similar to partial-order inequalities, limit the
correlations among $n$ parties under the assumption of a global, possibly
dynamical, causal order. Here, in contrast with partial-order inequalities, a
party may influence the causal relations of the parties in its causal future.
Clearly, partial-order correlations are a subset of the causal ones. Causal
inequalities have been extensively studied in the context of indefinite causal
order (see, e.g., Refs. [13, 31, 17, 32, 33, 18, 26]). While we are mainly
concerned about partial-order inequalities, we nevertheless introduce causal
correlations and the respective inequalities. The reason is that they coïncide
with the former for an even simpler scenario than studied above. Moreover, we
recover a Bell game that was studied in Ref. [34].

First, we introduce causal correlations in the general setting.

######  Definition 9 (Causal correlations).

The $n$-party correlations $p(\underline{a}|\underline{x})$, where $x_{k}$ is
the input to party $k$, and $a_{k}$ is the output from party $k$, are causal
if and only if they decomposed as

$\displaystyle
p(\underline{a}|\underline{x})=\sum_{i\in[n]}p(i)p(a_{i}|x_{i})p_{a_{i},x_{i}}^{i}(a_{\setminus\\{i\\}}|x_{\setminus\\{i\\}})\,,$
(35)

where $p(i)$ is a probability distribution over $[n]$, and
$p_{a_{i},x_{i}}^{i}(a_{\setminus\\{i\\}}|x_{\setminus\\{i\\}})$ are
$(n-1)$-party causal correlations.

In this recursive definition, party $i$ acts “first” (hence, its output may
only depend on its input). The remaining parties have access to
$i,a_{i},x_{i}$, but again, there exists a party that acts “first.” The
selection of that party may depend on $i$, $a_{i}$, and $x_{i}$.

In the single-output scenario (Def. 4) studied above, the input $(s,r)$
specifies the output-providing party $r$ and the party $s$ who gets the
additional input $x$. Instead, one can neglect $s$, and provide $x$ to every
party, except—to make it non-trivial—to party $r$.

######  Definition 10 (All-to-one scenario).

For $n\geq 2$ parties $[n]$, the input space of party $k\in[n]$ is
$\mathcal{X}_{k}:=[n]\times\mathcal{Z}_{k}$, where the space $\mathcal{Z}_{k}$
depends on the input to the $[n]$ part. Similarly, the output space
$\mathcal{A}_{k}$ depends on the input to the $[n]$ part. For
$r\in\mathcal{[}n]$,

$\displaystyle\mathcal{Z}_{k}=\begin{cases}[2]&\text{if }k\neq r,\\\
\emptyset&\text{otherwise,}\end{cases}\quad\mathcal{A}_{k}=\begin{cases}[2]&\text{if
}k=r,\\\ \emptyset&\text{otherwise.}\end{cases}$ (36)

The input to the $[n]$ part is shared with all parties, and the input to the
$\mathcal{Z}_{k}$ part is shared with all parties but $r$.

As above, one can define the set of partial-order correlations
$\mathcal{C}^{\text{all-to-1}}_{n}$ for this simplified scenario and study the
polytope $\mathcal{P}^{\text{all-
to-1}}_{n}:=\bm{\chi}^{\prime}(\mathcal{C}^{\text{all-
to-1}}_{n})\in\mathbb{R}^{2n}$, and likewise for causal correlations. Here,
the characteristic vector of some conditional probability distribution
$p\in\mathcal{C}^{\text{all-to-1}}_{n}$ is obtained from

$\displaystyle\bm{\chi}^{\prime}:\mathcal{C}^{\text{all-to-1}}_{n}$
$\displaystyle\rightarrow\mathbb{R}^{2n}$ (37) $\displaystyle p$
$\displaystyle\mapsto(p(0|r,x))_{(r,x)\in[n]\times[2]}\,.$ (38)

Note that in both cases, partial-order and causal, the output $a$ of party $r$
must be independent of $x$ only if $r$ is first in the partial, respectively
causal order. Hence, we arrive at the following statement, which is trivial to
prove.

######  Lemma 10 (All-to-one partial-order and causal correlations).

For $n$ parties $[n]$, the correlations $p(a|r,x)$, where $a$ is the output of
party $r$, $r$ is the input to every party, and $x$ is an input to the parties
$[n]\setminus\\{r\\}$, are partial-order correlations if and only if there
exists a distribution $p(k)$ over all parties, and a family of conditional
probability distributions
$\\{p_{r}^{\not\preceq}(a|r),p_{r}^{\preceq}(a|r,x)\\}_{r}$, such that

$\displaystyle
p(a|r,x)=p(r)p_{r}^{\not\preceq}(a|r)+(1-p(r))p_{r}^{\preceq}(a|r,x)\,.$ (39)

These correlations are causal correlations if and only if the same
decomposition exists.

We directly present our result. In the proof, we again exploit the property of
pairwise central symmetry. The projected polytope, as shown in the proof,
turns out to be the faulty hypercube.

######  Theorem 11 (All-to-one Bell game).

For $n\geq 2$ parties $[n]$, a referee picks uniformly at random a “receiver”
$r\in[n]$, and a bit $x\in\\{0,1\\}$, and distributes $r$ to every party, and
$x$ to every party but $r$. The inequality

$\displaystyle\Pr[a=x]\leq 1-\frac{1}{2n}$ (40)

is facet-defining for $\mathcal{P}^{\text{{all-to-1}}}_{n}$.

###### Proof.

The set $\mathcal{P}^{\text{{all-to-1}}}_{n}$ is a full-dimensional convex 0/1
polytope in $\mathbb{R}^{2n}$, where a vector
$\bm{p}=(p_{r,x})_{(r,x)\in[n]\times\\{0,1\\}}$ is a list of the probability
that party $r$ outputs $a=0$ on input $r$ to all parties and input $x$ to the
parties $[n]\setminus\\{r\\}$. This polytope is pairwise centrally symmetric,
where $p_{0}=(p_{r,0})_{r\in[n]}$, and $p_{1}=(p_{r,1})_{r\in[n]}$, for the
same reason as $\mathcal{P}_{n}$ is: Each party might relabel the output. We
apply the projection map (Def. 2) to obtain the polytope
$\mathcal{Q}^{\text{{all-
to-1}}}_{n}:=\operatorname{conv}(\pi_{n}(\operatorname{ext}(\mathcal{P}^{\text{{all-
to-1}}}_{n})))\subseteq\mathbb{R}^{n}$. As it turns out, this polytope is the
faulty $n$-cube

$\displaystyle\operatorname{ext}(\mathcal{Q}^{\text{{all-
to-1}}}_{n})=\\{0,1\\}^{n}\setminus\bm{1}\,.$ (41)

To see this, let $\bm{q}=(q_{r})_{r\in[n]}=\pi_{n}(\bm{p})$ be an element of
the left-hand side. The entries of this vector are $q_{r}=p_{r,0}\oplus
p_{r,1}$. The entry $q_{r}$ is zero if the output $a$ of party $r$ does not
depend on $x$, and is one otherwise. Since $\bm{q}$ arises from a partial
ordering of the parties, we have that there always must exist a party $r^{-}$
that is minimal with respect to that partial order. The entry $q_{r^{-}}$ must
be zero, and therefore $\bm{q}\neq\bm{1}$. For the converse, let
$\bm{v}=(v_{r})_{r\in[n]}$ be a vertex of the faulty $n$-cube, and suppose
that for $r_{0}\in[n]$ we have $v_{r_{0}}=0$. Now, take the partial order
$\preceq_{\sigma}$ where $r_{0}$ is minimal, i.e., for all
$r^{\prime}\in[n]\setminus\\{r_{0}\\}$, the relation
$r_{0}\preceq_{\sigma}r^{\prime}$ holds. From this, we can construct the
following strategy. If the selected party $r$ to make the guess is $r_{0}$,
then party $r_{0}$ outputs $a=0$. In the alternative case, where $r\neq
r_{0}$, party $r_{0}$ receives $x$ from the referee and forwards $x$ to party
$r$. Finally, party $r$ outputs $a=q_{r}x$.

The faulty hypercube has a single non-trivial facet, which is defined by the
inequality $(\bm{1},n-1)$. This facet-defining inequality is non-negative, and
therefore, we apply our facet-lifting theorem, and obtain the facet-defining
inequality $((\bm{1},-\bm{1}),n-1)$ for the polytope $\mathcal{P}^{\text{{all-
to-1}}}_{n}$. At last, this inequality

$\displaystyle(\bm{1},-\bm{1})\cdot(\bm{p}_{0},\bm{p}_{1})$
$\displaystyle=\sum_{r\in[n]}p(0|r,0)-\sum_{r\in[n]}p(0|r,1)$ (42)
$\displaystyle=\sum_{\begin{subarray}{c}x\in\\{0,1\\}\\\
r\in[n]\end{subarray}}p(x|r,x)-n$ (43) $\displaystyle\leq n-1$ (44)

is turned into the Bell game as stated. ∎

##  V Causal models

We present strategies with which the presented games are won. In contrast to
the device-independent approach that we followed until now, we give a physical
description of the parties, how they are interlinked, and their actions. This
description is given in terms of causal models. We start with a brief
introduction to this framework. The interested reader may consult Refs. [35,
34] for details.

###  V.1 Framework

Consider a setup with $n$ parties $[n]$. Each party $k\in[n]$ is composed out
of a past boundary and a future boundary (see Fig. 7(a)). Party $k$ receives a
physical system on the past boundary. The physical system is in a state from
the set $\mathcal{I}_{k}$. After receiving that system, party $k$ carries out
an experiment on that system, and releases a system to the future boundary.
The released system is in a state from the set $\mathcal{O}_{k}$. In a
classical-deterministic world, the experiment carried out by party $k$ is a
function $\mu_{k}:\mathcal{I}_{k}\rightarrow\mathcal{O}_{k}$. Party $k$,
additionally, may choose a specific experiment based on some experimental
setting $x_{k}\in\mathcal{X}_{k}$. The experiment may also produce some
experimental result $a_{k}\in\mathcal{A}_{k}$. Thus, in this general setting,
the experiment of party $k$ is some function
$\mu_{k}:\mathcal{X}_{k}\times\mathcal{I}_{k}\rightarrow\mathcal{A}_{k}\times\mathcal{O}_{k}$.

$x_{k}$$a_{k}$$\mathcal{O}_{k}$$\mathcal{I}_{k}$ (a)

012$\omega$ (b)

Figure 7: (a) Party $k$ receives a system, performs an experiment $\mu_{k}$
with experimental setting $x_{k}$, observes the experimental result $a_{k}$,
and releases a system back to the environment. (b) Three parties interlinked
by the environment (some process $\omega$).

The $n$ parties are interlinked through the environment (see Fig. 7(b)). The
environment takes the physical systems on the future boundaries of the
parties, and provides systems to their past boundaries. Thus, the environment
is a function
$\omega:\underline{\mathcal{O}}\rightarrow\underline{\mathcal{I}}$. If we do
not request the parties to be situated at some specific locations, but instead
assume that each party carries out their experiment exactly once, and that the
parties may only communicate through the environment, we arrive at the
following description of a process.

######  Theorem 12 (Process [36]).

The function
$\omega:\underline{\mathcal{O}}\rightarrow\underline{\mathcal{I}}$ is a
classical-deterministic process if and only if

$\displaystyle\begin{split}\forall(\mu_{k})_{k\in[n]}&\in(\\{\mathcal{I}_{k}\rightarrow\mathcal{O}_{k}\\})_{k\in[n]},\,\exists!\underline{i}\in\underline{\mathcal{I}}:\\\
\underline{i}&=\omega(\underline{\mu}(\underline{i}))\,,\end{split}$ (45)

where $\exists!$ is the uniqueness quantifier.

This theorem follows from the process-matrix framework [13], and states that
irrespective of the experiment carried out by the parties, the state of the
input system is well-defined. For a process $\omega$ and a choice of
experiments, the observed statistics are

$\displaystyle
p(\underline{a}|\underline{x})=\sum_{\underline{i},\underline{o}}[\omega(\underline{o})=\underline{i}][(\underline{a},\underline{o})=\underline{\mu}(\underline{x},\underline{i})]\,,$
(46)

where we use $[i=j]$ for the Kronecker delta $\delta_{i,j}$. Satisfying the
law of total probability, this expression returns one for experiments without
settings and results.

This notion of process is neatly combined with the notion of causal models. A
causal model is a pair: The causal structure, which is a digraph
$M=(\mathcal{W},\mathcal{S})$ with parties $\mathcal{W}$, and the model
parameters, which are a family of functions
$\\{\omega_{k}:\mathcal{O}_{\operatorname{Pa}_{M}(k)}\rightarrow\mathcal{I}_{k}\\}_{k\in[n]}$.
Here,
$\operatorname{Pa}_{M}(k):=\\{p\mid(p,k)\in\mathcal{S}\\}\subseteq\mathcal{W}$
denotes the set of parents of the vertex $k\in\mathcal{W}$ with respect to the
digraph $M$. By combining processes with causal models, we arrive at the
following, where the connections among the parties are faithfully represented
by the causal structure and where the model parameters are consistent in the
sense that the laws of probability are conserved.

######  Definition 11 (Faithful and consistent causal model [34]).

The causal structure $M$ and the model parameters
$\\{\omega_{k}:\mathcal{O}_{\operatorname{Pa}_{M}(k)}\rightarrow\mathcal{I}_{k}\\}_{k\in[n]}$
form a faithful and consistent causal model if and only if for each vertex
$k\in\mathcal{W}$, the model parameter $\omega_{k}$ depends on every argument,
i.e.,

$\displaystyle\forall p\in\operatorname{Pa}_{M}(k),\,$ $\displaystyle\exists
o\in\mathcal{O}_{\operatorname{Pa}_{M}(k)\setminus\\{p\\}},\,o_{0},o_{1}\in\mathcal{O}_{p}:$
(47) $\displaystyle\omega_{k}(o,o_{0})\neq\omega_{k}(o,o_{1})\,,$ (48)

and the function $\omega=(\omega_{k})_{k\in[n]}$ is a classical-deterministic
process.

Given a causal structure $M$, we build a causal model by defining some natural
model parameters, the veto model parameters, where we use
$\operatorname{Ch}_{M}(k):=\\{v\mid(k,v)\in\mathcal{S}\\}\subseteq\mathcal{W}$
to denote the set of children of the vertex $k\in\mathcal{W}$ with respect to
the digraph $M$.

######  Definition 12 (Veto model parameters [34]).

The veto model parameters for the causal structure
$M=(\mathcal{W},\mathcal{S})$ are

$\displaystyle\mathcal{I}_{k}:=\\{0,1\\}\,,$
$\displaystyle\qquad\mathcal{O}_{k}:=\operatorname{Ch}_{M}(k)\cup\\{\bot\\}$
(49) $\displaystyle\omega_{k}:\mathcal{O}_{\operatorname{Pa}_{M}(k)}$
$\displaystyle\rightarrow\mathcal{I}_{k}$ (50)
$\displaystyle(o_{\ell})_{\ell\in\operatorname{Pa}_{M}(k)}$
$\displaystyle\mapsto\prod_{\ell\in\operatorname{Pa}_{M}(k)}[k=o_{\ell}]\,.$
(51)

These model parameters implement the following functionality, which justifies
the name. Each party $k$ may specify one of its children on its future
boundary, or “nobody” expressed with the bottom symbol $\bot$. If all parents
of some party $k$ specified “$k$,” then party $k$ receives a one on the past
boundary, and a zero otherwise.

In the following theorem, we combine some known results on causal models
concerning a specific class of digraphs. On the one hand, when a causal
structure from that class is amended with the veto model parameters, the
resulting causal model is always faithful and consistent. On the other hand,
these causal models always give rise to causal correlations only.

######  Theorem 13 (Consistency and causal correlations [34]).

If $M=(\mathcal{W},\mathcal{S})$ is a chordless siblings-on-cycles digraph,
i.e., for each directed cycle $C=(s_{0},s_{1},\dots)$ in $M$ that traverses
the vertices $\mathcal{W}_{C}\subseteq\mathcal{W}$, (chordless) the arc set
$\mathcal{S}$ contains no chord $(u,v)\in\mathcal{W}_{C}^{2}\setminus C$, and
(siblings-on-cycles) the arc set $\mathcal{S}$ contains two arcs
$(p,u_{0}),(p,u_{1})$ with $u_{0},u_{1}\in\mathcal{W}_{C}$, then the causal
model with causal structure $M$ and the veto model parameters is a consistent
and faithful causal model, and for all experiments
$\\{\mu_{k}\\}_{k\in\mathcal{W}}$, the correlations
$p(\underline{a}|\underline{x})$ are causal.

###  V.2 Illustration: The classical switch

The present framework and this theorem are illustrated by the classical
switch. Consider the $3$-party scenario, and let the causal structure $M$ be
the digraph $D$ of Fig. 6(a). In this case, the veto model parameters are

$\displaystyle\omega_{0}:\\{0,\bot\\}\times\\{0,1,\bot\\}$
$\displaystyle\rightarrow\\{0,1\\}$ (52) $\displaystyle(o_{1},o_{2})$
$\displaystyle\mapsto[0=o_{1}][0=o_{2}]$ (53)
$\displaystyle\omega_{1}:\\{1,\bot\\}\times\\{0,1,\bot\\}$
$\displaystyle\rightarrow\\{0,1\\}$ (54) $\displaystyle(o_{0},o_{2})$
$\displaystyle\mapsto[1=o_{1}][1=o_{2}]\,.$ (55)

Since party $2$ has no parents, the model parameter $\omega_{2}$ is simply the
constant $1$. If party $2$ implements an experiment such that the system on
the future boundary of party $2$ is in the state $0$, then the above
functions—partially evaluated—become

$\displaystyle\omega_{0}(o_{1},o_{2}=0)$ $\displaystyle=[0=o_{1}]$ (56)
$\displaystyle\omega_{1}(o_{0},o_{2}=0)$ $\displaystyle=0\,;$ (57)

Party $0$ may now receive a signal from party $1$. If, however, the experiment
of party $2$ produces the state $1$, then

$\displaystyle\omega_{0}(o_{1},o_{2}=0)$ $\displaystyle=0$ (58)
$\displaystyle\omega_{1}(o_{0},o_{2}=0)$ $\displaystyle=[1=o_{0}]\,,$ (59)

and party $1$ may receive a signal from party $0$—just as in the quantum
switch (cf. Fig. 1). Now, note that $M$ is a chordless siblings-on-cycles
graph. The only directed cycle is $((0,1),(1,0))$. This cycle is chordless,
and there exists $p=2$ such that $(p,0),(p,1)$ are arcs. The above theorem
thus tells us that, no matter what experiments are carried out by the parties
$\\{0,1,2\\}$, only causal correlations (see Def. 9) are attainable. This
example also illustrates the influence of the common parent $p=2$: No matter
what experiment $p$ carries out, the information flow around the directed
cycle is effectively interrupted. In fact, this is what ensures consistency.
Were the information flow along the cycle not interrupted, then a party may
influence its own past [37], which yields a disagreement with Eq. (45).

###  V.3 Game-winning strategies

We present causal models and experiments with which the digraph Bell games
(Theorem 9) are won deterministically. The respective causal structures are
particularly simple.

$u_{0}$$y_{0}$$p$ (a)

$u_{k-1}$$y_{k-1}$$u_{0}$$y_{0}$$u_{1}$$y_{1}$$u_{2}$$y_{2}$$p$ (b)

Figure 8: Causal structure to win (a) the $k$-cycle game for $k<n$, and (b)
the $k$-fence and the $k$-Möbius game for $2k<n$. Remaining isolated vertices
are omitted.

######  Definition 13 (Game-winning causal models).

The game-winning causal model consists of the following causal structure with
the veto model parameters. For the $k$-cycle game $\Gamma(n,D)$ with
$D=(\mathcal{V}\subseteq[n],\mathcal{A})$ and $k<n$, the causal structure is
the digraph $([n],\mathcal{A}\cup\\{(p,u_{0}),(p,y_{0})\\})$, where
$p\in[n]\setminus\mathcal{V}$ and $(u_{0},y_{0})\in\mathcal{A}$ (see Fig.
8(a)). For the $k$-fence game $\Gamma(n,D)$ as well as for the $k$-Möbius game
with $D=(\mathcal{V}\subseteq[n],\mathcal{A})$ and $2k<n$, the causal
structure is the digraph with vertices $[n]$ and arcs

$\displaystyle\begin{split}&\\{(u_{i},u_{i+1}),(y_{i},y_{i+1})\mid
i\in[k-1]\\}\\\
&\cup\\{(u_{k-1},y_{0}),(y_{k-1},u_{0}),(p,u_{0}),(p,y_{0})\\}\,,\end{split}$
(60)

where $\mathcal{U}=\\{u_{i}\\}_{i\in[k]}$, $\mathcal{Y}=\\{y_{i}\\}_{i\in[k]}$
correspond to the two-coloring bipartition of $D$, and
$p\in[n]\setminus\mathcal{V}$ (see Fig. 8(b)).

Thanks to Theorem 13, the game-winning causal model is consistent and
faithful. Next, we specify the experiments to be carried out by the parties.

######  Definition 14 (Game-winning experiments).

For the $k$-cycle, $k$-fence, or $k$-Möbius game
$\Gamma(n,D=(\mathcal{V},\mathcal{A}))$ and the respective game-winning causal
model $M=([n],\mathcal{S})$, the game-winning experiments are the following.
Whenever the referee announces $(s,r)\in\mathcal{A}$ to all parties $[n]$ and
$x\in\\{0,1\\}$ to party $s$, then party $s$ implements

$\displaystyle\mu_{s}:\mathcal{A}\times\\{0,1\\}\times\mathcal{I}_{s}$
$\displaystyle\rightarrow\mathcal{O}_{s}$ (61) $\displaystyle(s,r,x=0,i_{s})$
$\displaystyle\mapsto\bot$ (62) $\displaystyle(s,r,x=1,i_{s})$
$\displaystyle\mapsto c\,,$ (63)

where $\operatorname{Ch}_{M}(s)=\\{c\\}$, i.e., party $s$ “votes” for its
unique child if and only if $x=1$, party $r$ (who produces the output $a$)
implements

$\displaystyle\mu_{r}:\mathcal{A}\times\mathcal{I}_{r}$
$\displaystyle\rightarrow\\{0,1\\}\times\mathcal{O}_{r}$ (64)
$\displaystyle(s,r,i_{r})$ $\displaystyle\mapsto(i_{r},\bot)\,,$ (65)

i.e., party $r$ produces $a$ according the state on the past boundary, party
$p$ (who has a controlling rôle) implements

$\displaystyle\mu_{p}:\mathcal{A}\times\mathcal{I}_{p}$
$\displaystyle\rightarrow\times\mathcal{O}_{p}$ (66)
$\displaystyle(s,r,i_{p})$ $\displaystyle\mapsto u_{0}$ (67)

whenever the directed path from $s$ to $r$ in the causal structure $M$
traverses or ends in $u_{0}$, and

$\displaystyle(s,r,i_{p})$ $\displaystyle\mapsto y_{0}$ (68)

otherwise, and each other party $k\in\mathcal{V}\setminus\\{s,r,p\\}$
implement

$\displaystyle\mu_{k}:\mathcal{A}\times\mathcal{I}_{k}$
$\displaystyle\rightarrow\times\mathcal{O}_{k}$ (69)
$\displaystyle(s,r,i_{k}=0)$ $\displaystyle\mapsto\bot$ (70)
$\displaystyle(s,r,i_{k}=1)$ $\displaystyle\mapsto c\,,$ (71)

where $\operatorname{Ch}_{M}(k)=\\{c\\}$, i.e., party $k$ forwards the signal.

######  Theorem 14 (Tame game-winning causal models).

Let $\Gamma(n,D)$ be a $k$-cycle game with $k<n$, a $k$-fence game with
$2k<n$, or a $k$-Möbius game with $2k<n$. If the parties implement the game-
winning experiments on the respective game-winning causal model, then the
parties win the game $\Gamma(n,D)$ with certainty, i.e.,
$\Pr[\mathcal{W}(\Gamma(n,D))]=1$, and yet for all experiments the causal
models yields causal correlations only.

###### Proof.

The latter part follows from Theorem 13. For the former part, suppose the
referee announces $(s,r)\in\mathcal{A}$ to all parties $[n]$, and
$x\in\\{0,1\\}$ to party $s$, and let $\pi$ be the directed path from $s$ to
$r$ on the game-winning causal structure $M$. First, note that $\pi$ is
unique, and in the case of the $k$-cycle game, $\pi$ consists of the single
arc $(s,r)$. In the case of the $k$-fence or $k$-Möbius game, $s$ has a
different color than $r$. Thus, in all cases, the directed path $\pi$
traverses or ends in at most one of $u_{0}$ and $y_{0}$. Thanks to the
experiment of party $p$, each party $k$ on the path $\pi$, and $r$, may
receive a signal from $\operatorname{Pa}_{M}(k)\setminus\\{p\\}$. Now, party
$s$ votes for its unique child $c$ only if $x=1$. If $c=r$, then according to
$\mu_{c}$, party $r$ outputs $a=x$. Else, party $c$ forwards the signal to its
unique child, etc. ∎

##  VI Discussion: Relativistic setting

We exploit the digraph Bell games presented in Theorem 9 to distinguish
between special and general relativity. In other words, we show that a
violation of the above inequalities may certify the dynamical spacetime
structure in general relativity. To arrive at this, we first present a setting
that, if embodied in special relativity, will never lead to any violation of
the inequalities. Crucial for this endeavor is the notion of event. It is
central to understand that the Bell games presented provide limits on the
correlations where the events form a partial order. The quantum switch,
mentioned in the introduction, has been demonstrated experimentally with
quantum-optics tabletop experiments (see Ref. [38] for a review). Clearly, no
significant gravitational effects entered these experiments. An event, there,
is understood as the reception and emission of a signal. So, with that notion
of event, our program fails. Instead, we propose to use the commonly accepted
notion of event in relativity defined as the crossing of worldlines.

###  VI.1 Special relativity

In the following, we describe a setup where the relevant events in special
relativity will always form a partial order. Consider the three-agent setup
schematically represented in Fig. 9. This setup is straight forwardly
generalizable to any number of agents.

$R_{1}$$R_{0}$$R_{A}$$R_{B}$$R_{C}$$A$$B$$C$$S_{A}$$S_{B}$$S_{C}$ Figure 9:
The spacetime regions $S_{A},S_{B},S_{C}$ form a partial order. Agent $A$ may
only obtain the input $x$ and produce the output $a$ in the region $S_{A}$,
and similarly for the agents $B$ and $C$. Therefore, the correlations
$p(a,b,c|x,y,z)$ decompose as a partial order, and no violation of the
presented games can be observed.

In this $1+1$ Minkowski spacetime, the agents $A,B,C$ are initially spacelike
separated, and so are the respective referees $R_{X}$ for
$X\in\\{A,B,C,0,1\\}$. In this setup, the referee $R_{0}$ carries the inputs
to the parties, and the referees $R_{1},R_{X}$ for $X\in\\{A,B,C\\}$, who
travel close to the speed of light, ensure that the outputs of the parties are
timely produced. For simplicity, we can imagine $R_{0}$ to emit a light signal
that carries the inputs.444Clearly, the information encoded in this light
signal must be encrypted in a way such that each agent cannot obtain the input
to any other agent. Also, we can imagine $R_{1}$ and $R_{X}$, for
$X\in\\{A,B,C\\}$, to emit light signals that switch off any detection device
of agent $X$.

By this setup, the input to each party $X\in\\{A,B,C\\}$ is only available in
the intersection of the future lightcones of the initial location of $X$ and
$R_{0}$. If $R_{1}$ and $R_{X}$ meet without having received any output from
party $X$, then the game is aborted. This means that each party
$X\in\\{A,B,C\\}$ may only receive the input and produce the output in the
spacetime region $S_{X}$, i.e., the event $E_{X}$ is in

$\displaystyle S_{X}:=J^{+}(R_{0})\cap J^{+}(X)\setminus J^{+}(R_{1})\cup
J^{+}(R_{X})\,,$ (72)

where $J^{+}(e)$ denotes the future lightcone of the event $e$. The spacetime
regions $\\{S_{X}\\}_{X\in\\{A,B,C\\}}$ form a partial order. Thus, the
correlations $p(\underline{a}|\underline{x})$ attainable in this relativistic
setting are partial-order correlations; the presented Bell inequalities, by
definition, cannot be violated.

###  VI.2 General relativity

As shown above, the games presented are deterministically won with causal
correlations. This suggests that these games may also be won within general
relativity (and likely with globally hyperbolic spacetime structures). For
instance, consider the two-cycle game defined by the digraph
$D=([B,C],\\{(B,C),(C,B)\\})$, played with the three parties $\\{A,B,C\\}$
arranged as in Fig. 9. In case the referee announces $(B,C)$ and some
$x\in\\{0,1\\}$ to $B$, then trivially, $C$ may output $x$. Instead, if the
referee announces $(C,B)$ and some $x\in\\{0,1\\}$ to $C$, then in the special
relativistic setting, $B$ may at best guess $x$ with half probability. In a
general relativistic setting, however, agent $A$ may alter the spacetime
structure within its future lightcone: Depending on the announced arc $(B,C)$
or $(C,B)$, agent $A$ may displace a heavy mass which, in the latter case,
results in an inversion of the causal relations between the spacetime regions
$S_{B}$ and $S_{C}$.

Note that an inversion of the causal relations is not necessary. As an
alternative, the initial configuration could be such that the spacetime
regions $S_{B}$ and $S_{C}$ are spacelike separated and within the future
lightcone of $A$. In this case, agent $A$ must, depending on the announced arc
by the referee, tilt the spacetime structure such that $S_{B}$ and $S_{C}$ are
time-like related in the desired way.

##  VII Conclusions and open questions

We derived families of collaborative multiparty games that, if the winning
chance exceeds the described limit, prove the parties’ influence on the causal
relations. These games are formulated with directed graphs, and are rather
simple: A referee picks an arc $(s,r)$, and asks party $s$ to communicate a
random bit to party $r$. The purpose of these games is to detect the dynamical
spacetime structure present in general relativity and absent in special
relativity. This, however, can also be phrased purely within the theory of
general relativity. First, note that the spacetime structure in general
relativity is said to be dynamical because matter exerts a back-action on it.
Thus, one can regard these Bell tests also as tests for the displacement, and
therefore also for the presence, of matter. Moreover, these games serve as
device-independent test for indefinite causal order, as exhibited by the
quantum switch. It is known that the causal structure $M$ of any unitary
quantum process with indefinite causal order is cyclic [35]. A candidate game
to detect the dynamical component of the indefinite causal order is then
simply obtained from the cyclic part of $M$.

The game-winning strategies for the $k$-cycle, the $k$-fence, and the
$k$-Möbius games require more players than nodes in the graph. It is possible,
however, to design a game-winning causal model for the excluded case, as well
as for the game in the “all-to-one” scenario (which is nota bene a causal
game): The Svetlichny-inspired causal model from Ref. [26] has as causal
structure the complete directed graph $K^{\text{di}}_{n}$ among all parties.
By using that causal model, it is therefore trivial to communicate a bit from
any party to any other. The correlations that arise there, however, are
incompatible with any global ordering of the parties, dynamical or not.

Our work raises a series of open questions, with the central one: What is the
precise general relativistic description of the game-winning causal models?
The detection of dynamical causal structure can be understood as the detection
of the curvature’s change in the spacetime manifold. Thus, an immediate
follow-up question is whether and to what extent these games detect
gravitational waves. Speculatively, it might be possible to reinterpret the
data collected at the LIGO experiments (see, e.g., Ref. [39]) as a violation
of an inequality presented.

Understanding the informational content of general relativity might be
beneficial for future research, especially when merging quantum theory with
general relativity. Towards that, not only answers to the above questions but
also a mathematical formalization of the “dynamics” of causal structures might
be helpful. How do the experiments implemented in local regions alter the
causal structure?

It is suspected that enumerating all facet-defining inequalities for the
acyclic subdigraph polytope is infeasible: The more nodes are involved, the
more structure enters the polytope, and novel facets emerge [22]. In fact,
deciding whether a vector is a member of the acyclic subdigraph polytope is
NP-complete [40]. This raises two questions. Firstly, inspired by the Möbius
inequality, one might wonder whether an orientation of the Klein-bottle graph
would give rise to a facet-defining inequality or not. After all, the Klein
bottle is a generalization of the Möbius strip. Secondly, the computational
difficulty mentioned above suggests that deciding whether some $n$-party
correlations are compatible with a partial order or not is NP-complete as
well. Note that this holds for local correlations in the context of quantum
nonlocality [41].

Finally, it is known [42] that the axiom of choice in set theory yields an
advantage for the following game played among infinitely many players situated
on a line: Each player carries a hat with a random color, red or black, sees
only the players in front, and must guess the own hat color. This game, in
fact, forces us to revise the concept of nonsignaling in physical theories
[43]. Now, the bounds on the games presented here are indifferent whether the
players’ actions form a partial or a total order: We can equivalently assume
the same configuration as for the “hats” game. Now, does the axiom of choice
also allow for an advantage for the “infinite”-versions of the games
presented?

Acknowledgments. We thank Luca Apadula, Flavio Del Santo, Andrea Di Biagio,
and Stefan Wolf for helpful discussions. EET thanks Alexandra Elbakyan for
providing access to the scientific literature. EET is supported by the
Austrian Science Fund (FWF) through ZK3 (Zukunftskolleg). ÄB is supported by
the Swiss National Science Foundation (SNF) through project 182452 and project
214808.

## References

  * Bell [1964] J. S. Bell, On the Einstein Podolsky Rosen paradox, Physics Physique Fizika 1, 195 (1964).
  * Bell [1975] J. S. Bell,  _The Theory of Local Beables_, Tech. Rep. TH-2053-CERN (CERN, 1975) presented at the Sixth GIFT Seminar, Jaca, 2–7 June 1975, reproduced in Epistemological Letters 9, 17 (1976), and in Speakable and Unspeakable in Quantum Mechanics (Cambridge University Press, Cambridge, 2004).
  * Wolf [2017] S. Wolf, An all-or-nothing flavor to the Church-Turing hypothesis, in  _Theory and Applications of Models of Computation. TAMC 2017_, edited by T. Gopal, G. Jäger, and S. Steila (Springer, Cham, 2017) pp. 39–56.
  * Lorenz [2022] R. Lorenz, Quantum causal models: the merits of the spirit of Reichenbach’s principle for understanding quantum causal structure, Synthese 200, 424 (2022).
  * Coretti  _et al._ [2011] S. Coretti, E. Hänggi, and S. Wolf, Nonlocality is transitive, Physical Review Letters 107, 100402 (2011).
  * Bancal  _et al._ [2012] J.-D. Bancal, S. Pironio, A. Acín, Y. C. Liang, V. Scarani, and N. Gisin, Quantum non-locality based on finite-speed causal influences leads to superluminal signalling, Nature Physics 8, 867 (2012).
  * Barnea  _et al._ [2013] T. J. Barnea, J.-D. Bancal, Y.-C. Liang, and N. Gisin, Tripartite quantum state violating the hidden-influence constraints, Physical Review A 88, 022123 (2013).
  * Wood and Spekkens [2015] C. J. Wood and R. W. Spekkens, The lesson of causal discovery algorithms for quantum correlations: causal explanations of Bell-inequality violations require fine-tuning, New Journal of Physics 17, 033002 (2015).
  * Nielsen and Chuang [2010] M. A. Nielsen and I. L. Chuang,  _Quantum Computation and Quantum Information: 10th Anniversary Edition_ (Cambridge University Press, Cambridge, 2010).
  * Bertlmann and Zeilinger [2002] R. A. Bertlmann and A. Zeilinger, eds.,  _Quantum [Un]speakables: From Bell to Quantum Information_ (Springer, Berlin, Heidelberg, 2002).
  * Hardy [2005] L. Hardy, Probability theories with dynamic causal structure: A new framework for quantum gravity, arXiv:0509120 [gr-qc] (2005).
  * Colnaghi  _et al._ [2012] T. Colnaghi, G. M. D’Ariano, S. Facchini, and P. Perinotti, Quantum computation with programmable connections between gates, Physics Letters A 376, 2940 (2012).
  * Oreshkov  _et al._ [2012] O. Oreshkov, F. Costa, and Č. Brukner, Quantum correlations with no causal order, Nature Communications 3, 1092 (2012).
  * Chiribella  _et al._ [2013] G. Chiribella, G. M. D’Ariano, P. Perinotti, and B. Valiron, Quantum computations without definite causal structure, Physical Review A 88, 022318 (2013).
  * Portmann  _et al._ [2017] C. Portmann, C. Matt, U. Maurer, R. Renner, and B. Tackmann, Causal boxes: Quantum information-processing systems closed under composition, IEEE Transactions on Information Theory 63, 3277 (2017).
  * Zych  _et al._ [2019] M. Zych, F. Costa, I. Pikovski, and Č. Brukner, Bell’s theorem for temporal order, Nature Communications 10, 3772 (2019).
  * Araújo  _et al._ [2015] M. Araújo, C. Branciard, F. Costa, A. Feix, C. Giarmatzi, and Č. Brukner, Witnessing causal nonseparability, New Journal of Physics 17, 102001 (2015).
  * Oreshkov and Giarmatzi [2016] O. Oreshkov and C. Giarmatzi, Causal and causally separable processes, New Journal of Physics 18, 093020 (2016).
  * Wechs  _et al._ [2021] J. Wechs, H. Dourdent, A. A. Abbott, and C. Branciard, Quantum circuits with classical versus quantum control of causal order, PRX Quantum 2, 030335 (2021).
  * van der Lugt  _et al._ [2022] T. van der Lugt, J. Barrett, and G. Chiribella, Device-independent certification of indefinite causal order in the quantum switch, arXiv:2208.00719 [quant-ph] (2022).
  * Gogioso and Pinzani [2023] S. Gogioso and N. Pinzani, The combinatorics of causality, arXiv:2206.08911 [quant-ph] (2023).
  * Grötschel  _et al._ [1985] M. Grötschel, M. Jünger, and G. Reinelt, On the acyclic subgraph polytope, Mathematical Programming 33, 28 (1985).
  * Guy and Harary [1967] R. K. Guy and F. Harary, On the Möbius ladders, Canadian Mathematical Bulletin 10, 493 (1967).
  * Collins  _et al._ [2002] D. Collins, N. Gisin, S. Popescu, D. Roberts, and V. Scarani, Bell-type inequalities to detect true $n$-body nonseparability, Physical Review Letters 88, 170405 (2002).
  * Seevinck and Svetlichny [2002] M. Seevinck and G. Svetlichny, Bell-type inequalities for partial separability in $N$-particle systems and quantum mechanical violations, Physical Review Letters 89, 060401 (2002).
  * Baumeler  _et al._ [2022a] Ä. Baumeler, A. S. Gilani, and J. Rashid, Unlimited non-causal correlations and their relation to non-locality, Quantum 6, 673 (2022a).
  * Ziegler [1994] G. M. Ziegler,  _Lectures on Polytopes_, Graduate Texts in Mathematics, Vol. 152 (Springer-Verlag, New York, NY, 1994).
  * Bang-Jensen and Gutin [2009] J. Bang-Jensen and G. Z. Gutin,  _Digraphs: Theory, Algorithms and Applications_, Springer Monographs in Mathematics (Springer-Verlag, London, 2009).
  * Jünger [1985] M. Jünger,  _Polyhedral combinatorics and the acyclic subdigraph problem_ , Ph.D. thesis, University of Augsburg, Germany (1985).
  * Goemans and Hall [1996] M. X. Goemans and L. A. Hall, The strongest facets of the acyclic subgraph polytope are unknown, in  _5th International Integer Programming and Combinatorial Optimization Conference_, Lecture Notes in Computer Science, Vol. 1084 (1996) pp. 415–429.
  * Baumeler and Wolf [2014] Ä. Baumeler and S. Wolf, Perfect signaling among three parties violating predefined causal order, in  _2014 IEEE International Symposium on Information Theory_ (IEEE, Piscataway, 2014) pp. 526–530.
  * Branciard  _et al._ [2015] C. Branciard, M. Araújo, A. Feix, F. Costa, and Č. Brukner, The simplest causal inequalities and their violation, New Journal of Physics 18, 013008 (2015).
  * Abbott  _et al._ [2016] A. A. Abbott, C. Giarmatzi, F. Costa, and C. Branciard, Multipartite causal correlations: Polytopes and inequalities, Phys. Rev. A 94, 032131 (2016).
  * Tselentis and Ämin Baumeler [2022] E.-E. Tselentis and Ämin Baumeler, Admissible causal structures and correlations, arXiv:2210.12796 [quant-ph] (2022).
  * Barrett  _et al._ [2021] J. Barrett, R. Lorenz, and O. Oreshkov, Cyclic quantum causal models, Nature Communications 12, 885 (2021).
  * Baumeler and Wolf [2016] Ä. Baumeler and S. Wolf, Device-independent test of causal order and relations to fixed-points, New Journal of Physics 18, 035014 (2016).
  * Baumeler and Tselentis [2021] Ä. Baumeler and E. Tselentis, Equivalence of grandfather and information antinomy under intervention, Electronic Proceedings in Theoretical Computer Science 340, 1 (2021).
  * Goswami and Romero [2020] K. Goswami and J. Romero, Experiments on quantum causality, AVS Quantum Science 2, 1 (2020).
  * LIGO Scientific Collaboration and Virgo Collaboration [2016] LIGO Scientific Collaboration and Virgo Collaboration, Observation of gravitational waves from a binary black hole merger, Physical Review Letters 116, 061102 (2016).
  * Garey and Johnson [1979] M. Garey and D. Johnson,  _Computers and Intractability: A Guide to the Theory of NP-completeness_ , Mathematical Sciences Series (Freeman, 1979).
  * Pitowsky [1989] I. Pitowsky,  _Quantum Probability — Quantum Logic_, Lecture Notes in Physics, Vol. 321 (Springer-Verlag, Berlin/Heidelberg, 1989).
  * Hardin and Taylor [2008] C. S. Hardin and A. D. Taylor, A peculiar connection between the axiom of choice and predicting the future, The American Mathematical Monthly 115, 91 (2008).
  * Baumeler  _et al._ [2022b] Ä. Baumeler, B. Dakić, and F. Del Santo, The axiom of choice and the no-signaling principle, arXiv:2206.08467 [quant-ph] (2022b).