# Parity Quantum Computing as YZ-Plane Measurement-Based Quantum Computing

Isaac D. Smith<EMAIL_ADDRESS>Hendrik Poulsen Nautrup  Institute for
Theoretical Physics, University of Innsbruck, Innsbruck, Austria  Hans J.
Briegel  Institute for Theoretical Physics, University of Innsbruck,
Innsbruck, Austria  Fachbereich Philosophie, Universität Konstanz, Konstanz,
Germany

###### Abstract

We show that universal parity quantum computing employing a recently
introduced constant depth decoding procedure is equivalent to measurement-
based quantum computation (MBQC) on a bipartite graph using only YZ-plane
measurements. We further show that any unitary MBQC using only YZ-plane
measurements must occur on a bipartite graph.

††preprint: APS/123-QED

In the present era of pre-fault-tolerant quantum computation [1], there exists
an array of theoretical proposals for computation that display certain
advantages and differing levels of suitability for implementation on current
physical devices.

Parity quantum computation [2, 3, 4, 5, 6, 7] refers to one such proposal,
initially based on quantum annealing [2]. The universal parity computing
framework [3] leverages the properties of a certain type of quantum state
encoding, the parity encoding. This encoding maps an $n$-qubit logical state
onto $n(n+1)/2$ physical qubits, some of which obtain parity information
related to subsets of logical qubits. Consequently, certain rotations acting
locally on these parity qubits translate to multi-qubit logical rotations on
the corresponding subset [3]. The parity code is in particular a stabiliser
code [8, 9] and many of the properties of the code are well understood using
the stabiliser formalism.

Stabiliser states and stabiliser codes are known to have a canonical form,
namely graph states [10, 11] and graph codes [12, 13, 14] respectively. Graph
states form an important class of highly entangled states that support
measurement-based quantum computation (MBQC) [15, 16, 17, 18, 19, 20]. MBQC is
a well-known alternative to the quantum circuit model driven by single qubit
projective measurements instead of unitary gates.

Recently, a proposal for measurement-based encoding and decoding procedures
were put forward for the parity computing regime [21], demonstrating
beneficial properties in terms of their computational depth. Due to the close
connection between stabiliser codes and graph codes, an investigation of the
potential connections to MBQC is warranted, which we initiate in this work.

After presenting the required background, we demonstrate that every parity
code is local Clifford equivalent to a bipartite graph code (1). Consequently,
we show that parity quantum computation with the measurement-based decoding is
MBQC where all measurements are from the YZ-plane of the Bloch sphere, and
where re-entanglement and some local operations are allowed (1). We further
show that any MBQC using only YZ-plane measurements and with input and output
sets of equal size must use bipartite graph states (2). To conclude, we
briefly outline some consequences of these results for both computing
paradigms.

##  I Background

Parity Quantum Computing -  A parity quantum computation commences by encoding
the computational input state using the LHZ architecture [2] (see Figure
1(a)). The computation proceeds by applying unitaries from a native gate set
for the parity encoding, such as that outlined in [3], which largely consists
of local rotations. To finish, a decoding procedure returns the computational
output. Presently, we will focus on the parity encoding procedure and
universal gate set presented in [3] in combination with the measurement-based
decoding procedure outlined in [21].

The parity encoding procedure maps a state on $n$ logical qubits to a state on
$n(n+1)/2$ physical qubits. Following [3], we consider an LHZ layout where $n$
physical qubits (the ‘data’ qubits) directly correspond to the $n$ logical
qubits. The remaining $N=n(n-1)/2$ qubits will be referred to as ‘parity’
qubits. We denote the sets of data and parity qubits by $I$ and $V\setminus I$
respectively.

Encoding consists of applying a sequence of CNOTs to an input state
$\ket{\psi}$ and the parity qubits, which are all initialised to $\ket{0}$.
Letting $C$ represent the set of control-target pairs, the encoded state is:

$\displaystyle\ket{LHZ_{\psi}}=U_{\text{enc}}\ket{0}^{\otimes
N}\ket{\psi}=\prod_{(c,t)\in C}\text{CNOT}_{(c,t)}\ket{0}^{\otimes
N}\ket{\psi}.$ (1)

Different constraint sets $C$ can produce the same encoded state. For example,
$C$ could contain only pairs where every control is a data qubit and every
target a parity qubit, which may involve non-nearest neighbour interactions
for a given physical layout. Equivalently, it is possible to take $C$ to
contain only nearest-neighbour CNOTs, where now some control qubits are parity
qubits (see e.g., Figure 1(a)). The compilation of a given parity code into a
nearest-neighbour layout is an interesting optimisation problem and a topic of
ongoing research [7, 6, 5].

For each $\ket{\psi}$, $\ket{LHZ_{\psi}}$ is a state in the parity codespace
for the given architecture. The stabilizer of the parity code is generated by
operators of the form

$\displaystyle K^{\prime}_{(ij...k)}:=Z_{(ij...k)}\otimes Z_{i}\otimes
Z_{j}\otimes...\otimes Z_{k}$ (2)

where the single subscripts $i$, $j$, etc. indicate data qubits and the
subscript $(ij...k)$ indicates the parity qubit that encodes the parity
information of data qubits $i$, $j$ and so on. The operators
$K^{\prime}_{(ij...k)}$ for all parity qubits are mutually independent and
generate the codespace. Note that often each parity qubit is taken to encode
the parity of just two data qubits.

A benefit of this encoding consists in the ability to implement diagonal
multi-qubit logical operations via single qubit physical rotations. For
example, applying a local $Z$-rotation to a parity qubit $(ij)$ effectively
applies a logical $Z_{i}\otimes Z_{j}$-rotation, from which a controlled-phase
gate between logical qubits $i$ and $j$ can be obtained via local
$Z$-rotations on the corresponding data qubits [3]. For full universal quantum
computation, in conjunction with $Z$-rotations and controlled-phase gates, it
suffices to be able to implement a logical $X$-rotation. For a data qubit $i$,
this can be done via a decoding sequence of CNOTs along all parity qubits
containing parity information about $i$, a local $X$-rotation at data qubit
$i$, and a re-encoding sequence of CNOTs (see [3] for more details).

Until recently, the typical parity decoding procedures involved applying the
encoding sequence of CNOT gates in reverse. In [21], an equivalent decoding
procedure was proposed involving local $X$-measurements on parity qubits
followed by local $Z$-operations conditional on measurement outcomes. One
benefit of this approach is that full and partial decoding can be performed in
constant-depth regardless of the size of the architecture.

For this gate set and measurement-based decoding, a unitary $U$ applied to
input state $\ket{\psi}$ in the parity regime can be decomposed into a series
of layers, where each layer involves parity qubit rotations followed by
decoding. For notational simplicity, we consider full decoding in each layer.
Denoting the set of layers by $L$, the set of data qubits by $I$ and the set
of parity qubits by $V\setminus I$, the computation can be written as:

$\displaystyle U\ket{\psi}$
$\displaystyle=\prod_{l=1}^{L}\left(U_{\text{data}}^{(l)}(\bm{\alpha}^{(l)},\bm{\phi}^{(l)})D_{\text{dec}}^{(l)}(\bm{\theta}^{(l)})U_{\text{enc}}\ket{0}^{\otimes
N}\right)\ket{\psi}$ (3)

where $U_{\text{enc}}$ acts on both the ancilla $\ket{0}^{\otimes N}$ as well
as the qubits in $I$, $D_{\text{dec}}^{(l)}(\bm{\theta}^{(l)})$ is the
operator involving parity qubit rotations and decoding for layer $l$ given by

$\displaystyle
D_{\text{dec}}^{(l)}(\bm{\theta}^{(l)}):=\bigotimes_{(ij...k)\in V\setminus
I}\bra{+_{(ij...k)}}R_{Z_{(ij...k)}}(\theta_{(ij...k)}^{(l)})$ (4)

and $U_{\text{data}}^{(l)}(\bm{\alpha}^{(l)},\bm{\phi}^{(l)})$ is the product
of local rotation on data qubits for layer l given by:

$\displaystyle
U_{\text{data}}^{(l)}(\bm{\alpha}^{(l)},\bm{\phi}^{(l)}):=\bigotimes_{i\in
I}R_{X_{i}}(\alpha_{i}^{(l)})R_{Z_{i}}(\phi_{i}^{(l)}).$ (5)

Note that the only distinction in the case of partial decoding is that
$D_{\text{dec}}^{(l)}$ contains measurements in some subset of $V\setminus I$,
the ancilla prepared in $\ket{0}$ in the subsequent layer correspond to the
same subset, and the relevant $U_{\text{enc}}$ is replaced by
$U_{\text{enc}}^{(l+1)}$ which applies only the appropriate CNOTs to re-encode
back to the full LHZ state.

(a) An example of an LHZ architecture.

(b) The equivalent bipartite graph code.

Figure 1: (a) The parity encoding encodes an input state prepared on the data
qubits (white circles). The grey circles denote parity qubits prepared in
$\ket{0}$ and CNOT gates are applied to data and parity according to the
layout as shown. This parity code in is equivalent to a graph code for the
bipartite graph shown in (b).

Measurement-Based Quantum Computing -  Measurement-based quantum computing
(MBQC) [15, 16, 17, 18] consists of three things: (i) a highly entangled graph
state [10, 11], (ii) a sequence of single qubit projective measurements in
certain planes of the Bloch sphere, and (iii) classical, adaptive corrections
of future measurements conditioned on prior measurement outcomes. Despite the
indeterminacy of quantum measurements, deterministic computation can be
performed, provided the sequence of measurements and underlying graph state
satisfy certain properties [22].

Graph states take their name from their connection to mathematical graphs,
where vertices correspond to qubits and edges correspond to two-qubit gates.
We consider here graph states where a computational input state $\ket{\psi}$
can be prepared on a selected subset of vertices, denoted $I$.

Let $G$ be a graph with vertex set $V$ and edge set $\tilde{E}$. Let $I\subset
V$ be a set of distinguished vertices such that $|I|=n$ and $|V\setminus
I|=N$. Let $\ket{\psi}$ be a state in the Hilbert space associated to the
input vertices, $\mathcal{H}_{I}$. Let $E$ denote the set of edges that are
not entirely contained in $I$. The graph state with input is then

$\displaystyle\ket{G_{\psi}}:=\prod_{\\{v,v^{\prime}\\}\in
E}\text{CZ}_{v,v^{\prime}}\ket{\psi}_{I}\ket{+}^{\otimes N}.$ (6)

For any input state $\ket{\psi}$, the graph state with input is invariant
under the application of any operation in the set $\\{K_{v}:v\in V\setminus
I\\}$ where

$\displaystyle K_{v}:=X_{v}\otimes Z_{N_{v}^{G}}$ (7)

with $N_{v}^{G}$ denoting the set of neighbours of vertex $v$ in $G$ and
$Z_{N_{v}^{G}}:=\bigotimes_{v^{\prime}\in N_{v}^{G}}Z_{v^{\prime}}$. The
$K_{v}$ are all mutually independent and the set $\\{K_{v}:v\in V\setminus
I\\}$ generates a $2^{n}$-dimensional subspace of $\mathcal{H}_{v}$, the graph
codespace corresponding to $G$ (see e.g., [12, 14] for further details on
graph codes 111Just as [3] modified the original LHZ architecture [2] to
contain data qubits, we are considering graph codes where the input qubits
remain unmeasured, a modification to be removed in future work.).

In the measurement-based regime, computation is driven by single-qubit
projective measurements restricted to the $XY$-, $XZ$\- and $YZ$-planes of the
Bloch sphere. A given computation is defined by one specific outcome for each
measurement, and the restriction to the given planes allows for the correction
of undesired outcomes via an effective application of an appropriate
stabiliser element (or products thereof). However, even with these
restrictions not every sequence of measurements for a given graph states is
possible. The combination of graph state and measurements that do allow for
computation are well characterised by a property called gflow (see Appendix A)
which is known to be a necessary and sufficient condition for deterministic
MBQC [22].

