# Rewriting game theory as a foundation for sate-based models of gene regulation

Chafika Chettaoui, Franck Delaplace, Pierre Lescanne, Mun'delanji Vestergaard, René Vestergaard

<figure><img src="image_1.png" /></figure>

## To cite this version:

Chafika Chettaoui, Franck Delaplace, Pierre Lescanne, Mun'delanji Vestergaard, René Vestergaard. Rewriting game theory as a foundation for sate-based models of gene regulation. International Conference on Computational Methods in Systems Biology (CMSB 2006), Oct 2006, Trento, Italy. pp.257-270, 10.1007/11885191_18. http-00339800

HAL Id: hal-00339800

https://hal.science/hal-00339800v1

Submitted on 18 Aug 2022

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_2.png" /></figure>
# Rewriting Game Theory as a Foundation for State-Based Models of Gene Regulation

Chafika Chettaoui<fnref n="1" />, Franck Delaplace<fnref n="1" />,*, Pierre Lescanne<fnref n="2" />, Mun'delanji Vestergaard<fnref n="3" />, and René Vestergaard<fnref n="3" />,**

**Abstract.** We present a game-theoretic foundation for gene regulatory analysis based on the recent formalism of *rewriting game theory*. Rewriting game theory is discrete and comes with a graph-based framework for understanding compromises and interactions between players and for computing Nash equilibria. The formalism explicitly represents the dynamics of its Nash equilibria and, therefore, is a suitable foundation for the study of steady states in discrete modelling. We apply the formalism to the discrete analysis of gene regulatory networks introduced by R. Thomas and S. Kauffman. Specifically, we show that their models are specific instances of a *C/P game* deduced from the *K* parameter.

## 1 Introduction

Gene regulation concerns the mutual inhibition and activation among genes and the wider impact this has on cells and on whole organisms through the resulting protein production or lack thereof, aka *gene expression*. In particular, the regulation of genes may involve complex regulatory processes such as auto-regulation and feedback loops, possibly via complex pathways. Studying regulation benefits from using formal tools to give well-founded explanations of their complexities.

<figure><img src="image_3.png" /></figure>

Substantial work has focused on stochastic techniques and differential equations (over time) [4]. In this article, we focus on the two best known state-based (aka *logical* and *multivalued*) models, due to Kauffman [5, 6] and Thomas [18, 19]. The two models are discrete and aim at providing qualitative information about the dynamic aspects of gene regulation [4]. They are underpinned by the definition of a state graph that is intended to represent possible gene-state changes [1, 19]. Informally, analyzing the dynamics of the state graph is based on the identification of paths having specific topological properties. Notions in dynamical systems are translated into topological properties on the graph. A trajectory

<footnote n="1">¹ IBISC - FRE 2873 CNRS, Evry, France</footnote>

<footnote n="2">² LIP - UMR 5668, Ecole Normale Supérieure, Lyon</footnote>

<footnote n="3">³ JAIST, Nomi, Ishikawa, Japan</footnote>

<footnote>* Corresponding author: <delapla@lami.univ-evry.fr>.</footnote>

<footnote>** Corresponding author: <vester@jaist.ac.jp>.</footnote>
is a pathway, a steady state is a sink (i.e., a vertex with no output edge), and periodicity is described by a cycle. Terminal cycles and sinks are remarkable topological features because they both embody attractors. Special attention is paid to attractors because they represent robust and steady characteristic modes of a dynamic system. Hence they can be considered as functional features (capabilities) of the system at a more integrated level because, over time, evolution will make the system reach one of them as influenced by external conditions.

Cycles, sinks and more generally attractors, can be computationally unified in a homogeneous notion of terminal strongly connected components (TSCC). Basically, it represents a sub graph where any two vertices are connected together by a cycle and from where there is no escaping path. The topology of the attractor is often interpreted as a characteristic feature of the regulatory dynamics. For instance, cycles and sinks correspond respectively to homeostasis [2] and multi-stationarity. However to embrace the complexity of these dynamics, one must understand and be able to work with them as mathematical objects in a general and ideally algebraic manner to smoothly and coherently address all the known and desirable features of gene regulation and to accommodate future discoveries. In other words, a foundation is called for that, on the one hand, is flexible and general and, on the other hand, employs a conceptual and technical framework that sheds direct light on the issues at hand, i.e., that can bridge the gap between topological features in a state graph and regulatory effects of inter-dependent but autonomous genes.

