text:
# A Continuous Variable Shor Algorithm

## 1. Introduction

In this paper, we create a continuous variable analogue of Shor’s quantum factoring algorithm. This algorithm is called a continuous variable Shor algorithm for the following reason. Recall that Shor’s quantum factoring algorithm , ,  reduces the task of factoring an integer $`N`$ to that of finding the period $`P`$ of a function

$$\mathrm{\Phi }:\mathrm{mod}N$$

from the integers $``$ to the integers $``$ modulo $`N`$. So by a continuous variable analogue to Shor’s factoring algorithm, we mean a quantum algorithm that finds the period $`P`$ of a function

$$\mathrm{\Phi }:$$

from the reals $``$ to the reals $``$.

One of the objectives in creating this continuous variable quantum algorithm was to make the structure of Shor’s factoring algorithm more mathematically transparent, and thereby give some insight into the inner workings of his original quantum factoring algorithm , . This continuous quantum algorithm also gives some insight into the inner workings of Hallgren’s Pell’s equation algorithm.

Whether or not this quantum algorithm is more efficient than its classical continuous variable counterpart remains to be determined. By allowing continuous variables, the complexity class of problems can easily change. For more insight into this issue, we refer the reader to Bartlett et al , . Moreover, the implementability of this continuous variable quantum algorithm, or an approximation there of, also remains to be determined.

Continuous variable algorithms for two other quantum algorithms are to be found in the open literature. A continuous variable analogue of Grover’s algorithm was constructed by Pati, Braunstein, and Lloyd in ; and a continuous variable Deutsch-Jozsa algorithm was recently created by Pati and Braunstein in .

There is also a great deal of literature written on many other areas of continuous variable quantum information science. For example, work on continuous variable teleportation can be found in , , and , on continuous variable quantum secrecy sharing in  and , on continuous variable entanglement in , and on continuous variable quantum error correction in  and .

## 2. Mathematical machinery

To create a continuous variable analogue of Shor’s algorithm, we will need to make use of the mathematical machinery of generalized functions (also known as distributions) and of rigged Hilbert spaces (also known as Gel’fand triplets.) For more in depth discussions of this mathematical machinery, we refer the reader to , , , , , and .

### 2.1. Generalized functions

In regard to generalized functions, the reader is no doubt familiar with one generalized function, namely, the Dirac delta function

$$\delta \left(x\right)$$

on the reals $``$. We will also make use of the following generalized function

$$\delta _P\left(x\right)=\frac{1}{\left|P\right|}\underset{n=\mathrm{}}{\overset{\mathrm{}}{}}\delta \left(x\frac{n}{P}\right)\text{,}$$

which is an infinite sum of Dirac delta functions over the lattice $`\{\frac{n}{P}:n\}`$, where $`P`$ is a nonzero real number.

### 2.2. Rigged Hilbert spaces

We will make use of the rigged Hilbert space $`_{}`$ with orthonormal basis

$$\left\{\right|x:x\}\text{}$$

where by orthonormal we mean there is a bracket product on $`_{}`$ defined by

$$xy=\delta \left(xy\right)\text{ .}$$

The elements of $`_{}`$ are formal integrals of the form

$$_{\mathrm{}}^{\mathrm{}}𝑑xf\left(x\right)|x\text{ ,}$$

where $`f:`$ is a function or a generalized function.

For $`x_0`$ a constant, we define

$$|x_0=\underset{\mathrm{}}{\overset{\mathrm{}}{}}𝑑x\delta \left(xx_0\right)|x$$

Since the Dirac delta function is a tempered distribution , it follows that