##  II Results

It is known that every stabiliser code is equivalent to a graph code [13] (see
also [24]). The following is an instance of this result using the specific
properties exhibited by parity codes.

######  Proposition 1.

Every parity code is local Clifford equivalent to a bipartite graph code,
where all data qubits are contained in one partition.

###### Proof.

A parity code is defined by a stabiliser generated by the operators
$K^{\prime}_{(ij...k)}=Z_{(ij...k)}\otimes Z_{i}\otimes Z_{j}\otimes...\otimes
Z_{k}$ for each parity qubit $(ij...k)$. The set of qubits upon which these
operators act includes only a single parity qubit. Via conjugation by
Hadamards on each parity qubit, we obtain the local Clifford equivalent
stabiliser generated by $K_{(ij...)}=X_{(ij...k)}\otimes Z_{i}\otimes
Z_{j}\otimes...\otimes Z_{k}$. Since the $K_{(ij...k)}$ are of the form
$X_{(ij...k)}\otimes Z_{N_{(ij...k)}^{G}}$ which generate a graph code for a
graph $G$ with edges between parity and data qubits. That is, each
neighbourhood $N_{(ij...k)}^{G}$ contains only vertices corresponding to data
qubits, which enforces a parity qubit-data qubit bipartition. ∎

An example of this correspondence is shown in Figure 1(a) and Figure 1(b).
Note that there exist graph codes that are not local Clifford equivalent to
bipartite graph codes, and hence are inequivalent to any parity code.

An immediate consequence of 1 is that, for any $\ket{\psi}$, we have

$\displaystyle\ket{LHZ_{\psi}}=\bigotimes_{v\in V\setminus
I}H_{v}\ket{G_{\psi}}$ (8)

where $G$ denotes the bipartite graph corresponding to the parity code, $I$
denotes the set of vertices corresponding to data qubits and $V$ is the set of
all qubits. We will use $V\setminus I$ to denote the set of parity qubits
forthwith.

Consider the parity computation $U$ described in Equation 3. For simplicity,
let us first consider only the initial layer $l=1$ and drop the parameters
$\bm{\alpha}$, $\bm{\phi}$ and $\bm{\theta}$ from the notation since the
following holds for all parameter values. Using Equation 8, we get that

$\displaystyle
U_{\text{data}}^{(1)}D_{\text{dec}}^{(1)}U_{\text{enc}}\ket{0}^{\otimes
N}\ket{\psi}=U_{\text{data}}^{(1)}D_{\text{dec}}^{(1)}H_{V\setminus
I}\ket{G_{\psi}}$ (9)

where $H_{V\setminus I}$ is shorthand for $\otimes_{v\in V\setminus I}H_{v}$.
Both $D_{\text{dec}}^{(1)}$ and $H_{V\setminus I}$ act on the same qubits and
can be simplified as:

$\displaystyle D_{\text{dec}}^{(1)}H_{V\setminus I}=\bigotimes_{v\in
V\setminus I}\bra{0_{v}}R_{X_{v}}(\theta_{v}^{(1)}).$ (10)

The operator $\bra{0_{v}}R_{X_{v}}(\theta_{v}^{(1)})$ is a measurement in the
YZ-plane of the Bloch sphere, and hence $D_{\text{dec}}^{(1)}H_{V\setminus
I}\ket{G_{\psi}}$ is precisely a measurement-based computation where all
measurements are restricted to that plane (the issue of measurement
corrections is covered below). Denote the output of the first layer as
$\ket{\psi^{(1)}}$, which is the resultant state of applying
$U_{\text{data}}^{(1)}$ to the output state of the MBQC. The remaining
computation is then given by

$\displaystyle\prod_{l=2}^{L}\left(U_{\text{data}}^{(l)}D_{\text{dec}}^{(l)}U_{\text{enc}}\ket{0}^{\otimes
N}\right)\ket{\psi^{(1)}}$ (11)

for which the above process can be repeated. We have thus shown the following:

######  Theorem 1.

Universal parity quantum computing is repeated measurement-based quantum
computation using YZ-plane measurements, interleaved with local rotations.

It should be noted that typically, MBQC is done on a fully pre-prepared graph
state where input $I$ and output $O$ are distinct. However, proposals for
repeated MBQC which de- and re-encode graph codes have been considered
previously [25]; see also [20] for a recent perspective.

In light of the above, it is prudent to demarcate the parity computing regime
with respect to the MBQC regime. One could reasonably ask if there exist YZ-
only measurement-based computations on graphs that are not bipartite. However,
the following theorem demonstrates that this in fact not the case. The theorem
also takes care of any issues regarding correction of measurements (this is
explained further in Appendix A).

As mentioned above, MBQC on a graph state $G$ typically includes specifying an
input and output set of vertices, denoted by $I$ and $O$ respectively. For a
deterministic MBQC to produce a unitary transformation (as opposed to an
isometry), we require $|I|=|O|$.

######  Theorem 2.

MBQC on a (simple, connected) graph $G$ with $|I|=|O|$ and using only YZ-plane
measurements is deterministic if and only if $G$ is bipartite with $I$ forming
one partition.

The proof makes use of technical lemmas related to gflow which are proved
along with the theorem in Appendix A.

##  III Discussion

This work has demonstrated that (i) parity codes are local Clifford equivalent
to bipartite graph codes, (ii) as a consequence, parity quantum computing can
be understood as repeated MBQC where all measurements are made in the YZ-
plane, supplemented by local rotations, and (iii) MBQC with equivalent input
and output qubits and using only YZ-plane measurements must use a bipartite
graph state.

Interestingly, these results demonstrate that the universal parity computing
regime has effectively singled out YZ-plane unitary MBQC exactly. To the best
of our knowledge, the restriction to having equivalent input and output and
only YZ-measurements has not been considered before in the MBQC literature. On
the other hand, this is a restriction of the full MBQC framework, which means
that there is ample scope for future investigation into what other aspects of
MBQC could be brought to bear on the parity computing regime, and vice versa.

There are a number of consequences of these results worth mentioning already
here. In [21], it was noted that the parity measurement-based encoding and
decoding procedures can be implemented in constant depth regardless of
architecture size. Since the decoding procedure corresponds to measuring
vertices in one partition of a bipartite graph, it is clear that all
measurements can be done simultaneously and corrected for in the other
partition. The encoding procedure can be understood as measuring ancilla
vertices of a larger graph state in the $X$-basis, which in particular
produces the required bipartite graph (see e.g., [10, 11] for a
characterisation of graph state deformations under Pauli measurements). It is
known that all Pauli-measurements can be performed simultaneously in MBQC
[18].

Bipartite graph states have previously received substantial attention in the
MBQC literature; see e.g., [26, 27, 28]. The set of bipartite graph states
includes both cluster states and GHZ states, which are both known to be useful
for computation and communication protocols. There exist multi-particle
entanglement purification protocols for bipartite graph states which exhibit
favourable error thresholds for realistic scenarios [26, 27, 28]. Similar
techniques may be of benefit for error mitigation in the parity regime - an
avenue for future work.

Acknowledgements: We would like to thank B. Klaver and A. Messinger for useful
discussions. This research was funded in whole or in part by the Austrian
Science Fund (FWF) through the DK-ALM W$1259$-N$27$ and the SFB BeyondC F7102.
For open access purposes, the authors have applied a CC BY public copyright
license to any author-accepted manuscript version arising from this
submission. This work was also co-funded by the European Union (ERC, QuantAI,
Project No. $101055129$). Views and opinions expressed are however those of
the author(s) only and do not necessarily reflect those of the European Union
or the European Research Council. Neither the European Union nor the granting
authority can be held responsible for them.

## References

  * Preskill [2018] J. Preskill, Quantum Computing in the NISQ era and beyond, Quantum 2, 79 (2018).
  * Lechner  _et al._ [2015] W. Lechner, P. Hauke, and P. Zoller, A quantum annealing architecture with all-to-all connectivity from local interactions, Science advances 1, e1500838 (2015).
  * Fellner  _et al._ [2022a] M. Fellner, A. Messinger, K. Ender, and W. Lechner, Universal parity quantum computing, Phys. Rev. Lett. 129, 180503 (2022a).
  * Fellner  _et al._ [2022b] M. Fellner, A. Messinger, K. Ender, and W. Lechner, Applications of universal parity quantum computation, Phys. Rev. A 106, 042442 (2022b).
  * Fellner  _et al._ [2023] M. Fellner, K. Ender, R. ter Hoeven, and W. Lechner, Parity Quantum Optimization: Benchmarks, Quantum 7, 952 (2023).
  * Drieb-Schön  _et al._ [2023] M. Drieb-Schön, K. Ender, Y. Javanmard, and W. Lechner, Parity Quantum Optimization: Encoding Constraints, Quantum 7, 951 (2023).
  * Ender  _et al._ [2023] K. Ender, R. ter Hoeven, B. E. Niehoff, M. Drieb-Schön, and W. Lechner, Parity Quantum Optimization: Compiler, Quantum 7, 950 (2023).
  * Gottesman [1997] D. Gottesman,  _Stabilizer codes and quantum error correction_ (California Institute of Technology, 1997).
  * Nielsen and Chuang [2010] M. A. Nielsen and I. L. Chuang,  _Quantum Computation and Quantum Information: 10th Anniversary Edition_ (Cambridge University Press, 2010).
  * Hein  _et al._ [2004] M. Hein, J. Eisert, and H. J. Briegel, Multiparty entanglement in graph states, Phys. Rev. A 69, 062311 (2004).
  * Hein  _et al._ [2006] M. Hein, W. Dür, J. Eisert, R. Raussendorf, M. Van den Nest, and H. J. Briegel, Entanglement in graph states and its applications, in  _Volume 162: Quantum Computers, Algorithms and Chaos_, Proceedings of the International School of Physics ”Enrico Fermi” (IOS Press Ebooks, 2006) pp. 115–218.
  * Schlingemann [2002] D. Schlingemann, Logical network implementation for cluster states and graph codes, arXiv preprint quant-ph/0202007 (2002).
  * Schlingemann [2001] D. Schlingemann, Stabilizer codes can be realized as graph codes, arXiv preprint quant-ph/0111080 (2001).
  * Schlingemann and Werner [2001] D. Schlingemann and R. F. Werner, Quantum error-correcting codes associated with graphs, Phys. Rev. A 65, 012308 (2001).
  * Raussendorf and Briegel [2001a] R. Raussendorf and H. J. Briegel, A one-way quantum computer, Phys. Rev. Lett. 86, 5188 (2001a).
  * Briegel  _et al._ [2009] H. J. Briegel, D. E. Browne, W. Dür, R. Raussendorf, and M. Van den Nest, Measurement-based quantum computation, Nature Physics 5, 19 (2009).
  * Raussendorf and Briegel [2001b] R. Raussendorf and H. Briegel, Computational model underlying the one-way quantum computer, arXiv preprint quant-ph/0108067 https://doi.org/10.48550/arXiv.quant-ph/0108067 (2001b).
  * Raussendorf  _et al._ [2003] R. Raussendorf, D. E. Browne, and H. J. Briegel, Measurement-based quantum computation on cluster states, Phys. Rev. A 68, 022312 (2003).
  * Walther  _et al._ [2005] P. Walther, K. J. Resch, T. Rudolph, E. Schenck, H. Weinfurter, V. Vedral, M. Aspelmeyer, and A. Zeilinger, Experimental one-way quantum computing, Nature 434, 169 (2005).
  * Poulsen Nautrup and Briegel [2023] H. Poulsen Nautrup and H. J. Briegel, Measurement-based quantum computation from clifford quantum cellular automata, arXiv preprint arXiv:2312.13185 (2023).
  * Messinger  _et al._ [2023] A. Messinger, M. Fellner, and W. Lechner, Constant depth code deformations in the parity architecture, in  _2023 IEEE International Conference on Quantum Computing and Engineering (QCE)_, Vol. 01 (2023) pp. 120–130.
  * Browne  _et al._ [2007] D. E. Browne, E. Kashefi, M. Mhalla, and S. Perdrix, Generalized flow and determinism in measurement-based quantum computation, New Journal of Physics 9, 250 (2007).
  * Note [1] Just as [3] modified the original LHZ architecture [2] to contain data qubits, we are considering graph codes where the input qubits remain unmeasured, a modification to be removed in future work.
  * Van den Nest  _et al._ [2004] M. Van den Nest, J. Dehaene, and B. De Moor, Graphical description of the action of local clifford transformations on graph states, Phys. Rev. A 69, 022316 (2004).
  * Zwerger  _et al._ [2014] M. Zwerger, H. Briegel, and W. Dür, Hybrid architecture for encoded measurement-based quantum computation, Scientific reports 4, 5364 (2014).
  * Dür  _et al._ [2003] W. Dür, H. Aschauer, and H.-J. Briegel, Multiparticle entanglement purification for graph states, Phys. Rev. Lett. 91, 107903 (2003).
  * Aschauer  _et al._ [2005] H. Aschauer, W. Dür, and H.-J. Briegel, Multiparticle entanglement purification for two-colorable graph states, Phys. Rev. A 71, 012319 (2005).
  * Zwerger  _et al._ [2013] M. Zwerger, H. J. Briegel, and W. Dür, Universal and optimal error thresholds for measurement-based entanglement purification, Phys. Rev. Lett. 110, 260503 (2013).