The cornerstone of our contribution is to show that the steady states of gene regulatory networks, as they are commonly understood, are a recently established kind of Nash-style equilibria, called *change-of-mind equilibria* [14]. The game-theoretic perspective we provide is technically and conceptually beneficial because non-cooperative game theory is the embodiment of the compete-and-coexist reality of genes and because it allows us to leverage the independently developed theory of dynamic equilibria in rewriting game theory. In particular, we show that Kauffman's and Thomas' models can be defined as specific instances of a particular game-skeleton. Technically, this recasts steady states (attractors) and gene regulation to the fixed-point construction underlying our discrete Nash equilibria. In particular, we show that steady states are the least non-empty fixed points (in a lattice of fixed points) of the *update* functions already considered by Kauffman and Thomas.

In Section 2, we briefly account for (rewriting) game theory, computation of discrete Nash equilibria, and the very general game formalism involved, called conversion/preference (C/P) games. In section 3, we review the discrete models for gene regulation introduced by Kauffman and Thomas. In section 4, we show that the two models can be viewed as instances of a C/P game.

In [15], we apply rewriting game theory to protein signalling in mitogen-activated protein kinase (MAPK) cascades, which govern biological responses such as cell growth. The aim there is more practical than in this article and
<figure><img src="image_4.png" /><figcaption>Fig. 1. Example of sequential(extensive form) and strategic game(normal form)</figcaption></figure>

involves establishing an analytic model for protein signalling in the first place and to develop tool support for it.

## 2 Rewriting Game Theory

In this section, we first provide a gentle reminder of the relevant ideas in game theory (Section 2.1) and then introduce the principles of a framework for discrete game theory (Section 2.2), before going into more technical details in the remainder of the section. The framework generalises the notions of strategic games and Nash equilibria without involving probability theory and continuous notions. Good accounts of traditional game theory are [9, 13].

### 2.1 Non-Cooperative Game Theory

Non-cooperative game theory is game theory based around the notion of Nash equilibrium. Nash equilibria are defined over strategies that account for the intended behaviour of all agents/players in a game. We say that an agent is happy if he cannot change his contribution to a (combined) strategy and generate a better overall outcome for himself. A (combined) strategy is a Nash equilibrium if all agents are happy with it. Game theory involves a wide spectrum of games and theories. However two kinds of games are usually considered for modelling : sequential games and strategic games. An example using a sequential game in extensive form is in Figure 1, left. An example of a strategic game in normal-form is in the figure, right.

A play of the game on the left is a path from the root to a leaf, where the first (second) number indicates the payoff to agent $a_1$ ($a_2$). A strategy over the game, by contrast, is a situation where a choice has been made in all internal nodes, not just in the nodes on a considered path. While it might look like the strategy of $a_1$ going right and $a_2$ going left is good, it is not a Nash equilibrium because $a_2$ can go right, for a better payoff. At that point, also $a_1$ can benefit from changing his choice and, in fact, the only Nash equilibrium in the game is $a_1$ ($a_2$) going left (right). Nash equilibria can be guaranteed to exist for all sequential games, a result known as Kuhn's Theorem [7, 20].

In strategic games, players act simultaneously. In contrast to sequential games, Nash equilibria do not always exist in a pure form in strategic games. An example is above on the right. In the example, there are two players: vertical, who chooses a row and gets the first payoff, and horizontal, who chooses a column and
gets the second payoff. As can be seen, in no outcome are both players happy, i.e., one player always can and wants to move away. Instead, Nash's Theorem says that a probabilistic combination of strategies exists, where the agents are happy with their expected payoffs [10, 12]. In the example, the only probabilistic Nash equilibrium arises if both agents choose between their two options with equal probability for expected payoffs of a half to each. Despite their clear mathematical interest, probabilistic strategies are often difficult to understand in a modeling context. In the strategic-form game above, for example, expected payoffs of a half to each agent result if just one agent chooses with equal probability between his two options. But, such situations do not amount to Nash equilibria. Addressing the hows and whys of this in general quickly turns in to pure probability theory, with justifications that need not necessarily be meaningful in the application area.

