text:
\section{Introduction}
In a binary ($0-1$) coordination game over a graph, where initially all agents are in the Nash equilibrium $0$, what is the minimum number of agents that if forced to $1$ will push the system to converge to the Nash equilibrium of all $1$'s under a best response dynamics? This paper is devoted to the analysis of this problem and to the design of an algorithm for an efficient solution.

The problem considered can be framed in the more general setting of studying minimal interventions strategies needed to make a multi-agent system governed by agents' myopic utility maximization, to drive from a Nash equilibrium to a desired another one. In game theory, typically, interventions have been modeled as perturbations of the utility functions (e.g. taxes and prices in economic models or tolls in transportation systems). Here we instead take a different viewpoint: that of individuating a subset of nodes (hopefully small) that if suitably controlled will lead the entire system to the desired configuration. The minimum cardinality of this set can also be interpreted as a measure of resilience of the system: the larger it is, the more difficult is for an external shock to destabilize it.

The problem of determining the best set of nodes to exert the most effective control in a networked system has recently appeared in other contexts: for instance in \cite{Yildiz-2013} and \cite{Vassio-2014} authors study the problem of the optimal position of stubborn influencers in linear opinion dynamics.

Binary coordination games have received a great attention in the recent years as one of the basic models for games with strategic complementarities \cite{gamesonnetworks}. Its variegate applications include modeling of social and economic behaviors like adopt a new technology, participate in an event, provide a public good effort.

This game is analyzed in detail in \cite{morris} where the key concept of cohesiveness of a set of players is introduced and then used in characterizing all NE's.
Moreover, the question if an initial seed of influenced players (that maintain action  $1$ in all circumstances) is capable of propagating to the all network is addressed in the same paper and an equivalent characterization of  this spreading phenomenon is also expressed in terms of cohesiveness. This contagion phenomenon is exactly what we want to analyze: subset of nodes from which propagation is successful will be called sufficient control sets and our goal is to find such sets of minimum possible cardinality.

The condition proposed in \cite{morris} is computationally quite demanding and can not be used to directly solve our optimization problem. Indeed, even to determine if a single set  is a sufficient control set,  it requires a number of check growing exponentially in the cardinality of the complement of such set.

The complementary problem of understanding, given an integer $k$, what is the maximum possible spreading of the state $1$, starting from an initial seed of $k$ influenced players, was studied in a seminal paper by \cite{Kempe}. While their problem and ours are related, they are independent, in the sense that solving one does not provide a solution of the other. Another point worth stressing is that, in their setting, \cite{Kempe} consider agents equipped with random independent activation thresholds and take as functional to be optimized the average size of the maximum spreading. They prove that such functional is sub-modular and then they design a greedy algorithm for obtaining suboptimal solutions. The randomness that they introduce is actually crucial in their approach, as the functional considered would not be sub-modular for deterministic choices of thresholds.

In this paper we consider a scenario when all agents have a fixed threshold $1/2$, thus not covered in \cite{Kempe}, and we design an iterative search randomized algorithm with provable properties of convergence towards sufficient control sets of minimum cardinality. The core of the algorithm is a time-reversible Markov chains over the family of all sufficient control sets that starts with the full set, moves through all of them in an ergodic way, and concentrates its mass on those of minimum cardinality .

We conclude this introduction with a brief outline of the paper. In the final part of this section we report some basic notation used throughout the paper. Section \ref{sec:model} is dedicated to the formal introduction of the problem. The main technical parts are Sections \ref{sec:monotone} and \ref{sec:MC}. In Section \ref{sec:monotone}, we introduce the important notion of monotone crusade (appeared for other purposes in \cite{Drakopoulos.ea:2015,Drakopoulos.ea:2016}) and we give an equivalent (but more operative) characterization of sufficient control sets. In Section  \ref{sec:MC} we introduce a family of reversible Markov chains whose invariant probability is proven to concentrate on the optimal sufficient control sets. Section \ref{sec:simulations} describes the algorithm, based on the Markov chains introduced in the previous section, and presents some simulation results. Finally, Section \ref{sec:conclusions} ends the paper.

\subsection{Notation} Vectors are indicated in bold-face letters ${\bf x},\, {\bf y}, {\bf z}$. For $\mathbf{x},\, \mathbf{y}$ are two vectors of the same dimension, the notation $\mathbf{x} \le \mathbf{y}$ indicates that $\mathbf{x}$ is lower or equal \emph{component-wise} than $\mathbf{y}$.
We define as usual the binary vectors $\delta_i$: $(\delta_i)_i=1$ and $(\delta_i)_j=0$ for every $j\neq i$.
If $\mathcal S\subseteq\{1,\dots , n\}$, we put $\mathbbm{1}_{\mathcal S}=\sum_{i\in\mathcal S}\delta_i$.
Every ${\bf x}\in \{0,1\}^n$ can be written as ${\bf x}=\mathbbm{1}_S$ for some $S\subseteq \{1,\dots , n\}$.  We call such a subset $S$ the \emph{support} of ${\bf x}$ and we denote it $S_{\bf x}$.
We use the notation $\mathbb{0}$ and $\mathbbm{1}$ to denote, respectively, the vector of all $0$'s and the vector of all $1$'s of any possible dimension.