##  Appendix A Appendix A: Proof of 2

A computation in MBQC is defined by the positive measurement outcomes of a
sequence of single qubit projective measurements on a graph state $\ket{G}$.
To compute deterministically, a method for effectively correcting for the
occurrence of negative outcomes is required. By restricting measurements to
the XY-, XZ- or YZ-planes of the Bloch sphere, the positive and negative
projections are related by conjugation via $Z$, $XZ$ and $X$ respectively.
Since each of these operators features in a tensor factor of some element of
the stabiliser for $\ket{G}$, it is possible to correct for a negative outcome
by conditionally “completing” that stabiliser element.

The following definition, due to Browne et al. [22], outlines the criteria
that a graph $G$, choice of input and output sets $I$ and $O$, and assignment
of measurement planes to qubits must satisfy so that any measurement is
correctable.

######  Definition 1.

Let $G=(V,E)$ be a graph, $I$ and $O$ be input and output subsets of $V$
respectively, and $\omega:V\setminus O\rightarrow\\{XY,XZ,YZ\\}$ be a map
assigning measurement planes to qubits (the superscript $c$ denotes set
complement). The tuple $(G,I,O,\omega)$ has gflow if there exists a map
$g:V\setminus O\rightarrow\mathcal{P}(V\setminus I)$, where $\mathcal{P}$
denotes the powerset, and a partial order over $V$ such that the following
hold for all $v\in V\setminus O$:

  1. 1.

if $v^{\prime}\in g(v)$ and $v^{\prime}\neq v$, then $v<v^{\prime}$;

  2. 2.

if $v^{\prime}\in\operatorname{Odd}(g(v))$ and $v^{\prime}\neq v$, then
$v<v^{\prime}$;

  3. 3.

if $\omega(v)=XY$, then $v\notin g(v)$ and $v\in\operatorname{Odd}(g(v))$;

  4. 4.

if $\omega(v)=XZ$, then $v\in g(v)$ and $v\in\operatorname{Odd}(g(v))$;

  5. 5.

if $\omega(v)=YZ$, then $v\in g(v)$ and $v\notin\operatorname{Odd}(g(v))$;

where $\operatorname{Odd}(K):=\\{\tilde{v}\in V:|N_{\tilde{v}}^{G}\cap
K|=1\bmod 2\\}$ for any $K\subseteq V$.

An intuition for the above definition is as follows. For each $v$, the sets
$g(v)$ and $\operatorname{Odd}(g(v))$ specify the stabiliser element for the
correction: $g(v)$ is the set of vertices that receive an $X$ and
$\operatorname{Odd}(g(v))$ is the set of vertices that receive a $Z$. The
first two conditions of the definition stipulate that the measurement
corrections must occur in the future of the measurement, and the last three
conditions enforce the correcting stabiliser element to have the correct
tensor factor at each vertex corresponding to which plane that vertex was
measured in. It was shown in Theorems $2$ and $3$ of [22] that the gflow is a
necessary and sufficient condition for deterministic MBQC. Accordingly, an
equivalent statement to 2 in the main text is:

######  Theorem 3.

$(G,I,O,\omega\equiv YZ)$ with $|I|=|O|$ has gflow if and only if $G$ is
bipartite with $I$ forming one partition.

Before giving the proof of the above theorem, we require the following lemmas:

######  Lemma 1.

If $(G,I,O,\omega\equiv YZ)$ with $|I|=|O|$ has gflow, then $I=O$.

###### Proof.

Let $(g,<)$ be a gflow for $(G,I,O,\omega)$ and suppose for a contradiction
that $I\neq O$. Since $|I|=|O|$ this means that there exists some $v\in I$
such that $v\notin O$. Accordingly, $v$ is an element of the domain of the map
$g$ but not the codomain so $v\notin g(v)$. Via criterion $5$ of 1, this
contradicts the assumption that $\omega(v)=YZ$. ∎

######  Lemma 2.

Let $(G,I,O,\omega)$ with $I=O$ have gflow $(g,<)$ and let $\prec$ denote the
partial order obtained by restricting $<$ to $V\setminus I$. Then any maximal
element $v$ of $\prec$ must be such that $g(v)=\\{v\\}$ and hence
$\omega(v)=YZ$.

###### Proof.

Since $I=O$, $g$ maps from $V\setminus I$ to $\mathcal{P}(V\setminus I)$. If
$v$ is maximal and $g(v)\neq\\{v\\}$ then there exists a $v^{\prime}\in
g(v)\setminus v$ (no $g(v)$ can be empty otherwise this would contradict
criteria $3$, $4$ or $5$ of 1). By criterion $1$ of 1, this would mean that
$v<v^{\prime}$ and hence also $v\prec v^{\prime}$, contradicting the
maximality of $v$. Hence $g(v)=\\{v\\}$ and this must mean that $\omega(v)=YZ$
since otherwise this would contradict criteria $3$ or $4$. ∎

It is worth noting that, in the case where $I=O$, the restriction from $<$ to
$\prec$ is not a significant one since every $v\in I$ is maximal in $<$.

######  Lemma 3.

Let $(G,I,O,\omega\equiv YZ)$ with $I=O$ have gflow. Then for every $u,v\in
V\setminus I$ and $w\in g(u)$ and $x\in g(v)$, $w\notin N_{x}^{G}$.

Before giving the proof, let us consider some consequences of this lemma.
Taking $u=v=x$, we get that $N_{u}^{G}\cap g(u)=\emptyset$. Taking $u=v$ but
$x\neq w$, we get that no two elements of $g(u)$ are connected by an edge.
Taking $u\neq v$, we get that no element of $g(u)$ is connected to an element
of $g(v)$. As a result, there are no edges between any elements in
$\bigcup_{v\in V\setminus I}g(v)$, which is used in the proof of the theorem
below.

###### Proof.

Suppose $(g,<)$ is a valid gflow for $(G,I,O,\omega\equiv YZ)$ with $I=O$,
which in particular means that $<$ is a valid partial order and criteria $1$,
$2$ and $5$ in 1 are satisfied. Pursuant to 2, we make use of the partial
order $\prec$ which is the restriction of $<$ to $V\setminus I$.

Let $u,v\in V\setminus I$ and $w\in g(u)$ and $x\in g(v)$. Since $G$ is a
simple graph, for $w=x$, $w\notin N_{x}^{G}$ by definition, so we consider
$w\neq x$ forthwith. Suppose for a contradiction that $w\in N_{x}^{G}$. If
$w\in\operatorname{Odd}(g(x))$ and $x\in\operatorname{Odd}(g(w))$, then a
contradiction arises since criterion $2$ requires $w\prec x$ and $x\prec w$.
We consider the following two cases in turn: (a)
$w\notin\operatorname{Odd}(g(x))$ and $x\in\operatorname{Odd}(g(w))$ or
$w\in\operatorname{Odd}(g(x))$ and $x\notin\operatorname{Odd}(g(w))$ and (b)
$w\notin\operatorname{Odd}(g(x))$ and $x\notin\operatorname{Odd}(g(w))$.

Case (a): Since the two sub-cases are the same up to swapping $w$ and $x$, we
consider without loss of generality the case where
$w\notin\operatorname{Odd}(g(x))$ but $x\in\operatorname{Odd}(g(w))$. Since
$w\neq x$, the latter gives that $w\prec x$. Since $x\in N_{w}^{G}$ by
assumption, there must exist a $x_{1}\in g(x)\setminus x$ such that $x_{1}\in
N_{w}^{G}$ in order for $w\notin\operatorname{Odd}(g(x))$ to hold. If
$w\in\operatorname{Odd}(g(x_{1}))$, then a contradiction arises since the
criteria of gflow would require that $w\prec x\prec x_{1}\prec w$. If
$w\notin\operatorname{Odd}(g(x_{1}))$, then there must exist a $x_{2}\in
g(x_{1})\setminus x_{1}$ such that $x_{2}\in N_{w}^{G}$. By iterating the
above reasoning, a sequence of vertices $x_{1},x_{2},...,x_{l}$ is generated
for which $x_{i+1}\in g(x_{i})\setminus x_{i}$, $x_{i+1}\in N_{w}^{G}$, and
$w\notin\operatorname{Odd}(g(x_{i+1}))$ for each $i=1,...,l-1$. However, after
finitely many steps, this sequence must terminate with some $x_{l+1}$ such
that $w\in\operatorname{Odd}(g(x_{l+1}))$: in the worst case, this occurs when
$x_{l+1}$ is a maximal element of $\prec$, which from 2 means that
$g(x_{l+1})=\\{x_{l+1}\\}$ and thus $w\in\operatorname{Odd}(g(x_{l+1}))$. The
contradiction arises since $w\prec x\prec x_{1}\prec...\prec x_{l}\prec
x_{l+1}\prec w$.