$$y_0x_0=\{\begin{array}{cc}1\hfill & \text{if }x_0=y_0\hfill \\ & \\ 0\hfill & \text{otherwise}\hfill \end{array}$$

## 3. Fourier analysis on the real line $``$

Let $`\mathrm{\Phi }:`$ be a periodic admissible function of minimum period $`P`$ from the reals $``$ to the reals $``$.

###### Remark 1.

We have intentionally not defined the term ‘admissible,’ since there are many possible definitions of this term. For example, one workable definition of an admissible function is a function that is Lebesgue integrable on every closed subinterval of the reals $``$.

We seek to define the Fourier transform of $`\mathrm{\Phi }`$. Since $`\mathrm{\Phi }`$ is in general neither $`L^1`$ nor $`L^2`$ nor of compact support, the usual definitions of the Fourier transform will not apply. So we need to be a bit creative.

We proceed to define the Fourier transform as follows:

###### Definition 1.

Let $`\mathrm{\Phi }:`$ be a periodic admissible function of minimum period $`P`$ from the reals $``$ to the reals $``$. We interpret the standard expression $`{\displaystyle \underset{\mathrm{}}{\overset{\mathrm{}}{}}}𝑑xe^{2\pi ixy}\mathrm{\Phi }\left(x\right)`$ for the Fourier transform $`\widehat{\mathrm{\Phi }}:`$ as the generalized function

$$\widehat{\mathrm{\Phi }}\left(y\right)=\delta _P\left(y\right)\underset{0}{\overset{P}{}}𝑑xe^{2\pi ixy}\mathrm{\Phi }\left(x\right)$$

where

$$\delta _P\left(y\right)=\frac{1}{\left|P\right|}\underset{n=\mathrm{}}{\overset{\mathrm{}}{}}\delta \left(y\frac{n}{P}\right)\text{ ,}$$

and where $``$ denotes the complex numbers.

###### Remark 2.

The above definition can be motivated as follows:

$$\begin{array}{ccc}\underset{\mathrm{}}{\overset{\mathrm{}}{}}𝑑xe^{2\pi ixy}\mathrm{\Phi }\left(x\right)& =& \underset{n=\mathrm{}}{\overset{\mathrm{}}{}}\underset{nP}{\overset{\left(n+1\right)P}{}}𝑑xe^{2\pi ixy}\mathrm{\Phi }\left(x\right)\hfill \\ & & \\ & =& \underset{n=\mathrm{}}{\overset{\mathrm{}}{}}\underset{0}{\overset{P}{}}𝑑xe^{2\pi i\left(x+nP\right)y}\mathrm{\Phi }\left(x+nP\right)\hfill \\ & & \\ & =& \underset{n=\mathrm{}}{\overset{\mathrm{}}{}}e^{2\pi inPy}\underset{0}{\overset{P}{}}𝑑xe^{2\pi ixy}\mathrm{\Phi }\left(x\right)\hfill \\ & & \\ & =& \underset{n=\mathrm{}}{\overset{\mathrm{}}{}}\frac{1}{\left|P\right|}\delta \left(y\frac{n}{P}\right)\underset{0}{\overset{P}{}}𝑑xe^{2\pi ixy}\mathrm{\Phi }\left(x\right)\hfill \\ & & \\ & =& \delta _P\left(y\right)\underset{0}{\overset{P}{}}𝑑xe^{2\pi ixy}\mathrm{\Phi }\left(x\right)\hfill \end{array}$$

where, in the context of distributions, we have

$$\underset{n=\mathrm{}}{\overset{\mathrm{}}{}}e^{2\pi inPy}=\frac{1}{\left|P\right|}\delta \left(y\frac{m}{P}\right)\text{ , for }y[\frac{m}{P},\frac{m+1}{P})$$

(See .)

The reader can easily verify that the inverse Fourier transform behaves as expected, i.e., that

###### Proposition 1.

$$\mathrm{\Phi }\left(x\right)=\underset{\mathrm{}}{\overset{\mathrm{}}{}}𝑑ye^{2\pi ixy}\widehat{\mathrm{\Phi }}\left(y\right)$$

## 4. The algorithm for finding integer periods

Let

$$\mathrm{\Phi }:$$

be a periodic admissible function of minimum period $`P`$ from the reals $``$ to the reals $``$. We will now create a continuous variable Shor algorithm to find integer periods. In later sections, we will extend the algorithm to rational periods, and then to irrational periods.

We construct two quantum registers

$$|\text{Left Register}\text{ and }|\text{Right Register}$$

called left- and right-registers respectively, each ‘living’ respectively in its own separate rigged Hilbert space $`_{}`$. The left register is constructed to hold arguments of the function $`\mathrm{\Phi }`$, the right to hold the corresponding function values.

We assume we are given the unitary transformation

$$U_\mathrm{\Phi }:_{}_{}_{}_{}$$

defined by

$$U_\mathrm{\Phi }:|x|y|x|y+\mathrm{\Phi }\left(x\right)$$

Finally, we choose a large positive integer $`Q`$, so large that $`Q2P^2`$.

The quantum part of our algorithm consists of Step 0 through Step 4 as described below:

* Initialize

$$|\psi _0=|0|0$$
* Apply the inverse Fourier transform to the left register, i.e. apply $`^11`$ to obtain

$$|\psi _1=\underset{\mathrm{}}{\overset{\mathrm{}}{}}𝑑xe^{2\pi ix0}|x|0=\underset{\mathrm{}}{\overset{\mathrm{}}{}}𝑑x|x|0$$
* Apply $`U_\mathrm{\Phi }:|x|u|x|u+\mathrm{\Phi }\left(x\right)`$ to obtain

$$|\psi _2=\underset{\mathrm{}}{\overset{\mathrm{}}{}}𝑑x|x|\mathrm{\Phi }\left(x\right)$$
* Apply the Fourier transform to the left register, i.e. apply $`1`$ to obtain

$`|\psi _3`$ $`={\displaystyle \underset{\mathrm{}}{\overset{\mathrm{}}{}}}𝑑y{\displaystyle \underset{\mathrm{}}{\overset{\mathrm{}}{}}}𝑑xe^{2\pi ixy}|y|\mathrm{\Phi }\left(x\right)={\displaystyle \underset{\mathrm{}}{\overset{\mathrm{}}{}}}𝑑y|y{\displaystyle \underset{n=\mathrm{}}{\overset{\mathrm{}}{}}}{\displaystyle \underset{nP}{\overset{\left(n+1\right)P}{}}}𝑑xe^{2\pi ixy}|\mathrm{\Phi }\left(x\right)`$
$`={\displaystyle \underset{\mathrm{}}{\overset{\mathrm{}}{}}}𝑑y|y{\displaystyle \underset{n=\mathrm{}}{\overset{\mathrm{}}{}}}{\displaystyle \underset{0}{\overset{P}{}}}𝑑xe^{2\pi i\left(x+nP\right)y}|\mathrm{\Phi }\left(x+nP\right)`$
$`={\displaystyle \underset{\mathrm{}}{\overset{\mathrm{}}{}}}𝑑y|y\left({\displaystyle \underset{n=\mathrm{}}{\overset{\mathrm{}}{}}}e^{2\pi inPy}\right)\left({\displaystyle \underset{0}{\overset{P}{}}}𝑑xe^{2\pi ixy}|\mathrm{\Phi }\left(x\right)\right)`$
$`={\displaystyle \underset{\mathrm{}}{\overset{\mathrm{}}{}}}𝑑y|y\delta _P\left(y\right)\left({\displaystyle \underset{0}{\overset{P}{}}}𝑑xe^{2\pi ixy}|\mathrm{\Phi }\left(x\right)\right)={\displaystyle \underset{n=\mathrm{}}{\overset{\mathrm{}}{}}}|{\displaystyle \frac{n}{P}}\left({\displaystyle \frac{1}{\left|P\right|}}{\displaystyle \underset{0}{\overset{P}{}}}𝑑xe^{2\pi ix\frac{n}{P}}|\mathrm{\Phi }\left(x\right)\right)`$
$`={\displaystyle \underset{n=\mathrm{}}{\overset{\mathrm{}}{}}}|{\displaystyle \frac{n}{P}}|\mathrm{\Omega }\left({\displaystyle \frac{n}{P}}\right)`$

where

$$|\mathrm{\Omega }\left(\frac{n}{P}\right)=\frac{1}{\left|P\right|}\underset{0}{\overset{P}{}}𝑑xe^{2\pi ix\frac{n}{P}}|\mathrm{\Phi }\left(x\right)\text{ .}$$

* Measure the left register with respect to the observable

$$𝒪=\underset{\mathrm{}}{\overset{\mathrm{}}{}}𝑑y\frac{Qy}{Q}|yy|$$

to produce a random eigenvalue

$$\frac{m}{Q}\text{ ,}$$

where $`Qy`$ denotes the greatest integer $`Qy`$, and then determine whether $`\frac{m}{Q}`$ can be used to find the period $`P`$.

## 5. The observable $`𝒪`$

In this section, we now discuss the above Step 4 in greater detail.

The spectral decomposition of the observable $`𝒪`$ is given by

$$𝒪=\underset{\mathrm{}}{\overset{\mathrm{}}{}}𝑑x\frac{Qx}{Q}|xx|=\underset{m=\mathrm{}}{\overset{\mathrm{}}{}}\left(\frac{m}{Q}\right)P_m\text{ ,}$$

where $`P_m`$ denotes the projection operator

$$P_m=\underset{\frac{m}{Q}}{\overset{\frac{m+1}{Q}}{}}𝑑x|xx|$$

Measurement of the left register of

$$|\psi _3=\underset{n=\mathrm{}}{\overset{\mathrm{}}{}}|\frac{n}{P}|\mathrm{\Omega }\left(\frac{n}{P}\right)$$

with respect to $`𝒪`$ will always produce an eigenvalue $`\frac{m}{Q}`$ for which there exists an integer $`n`$ such that

$$\frac{m}{Q}\frac{n}{P}<\frac{m+1}{Q}$$

We seek to determine the unknown rational $`\frac{n}{P}`$ from the known rational eigenvalue $`\frac{m}{Q}`$.

If $`Q2P^2`$, then the unknown rational $`\frac{n}{P}`$ will be a convergent of the continued fraction expansion of the known eigenvalue $`\frac{m}{Q}`$. Thus, the continued fraction recursion can be used to determine the period $`P`$. (See \[18, Theorem 184, Section 10.15\].)

## 6. The algorithm for finding rational periods

We now extend the above algorithm to one for finding rational periods

$$P=\frac{a}{b}\text{}\mathrm{gcd}(a,b)=1$$

We choose an integer $`Q2a^2`$.

* Execute the above steps Step 0 through Step 4 twice to produce two eigenvalues

$$\frac{m_1}{Q}\text{ and }\frac{m_2}{Q},$$

and then goto Part 2.

Since $`Q2a^2`$, the eigenvalues $`\frac{m_1}{Q}`$ and $`\frac{m_2}{Q}`$ will have unique convergents respectively of the form

$$\frac{n_1b}{a}\text{ and }\frac{n_{2b}}{a}$$

(See \[18, Theorem 184, Section 10.15\].)

If the following Condition A is satisfied, then the reciprocal period is simply given by

$$\frac{1}{P}=\frac{\mathrm{gcd}(n_1b,n_2b)}{a}$$

Condition A. $`\mathrm{gcd}(n_1,n_2)=1`$, $`\mathrm{gcd}(n_1,a)=1`$, $`\mathrm{gcd}(n_2,a)=1`$

If we assume that Condition A is satisfied, then the above expression for the reciprocal period can be computed in Part 2 given below:

* Execute the following:

+ Compute all the convergents $`\{\frac{p_{1k}}{q_{1k}}:k=1,2,\mathrm{},K\}`$ and $`\{\frac{p_2\mathrm{}}{q_2\mathrm{}}:\mathrm{}=1,2,\mathrm{},L\}`$ of $`\frac{m_1}{Q}`$ and $`\frac{m_2}{Q}`$, respectively
    + Search for denominators $`q_{1k}`$ and $`q_2\mathrm{}`$ which are equal

    For $`k=1,2,\mathrm{},K`$ do

    For $`\mathrm{}=1,2,\mathrm{},L`$ do

    If $`q_{1k}=q_2\mathrm{}`$ then

    Let $`q=q_{1k}=q_2\mathrm{}`$ and $`\alpha =\frac{q}{\mathrm{gcd}(p_{1k},p_2\mathrm{})}`$

    If $`\alpha `$ is a period of $`\mathrm{\Phi }`$ Then

    Output $`\alpha `$ and Stop \# Period found

    EndFor

    EndFor

    goto Part 1 \# Period not found

Part 2 will find and output the period $`P`$ provided the output of Part 1 satisfies Condition A. From the last corollary of the Appendix, we know this will occur after Part 1 is repeated an average of $`O\left(\left(\mathrm{lg}\mathrm{lg}a\right)^2\right)=O\left(\left(\mathrm{lg}\mathrm{lg}Q\right)^2\right)`$ times. However, since we do not know until the completion of Part 2 whether or not the output of Part 1 satisfies Condition A , both Part 1 and Part 2 need to be repeated on average at most $`O\left(\left(\mathrm{lg}\mathrm{lg}Q\right)^2\right)`$ to finally find the output $`P`$.

###### Remark 3.

One can quadratically speedup Step 6 by taking advantage of the fact that the convergent denominators are linearly ordered.

## 7. Finding irrational periods

The above algorithm can be extended to finding, to any degree of desired precision, the period $`P`$ of a periodic admissible function $`\mathrm{\Phi }`$ when the period $`P`$ is irrational. But in this case, there is a severe restrictive condition that must be imposed on the function $`\mathrm{\Phi }`$. Namely, we need to assume that the function $`\mathrm{\Phi }`$ is continuous. This continuity condition is needed for determining whether or not a rational is sufficiently close to the unknown irrational period.

## 8. Conclusion

The continuous variable quantum algorithm constructed in this paper does give some insight into the inner workings of Shor’s original quantum factoring algorithm. Moreover, it also gives some insight into the inner workings of Hallgren’s Pell’s equation algorithm.

On the other hand, the quantum algorithm constructed in this paper raises many more questions than it answers. Is this quantum algorithm more efficient than its classical continuous variable counterpart? Can this algorithm be implemented? Can an approximation of this algorithm be implemented?

## 9. Appendix. Number theoretic probabilities.

In this Appendix, we derive an asymptotic lower bound $`\mathrm{\Omega }\left(\left(\frac{1}{\mathrm{lg}\mathrm{lg}a}\right)^2\right)`$ on the probability that the output of Part 1 of the algorithm found in Section 6 of this paper will satisfy the Condition A defined within that Section.

Notation Convention. Throughout this section, the symbol ‘$`p`$’ will always be used to denote a prime integer.

###### Proposition 2.

Let $`a`$ be a fixed positive integer. Then for every positive integer $`Na`$, if an integer $`n`$ is randomly chosen from the set integers

$$\{k:0<kN\}$$

according to the uniform probability distribution, then the probability

$$Prob_N\left(\underset{}{\overset{}{\mathrm{gcd}}}(a,n)=1\right)$$

that $`n`$ is relatively prime to $`a`$ is bounded below by

$$Prob_N\left(\underset{}{\overset{}{\mathrm{gcd}}}(a,n)=1\right)\frac{\phi \left(a\right)}{a}\text{}$$

where $``$ denotes the set of integers, and where $`\phi `$ denotes the Euler phi function.

###### Proof.

$$Prob_N\left(\underset{}{\overset{}{\mathrm{gcd}}}(a,n)=1\right)=\underset{pa}{}\left(1\frac{N/p}{N}\right)\underset{pa}{}\left(1\frac{1}{p}\right)=\frac{\phi \left(a\right)}{a}$$

As a corollary, we have:

###### Corollary 1.

Let $`a`$ be a fixed positive integer. Then for every positive integer $`Na`$, if $`n_1`$ and $`n_2`$ are two random integers chosen independently with replacement from the set integers

$$\{k:0<kN\}$$

according to the uniform probability distribution, then the probability

$$Prob_N\left(\underset{}{\overset{}{\mathrm{gcd}}}(a,n_1)=1=\mathrm{gcd}(a,n_2)\right)$$

that both $`n_1`$ and $`n_2`$ are relatively prime to $`a`$ is bounded below by

$$Prob_N\left(\underset{}{\overset{}{\mathrm{gcd}}}(a,n_1)=1=\mathrm{gcd}(a,n_2)\right)\left(\frac{\phi \left(a\right)}{a}\right)^2\text{}$$

where $``$ denotes the set of integers, and where $`\phi `$ denotes the Euler phi function.

###### Proposition 3.

Let $`a`$ be a fixed positive integer. Then for every positive integer $`Na`$, if $`n_1`$ and $`n_2`$ are two random integers chosen independently with replacement from the set of integers

$$\{k:0<kN\}$$

according to the uniform probability distribution, then the conditional probability

$$Prob_N\left(\underset{}{\overset{}{\mathrm{gcd}}}(n_1,n_2)=1\mathrm{gcd}(a,n_1)=1=\mathrm{gcd}(a,n_2)\right)$$

that $`n_1`$ and $`n_2`$ are relatively prime given that $`n_1`$ and $`n_2`$ are both relatively prime to $`a`$ is bounded below by

$$Prob_N\left(\underset{}{\overset{}{\mathrm{gcd}}}(n_1,n_2)=1\mathrm{gcd}(a,n_1)=1=\mathrm{gcd}(a,n_2)\right)\frac{6}{\pi ^2}\text{}$$

where $``$ denotes the set of integers, and where $`\phi `$ denotes the Euler phi function.

###### Proof.

$`Prob_N\left(\underset{}{\overset{}{\mathrm{gcd}(n_1,n_2)=1}}\right|\begin{array}{c}\mathrm{gcd}(a,n_1)=1\\ \text{and}\\ \mathrm{gcd}(a,n_2)=1\end{array})`$ $`={\displaystyle \underset{\underset{pa\text{ and }pN}{p}}{}}\left(1\left({\displaystyle \frac{N/p}{N}}\right)^2\right)`$
$`{\displaystyle \underset{\underset{pa\text{ and }pN}{p}}{}}\left(1p^2\right)`$
$`>{\displaystyle \underset{p}{}}\left(1p^2\right)=\zeta \left(2\right)^1={\displaystyle \frac{6}{^{\pi ^2}}}`$
where $`\zeta `$ denotes the Riemann zeta function. (See .) ∎

###### Corollary 2.

Let $`a`$ be a fixed positive integer. Then for every positive integer $`Na`$, if $`n_1`$ and $`n_2`$ are two random integers chosen independently with replacement from the set of integers

$$\{k:0<kN\}$$

according to the uniform probability distribution, then the probability

$$Prob_N\left(\underset{}{\overset{}{\mathrm{gcd}}}(n_1,n_2)=\mathrm{gcd}(a,n_1)=\mathrm{gcd}(a,n_2)=1\right)$$

that the integers $`a`$, $`n_1`$, $`n_2`$ are all relatively prime to each other is bounded below by

$$Prob_N\left(\underset{}{\overset{}{\mathrm{gcd}}}(n_1,n_2)=\mathrm{gcd}(a,n_1)=\mathrm{gcd}(a,n_2)=1\right)\frac{6}{\pi ^2}\left(\frac{\phi \left(a\right)}{a}\right)^2\text{}$$

where $``$ denotes the set of integers, and where $`\phi `$ denotes the Euler phi function. Moreover, we have the asymptotic bound

$$Prob_N\left(\underset{}{\overset{}{\mathrm{gcd}}}(n_1,n_2)=\mathrm{gcd}(a,n_1)=\mathrm{gcd}(a,n_2)=1\right)=\mathrm{\Omega }\left(\left(\frac{1}{\mathrm{lg}\mathrm{lg}a}\right)^2\right)$$

###### Proof.

The first part of this corollary follows immediately from the above corollary and proposition. The second part follows immediately from a number theoretic theorem found in \[18, Theorem 328, Section 18.4\] which states that

$$liminf\frac{\phi \left(a\right)}{a/\mathrm{ln}\mathrm{ln}a}=e^\gamma \text{,}$$

where $`\gamma `$ denotes Euler’s constant. ∎

## 10. References


format: text

text:
# Competition between adaptive agents: from learning to collective efficiency and back

## 1 No public information

### 1.1 “If it ain’t broke, don’t fix it”

The arguably simplest behavior is the following : if agent $`i`$ wins at time $`t`$, she sticks to her choice $`a_i(t)`$ until she looses, when she takes the opposite choice with probability $`p`$. The dynamics is Markovian, thus can be solved exactly . When $`N`$ is large, the fluctuations $`\sigma ^2`$ are of order $`(pN)^2`$: indeed, as the number of losers is $`N`$, the average number of agents changing their minds at time $`t`$ is $`pN`$. Therefore, one can distinguish three regimes

* $`pN=x=cst`$; this leads to small fluctuations $`\sigma ^2=1+4x(1+x/3)`$, which tend to the absolute minimum $`\sigma ^2=1`$ when $`x0`$. The time needed to reach the stationary state is typically of order $`\sqrt{N}`$.
* $`p1/\sqrt{N}`$; this yields $`\sigma ^2N`$, which is the order of magnitude of produced by agents making independent choices.
* $`pN1`$. In this case, a finite fraction of agents change their mind at each time step and $`\sigma ^2=N(Np^2+4(1p))/(2p)^2N^2`$.

The major problem here is that $`p`$ needs to be tuned in order to reach high efficiency. But it is very easy to design a feedback from the fluctuations on $`p`$ , that lowers $`p`$ as long as the fluctuations are too high, and to use the above results in order to relate the fluctuations to $`p(t\mathrm{})`$. Mathematically, this amounts to take $`p(t=0)=1`$, $`\text{d}p/\text{d}t=f(p,N,t)`$. For instance, $`f(t)=t^\beta `$ seems appropriate as long as $`\beta `$ is small enough. Note that $`p(t)0`$ as $`t\mathrm{}`$, in words, the system eventually freezes. From the optimization point of view, this is a welcome, but as for agents, complete freezing, although being a Nash equilibrium , is not satisfactory. as it may be better for an agent sitting on the losing side to provoke an game-quake and to profit from a re-arrangement of the winners/losers. Therefore, an unanswered question is where to stop the time evolution of $`p`$.

Nevertheless, this simple example illustrates well what happens in MGs: the efficiency essentially depends on the opinion switching rate, which itself depends on the learning rate. It has to be small in order to reach good level of efficiency.

### 1.2 Inductive behavior

Inductive behavior can remedy the problems of the previous learning scheme if, as we shall see, agents know the nature of the game that they are playing. This subsection is a simplified version of the simplest setting for inductive agents of ref. . At time $`t`$, each agent $`i=1,\mathrm{},N`$ plays $`+1`$ with probability $`\pi _i(t)`$, and $`1`$ with probability $`1\pi _i(t)`$. Learning consists in changing $`\pi _i`$ given the outcome of the game at time $`t`$. For this purpose, each agent $`i`$ has a numerical register $`\mathrm{\Delta }_i(t)`$ which reflects her perception at time $`t`$ of the relative success of action $`+1`$ versus action $`1`$. In other words, $`\mathrm{\Delta }_i(t)>0`$ means that she believes that action $`+1`$ has been more successful than $`1`$. The idea is the following: if agent $`i`$ observes $`A(t)<0`$ she will increase $`\mathrm{\Delta }_i`$ and hence her probability of playing $`a_i=+1`$ at the next time step. Reinforcement here means that $`\pi _i`$ is an increasing function of $`\mathrm{\Delta }_i`$. For reasons that will become obvious later, it is advisable to take $`\pi _i=(1+m_i)/2`$ and $`m_i=\chi (\mathrm{\Delta }_i)/2`$, where $`\chi `$ is an increasing function and $`\chi (\pm \mathrm{})=\pm 1`$. The way in which $`\mathrm{\Delta }_i(t)`$ is updated is the last and most crucial element of the learning dynamics to be specified:

$$\mathrm{\Delta }_i(t+1)=\mathrm{\Delta }_i(t)\frac{1}{N}[A(t)\eta a_i(t)].$$
(1)
The $`\eta `$ term above describe the fact that agent $`i`$ may account for her own contribution to $`A(t)`$. When $`\eta =0`$, she believes that $`A(t)`$ is an external process on which she has no influence, or does not know what kind of game she is playing. She may be called naive with this respect. For $`\eta =1`$, agent $`i`$ considers only the behavior of other agents $`A_i(t)=A(t)a_i(t)`$ and does not react to her own action $`a_i(t)`$. As we shall see, this subtlety is the key to high efficiency. The private utility of sophisticated agents corresponds more or less to what is called Aristocrat Utility (AU) in COIN’s nomenclature .

#### Naive agents $`\eta =0`$

It is possible to show that agents minimize the predictability  $`H=A^2`$. As a consequence $`H`$ vanishes in the $`t\mathrm{}`$ limit. There are of course many states with $`H=0`$ and the dynamics selects that which is the “closest” to the initial condition. To be more precise, let $`\mathrm{\Delta }_i(0)`$ be the initial condition (which encodes the a priori beliefs of agent $`i`$ on which action is the best one). As $`t\mathrm{}`$, $`A_t=_im_i(t)0`$ and $`\mathrm{\Delta }_i`$ converges to

$$\mathrm{\Delta }_i(\mathrm{})=\mathrm{\Delta }_i(0)+\delta A,\text{with}\delta A=_0^{\mathrm{}}𝑑tA_t.$$
(2)
The condition $`A_{\mathrm{}}=0`$ provides an equation for $`\delta A`$

$$0=\underset{i=1}{\overset{N}{}}\chi \left(\mathrm{\Delta }_i(0)+\delta A\right).$$
(3)
By the monotonicity property of $`\chi `$, this equation has one and only one solution.

The asymptotic state of this dynamics is information–efficient ($`H=0`$), but it is not optimal, as, in general, this state is not a Nash equilibrium. The fluctuations are indeed determined by the behavior of $`\chi (x)`$. This is best seen with a particular example: assume that the agents behave according to a Logit model of discrete choice  where the probability of choice $`a`$ is proportional to the exponential of the “score” $`U_a`$ of that choice: $`\pi (a)e^{\mathrm{\Gamma }U_a/2}`$. With only two choices $`a=\pm 1`$, $`\pi (a)=(1+am)/2`$ and $`\mathrm{\Delta }=U_+U_{}`$, we obtain 222This learning model has been introduced by  in the context of the MG.

$$\chi (\mathrm{\Delta })=\mathrm{tanh}(\mathrm{\Gamma }\mathrm{\Delta }),i.$$
(4)
Here $`\mathrm{\Gamma }`$ is the learning rate, which measures the scale of the reaction in agent’s behavior (i.e. in $`m_i`$) to a change in $`\mathrm{\Delta }_i`$ . We also assume that agents have no prior beliefs: $`\mathrm{\Delta }_i(0)=0`$. Hence $`\mathrm{\Delta }_i(t)y(t)/\mathrm{\Gamma }`$ is the same for all agents. From the results discussed above, we expect, in this case the system to converge to the symmetric Nash equilibrium $`m_i=0`$ for all $`i`$. This is not going to be true if agents are too reactive, i.e. if $`\mathrm{\Gamma }>\mathrm{\Gamma }_c`$. Indeed, $`y(t)=\mathrm{\Gamma }\mathrm{\Delta }_i(t)`$ satisfies the equation

$`y(t+1)`$ $`=`$ $`y(t){\displaystyle \frac{\mathrm{\Gamma }}{N}}{\displaystyle \underset{i=1}{\overset{N}{}}}a_i(t)`$ (5)
$``$ $`y(t)\mathrm{\Gamma }\mathrm{tanh}[y(t)]`$
where the approximation in the last equation relies on the law of large numbers for $`N1`$. Eq. (5) is a dynamical system. The point $`y^0=0`$ is stationary, but it is easy to see that it is only stable for $`\mathrm{\Gamma }<\mathrm{\Gamma }_c=2`$. For $`\mathrm{\Gamma }>2`$, a cycle of period $`2`$ arises, as shown in Fig. 1. This has dramatic effects on the optimality of the system. Indeed, let $`\pm y^{}`$ be the two values taken by $`y(t)`$ in this cycle333$`\pm y^{}`$ are the two non-zero solutions of $`2y=\mathrm{\Gamma }\mathrm{tanh}(y)`$.. Since $`y(t+1)=y(t)=\pm y^{}`$ we still have $`A=0`$ and hence $`H=0`$. On the other hand $`\sigma ^2=N^2y_{}^{}{}_{}{}^{2}`$ is of order $`N^2`$, which is even worse than the symmetric Nash equilibrium $`\pi _i=1/2`$ for all $`i`$, where $`\sigma ^2=N`$.

Hence, one finds again a transition from $`\sigma ^2N`$ to $`\sigma ^2N^2`$ when the learning rate is too large.

#### Sophisticated agents $`\eta >0`$

It is easy to check that with $`\eta >0`$, following the same steps as in the previous section, the learning dynamics of agents minimize the function

$$H_\eta =A^2\eta \underset{i=1}{\overset{N}{}}m_i^2,$$
(6)
Since $`H_\eta `$ is a harmonic function, $`H_\eta `$ attains its minima on the boundary of the domain $`[1,1]^N`$. In other words, $`m_i=\pm 1`$ for all $`i`$ which means that agents play pure strategies $`a_i=m_i`$. The stable states are optimal Nash equilibria for $`N`$ even. By playing pure strategies agents minimize the second term of $`H_\eta `$. Of all corner states where $`m_i^2=1`$ for all $`i`$, agents select those with $`A=0`$ by dividing into two equal groups playing opposite actions. All these states have minimal “energy” $`H_\eta =N\eta `$. Which of these states is selected depends on the initial conditions $`\mathrm{\Delta }_i(0)`$, but this has no influence on the outcome, since $`A=0`$.

Note that the set of stable states is disconnected. Each state has its basin of attraction in the space of $`\mathrm{\Delta }_i(0)`$. The stable state changes discontinuously as $`\mathrm{\Delta }_i(0)`$ is varied. This contrasts with the case $`\eta =0`$ where Eq. (3) implies that the stationary state changes continuously with $`\mathrm{\Delta }_i(0)`$ and the set of stationary states is connected.

For $`N`$ odd, similar conclusions can be found. This can be understood by adding a further agent to a state with $`N1`$ (even) agents in a Nash equilibrium. Then $`H_\eta =(1\eta )m_N^2`$, so for $`\eta <1`$ the new agent will play a mixed strategy $`m_i=0`$, whereas for $`\eta >1`$ it will play a pure strategy. In both cases other agents have no incentive to change their position. In this case we find $`\sigma ^21`$.

It is remarkable how the addition of the parameter $`\eta `$ radically changes the nature of the stationary state. Most strikingly, fluctuations are reduced by a factor $`N`$. From a design point of view, this means that one has either to give a personalized feedback to autonomous agents, or to make them more sophisticated, for instance because they need to know the functional form of the payoff.

## 2 Public information

As each agent has an influence on the outcome of the game, the behavior of particular agent may introduce patterns that the other agents will try to exploit. For instance, if only one agent begins to think that the outcome of next game depends on some external state, such as the present weather of Oxford, and behave accordingly, then indeed, the outcome will depend on it.444This kind of self-fulfilled prophecy is found for instance in financial markets, where it is called ‘sunspot effect’. But this means that other agents can exploit this new pattern by behaving conditionally on the same state. One example of public information state family that agents may consider as relevant is the past winning choices, for instance a window of size $`M`$ of past outcomes . Each such state can be represented by a bit-string of size $`M`$, hence there are $`2^M`$ possible states of the world. This kind of state has a dynamics of its own: it diffuses on a so called De Bruijn Graph . Another state dynamics consists simply in drawing at random the state at time $`t`$ from some ensemble  of size $`P`$ (e.g. $`P=2^M`$). All exact results below are obtained with this setup.

### 2.1 Neural Networks

Two types of neural networks have been studied in the context of the MG . Beyond the mere academic question of how well or badly they can perform, it is worth noting that these papers were interested for the first time in interacting neural networks.

Refs  introduced simple perceptrons playing the minority game. Each perceptron $`i=1,\mathrm{},N`$ is made up of $`M`$ weights $`\stackrel{}{w}_i=(w_1^1,\mathrm{},w_1^M)`$ which are drawn at random before the game begins. The decision of network $`i`$ is $`a_i=\mathrm{sgn}(\stackrel{}{w}.\stackrel{}{\mu })`$, where $`\stackrel{}{\mu }`$ is the vector containing the $`M`$ last minority signs. The payoff was chosen to be $`a_i\mathrm{sgn}(A)`$. Neural networks are trained following the usual Hebbian rule, that is,

$$\stackrel{}{w}_i(t+1)=\stackrel{}{w}_i(t)\frac{\eta }{M}\stackrel{}{\mu }_t\mathrm{sgn}(A_t).$$
(7)
Under some simplifying assumptions, it is possible to find that the fluctuations are given by

$$\sigma ^2=N+N(N1)\left(1\frac{2}{\pi }\mathrm{arccos}\frac{K1/(N1)}{K+1}\right)$$
(8)
where $`K=\frac{\eta ^2\pi }{16}\left(1+\sqrt{1+\frac{16(\pi 2)}{\eta ^2\pi N}}\right)`$. The best efficiency, obtained in the limit $`\eta 0`$, is given by

$$\sigma ^2=N\left(1\frac{2}{\pi }\right).$$
(9)
This means that the fluctuations are at best of order $`N`$, and at worst of order $`N^2`$ when the learning rate is too high. This is likely to be corrected for neural networks with sophisticated private utility.

### 2.2 Inductive behavior

El Farol’s problem was introduced with public information and inductive behavior , but with no precise characterization of the strategy space. In most MG-inspired models, a strategy is a lookup table $`a`$, or a map, or a function, which predicts the next outcome $`a^\mu `$ for each state $`\mu `$, and whose entries are fixed for the whole duration of the game. Each agent $`i`$ has a set of $`S`$ strategies, say $`S=2`$ ($`a_{i,1}`$ and $`a_{i,2}`$), and use them essentially in the same way as before .

#### Naive agents

To each of her strategies, agent $`i`$ associate a score $`U_{i,s}`$ which evolves according to

$$U_{i,s}(t+1)=U_{i,s}(t)a_{i,s}^{\mu (t)}g[A(t)]$$
(10)
Since we consider $`S=2`$, only the difference between $`\mathrm{\Delta }_i=U_{i,2}U_{i,1}`$ matters, and

$$\mathrm{\Delta }_i(t+1)=\mathrm{\Delta }_i(t)(a_{i,2}^{\mu (t)}a_{i,1}^{\mu (t)})g[A(t)]$$
(11)
Note that now $`\mathrm{\Delta }_i`$ encodes the perception of the relative performance of the two strategies of agent $`i`$, $`\mathrm{\Delta }_i>0`$ meaning that the agent $`i`$ thinks that strategy 2 is better than strategy 1, and $`m_i`$ is the frequency of use of strategy $`2`$. As before, we consider $`\chi (x)=\mathrm{tanh}(\mathrm{\Gamma }x)`$. This kind of agents minimizes the predictability, which has now to be averaged over the public information states

$$H=\frac{1}{P}\underset{\mu =1}{\overset{P}{}}A|\mu ^2=\overline{A^2}$$
(12)
where $`\overline{Q}=_{\mu =1}^PQ^\mu `$ is a useful shortcut for the average over the states of the world. In contrast with the case with no information, $`H`$ is not always canceled by the agents. This is due to the fact that the agents are faced to $`P`$ possible states, but their control over their behavior is limited: when they switch from one strategy to another, they change their behavior potentially for all states. In fact all macroscopic quantities such as $`H/N`$ and $`\sigma ^2/N`$ depend of the ratio $`\alpha =P/N`$ , which is therefore the control parameter of the system. Solving this model is much more complex and requires tools of Statistical Physics of disordered systems . The resulting picture is that for infinite system size ($`P`$, $`N\mathrm{}`$ with $`P/N=\alpha =\mathrm{cst}`$ (see also Fig 2),

* $`H>0`$ if $`\alpha =N/P>\alpha _c=0.3374\mathrm{}`$. In this region, the system is not informationally efficient. It tends to a stationary state which is unique and stable, and does not depend either on $`\mathrm{\Gamma }`$ or on initial conditions. $`\mathrm{\Gamma }`$ is a time scale .
* $`H=0`$ when $`\alpha <\alpha _c`$. Since agents succeed in minimizing $`H`$, the question for them is what should they do? They do not known, and as a result, the dynamics of the system is very complex: it depends on initial conditions555Physicists say that it is not ergodic , and on $`\mathrm{\Gamma }`$ . Any value of the fluctuations can be obtained, from $`\sigma ^2=1`$ for very heterogeneous initial conditions $`\mathrm{\Delta }_i(t=0)`$ to $`\sigma ^2N^2`$ for $`\mathrm{\Gamma }=\mathrm{}`$ and homogeneous initial conditions, including $`\sigma ^2N`$ for $`\mathrm{\Gamma }=0`$ and any initial conditions. Two alternative theories have been proposed, one which is exact, but which has to be iterated , and another one which rests on a closed form for the fluctuations . Iterating the exact theory is hard, since the $`t`$th iteration is obtained by inverting $`t\times t`$ matrices, and one has to average of several realizations. Nevertheless, a hundred numerical iterations bring promising results .

The origin of the phase transition can easily be understood in terms of linear algebra: canceling $`H=0`$ means that $`A|\mu =0`$ for all $`\mu `$. This is nothing else than a set of $`P`$ linear equations of $`N`$ variables $`\{m_i\}`$. As the variables are bounded ($`0m_i^21`$), one needs more that $`P`$ of them, $`N=P/\alpha _c>P`$ to be precise .

In fact, the transition from low to high (anomalous) fluctuations does not occur at $`\alpha _c`$ for finite system size as it clearly appears on Fig 2. This can be traced back to a signal to noise ratio transition : the system is dynamically stable in the phase of $`H>0`$ as long as the signal to noise ratio $`H/\sigma ^2`$ is larger than $`K/\sqrt{P}`$ for some constant $`K`$. This transition is universal for naive competing agents. Hence in this kind of interacting agents systems, the ultimate cause of large fluctuations is this signal-to-noise transition and high learning rate. Sophisticated agents are not affected by this problem, as explained below.

#### Sophisticated agents

As before, a sophisticated agent is able to disentangle her own contribution from $`g(A)`$. Eq (10) becomes :

$$\mathrm{\Delta }_i(t+1)=\mathrm{\Delta }_i(t)(a_{i,1}^{\mu (t)}a_{i,2}^{\mu (t)})g(A(t)a_i(t))$$
(13)
When the payoff is linear $`g(A)=A`$, the agents also minimize the fluctuations $`\sigma ^2=A^2`$. Similarly, they end up using only one strategy, which implies that $`H=\sigma ^2`$. In this case, they cannot cancel $`A`$ for all $`\mu `$ at the same time, hence $`\sigma ^2/N>0`$. How to solve exactly this case is known in principle . ’In principle’ here means that the minimization of $`\sigma ^2`$ is hard from an technical point of view; how much harder is also a question hard to answer. A first step was done in ref. , which is able to describe reasonably well the behavior of the system. Interestingly, in this case the signal-to-noise ratio transition does not exist, as the signal is also the noise ($`H=\sigma ^2`$), hence, there is no high volatility region (see Fig. 3). Therefore, the fluctuations are again considerably reduced by introducing sophisticated agents. An important point here is that the number of stable final states $`\{m_i\}`$  grows exponentially when $`N`$ increases. Which one is selected depends on the initial conditions, but the efficiency of the final state greatly fluctuates. As the agents (and the programmer) have no clue of which one to select, the system ends up having non-optimal fluctuations of order $`N`$, as seen of Fig. 3.

## 3 Forward/reverse problems

Inductive agents minimize a world utility whose determination is the first step in solving the forward problem. Finding analytically its minimum is then possible in principle thanks to methods of Statistical Physics . The reverse problem consists in starting from a world utility $`W`$ and finding the appropriate private payoff.

### 3.1 Naive agents

The case with no information ($`P=1`$) is trivial, since $`A=0`$ in the stationary state, hence all functions $`H_{2n}=A^{2n}`$ ($`n`$ integer) are minimized by a linear payoff. When the agents have access to public information ($`P>1`$), the world utility $`W`$ given any private payoff function $`g(A)`$ is

$$W_{\mathrm{naive}}(\{m_i\})=\frac{1}{P}\underset{\mu =1}{\overset{P}{}}_{\mathrm{}}^{\mathrm{}}\frac{dx}{\sqrt{2\pi }}\mathrm{e}^{x^2/2}G\left(A|\mu (\{m_i\})+x\sqrt{D}\right)$$
(14)
where $`g(x)=\text{d}G(x)/\text{d}x`$ and $`D=\sigma ^2H=(N_im_i^2)/2`$. In other words, the agents select the set of strategy usage frequencies $`\{m_i\}`$ that minimizes $`U`$. The final state is unique and does not depend on the initial conditions. Note that in Eq (14), only powers of $`A|\mu `$ ($`\mu =1,\mathrm{},P`$) appear, which means that naive agents are only able to minimize world utility that only depend on these quantities. This implies that a phase transition always happen if the agents are naive, and even more, that it always happen at the same $`\alpha _c=0.3374\mathrm{}`$, as seen conjecture from numerical simulations in . As explained above, $`\alpha _c`$ is the point where it is algebraically possible to cancel all $`A|\mu `$ . The above theory also means that the stationary state depends only weakly on the payoff, which can be seen numerically by comparing the $`m_i`$ of a given set of agents for different payoffs.

The reverse problem is now to find $`g`$ given $`W`$. Let us focus on the particular example $`W=\overline{A^{2n}}`$, ($`n`$ integer). First, one determines the world utility $`W^{(2k)}`$ associated with $`g(x)=2kx^{2k1}`$, where $`k`$ is an integer,

$$W^{(2k)}=\underset{l=0}{\overset{k}{}}\left(\genfrac{}{}{0pt}{}{2k}{2l}\right)D^{kl}X_{2(kl)}H_{2l},$$
(15)
where $`X_l=\mathrm{exp}(x^2/2)x^l/\sqrt{2\pi }`$ is the $`l`$-th moment of a Gaussian distribution of unitary variance and zero average, and $`H_{2l}=\overline{A^{2l}}`$ is the $`2l`$norm of the vector $`(A|\mu )`$. Suppose now that one wishes to minimize $`W=H_{2n}`$. This can be done in principle with a linear combination of the $`W^{(2k)}`$

$$W=\overline{A|\mu ^{2n}}=\underset{k=0}{\overset{n}{}}a_kW^{(2k)}=\underset{k=0}{\overset{n}{}}a_k\underset{l=0}{\overset{k}{}}\left(\genfrac{}{}{0pt}{}{2k}{2l}\right)D^{kl}X_{2(kl)}H_{2l},$$
(16)
The condition on the $`\{a_k\}`$ is that the coefficient of $`H_{2k}`$ be 0 for $`k=0,\mathrm{},n1`$, and the coefficient of $`H_{2n}`$ be 1, that is

$$\underset{m=k}{\overset{n}{}}a_m\left(\genfrac{}{}{0pt}{}{2m}{2k}\right)D^{mk}X_{2(mk)}=01kn1$$
(17)
and $`a_n=1`$. Then the problem is solved by finding the solution of these $`n1`$ linear equations of $`a_k`$, $`k=1,\mathrm{},n1`$, and taking $`g(x)=_{k=1}^na_kx^{2k1}`$. Note that the set of the problems that naive agents can solve is of limited practical interest.

### 3.2 Sophisticated agents

Sophisticated agents have instead

$$W_{\mathrm{naive}}(\{m_i\})=\frac{1}{PN}\underset{\mu =1}{\overset{P}{}}_{\mathrm{}}^{\mathrm{}}\frac{dx}{\sqrt{2\pi }}\mathrm{e}^{x^2/2}\underset{i}{}G\left(A_i^\mu (\{m_i\})+x\sqrt{D_i}\right)$$
(18)
where $`D_i=[(N1)_{ji}m_i^2]/2`$. This case is much simpler than the previous one, as all agents end up playing only one strategy , that is, $`D_i=0`$. Therefore, in this case, if $`g(A)=2kA^{2k+1}`$,

$$W^{(2k)}=A^{2k}.$$
(19)
Interestingly, similar functions are well-studied in Statistical Physics, where they usually represent the energy of interacting magnetic moments called ”spins” ; a (classical) spin can have two values $`1`$ or $`+1`$, which is the equivalent of choosing strategy $`1`$ or $`2`$. A well-known qualitative change occurs between $`k=2`$ and $`k>2`$, where the mathematical minimization of $`W`$ is somehow less problematic; this may also be the case in such MGs. The final state is not unique, and depends on initial conditions, implying that agents cannot are not particularly good at minimizing such functions.

### 3.3 Example: agent-based optimization

Some optimization problems are so hard to solve that they have a name: they are hard, NP-hard . There is no algorithm that can find the optimum of this kind of problems in polynomial time. One of them consists in finding amongst $`N`$ either analogic or binary components the combination that is the least defective : in the problem with analogic components, one has a set of $`N`$ measuring devices; instead of $`A`$, each of them records the wrong value $`A+a_i`$ with a constant bias $`a_i`$, $`i=1,\mathrm{},N`$, drawn from a given probability function. The problem is to find a subset such that the average bias

$$ϵ\{n_i\}=\frac{|_{i=1}^Nn_ia_i|}{_{j=1}^Nn_j}$$
(20)
is minimal. Here $`n_i=0,1`$ depending on whether component $`i`$ is included in the subset. Statistical Physics shows that $`ϵ_{\mathrm{opt}}C\mathrm{\hspace{0.17em}2}^N/\sqrt{N}`$ for large $`N`$, with $`C4.6`$ (the average is over the samples). In order to find the optimal subset, one cannot do better than enumerating all the $`2^N`$ possibilities. This makes it hard to tackle such problems for $`N`$ larger than $`40`$ with nowadays computers. Agent-based optimization on the other hand needs typically $`O(N)`$ iterations and can be used with much larger samples. It is clear that one cannot expect this method to perform as well as the enumeration, still how well it perform as a function of the setup is a valuable question. Ref  compares a set of private payoffs and concludes that agent-based optimization is better than simulated annealing for short times and large samples, provided that the agents’ private utility is “aristocratic”.

Optimizing $`h=|_{i=1}^Nn_ia_i|`$ and then dividing by the number of components used in the chosen subset leads to almost optimal subsets . Hence, we can use sophisticated MG-agents in order to optimize $`h^2`$ , which plays the role of the fluctuations in the MG. The most straightforward application of the MG is to give two devices to each agents, which are their strategies. Each agent ends up playing with only one strategy. This setup constraints the use of $`N/2`$ devices in the optimal subset, and gives an error of order $`N^{1.5}`$, to be compared with the exponential decay of the optimal average error $`ϵ_{\mathrm{opt}}`$. One can unconstrain the agents by giving only one component to each agent, and letting them decide whether to include their components or not into $`ϵ`$, making the game ’grand canonical’ . This is achieved by the following score evolution

$$U_i(t+1)=U_i(t)a_i[An_i(t)a_i]$$
(21)
and $`n_i(t)=\mathrm{\Theta }[U_i(t)]`$. The $`n_ia_i`$ term makes the agents sophisticated. This gives similar results as those of ref , as indeed the Aristocrat Utility is essentially the same concept as sophisticated agents. But in any case, it minimizes the fluctuations, but does not optimize them. The resulting error $`ϵ`$ is much better with $`S=1`$ than with $`S=2`$: it decays $`N^2`$ (Fig 4). Therefore, as in the optimal case, unconstraining the problem by not fixing the number of selected components leads to much better efficiency.

At this stage, one can improve substantially the error, still remaining in the $`O(N)`$ complexity regime. First, since the agents update their behavior simultaneously, they may be unable to distinguish whether removing only one component improves the error. We can do it by hand at the end of the simulations, repeatedly. This is a kind of greedy algorithm. On average, about 1.5 components are removed. In both the $`S=2`$ and $`S=1`$ cases, this results into a large improvement (see Fig. 4), and curioulsy produces the same error, with a decay $`N^{2.3}`$. Nevertheless, the final error is still far from optimality. This illustrates how hard this optimization problem is. Much better results can be obtained by removing a group of 2, or 3 components, ad libitum, but of course, this needs much more computing resources ($`O(N^2)`$, $`O(N^3)`$, …), and eventually amounts to enumerating all possibilities.

Here is the second trick that keeps the complexity with the $`O(N)`$ regime. As mentioned, the final state depends on the initial conditions, and is often not optimal or not even near optimal. But it is still a local minimum of $`h^2`$. Therefore the idea is to do $`T`$ runs with the same set of defective devices, changing the initial condition $`U_i(t=0)`$, and to select the best run. It is a kind of simulated annealing  with zero temperature, or partial enumeration where repetition would be allowed. Interestingly, Figure 5 reports that the decay is apparently a power-law first, and then begins to saturate. For $`S=1`$, the exponent is about $`0.5`$, and $`0.4`$ for $`S=2`$; it depends weakly on $`N`$. Remarkably, the error decreases faster with $`S=1`$ agents than $`S=2`$. Note that the optimal value is at about $`10^6`$, hence, agents are far from it. This is due to the fact that the agents use too many components. Nevertheless, the improvement brought by this methods is impressive, and increases as $`N`$ increases, but cannot keep up with the exponential decay of $`ϵ_{\mathrm{opt}}`$: the difference becomes more and more abysmal. The component removal further lowers the error (same figure), and more in the $`S=2`$ that in the $`S=1`$ one. This advantage is reversed for $`T`$ large enough when $`N`$ is larger, as reported by the right panel Fig. 5).

The other optimization problem recycles binary components : one has a set of $`N`$ partially defective processors, each of them able to perform $`P`$ different operations. The manufacturing process is supposed to be fault with probability $`f`$ for each operation of each component. Mathematically, the operation $`\mu `$ of processor $`a`$ is permanently defective ($`a^\mu =1`$) with probability $`f`$ and works permanently with probability $`1f`$ ($`a^\mu =1`$). The probability that a component is working becomes vanishingly small when $`P`$ grows at fixed $`f`$. The task consists in finding a subset such that the majority of its components gives the right answer, that is,

$$\underset{i=1}{\overset{N}{}}n_ia_i^\mu >0\mathrm{for}\mathrm{all}\mu =1,\mathrm{},P$$
(22)
Surprisingly, the fraction $`\varphi `$ of samples in which a perfectly working subset of components can be found increases very quickly as $`N`$ grows at fixed $`P`$ and $`f`$  (see also fig. 6). Finding a subset that perfectly works is an easy problem when it is possible, but finding the one which has the least components is a hard problem . By contrast with the minimization of fluctuations, here one wishes to maximize $`A`$ given $`\mu `$, that is, the predictability $`H`$. Since all the agents eventually use only one strategy in majority games , $`H=\sigma ^2`$, hence, the fluctuations $`\sigma ^2`$ are also maximized: naive agents are also sophisticated in this case. A simple majority game does not favor any particular sign of $`A^\mu `$ a priori. However, if $`f1/2`$ the sign $`+`$, hence mostly working combinations, are favored. In practice, a majority game payoff increase is $`ag(A)`$ instead of $`ag(A)`$ as in minority games, which means that here one has

$$U_i(t+1)=U_i(t)+a_i^{\mu (t)}A(t)$$
(23)
Majority games with $`S=1`$ turn out to be better than those agents with $`S=2`$, as shown in Fig. 6, where the results of enumeration are also displayed. As the problem to find a working subset is easy for $`N`$ large enough, the agents are successful.

## 4 Conclusions

The efficiency of Minority Games seems to be universal with respect to agents’ learning rate: if the latter is too high, anomalous fluctuations, hence small efficiency arise. However, these are totally suppressed if the agents are sophisticated, who can optimally coordinate if there is no public information. An unexplored issue is what happens with neural networks taking into account their impact on the game. Based on this ‘universality’, it would be tempting to study neural networks with the sophisticated payoff.

The study of forward/reverse problems showed the limitations of agent-based optimization in hard cases, which leaves the interesting open question of how to improve the overall performance, and how the setup of agent-based models can and must be tuned for individual cases.

I am grateful to J.-P. Garrahan, N. F. Johnson, M. Marsili, D. Sherrington and Yi-Cheng Zhang for numerous discussions. This work has been supported by EPSRC.