{
\section{Controlled majority dynamics}\label{sec:model}
We consider a set of players $\mathcal V=\{1,\dots , n\}$ connected by a simple undirected graph $\mathcal G=(\mathcal V, \mathcal E)$ (e.g. $\mathcal E\subseteq\mathcal V\times\mathcal V$ is such that $(i,i)\not\in\mathcal E$ for any $i$ and $(i,j)\in\mathcal E$ iff $(j,i)\in\mathcal E$). The binary set $\mathcal A=\{0,1\}$ is the set of possible actions for all players. We put $\mathcal X=\mathcal A^n$ and we define
the \emph{majority game} on $\mathcal G$ as the game where each player $i\in \mathcal V$ has utility $\lambda^{\text c}_i:\mathcal X\to\mathbb{R}$ given by
$$\lambda^{\text c}_i({\bf x})=|\{j\in N_i\,|\, x_j=x_i\}|$$
where $N_i$ is the neighborhood of agent $i$ in $\mathcal G$. In other words, $\lambda^{\text c}_i({\bf x})$ is
the number of neighbors of $i$ with which $i$ is in agreement.

As usual in game theory, given a configuration vector  $\mathbf{x}\in\mathcal X$ and a player $i$, we indicate with $\mathbf{x}_{-i}$ the configuration restricted to all players but $i$ and we consequently write
$\mathbf{x}=(x_i, \mathbf{x}_{-i})$.

Best response sets are defined by
$$
\mathcal B^{\text c}_i(\bf x)=\argmax\limits_{\alpha\in\mathcal A} \lambda^{\text c}_i(\alpha, \mathbf{x}_{-i})
$$

Using the notation
\begin{equation}\label{n01}n_{i,a}(\mathbf{x})=|\{j\in N_i\,|\, x_j=\alpha\}|,\quad \alpha=0,1\end{equation}
to indicate the number of neighbors of an agent  $i$ playing action $\alpha$  in the configuration $\mathbf{x}$,
Best response sets can be more explicitly described as
$$
\mathcal B^{\text c}_i(\bf x)=\left\{\begin{array}{ll} \{0\},\quad&{\rm if}\, n_{i,0}(\mathbf{x})>n_{i,1}(\mathbf{x})\\
\{0,1\},\quad&{\rm if}\, n_{i,0}(\mathbf{x})=n_{i,1}(\mathbf{x})\\
\{1\},\quad&{\rm if}\, n_{i,0}(\mathbf{x})<n_{i,1}(\mathbf{x})
\end{array}\right.$$

$\mathcal N$ denotes the set of Nash equilibria: $\mathcal N=\{{\bf x}\in\mathcal X\,|\, x_i\in \mathcal B^{\text c}_i(\mathbf{x})\,\forall i\in\mathcal V\}$. This set depends on the topology of the graph $\mathcal G$, note however that $\mathbb{0}$ and $\mathbbm{1}$ are always Nash equilibria.

It is well known that this game is potential with a potential $\Phi_{\text c}$ given by
\begin{equation} \Phi_{\text c}({\bf x})=|\{(i,j)\in\mathcal E,|\, x_j=x_i\}|\end{equation}
This simply says that, for every configuration $\mathbf{x}\in\mathcal X$, action $\alpha\in\mathcal A$ and player $i\in\mathcal V$, it holds
\begin{equation}\label{potential} \Phi_{\text c}(\alpha, {\bf x}_{-i})- \Phi_{\text c}({\bf x})=\lambda^{\text c}_i(\alpha, {\bf x}_{-i})-\lambda^{\text c}_i({\bf x})\end{equation}

The (asyncronous) best response dynamics is a discrete time Markov chain (MC) $X_t$ on the configuration space $\mathcal X$ where, at every time $t$, a player $i$ is chosen
uniformly at random and it modifies its action choosing an element uniformly at random within $\mathcal B^{\text c}_i((X_t)_{-i})$. Denote with $P_{\mathbf{x},\mathbf{y}}$ the transition matrix (on $\mathcal X\times\mathcal X$) of the MC $X_t$ and note that, given $\mathbf{x}\in\mathcal X$ and $\mathbf{y}=(\alpha, {\bf x}_{-i})$, it holds that
\begin{equation}\label{BRtransition} P_{\mathbf{x},\mathbf{y}}>0\;\Leftrightarrow\;  \Phi_{\text c}(\alpha, {\bf x}_{-i})\geq  \Phi_{\text c}({\bf x})\end{equation}
From the fact that the potential is not decreasing along the trajectories of $X_t$, it follows the classical result that, with probability $1$, $X_t$ converges in finite time to the set $\mathcal N$ of Nash equilibria.

The question we pose is: what is the minimal number of agents that if forced to $1$ will ensure almost surely that the best response dynamics reach the state $\mathbbm{1}$.

Given a subset $\mathcal C\subseteq \mathcal V$, we indicate with $X^{\mathcal C}_t$ the Markov chain where only the agents in $\mathcal V\setminus\mathcal C$ update their action according to the best response rule defined above, while agents in $\mathcal C$ maintain action $1$. This new MC  takes values in the subset of configurations
$$\mathcal X^{(\mathcal C)}=\{x\in\mathcal X\,|\, x_i=1\,\forall i\in\mathcal C\}$$

This restricted game remains potential. This new dynamics will converge too to its set of Nash equilibria $\mathcal N^{\mathcal C}=\mathcal N\cap\mathcal X^{(\mathcal C)}$.

The following definition is the main object of study of this paper.

\begin{definition}[Sufficient control set]\label{def:sufficient} $\mathcal C$ is a \emph{sufficient control set} if
\begin{equation}
\forall x_0\in\mathcal X^{(\mathcal C)}, \;
\P(\exists t\,:\, X^{\mathcal C}_t=\mathbbm{1},|\, X^{\mathcal C}_0=x_0)=1
\label{convergence}
\end{equation}
A sufficient control set is \emph{minimal} if none of its strict subsets is a sufficient control set. \\
A sufficient control set is \emph{optimal} if there exists no sufficient control set of strictly smaller cardinality.
\end{definition}

Our objective is to find optimal sufficient control sets.

To give a more intuitive idea of what control sets resemble, here are a few illustrative examples.

\begin{figure}[h]
\centering
\begin{tikzpicture}

\draw[thick] (-1.3,3) -- (0,4);
\draw[thick] (1.3,3) -- (0,4);
\draw[thick] (-1.8,2) -- (-1.3,3);
\draw[thick] (-1.8,1) -- (-1.8,2);
\draw[thick] (-.8,2) --(-1.3,3);
\draw[thick] (.8,2) --(1.3,3);
\draw[thick] (1.8,2) --(1.3,3);
\draw[thick] (0.3,1) --(.8,2);
\draw[thick] (1.3,1) --(.8,2);

\draw[fill,white] (0,4) circle (.13);
\draw[thick] (0,4) circle (.13);

\draw[fill,red] (-1.3,3) circle (.13);
\draw[thick] (-1.3,3) circle (.13);

\draw[fill, white] (1.3,3) circle (.13);
\draw[thick] (1.3,3) circle (.13);

\draw[fill,white] (-1.8,2) circle (.13);
\draw[thick] (-1.8,2) circle (.13);

\draw[fill,green] (-1.8,1) circle (.13);
\draw[thick] (-1.8,1) circle (.13);

\draw[fill,green] (-.8,2) circle (.13);
\draw[thick] (-.8,2) circle (.13);

\draw[fill,red] (.8,2) circle (.13);
\draw[thick] (.8,2) circle (.13);

\draw[fill,green] (1.8,2) circle (.13);
\draw[thick] (1.8,2) circle (.13);

\draw[fill,green] (0.3,1) circle (.13);
\draw[thick] (0.3,1) circle (.13);

\draw[fill,green] (1.3,1) circle (.13);
\draw[thick] (1.3,1) circle (.13);

\end{tikzpicture}
\caption{Example : on trees, the set of the leaves (in green) is always a valid control set.In red you can see another  valid control set, of size 2, minimal for this particular tree }
\end{figure}

\begin{figure}[h]
\centering
\begin{tikzpicture}
\foreach \i in {90,162,...,450}
{
	\draw (\i+144:1)--(\i:1) -- (\i+72:1);
}
\foreach \i in {90,162,...,450}
{
	\draw[white,fill] (\i:1) circle (.13);
	\draw[thick] (\i:1) circle (.13);

}
	\draw[red,fill] (162:1) circle (.13);
	\draw[thick] (162:1) circle (.13);

	\draw[red,fill] (18:1) circle (.13);
	\draw[thick] (18:1) circle (.13);

\end{tikzpicture}
\caption{An example of a clique, the sets of size $\left\lceil \frac{k}{2} \right\rceil-1$ are exactly the minimal control sets}
\end{figure}

\begin{figure}[h]
\centering
\begin{tikzpicture}
\begin{scope}{yshift=.86 cm}
	\draw[thick] (90:1)--(330:1)--(210:1)--(90:1);

\foreach \i in {330,90,210}
{
	\draw[white,fill] (\i:1) circle (.13);
	\draw[thick] (\i:1) circle (.13);
}
\draw[red,fill] (90:1) circle (.13);
\draw[thick] (90:1) circle (.13);
\end{scope}
\begin{scope}[xshift=2.5 cm, yshift=.31cm]

\foreach \i in {90,162,234,306,18}
{
	\draw[thick] (\i:1)--(\i+72:1);
}
\foreach \i in {90,162,234,306,18}
{
	\draw[white,fill] (\i:1) circle (.13);
	\draw[thick] (\i:1) circle (.13);
}
\draw[red,fill] (90:1) circle (.13);
\draw[thick] (90:1) circle (.13);

\end{scope}
\begin{scope}[xshift=5 cm, yshift=-.5 cm]
\draw (0,0)--(0,1)--(1,1)--(1,0)--(2,0)--(2,1);
\foreach \i in {0,1,2}
{
\foreach \j in {0,1}
{
	\draw[white,fill] (\i,\j) circle (.13);
	\draw[thick] (\i,\j) circle (.13);
}
}
\draw[red,fill] (1,1) circle (.13);
\draw[thick] (1,1) circle (.13);

\end{scope}

\end{tikzpicture}
\caption{If all node have degree at most  $2$, then choosing one node per connected component gives a control set}
\end{figure}

\section{Monotone crusades and valid control sets}\label{sec:monotone}

We now define the concept of monotone crusade,  that will play a crucial role in our theory.

They are particular sequences of states, starting from an initial state, end at $\mathbbm{1}$ and such that at every step, the number of their component with value $1$, without ever decreasing the potential. \\
More formally:
\begin{definition}[Adapted Monotone Crusade]\label{def:crusade} Let $\mathcal C\subseteq \mathcal V$.
A \emph{monotone crusade from $\mathcal C$} is a sequence of vectors ${\bf x}^k\in\mathcal X$, for $k=0,\dots , m$ such that
\begin{enumerate}
\item ${\mathbf x}^0=\mathbbm{1}_{\mathcal C}$, ${\mathbf x}^m=\mathbbm{1}$
\item for every $k=1,\dots ,m-1$ there exists $i_k\in\mathcal V\setminus\mathcal C$ such that ${\mathbf x}^{k+1} ={\mathbf x}^k+\delta_{i_k}$
\end{enumerate}
Moreover, if given a function $V:\mathcal X\to \mathbb{R}$, it holds
\begin{enumerate}
\item[3.] $V({\mathbf x}^{k+1})\geq V({\mathbf x}^k)$ for $k=0,\dots , n-1$
\end{enumerate}
then the sequence ${\bf x}^k$ is called a $V$-\emph{adapted} monotone crusade from $\mathcal C$.
\end{definition}

A few comments on the above definition:
\begin{remark} All nodes $i_1,\dots ,1_m$ appearing in (2) are necessarily distinct otherwise the condition ${\bf x}^k\in\{0,1\}^n$ for all $k$ would be violated. Indeed, we must have that $\mathcal V\setminus\mathcal C=\{i_1,\dots ,1_m\}$ and thus $m=|\mathcal V\setminus\mathcal C|$. This allows for a monotone crusade from $\mathcal C$ to be equivalently characterized by the sequence of nodes $(i_k)$, the induced order on the nodes or by the sequence of increasing support sets $(S_k)$ defined by $S_k=S_{{\bf x}^k}$, for $k=0,\dots , m$ having the property that $S_0=\mathcal C$ and $S_m=\mathcal V$.
\end{remark}
\begin{remark}
We can also define a decreasing version of the monotone crusade where ${\mathbf x}^0=\mathbbm{1}$, ${\mathbf x}^m=\mathbbm{1}_{\mathcal C}$ and where. for every $k$, ${\mathbf x}^{k+1} ={\mathbf x}^k-\delta_{i_k}$. This will be called a \emph{decreasing monotone crusade to $\mathcal C$} ($V$-\emph{adapted} if property 3. holds true).
\end{remark}

{
\begin{definition}[Valid control set]
A set $\mathcal{C}$ is $V$-\emph{valid} if there exists a $V$-adapted monotonous crusade from $\mathcal C$.
\end{definition}

Main goal of the rest of this section is to show that the class of $\Phi_c$-{valid} control sets (we recall that $\Phi_c$ is the potential of the majority game) coincides with the class of sufficient control sets defined in (Definition \ref{def:sufficient}).

The following property is instrumental to our results.}

\begin{lemma}[monotonicity of Coordination Game]\label{lemma:monotonicity}

For all $\mathbf{x}, \mathbf{y} \in\mathcal X$ and $  i \in \mathcal{V}$, the following conditions hold:
\begin{enumerate}
\item
if $\mathbf{x}\le \mathbf{y}$ and $\Phi_{\text c}(1,\mathbf{x}_{-i}) \ge \Phi_{\text c}(\mathbf{x})$ then $\Phi_{\text c}(1,\mathbf{y}_{-i}) \ge \Phi_{\text c}(\mathbf{y})$;
\item if $\mathbf{x}\ge \mathbf{y}$ and $\Phi_c(0,\mathbf{x}_{-i}) \ge \Phi_c(\mathbf{x})$ then $\Phi_c(0, \mathbf{y}_{-i}) \ge \Phi_c(\mathbf{y})$.
\end{enumerate}

\end{lemma}
\begin{proof} We only prove the first assertion, the second can be obtained by exchanging the role of $0$ and $1$.

If $y_i=1$, we have that $(1, \mathbf{y}_{-i})=\mathbf y$ and there is nothing to prove. If $x_i=1$, then the inequality $ \mathbf{x}\le \mathbf{y}$ ensure that $y_i=1$ and we are thus in the previous case.

We now consider the case when both $x_i$ and $y_i$ have value $0$.
Note that, if $\mathbf z$ is such that $z_i=0$, the variation of the potential when player $i$ changes its action from $0$ to $1$ can be expressed as
$$\Phi_c(1,\mathbf{z_{-i}}) - \Phi_c(\mathbf{z})= n_{i,1}(\mathbf{z}) -n_{i,0}(\mathbf{z})$$
where, we recall, $n_{i,1}(\mathbf{z})$ and $n_{i,0}(\mathbf{z})$ are the number of neighbors of $i$ whose action is, respectively, $1$ and $0$.
As $\mathbf{x} \le \mathbf{y}$, we have that $n_{i,0}(\mathbf{y}) \le n_{i,0}(\mathbf{x})$ and $n_{i,1}(\mathbf{y}) \ge n_{i,0}(\mathbf{x})$. Hence,
$$\begin{array}{l}\Phi_c(1, \mathbf{y}_{-i}) -\Phi_c(\mathbf{y})=n_{i,1}(\mathbf{y}) -n_{i,0}(\mathbf{y})\\\ge n_{i,1}(\mathbf{x}) -n_{i,0}(\mathbf{x})=\Phi_c(1, \mathbf{x}_{-i}) - \Phi_c(\mathbf{x})\end{array}$$
This yields the thesis.
\hfill \vrule height 7pt width 7pt depth 0pt\medskip
\end{proof}

\begin{proposition}[monotonicity for inclusion]\label{prop:superset}
\label{mono}
A superset of a $\Phi_c$-{valid} control set  is a $\Phi_c$-{valid} control set.
\end{proposition}
\begin{proof}
Assume that $\mathcal C$ is a $\Phi_c$-{valid} control set and let $\mathcal C'\supseteq \mathcal C$.
Let ${\bf x}^k$ be a $\Phi_c$-{adapted monotone crusade} from $\mathcal C$ with associated sequence of points $(i_k)$ for $k=1,\dots , m=n-|\mathcal C|$ such that
${\bf x}^{k+1}- {\bf x}^k=\delta_{i_k}$ for each $k$.
 Consider the subsequence of points $i_{k_1}, i_{k_2}, \dots , i_{k_{m'}}$ that are in $\mathcal V\setminus\mathcal C'$ and put $\mathbf{y}^h=\max\{\mathbbm{1}_{\mathcal C'}, \mathbf{x}^{k_h}\}$. By construction, we have that $\mathbf{y}^{h}\geq \mathbf{x}^{k_{h+1}-1}$ and thus, by Lemma \ref{lemma:monotonicity} and the fact that ${\bf x}^k$ is a  $\Phi_c$-{adapted monotone crusade} from $\mathcal C$, we have that $\Phi_c({\bf y}^{h})\leq \Phi_c({\bf y}^{h+1})$.

\hfill \vrule height 7pt width 7pt depth 0pt\medskip
\end{proof}
\begin{remark}[full set]
The full set is always a $\Phi_c$-{valid} control set
\end{remark}

The following clarifies the connection between valid control sets for the majority game and sufficient control sets introduced in the previous section.

\begin{theorem}\label{theo:valid-sufficient} A subset $\mathcal C\subseteq \mathcal V$ is a sufficient control set iff it is a $\Phi_c$-{valid} control set.
\end{theorem}

\begin{proof}
We first show that a sufficient control set is $\Phi_c$-{valid}. If $\mathcal C$ is a sufficient control set, there exists a sequence of vectors ${\bf y}^0,\dots , {\bf y}^T\in\mathcal X^{(\mathcal C)}$ such that ${\bf y}^0=\mathbbm{1}_{\mathcal C}$ and ${\bf y}^T = \mathbbm{1}$ that the best response dynamics follows with positive probability. This is equivalent to saying, using  the definition of best response dynamics (see in particular property (\ref{BRtransition})) , that
\begin{enumerate}
\item ${\bf y}^{k+1}- {\bf y}^k=\pm\delta_{i_k}$ for all $k=0,\dots , T-1$;
\item $\Phi_c({\bf y}^0)\leq\cdots \leq \Phi_c({\bf y}^T)$.
\end{enumerate}
For every $i\not\in\mathcal C$, define
$$k(i)=\min\{k=1,\dots , T\;|\; {\bf y}^{k}- {\bf y}^{k-1}=\delta_{i}\}$$
that is the first time when agent $i$ change its action to $1$ in the sequence ${\bf y}^t$. Order now the agents in $\mathcal V\setminus\mathcal C$ as $i_1,\dots , i_m$ in such a way that
$k_{i_1}<k_{i_2}<\cdots <k_{i_m}$. Consider the increasing monotone crusade ${\bf x}^h$ associated with the sequence of points $(i_h)$, namely,
$${\bf x}^h=\mathbbm{1}_{\mathcal C}+\sum_{h'\leq h}\delta_{i_h}$$
and notice that ${\bf x}^{h-1}\geq {\bf y}^{k(i_h)-1}$. Since $\Phi_c({\bf y}^{k(i_h)-1})\leq \Phi_c({\bf y}^{k(i_h)})$, it follows from Lemma \ref{lemma:monotonicity} that $\Phi_c({\bf x}^{h-1})\leq \Phi_c({\bf x}^{h})$. This tells us that
${\bf x}^h$ is a $\Phi_c$-{adapted monotone crusade} from $\mathcal C$ and, thus, $\mathcal C$ a $\Phi_c$-valid control set.

We now show that a $\Phi_c$-{valid} control set $\mathcal C$ is sufficient.\\
 We fix any initial condition ${\bf x}_0\in\mathcal X^{(\mathcal C)}$ and we put $\mathcal C'=S_{{\bf x}_0}$. $\mathcal C'$ is a superset of $\mathcal C$ and, on the basis of Proposition \ref{prop:superset}, $\mathcal C'$ is also a $\Phi_c$-{valid} control set. Let ${\bf x}^k$ be a corresponding $\Phi_c$-{adapted monotone crusade} from $\mathcal C'$. By the properties of adapted monotone crusades (properties 2. and 3. in Definition \ref{def:crusade}) and the characterization (\ref{BRtransition}) of the transition matrix of the best response dynamics $X_t$, starting from ${\bf x}_0$, the MC $X_t$ will follow such a sequence with positive probability. Thus, from any initial condition, $X_t$ will reach $\mathbbm{1}$ with positive probability. A standard result on MC then yields the thesis.

\hfill \vrule height 7pt width 7pt depth 0pt\medskip
\end{proof}

}

\section{Markov chains and backward search algorithms}\label{sec:MC}
The characterization of sufficient control sets through the concept of monotone crusades suggest the possibility that such sets can be found starting from the configuration $\mathbbm{1}$, iteratively replacing $1$'s with $0$'s in the attempt to follow backwards a monotone crusade. To this aim we now introduce a family of MC $Z_t^{\epsilon}$ on the binary space $\mathcal X$, parameterized by $\epsilon\in [0,1]$ that will be the core part of our algorithms.

Transitions of $Z_t^{\epsilon}$ are described as follows:\\ At every discrete time, a node uniformly at random $i$ is activated.
If its neighbors with current action $1$ ($n_{i,1}$) are strictly less than its neighbors with current action $0$ ($n_{i,0}$), it stays still. Otherwise,
 if its  action is $1$ it changes to $0$ with probability $1$, while if its action is $0$, it changes to $1$ with probability $\epsilon$.

The only non zero non trivial transition probabilities of $Z_t^{\epsilon}$ are the following. Given ${\bf x}\in\mathcal X$,
\begin{equation}\label{zepsilon}
\begin{array}{l}
x_i=1,\, n_{i,1}({\bf x})\geq n_{i,0}({\bf x})
\; \Rightarrow\;  P^{\epsilon}_{{\bf x},(0,{\bf x}_{-i})}=1/n
\\
x_i=0, \, n_{i,1}({\bf x})\geq n_{i,0}({\bf x})
\;\;\Rightarrow\;  P^{\epsilon}_{{\bf x},(1,{\bf x}_{-i})}=\epsilon/n
\end{array}
\end{equation}

In the case when $\epsilon=0$, only transitions from $1$ to $0$ are allowed. In this case, the MC has absorbing points. The relation of these points with sufficient control sets is studied in the next result.

We denote
$$
\begin{array}{lcl}
\mathcal Z & =& \{x\in\mathcal X\;|\; \P(\exists t_0\,:\, Z^0_{t_0}=x\;|\; Z_0^0=\mathbbm{1})>0\}\\[1pt]
\mathcal Z^{\infty} & = & \{x\in\mathcal X\;|\; \P(\exists t_0\,:\, Z^0_{t}=x \,\forall t\geq t_0\;|\; Z^0_0=\mathbbm{1})>0\}
\end{array}
$$
the sets of reachable and absorbing state of the chain $Z^{0}$.

\begin{theorem}\label{theo:Z} The following facts hold:
\begin{enumerate}
\item $\mathcal C$ is a sufficient control set iff $\mathbbm{1}_{\mathcal C}\in\mathcal Z$;
\item $\mathcal C$ is a minimal sufficient control set iff $\mathbbm{1}_{\mathcal C}\in\mathcal Z^{\infty}$;
\end{enumerate}
\end{theorem}
\begin{proof}

(1):
By definition, if $\mathbf{x}=\mathbbm{1}_{\mathcal C}\in \mathcal Z $, there exists a sequence of configuration vectors $y^k$, for $k=0,\dots , m$ such that
${\bf y}^0=\mathbbm{1}$ and ${\bf y}^m = \mathbbm{1}_{\mathcal C}$ satisfying the properties
\begin{enumerate}
\item ${\bf y}^{k}- {\bf y}^{k+1}=\delta_{i_k}$ for all $k=0,\dots , m-1$;
\item $\Phi_c({\bf y}^0)\geq\cdots \geq \Phi_c({\bf y}^T)$.
\end{enumerate}
Then $x^k=y^{m-k}$ is a $\Phi^c$-adapted monotone crusade from
$\mathcal C$ and this yields that $\mathcal C$ is a $\Phi_c$-valid control set and thus also a sufficient control set by virtue of Theorem \ref{theo:valid-sufficient}. Inverting this argument we prove the other implication.

(2): If $\mathcal C$ is a minimal sufficient control set, we know from (1) that $\mathbbm{1}_{\mathcal C}\in\mathcal Z$. If, by contradiction, $\mathbbm{1}_{\mathcal C}\not\in\mathcal Z^{\infty}$, then, from $\mathbf{x}=\mathbbm{1}_{\mathcal C}$, the MC $Z^0_t$ could reach, in one step, a different state $\mathbf{x}'=\mathbbm{1}_{\mathcal C'}$ with $\mathcal C'\subsetneq \mathcal C$. This contradicts minimality.

\end{proof}

Theorem \ref{theo:Z} allows to reformulate the optimization problem as follows:
\begin{equation}\label{optimization}\min\limits_{\mathbf{x}\in\mathcal Z}||\mathbf{x}||_1\end{equation}
where $||x||_1=\sum_ix_i$. Optimal sufficient control sets $\mathcal C$ are those for which $\mathbbm{1}_{\mathcal C}$ solves (\ref{optimization}).

The MC $Z^0_{t}$ is naturally related to the minority game whose definition we briefly recall thus: Given an undirected graph $\mathcal G=(\mathcal V, \mathcal E)$, we define the minority game on $\mathcal G$ as the binary game where each player $i\in\mathcal V$ has utility $\lambda^{\text a}_i:\mathcal X\to \mathbb{R}$ given by
$$\lambda^{\text a}_i({\bf x})=|\{j\in N_i\,|\, x_j\neq x_i\}|$$
that is simply the number of neighbors with which $i$ is in disagreement.
We denote by $\mathcal N_{\text a}$ the set of Nash equilibria of the minority game.
This game is potential with a potential $\Phi_{\text a}$ that is just the opposite than the potential of the majority game:
\begin{equation} \Phi_{\text a}({\bf x})=-\Phi_{\text c}(\mathbf{x})\end{equation}

The following property clarifies the relation of the minority game with our problem.
\begin{proposition}\label{prop:minority}
$\mathcal N_{\text a}\subseteq \mathcal Z$: Nash equilibria of the minority game are valid control sets.
\end{proposition}
\begin{proof}
Let $\mathbf{x}\in\mathcal N_a$ and let ${\bf y}^k$, for $k=1,\dots , m$ be any decreasing monotone crusade from $\mathbbm{1}$ to ${\bf x}$. By construction, ${\bf x}\le {\bf y}^k \le \mathbbm{1}$ for all $k$.
Consider the sequence of nodes $(i_k)$ such that ${\bf y}^{k-1}-{\bf y}^{k}=\delta_{i_k}$. We have that ${\bf  x}_{i_k}=0$ for every $k$.
 For all $k$, since ${\bf x}$ is a Nash equilibrium then $0$  is in $i_k$'s minority best response, thus $\Phi_a(\mathbf{x}) \ge \Phi_a(1,\mathbf{x}_{-i})$, or equivalently, $\Phi_c(\mathbf{x}) \le \Phi_c(1,\mathbf{x}_{-i})$. By Lemma \ref{lemma:monotonicity}, it follows that $\Phi_c(\mathbf{y}^{k}) \le \Phi_c(1,\mathbf{y}^{k}_{-i}) = \Phi_c(\mathbf{y}^{k-1})$. Therefore $\mathbf{x}^h=\mathbf{y}^{m-h}$ is a
$\Phi_c$-adapted monotone crusade from $\mathcal C=S_{\mathbf{x}}$. By virtue of Theorem \ref{theo:Z}, we have that $\mathbf{x}\in\mathcal Z$.

\end{proof}

We have the following simple but not obvious consequence.
\begin{corollary}[existence]
For any graph, there exist a sufficient control set whose size is less or equal to half the number of nodes.
\end{corollary}
\begin{proof}
The minority game, being potential, admits at least one Nash equilibrium $\mathbf{x}\in\mathcal N_a$. By symmetry  $\tilde{\mathbf{x}}=\mathbbm{1}-\mathbf{x}$ is also a Nash equilibrium. Proposition \ref{prop:minority} tells us that they are both sufficient control sets and one of the two has the required size property.
\end{proof}

Theorem \ref{theo:Z} and Proposition \ref{prop:minority} can not be improved further as shown by the following examples.

In the following  figures  \ref{fig:ex1} and \ref{fig:ex1b} we report two examples of optimal sufficient control sets that are not Nash equilibria of the minority game, while figure \ref{fig:ex2} is a counter example to the assumption that $\mathcal Z^\infty$ elements are minimal.

\begin{figure}[h]

\centering
\begin{tikzpicture}

\foreach \i in {0,120,240}
{
\draw (\i:0) -- (\i:1.5);
\draw[fill] (\i:1.5) circle(.13);
}
\draw[fill,white] (0,0) circle (.13);
\draw[fill,white] (0:1.5) circle(.13);
\draw[thick] (0,0) circle (.13);
\draw[thick] (0:1.5) circle(.13);

\draw[fill,red] (120:1.5) circle(.13);
\draw[fill,red] (240:1.5) circle(.13);
\draw[thick] (120:1.5) circle(.13);
\draw[thick] (240:1.5) circle(.13);

\end{tikzpicture}
\caption{This set is a minimal control set for the inclusion, yet the rightmost node is not in its best response, making it not a Nash }
\label{fig:ex1}
\end{figure}
\begin{figure}[h]
\centering

\begin{tikzpicture}
\draw (0,0) -- (6,0);

\foreach \i in {0,1.5,3,4.5}
{

\draw[fill,white] (\i,0) circle(.13);
\draw[thick] (\i,0) circle(.13);
}
\draw[fill, red] (6,0) circle(.13);
\draw[thick] (6,0) circle(.13);
\end{tikzpicture}\\

\caption{This set is optimal, but not Nash}
\label{fig:ex1b}
\end{figure}

\begin{figure}[h]

\centering
\begin{tikzpicture}{scale=.8}
\draw[thick] (-.75,1) -- (0,0)--(.75,1)--(1.5,0)--(.75,-1)--(0,0)--(-.75,-1);
\draw[thick](2.25,1)--(1.5,0)--(2.25,-1);

\draw[fill,red] (0,0) circle (.13);
\draw[thick] (0,0) circle (.13);

\draw[fill,white] (.75,1) circle (.13);
\draw[thick] (.75,1) circle (.13);

\draw[fill,white] (.75,-1) circle (.13);
\draw[thick] (.75,-1) circle (.13);

\draw[fill,red] (1.5,0) circle (.13);
\draw[thick] (1.5,0) circle (.13);

\draw[fill,white] (2.25,1) circle (.13);
\draw[thick] (2.25,1) circle (.13);

\draw[fill,white] (2.25,-1) circle (.13);
\draw[thick] (2.25,-1) circle (.13);

\draw[fill,white] (-.75,1) circle (.13);
\draw[thick] (-.75,1) circle (.13);

\draw[fill,white] (-.75,-1) circle (.13);
\draw[thick] (-.75,-1) circle (.13);

\end{tikzpicture}
\hspace{1cm}
\begin{tikzpicture}{scale=.8}

\draw[thick] (-.75,1) -- (0,0)--(.75,1)--(1.5,0)--(.75,-1)--(0,0)--(-.75,-1);
\draw[thick](2.25,1)--(1.5,0)--(2.25,-1);

\draw[fill,red] (0,0) circle (.13);
\draw[thick] (0,0) circle (.13);

\draw[fill,white] (.75,1) circle (.13);
\draw[thick] (.75,1) circle (.13);

\draw[fill,white] (.75,-1) circle (.13);
\draw[thick] (.75,-1) circle (.13);

\draw[fill,white] (1.5,0) circle (.13);
\draw[thick] (1.5,0) circle (.13);

\draw[fill,white] (2.25,1) circle (.13);
\draw[thick] (2.25,1) circle (.13);

\draw[fill,white] (2.25,-1) circle (.13);
\draw[thick] (2.25,-1) circle (.13);

\draw[fill,white] (-.75,1) circle (.13);
\draw[thick] (-.75,1) circle (.13);

\draw[fill,white] (-.75,-1) circle (.13);
\draw[thick] (-.75,-1) circle (.13);

\end{tikzpicture}
\caption{Two sufficient control sets on the same graph, both in $\mathcal Z^\infty$ only the one on the right is minimal.}
\label{fig:ex2}
\end{figure}

The above considerations imply that we can not directly use the dynamics $Z^0_t$ as our algorithm to find optimal sufficient control sets as its absorbing state $\mathcal Z^{\infty}$ are not even minimal in general. To overcome this difficulty we will instead use the MC $Z^{\epsilon}_t$ with $\epsilon >0$. As we will see, the presence of the transition in the opposite direction will permit the algorithm to make a full search on the set $\mathcal Z$ and not to remain stacked in non optimal configurations. This is guaranteed by the following final result.

\begin{theorem} Let $\epsilon >0$. The following facts hold:
\begin{enumerate}
\item $Z^{\epsilon}_t$ is ergodic inside the set of states $\mathcal Z$;
\item $Z^{\epsilon}_t$ is time-reversible and its unique invariant probability is given by $\mu^\epsilon ({\bf x}) := K\epsilon^{ ||\mathbf{x}||_1}$ where $K>0$ is the normalization constant;
\item For $\epsilon\to 0+$, $\mu^{\epsilon}$ converges in law to a probability measure $\mu$ concentrated on the subset $\argmin_{{\bf x}\in\mathcal Z}||\mathbf{x}||_1$.
\end{enumerate}
\end{theorem}
\begin{proof}
(1): We first show that $\mathcal Z$ is invariant by $Z^{\epsilon}_t$. First notice that the transitions that decrease the number of $0$'s in  $Z^{\epsilon}$ are also possible in $Z^0$. We thus only have to check the invariance for the transitions that increase the number of $1$'s in $Z^{\epsilon}$. Fix $\bf x\in \mathcal Z$, suppose that $x_i=0$ and put $\bf y= (1,{\bf x}_{-i})$. If $P^{\epsilon}_{{\bf x},\bf y}>0$, it follows from
(\ref{zepsilon}) that $n_{i,1}(\bf x)\geq n_{i,0}(\bf x)$. Since $\bf x\in \mathcal Z$, there exists a sequence of configuration vectors $\bf x^k$, for $k=0,\dots , m$ such that
${\bf x}^0=\mathbbm{1}$ and ${\bf x}^m = \mathbbm{1}_{\mathcal C}$ satisfying the properties
\begin{enumerate}
\item ${\bf x}^{k}- {\bf x}^{k+1}=\delta_{i_k}$ for all $k=0,\dots , m-1$;
\item $\Phi_c({\bf x}^0)\geq\cdots \geq \Phi_c({\bf x}^T)$.
\end{enumerate}
There must exist $\bar k$ such that $i_{\bar k}=i$. Consider now $\bf y^h$ defined by
$$\bf y^h=\left\{\begin{array}{ll} \bf x^h\quad &{\rm for}\, h\leq \bar k\\ \bf x^{h+1}+\delta_{i} \quad &{\rm for}\, h> \bar k\end{array}\right.$$
Notice that ${\bf y}^{T-1}=\bf y$
Using again Lemma \ref{lemma:monotonicity}, we have that $\Phi_c({\bf y}^0)\geq\cdots \geq \Phi_c({\bf y}^{T-1})$ so that $\bf y\in\mathcal Z$.

Ergodicity follows now from the observation that $Z^\epsilon$ verify the following property: for all transition with non zero probability, also the reversed transition has non zero probability. If $\bf x,\bf y\in\mathcal Z$, by definition of $\mathcal Z$, they are both reachable by $Z^0$ (and thus also by $Z^{\epsilon}$) starting from $\mathbbm{1}$. Therefore, with positive probability, under the MC $Z^{\epsilon}$ it is possible to move from $\bf x$ to $\mathbbm{1}$ and then to $\bf y$.

(2) We need to show that for all $\bf x,\, \bf y\in\mathcal Z$, it holds $$ \epsilon^{ ||\mathbf{x}||_1}P^{\epsilon}_{{\bf x},\bf y}=\epsilon^{ ||\mathbf{y}||_1}P^{\epsilon}_{{\bf y},\bf x}$$
Since the only non-trivial transitions of $Z^{\epsilon}$ are those in (\ref{zepsilon}), we can reduce to check it in the case when, for some $i\in\mathcal V$, $x_i=1$ and $\bf y=(0, \bf x_{-i})$. In this case we obtain
that $$ \epsilon^{ ||\mathbf{x}||_1}P^{\epsilon}_{{\bf x},\bf y}= \frac{\epsilon^{ ||\mathbf{x}\|_1}}{n},\quad \epsilon^{ ||\mathbf{y}||_1}P^{\epsilon}_{{\bf y},\bf x}= \epsilon^{ ||\mathbf{x}||_1-1}\frac{\epsilon}{n}=\frac{\epsilon^{ ||\mathbf{x}||_1}}{n}$$
This proves the claim.

(3) follows from the expression of $\mu^{\epsilon}$.

\hfill \vrule height 7pt width 7pt depth 0pt\medskip
\end{proof}

By virtue of the reformulation (\ref{optimization}), we have that, for small $\epsilon$ and sufficiently large $t$, the MC $Z^{\epsilon}_t$ will be 'most of the time' in configurations whose support are optimal sufficient control sets. Thsi observation is at the base of a practical algorithm described in the next section.

\section{Simulations}\label{sec:simulations}

We have implemented an iterative algorithm based on the MC $Z^{\epsilon}_t$. For the sake of increasing the speed to convergence, we actually considered a modification of $Z^{\epsilon}_t$ with all trivial self-loop transitions removed. This induces a little modification in the invariant probability, but do not affect the minimal set that is the return of the algorithm. Details will be reported elsewhere. The algorithm keeps track of the best configuration (the smallest $||x||_1$) found so far.

We have applied the algorithm to random realizations of Erd\"os-R\'eniy graphs with different number of nodes $n$ and probability $p=1/2$. For every value of $n$, we ran $500$ executions on $20$ randomly generated graphs. The algorithm is stopped after $100n$ iterations, using for epsilon the constant value {$\epsilon = 0.2 $.}

As a point of comparison, we computed a benchmark optimum consisting of the exhaustive optimum for small graphs, and a much longer execution on bigger graphs. Figure \ref{fig} shows the average values of the size of the sufficient control sets computed by the algorithm. We compare it with the benchmark optimum and also with the result obtained looking at the very last step of the algorithm. This plot shows a remarkable performance of the algorithm that in linear time gets quite close to the optimum.
It also shows that the MC, though fluctuating, as $\epsilon >0$, still remains close to the optimal configurations. The important question of how to tune the parameter $\epsilon$ for optimize performance has not been addressed here.

Finally notice how optimal sufficient control sets are scaling linearly with respect to the size of the graph. This suggests that Erd\"os-R\'eniy graphs are somewhat 'difficult' to control in this sense, in other terms they show resilience to this type of external actions.

\begin{figure}
\includegraphics[scale=.7]{nvarying.pdf}
\caption{In blue, the benchmark optimum. In purple, the minimal control set encountered in $100n$ steps. In green, the size of the control set at the end.
}
\label{fig}
\end{figure}

\section{Conclusion}\label{sec:conclusions}

We have formulated the problem of finding, in a network coordination game, the minimum number of players to be controlled in order to drive the system from one Nash equilibrium to another one. To the scope, we have designed a low complexity randomized algorithm and proven its convergence properties. We have finally carried on some numerical simulations corroborating the results.

Many challenging issues naturally pop up from our analysis and simulations. Erd\"os-R\'eniy graphs have exhibited optimal sufficient control sets growing linearly in the size of the graph. It would be of interest if this could be proven analytically, as well if this could be extended to other family of graphs, connecting such resilient phenomena to topological properties.

The problem studied in this paper is an instance of a more general problem of studying the effect of control actions in evolutionary game theory. Future research will be in this direction analyzing similar control problems for general games with strategic complementarity as well strategic substitutes.

redpajama_set_name: RedPajamaArXiv


text:
WWF War Zone
Monster Truck Madness 64
Great replacement part, fits perfect and corrected all...
Carby Ver 2 Gamecube Digital to HDMI Adapter Accessory
Home :: N64 Games, Parts & Service :: N64 Games
The NES Repair Shop sells almost every game made for the 64-bit Super Nintendo Entertainment System (commonly known as N64). And if we don't have it, write us and we'll try and get it for you. From Super Mario 64 to Conker's Bad Fur Day and final fantasy, we sell it here at reasonable prices.
007: The World is Not Enough
N64GM024 - Developed by Eurocom Entertainment Software AND Published by Electronic Arts, Inc., "007: The World is Not Enough" was released for the...
1080° Snowboarding
n64gm061 - Developed and Published by Nintendo of America Inc., 1080 degrees Snowboarding was released for the Nintendo 64 Entertainment System (N64)...
n64gm137 - Developed by Travellers Tales (Uk) Ltd. and Published by Activision, Inc., Activision, Inc., "Disney Pixar A Bug's Life" was released for...
All-Star Baseball 99
n64gm177 - Developed by Iguana Entertainment, Inc. and Published by Acclaim Entertainment, Inc., "All Star Baseball '99" was released for the...
Army Men: Sarge's Heroes 2 (Green Version)
#n64gm110 - Developed and Published by The 3DO Company, "Army Men: Sarge's Heroes 2" was released for the Nintendo 64 (N64) Entertainment System on...
Backstage Assault
n64gm174 - Developed by Kodiak Interactive Software Studios, Inc. and Published by Electronic Arts, Inc. "WCW Backstage Assault," was released for...
n64gm064 - Developed by Rare, Ltd. and Published by Nintendo of America Inc., "Banjo Kazooie" was released for the Nintendo 64 (N64) system on May...
n64gm065 - Developed by Rare, Ltd. and Published by Nintendo of America Inc., "Banjo-Tooie" was released on November Nov 20, 2000 for the Nintendo 64...
BattleTanx
n64gm173 - Developed and Published by the 3DO Company, "BattleTanx" was released for the Nintendo 64 (N64) Entertainment System on December 29, 1998....
Beetle Adventure Racing!
n64gm165 - Developed by Electronic Arts Canada, Paradigm Entertainment Inc. and Published by Electronic Arts, Inc., "Beetle Adventure Racing!" was...
Bio Freaks
n64gm067 - Developed by Saffire Corporation and Published by Midway Games, Inc., "Bio Freaks" was released for the Nintendo 64 (N64) System in May of...
Blast Corps
n64gm192 - Developed by Rare, Ltd. and Published by Nintendo of America Inc., "Blast Corps" was released for the Nintendo 64 (N64) Entertainment...
n64gm190 - Developed by Player 1 and Published by Titus France SA, "Blues Brothers 2000" was released for the Nintendo 64 (N64) Entertainment System...
Bomberman Hero
#n64gm115 - Developed by A.I Co., Ltd. and Published by Hudson Soft Company, Ltd., "Bomberman Hero" was released for the Nintendo 64 Entertainment...
Buck Bumble
n64gm188 - Developed by Argonaut Software Ltd. and Published by Ubi Soft Entertainment Software, Buck Bumble" was released for the Nintendo 64 (N64)...
Dual Heroes
Xena Warrior Princess: The Talisman of F...
Bust-A-Move 2 (Again) Arcade Edition
Bust-A-Move '99
Mischief Makers
Sin and Punishment: Su...$49.99 $36.99
The Legend of Zelda: Ocarina of...
Goldeneye: 007
Mario Golf
Donkey Kong 64
VisionTek 900636 Mini DisplayPort to HDMI Active Adapter (M/F)

redpajama_set_name: RedPajamaCommonCrawl


WILLEMSTAD - The 47-year-old Eugene Rhuggenaath is likely to be the new Prime Minister of Curaçao. His liberal political party Partido Alternativa Real (PAR) won on 6 of 21 seats on Friday and is now the biggest party to form a stable government.
The most obvious coalition partner is the social democratic party MAN of former Prime Minister Hensley Koeiman, who achieved five seats.
Curaçao, which has an autonomous status within the Kingdom since 2010, according to the Dutch Member of Parliament Ronald van Raak (SP), chose for the Kingdom and against corruption. Otherwise formulated: for the democratic parties and against the "mafia parties". The latter remark is, in particular, a reference to the anti-Dutch politician convicted of corruption, Gerrit Schotte and his party MFK.
Rhuggenaath studied Business Administration in Miami and at the Rotterdam School of Management. He has been active in politics since 2003 but retired from politics in 2009 after a conflict with his party. In 2015 he was retrieved as a "lost son".


Transition is energy's new buzzword. Benign as it sounds, for oil companies and many utilities it means the game is up. Or will be. Sometime. A consensus about when hasn't emerged. But predictions of the end are legion these days. Dieter Helm's new book, Burn Out, is the latest. It's long on hunches, short on detail.
Helm's thesis is straightforward. Three "predictable surprises" are in store: the end of the commodity super-cycle and the fall in oil and gas prices over the long term; decarbonisation; and technological revolution.
The oil companies that dominate today are doomed, though they don't realise it. Their businesses simply can't exist alongside the climate imperative. There is a "basic and fundamental disconnect" between the "assumptions of business-roughly-as-usual and the fate of the planet".
Prices will fall over the long term because shale, Iran, Iraq and other resource-rich areas have much more oil to yield, but also because producers, fearing imminent demise, will pump while they can. On the demand side, the China growth story is over and new materials will replace plastics (and therefore the need for petrochemicals). All the while, alternative sources of energy will take over. Oil prices of $40-60 a barrel or lower "may be the new normal".
In Helm's words, this is "a story about digitalisation, the coming of robots, 3-D printing, artificial intelligence, and the applications of communications technologies to infrastructure". It is, therefore, about "the electrification of almost everything". Few if any of the big incumbent energy firms "can look forward to survival in the medium term—and certainly not a ripe old age".
Helm scores some hits. In the energy sector, "resistance to the idea that the future might be very different from the past is endemic" and the "existential threat has not sunk in". He's right—the proof is in each long-term outlook from the oil majors. Their future always looks a lot like now, but with more demand for fossil fuels.
Helm is especially strong on the radically different economic model embedded in new alternative energy. Almost all new forms of generation—crucial, because digitalisation means more electricity—do not have an energy cost once they are installed, he writes. A world of zero-marginal-cost energy is one where energy-demand growth does not matter.
This isn't the only big change Helm foresees. A world of sleepless and ununionised robotic workers means cheap labour in Asia is irrelevant. Manufacturing can return closer to the buyers. Global trade will shrink. Europe and, especially, the US will fare best in this new economy.
The thesis is sometimes subtle, and occasionally confusing. Decarbonisation is coming. But Helm spends a good chunk of the book rubbishing both today's alternative energies—simply not up to dealing with the climate problem—and the global emissions agreements, from Kyoto to Paris. It's hard, after this successful demolition job, to grasp that, nonetheless, decarbonisation efforts will be successful.
Technology is the answer, Helm believes. Battery storage at scale will surely make a difference. Smart meters and the internet of things sound plausible. Battery-powered cars will threaten oil, as will materials like graphene to replace plastics. But their triumph is assumed, not shown. The book is light on details. Helm places huge faith in some future solar technology, but isn't clear what it will be. "It is now possible to at least imagine [Helm's italics] a world in which almost everything could be coated in solar film." Almost everything? Is it?
The book's section on the geopolitics of all this is weak and already dated. That tight oil means "the US can now afford to offend the Saudis" is definitely a sentence from the pre-Trump era. So are the bits about the US switching its allegiance from Riyadh to Tehran. Turkey and Russia are no longer "in a stand-off". Iran doesn't have "Red Guards" (Russia and China did), they are Revolutionary Guards. Helm justifiably pans the Saudi Vision 2030, but misnames it. Cnooc did not buy Canada's Nexus, it bought Nexen. And so on.
As for China, Helm thinks its transition from an export-led economy to a consumption-based one will fail. Few other countries have managed such a shift. This is another threat to oil. Yet, Helm writes, it would be "foolhardy to simply extrapolate Chinese energy demand into the future at current growth rates and assume that it will be the engine for pushing world oil demand to 100m b/d and beyond". Perhaps. But global demand is already 98.2m b/d, and rising at a clip of about 1.5m b/d per year, and China accounts for more than a third of the rise this year.
Still, the broad transition argument is hard to dispute and Helm is surely right about the implications for oil companies. The 21st century will not belong to the existing players. Their best ploy may be what Helm calls "harvest and exit": recognise the clock is ticking and pump hard before the price decline takes over.
This is bad news for the pension funds and governments that rely on the oil sector's dividends and taxes. The good news? Digitalisation, electrification and the arrival of the bots will save the planet.


text:
Q: Trouble using Find/Replace with a regex I have the below sample text
in front xxxx extra xxxx

that I am trying to convert so "http" starts on a new line:
in front
xxxx
xxxx

I am using TEXTPAD with regular expressions checked in the FIND/REPLACE window.
I have tried using the /n command, but all it does is add the /n to the from of xxxx in the original line.
How do I use FIND/REPLACE with regular expressions to do what I want?

A: You have your syntax confused and backwards. A newline sequence is \n not "/n" ...

redpajama_set_name: RedPajamaStackExchange


text:
require "komments/version"
require "komments/configuration"

module Komments
  def self.configure
    yield(configuration)
  end

  def self.website_url
    "//#{configuration.root_url}/embed/#{configuration.api_key}"
  end

  private

  def self.configuration
    Configuration.instance
  end
end

if defined?(Rails::Railtie)
  require 'komments/railtie'
end

redpajama_set_name: RedPajamaGithub


Correspondence issued by the General Accounting Office with an abstract that begins "GAO provided information on how a Direct Vendor Delivery (DVD) contract would affect the Navy's financial reporting, focusing on: (1) whether accounting and auditing standards would require DVD contractors to report individual transactions through the Transaction Item Reporting (TIR) system; and (2) what level of reporting would be required under a DVD contract to meet accounting and auditing standards."
United States. General Accounting Office. September 13, 2000.
This text is part of the collection entitled: Government Accountability Office Reports and was provided by UNT Libraries Government Documents Department to Digital Library, a digital repository hosted by the UNT Libraries. It has been viewed 123 times , with 7 in the last month . More information about this text can be viewed below.
United States. General Accounting Office. Financial Management: Financial Reporting Issues Related to the Navy's Direct Vendor Delivery Initiative, text, September 13, 2000; Washington D.C.. (https://digital.library.unt.edu/ark:/67531/metadc297968/: accessed April 24, 2019), University of North Texas Libraries, Digital Library, https://digital.library.unt.edu; crediting UNT Libraries Government Documents Department.


text:
Chancellor-elect, trustees hear about research, outreach at Highlands Biological Station
Established in 1927, the facility includes the Highlands Nature Center, the William Coker Laboratories and the Highlands Botanical Garden, plus public-accessible trails and boardwalks.
Retired educator receives lifetime achievement award from craft guild
Anna Fariello, retired associate professor for digital initiatives, was honored for her work at WCU and its benefit to the community.
MHC hosts exhibit on ancient Spanish fort, Native American town
"Uncovering Our Forgotten Past: Fort San Juan" focuses on an archaeological site that was an important Native American township and later a Spanish fortification.
Summer camps to focus on nature exploration, laboratory science
Both camps will be led by Max Lanning, a science teacher at Swain County High School and WCU alumnus.
Nominations are sought for this year's Mountain Heritage Awards
The honors are presented at WCU's annual fall festival of Appalachian culture, Mountain Heritage Day.
Board of Trustees schedule quarterly meeting for June 7
The board also will hold committee meetings beginning at 2 p.m. Thursday, June 6, in the boardroom.
Rimes to assume director position for public affairs master's program
The MPA program prepares town managers, directors of nonprofit organizations, professors, police officers and other professionals committed to public service.
Program for the Study of Developed Shorelines joins American Flood Coalition
The coalition states its mission is to protect the nation's residents, economy and military installations.
Graduate student explores dystopia, literature, and racial bias in journalism
Crystal Ellwood constantly toed the line between literature and art up until the moment she decided to pursue her graduate degree in English at Western Carolina University. Her passion for literature and creative arts inspired her to take a more creative approach to her literature masters and paved the way for her first novel.


We found this great socks for retro gaming addicts. Our nerd product finder checked online shops for Mega Man Socks and came back with this unique thing. Next search will be a geeky item or a hostess gift.


Offered, will cost more on overall out of pocket costs.
There was no supplemental life insurance available at my time of occupation. I would have purchased it if it had been available.
What can you tell job seekers about ALDI's Supplemental Life Insurance?"
Glassdoor is your resource for information about the Supplemental Life Insurance benefits at ALDI. Learn about ALDI Supplemental Life Insurance, including a description from the employer, and comments and ratings provided anonymously by current and former ALDI employees.


text:
Read Next:	Box Office: 'Bad Boys for Life' Scores Big With $66 Million Launch
June 5, 2012 7:23PM PT
Beall writing 'Justice League' for Warner Bros.
Superhero pic back on with 'Gangster Squad' writer
By Jeff Sneider
's Most Recent Stories
Sundance: Oscilloscope nabs 'Mother of George'
Sundance: Miller bros. make debut with 'Sweetwater'
Sony Pictures Classics nabs 'Before Midnight'
While Disney and Marvel were busy shooting "The Avengers" last year, Warner Brothers quietly began getting its own all-star superhero pic back on track, tapping "Gangster Squad" scribe Will Beall to write "Justice League," based on the WB-controlled stable of DC Comics superheroes.
Warner Bros. had no comment on the top-secret hire, which, due to its timing, was more in anticipation of — rather than a reaction to — the box office success of "The Avengers."
Beall has yet to turn in his "Justice League" script, though he has become a favorite scribe of Warners. He's been linked to the studio's proposed "Lethal Weapon" reboot and several other projects at WB, which will release "Gangster Squad" on Sept. 7.
Warners originally tried to mount a "Justice League" movie several years ago, with George Miller directing from a script by Kieran and Michele Mulroney. That iteration was set to star Adam Brody as the Flash, Megan Gale as Wonder Woman and then-newcomer Armie Hammer as Batman. Back in January 2008, the studio cited a lack of tax breaks as the main reason it pulled the plug on the project, which also needed a rewrite that wasn't possible because of the writers' strike.
DC Comics is a vital component of Warner Bros.' intellectual property, as "Green Lantern" scribes Marc Guggenheim and Michael Green were tapped to write "The Flash" for director Greg Berlanti, while another "Green Lantern" scribe, Michael Goldenberg, was hired to write "Wonder Woman." Additionally, Brad Peyton is working on a new draft of "Lobo," while John Kamps and David Koepp are developing "Spy vs. Spy" as a potential directing vehicle for Ron Howard. WB also developed the "Aquaman" property several years ago.
Beall is repped by CAA and Management 360.
Independent Filmmaker Project
John Kamps
Katherine Oliver
Michael Goldenberg
The Gangster Squad
Will Beal
More Film
Netflix Praised by 'The Irishman,' 'Marriage Story' Filmmakers at Producers Guild Panel
Streaming giant Netflix received strong support from filmmakers behind "The Irishman" and "Marriage Story" at the Producers Guild of America's nominees panel on Saturday at the Skirball Cultural Center in Los Angeles. Jane Rosenthal, one of "The Irishman" producers, said Netflix embraced the vision that she and Martin Scorsese had for the $170 million film. [...]
Gabriel Harel Discusses Dystopic Parable 'The Night of the Plastic Bags'
With his first short film, the animated "Yùl and the Snake," Gabriel Harel won Europe's Cartoon d'Or for the continent's best animated short film, given at the 2016 Cartoon Forum in Toulouse. Now, Harel's awaited sophomore effort, the animated "The Night of the Plastic Bags," competes at UniFrance's MyFrenchFilmFestival, and is available on a swathe [...]
'The Glorious Acceptance of Nicolas Chauvin': Nationalism Wrapped in Charisma
Winner of Locarno's Signs of Life section, Benjamin Crotty's "The Glorious Acceptance of Nicolas Chauvin" has enjoyed more than 12 months of festival success and critical acclaim as it reaches the end of its festival run at UniFrance's MyFrenchFilmFestival. A modern take on one of France's most influential yet widely unknown characters, the film headlines [...]
Alexander Ludwig on Sharing his Recovery Journey, Playing the 'Bad Boys' Tech Guy
With his towering height and stature, Alexander Ludwig looks every bit the action star, first appearing as Cato in "The Hunger Games," and more recently as fierce Norse Viking chief Bjorn Ironside on History Channel's "Vikings" and in "Bad Boys for Life," the third installment of the "Bad Boys" franchise, with Will Smith and Martin [...]
Box Office: 'Bad Boys for Life' Scores Big With $66 Million Launch
"Bad Boys for Life" is showing plenty of power at the North American box office with an impressive launch of around $66 million at 3,740 venues over the four-day holiday weekend. Sony's sequel to 1995's "Bad Boys" and 2003's "Bad Boys II" far exceeded the studio's pre-release forecasts of a $38 million weekend. The film, [...]
'A Bump Along the Way': Film Review
While "Derry Girls" continues to be the last word in young, raucous female rebellion on the Emerald Isle, "A Bump Along the Way" has a little something to add. Sin the same Northern Irish city as the hit Netflix sitcom, but shedding the '90s nostalgia for the Snapchat age, Shelly Love's appealing, unassuming debut feature [...]
Tresor Films Plots $72 Million 'Asterix & Obelix: The Silk Road,' New Projects (EXCLUSIVE)
After delivering two of the highest-grossing French films of last year, Alain Attal's Paris-based production company Tresor Films ("Sink or Swim," "Little White Lies 2") is kicking off 2020 with its most ambitious project yet, Guillaume Canet's "Asterix & Obelix: The Silk Road." Co-produced and financed by Jerome Seydoux's Pathé, "Asterix & Obelix" is budgeted [...]


Home ›› Personal Care ›› Trimmers ›› Nova Prime Series NHT 1087 Turbo power Cordless Trimmer fo..
492 people have added this product to Wishlist.
I am happy!!! good product, I am satisfied thank you for !!! Flipcart !!! ??????????
Awesome Trimmer, specially nice setting in points, So you can Trim your Beard according to your choice..... Pros 90 min Run Time Good performance Nice Beard Trimming Easy to use Great battery backup 20 length settings Titanium blades universal voltage Superior quality Cons.... At the moment, there is no issue.
We have aggregated Nova Prime Series NHT 1087 Turbo power Cordless Trimmer for Men price and coupon offers available across all online stores in India.
Nova Prime Series NHT 1087 Turbo power Cordless Trimmer for Men lowest price in India as on Wed, 24 Apr 2019 is Rs. 849.0 offered by Flipkart.
Products similar to Nova Prime Series NHT 1087 Turbo power Cordless Trimmer ..