Case (b): If $w\notin\operatorname{Odd}(g(x))$ and
$x\notin\operatorname{Odd}(g(w))$ but $w\in N_{x}^{G}$, then there must exist
$w_{1}\in g(w)\setminus w$ and $x_{1}\in g(x)\setminus x$ such that $x_{1}\in
N_{w}^{G}$ and $w_{1}\in N_{x}^{G}$. If $w\in\operatorname{Odd}(g(x_{1}))$ and
$x\in\operatorname{Odd}(g(w_{1}))$, then a contradiction arises since $w\prec
w_{1}\prec x\prec x_{1}\prec w$. If $w\notin\operatorname{Odd}(g(x_{1}))$ and
$x\in\operatorname{Odd}(g(w_{1}))$ or $w\in\operatorname{Odd}(g(x_{1}))$ and
$x\notin\operatorname{Odd}(g(w_{1}))$, then we are in a similar situation to
Case (a) above. By analogous reasoning, we obtain a sequence of vertices
$x_{1}\prec x_{2}\prec...\prec x_{l}$ such that there exists a $x_{l+1}\in
g(x_{l})\setminus x_{l}$ for which $w\in\operatorname{Odd}(g(x_{l+1})$,
producing a contradiction via $w\prec w_{1}\prec x\prec x_{1}\prec...\prec
x_{l+1}\prec w$.

If both $w\notin\operatorname{Odd}(g(x_{1}))$ and
$x\notin\operatorname{Odd}(g(w_{1}))$ hold then we are in a scenario similar
to that defining Case (b) to begin with. Accordingly, there must exist
$w_{2}\in g(w_{1})\setminus w_{1}$ and $x_{2}\in g(x_{1})\setminus x_{1}$ such
that $x_{2}\in N_{w}^{G}$ and $w_{2}\in N_{x}^{G}$. By iterating the above
splitting into cases and the corresponding reasoning, we obtain sequences of
vertices $w\prec w_{1}\prec...\prec w_{l}$ and $x\prec x_{1}\prec...\prec
x_{l}$ which must terminate (in the worst case) with either $g(w_{l})\setminus
w_{l}$ or $g(x_{l})\setminus x_{l}$ containing a maximal element $w_{l+1}$ or
$x_{l+1}$ respectively, and hence $w\in\operatorname{Odd}(g(x_{l+1}))$ or
$x\in\operatorname{Odd}(g(w_{l+1}))$. Without loss of generality, suppose that
$x\in\operatorname{Odd}(g(w_{l+1}))$. If $w\in\operatorname{Odd}(g(x_{l+1}))$,
then we obtain a contradiction via $w\prec w_{1}\prec...\prec w_{l+1}\prec
x\prec x_{1}\prec...\prec x_{l+1}\prec w$. If
$w\notin\operatorname{Odd}(g(x_{l+1}))$, then we are again in a scenario
similar to Case (a), which by analogous reasoning also terminates in a
contradiction. ∎

The proof of 3 proceeds as follows:

###### Proof.

Suppose $G$ is bipartite and denote one partition by $I$. Consider $(g,<)$
where $g$ is defined by $v\mapsto\\{v\\}$ for all $v\in V\setminus I$ and (ii)
$<$ is the coarsest partial order such that the vertices in $V\setminus I$
precede those in $I$. That criteria $1$, $2$ and $5$ in the definition of
gflow are satisfied for all $v\in V\setminus I$ can be readily verified, hence
$(g,<)$ is a valid gflow for $(G,I,O=I,\omega\equiv YZ)$. Clearly, with this
choice of $O$, the requirement that $|I|=|O|$ is satisfied.

For the opposite direction, suppose $(G,I,O,\omega)$ with $\omega\equiv YZ$
and $|I|=|O|$ has gflow $(g,<)$. From 1, we know that $I=O$. From 3, we know
that for each $u,v\in V\setminus I$, there are no edges between elements of
$g(u)$ and also no edges between elements of $g(u)$ and $g(v)$. Consequently,
there are no edges between elements of $g(V\setminus I):=\bigcup_{v\in
V\setminus I}g(v)$. Accordingly, we can partition $G$ into those vertices in
$g(V\setminus I)\equiv V\setminus I$ and those in $I$. ∎


# Genus Zero Complete Maximal Maps and Maxfaces with an Arbitrary Number of
Ends

Pradip Kumar  Department of Mathematics, Shiv Nadar Institute of Eminence,
Deemed to be University, Dadri 201314, Uttar Pradesh, India.
<EMAIL_ADDRESS>and  Sai Rasmi Ranjan Mohanty  Department of
Mathematics, Shiv Nadar Institute of Eminence, Deemed to be University, Dadri
201314, Uttar Pradesh, India<EMAIL_ADDRESS>
###### Abstract.

We prove the existence of a genus-zero complete maximal map with a prescribed
singularity set and an arbitrary number of simple and complete ends. We also
discuss the conditions under which this maximal map can be made into a
complete maxface.

###### Key words and phrases:

complete maxface, maximal map, zero mean curvature surfaces.

###### 2020 Mathematics Subject Classification:

53A35

##  1\. Introduction

Similar to minimal surfaces in $\mathbb{R}^{3}$, maximal surfaces are
immersions with zero mean curvature in the Lorentz Minkowski space
$\mathbb{E}_{1}^{3}$. Maximal surfaces share many similarities with minimal
surfaces, such as being critical points of the area functional and admitting
the Weierstrass-Enneper representation. However, the theory of complete
maximal immersions is limited compared to the theory of complete minimal
surfaces. It has been proven [UMEHARA2006] that the plane is the only complete
maximal immersion.

Maximal immersions naturally appear with singularities. Following the
terminology from [imaizumi2008], [LOPEZ20072178], [UMEHARA2006], etc., we use
the term “maximal map" to refer to generalized maximal immersions. Maxfaces
are a subclass of generalized maximal immersions where the singularities occur
only at points where the limiting tangent plane contains a light-like vector
[UMEHARA2006].

The object of the discussion in this article is genus-zero maximal maps and
maxfaces. We summarize the existing results and examples for genus-zero
complete maximal maps/maxfaces as follows:

  1. (1)

The space-like plane is a maximal immersion.

  2. (2)

The Lorentzian catenoid is a maxface with two complete, embedded ends.

  3. (3)

The trinoid is also a genus-zero maxface with three embedded ends
[Fujimori2009].

  4. (4)

In [Fujimori2009], the authors provide an example of a genus-zero maxface with
two complete ends, with swallowtails, cone-like features, cuspidal edge, and
cuspidal crosscaps. These ends are not embedded.

  5. (5)

Imaizumi and Kato [imaizumi2008] discuss different types of simple ends and
classify maximal surfaces of genus zero with at most three embedded ends.

In [imaizumi2008], authors discuss the classifications of ends of the maximal
map, and in [Ando], we see the regularity results about the ends of zero mean
curvature surfaces in the Lorentz-Minkowski space.

The question addressed in this article is as follows:

######  Question 1.1.

Given a prescribed singular set and the prescribed nature of singularity, can
we construct a genus-zero maximal map or maxface with an arbitrary number of
simple ends and complete ends?

One possible approach to constructing a maximal map or maxface is by starting
with a minimal immersion. For a minimal immersion, there exists a
corresponding maximal immersion (known as a companion [UMEHARA2006]). However,
this method does not always yield a complete maxface. An example of this is
the Jorge-Meeks minimal surface [Meeks1983].

Weierstrass data for Jorge-Meek’s minimal surface is the following:

$g(z)=z^{n}\mbox{ and }\omega=\dfrac{dz}{(z^{n+1}-1)^{2}}.$

This gives a complete minimal surface on $\mathbb{C}\cup\\{\infty\\}$ with
punctures $\\{1,\zeta,\zeta^{2},...,\zeta^{n-1}\\}$, where
$\zeta=e^{\frac{2i\pi}{n}}$. We see $(g_{0}=ig,\omega_{0}=\omega)$ gives a
maximal map, but this is not complete maxface since the singular set is not
compact.

To construct a complete maximal map or maxface, the Björling problem and its
solution are not always sufficient. In some cases, starting from the Björling
data leads to a non-complete maxface. Examples in [Kim2007] (for instance, see
Example 3.11) do not provide the Weierstrass data for complete maxfaces.

To construct examples of complete maxfaces, we need to find a suitable
meromorphic function $g$ and a holomorphic 1-form $\omega$ on
$\mathbb{C}\cup\\{\infty\\}\setminus\\{p_{1},...,p_{n}\\}$ that satisfies the
period condition (as in (3) of Theorem 2.1). However, unlike in the case of
minimal surfaces, when solving the balance equation of the period problem, we
have to ensure that the meromorphic function $g$ is chosen in a way that
$|g(p_{i})|\neq 1$ after extension to the ends. Due to this restriction, most
methods and techniques used for minimal surfaces can not be directly applied.

In this article, we prove the existence of maximal maps or maxfaces with
complete ends, and since we are not specifically looking for embedded ends,
the method for solving the period problem can be simplified. Here, we explain
the method we will use.

For any $r$ and the subset $\\{p_{1},...,p_{r}\\}\subset\mathbb{C}$, if we
take

$f(z)=\frac{dz}{(z-p_{1})^{2}\cdots(z-p_{r})^{2}};\mbox{ and
}g(z)=\sum_{i=0}^{r-1}a_{i}z^{i}+\sum_{j=1}^{r}\frac{b_{j}}{z-p_{i}},$

then it is well-known (see [KichoonBook]) that there exist constants $a_{i}$’s
and $b_{j}$’s such that $(g,f(z)dz)$ gives a complete branched minimal surface
on $\mathbb{C}\cup\\{\infty\\}\setminus\\{p_{1},...,p_{r}\\}$. The same data
and solution can be used to obtain a maximal map with any number of ends.
However, this solution does not guarantee that $|g(p_{i})|\neq 1$ at the ends,
and thus we do not obtain complete ends. Moreover, the $a_{i}$’s and $b_{j}$’s
are not explicitly determined, so we do not have control over the exact
singularity set for the maxface. In this article, we will modify this method
to solve the period problem and find the desired maxface or maximal map.

In Section 3, we explain the period problem and prove the following results:

  1. (1)

Let $C$ be a singular curve in $\mathbb{C}$ as defined in the definition 3.1,
and let $m,n\in\mathbb{N}^{*}$. Then:

    1. (a)

(Theorem 3.4) there exists a maximal map with $m$ complete ends and $C$ as its
singularity set.

    2. (b)

(Theorem 3.6) there is a maximal map with $m$ complete ends, $n$ simple ends,
and $C$ as its singularity set. All simple ends, in this case, are embedded.

  2. (2)

(Theorem 3.5) Let
$X:\mathbb{C}\cup\\{\infty\\}\setminus\\{p_{1},...,p_{n}\\}\to\mathbb{E}_{1}^{3}$
be a complete maximal map with the Gauss map $g$. Then, there exists a finite
set $E$ and a family of complete maxfaces on $M\setminus E$ with the Gauss map
$\tilde{g}$, such that $\tilde{g}$ is very close to $g$ away from the ends.

It is important to note that these results are trivially solved in the case of
minimal immersions (such as the Jorge-Meeks surface). However, for maximal
surfaces, due to the presence of non-isolated singularities, finding such
results requires a slightly different approach.

##  2\. Preliminary

We denote the Lorentz Minkowski space as $\mathbb{E}_{1}^{3}$, which is the
vector space $\mathbb{R}^{3}$ with the metric $dx^{2}+dy^{2}-dz^{2}$. Similar
to the case of minimal immersions, Esutidillo and Romero [Estudillo1992] have
proved the Weierstrass-Enneper representation for generalized maximal
immersions (maximal maps). We mention it here.

######  Theorem 2.1 (Weierstrass-Enneper representation for maximal maps
[Estudillo1992]).

Let $M$ be a Riemann surface, $g$ be a meromorphic function, and
$\omega=f(z)dz$ be a holomorphic 1-form on $M$ such that:

  1. (1)

If $p\in M$ is a pole of $g$ of order $m$, then $f$ has a zero at $p$ of order
at least $2m$.

  2. (2)

$|g|\not\equiv 1$ on $M$.

  3. (3)

$Re\int_{\gamma}((1+g^{2})\omega,i(1-g^{2})\omega,-2g\omega)=0$ for all closed
loops $\gamma$ on $M$.

Then, the map $X:M\to\mathbb{E}_{1}^{3}$ given by

(2.1) $X(p)=Re\int_{0}^{p}((1+g^{2})\omega,i(1-g^{2})\omega,-2g\omega)$

is a maximal map with base point $0\in M$.

Moreover, any maximal map can be expressed in this form.

The third condition in the above theorem 2.1 is called the period condition.
For the maximal map $X:M\to\mathbb{E}_{1}^{3}$ with the Weierstrass data
$(g,\omega)$, the pullback metric is given by
$ds^{2}=(1-|g|^{2})^{2}|\omega|^{2}$.

The singularities of the maximal map $X:M\to\mathbb{E}_{1}^{3}$ are given by
the set $Sing(X)=\\{p\in M:|g(p)|=1\text{ or }\omega(p)=0\\}$. We call the set
$\\{p\in M:|g(p)|=1\\}$ the singularity set of the maximal map and $\\{p\in
M:\omega(p)=0\\}$ the set of branch points.

For the maxface, there are no branch points, and we have a singularity where
$|g|=1$ and $\omega\neq 0$. Therefore, if $(g,\omega)$ is the Weierstrass data
for the maxface, we must have

(2.2) $(\omega)_{0}=2(g)_{\infty}\text{ on }M.$

We refer to the above equation as the divisor condition.