## 2.2 Conversion/Preference Games

Conversion/preference (C/P) games have been designed as an abstraction over strategic-form games and as a game formalism that introduces as few concepts as possible. This aim leads us to distinguish two relations on strategies, *Conversion* and *Preference*. The key concept of C/P games is the *synopsis*, which abstracts the notion of (combined) strategies. Roughly speaking, conversion says how an agent can move from a synopsis to another; in other words, it says which changes are allowed on synopses for a given agent. An agent makes choices among synopses according to which he prefers over others. It should be noted that conversions and preferences depend on agents. In what follows, conversion is denoted $\succ$ and preference is denoted $\prec$. Clearly strategic-form games are instances of C/P games, conversions are one dimension move (for instance along a line or a column), while preferences are given by comparisons over payoffs: a synopsis is preferred by an agent over another if his payoff is larger in the former.

**Definition 1 (C/P Games [14])** G<sup>cp</sup> are 4-tuples $\langle A, S, (\succ_a)_{a \in A}, (\prec_a)_{a \in A} \rangle$:

- A is a non-empty set of agents.

- S is a non-empty set of synopses (read: outcomes of the game).

- For a $\in A$, $\succ_a$ is a binary relation over S, associating two synopses if agent a can convert the first to the second.

- For a $\in A$, $\prec_a$ is a binary relation over S, associating two synopses if agent a prefers the second to the first.

The idea of the definition is to make explicit the parts of strategic-form games that are relevant to the definition of Nash equilibria and to dispense with any other structural constraints, such as the uniform restriction that ‘vertical’ can only move up and down. To illustrate, we note that the example we considered earlier amounts to the C/P game in Figure 2.
<figure><img src="image_5.png" /><figcaption>Fig. 2. Conversions and Preferences example</figcaption></figure>