The completeness of a maxface can be understood using the following equivalent
criteria:

######  Fact 2.2.

A maxface is complete (see [UMEHARA2006], corollary 4.8) if and only if:

  1. (1)

$M$ is bi-holomorphic to $\overline{M}\setminus\\{p_{1},...,p_{n}\\}$.

  2. (2)

$|g|\neq 1$ at $p_{i}$, $1\leq i\leq n$.

  3. (3)

The induced metric $ds^{2}$ is complete at the ends.

In this case, the points $p_{i}$’s are called ends for the maxface, and $g$
and $\omega$ can be extended as meromorphic function and meromorphic 1-form
respectively at the ends.

Similarly, for the maximal map defined on
$\overline{M}\setminus\\{p_{1},...,p_{n}\\}$, we say it is a complete maximal
map if and only if $|g(p_{i})|\neq 1,1\leq i\leq n,$ and the induced metric
$ds^{2}$ is complete at the ends.

In the next section, we will prove the existence of a maximal map with an
arbitrary number of complete ends and a prescribed singularity set. We will
start the discussion by finding a complete maximal map with the prescribed
Gauss map.

##  3\. Genus zero complete maxface with prescribed singularities

We will start this section by constructing a maximal map with a given Gauss
map.

###  3.1. Maximal map with an arbitrary number of complete ends and a
prescribed Gauss map

Let $g$ be a meromorphic function on $\mathbb{C}\cup\\{\infty\\}$ such that

(3.1) $(g)_{\infty}=\sum_{i=1}^{n}x_{i}p_{i},\quad
x_{i}\in\mathbb{N}^{*},1\leq i\leq n.$

Without loss of generality, we assume $p_{n}=\infty$.

Next, we will find a suitable holomorphic 1-form $\omega$ such that
$(g,\omega)$ becomes the Weierstrass data for a maximal map $X$ defined on
$\mathbb{C}\cup\\{\infty\\}\setminus\\{p_{1},...,p_{n}\\}$, and all the ends
are complete.

Consider the following expression for $f(z)$:

(3.2)
$f(z)=\sum_{i=1}^{n-1}\frac{a_{i}}{(z-p_{i})^{2}}+\sum_{j=0}^{2n-2}b_{j}z^{j},$

where $a_{i},b_{j}\in\mathbb{C}$ (we will find suitable values for $a_{i}$’s
and $b_{j}$’s). Set $\omega_{0}:=f(z)dz$.

We need to show that there exist constants $(a_{i};b_{j})\in\mathbb{C}^{3n-2}$
such that the period condition, as in the theorem 2.1, holds for all loops on
$\mathbb{C}\cup\\{\infty\\}\setminus\\{p_{1},...,p_{n}\\}$. Since $\omega_{0}$
is an exact form, and if $g^{2}\omega_{0}$ and $g\omega_{0}$ have no residues
on $\mathbb{C}\cup\\{\infty\\}$, the pair $(g,\omega_{0})$ satisfies the
period condition. Therefore, we need to find values of $(a_{i};b_{j})$ such
that the following equations hold:

(3.3)
$\text{Res}_{p_{i}}(g\omega_{0})=0,\quad\text{Res}_{p_{i}}(g^{2}\omega_{0})=0,\quad
1\leq i\leq n.$

Equation 3.3 gives a homogeneous system of linear equations in the variables
$a_{i}$ and $b_{j}$. Moreover, since the total residues of $g\omega_{0}$ and
$g^{2}\omega_{0}$ are zero on $\mathbb{C}\cup\\{\infty\\}$, we have a
homogeneous system of at most $2n-2$ linear equations in $3n-2$ variables
$a_{i}$ and $b_{j}$. Therefore, the solution space (denoted by
$Sol\subset\mathbb{C}^{3n-2}$) for the system of equations 3.3 has a dimension
of at least $n$. This proves that we can choose suitable $(a_{i};b_{j})\in
Sol\setminus\\{0\\}$ such that $(g,\omega_{0})$ satisfies the period
condition.

Since $\omega_{0}$ has poles at $p_{i}$’s, the divisor condition for
$(g,\omega_{0})$, as stated in the theorem 2.1, holds trivially on
$\mathbb{C}\cup\\{\infty\\}\setminus\\{p_{1},...,p_{n}\\}$. Moreover, since
the solution space is of dimension $n$, for $(a_{i};b_{j})\in
Sol\setminus\\{0\\}$, at least one of the $b_{j}$’s is non-zero. Therefore,
$p_{n}$ is a pole of both $\omega_{0}$ and $g$, making $p_{n}$ a complete end
for the maximal map.

However, it may happen that for some $i$ ($1\leq i\leq n-1$), $a_{i}=0$, in
which case $p_{i}$ may be a zero of $\omega_{0}$. Thus, while the pair
$(g,\omega_{0})$ gives a maximal map, $p_{i}$ may not be a complete end for
this maximal map. To address this, we aim to modify $\omega_{0}$ such that the
resulting pair becomes the Weierstrass data for a maximal map with all
$p_{i}$’s as poles of $\omega_{0}$, ensuring that all $p_{i}$’s are complete
ends.

To achieve this, for $1\leq i\leq n-1$, we consider

$f_{i}=\sum_{k=1}^{2n}\frac{\alpha_{k}}{(z-p_{i})^{2+k}}$

and we want to find $(\alpha_{k})\in\mathbb{C}^{2n}$ with at least one
$\alpha_{k}\neq 0$ such that $(g,f_{i})$ satisfies the period condition on
$\mathbb{C}\cup\\{\infty\\}$. By using the technique mentioned earlier, i.e.,
$Res_{p_{j}}(gf_{i}dz)=0$ and $Res_{p_{j}}(g^{2}f_{i}dz)=0$ for $1\leq j\leq
n$, we obtain $2n-2$ independent linear homogeneous equations with $2n$
variables. Therefore, there exists
$(\alpha_{k})\in\mathbb{C}^{2n}\setminus\\{0\\}$ such that $(g,f_{i})$
satisfies the period condition and $p_{i}$ is a pole of $f_{i}$.

Let $F:=f+\sum_{i=1}^{n-1}f_{i}$ and ${\omega}:=F(z)dz$. It is clear that $g$
and ${\omega}$ satisfy the divisor condition and the period condition on
$\mathbb{C}\cup\\{\infty\\}\setminus\\{p_{1},...,p_{n}\\}$. Moreover, all
$p_{i}$’s are poles of $g$ and ${\omega}$, making all ends complete.

To have a complete maximal map
$X:\mathbb{C}\cup\\{\infty\\}\setminus\\{p_{1},...,p_{n}\\}\to\mathbb{E}_{1}^{3}$
with the Weierstrass data $(g,{\omega})$, we only need to prove that the
singular set is compact. It is evident from the fact that $g$ has poles at the
ends and the manner in which we adjusted $\omega_{0}$ to obtain $\omega$,
which implies that $\\{z:|g|=1\\}\cup\\{z:{\omega}(z)=0\\}$ is compact.

To summarize, we have proved the following proposition:

######  Proposition 3.1.

Let $g$ be a meromorphic function on the Riemann sphere such that the number
of distinct poles of $g$ is $n$. Then there exists a maximal map with $n$
complete ends having the Gauss map $g$.

The maximal map obtained from the proposition 3.1 is not necessarily a maxface
because the 1-form $\omega$ may have some zeros on
$\mathbb{C}\cup\\{\infty\\}\setminus\\{p_{1},...,p_{n}\\}$. In subsection 3.3,
we will perturb the Gauss map to obtain the complete maxface. Furthermore, the
above method takes care of the ends as complete, but in this process, we
obtain higher-order poles at the ends, which prevents the possibility of
embedded ends.

Moreover, if we replace $F$ as defined above by

(3.4) $F(z)=\sum_{i=1}^{2n}a_{i}h^{i},$

where, for $n\geq 2$,
$h(z)=\prod_{j=1}^{n-1}\frac{(z-c)^{2n-2}}{(z-p_{j})^{2}}$ and $c\neq p_{j}$
for $1\leq j\leq n$, and for $n=1$, $h(z)$ is any polynomial, we obtain the
same result. Additionally, there are other ways to define the required
$\omega$. In all these cases, we can increase the number of variables to
obtain a larger dimensional solution space, which may help us in obtaining the
maxface with a prescribed nature of singularity. This aspect needs to be
explored further.

Below, we will define the singular curve and discuss the possibility of the
existence of a maximal map with such a curve as its singularity set.

###  3.2. Maximal map with an arbitrary number of complete ends and a
prescribed singularity set

For a given curve or collection of disjoint union of curves
$C\subset\mathbb{C}$, we aim to find a complete maximal map with an arbitrary
number of complete ends such that $C$ is the singularity set. So firstly, for
a given $C$, we will be looking for the meromorphic function $g$ on
$\mathbb{C}\cup\\{\infty\\}$ such that for $z\in C$, $|g(z)|=1$, and then
applying the proposition 3.1, we will get the required maximal map.

Considering the above, we will take $C$ as follows in the rest of the article.

######  Definition 3.1.

The singular curve $C$ is a curve or disjoint union of curves such that there
exists a meromorphic function $g$ on $\mathbb{C}\cup\\{\infty\\}$ such that
$g(C)$ is mapped to the circle $|z|=R$.

There are many examples of singular curves. Below, we present two examples
that constitute a significant class of singular curves.

######  Example 3.2.

We begin by recalling the definition of the Schwarzian derivative of a
meromorphic function $f(z)$;
$S[f](z):=\left(\frac{f^{\prime\prime}(z)}{f^{\prime}(z)}\right)^{\prime}-\frac{1}{2}\left(\frac{f^{\prime\prime}(z)}{f^{\prime}(z)}\right)^{2}.$
The Möbius transformations are the only functions for which $S[f](z)=0$
[Osgoos].

Consider a regular simple closed curve $C$ such that the Schwarzian derivative
of any conformal parameterization $f(z)$ of $C$ is identically zero. In this
case, there exists a meromorphic function $G(z)$ on
$\mathbb{C}\cup\\{\infty\\}$ that maps $C$ to the unit circle.

######  Example 3.3.

Another example of a singular curve is the subset $C=|G|^{-1}(1)$, where $G$
is defined as follows:

$G(z)=\frac{(z-1)(z^{2}+3z+1)}{(z+1)(z^{2}-3z+1)}.$

This curve and the meromorphic function $G$ are taken from the proof of the
theorem A [Fujimori2009], where the authors investigated various types of
singularities on maxfaces. For this particular $G$, the singular curve $C$
consists of three disjoint (topological) circles on the Riemann sphere,
including the imaginary axis.

Moreover, any meromorphic function $G$ that maps a circle of radius $R$ to the
unit circle is a Blaschke product, as discussed by Gronwall in [Gronwall1912],
and is given by

(3.5)
$G(z)=\prod_{i=1}^{m}\frac{R(z-a_{i})}{a_{i}(z-a_{i}^{\prime})}\prod_{j=1}^{n}\frac{b_{j}(z-b_{j}^{\prime})}{R(z-b_{j})},$

where $a_{i}$, $1\leq i\leq m$, and $b_{j}$, $1\leq j\leq n$, are points
inside the circle $|z|=R$, and $a_{i}a_{i}^{\prime}=R^{2}$ and
$b_{j}b_{j}^{\prime}=R^{2}$. For $a_{i}=0$, the factor
$\frac{R(z-a_{i})}{a_{i}(z-a_{i}^{\prime})}$ in the equation 3.5 is replaced
by $-\frac{z}{R}$, and for $b_{j}=0,$ the factor
$\frac{b_{j}(z-b_{j}^{\prime})}{R(z-b_{j})}$ is replace by $-\frac{R}{z}$.
Note that $a_{i}$’s and $b_{j}$’s are repeated according to the order of zeros
and poles.

For the given singular curve $C$, as defined in the definition 3.1, there is a
meromorphic map $f:\mathbb{C}\cup\\{\infty\\}\to\mathbb{C}\cup\\{\infty\\}$
such that $f(C)$ is the circle of radius $R$. We choose $G$ as described in
the equation 3.5 and compose it with the meromorphic map $f$. This composite
map, denoted as $g$, satisfies $|g(z)|=1$ on $C$. Additionally, by choosing
$G$ appropriately, we have the flexibility to increase the number and order of
poles of $g$.

Furthermore, after the change of coordinates, we assume that one of the poles
of $g$ is at $\infty$. We denote the poles of $g$ as $p_{i}$, where $1\leq
i\leq n$, and write $(g)_{\infty}=\sum_{i=1}^{n}x_{i}p_{i}$, as in the
equation 3.1.

Now, if we start with the meromorphic function $g$ as described in the
previous paragraph, we can use the proposition 3.1 to establish the following
theorem:

######  Theorem 3.4.

Given a singular curve $C$ as in the definition 3.1, and $m\in\mathbb{N}^{*}$,
there exists a maximal map with $m$ complete ends and $C$ as its singularity.

Theorem 3.4 establishes the existence of the desired maximal map. However, if
we want a maxface, we can get it by slightly modifying the normal vector (the
Gauss map $g$). Specifically, in the following subsection, given a complete
maximal map with Weierstrass data $(g,\omega)$, we will find a suitable
meromorphic function $g_{0}$ such that $(\tilde{g}=g+g_{0},\omega)$ yields a
complete maxface. Moreover, $\tilde{g}$ can be chosen arbitrarily close to
$g$, away from the ends.

###  3.3. Perturbation of the Weierstrass data for the complete maxface

Let $(g,\omega=fdz)$, as defined in the equations 3.1 and 3.4 respectively, be
the Weierstrass data for the maximal map
$X:\mathbb{C}\cup\\{\infty\\}\setminus\\{p_{1},\ldots,p_{n}\\}\to\mathbb{E}_{1}^{3}$
with complete ends, as stated in the theorem 3.4.

Let $\\{z_{j}:1\leq j\leq l\\}$ be the zeros of $\omega$ and
$Ord_{z_{j}}\omega=m_{j}>0$. With $\alpha_{i}\in\mathbb{C}$, we define

(3.6) $\displaystyle
g_{0}(z)=\frac{1}{\prod_{j=1}^{l}(z-z_{j})^{2m_{j}}}\left(\sum_{i=1}^{3(l+n)}\alpha_{i}z^{i}\right).$

We take $\tilde{g}=g+g_{0}$. In the following, we will determine
$(\alpha_{i})\in\mathbb{C}^{3(l+n)}$ such that $(\tilde{g},\omega)$ serves as
the Weierstrass data for the complete maxface on
$\mathbb{C}\cup\\{\infty\\}\setminus\\{p_{1},\ldots,p_{n},z_{1},\ldots,z_{l}\\}$,
with $\tilde{g}$ being close to $g$ away from the ends.

The divisor condition, as given in the equation 2.2, trivially holds for it to
be a maxface.

If the period condition holds for $(\tilde{g},\omega)$, then the corresponding
maxface will be complete. This follows from the construction, since we observe
that $|\tilde{g}|\neq 1$ at the ends $\\{p_{i};z_{j}:1\leq i\leq n,1\leq j\leq
l\\}$. Additionally, at the end, the metric $ds^{2}$ is complete. Hence, all
ends are complete.

Thus, we need to find $(\alpha_{i})$ such that the period condition for
$(\tilde{g},\omega)$ is satisfied. Since $g\omega$ and $g^{2}\omega$ have no
residues on $\mathbb{C}\cup\\{\infty\\}$ and $\omega$ is exact, we need to
find $(\alpha_{i})$ such that $g_{0}\omega$, $g_{0}^{2}\omega$, and
$gg_{0}\omega$ have no residues on $\mathbb{C}\cup\\{\infty\\}$. This can be
achieved by employing the same technique as in subsection 3.1.

Moreover, for any $\epsilon>0$, the vector
$\epsilon\alpha=(\epsilon\alpha_{i})$ is also a solution. Therefore, $g_{0}$
can be suitably chosen such that away from the ends $z_{j}$, we have
$|g_{0}|<\epsilon$. This proves that $|\tilde{g}-g|=|g_{0}|$ is very small
away from the ends.

Combining all the above, we establish the following result:

######  Theorem 3.5.

Let
$X:M=\mathbb{C}\cup\\{\infty\\}\setminus\\{p_{1},\ldots,p_{n}\\}\to\mathbb{E}_{1}^{3}$
be a complete maximal map with the Gauss map $g$. Then, there exists a finite
set $E$ and a family of complete maxfaces on $M\setminus E$ with the Gauss map
$\tilde{g}$ such that $\tilde{g}$ is very close to $g$ away from the ends.

In all of the above proofs, we solved the period problem by increasing the
order of poles and variables sufficiently. This ensured the existence of
complete ends, but it did not guarantee simple ends. However, with some
modifications and a similar technique, it is possible to obtain a maximal map
with the prescribed simple ends. We explain the approach here.

###  3.4. Maximal map with a given Gauss map and an arbitrary number of simple
ends

Let $g$ be a meromorphic function as defined in the equation 3.1, and for any
$q_{j}$ (where $1\leq j\leq m$) on $\mathbb{C}$ distinct from $p_{i}$’s, we
aim to find a suitable holomorphic 1-form $\omega$ such that $(g,\omega)$
serves as the Weierstrass data for the complete maximal map on
$\mathbb{C}\cup\\{\infty\\}\setminus\\{p_{1},\ldots,p_{n},q_{1},\ldots,q_{m}\\}$,
where $p_{i}$’s are complete ends and $q_{j}$’s are simple (in particular,
embedded) ends.

We introduce some $a_{i}$’s and, we define

(3.7)
$f(z)=\frac{1}{\prod_{j=1}^{m}(z-q_{j})^{2}}\left(\sum_{i=1}^{2m+2n}a_{i}h^{i}\right),$

where for $n\geq 2$,
$h(z)=\prod_{k=1}^{n-1}\frac{(z-c)^{2n-2}}{(z-p_{k})^{2}}$ and $c\neq p_{i}$
for $1\leq i\leq n$, and for $n=1$, $h(z)$ is any polynomial.

By employing a similar technique as discussed in the section 3.1, we can prove
that there exists a choice of $(a_{i})$ such that $(g,f(z)dz)$ provides the
desired maximal map.

Formally, we state the theorem as follows:

######  Theorem 3.6.

Given a meromorphic function $g$ and $m\in\mathbb{N}^{*}$, there exists a
maximal map with complete ends at the poles of $g$ and $m$ simple ends. All
simple ends, in this case, are embedded.

Again, if we examine the proof, we realize that the choice of $f(z)$ is
flexible. We have the freedom to increase the variables and points to obtain
any desired number of ends.

##  4\. General remarks and conclusion

The main results of this article are presented in theorems 3.4, 3.5, and 3.6.
These theorems establish the existence of maxfaces/maximal maps with a
prescribed singular set and an arbitrary number of complete ends, as well as
simple ends. However, finding such non-complete maxfaces is straightforward.
For example, if we take $a,b,c,d$ and $e$ as distinct real numbers and set
$g(z)=e^{iz}$ and $f(z)=((z-b)(z-d)^{2}-i(z-c)(z-e)^{2})e^{-iz}$, then
$(g,f(z)dz)$ forms a Weierstrass data for a non-complete maxface on
$\mathbb{C}$. An interesting observation, in this case, is that the
singularities at $a,b,c,d$, and $e$ correspond to cuspidal-edge, swallowtails,
cuspidal-butterflies, cuspidal $S_{1}^{-}$, and cuspidal-crosscaps,
respectively.

Similar questions can be posed regarding the existence of complete maxfaces
with various prescribed types of singularities occurring at different points.
As the solution space for the required constants is vast, it is likely
possible to choose suitable constants. However, this requires an improved
method for solving the period problem.

##  5\. Acknowledgments

The authors would like to express their sincere gratitude to the anonymous
reviewers for their valuable comments and suggestions, which greatly
contributed to the improvement of this article.

## References


11institutetext: University of Alberta, Edmonton, Alberta, Canada
22institutetext: Indian Institute of Technology (BHU), Varanasi, India
33institutetext: Indian Institute of Technology, Guwahati, India
44institutetext: ChainRisk Research, India

# Analyzing Games in Maker Protocol Part One: A Multi-Agent Influence Diagram
Approach Towards Coordination

Abhimanyu Nag 1144 Samrat Gupta 44 Sudipan Sinha 2244 Arka Datta 3344

###### Abstract

Decentralized Finance (DeFi) ecosystems, exemplified by the Maker Protocol,
rely on intricate games to maintain stability and security. Understanding the
dynamics of these games is crucial for ensuring the robustness of the system.
This motivating research proposes a novel methodology leveraging Multi-Agent
Influence Diagrams (MAID), originally proposed by Koller and Milch, to dissect
and analyze the games within the Maker stablecoin protocol. By representing
users and governance of the Maker protocol as agents and their interactions as
edges in a graph, we capture the complex network of influences governing agent
behaviors. Furthermore in the upcoming papers, we will show a Nash Equilibrium
model to elucidate strategies that promote coordination and enhance economic
security within the ecosystem. Through this approach, we aim to motivate the
use of this method to introduce a new method of formal verification of game
theoretic security in DeFi platforms.

###### Keywords:

DeFi Multi-Agent Influence Diagrams Maker ProtocolGame Theory Formal
Verification Security

##  1 Introduction

Decentralized Finance (DeFi) [2] has emerged as a transformative force in the
financial landscape, offering innovative solutions that challenge traditional
centralized systems [1]. At the forefront of this movement lies the Maker
Protocol [4], a cornerstone of the DeFi ecosystem, providing the
infrastructure for the creation and governance of the Dai stablecoin (see
[5]). However, the stability and security of DeFi platforms like Maker heavily
rely on intricate coordination games, which necessitate a deep understanding
of their dynamics.

In this research, we propose a novel methodology for dissecting and analyzing
the games within the Maker Protocol and in turn, similar stablecoin protocols,
leveraging Multi-Agent Influence Diagrams (MAIDs) [3]. Originally introduced
by Koller and Milch in 2003, MAIDs offer a powerful framework for modeling
complex decision-making scenarios involving multiple agents with competing or
aligned objectives. By representing users of the Maker protocol as agents and
their interactions as edges in a graph, we capture the intricate network of
influences that govern user behaviors within the ecosystem.

Our research aims to shed light on the interplay between incentives,
behaviors, and outcomes within the Maker Protocol. By employing MAIDs, we aim
to systematically analyze the incentives driving user decisions, identify
vulnerabilities in the system, and optimize incentive mechanisms to enhance
the stability and security of the platform. Furthermore, we will introduce a
Nash Equilibrium model [6, 7] in next papers to elucidate strategies that
promote coordination among users, fostering economic security and resilience
in the DeFi ecosystem.

Through this approach, we not only contribute to a deeper understanding of the
Maker Protocol but also provide a methodology that can be extended to other
DeFi platforms. By fortifying coordination security and mitigating risks, our
research seeks to pave the way for the continued growth and adoption of
decentralized financial systems, ushering in a new era of financial
inclusivity and innovation. This paper focuses on construction of MAIDs for
the Maker protocol and the subsequent iterations would involve employing the
ideas of MAID to conduct a full length equilibrium analysis of the protocol
using the mathematical ideas presented in the following sections.

##  2 Background

###  2.1 Multi Agent Influence Diagrams