$$ \frac{\begin{array}{c} s >_a s' \\ s \to_a s' \end{array}}{s \to_a s'} $$

<caption>Fig. 3. The (free) change-of-mind relation for agent a in G<sup>cp</sup></caption>

## 2.3 Abstract Nash Equilibrium

The following definition says that a synopsis *s*, i.e., our abstraction over (combined) strategies, is an abstract Nash equilibrium if and only if all agents are happy, meaning that whenever an agent can convert *s* to *s'* then it is not the case that he prefers *s'* to *s*. The notion of abstract Nash equilibrium specialises to Nash's concrete form in the presence of the discussed structural constraints on strategic-form games.

**Definition 2 (Abstract Nash Equilibrium [14])** *Given G<sup>cp</sup>.*

$$ \mathrm{Eq}^{\mathrm{aN}}(s) \triangleq \forall a \in \mathcal{A}, s' \in \mathcal{S} \cdot s >_a s' \Rightarrow \neg(s \triangleleft_a s') $$

We suppress the word abstract from the definition for the reason discussed above: in strategic-form games, the notions coincide. [14]. Said differently, Definition 2 is merely a more general (and simpler) way of writing what Nash wrote [10, 12]. Technically, the form of our definition is intended to facilitate the following definition, thus giving rise to the name *rewriting game theory*.

**Definition 3 ([14])** *Given G<sup>cp</sup>, the change-of-mind relation, →<sub>a</sub>, for agent a is given in Figure 3. Let → = ⋃<sub>a∈A</sub> →<sub>a</sub>.*

In other words, a Nash equilibrium is a synopsis for which there is no outgoing change-of-mind step, i.e., an →-irreducible (aka a →-normal form).

**Proposition 4 ([14])** *Eq<sup>aN</sup>(s) ⇔ s ∈ IrR<sub>−</sub>.*

The benefits of the changed perspective on game theory are partly conceptual, in the first instance for people that like rewriting, but they are also technical in that Proposition 4 highlights the positive notion, i.e., change-of-mind, that is behind Nash's original definition and through which we get easy access to a range of formal(ist) tools, not least of which is definition and proof by induction.
## 2.4 A Graph-Theoretic Construction

Returning to our rewriting/graph-theoretic view on game theory, we note that for arbitrary finite graphs only cycles can prevent the existence of terminal nodes. We show in this section how that simple observation suffices for underpinning a discrete version of Nash's Theorem for arbitrary finite C/P games. The relevant graph-theoretic notion we need for capturing all cycles is *strongly connected components*.

- A *graph* is a binary relation on a carrier set, called vertices: $\to \subseteq \mathcal{V} \times \mathcal{V}$.

- The *reflexive, transitive (or pre-order) closure*, $\to^*$, of a graph, $\to$, is

$$ \frac{v_1 \to v_2}{v_1 \to^* v_2} \qquad \frac{v_1 \to^* v \quad v \to^* v_2}{v \to^* v} $$

- The strongly connected component (SCC) of a vertex, $v$, in a graph is

$$ \lfloor v \rfloor \triangleq \{v' \mid v \to^* v' \land v' \to^* v\} $$

(The relation “is in the $\lfloor - \rfloor$-class of” is an equivalence relation.)

- The set of SCCs of a graph is

$$ \lfloor \mathcal{V} \rfloor \triangleq \{ \lfloor v \rfloor \mid v \in \mathcal{V} \} $$

- The *shrunken graph* of $\to \subseteq \mathcal{V} \times \mathcal{V}$ is $\frown \subseteq \lfloor \mathcal{V} \rfloor \times \lfloor \mathcal{V} \rfloor$, defined by

$$ V_a \frown V_b \triangleq V_a \neq V_b \land (\exists v_a \in V_a, v_b \in V_b \cdot v_a \to v_b) $$

The following result says that a Nash equilibrium exists in the “shrunken” game of any finite original C/P game.

**Theorem 5 ([14]**)

- $\langle \mathcal{A}, \lfloor S \rfloor, (\frown_a)_{a \in \mathcal{A}}, (\frown_a)_{a \in \mathcal{A}} \rangle$ has a Nash equilibrium,

- all of which can be found in linear time in the size of $S$ and $\to$.

Nash's Theorem says that probabilistic Nash equilibria exist for all finite strategic-form games. By comparison, the result above says that “shrunken” Nash equilibria always exist for finite members of the much larger class of C/P games. We clarify what the $\lfloor - \rfloor$-qualifier means next.

## 2.5 Change-of-Mind Equilibria

The topic of this section is to directly characterise the Nash equilibria prescribed by Theorem 5. Naively speaking, our notion of *change-of-mind* equilibrium is simply the graph underlying the considered compromises between synopses.

**Definition 6 (Change-of-Mind Equilibrium)** Write $\xrightarrow{S} for \to \cap (S \times S)$.
$$ \begin{array}{c} 0, 1 \leftarrow 1, 0 \\ \Downarrow \\ 1, 0 \rightarrow 0, 1 \end{array} $$

<caption>**Fig. 4.** Change-of-mind equilibrium for our running strategic-form example</caption>

$$ \begin{array}{l} \text{— Eq}^{\text{com}}(s) \triangleq \forall s' \in \mathcal{S}. (s \rightarrow *s' \Rightarrow s' \in \lfloor s \rfloor) \\ \text{— Eq}^{\text{com}}(\lfloor s \rfloor) \triangleq \text{Eq}^{\text{com}}(s) \end{array} $$

We refer to the former notion as change-of-mind equilibrium points and the latter simply as change-of-mind equilibria. The concept of change-of-mind equilibrium is well-defined because “$_{\in}$ ⌊s⌋” is an equivalence relation.

**Lemma 7** Consider $\langle \mathcal{A}, \mathcal{S}, (\succ_a)_{a \in \mathcal{A}}, (\prec_a)_{a \in \mathcal{A}} \rangle$, $\langle \mathcal{A}, \lfloor \mathcal{S} \rfloor, (\prec_a)_{a \in \mathcal{A}}, (\succ_a)_{a \in \mathcal{A}} \rangle$.

$$ \text{Eq}^{\text{com}}(\xrightarrow{\lfloor s \rfloor}) \Leftrightarrow \text{Eq}^{\text{aN}}(\lfloor s \rfloor) $$

The lemma implies that the Nash equilibria prescribed by Theorem 5 have the property that no agent can escape from them. Agents are allowed to move within the equilibria but they will have to stay within the set perimeter. We will return to the issue of size of the perimeter in Section 5. For now, we note that our running example, see Figure 1, left, and Figure 2, has the change-of-mind equilibrium in Figure 4. We note that both the probabilistic Nash and the change-of-mind equilibria of the example involve all four outcomes. The probabilistic version prescribes an exact *expected* payoff, while the discrete change-of-mind version makes the dynamics behind the equilibrium clear. The two notions may differ quite substantially in general but neither is uniformly smaller, has higher (implied) payoff values, or is better in any similar sense.

## 3 Basic State-Based Analysis of Gene Regulation

Kauffman's and Thomas' models differ on a number of minor and on one major issue, relative to our presentation. Among the minor ones, we count Kauffman's assumption that i) genes are boolean, i.e., that they can be in exactly two states: active (expressing protein) or inactive and that ii) when one gene regulates another it is always either repressing or activating it. Assumption ii) is reflected in the signs (polarities) annotated to the regulatory-network example at the beginning of Section 1. The major difference between the two approaches concerns the way states are updated. In Thomas' model only one gene is updated at each step (asynchronous update) while in Kauffman's all genes are updated (synchronous update), albeit possibly reflexively. We return to this issue in Section 3.2.
<figure><img src="image_6.png" /><figcaption>Fig. 6. Kauffman (left) and Thomas (right) analysis of two-variable phage λ</figcaption></figure>

synchronous move is made towards the combined comfort state, while allowing for at most one phase transition for each gene. If a gene is not regulated upon, i.e., if no comfort state is specified, it retains its state. Reflexive state-space transitions are not considered. The details for the example in Figure 5 are in Figure 6, left.

In Thomas' case, Figure 6 right, each gene is prompted as before but moves are made *asynchronously*, i.e., each state may have several moves out of it, one for each gene being considered. In the figure, we indicate *cI*-updates with dashed arrows and *cro*-updates with dotted arrows, although the two are not distinguished in the actual analysis.

## 3.3 Steady States

In the two state graphs above, $\langle cI_1, cro_0 \rangle$ clearly plays a special role: it is a static steady state, i.e., it is the only state that does not have arrows out of it. From this, we can seemingly, i.e., we would like to, conclude that if the two genes end up in that configuration, they stay that way. The relevance of state-based analysis comes from the fact that the state in question has been observed to be (*self*)-sustainable: it is phage $\lambda$'s *lysogenic* state that “involves integration of the phage DNA into the bacterial chromosome [of its host] where it is passively replicated at each cell division — just as though it were a legitimate part of the bacterial genome” [21].

Similarly, there is an inescapable cycle, i.e., a dynamic steady state, involving $\langle cI_0, cro_1 \rangle$ and $\langle cI_0, cro_2 \rangle$ in both graphs. The implied regulatory flip-flopping between $\langle cI_0, cro_1 \rangle$ and $\langle cI_0, cro_2 \rangle$ is, in fact, biologically characteristic of phage $\lambda$'s *lytic* state in which it actively uses its host's transcription mechanism to replicate itself [21].<fnref n="4" />

In our formalism, and despite their obvious topological differences, both the static and the dynamic steady states described are simply change-of-mind-equilibria, which means that they can be uniformly accommodated as far as our general theory goes. More, the biological justification for why the states are spe-

<footnote n="4">⁴ The cycle between $\langle cI_0, cro_0 \rangle$ and $\langle cI_1, cro_1 \rangle$ is a known false positive of Kauffman's model.</footnote>
cial, i.e., that they are inescapable, is the exact justification for why they
are both change-of-mind equilibria.

4 C/P games-based Modeling of Gene Regulatory Networks

Our modeling of Kauffman/Thomas-style gene regulation via C/P games will
have the update graphs exemplified in Figure 6 as change-of-mind relations.
Several ways of specifying the C/P-game 4-tuple, ⟨A, S, (▷_a )_a∈A , (◁_a )_a∈A ⟩, will
lead to the desired result. The approach we take interprets the distinction be-
tween conversion and preference as chemical reality vs observation of the same.
Specifically, we distinguish chemical reactions that genes and proteins are in-
volved in and how closely we choose/are able to observe changes.

Given a regulatory network, ⟨G, ⋇, K<sub>G</sub>⟩, with associated gene states, (S<sub>g</sub>)<sub>g∈G</sub>,
we take the gene state space, S<sub>G</sub> ≜ ⊗<sub>g∈G</sub> S<sub>g</sub>, as our set of synopses, S. Reflect-
ing the (perceived) universality of the considered chemical situation, we insist
that the conversion relations of all agents, whatever we specify them to be, are
the same. By default, we allow all state changes and leave it to the specific ap-
plications to put in place any necessary ad hoc restrictions.<sup>5</sup> Following Thomas,
however, we are particularly interested in the at-most-one-phase-transition-at-
a-time restriction.

**Definition 9** For linear order $g_0 < \dots < g_n$, let $g_i \ominus g_j = i - j$, and let $s \succcurlyeq^\pm s'$ $\triangleq \ \forall g \in G. \ |\pi_g(s) \ominus \pi_g(s')| \le 1$

A C/P game whose conversion fulfills the previous definition is called 1-restrained.
Similarly straightforwardly, our preference relation is dictated by the comfort
functions, K<sub>g</sub>, of a regulation network.

**Definition 10** We say that *s'* is a comfort approximation for *g* in *s* if

$$
\text{K-Approx}_g(s, s') \triangleq (\pi_g(s) \le \pi_g(s') \le K_g(s)) \lor (\pi_g(s) \ge \pi_g(s') \ge K_g(s))
$$

**Definition 11** Given $\langle G, \frown, K_G \rangle$ and for any $s, s' \in S_G$ and $g \in G$, let

$$
- s \prec_G s' \triangleq \forall g . K-\text{Approx}_g(s, s')
$$

$$
- s \prec_g s' \triangleq \text{K-Approx}_g(s, s') \wedge (\forall g' . g' \neq g \Rightarrow \pi_{g'}(s) = \pi_{g'}(s'))
$$

be the synchronous respectively g-asynchronous preference relations.

With this, we see that Kauffman-style regulation analysis is a 1-player reg-
ulation game, while Thomas-style regulation analysis is a multi-player game,
played by the considered genes. In Kauffman-style the 1-player is the whole set
of genes G, whereas in Thomas-style, players are the elements of G.

<footnote n="5">⁵ For example, for eliminating “false cycles” arising due to vastly differing kinetics for two or more reactions, e.g., in the standard 4-variable model of phage λ [17].</footnote>
**Theorem 12 (Regulation Games & Kauffman/Thomas)** Given $\langle G, \frown, K_G \rangle$,

- The Kauffman update function, cf. Figure 6, left, is the change-of-mind relation, $\to$, of $\langle G, S_G, \stackrel{\pm 1}{\frown}, \langle_G \rangle$, the 1-restrained synchronous regulation game, and the steady states are the change-of-mind equilibria, Eq$^{com}$.

- The Thomas update function, cf. Figure 6, right, is the change-of-mind relation, $\to$, of $\langle G, S_G, (\stackrel{\pm 1}{\frown})_{g \in G}, (\langle_G \rangle)_{g \in G} \rangle$, the 1-restrained asynchronous regulation game, and the steady states are the change-of-mind equilibria, Eq$^{com}$.

Moreover, and in both cases, the static (dynamic) steady states are the change-of-mind equilibria that are also (not) Nash equilibria, Eq$^{aN}$.

**Proof** The statements about the update functions follow by construction. The statements about static vs dynamic equilibria are questions of terminology, according to Proposition 4: “singleton change-of-mind equilibria are Nash equilibria”. That steady states and change-of-mind equilibria coincide follow from Lemma 7 and (the proof of) Theorem 5, further to the characterisation of steady states as terminal strongly connected components in [3]. □

In Figure 7 we depict the full regulation game of 2-variable $\lambda$-phage.

## 5 A Fixed-Point Construction

The original Thomas characterisation of steady states is in terms of fixed points of the considered update function [17]. As noted earlier, that function is a specific instance of the following function.

**Definition 13 (Upgrade)** $\mathcal{U}(S) \triangleq \bigcup_{s \in S} \{s' \in S \mid s \to s'\}$

We first note that $\mathcal{U}$ always has fixed points.

**Lemma 14 ([14)** The fixed points of $\mathcal{U}$ is a non-empty, complete lattice.

**Proof** $\mathcal{U}$ is monotonic on the complete lattice $\mathcal{P}(S)$ because $\to^*$ is reflexive, and we are done by Tarski's Fixed-Point Theorem [16]. □

Example fixed-points are the empty set, $\emptyset$, and the whole set, $S$. The interesting point is that the change-of-mind equilibria are exactly the least non-empty (pre-)fixed-points of the upgrade function.

**Lemma 15 ([14)** Consider some $\langle A, S, (\stackrel{\frown}{a})_{a \in A}, (\langle_a \rangle)_{a \in A} \rangle$.

$$ \begin{array}{c} \text{Eq}^{\text{com}}(\stackrel{\lfloor s \rfloor}{\to}) \\ \Downarrow \\ \mathcal{U}(\lfloor s \rfloor) = \lfloor s \rfloor \wedge (\forall S' \cdot \emptyset \subsetneq S' \subsetneq \lfloor s \rfloor) \Rightarrow \mathcal{U}(S') \not\subseteq S') \end{array} $$

The characterisations of steady states in [17] and in [3] therefore coincide, with the proviso that the fixed points are least non-empty, and both are instances of our more general theory of dynamic equilibria in rewriting game theory.
$$
\begin{align*}
K_{cl}(\langle-, \text{cro}_0\rangle) &= cI_1 & K_{cro}(\langle cI_0, \text{cro}_0\rangle) &= \text{cro}_2 \\
K_{cl}(\langle-, \text{cro}_1\rangle) &= cI_0 & K_{cro}(\langle cI_0, \text{cro}_1\rangle) &= \text{cro}_2 \\
K_{cl}(\langle-, \text{cro}_2\rangle) &= cI_0 & K_{cro}(\langle cI_0, \text{cro}_2\rangle) &= \text{cro}_0 \\
& & K_{cro}(\langle cI_1, \rangle) &= \text{cro}_0
\end{align*}
$$

<figure><img src="image_7.png" /><figcaption>Fig. 7. λ-phage C/P game.</figcaption></figure>

- The upper left hand-side diagram describes the convertibility relation.

- The upper right hand-side diagram describes the resulting C/P game.

- The lower left hand-side diagram is the preference relation of cI.

- The lower right hand-side diagram is the preference relation of cro.

# 6 Conclusion

In this article we introduce a game-theory based framework to model gene regulatory networks. We show that a discrete Nash equilibrium can be viewed as a generalization of steady states in discrete models (TSCC). More, we show that Thomas' and Kaufman's models are particular instances of a more general game construction (that conceivably could have other interesting instances). Game theory aims at describing equilibria coming from interactions between agents. One way of viewing Nash-style equilibria is that they are logical expressions capturing the functional units at the level of abstraction above the one at which the considered game exists. In this paper, for example, we have shown that change-of-mind equilibria can be used to predict what gene expression will take place. In other words, we have moved from the chemical abstraction level of protein binding and catalysis captured in expression games, up to the biochemical abstraction level of, e.g., phage λ's lysogenic and lytic states. At the other end of the spectrum, Maynard Smith has shown that a game-theoretic analysis of the
ecological concept of fitness leads to the formal substantiation of Darwinian evo-
lution, i.e., “survival of the fittest”. Our future work concerns similar treatments
of the various abstraction levels in between, namely chemical, biochemical, cellu-
lar, multi-cellular and environmental level. Game theory may provide a unified
framework to encompass theory occuring at different levels and to provide a
suitable framework to deal with interactions between levels in order to get an
integrative theory of biology.

References

1. G. Bernot, Cassez, J.P. G. Comet, F. Delaplace, C. Mller, O. Roux, and Roux O.(H.). Semantics of biological regulatory networks. In *Workshop on Concurrent Models in Molecular Biology (BioConcur 2003)*, 2003.

2. Walter Bradford Cannon. *The Wisdom of the Body*. W. W. Norton, New York, 1932.

3. Claudine Chaouiya, Elizabeth Remy, and Denis Thieffry. Petri net modelling of biological regulatory networks. *Proceedings of CMSB-3*, 2005.

4. Hidde de Jong. Modeling and simulation of genetic regulatory systems: A literature review. *Journal of Computational Biology*, 9(1):67–103, 2002.

5. Stuart A. Kauffman. Metabolic stability and epigenisis in randomly constructed genetic nets. *Journal of Theoretical Biology*, 22:437–467, 1969.

6. Stuart A. Kauffman. *The Origins of Order: Self-Organization and Selection in Evolution*. Oxford University Press, 1993.

7. Harold W. Kuhn. Extensive games and the problem of information. *Contributions to the Theory of Games II*, 1953. Reprinted in [8].

8. Harold W. Kuhn, editor. *Classics in Game Theory*. Princeton Uni. Press, 1997.

9. R. B. Myerson. *Game Theory: Analysis of Conflict*. Harvard University Press, 1991.

10. John F. Nash. Equilibrium points in n-person games. *Proceedings of the National Academy of Sciences*, 36, 1950. Reprinted in [8].

11. John F. Nash. *Non-Cooperative Games*. PhD thesis, Princeton University, 1950.

12. John F. Nash. Non-cooperative games. *Annals of Mathematics*, 54, 1951. Reprinted in [8]; published version of [11].

13. M. J. Osborne. *An introduction to game theory*. Oxford University Press, 2003.

14. Stéphane Le Roux, Pierre Lescanne, and René Vestergaard. Rewriting game theory and Nash's construction, 2006. Available at http://www.jaist.ac.jp/~vester/.

15. J. Senachak, M. Vestergaard, and R. Vestergaard. Rewriting game theory applied to protein signalling in MAPK cascades. Submitted to CMSB 2006.

16. Alfred Tarski. A lattice-theoretical fixpoint theorem and its applications. *Pacific Journal of Mathematics*, 5:285–309, 1955.

17. R. Thomas and M. Kaufman. Multistationarity, the basis of cell differentiation and memory II: Logical analysis of regulatory networks in terms of feedback circuits. *Chaos*, 11(1):180–195, 2001.

18. René Thomas. Boolean formalization of genetic control circuits. *Journal of Theoretical Biology*, 42(3):563–585, 1973.

19. René Thomas, Denis Thieffry, and Marcelle Kaufman. Dynamical behaviour of biological regulatory networks I: Biological role of feedback loops and practical use of the concept of the loop-characteristic state. *Bulletin of Mathematical Biology*, 57:247–276, 1995.
20. René Vestergaard. A constructive approach to sequential Nash equilibria. *Information Processing Letters*, 97:46–51, 2006.

21. James D. Watson, Tania A. Baker, Stephen P. Bell, Alexander Gann, Michael Levine, and Richard Losick. *Molecular Biology of the Gene*, 5th edition. The Benjamin/Cummings Publishing Company, 2004.