Multi Agent Influence Diagrams (MAIDs) combine the ideas of Bayesian Networks
(BNs) [8] and Influence Diagrams [9] to describe decision problems related to
multiple agents. MAIDs are graphical models used to represent decision-making
scenarios involving multiple agents, each with their own objectives, beliefs,
and actions. They extend the traditional influence diagram framework to
accommodate the complexities of interactions and dependencies among multiple
decision-makers. In a MAID, nodes represent variables such as decisions,
uncertainties, utilities, and influences, while directed edges indicate causal
relationships or dependencies between them. Each agent is associated with a
subset of nodes, representing their local decisions, beliefs, and preferences
(see [3]). MAIDs allow for the explicit representation of interactions between
agents, including cooperation, competition, coordination, and negotiation.
This enables the analysis of strategic interactions and the prediction of
outcomes resulting from the decisions of multiple agents. There has been a lot
of related work done by Google Deepmind (see [10, 11]) on agent incentives for
artificial intelligence architectures which forms the underlying motivator to
try and bring the same ideas to DeFi.,

###  2.2 Maker Protocol

The Maker Protocol operates as a decentralized finance (DeFi) platform on the
Ethereum blockchain, facilitating the creation of Dai, a stablecoin pegged to
the US dollar. As per [4], Users engage with the protocol by depositing
cryptocurrency assets, such as Ethereum or other tokens, into smart contracts
as collateral. Based on the value of this collateral, users can then generate
Dai, typically up to a predetermined percentage of the collateral’s worth. To
maintain the stability and security of the system, the protocol enforces
various risk parameters, including collateralization ratios and debt ceilings,
which dictate the relationship between collateral and the amount of Dai that
can be generated. Users pay stability fees on the Dai they generate, serving
as interest rates that contribute to the protocol’s stability. Governance of
the Maker Protocol is decentralized, with MKR token holders participating in
decision-making through a voting mechanism. These holders vote on proposals to
adjust risk parameters and other protocol settings, ensuring the protocol
remains responsive to market conditions and emerging risks. Additionally, the
protocol includes mechanisms for liquidating collateral if its value falls
below a certain threshold, helping to mitigate systemic risk and maintain the
stability of the Dai ecosystem. Overall, the Maker Protocol offers users a
decentralized and trustless means of generating a stable cryptocurrency,
providing access to the benefits of DeFi while minimizing counterparty risk.

##  3 Model

###  3.1 Mathematical Exposition

As per Koller and Milch [3], to define a Multi-Agent Influence Diagram (MAID),
we start with a collection of agents. We represent them as
$\textbf{A}=\\{A_{i}\\}$ for $i\in N$. These agents interact within the Maker
Protocol, which is represented by a set of chance variables denoted as $\chi$,
and a set of decision variables $D_{A_{i}}$ specific to each agent $A_{i}\in
A$.
Chance variables represent uncertain events or outcomes, similar to nodes in
Bayesian networks[8], while decision variables are the choices that each agent
$A_{i}$ can make, depicted as rectangular nodes in the diagram. We use $D$ to
denote $\cup_{A_{i}\in A}D_{A_{i}}$ The agents’ preferences and objectives are
captured using utility variables, denoted as $U_{A_{i}}$ for each agent
$A_{i}\in A$, where each agent has a set of utility variables. Similar to the
decision variables, we use $U$ to denote $\cup_{A_{i}\in A}U_{A_{i}}$. These
utility variables quantify the agent’s satisfaction or payoff based on the
outcomes of the decision and chance variables. In the Maker Protocol context,
chance variables represent factors like market conditions and collateral
fluctuations, while decision variables denote actions taken by users and
governance entities.

Mathematically, a MAID is represented as a directed acyclic graph (which is
used to denote causal relationships, see [12]) where each variable corresponds
to a node, and the relationships between variables are depicted through
directed edges. For each chance variable $X_{i}\in\chi$, the MAID specifies a
conditional probability distribution (CPD) given the instantiations of its
parent variables $Pa(N)\subset\chi\cup D$ for each node $N$ in the diagram,
which is $P(N|Pa(N))$. Similarly, for each utility variable $U_{A_{i}}$, the
MAID specifies a conditional probability distribution, ensuring that the
utility value is deterministic based on the values of its parents. The total
utility derived by an agent from a particular instantiation of the environment
is computed as the sum of the utility values of all relevant utility
variables.

Agents determine their actions at decision nodes based on the variables they
observe prior to making a decision, typically represented by the parent
variables of the decision node. The decision-making process is defined by a
set of decision rules, which specify the agent’s strategy or behavior at each
decision node. In the context of the Maker Protocol, users and governance
entities make decisions based on observed market conditions, collateral
fluctuations, and similarly relevant factors to optimize their utility. By
utilizing MAIDs, stakeholders can model and analyze the complex interactions
and decision-making processes within the Maker Protocol ecosystem to enhance
stability, security, and efficiency as we will demonstrate in the next
section. The next portion describes the definitions and theorems, from Koller
and Milch’s paper [3], which will be useful in our analysis. Readers are
encouraged to refer to the original paper to know more about the ideas in
detail.

###### Definition 1

A decision rule for a decision variable $D$ is a function that maps each
instantiation $pa$ of parents $\mathcal{P}(D)$ to a probability distribution
over the domain $\text{dom}(D)$. An assignment of decision rules to every
decision $D_{A_{i}}$ for a particular agent in $A$ is called a strategy.

We define the payoffs at the leaves by computing a distribution over the
utility nodes, given an instantiation of $\theta$. For a leaf $\ell$, the
payoff for agent $A$ is:

$u_{A}(\ell)=\mathbb{E}_{\theta}[u_{A}\,|\,\text{inst}_{\ell}]$

###### Theorem 3.1

Let $D$ be a decision node in a MAID $K$, $\beta$ be a decision rule for $D$,
and $C$ be a strategy profile such that $\beta$ is optimal for $C$. $\beta$
strategically relies on a decision node $D^{\prime}$ in $K$ if there is
another strategy profile $C^{\prime}$ such that $C^{\prime}$ differs from $C$
only at $D^{\prime}$, but $\beta$ is not optimal for $C^{\prime}$, and neither
is any decision rule $\beta^{\prime}$ that agrees with $\beta$ on all parent
instantiations $pa\in\text{dom}(Pa(D))$, where $P_{M[\sigma]}(pa)>0$.

###### Definition 2

A node $D^{\prime}$ is $s$-reachable from a node $D$ in a MAID $K$ if there is
some utility node $U_{e}$ such that if a new parent $D^{\prime}$ were added to
$D$, there would be an active path in $K$ from $D$ to $U_{e}$ given
$\phi(D)\subseteq j\lor\forall r$, where a path is active in a MAID if it is
active in the same graph, viewed as a Bayesian Network.

###### Definition 3

The relevance graph for a MAID $K$ is a directed graph whose nodes are the
decision nodes of $K$, and which contains an edge ${}_{\to}D^{\prime}$ if and
only if $D^{\prime}$ is $s$-reachable from $D$.

###### Definition 4

If $K$ is a MAID and $C$ is a strategy profile for $K$, then the joint
distribution for $K$ induced by $C$, denoted $Q_{K}^{C}$, is the joint
distribution over $\mathcal{X}$ defined by the Bayes network where:

  * •

The set of variables is $\mathcal{X}$.

  * •

For each chance variable $X_{i}\in\mathcal{X}$, for each instantiation
$\mathbf{pa}$ of parents of $X_{i}$, denoted $Pa(X_{i})$, there is an edge
$X_{i}\rightarrow X_{i}$ iff $X_{i}\in\mathbf{pa}$.

  * •

For each decision variable $D_{i}\in\mathcal{D}$, the CPD for $D_{i}$ is
$P(D_{i}|\mathbf{pa})$.

  * •

For each agent $A_{i}$, the CPD for each decision variable $D_{i}$ is
specified by the corresponding decision rule in $C$.

We can now formulate an equation representing the expected utility that agent
$A_{i}$ anticipates in a MAID $K$ when the agents adhere to a specific
strategy profile $C$. Let $U_{A_{i}}^{C}$ denote the utility, and suppose
$U_{A_{i}}^{C}=\sum_{j}u_{A_{i}}^{j}$. Then:

$E[U_{A_{i}}^{C}]=\sum_{\mathbf{v}\in\text{dom}(\mathbf{V})}u_{A_{i}}(\mathbf{v})\prod_{D\in\mathcal{D}}P(D|\mathbf{pa})\quad\text{where}\quad\text{dom}(\mathbf{V})=\text{joint
domain of}\ \mathbf{V}.$ (1)

Since the expectation of a sum of random variables equals the sum of the
expectations of the individual random variables, we can express this equation
as:

$E[U_{A_{i}}^{C}]=\sum_{\mathbf{v}\in\text{dom}(\mathbf{V})}\sum_{j}u_{A_{i}}^{j}P(D|\mathbf{pa})\quad\text{where}\quad\text{dom}(\mathbf{V})=\text{joint
domain of}\ \mathbf{V}.$ (2)

After defining the expected utility, we can now elucidate what it signifies
for an agent to optimize their decision at one or more of their decision
nodes, relative to a given set of decision rules for the other variables.

###### Definition 5

Let $H$ be a subset of $\mathcal{D}$, and let $C$ be a strategy profile. We
define $C_{\text{opt}}$ as optimal for the strategy profile $C$ if, in the
induced MAID $K_{(LCoI_{\text{opt}}M)}$, where the only remaining decisions
are those in $H$, the strategy $C_{\text{opt}}$ is optimal. Formally, for all
strategies $C_{\text{alt}}$:

$\displaystyle EU_{A_{i}}^{C_{\text{opt}}}$ $\displaystyle\geq
EU_{A_{i}}^{C_{\text{alt}}}$ $\displaystyle EU_{A_{i}}^{C}$ $\displaystyle\geq
EU_{A_{i}}^{C_{\text{opt}}}$

Note that, in this definition, the decision rules assigned to the variables in
$H$ by $C$ are not relevant.

In the context of game theory, a strategy profile is deemed to represent
rational behavior if it constitutes a Nash equilibrium [7]. Essentially, a
strategy profile is a Nash equilibrium if no agent has an incentive to deviate
from the strategy prescribed for them by the profile, provided that the other
agents adhere to their specified strategies.

###### Definition 6

A strategy profile $C$ is a Nash equilibrium for a MAID $K$ if, for all agents
$A_{i}$, $C_{\text{opt}}$ is optimal for the strategy profile.

###  3.2 Model Set Up

We analyse the coordination game played between the key stakeholders within
the Maker Protocol : the governance DAO and users of the protocol. The
dynamics of the game are as follows :

  1. 1.

Governance entity (DAO), represented as a set of agents
$\textbf{G}=\\{G_{1},G_{2}\cdots G_{i}\\}$, make decisions regarding protocol
parameters, such as interest rates, collateral types, and governance policies.

  2. 2.

Users of the protocol, represented as another set of agent
$\textbf{Up}=\\{Up_{1},Up_{2}\cdots Up_{i}\\}$, make decisions regarding
paying back or borrowing more Dai by adding collateral.

Referring [4], in the game between governance and users within the Maker
Protocol, users interact with the protocol by borrowing Dai against collateral
and governance entities, including voters and decision-makers, shape the
protocol’s direction by proposing and voting on changes to parameters and
policies. Users are incentivized to maintain adequate collateralization levels
and repay debt obligations while governance entities seek to make decisions
that enhance protocol stability, security, and efficiency while considering
the preferences and welfare of the broader community.

###  3.3 Multi Agent Influence Diagram Construction

As per [13], the key risk parameters for Maker Vaults are:

  * •

Debt Ceiling: The Debt Ceiling represents the upper limit on the aggregate
debt that can be generated through a singular collateral type within the Maker
Protocol. Maker Governance allocates a specific Debt Ceiling to each
collateral type, thereby facilitating adequate diversification within the
collateral portfolio of the Maker Protocol. Upon reaching its designated Debt
Ceiling, further creation of debt becomes unattainable unless existing users
repay some or all of their outstanding Vault debt.

  * •

Stability Fee: The Stability Fee constitutes an annualized interest rate (APY)
assessed on the total amount of Dai generated against a Vault’s collateral.
This fee is exclusively denominated in Dai.

  * •

Liquidation Ratio: The Liquidation Ratio signifies the minimum collateral-to-
debt ratio required within the Maker Protocol. A lower Liquidation Ratio
implies an anticipation of relatively stable collateral prices, while a higher
ratio indicates an expectation of greater price volatility. Mathematically,
the Liquidation Ratio can be expressed as the ratio of the value of collateral
to the total outstanding debt.

  * •

Liquidation Penalty: The Liquidation Penalty represents an additional fee
imposed on the total outstanding Dai generated by a Vault upon liquidation.
This penalty serves as an incentive for Vault owners to maintain adequate
levels of collateral to mitigate the risk of liquidation. It is typically
expressed as a percentage of the total debt outstanding.

  * •

Collateral Auction Duration: The Collateral Auction Duration specifies the
maximum period allocated for the auctioning of collateral associated with
Maker Vaults. While debt and surplus auction durations are system-wide
parameters, the collateral auction duration is specific to individual Vaults.

  * •

Auction Bid Duration: The Auction Bid Duration denotes the duration for which
an individual bid remains valid before expiring and subsequently closing the
auction. This parameter is crucial in determining the efficiency and speed of
the auction process within the Maker Protocol.

  * •

Auction Step Size: The Auction Step Size serves as a risk parameter aimed at
incentivizing early participation in auctions and preventing potential abuse
by discouraging minimal bid increments. It establishes the minimum bid
increment required for successive bids in an auction, promoting a fair and
efficient auction mechanism.

####  3.3.1 Smart contract Modules:

The Maker Protocol relies on various smart contracts to automate its core
functionalities. These modules interact with each other and with external
actors to maintain system stability and facilitate user interactions. As per
[16] :

  * •

Core Module: The Core Module is crucial to the system as it contains the
entire state of the Maker Protocol and controls the central mechanisms of the
system while it is in the expected normal state of operation.

  * •

Collateral Module: The collateral module is deployed for every new `ilk`
(collateral type) added to `Vat`. It contains all the adapters and auction
contracts for one specific collateral type.

  * •

The System Stabilizer Module: It’s purpose is to correct the system when the
value of the collateral backing Dai drops below the liquidation level
(determined by governance) when the stability of the system is at risk. The
system stabilizer module creates incentives for Auction Keepers (external
actors) to step in and drive the system back to a safe state (system balance)
by participating in both debt and surplus auctions and, in turn, earn profits
by doing so.

  * •

Oracle Module: An oracle module is deployed for each collateral type, feeding
it the price data for a corresponding collateral type to the `Vat`. The Oracle
Module introduces the whitelisting of addresses, which allows them to
broadcast price updates off-chain, which are then fed into a `median` before
being pulled into the `OSM`. The `Spot`’ter will then proceed to read from the
`OSM` and will act as the liaison between the `oracles` and `dss`.

  * •

MKR Module: The MKR Module contains the MKR token, which is a deployed DS
Token contract. It is an ERC20 token that provides a standard ERC20 token
interface. It also contains logic for burning and authorized minting of MKR.

  * •

Governance Module: The Governance Module contains the contracts that
facilitate MKR voting, proposal execution, and voting security of the Maker
Protocol.The Governance Module has 3 core components consisting of the
`Chief`, `Pause` and `Spell` contracts.

  * •

Rate Module: The Maker Protocol’s Rate Accumulation Mechanism

  * •

Proxy Module: The Proxy module was created in order to make it more convenient
for users/developers to interact with the Maker Protocol. It contains contract
interfaces, proxies, and aliases to functions necessary for both DSR and Vault
management and Maker governance.

  * •

Maker Protocol Emergency Shutdown: Shutdown is a process that can be used as a
last resort to directly enforce the Target Price to holders of Dai and Vaults,
and protect the Maker Protocol against attacks on its infrastructure. Shutdown
stops and gracefully settles the Maker Protocol while ensuring that all users,
both Dai holders and Vault holders, receive the net value of assets they are
entitled to.

The below figure shows the MAID for this game :

Multi Agent Influence Diagram for GovernanceDAO and User game

Deeper Influence Diagram to show interdependencies between parameters on the
smart contract level

The MAID model captures the dependencies and influences between the decisions
of the governance entity and the users of the Maker Protocol. Nodes in the
MAID represent variables such as decisions, uncertainties, utilities, and
influences, while directed edges indicate causal relationships or dependencies
between them.
The game unfolds over discrete time steps, with each agent making sequential
decisions based on their objectives, beliefs, and the actions of the other
agent. The decisions of one agent influence the payoffs and strategies
available to the other agent, creating a dynamic interplay of incentives and
behaviors.
A brief overview of the connections is as follows :

Sustainability

The sustainability of the Maker Protocol hinges on prudent management of risk
parameters such as the debt ceiling, liquidation ratio, and stability fee.
While higher debt ceilings can potentially increase revenue through stability
fees, they also expose the protocol to greater risk if not managed carefully.
Similarly, a lower liquidation ratio allows for more borrowing and higher fee
generation but escalates the risk of undercollateralization and losses during
market downturns. The stability fee, crucial for revenue generation, must
strike a delicate balance to avoid discouraging borrowing and reducing demand
for DAI. The Governance Module assumes a pivotal role in aligning decisions
regarding risk parameters and protocol upgrades with sustainability goals.

Profitability

Profitability within the Maker Protocol ecosystem is intricately linked to the
effectiveness of risk parameters and smart contract modules. The stability
fee, determined by governance, directly impacts the profitability of Vault
owners by influencing the cost of borrowing Dai against collateral.
Additionally, the efficacy of the System Stabilizer Module in managing
liquidations and surplus auctions affects the profitability of participants,
including Keepers engaging in these auctions to earn profits. Higher
liquidation penalties incentivize users to maintain adequate
collateralization, thereby reducing the need for liquidations and potential
losses for the protocol.

Risk Parameters

Risk parameters, governed by the Governance Module, play a pivotal role in
capital efficiency, risk mitigation, and profitability within the Maker
Protocol ecosystem. Parameters such as the liquidation ratio, debt ceiling,
liquidity penalty, and stability fee directly influence user debt, security
risk, demand for DAI, and collateral dynamics. These parameters must be
meticulously adjusted to ensure high capital efficiency, low risk exposure,
and sustainable profitability. For instance, the debt ceiling sets limits on
debt generation against specific collateral types to prevent over-leveraging
and maintain system stability. Similarly, the liquidation ratio and penalty
incentivize users to uphold sufficient collateralization levels, mitigating
the risk of liquidation events.

Debt

The debt within the Maker Protocol represents borrowed Dai against provided
collateral. Smart contract modules like the Core Module and Rate Module are
instrumental in managing user debt by maintaining accurate records and
dynamically adjusting stability fees based on market conditions. Risk
parameters such as the debt ceiling, liquidation ratio, and penalty further
influence debt dynamics by setting limits and incentivizing adequate
collateralization.

Demand for DAI

The demand for DAI is intricately linked to borrowing conditions within the
Maker Protocol, influenced primarily by the stability fee. Lower stability
fees make borrowing DAI more attractive, potentially increasing demand,
although this must be balanced with the need for protocol revenue.
Additionally, risk parameters such as the liquidation ratio and debt ceiling
play crucial roles in managing risk and ensuring the stability of DAI, thus
impacting demand. The efficiency of collateral auctions facilitated by modules
like the System Stabilizer Module also influences confidence in the protocol
and, consequently, demand for DAI.

Security Risks

Security risks within the Maker Protocol stem from vulnerabilities in smart
contracts, market manipulation, or unexpected events like oracle failures. The
Oracle Module is vital for mitigating security risks by providing accurate
price feeds, while the Maker Protocol Emergency Shutdown mechanism serves as a
safeguard against critical failures. Adjusting parameters like the liquidation
ratio and debt ceiling is essential for managing security risks associated
with insolvency or exposure to volatile assets.

Market Conditions

Market conditions significantly impact the stability and performance of the
Maker Protocol. Risk parameters such as the liquidation ratio and penalty are
designed to account for market fluctuations and maintain system health during
adverse conditions. The Oracle Module provides real-time price data, enabling
swift reactions to changing market conditions, while dynamically adjusting
debt ceilings based on market conditions helps manage risk and maintain
stability.

Collateral Dynamics

The Collateral Module manages collateral types and associated parameters
within the Maker Protocol. Adjusting risk parameters like the debt ceiling and
liquidation ratio influences collateral dynamics by affecting the selection
and utilization of collateral assets. Furthermore, the efficiency of
collateral auctions, facilitated by modules like the System Stabilizer Module,
impacts collateral dynamics by determining the ease of collateral liquidation
in case of undercollateralization.

##  4 Conclusion and Future Work

In this paper, we have successfully quantified the different inter
dependencies between the different parameters in the Maker protocol and
created a MAID like structure to analyse the games in the protocol. In future
iterations, we will analyse the game using the mathematical principles laid
down by Koller and Milch and provide a comprehensive view of equilibria in the
protocol in different conditions. In subsequent papers, we will also show that
MAIDs can be used as a way to assess the incentive security of a defi protocol
such as Maker. Using the library developed by Google Deepmind (see [14]), we
will develop our own code with a thorough analysis of collateral dynamics (see
[15] ), quantify expected values and payoff functions using ideas from Section
3, and we will demonstrate the equilbrium conditions of the protocol in real
time so as to motivate a formal verification procedure of game theoretic
interactions on Maker protocol.

## References

  * [1] Zetzsche, D. A., Arner, D. W., & Buckley, R. P. (2020). Decentralized finance (defi). Journal of Financial Regulation, 6, 172-203.
  * [2] Schueffel, P. (2021). DeFi: Decentralized Finance-An Introduction and Overview. Journal of Innovation Management, 9(3), I-XI.
  * [3] Koller, D., & Milch, B. (2003). Multi-agent influence diagrams for representing and solving games. Games and economic behavior, 45(1), 181-221.
  * [4] Maker Foundation. (2014). The Maker Whitepaper. https://makerdao.com/da/whitepaper
  * [5] Fiedler, I., & Ante, L. (2023). Stablecoins. In The Emerald Handbook on Cryptoassets: Investment Opportunities and Challenges (pp. 93-105). Emerald Publishing Limited.
  * [6] Kreps, D. M. (1989). Nash equilibrium. In Game Theory (pp. 167-177). London: Palgrave Macmillan UK.
  * [7] Nash, J. (1951). Non-Cooperative Games. Annals of Mathematics, 54(2), 286–295. https://doi.org/10.2307/1969529
  * [8] Pearl, J. (1988). Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan kaufmann.
  * [9] Howard, R. A., & Matheson, J. E. (2005). Influence diagrams. Decision Analysis, 2(3), 127-143.
  * [10] Everitt, T., Carey, R., Langlois, E. D., Ortega, P. A., & Legg, S. (2021, May). Agent incentives: A causal perspective. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 35, No. 13, pp. 11487-11495).
  * [11] Everitt, T., Ortega, P. A., Barnes, E., & Legg, S. (2019). Understanding agent incentives using causal influence diagrams. Part I: Single action settings. arXiv preprint arXiv:1902.09980.
  * [12] Williams, T. C., Bach, C. C., Matthiesen, N. B., Henriksen, T. B., & Gagliardi, L. (2018). Directed acyclic graphs: a tool for causal studies in paediatrics. Pediatric research, 84(4), 487-493.
  * [13] Maker Foundation. (2014). Risk Parameters Controlled by Maker Governance. https://makerdao.com/da/whitepaper/#risk-parameters-controlled-by-maker-governance
  * [14] Fox, J., Everitt, T., Carey, R., Langlois, E., Abate, A., & Wooldridge, M. (2021). PyCID: a Python library for causal influence diagrams. In Scientific Computing with Python Conference (SciPy).
  * [15] Kozhan, R., & Viswanath-Natraj, G. (2021). Decentralized stablecoins and collateral risk. WBS Finance Group Research Paper.
  * [16] Maker Foundation. (2014).$\textit{Maker Smart Contract Module}.\texttt{https://docs.makerdao.com/}$