\section{Introduction}

It is an experimental fact \cite{data} that within measurement errors
the observed neutrino mixing matrix is compatible with
the so called tri-bimaximal (TB) form, introduced by Harrison, Perkins
and Scott (HPS) \cite{hps}. The best measured neutrino mixing angle $\theta_{12}$ is just about 1$\sigma$ below the HPS value $\tan^2{\theta_{12}}=1/2$, while the other two angles are well inside the 1$\sigma$ interval \cite{data}. In a series of papers \cite{ma1,ma2,OurTriBi,Mod,us3} it has been
pointed out that a broken flavour symmetry based on the discrete
group $A_4$ appears to be particularly suitable to reproduce
this specific mixing pattern as a first approximation.
Other
solutions based on alternative discrete or  continuous flavour groups have
also been considered \cite{continuous,others}, but the $A_4$
models have a very economical
and attractive structure, e.g. in terms of group representations and of field content.
 In most of the models $A_4$ is accompanied by additional symmetries, either continuous like U(1) or discrete like $Z_N$, which are necessary to eliminate unwanted couplings, to ensure the needed vacuum alignment and to reproduce the observed mass hierarchies.
In this way one can construct natural models where the corrections to TB mixing can be evaluated in a well defined expansion.

Recently much attention has been devoted to the question whether a model for HPS mixing in the neutrino sector can be  suitably extended to also successfully describe the observed pattern of quark mixings and masses and whether this more complete framework can be made compatible with (supersymmetric (SUSY)) SU(5) or SO(10) grand unification. Early attempts of extending models based on $A_4$ to quarks  \cite{ma1.5,Mod} and to construct grand unified versions \cite{maGUT}  so far have not been completely satisfactory, e.g. do not offer natural mechanisms for mass hierarchies and for the vacuum alignment. A direct extension of the $A_4$ model to quarks leads to the identity matrix for $V_{CKM}$ in the lowest approximation, which at first looks promising. But the corrections
 to it turn out to be strongly constrained by the leptonic sector, because lepton mixings are nearly TB, and are proven to be too small to accommodate the observed quark mixing angles \cite{Mod}. Also, the quark classification adopted in these models is not compatible with $A_4$ commuting with SU(5) \footnote{In ref. \cite{KM} an $A_4$ model compatible with the Pati-Salam group SU(4)$\times$ SU(2)$_L \times$ SU(2)$_R$ has been presented.}.
 Due to this, larger discrete groups are considered for the description of quarks  and for grand unified versions with approximate TB mixing in the lepton sector. A particularly appealing set of models is based on the discrete group $T'$, the double covering group of $A_4$ \cite{T'0}. In ref. \cite{T'} a viable description was obtained, i.e. in the leptonic sector the predictions of the $A_4$ model are reproduced, while the $T'$ symmetry plays an essential role for reproducing the pattern of quark mixing. But, again, the classification adopted in this model is not compatible with grand unification. Unified models based on the discrete groups $T'$ \cite{CM}, $S_4$ \cite{S4} and $\Delta(27)$  \cite{27} have been
discussed. Several models using the smallest non-abelian symmetry
$S_3$ (which is isomorphic to $D_3$) can also be found in the recent literature \cite{S3}.

In conclusion, the group $A_4$ is considered by most authors to be too
limited to also describe quarks and to lead to a grand unified
description. In the present work we show that this negative attitude
is not justified and that it is actually possible to construct a
viable model based on $A_4$ which leads to a grand
unified theory (GUT) of quarks and leptons with TB mixing
for leptons. At the same time our model offers an example of an
extra dimensional GUT in which a description of all fermion masses
and mixings is attempted. The model is natural, since most of the
small parameters in the observed pattern of masses and mixings as well
as the necessary vacuum alignment are  justified by the symmetries of
the model. For this, it is sufficient to enlarge the  $A_4$ flavour
symmetry by adding a U(1) of the Froggatt-Nielsen type and to suitably
modify and extend the classification under the flavour group so that
finally all fermions transform in an SU(5) compatible way.
 In addition, a $Z_3$ symmetry must be assigned to the fields
of the model which is, however, flavour-independent. The
formulation of SU(5) in extra dimensions has the usual advantages of
avoiding large Higgs representations to break SU(5) and of solving the
doublet-triplet splitting problem. A further ingredient of the model is a U(1)$_R$
symmetry which contains the discrete $R$-parity as a
subgroup. A see-saw realization
in terms of an $A_4$ triplet of right-handed neutrinos $N$ ensures the
correct ratio of light neutrino masses with respect to the GUT
scale. In the present model extra dimensional effects directly
contribute to determine the flavour pattern, in that the two lightest
tenplets $T_1$ and $T_2$ are in the bulk (with a doubling $T_i$ and
$T'_i$, $i=1,2$ to ensure the correct zero mode spectrum), whereas the
pentaplets $F$ and $T_3$ are on the brane. The hierarchy of quark and
charged lepton masses and of quark mixings is determined by a
combination of extra dimensional suppression factors for the first two
generations and of the U(1) charges, while the neutrino mixing angles
derive from $A_4$. The choice of the transformation properties of the two
 Higgses $H_5$ and $H_{\bar{5}}$ is also crucial. They are chosen to transform
as two different $A_4$ singlets
$1$ and $1'$. As a consequence, mass terms for the Higgs colour
triplets are  not directly allowed \footnote{Even after $A_4$ breaking they are
forbidden at all orders by the U(1)$_R$ symmetry.} and their masses are
introduced by orbifolding, \`{a} la Kawamura \cite{5DSU5}. Finally, in this model, proton
decay is dominated by gauge vector boson exchange giving rise to
dimension six operators. Given the relatively large theoretical
 uncertainties, the decay rate is within the present
experimental limits.

The resulting model is shown to be directly compatible with approximate TB mixing for leptons
as well as with a realistic pattern of fermion masses and of quark mixings in a SUSY SU(5)
framework.

\section{The Model}

We consider a SUSY GUT based on SU(5) in 4+1 dimensions. Leaving aside extra dimensional effects for a moment, from the four-dimensional (4D) point of view matter fields are chiral supermultiplets transforming
as $10$, $\bar{5}$ and $1$ under SU(5). Part of the flavour symmetry is related to the discrete group $A_4$, whose properties
are summarized, for instance, in section 2 of ref. \cite{Mod}, whose conventions are adopted here.
The three $\bar{5}$ and the three singlets (corresponding to the right-handed neutrinos) are grouped into $A_4$ triplets $F$ and $N$, while
the tenplets $T_1$, $T_2$ and $T_3$ are assigned to $1''$, $1'$ and $1$ singlets of $A_4$, respectively (see table 1).
The Higgs chiral supermultiplets that break the electroweak symmetry are $H_5$ and $H_{\bar{5}}$,
transforming as $(5,1)$ and $(\bar{5},1')$ under SU(5)$\times A_4$. We also consider a set of flavon
supermultiplets, all invariant under SU(5), that break the $A_4$ symmetry: two triplets $\varphi_T$ and
$\varphi_S$ and two singlets $\xi$ and $\tilde{\xi}$. The alignment of their vacuum expectation values (VEVs) along appropriate directions in
flavour space will be the source of TB lepton mixing. It is well-known that, for this to work,
each triplet should mainly contribute to the mass generation of a specific sector. At the leading order and after
spontaneous $A_4$ breaking, $\varphi_S$, $\xi$ and $\tilde{\xi}$ should give mass to neutrinos only, while $\varphi_T$
gives mass to charged leptons and to down quarks. This separation
can be realized with the help of an additional spontaneously broken
$Z_3$ symmetry under which $N$, $F$, $T_i$, $H_{5,\bar{5}}$, $\varphi_S$, $\xi$ and $\tilde{\xi}$ are multiplied by $\omega=\exp(i2\pi/3)$, while
$\varphi_T$ is left invariant. The generation of the up quark masses as well as the
quark mixings will be discussed below.

The breaking of the grand unified symmetry is a potential source of serious problems, like those related to the doublet-triplet splitting
and to proton decay. One of the most efficient mechanisms to break SU(5) and avoid these problems is the one based on compactification of extra spatial dimensions \cite{5DSU5}.
The simplest setting is an SU(5) gauge invariant five-dimensional (5D) theory where the fifth dimension is compactified on a circle $S^1$ of radius $R$.
The gauge fields, living in the whole 5D space-time, are assumed to be periodic along the extra dimension only up to
a discrete parity transformation $\Omega$ such that the gauge fields of the SU(3)$\times$SU(2)$\times$U(1) subgroup are periodic,
while those of the coset SU(5)/SU(3)$\times$SU(2)$\times$U(1) are antiperiodic. Only the gauge vector bosons of SU(3)$\times$SU(2)$\times$U(1)
possess a zero mode. Those of SU(5)/SU(3)$\times$SU(2)$\times$U(1)
form a Kaluza-Klein tower starting at the mass level
$1/R$. From the viewpoint of a 4D observer, these boundary conditions effectively break SU(5) down to the Standard Model (SM) gauge group,
at a GUT scale of order $1/R$. The transformation $\Omega$ is an automorphism of the SU(5) algebra, so that the whole construction
can be carried out within an SU(5) invariant formalism.
An important advantage of this mechanism is that it provides a simple solution to the doublet-triplet splitting problem.
The parity $\Omega$ is consistently extended to the Higgs multiplets $H_5$ and $H_{\bar 5}$, also assumed to live in the whole 5D space, in such a way that the electroweak doublets are periodic,
whereas the colour triplets are antiperiodic. In this way we have zero modes only for the doublets and the lightest colour triplets get masses of order $1/R$.
Notice that, if the model is supersymmetric as in the case under discussion here, we have an effective 4D $N=2$ SUSY, induced by the
original $N=1$ SUSY in five dimensions. To reduce $N=2$ down to $N=1$ it is convenient to compactify the fifth dimension on the orbifold
$S^1/Z_2$ rather than on the circle $S^1$. The orbifold projection eliminates all the zero modes of the extra states belonging to $N=2$ SUSY
and also those of the fifth component of the gauge vector bosons. The zero modes we are left with are the 4D gauge bosons of the
SM, two electroweak doublets and their $N=1$ SUSY partners. To complete the solution of the doublet-triplet splitting problem, we should also forbid
a large mass term $H_{5} H_{\bar 5}$, which would otherwise lift the doublet masses.
 As will be explained below, this is automatically guaranteed by
the U(1)$_R$ symmetry that we specify in table 1.

For the gauge vector bosons and the Higgses $H_{5}$ and $H_{\bar 5}$ we will adopt this setup, which is described in detail in refs. \cite{5D}.
For the remaining fields we have much more freedom \cite{5D,5Dfreedom}. Indeed the orbifold $S^1/Z_2$ corresponds to a segment where the fifth coordinate $y$ runs from 0 to $\pi R$.
The boundaries of the segment determine two 4D slices of the original 5D space-time. When boundary conditions are consistently defined for the local parameters
of SU(5) gauge transformations, we find that such transformations are generically non-vanishing only in the bulk and at $y=0$. At the opposite endpoint
of the segment, $y=\pi R$, the only gauge transformations that are different from zero are those of the SM. Therefore we have three qualitatively different possible
locations for the remaining fields: in the bulk, at the SU(5) preserving brane $y=0$, or at the SU(5) breaking brane $y=\pi R$. We choose to put the two tenplets $T_1$ and $T_2$ of the first and second family in the bulk. As explained in ref.  \cite{5D, 5Dfreedom} to obtain the correct zero mode spectrum with intrinsic parities compatible with symmetry and orbifolding, one must introduce two copies of each multiplet with opposite parity $\Omega$ in the bulk.
Therefore $T_{1,2}$ is a short notation for the copies $T_{1,2}$ and $T_{1,2}'$. The zero modes of $T_{1,2}$ are the SU(2) quark doublets $Q_{1,2}$,
while those of $T_{1,2}'$ are $U_{1,2}^c$ and $E_{1,2}^c$. All remaining $N=1$ supermultiplets are assigned to the SU(5) preserving brane at $y=0$.
\\[0.2cm]
\begin{table}[h]
\begin{center}
\begin{tabular}{|c||c|c|c|c|c||c|c||c|c|c|c|c||c|c|c|}
\hline
{\tt Field}& $N$& $F$ & $T_1$ & $T_2$ & $T_3$ & $H_5$ & $H_{\bar 5} $ &
$\varphi_T$ & $\varphi_S$ & $\xi,~\tilde{\xi}$ & $\theta$& $\theta''$  & $\varphi_0^T$ & $\varphi_0^S$ & $\xi_0$ \\
\hline
SU(5) & $1$& $\bar{5}$ & $10$ & $10$ & $10$ & $5$ & $\bar{5}$ &
$1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ \\
\hline
$A_4$ & $3$& $3$ & $1''$ & $1'$ & $1$ & $1$ & $1'$ &
$3$ & $3$ & $1$ & $1$ & $1''$ & $3$ & $3$ & $1$ \\
\hline
U(1) & $0$& $0$ & $3$ & $1$ & $0$ & $0$ & $0$ &
$0$ & $0$ & $0$ & $-1$ & $-1$ & $0$ & $0$ & $0$ \\
\hline
$Z_3$ & $\omega$& $\omega$ & $\omega$ & $\omega$ & $\omega$ & $\omega$ & $\omega$ &
$1$ & $\omega$ & $\omega$ & $1$ & $1$ & $1$ & $\omega$ & $\omega$ \\
\hline
U(1)$_R$ & $1$& $1$ & $1$ & $1$ & $1$ & $0$ & $0$ &
$0$ & $0$ & $0$ & $0$ & $0$ & $2$ & $2$ & $2$ \\
\hline
\end{tabular}
\end{center}
\caption{Fields and their transformation properties under SU(5), $A_4$, U(1), $Z_3$ and U(1)$_R$. $T_1$ and $T_2$ come in two replicas with the same quantum numbers, except for the intrinsic parity $\Omega$. For simplicity, we only show one of them in the table.}
\end{table}
\vspace{0.2cm}

An interesting feature of the 5D setup is the automatic suppression of the Yukawa couplings for the fields living in the bulk.
Indeed, a bulk field $B$ and its zero mode $B^0$ are related by:
\begin{equation}
B=\frac{1}{\sqrt{\pi R}} B^0+...
\end{equation}
where dots stand for the higher modes. This expansion produces a suppression factor
\begin{equation}
s\equiv\displaystyle\frac{1}{\sqrt{\pi R \Lambda}}<1~~~.
\label{vsup}
\end{equation}
Thereby, $\Lambda$ denotes the ultraviolet cut-off. Such a suppression factor enters the Yukawa couplings depending on the field $B^0$.
As a result, the hierarchies among the charged fermion masses are partly
due to the geometrical dilution of the Yukawa couplings involving $T_{1,2}$. However this dilution cannot account for all the observed hierarchies
and, to achieve a realistic mass spectrum, we also exploit the Froggatt-Nielsen mechanism.
The tenplets $T_1$ and $T_2$ are charged under a U(1) flavour group, spontaneously broken by the VEVs of two fields
$\theta$ and $\theta''$ both carrying U(1) charges $-1$. The elements of the charged fermion mass matrices are
provided by higher-dimensional operators with powers of $\theta$ and $\theta''$ balancing the U(1) charge of the relevant
combination of matter fields. Indeed, we need two fields, $\theta$ and $\theta''$, in order to reproduce a realistic pattern of
quark masses and mixing angles. Under $A_4$, $\theta$ is invariant, while $\theta''$ transforms as
$1''$.
All this is summarized in table 1.

Notice that, once we have introduced all the fields with the quantum numbers displayed
in table 1, there will be no contribution coming from colour triplet exchange to the dangerous dimension five operator that induces proton decay
in SUSY theories. Actually that operator is strictly forbidden as long as the U(1)$_R$ symmetry remains unbroken.
Indeed, the superpotential  of the effective $N=1$ SUSY should have U(1)$_R$ charge $+2$, to compensate the $R$-charge $-2$ coming
from the Grassmann integration measure $d^2\theta$. With the $R$ assignment in table 1, all superpotential couplings bilinear in the matter fields
$N$, $F$ and $T$ have $R$-charge $+2$ and are allowed. At the same time dangerous operators are forbidden. First of all these include
the mass term $H_5 H_{\bar 5}$, that would spoil the solution to the doublet-triplet splitting problem. Moreover, since U(1)$_R$ contains
the discrete $R$-parity, also all renormalizable baryon and lepton number violating operators, such as $F H_5$ and $F F T$, are not allowed.
Finally, the dimension five operator $FTTT$, leading to proton decay, has $R$-charge $+4$ and
 therefore is absent.
As discussed in detail in ref. \cite{Mod} and briefly recalled in section 4, the U(1)$_R$ symmetry plays also an important role in the dynamics that selects the correct vacuum of the
theory, which is a crucial feature to reproduce nearly TB mixing in the lepton sector. The U(1)$_R$ symmetry is a remnant of the SU(2)$_R$ symmetry of the
$N=2$ SUSY bulk action, before compactification. By reducing $N=2$ down to $N=1$ the orbifold projection breaks SU(2)$_R$ down to U(1)$_R$.
Eventually, after the inclusion of $N=1$ SUSY breaking effects, the U(1)$_R$ symmetry will be broken down to the discrete $R$-parity, at the low energy scale $m_{SUSY}$.
The operator $FTTT$ might be generated, but with a highly suppressed coupling of the kind $(m_{SUSY}/\Lambda)^n/ \Lambda$, $n>0$.
Therefore, the leading contribution
to proton decay comes from gauge vector boson exchange and the corresponding proton decay rate is typically small enough, though suffering from considerable uncertainties \cite{5Dpdecay}.

\section{Fermion Masses}
The $N=2$ SUSY invariance is broken down to $N=1$ by the orbifold projection, but it still forbids 5D superpotential couplings. These couplings should be strictly
localized at one of the two branes. By choosing the brane at $y=0$, the brane action reads:
\begin{equation}
\int d^4x\int_0^{\pi R} dy \int d^2\theta~ w(x) \delta(y)+h.c.=\int d^4x \int d^2\theta~ w(x) +h.c.~~~.
\end{equation}
The superpotential $w$, which can be expressed in terms of $N=1$ superfields, can be decomposed into several parts:
\begin{equation}
w=w_{up}+w_{down}+w_{\nu}+w_d+...~~~.
\label{superw}
\end{equation}
The first three contributions in eq. (\ref{superw}) give rise to fermion masses
after $A_4$, U(1) and electroweak symmetry breaking. They are of the form:
\begin{eqnarray}
w_{up}&=&
\frac{1}{\Lambda^{1/2}} H_5 T_3 T_3+
\frac{{\theta''}}{\Lambda^2} H_5 T_2 T_3 +
\frac{{\theta''}^2}{\Lambda^{7/2}} H_5 T_2 T_2  +  \frac{\theta{\theta''}^2}{\Lambda^4} H_5 T_1 T_3 \nonumber\\
&+& \frac{{\theta}^4}{\Lambda^{11/2}} H_5 T_1 T_2 +
\frac{{\theta}{\theta''}^3}{\Lambda^{11/2}} H_5 T_1 T_2 +
\frac{{\theta}^{5}{\theta''}}{\Lambda^{15/2}} H_5 T_1 T_1
+ \frac{\theta^2{\theta''}^{4}}{\Lambda^{15/2}} H_5 T_1 T_1
\label{wup}
\end{eqnarray}
\begin{eqnarray}
w_{down}&=&
\frac{1}{\Lambda^{3/2}} H_{\bar 5} (F \varphi_T)''  T_3+
\frac{\theta}{\Lambda^3} H_{\bar 5} (F \varphi_T)' T_2 +
\frac{\theta^3}{\Lambda^5} H_{\bar 5} (F \varphi_T)  T_1+\frac{{\theta''}^3}{\Lambda^5} H_{\bar 5} (F \varphi_T)  T_1 \nonumber\\
&+&
\frac{{\theta''}}{\Lambda^3} H_{\bar 5} (F \varphi_T)''  T_2 +
\frac{\theta^2 {\theta''}}{\Lambda^5} H_{\bar 5} (F \varphi_T)'   T_1 +
\frac{\theta{\theta''}^2}{\Lambda^5} H_{\bar 5} (F \varphi_T)''  T_1 +...~~~,
\label{wdown}
\end{eqnarray}
where dots stand for higher-dimensional operators.
In both, $w_{up}$ and $w_{down}$, the dimensionless coefficients of each independent operator have been omitted, for notational simplicity.
They are not predicted by the flavour symmetry, though they are all expected to be of the same order.
The powers of the cut-off $\Lambda$ are determined by the dimensionality of the various operators, by recalling that brane and bulk superfields have mass dimensions 1
and 3/2, respectively. Some combinations of matter fields, as for instance $T_1 T_2$ in $w_{up}$, appear several times, but with the same cut-off suppression.
Provided $\theta$ and $\theta''$ develop VEVs of similar size, the corresponding contributions to the charged fermion mass matrices will be of the same order.
The bulk matter supermultiplets $T_1$ and $T_2$ come in two copies and, to keep our notation compact, the previous formulae do not contain all possible terms originating from such a doubling.
For instance, $F_1 T_2$ stands for both combinations $F_1 T_2$ and $F_1 T_2'$,  which are suppressed by the same
power of $\Lambda$, but can differ by order-one relative weights.  It is important to keep this point in mind, since it allows to escape the too rigid mass
relations between the first two generations of charged leptons and down quarks  predicted by the minimal SU(5) GUT.

Neutrinos have both Dirac and Majorana mass terms, induced by:
\begin{equation}
w_{\nu}=\frac{y^{D}}{\Lambda^{1/2}} H_5 (N F)+(x_a \xi +\tilde{x}_a \tilde{\xi})(NN)+x_b (\varphi_S NN)~~~,
\label{wnu}
\end{equation}
where $\tilde{\xi}$ is defined as the combination of the two independent $\xi$-type fields
 which has a vanishing VEV. Therefore, it does not contribute to the
neutrino masses.

The last term in eq. (\ref{superw}), $w_d$, is responsible for the alignment of the flavon fields $\varphi_T$,
$\varphi_S$, $\xi$ and $\tilde{\xi}$. The fields $\theta$ and $\theta''$ get VEVs from the minimisation
of the D-term of the scalar potential. We will discuss these issues in the next section.
For the time being we assume that the scalar components of the supermultiplets acquire VEVs according to
the following scheme:
\begin{eqnarray}
\displaystyle\frac{\langle \varphi_T \rangle}{\Lambda}=(v_T,0,0)~~~,&
\displaystyle\frac{\langle \varphi_S \rangle}{\Lambda}=(v_S,v_S,v_S)~~~,&
\displaystyle\frac{\langle \xi \rangle}{\Lambda}=u~~~,\nonumber\\
\displaystyle\frac{\langle \theta \rangle}{\Lambda}=t~~~,&
\displaystyle\frac{\langle \theta'' \rangle}{\Lambda}=t'' ~~~.&
\label{align}
\end{eqnarray}
The Higgs multiplets live in the bulk and what matters for the Yukawa couplings are the values of the VEVs at $y=0$:
\begin{equation}
\langle H_5(0) \rangle=\displaystyle \frac{v_u^0}{\sqrt{\pi R}}~~~,~~~~~~~~~~ \langle H_{\bar 5}(0) \rangle= \displaystyle\frac{v_d^0}{\sqrt{\pi R}}~~~,
\label{hvev}
\end{equation}
where $v_{u,d}^0$ have mass dimension 1. The electroweak scale is determined by the relation:
\begin{equation}
v_u^2+v_d^2\approx (174~{\rm GeV})^2~~~,~~~~~v_u^2\equiv\int_0^{\pi R} dy \left\vert\langle H_5(y) \rangle\right\vert^2~~~,~~~~
v_d^2\equiv\int_0^{\pi R} dy \left\vert\langle H_{\bar 5}(y) \rangle\right\vert^2~~~.
\end{equation}
Notice that the electroweak gauge boson masses depend on the 5D averages of $\vert\langle H_{5,\bar{5}}(y) \rangle\vert^2$, rather than on the values at $y=0$.
If the VEVs of $H_{5,\bar{5}}$ are constant along the fifth dimension, then $v_u^0=v_u$ and $v_d^0=v_d$.
However, if the profile of $\langle H_{5,\bar{5}}(y) \rangle$ is not flat in $y$, the parameters $v_{u,d}^0$ are less constrained.
In order to obtain $v_{u,d}^0\ne v_{u,d}$, we need some special dynamics on the $y=0$ and $y=\pi R$ branes,
that we cannot control without detailing additional features of the model, such as the breaking of the residual $N=1$ SUSY
and the generation of a non-trivial potential for the electroweak doublets. In this section we consider  $v_{u,d}^0\ne v_{u,d}$ as an open possibility and we will discuss
a possible application of it.
All the other fields have vanishing VEVs.

From these VEVs, the superpotential terms in eqs. (\ref{wup},\ref{wdown},\ref{wnu}) and the volume suppression $s$ of eq. (\ref{vsup}), it is immediate to derive the
fermion mass matrices. In the up and down quark sector we get,
up to unknown coefficients of order one for each
matrix element and by adopting the convention $\overline{f_R} m_f f_L$:
\begin{equation}
m_u=\left(
\begin{array}{ccc}
s^2 t^5 {t''}+s^2 t^2 {t''}^4
& s^2 t^4+s^2 t {t''}^3&
s t {t''}^2\\
s^2 t^4+s^2 t {t''}^3&s^2 {t''}^2& s t''\\
s t {t''}^2&s t'' & 1
\end{array}
\right) s v_u^0~~~,
\label{mu}
\end{equation}
\begin{equation}
m_d=\left(
\begin{array}{ccc}
s t^3+s {t''}^3 & ... & ... \\
s t^2{t''}&s t& ...\\
s t {t''}^2& s t''& 1
\end{array}
\right) v_T s v_d^0 ~~~,
\label{md}
\end{equation}
where the dots stand for subleading contributions, that will be fully discussed in section 5.
Here we explicitly see the interplay between the volume dilution and the Froggatt-Nielsen mechanism, to
 achieve the hierarchical pattern
of the quark mass matrices. Realistic values of quark mass ratios and mixing angles are obtained by assuming
\begin{equation}
t\approx t''\approx s\approx O(\lambda)~~~~\mbox{with}~~~~\lambda\equiv 0.22~~~.
\label{ttpr_order}
\end{equation}
Indeed, with this choice we obtain
\begin{equation}
m_u=\left(
\begin{array}{ccc}
\lambda^8& \lambda^6& \lambda^4\\
\lambda^6& \lambda^4& \lambda^2\\
\lambda^4& \lambda^2& 1
\end{array}
\right) \lambda v_u^0~~~,
\label{mulam}
\end{equation}
\begin{equation}
m_d=\left(
\begin{array}{ccc}
\lambda^4 & ... & ...\\
\lambda^4& \lambda^2& ...\\
\lambda^4& \lambda^2& 1
\end{array}
\right) v_T \lambda v_d^0 ~~~.
\label{mdlam}
\end{equation}
We anticipate that, in the absence of corrections to the vacuum alignment given in eq. (\ref{align}), the dots receive contributions from highly suppressed operators.
In this case the entries 12, 13 and 23 of $m_d/(v_T v_d^0)$ would be of order $\lambda^{7}$, $\lambda^5$ and $\lambda^5$, respectively.
Since $v_T\approx O(\lambda^2)$ (see below),  $m_b/m_t\approx v_T v_d^0/v_u^0 \approx \lambda^2$ is easily reproduced by taking
$v_u^0\approx v_d^0$.
Notice that there is an overall factor $s\approx O(\lambda)$, coming from the normalization of the Higgs VEVs,
eq. (\ref{hvev}), suppressing both $m_u$ and $m_d$. In order to avoid large dimensionless coefficients, we make use of the freedom related to
the boundary values $v_{u,d}^0$ and we will assume that $v_{u,d}\approx \lambda v_{u,d}^0$. In this way, the Yukawa coupling of the top quark
is of order one and, by the patterns given in eqs. (\ref{mulam},\ref{mdlam}), also all the other couplings are of the same order.
Alternatively, if the Higgs VEVs are flat along the fifth dimension and $v_{u,d}^0=v_{u,d}$, we must assume that all Yukawa operators in $w$ have similar
couplings of order $1/\lambda$ \cite{Nomura}.
To correctly reproduce the quark mixing angle between the first and the second generation, a moderate tuning is needed in order to enhance
the individual contributions from the up and down sectors, which are both of order $\lambda^2$.

The mass matrix for the charged lepton sector is of the type:
\begin{equation}
m_e=\left(
\begin{array}{ccc}
s t^3+s {t''}^3 &s t^2{t''}&s t {t''}^2 \\
...&s t& s t'' \\
...&...& 1
\end{array}
\right) v_T s v_d^0
=\left(
\begin{array}{ccc}
\lambda^4 & \lambda^4& \lambda^4\\
...& \lambda^2&\lambda^2\\
...& ...& 1
\end{array}
\right) v_T \lambda v_d^0 ~~~.
\label{me}
\end{equation}
We observe that the minimal SU(5) relation $m_e=m_d^T$ is relaxed. Indeed, while the third column of $m_d$ exactly coincides with the
third row of $m_e$, thus implying $m_b\approx m_\tau$ at the GUT scale, the remaining entries are only equal (up to a transposition) at the level
of the orders of magnitude, since $T_{1,2}$ are doubled. This allows to evade the too rigid relations $m_\mu=m_s$ and $m_e=m_d$ of minimal SU(5). In our 5D setup these relations
hold only up to order one coefficients and acceptable values of the masses for $e$, $\mu$, $d$ and $s$ can be accommodated.

In the neutrino sector, after the fields $\varphi_S$ and $\xi$ develop their VEVs, the gauge singlets $N$ become heavy and the see-saw mechanism
takes place. The mass matrix for light neutrinos is given by:
\begin{equation}
m_\nu=
\frac{1}{3 a(a+b)}
\left(
\begin{array}{ccc}
3a+b& b& b\\
b& \displaystyle\frac{2a b+b^2}{b-a}& \displaystyle\frac{b^2-a b -3a^2}{b-a}\\
b& \displaystyle\frac{b^2-a b-3 a^2}{b-a}& \displaystyle\frac{2a b+b^2}{b-a}
\end{array}
\right) \frac{s^2 (v_u^0)^2}{\Lambda} ~~~,
\label{mnu}
\end{equation}
where
\begin{equation}
a\equiv \frac{2 x_a u}{(y^{D})^2}~~~,~~~~~~~b\equiv \frac{2 x_b v_S}{(y^D)^2}~~~.
\label{ad}
\end{equation}
The neutrino mass matrix is diagonalized by the transformation:
\begin{equation}
U^T m_\nu U ={\tt diag}(m_1,m_2,m_3)~~~,
\end{equation}
where, in units of $s^2 (v_u^0)^2/\Lambda$,
\begin{equation}
m_1=\displaystyle\frac{1}{(a+b)}~~~,~~~~~~~m_2=\displaystyle\frac{1}{a}~~~,~~~~~~~m_3=\displaystyle\frac{1}{(b-a)}
\label{numasses}
\end{equation}
and $U$ is given by
\begin{equation}
U=\left(
\begin{array}{ccc}
\sqrt{2/3}& 1/\sqrt{3}& 0\\
-1/\sqrt{6}& 1/\sqrt{3}& -1/\sqrt{2}\\
-1/\sqrt{6}& 1/\sqrt{3}& +1/\sqrt{2}
\end{array}
\right)~~~.
\label{HPSmatrix1}
\end{equation}
Note that, in the leading approximation, the model predicts the relation:
\begin{equation}
\frac{2}{m_2}=\frac{1}{m_1}-\frac{1}{m_3}~~~.
\end{equation}
 It is expected to hold up to corrections
of $O(\lambda^2)$, as will be discussed in section 5. Notice,
that in our conventions $m_i$ $(i=1,2,3)$
are in general complex numbers, so that the previous relation cannot
be used to exactly predict one physical neutrino mass in terms of the other
two ones. Nevertheless, it provides a non-trivial constraint that the neutrino
masses should obey.

To get the right solar mixing angle, we should impose $|m_2|>|m_1|$ and this requires $\cos\phi>-|z|/2$, where $z=b/a$ and $\phi$ is the phase difference
between the complex numbers $a$ and $b$. The neutrino spectrum can have
 either normal or inverted mass ordering.
If $\max(-1,-|z|/2)\le\cos\phi\le0$
the ordering is inverted, $|m_3|\le |m_1|<|m_2|$, while $|z|/2\le \cos\phi\le 1$ gives rise to a normal ordering, $|m_1|<|m_2|\le |m_3|$.
By defining
\begin{equation}
r\equiv \Delta m^2_{sol}/\Delta m^2_{atm}~~~,~~~~~~~
\Delta m^2_{sol}\equiv |m_2|^2-|m_1|^2~~~,~~~~~~~
\Delta m^2_{atm}\equiv\left\vert|m_3|^2-|m_1|^2\right\vert~~~,
\end{equation}
we find
\begin{equation}
r=\frac{|1-z|^2|z+\bar{z}+|z|^2|}{2|z+\bar{z}|}~~~,~~~~~~~~~~~z\equiv\frac{b}{a}~~~.
\label{rrr}
\end{equation}
We see that a sufficiently small $r$ requires $z$ not to far from either +1 ($\cos\phi=1$, normal hierarchy) or -2 ($\cos\phi=-1$, inverted hierarchy).
If we expand $z$ around +1, we obtain:
\begin{eqnarray}
|m_1|^2&=&\frac{1}{3}
\Delta m^2_{atm}~r+...\nonumber\\
|m_2|^2&=&\frac{4}{3}
\Delta m^2_{atm}~r+...\nonumber\\
|m_3|^2&=&\left(1+\frac{r}{3}\right)
\Delta m^2_{atm}+...\nonumber\\
|m_{ee}|^2&=&\frac{16 }{27}\Delta m^2_{atm}~r+...~~~,
\label{lospe}
\end{eqnarray}
where we have expressed the parameters in terms of $\Delta m^2_{atm}$ and $r$. Dots denote terms of order $r^2$ and $|m_{ee}|$ is the effective mass
combination controlling the violation of the total lepton number in neutrinoless double beta decay.
It is useful to estimate the cut-off $\Lambda$. We have roughly
\begin{equation}
\sqrt{\Delta m^2_{atm}}\approx \displaystyle\frac{s^2 (v_u^0)^2}{|a| \Lambda \sqrt{r}}~~~.
\end{equation}
By taking $\sqrt{\Delta m^2_{atm}}=0.05$ eV, $s^2 (v_u^0)^2=(100$ GeV$)^2$ and  $\sqrt{r}\approx 0.2$, we obtain $|a| \Lambda\approx 10^{15}$ GeV, not far from the
unification scale. For $u\approx v_{S,T}\approx \lambda^2$
 the cut-off $\Lambda$ is then above $10^{16}$ GeV.
If we expand $z$ around -2, we get:
\begin{eqnarray}
|m_1|^2&=&\left(\displaystyle\frac{9}{8}+\displaystyle\frac{r}{12}\right)
\Delta m^2_{atm}+...\nonumber\\
|m_2|^2&=&\left(\displaystyle\frac{9}{8}+\displaystyle\frac{13}{12}r\right)
\Delta m^2_{atm}+...\nonumber\\
|m_3|^2&=&\left(\displaystyle\frac{1}{8}+\displaystyle\frac{r}{12}\right)
\Delta m^2_{atm}+...\nonumber\\
|m_{ee}|^2&=&\left(\displaystyle\frac{1}{8}-\displaystyle\frac{11}{108}r\right)
\Delta m^2_{atm}+...
~~~.
\label{lospe2}
\end{eqnarray}
We now have
\begin{equation}
\sqrt{\Delta m^2_{atm}}\approx \displaystyle\frac{s^2 (v_u^0)^2}{|a|\Lambda}~~~.
\end{equation}
By repeating the previous estimate, we find $|a|\Lambda \approx 10^{14}$  GeV and $\Lambda$ slightly below $10^{16}$ GeV.

 Several remarks should be made:

 Concerning the lepton mixing, this is dominated by $U$, eq. (\ref{HPSmatrix1}). The contribution from the charged lepton sector depends
on the entries denoted by the dots in $m_e$.
Putting all the dots to zero, the charged leptons affect the lepton mixing
 through rotations of order $\lambda^4$, $\lambda^8$ and $\lambda^4$ in the 12, 13 and 23 sectors, respectively.
Operators of dimensions higher than the ones, considered so far, are strongly
suppressed and provide contributions of order $\lambda^4$ to
the mixing matrix. These are negligible, since the leading effect comes from
the modification of the vacuum structure of eq. (\ref{align}), due to higher
order terms in the scalar potential. We shall discuss this in sections 4 and 5.
 Eventually, such terms modify only slightly the TB mixing pattern.

 Apart from $w_{\nu}$ contributions to neutrino masses and mixing angles might come from higher dimensional operators, as for instance
\begin{equation}
\frac{\xi \xi F F H_5 H_5}{\Lambda^4}~~~.
\end{equation}
 However, they are completely negligible compared to those discussed above. If we forced this type of operator to be the dominant one, by eliminating
the singlets $N$ from our model, we would need a value of $\Lambda$ too small compared with the GUT scale.

Depending on the value of $z$, our model gives rise to two separate branches in the neutrino spectrum, both characterized by a nearly
TB mixing. On the first branch, $z\approx+1$, we find a spectrum with normal hierarchy, while on the second branch, $z\approx-2$, we get an inverted hierarchy.
A degenerate spectrum is actually disfavored in our construction, since
 it would require $z\ll1$ (see eq. (\ref{numasses})) which leads to $r$ close to 1/2,
 as can be read off from eq. (\ref{rrr}). This can obviously not be reconciled with the data.

In our model the possibility of normal hierarchy is somewhat more natural than the one of inverted hierarchy.
There is no reason a priori why $z$ should be close to $+1$ or to $-2$ and reproducing $r$ requires some amount of tuning.
However, such a tuning is stronger for inverted hierarchy ({\tt ih}) than for the normal one ({\tt nh}), as can be seen by
\begin{equation}
\left.\frac{d r}{d z}\right\vert_{\tt nh} \left.\frac{d z}{d
  r}\right\vert_{\tt ih}\approx -\frac{4}{3 \sqrt{3}} \sqrt{r}\approx
- 0.14~~~.
\end{equation}
 The derivatives are
computed at the relevant value of $z$ in each case and $r$ is the
experimental value. Moreover the solution with a normal hierarchy has a domain of validity in energy larger by a factor of $1/\sqrt{r}\approx 5.6$
and extends beyond $10^{16}$ GeV.
In the normal hierarchy solution we find with the help of  eq. (\ref{lospe})
\begin{equation}
\sum_i |m_i|\approx (0.06 - 0.07)~{\rm eV}~~~~~~~~~\mbox{and}~~~~~~~~|m_{ee}|\approx 0.007~{\rm eV}~~~~~.
\end{equation}
It is interesting to see that $|m_{ee}|$ is close to the upper limit of the range expected in the normal hierarchy case, being not too far from
the aimed for sensitivity of the next generation of neutrinoless double beta decay experiments, $0.01$ eV.
This is partly attributed to the fact that $|m_1|\approx 0.005$ is different from zero and in part to the absence of a negative interference
with the $m_3$ contribution, as $\theta_{13}=0$.

\section{Vacuum Alignment}

Here we discuss the minimisation of the scalar potential, in order to justify the VEVs assumed in the previous section. We work in the limit
of exact SUSY. This will not allow us to analyse the electroweak symmetry breaking induced by $H_{5}$ and $H_{\bar 5}$, whose VEVs
are assumed to vanish in first approximation. Indeed all the VEVs we are interested in here,
 i.e. those of the flavon fields $\varphi_{S,T}$, $\xi$, $\tilde{\xi}$,
$\theta$ and $\theta''$, are relatively close in magnitude to the cut-off $\Lambda$ and therefore much larger than the electroweak scale, which will be consistently
neglected.
Moreover we work at leading order in the parameter $1/\Lambda$, that is we keep only the lowest dimensional operators in the superpotential
shown in the previous section. Subleading effects will be discussed
 later on. All the multiplets but the flavon ones are assumed to have vanishing
VEVs and set to zero for the present discussion.
We regard the U(1) Froggatt-Nielsen flavour symmetry as local. Since the field content displayed in table 1 is anomalous under the U(1),
we need additional chiral multiplets to cancel the anomaly. These multiplets can be chosen vector-like with respect to SU(5), so that they only contribute
to the U(1) anomaly. Here we do not need to specify these fields, but we must
 presume that they do not acquire a VEV.
Within these assumptions the relevant part of the scalar potential of the model is given by the sum of
 the F-terms and of a D-term:
\begin{equation}
V=V_F+V_D~~~,
\end{equation}
\begin{equation}
V_F=\sum_i\left\vert\frac{\partial w}{\partial\varphi_i}\right\vert^2~~~,
\end{equation}
where $\varphi_i$ stands for the generic chiral multiplet. Only the last term in eq. (\ref{superw}), $w_d$, contributes to the VEVs we are looking for.
It is given by:
\begin{eqnarray}
w_d&=&M (\varphi_0^T \varphi_T)+ g (\varphi_0^T \varphi_T\varphi_T)\nonumber\\
&+&g_1 (\varphi_0^S \varphi_S\varphi_S)+
g_2 \tilde{\xi} (\varphi_0^S \varphi_S)+
g_3 \xi_0 (\varphi_S\varphi_S)+
g_4 \xi_0 \xi^2+
g_5 \xi_0 \xi \tilde{\xi}+
g_6 \xi_0 \tilde{\xi}^2~~~~.
\nonumber
\end{eqnarray}
Since also the terms in $w_d$ have to have $R$-charge +2, we introduce additional
gauge singlets, so called driving fields, $\varphi_{0}^{T}$, $\varphi_{0}^{S}$ and
$\xi_{0}$ with $R$-charge +2 (see table 1). Note that therefore all terms in $w_d$ are linear
in these fields. Note further that due to U(1) invariance neither the multiplet
$\theta$, nor the multiplet $\theta''$ is contained in $w_d$.
 Moreover the D-term $V_D$ does not depend on $\varphi_{S,T}$,
  $\xi$, $\tilde{\xi}$, which are all singlets under the (gauged) U(1).
The expression of $w_d$ and the minimisation procedure are exactly as
described in ref. \cite{Mod} and leads to the result anticipated in
the previous section:
\begin{eqnarray}\nonumber
&&\langle\varphi_T\rangle=(v_T,0,0)\Lambda~~~,~~~~v_T\Lambda=-\displaystyle\frac{3M}{2g}~~~,\\ \nonumber
&&\langle\varphi_S\rangle=(v_S,v_S,v_S)\Lambda~~~,~~~~v_S=\displaystyle\frac{\tilde{g}_4}{3 \tilde{g}_3} u~~~,\\ \nonumber
&&\langle\xi\rangle=u\Lambda~~~,\\
&&\langle\tilde{\xi}\rangle=0
\label{sols}
\end{eqnarray}
with $u$ undetermined and $g_3\equiv 3\tilde{g}_3^2$ , $g_4\equiv -\tilde{g}_4^2$. In the following
 we take $v_T$, $v_S$ and $u$ to be of $O(\lambda^2)$. This order of magnitude is indicated by the observed ratio of up and down or charged lepton masses, by the scale of the light neutrino masses and is
 also compatible with the bounds on the deviations from TB mixing for leptons.

The D-term is given by:\footnote{Note that $\vert\theta''\vert^2$ is a singlet under $A_4$,
 because $\theta''\sim1''$ and $\theta''^*\sim1'$ under $A_4$.}
\begin{equation}
V_D=\frac{1}{2}(M_{FI}^2- g_{FN}\vert\theta\vert^2-g_{FN}\vert\theta''\vert^2+...)^2
\end{equation}
where $g_{FN}$ is the gauge coupling constant of U(1) and $M_{FI}^2$ denotes the contribution of the Fayet-Iliopoulos term. We have omitted the SU(5) contribution to the D-term, whose VEV is
 zero.
There are SUSY minima such that $V_F=V_D=0$. The vanishing of $V_D$
requires
\begin{equation}
g_{FN}\vert\theta\vert^2+g_{FN}\vert\theta''\vert^2=M_{FI}^2~~~.
\end{equation}
If the parameter $M_{FI}^2$ is positive, the above condition
determines a non-vanishing VEV for a combination of $\theta$ and
$\theta''$. Here we assume that the VEVs fulfil $t$, $t'' \sim O(\lambda)$
 according to eqs. (\ref{align},\ref{ttpr_order}). The different order of $t$, $t''$ versus $v_T$, $v_S$ and $u$
can be attributed to the different couplings and mass parameters in $V_D$ and $V_F$.

Finally, we discuss the subleading corrections to the vacuum alignment.  As already noticed
above, the fields $\theta$ and ${\theta}''$ cannot couple to the flavon fields, since the flavons $\varphi_T$,
$\varphi_S$, $\xi$, $\tilde{\xi}$, $\varphi ^T _0$, $\varphi ^S _0$ and $\xi _0$ are not charged under the U(1)
symmetry, responsible for the charged fermion mass hierarchy. Therefore, the subleading effects in the potential
 arise from terms made up of one driving field and three fields $\varphi_T$, $\varphi_S$, $\xi$ and $\tilde{\xi}$.
They induce shifts in the VEVs shown above
and thereby influence the mass matrices, as discussed in the next section. Since the flavon field content of this model is essentially the
same as the one in ref. \cite{Mod}, not only the renormalizable part of $w_d$ coincides, but also the
subleading terms are the same. Hence, we do not need to repeat this discussion and we only state the results found there. The shifted VEVs are
\begin{eqnarray}\nonumber
\langle\varphi_T\rangle/\Lambda&=&(v_T+\delta v_{T1},\delta v_{T2},\delta v_{T3})~~~,\\ \nonumber
\langle\varphi_S\rangle/\Lambda&=&(v_S+\delta v_1,v_S+\delta v_2,v_S+\delta v_3)~~~,\\ \nonumber
\langle\xi\rangle/\Lambda&=&u~~~,\\ \label{sols1}
\langle\tilde{\xi}\rangle/\Lambda&=&\delta u'~~~,
\end{eqnarray}
where $u$ remains undetermined and, once we have taken $v_{T,S}$,  $u \sim O(\lambda^2)$, all shifts are suppressed by a factor of order $\lambda^2$: $\delta v/v \sim O(\lambda^2)$.
 As found in ref. \cite{Mod} the following relation holds:
\begin{equation}
\delta v_{T2} = \delta v_{T3}~~~.\\
\label{deltas}
\end{equation}
Higher order corrections to $t$ and $t^{\prime\prime}$ simply amount to a rescaling that does not change their individual order of magnitude which remains of $O(\lambda)$.

\section{Subleading Corrections}

In this section, we analyse the effects of the subleading corrections in terms of $\lambda$ to the fermion masses and mixings. The corrections arise from additional insertions of the flavons $\varphi_T$,
$\varphi_S$, $\xi$ and $\tilde{\xi}$ as well as from shifts of the VEVs shown above.

\mathversion{bold}
\subsection{Corrections to $w_{up}$}
\mathversion{normal}

In the up quark sector the leading order terms only involve the fields $\theta$ and $\theta''$, since they are
the only fields which have a non-vanishing U(1) charge among the gauge singlets of the model. The subleading
terms then additionally involve the fields $\varphi_{T}$, $\varphi_{S}$, $\xi$
and $\tilde{\xi}$. As the tenplets transform as singlets under $A_4$ and the combinations $T_i T_j H_5 \theta^n {\theta''}^m$
are invariant under the $Z_3$ group, we cannot
multiply the $w_{up}$ terms by a single flavon field. The most economic possibility is to insert two flavons, namely $\varphi_{T}
\, \varphi_{T}$. Among the three contractions leading to a 1 or $1'$ or $1''$ representation of $A_4$ only the 1 has a non-vanishing VEV, given that $\langle \varphi_{T} \rangle = (v_{T},0,0) \, \Lambda$. Therefore the dominant subleading
corrections to the up quark mass matrix have the same structure as the
leading order results and are suppressed by an
overall factor $v_{T}^2 \sim O(\lambda^4)$. The fields $\varphi_{S}$ and $\xi$, $\tilde{\xi}$ can only couple
at the level of three flavon insertions due to the requirement of $Z_3$ invariance. However, all contributions
stemming from three flavon insertions are suppressed by $\lambda^6$ relative to the leading order term. Similarly,
the corrections due to shifts in the VEVs contribute at most at relative order $\lambda^6$.
 For the up quark masses and the mixings all these corrections are negligible.

\mathversion{bold}
\subsection{Corrections to $w_{down}$}
\mathversion{normal}

In the down sector the main effect of the subleading corrections is to fill the zeros indicated
by dots in the upper triangle of $m_d$. In order to maintain the $A_4$ invariance the leading order terms include one
insertion of the flavon $\varphi_T$. The subleading corrections arise from two effects: $a.)$ replacing  $\varphi_T$ with products of flavon fields and $b.)$ including the corrections to the VEVs of $\varphi_T$. The replacement of $\varphi_T$ with
a product $\varphi_T \varphi_T$ is the simplest choice compatible with the $Z_3$ charges.
 Note that this is similar to the up quark sector. If the VEVs are unchanged this contribution to $m_d$
is of the same form as displayed in eq. (\ref{md}) and suppressed by $v_T \sim O(\lambda^2)$ compared to the
leading result due
to the additional flavon field. Therefore this type of correction does not fill the zeros in $m_d$.
They are filled by the corrections coming from the VEV shifts inserted in the terms containing one flavon $\varphi_{T}$.
 Considering that we assumed all $\delta v/v \sim O(\lambda^2)$, the corrections to the matrix elements
of $m_d$ are of the following order in $\lambda$:
\begin{equation}
\nonumber
\delta m_d=\left(
\begin{array}{ccc}
\lambda^6 & \lambda^4 & \lambda^2 \\
\lambda^6 & \lambda^4 & \lambda^2 \\
\lambda^6 & \lambda^4 & \lambda^2
\end{array}
\right) v_T \lambda v^0_d ~~~.
\label{corrvev1}
\end{equation}
As said, the matrix elements which are already non-vanishing at the leading order, eq. (\ref{md}),
receive additional corrections from the two flavon insertion $\varphi_T \varphi_T$. These are of the
same order
as the corrections from the VEV shifts, e.g. for the element $11$ also of order $\lambda^6$.
In summary, the zeroes in the elements $12$, $13$ and
$23$ of $m_d$, appearing at leading order, are replaced by terms of order $\lambda^4$, $\lambda^2$
and $\lambda^2$, respectively, in units of $ v_T \lambda v^0_d$.

In our model the relation $m_d=m_e^T$ is not valid for the first two families but it still holds at the level of orders of magnitude for each entry. So the powers of $\lambda$ are also the same for each matrix element of $m_d  m_d^\dagger$ and of $m_e^\dagger  m_e$. This is important as the matrix $m_e^\dagger  m_e$ is diagonalized by the unitary matrix $U_e$ that enters in determining the leptonic mixing matrix $U=U_e^\dagger U_{\nu}$. The results just described for the subleading corrections on $m_d$ and $m_e^\dagger$ imply that $U_e$ induces corrections of $O(\lambda^2)$ on all mixing angles in $U$, that is, in our case, corrections of $O(\lambda^2)$ to the TB values of each mixing angle.

\mathversion{bold}
\subsection{Corrections to $w_{\nu}$}
\mathversion{normal}

Also the $w_{\nu}$ term of the superpotential, eq. (\ref{wnu}), is
modified by terms with more flavon factors and by subleading
corrections to the VEVs. The Dirac mass term, proportional to $H_5(NF)$,
is mainly modified by a single $\varphi_T$ insertion,
that produces corrective terms suppressed by a $O(\lambda^2)$
  factor. These corrections are of the same order as those arising for Majorana mass terms.
 In fact, $NN$ can be in a $1$ , $1'$, $1''$ or $3_s$ combination. Since $NN\sim \omega^2$ under $Z_3$,
the singlet $1$ can be multiplied by $\xi$ (the singlet leading term) or by $(\varphi_T \varphi_S)$
(which can be absorbed into a redefinition of the leading term), $1'$ by $(\varphi_T \varphi_S)^{''}$, $1''$
by $(\varphi_T \varphi_S)^{\prime}$ and $3_s$ by $ \varphi_S$ (the triplet leading term) or
by $(\varphi_T \xi)$ or $(\varphi_T \varphi_S)_{3_s}$ or $(\varphi_T \varphi_S)_{3_a}$. All
 two flavon insertions lead to corrections of relative order of $O(\lambda^2)$ to the
matrix elements of the Majorana matrix. In addition, the shifts of the $\varphi_S$ VEVs applied to the triplet leading term also produce $O(\lambda^2)$ corrective terms. As it is easy to check, in general there are enough parameters so that all 6 independent entries of the (symmetric) Majorana mass matrix receive a different correction at $O(\lambda^2)$.

 The described corrections affect the neutrino masses and, together with the corrections to $m_e$, also
 all lepton mixing angles. To be compatible with the data, given the accuracy of the TB approximation,
the dominant corrections must be of $O(\lambda^2)$ at most, and this is precisely the magnitude of the
terms that we have just mentioned.

\section{Conclusion}

We have constructed a SUSY SU(5) grand unified model which includes
the $A_4$ description of TB mixing for leptons. For this it is not only
necessary to adopt an $A_4$ classification of quarks and leptons
compatible with SU(5), but also to introduce additional U(1) and $Z_N$
symmetries and to suitably formulate the grand unification model. We
find that the most attractive solution to cope with the different
requirements from fermion mass and mixing hierarchies, from the
problem of doublet-triplet splitting in the Higgs sector, from proton
decay bounds and from maintaining bottom tau unification only,
 is a formulation in 5 space-time dimensions with a
particular location of the different fields, with some of them on the
brane at $y=0$ and some in the bulk. The latter include the gauge
and Higgs fields as well as the tenplets of the first two, i.e. lightest,
families. The resulting model naturally leads to TB mixing in first
approximation with corrections of $O(\lambda^2)$ from higher dimensional
effective operators, together with reproducing the observed mass
hierarchies for quarks and charged leptons and the CKM mixing pattern.
 In the quark sector, however, as is typical of U(1) models, only orders of
magnitude are determined in terms of powers of $\lambda$ with
exponents fixed by the charges. A moderate fine tuning is only needed
to enhance the CKM mixing angle between the first two generations,
which would generically be of $O(\lambda^2)$, and to suppress
the value of $r$, given in eq. (\ref{rrr}), which would typically be
of order 1. The latter feature is also true in all purely leptonic $A_4$
models, in which $A_4$ leads to the correct mixing, but not directly to the
spectrum of the neutrino masses. Actually the model allows for both
types of neutrino mass hierarchy, the normal and the inverted one.
The normal hierarchy is, however, somewhat more natural, since it
requires less tuning to reproduce $r$. Furthermore, it is consistent with a
larger value of the cut-off $\Lambda$. If the normal
hierarchy is the correct one, the model predicts the sum of
neutrino masses to be around $(0.06-0.07)$ eV and $|m_{ee}|$
 to be close to 0.007 eV.
 Therefore, $|m_{ee}|$ is not far from the future aimed for
experimental sensitivity. Finally, all subleading corrections to the leading order result
of fermion masses and mixings have been carefully analysed.

In conclusion, we have demonstrated that the simple $A_4$ approach to TB mixing is compatible with a grand unified picture describing all quark and lepton masses and mixings.

\section*{Acknowledgements}

We thank S. King for very interesting discussions. We recognize that this work has been partly supported by the European Commission under contracts MRTN-CT-2004-503369 and MRTN-CT-2006-035505, and by the Italian Ministero dell'Universita' e della Ricerca Scientifica, under the COFIN program for 2007-08.

\vfill


\section{PTAS}
\input{AGG_PTAS_fin}

\section{Hardness Results}~\label{section:Hardness Results}

\input{AGG_mpnash11_fin}

\input{AGG_hardness_fin}

\section{Conclusions and Open Problems}
\input{AGG_conclusion_fin}

\bibliographystyle{plain}

\subsection*{A Copy Gadget}

As a preliminary to the hardness results of the next two subsections, we describe a \emph{copy gadget} which will prove useful
in both NP-completeness and PPAD-completeness results.  Intuitively, to simulate games $G$ of high treewidth by treewidth 1 action graph games $H$, we create several ``copies'' of each player, but only one copy of each edge relating players, thus ending up with a very ``sparse'' simulation, whose treewidth we can control.  Explicitly, given an AGG
$A$, and an agent $i$ whose strategy set consists of the two strategies $S_i=\{f_i,t_i\}$, our copy gadget will add two additional players $a,c$, of which player $c$ will be the ``copy'' and player $a$ is an auxiliary player, whose inclusion will allow player $i$'s strategies to be disconnected from player $c$'s.  We add strategies for $a$ and $c$ that are $\{f_a,t_a\}$ and $\{f_c,t_c\}$ respectively, and set the incentives so that in any Nash equilibrium $\Pr[
s(i)=t_i] = \Pr[s(b)=t_b]$ (and $\Pr[ s(i)=f_i] = \Pr[s(b)=f_b]$).

\begin{figure}
\begin{center}
\epsfig{file=copy_gadget.eps,width=.4\textwidth} \caption{The
\emph{copy gadget}---in any Nash equilibrium
$\Pr[s(b)=f_b]=\Pr[s(i)=f_i]$.}\label{fig:copy gadget}
\end{center}
\end{figure}

\begin{definition}~\label{def:copy gadget}
Given an AGG $A=\langle P,\bold{S},G,u \rangle$, and an agent $i$
with two strategy choices $S_i=\{f_i,t_i\}$, we create AGG
$A'=\langle P',\bold{S'},G',u' \rangle$ from $A$ via the addition of
a \emph{copy gadget on $i$} as follows:
\begin{itemize}
    \item{$P':=P \cup \{a,c\}.$}
    \item{$\bold{S'}:=(S_1,\ldots,S_{|P|},S_a,S_c)$, where $S_a=\{f_a,t_a\}$, and $S_c=\{f_c,t_c\}$, where $f_a,t_a,f_c,t_c \not \in S$.}
    \item{$G'$ consists of the graph $G$ with the additional vertices corresponding to $f_a,t_a,f_c,t_c$, and the directed edges $(f_i,f_a), (t_a,f_c),(f_c,t_a)$.}
    \item{$u'$ is identical to $u$ for all strategies in $S'\backslash \{S_a \cup S_c\}$, and for a configuration $D$, $u'(f_a)=D(f_i),$ $u'(t_a)=1-D(f_c),$ and $u'(f_c)=1-2 D(t_a).$}
\end{itemize}
\end{definition}
See Figure~\ref{fig:copy gadget} for a depiction of the copy gadget.

\begin{lemma}~\label{lemma:copy gadget}
Given an AGG $A$ and an agent $i$, the addition of a copy gadget on
$i$ yields $A'$ that satisfies the following properties:
\begin{itemize}
    \item{The description size of $A'$ is at most a constant larger than $A$.}
\iffalse    \item{For every $\epsilon$--Nash equilibrium $M'$ of $A'$, the restriction of $M'$ to agents $1,\ldots,n_A$ is a Nash equilibrium of $A$, and for any equilibrium $M$ of $A$, there exist distributions $M_a:=(p_{a,f},p_{a,t}), M_b:=(p_{b,f},p_{b,t})$ over strategies for agents $a$ and $b$ such that $M$ together with $M_a,M_b$ is an equilibrium of $A'$.}\fi
    \item{In the strategy graph $G_{A'}$, $f_c$ and $t_c$ are not path connected to either $f_i$ or $t_i$.}
    \item{In every $\epsilon^2$--Nash equilibrium with agent $i$'s profile $(p_{i,f},1-p_{i,f})$, agent $c$'s profile will have $|p_{c,f}-p_{i,f}|\leq \epsilon$ (and $|p_{b,t}-p_{i,t}|\leq \epsilon$).}
\end{itemize}
\end{lemma}

\begin{proof}
The first two properties follow directly from
Definition~\ref{def:copy gadget}.  For the third property, assume
otherwise and consider the case where $p_{c,f} > \epsilon+p_{i,f}$.  Agent
$a$'s expected utility for playing $f_a$ is $p_{i,f}$, and is
$p_{c,f}$ for playing $t_a$, thus our assumption that $p_{c,f} >
\epsilon+p_{i,f}$ implies that agent $a$ must be playing $t_a$ with probability at least $1-\epsilon$ since the game
is at $\epsilon^2$--equilibrium.  Given that $a$ plays $t_a$ with probability at least $1-\epsilon$, agent $b$ maximizes
her utility by playing $t_c$, and thus $p_{c,f}\leq \epsilon$, which contradicts our assumption that $p_{c,f}$ is the larger of $p_{c,f},p_{i,f}$, namely at least $\frac{1}{2}$.  An analogous argument applies to rule out the case $p_{c,f} < p_{i,f}-\epsilon$.
\end{proof}

\subsection{PPAD-Completeness}

Our PPAD-Completeness results are reductions from the problem of
computing equilibria in graphical games, and rely on the following
fact due to~\cite{CDT06}.

\begin{fact}~\label{fact:PPAD}
For the class of graphical games with $n$ players, maximum degree $3$ and
payoffs in $\{0,1,2\}$, it is PPAD--complete to compute $\epsilon$-Nash equilibria where
$\epsilon \propto 1/poly(n)$.
\end{fact}

\begin{theorem}~\label{thm:PPAD tw1}
Computing a Nash equilibrium for AGGs with strategy graph $G_A$ is
PPAD-complete even if \\$treewidth(G_A)=1$, and $G_A$ has constant degree.
\end{theorem}

\begin{proof}
From Theorem \ref{th:generalTheoremForGames} this problem is in PPAD.

To show PPAD-hardness, we reduce from the known PPAD-hard problem of Fact \ref{fact:PPAD}.  Given an instance of such a graphical game $H$, we construct an AGG $A_H'$ with
treewidth $1$ and maximum degree 4 with similar description size to
$H$ such that there a polynomial time mapping from $\epsilon$--Nash equilibria of $A_H'$ to the $\epsilon$--Nash equilibria of $H$.  We construct $A_H'$ via the
intermediate step of constructing an AGG $A_H$ which will be
equivalent to $H$ and might have large treewidth.  From $A_H$, we
construct $A_H'$ using our copy gadget to reduce the treewidth of
the associated strategy graph.  See Figure~\ref{fig:H to A_H} for a
depiction of the reduction.

The construction of $A_H$ is straightforward: for each player $i_H$
in the graphical game, we have a corresponding player $i_A$ in the
AGG with strategy set $S_{i_A}=\{f_i,t_i\}$, corresponding to the
two strategies that $i_H$ may play in $H$.  For each undirected edge between players
$(i,j) \in H$, we add directed edges between the $t$ nodes $(t_j,t_i),(t_i,t_j)$, and edges between the $f$ nodes $(f_j,f_i),(f_i,f_j)$ to the strategy graph
$G_{A_H}$ of $A_H$.  We define utilities $u$ by simulating the utility functions from the original game $H$: from each $f$ strategy connected to $i_A$ in the AGG we know that if it is played then the corresponding $t$ strategy is not played and vice versa; thus we have recovered the strategy choice of each neighbor of $I_H$ in original graphical game; we then apply the utility function of the graphical game to compute the utility in the AGG.  We do the symmetric procedure for the $t$ nodes of the AGG.  From the
construction, it is clear that $H$ and $A_H$ represent the same game
via the correspondence $i_H \rightarrow i_A$, and in particular an
$\epsilon$--Nash equilibrium of one game will correspond to an
$\epsilon$--Nash equilibrium of the other game via the natural
mapping.

We obtain $A_H'$ from $A_H$ by making three copies of each $i_A$ via
the copy gadget.  Thus for each $i$ there are agents $i_A,
i_A^1,i_A^2,i_A^3$ with $S_{i_A^k}=\{f_{i_A}^k,t_{i_A}^k\}$.
Finally, for each of the (at most three) outgoing edges of $f_{i_A}$
that are not part of copy gadgets, i.e the edges of the form
$(f_{i_A},f_{j_A})$, we replace the edge by $(f_{i_A}^k,f_{j_A})$,
with each $f_{i_A}^k$ having at most one outgoing edge, and modify
the utility function $u$ analogously so as to have the utility of
strategy $f_{j_A}$ depend on $f_{i_A}^k$ instead of $f_{i_A}$.
Analogous replacements are made for the outgoing edges of $t_{i_A}$.
Since the copied strategies $f_{i_A}^k,t_{i_A}^k$ are disconnected
from the original strategies $f_{i_A},t_{i_A}$ the longest path in
the strategy graph $G_{A_H'}$ associated with $A_H'$ has length at
most 4, with maximum degree 6, and $treewidth(G_{A_H})=1$.  (See
Figure~\ref{fig:H to A_H}.) Lemma~\ref{lemma:copy gadget} guarantees
that the transformation from $A_H$ to $A_H'$ increases the
representation size by at most a constant factor.  Further, from an $\frac{1}{144}\epsilon^2$--Nash equilibrium of $A_H'$ we can extract an $\epsilon$--Nash equilibrium of $A_H$ by simply ignoring the new players: all of the copies $i_A^k$ of a player $i_A$ will play strategies with probabilities within $\frac{1}{12}\epsilon$ of the probabilities of playing the original by Lemma~\ref{lemma:copy gadget}; thus the joint distribution of any triple of these will have joint distribution within $\frac{1}{4}\epsilon$ of the ``true'' joint distribution; since each utility has magnitude at most 2 the computed utilities will be within $\frac{1}{2}\epsilon$ of the utilities computed in $A_H$; thus each of the mixed strategies of a player $i_A$ in $A_H'$, interpreted as a strategy in $A_H$ will yield utility within $\epsilon$ of optimal.  From Fact \ref{fact:PPAD} we conclude that finding an $\frac{1}{144}\epsilon^2$--Nash equilibrium of $A_H'$ is PPAD complete for any polynomial $\epsilon$, yielding the desired result.
\end{proof}

\begin{figure}
\begin{center}
\epsfig{file=HtoA_H.eps,width=.6\textwidth} \caption{The
transformation from the graphical game $H$ to the AGG $A_H'$.  For
simplicity, the internal strategies and edges associated with the
copy gadgets are omitted.}~\label{fig:H to A_H}
\end{center}
\end{figure}

We now turn our attention to AGGs that have a constrained number of
player types.

\begin{theorem}~\label{thm:PPAD sym}
Computing a Nash equilibrium for symmetric AGGs ($1$ player type) is
PPAD-complete even if the strategy graph $G_A$ has bounded degree.
\end{theorem}

To show PPAD-hardness, as above we reduce from the known PPAD-hard problem of
computing Nash equilibria in graphical games of degree at most $3$
where each player chooses between $2$ strategies $f,t$ and has
utility $0$, $1$, or $2$.  Given such a graphical game $H$, we will
reduce it to an AGG $A_H$ that has strategies $f_i,t_i$
corresponding to the two strategies that agent $i$ may choose in
$H$.  Intuitively, if our reduction is to be successful there are
several properties of $G_H$ that seem necessary.  First, in every
Nash equilibrium of $G_H$, there must be at least one agent playing
either $f_i$ or $t_i$ for every $i$.  This is accomplished by giving
agents a bonus payment if they choose either of the two strategies
of a sparsely-played $f_i,t_i$ pair.  Second, there must be some
unambiguous mapping between the number of agents playing $f_i$ and
$t_i$ in $A_H$ to a choice of actions of agent $i$ in $H$.  This is
accomplished via the MAJORITY function: if more agents play $f_i$
than $t_i$ in $A_H$, we say that $i$ plays $f$.  This motivating intuition is formalized in the
proof below.

\begin{prevproof}{Theorem}{thm:PPAD sym}
From Theorem \ref{th:generalTheoremForGames} this problem is in PPAD

To show PPAD-hardness, we reduce from the known PPAD-hard problem of
computing Nash equilibria in graphical games of degree at most $3$
where each player chooses between $2$ strategies and has utility
$0$, $1$, or $2$.  Given an instance of such a graphical game $H$,
with $n$ agents, and some $\epsilon>0$ we construct the symmetric
AGG $A_H$ so that an $\epsilon$--Nash equilibrium of $A_H$ can be
efficiently mapped to a $2 \epsilon$--Nash equilibrium of $H$.  We
construct $A_H=\langle P,\bold{S},G_{A},u \rangle$ as follows:
\begin{itemize}
    \item{$P:=\{1,\ldots,3 c n\}$ with $c>\frac{64}{\epsilon^2}$.}
    \item{$\bold{S}:= (S,\ldots,S)$, that is, each player has identical (symmetric) strategy set $S:=\{f_1,t_1,\ldots,f_n,t_n\}$ where strategies $f_i$ and $t_i$ correspond to the two strategies of the $i^{th}$ agent of $H$.}
    \item{For every undirected edge $(i,j)$ in the graph of $H$, the strategy graph $G_A$ has the eight directed edges $(f_i,f_j)$, $(f_j,f_i)$, $(f_i,t_j)$, $(t_j,f_i)$, $(t_i,f_j)$, $(f_j,t_i)$, $(t_i,t_j)$, $(t_j,t_i).$  Furthermore, for all $i \in \{1,\ldots, n\}$, $G_A$ contains the edges $(f_i,t_i),(t_i,f_i)$ and the self loops $(f_i,f_i)$ and $(t_i,t_i)$.}
    \item{To simplify the description of the utility function $u$, it will be useful to define the indicator functions\\ $I_1[D(f_1,t_1)],\ldots,I_n[D(f_n,t_n)]$ where $$I_i[D(f_i,t_i)]:= \left\{ \begin{array}{cc} f & \text{if $D(f_i) \ge D(t_i)$} \nonumber \\ t & \text{if $D(f_i)< D(t_i)$} \nonumber \end{array} \right.$$ Let $u$ assign utility to $f_i$ as a function of $D(\nu(i))$, where $\nu(i)$ denotes $i$'s neighbors, by applying the utility function for agent $i$ from $H$ on the simulated actions of her neighbors $j_1,j_2,j_3$ evaluated as $I_{j_1}[D(f_{j_1},t_{j_1})],I_{j_2}[D(f_{j_2},t_{j_2})],$ and $I_{j_3}[D(f_{j_3},t_{j_3})]$, respectively.  Finally, if $D(f_i)+D(t_i) \leq c$, $u$ assigns an extra $100$ utility to strategies $f_i$ and $t_i$.}
\end{itemize}
Observe that the description size of $A_H$ is polynomial in $cn$,
and thus is polynomial in the description size of $H$.  From Fact~\ref{fact:PPAD} our theorem will follow if we show that any $\epsilon^2$--Nash equilibrium of $A_H$ can
be efficiently mapped to an $\epsilon$--Nash equilibrium of $H$.

Consider the map from mixed strategy profiles of $A_H$ to mixed
strategy profiles of $H$ given by $\phi: \bold{M_A} \rightarrow
\bold{M_H}$ that assigns $M_H=[ (p_{1,f},
1-p_{1,f}),\ldots,(p_{n,f}, 1-p_{n,f}) ]$ by setting
$p_{i,f}:=\Pr_{M_A} (I_i=f)$ where the probability is taken over the
distribution over $\Delta$ defined by $M_A$.  It is clear that the
map $\phi$ can be computed efficiently, as it essentially involves simply evaluating multinomial distributions on 4 outcomes.

Before showing that $\phi$ maps $\epsilon$--equilibria to
$2\epsilon$--equilibria we first show that the ``extra utility" of 100 correctly incentivizes a large number of players to play on each strategy pair. We observe that in any mixed strategy
profile there will be at least one agent, $j$, who has probability at most $1/3$ of receiving a payoff of at least $100$.  Since his payoff from the simulation of $H$ is at most 2, such an agent's
expected utility is at most $35+\frac{1}{3}$, and thus any Nash equilibrium
mixed strategy profile must satisfy $100 \Pr( D(f_i)+D(t_i) < c) <
36, \forall i \in \{1,\ldots,n\}.$  If this were not the case, then
agent $j$ could improve her expected utility to at least $36$ by
always choosing strategy $f_i$, a contradiction.  The above
inequality implies that $$\mathbb{E}\left[\max\left(D(f_i),D(t_i)\right)
\right] > \frac{c}{4}.$$

We now proceed with the proof of correctness of the map $\phi$.  Let
$M_A$ be an $\epsilon$--Nash equilibrium of $A_H$, and
$M_H=\phi(M_A)$.  Consider a player $i$ in the graphical game, and a strategy of his that he plays with probability at least $\epsilon$.  Without loss of generality let this strategy be $f_i$.  We show that his utility for playing $f_i$ is at least his utility for playing his other choice, $t_i$, minus $\epsilon$; taken together, these statements imply that $M_H$ is an $\epsilon$--Nash equilibrium of the graphical game, as desired.

Since $\mathbb{E}\left[\max\left(D(f_i),D(t_i)\right)
\right] > \frac{c}{4}$, we have that if $f_i$ is played with probability at least $\epsilon$, namely if $\Pr(D(f_i)\geq D(t_i))\geq \epsilon$ then (by Chernoff bounds) we must have $\mathbb{E}[D(f_i)]\geq\frac{c}{6}$.  This implies that for at least one of the $3cn$ players $j$ in $A_H$, his probability of playing $f_i$ is at least $\frac{1}{18n}$, which is at least $2\epsilon$.  Thus, since $M_A$ is, by assumption, an $\epsilon^2$--Nash equilibrium, we have that player $j$'s utility for playing $f_i$ is at most $\frac{1}{2}\epsilon$ below his utility for playing $t_i$, when the other players play from $M_A$.  Further, by construction, each of these two utilities are within $\frac{1}{4}\epsilon$ of the utilities for player $i$ in the graphical game to play $f_i,t_i$ respectively, when the other players play from $M_H$: this is because fixing player $j$'s move from $M_{A,j}$ to one of $f_i,t_i$ changes each $I_k$ by at most the probability of $j$ playing one of $(f_k,t_k)$ divided by the standard deviation of $\max\left(D(f_i),D(t_i)\right)$, which is at least the square root of its expectation, $\sqrt{\frac{c}{4}}=\frac{4}{\epsilon}$.  Thus by the triangle inequality we have that player $i$'s utility for playing $f_i$ is no more than $\epsilon$ worse than playing $t_i$.  Since our choice of $i$ was arbitrary and a corresponding argument applies to the $t$ strategies, we conclude that $M_H$ is an $\epsilon$--Nash equilibrium of $H$, as desired.
\end{prevproof}

\subsection{NP--Completeness}

Both of our NP--completeness results are reductions from the
NP-Complete problem CIRCUITSAT and follow an approach employed
in~\cite{SV_2006}.

\begin{fact}~\label{fact:NP-complete}
It is NP-complete to decide satisfiability for the class of circuits consisting of AND, OR, and NOT gates, with maximum degree $3$ (in-degree plus out-degree).
\end{fact}

In our reductions from CIRCUITSAT, given a circuit $C$, we construct
an AGG $A_C$ that computes $C$ in the sense that pure strategy Nash
equilibria of $A_C$ map to valid circuit evaluations.
To this game we add two agents that have a simple pure-strategy equilibrium if $C$
evaluates to $true$, but when $C$ evaluates to $false$ play \emph{pennies}---a simple game
that has no pure strategy Nash equilibria.  Thus the existence of a
pure strategy Nash equilibrium is equivalent to the satisfiability of
$C$.

\begin{theorem}~\label{thm:NP tw1}
Deciding the existence of a pure strategy Nash equilibrium for AGGs
with strategy graph $G_A$ is NP-complete even if $treewidth(G_A)=1$,
and $G_A$ has constant degree.
\end{theorem}

\begin{proof}
Membership in NP is clear.  To show hardness, given a circuit $C$,
we construct the associated AGG $A_C:=\langle P,\bold{S},G_{A},u
\rangle$ as follows:
\begin{itemize}
    \item{$P:=\{1,\ldots,n, p_1,p_2\}$, where $n$ is the number of gates in $C$, and the gate corresponding to player $n$ is the output gate.}
    \item{$\bold{S}:= \left((f_1,t_1),\ldots,(f_n,t_n), (f_{p_1},t_{p_1}), (f_{p_2},t_{p_2})\right)$.}
    \item{For every pair of gates $i,j$ for which the output of gate $i$ is an input to gate $j$, $G_A$ has the edges $(f_i,f_j),$ and $(f_i,t_j)$.  Furthermore, we add edges $(f_n,f_{p_1}), (f_n,t_{p_1}), (f_n,f_{p_2}), (f_n,t_{p_2})$, and the edges $(f_{p_1}, f_{p_2})$, $(f_{p_1},t_{p_2})$, $(f_{p_2},f_{p_1})$, $(f_{p_2},t_{p_1})$.}
    \item{The utility function $u$ is defined as follows: if agent $i$ corresponds to an input gate, than strategies $f_i,t_i$ both have utility 0.  For any other agent $i$ corresponding to a gate of $C$, the payoff of strategy $f_i$ is $1$ or $0$ according to whether $f_i$ is the correct output value of gate $i$ given the values corresponding to the strategies played by neighboring agents/strategies.  Similarly for the payoff for strategy $t_i$. If $D(f_n)=0$, then $f_{p_1}$ and $t_{p_1}$ have utility 0, otherwise the utility of $p_1$ is 1 if $D(f_{p_1})=D(f_{p_2})$, and is 0 otherwise.  The utility of $p_2$ is 1 if $D(f_{p_1}) \neq D(f_{p_2})$, and is 0 otherwise.}
\end{itemize}
From the construction it is clear that if $C$ is satisfiable, there
is a pure strategy profile for agents $1,\ldots,n$ with agent $n$
playing $t_n$, such that agents $1,\ldots,n$ can not improve their
utility by deviating from their strategies.  Furthermore, $p_1$ will
be indifferent between her strategies, and $p_2$ will play the
opposite of $p_1$; in particular, there will be a pure strategy Nash
equilibrium.  If $C$ is not satisfiable, then any pure strategy
profile that is an equilibrium for agents $1,\ldots, n$ will have
$D(f_n)=1$, and thus $p_1$ will be incentivized to agree with $p_2$,
and $p_2$ will be incentivized to disagree, and thus $A_C$ will
admit no pure strategy Nash equilibrium.

To complete the proof, note that we can apply the copy gadget to
each agent of $A_C$, as was done in the proof of
Theorem~\ref{thm:PPAD tw1} to yield the game $A_C'$ that has
strategy graph of treewidth 1, and a mapping from equilibria of $A_C'$ to equilibria of $A_C$.
\end{proof}

\begin{theorem}~\label{thm:NP sym}
Deciding the existence of a pure strategy Nash equilibrium for
symmetric AGGs ($1$ player type) is NP-complete even if the strategy
graph $G_A$ has bounded degree.
\end{theorem}

\begin{proof}
Membership in NP is clear; to show hardness we proceed as was done
in the proof of Theorem~\ref{thm:NP tw1}, and obtain AGG $A_C$ from
circuit $C$.  Now, we make $A_C$ symmetric by retaining the same number of agents, but allowing each of them to
pick any of the strategies.   We modify the strategy graph $G$ by
adding edges $(f_x,t_x),(t_x,f_x),(f_x,f_x),(t_x,t_x)$ for each player $x$ from $A_C$, and extend
the utility function $u$ so that if $D(f_x)+D(t_x) >1$ then strategies
$f_x$ and $t_x$ have utility $-1$.  Thus in any pure strategy Nash
equilibrium $D(f_x)+D(t_x)=1$, and the reasoning in the proof of
Theorem~\ref{thm:NP tw1} applies to complete our reduction.
\end{proof}

\section{Introduction}~\label{section:Introduction}

What is the likely behavior of autonomous agents in a variety of competitive environments?  This question has been the motivation for much of economic theory.  Partly due to the increasing prevalence of vast online networks over which millions of individuals exchange information, goods, and services, and the corresponding increasing importance of understanding the dynamics of such interactions, the Computer Science community has joined in the effort of studying game-theoretic questions.

Computing equilibria in games and markets has been extensively studied in the Economics and Operations Research communities since the 1960's, see e.g. \cite{Lemke-Howson,Rosenmuller,Wilson,Scarf,Taal}. Computational tractability has been recently recognized as an important prerequisite for modeling competitive environments and measuring the plausibility of solution concepts in Economics: if finding an equilibrium is computationally intractable, should we believe that it naturally arises? And, is it plausible that markets converge to solutions of computationally intractable problems?  Probably not --- but if so, we should certainly know about it.

Computing Nash equilibria in games, even in the case of two players, has been recently shown to be an intractable problem; in particular, it was shown to be complete for the class of fixed point computation problems termed PPAD~\cite{DP_2006,CD_2006}. This result on the intractability of computing Nash equilibria has sparked considerable  effort to find efficient algorithms for approximating such equilibria, and has increased the importance of considering special classes of games for which Nash equilibria might be efficiently computable.

For two-player games the hardness of computing approximate equilibria persists even if the required approximation is inverse polynomial in the number of strategies of the game \cite{CDT06}; similarly, hardness persists in graphical games if the required approximation is inverse polynomial in the number of players \cite{DP_2006,CDT06}. The same hardness results apply to special cases of the problem, e.g. win-lose games, where the payoff values of the game are restricted to $\{0,1\}$ \cite{Val05}, sparse bimatrix games, where the number of non-zero entries of each row an column of the payoff matrices is a constant, and two-player symmetric games \cite{GaleKuhnTucker}. The emerging question of the research in this field is: { Is there a Polynomial Time Approximation Scheme (PTAS) for Computing Nash Equilibria?} And, { which special cases of the problem are computationally tractable?}

The zero-sum two-player case is well-known to be tractable by reduction to linear programming \cite{vonNeumanLP}. Tractability persists in the case of low-rank two-player games, in which the sum $A+B$ of the payoff matrices of the players, instead of being $0$, has fixed rank; in this case, a PTAS exists for finding mixed Nash equilibria \cite{KannanTheobald}. In $n$-player graphical games, a PTAS has been provided if the tree-width is $O(\log n)$ and the maximum degree is bounded \cite{DasPapEC06}; in the case of dense graphical games, a quasi-polynomial time approximation scheme exists \cite{DasPapExhaustive}.

An important line of research on tractable special cases has explored games with symmetries. Mutli-player symmetric games with about logarithmically few strategies per player can be solved exactly in polynomial time by reduction to the existential theory of reals \cite{PapRough}. For congestion games, a pure Nash equilibrium can be computed in polynomial time if the game is a symmetric network congestion game \cite{FabPapTalwar}, and an approximate pure Nash equilibrium if the game is symmetric but not necessarily a network game and the utilities satisfy a ``bounded-jump condition'' \cite{ChienSinclair}. Another important class of games for which computing an approximate equilibrium is tractable is the class of anonymous games, in which each player is different, but does not care about the identities of the other players, as it happens for example congestion games, certain auction settings, and social phenomena \cite{Blonski99}; a PTAS for anonymous games with a fixed number
 of strategies has been provided in \cite{DP:anonymous07,DasPapExhaustive}. For a thorough study of the problem of computing pure Nash equilibria in symmetric and anonymous games see \cite{BFH_2007}.

In this paper, we consider another special class of games,  {\em Action Graph Games} (AGGs), that were introduced by Bhot and Leyton-Brown \cite{B_LB_2004}.  AGGs is a fully general game representation that succinctly captures both `local' dependencies as in graphical games, as well as partial indifference to other agents' identities as in anonymous games.  Strategies are represented as nodes in a graph, called \emph{strategy graph},  and the utility of an agent for selecting a strategy-node depends on the number of other agents selecting each of the neighboring strategies.  The only attribute that distinguishes players is the set of strategies that each player is allowed to play.  In particular, all agents who play a given strategy get the same payoff.  A variety of natural games can be concisely represented as AGGs, and we refer the reader to~\cite{B_LB_2004,J_LB_2007} for further discussion.

In the remainder of this section, we discuss previous work on AGGs and summarize our results. In the end of the section, we provide definitions.

\subsection{Previous Work}

Action graph games were first defined by Bhat and Leyton-Brown~\cite{B_LB_2004} who considered the problem of computing Nash equilibria of these games.  In particular, they analyzed the complexity of computing the Jacobian of the payoff function---a computation that is, in practice, the bottleneck of the continuation method of computing a Nash equilibrium.  They considered this computation for both general AGGs and AGGs with a single player type (symmetric AGGs), and found that this computation is efficient in the latter case.  For pure Nash equilibria, Jiang and Leyton-Brown~\cite{J_LB_2007}
show that deciding the existence of such equilibria in AGGs is $\mathbf{NP}$-complete, even in the case of a single player type and bounded degree.  On the other hand, they provide a polynomial time algorithm for finding pure-Nash equilibria in AGGs with constant number of player types when the strategy graph has bounded tree-width.

\subsection{Our Results}
We examine, and largely resolve the computational complexity of computing Nash equilibria in action graph games. We give a polynomial algorithm for computing an $\epsilon$-Nash equilibrium
for AGGs with constant treewidth and degree and a constant number of agent
types (and arbitrarily many strategies), together with hardness
results for the cases when either the treewidth or the number of
agent types is unconstrained.  In particular, we show that even if
the strategy graph is a tree with bounded degree but the number of agent types
is unconstrained, it is NP--complete to decide the existence of a
pure-strategy Nash equilibrium and PPAD--complete to compute a mixed
Nash equilibrium; similarly for AGGs in which all agents are a
single type if we allow the strategy graph to have arbitrary treewidth.  These hardness results
suggest that, in some sense, our PTAS is as strong of a positive
result as one can expect.   While Bhat and Leyton-Brown studied heuristics for computing mixed
Nash equilibria \cite{B_LB_2004}, the authors know of no previous
complexity theoretic results concerning computing mixed Nash
equilibria for AGGs apart from the $\mathbf{PPAD}$-hardness result that follows from
them being a generalization of normal-form games.

\subsection{Definitions}~\label{subsection:Action Graph Games}

In this section we give a formal definition of AGGs and introduce the terminology that will be used in the remainder of this paper.  We follow the notation and terminology introduced in~\cite{J_LB_2007}. \\

\begin{definition}
An \emph{action-graph game}, $A$, is a tuple $\langle P,\bold{S},G,u
\rangle$ where
\begin{itemize}
     \item{$P:=\{1,\ldots, n\}$ is the set of agents.}
     \item{$\bold{S}:=(S_1,\ldots,S_n),$ where $S_i$ denotes the set of pure strategies that agent $i$ may play.}
     \item{For convenience, let $S := \bigcup_i S_i = \{s_1,\ldots,s_{|S|}\}$ denote the set of all strategies, and thus each $S_i \subseteq S$.
        Also, we write $S_i = \{s_{i, 1}, s_{i, 2}, \ldots, s_{i,
        |S|_i}\}$
        Furthermore, we'll let $s(i)$ denote the strategy played by agent $i$.}
     \item{For any $S' \subset S$, let $\Delta(S')$ denote the set of valid configurations of agents to strategies $s \in S'$; we represent a configuration $D(S') \in \Delta(S')$ as an $|S'|$-tuple $D(S')=\{n_1,\ldots,n_{|S'|}\}$ where $n_i$ is the number of agents playing the $i^{th}$ strategy of $S'$.}
     \item{$G$ is a directed graph with one node for each action $s_i$.  Let $\nu : S\rightarrow 2^S$, be the neighbor relation induced by graph $G$, where $s' \in \nu(s)$ if the edge $(s',s) \in G$.  Note that self-loops are allowed, and thus it is possible that $s \in \nu(s)$.  We refer to $G$ as the \emph{strategy graph} of $A$.}
     \item{The utility function $u$ assigns identical utilities to all agents playing a given strategy $s$, with the utility depending only on the number of agents playing neighboring strategies.  Formally, $u: \Delta(S) \rightarrow \mathbb{R}^{|S|}$, via maps $u_1,\ldots,u_{|S|}$ where $u_i: \Delta[\nu(s_i)] \rightarrow \mathbb{R}$ defines the common utility of all agents playing strategy $s_i$.}
\end{itemize}
\end{definition}

Note that AGGs are fully expressive because any games can be
written as an action graph game in which the strategy sets of different players are disjoint, and the strategy graph $G$ is complete.

We now define a further type of possible symmetry between agents
that will be important in our analysis of the complexity of
computing Nash equilibria.

\begin{definition}
We say that an AGG has $k$ \emph{player types} if there exists a
partition of the agents into $k$ sets $P_1,\ldots,P_k$, such that if
$p,p' \in P_i$, then $S_p = S_{p'}$.  (The terminology
of~\cite{J_LB_2007} refers to such games as $k$-symmetric AGGs.)
\end{definition}

Since agents who play the same
strategy receive the same utility, all agents of a given type are
identical---for example an AGG with a single player type is a
symmetric game.  While the number of player types does not
significantly alter the description size, decreasing the number of
player types constrains the space of possible Nash equilibria; this is the motivation for considering AGGs with few player types as a possible class of tractable games.

A \emph{strategy profile},
$M:=[m_1,\ldots, m_n]$, with $m_i =(p_{i,1},\ldots,p_{i,|S_i|})$
assigns to each agent a probability distribution over the possible
strategies that the agent may play, with $\Pr[
s(i)=s_{i,k}]=p_{i,k}$ where $s_k$ is the $k^{th}$ element of $S_i$.  Thus a given strategy profile induces an expected utility for each player $\mathbb{E}[u|M] = \sum_{D \in \Delta} u(D) \Pr(D),$ where the probability is with respect to the strategy profile $M$.

\begin{definition}
A strategy profile $M$ is a \emph{Nash-equilibrium} if no player
can increase her expected utility by changing her strategy $m_i$ given the strategy profiles $m_{-i}$ of the other agents. That is,
for all strategy profiles $m_i'$. $\mathbb{E}[u_i|m_{-i},m_i] \ge \mathbb{E}[u_i|m_{-i},m_i']$.
\end{definition}

\begin{definition}
A strategy $m\in M$ is an
$\epsilon$-\emph{Nash-equilibrium} if no player can increase her
expected utility by more than $\epsilon$ by changing her strategy profile.
\end{definition}

Note that there is the slightly stronger definition of an $\epsilon$--Nash equilibrium in which, for all agents $i$, the expected utility of playing every strategy $s$ in the support of $m_i$ is at most $\epsilon$ less than the expected utility of playing a different $s' \in S_i$.  We do not stress the distinction, as our PTAS finds such an $\epsilon$--Nash equilibrium, and our hardness results apply to the weaker definition given above.
\subsection*{Mapping Action Graph Games to Graphical Games}
\label{sec:actiontographical}

We show the following result which reduces the problem of computing a Nash equilibrium of an action graph game to the problem of computing a Nash equilibrium of a graphical game. Since the latter is in PPAD \cite{PapParityArgument}, it follows that the former is in PPAD as well.
\begin{theorem} \label{th:generalTheoremForGames}
Any action-graph game $A$ can be mapped in polynomial time to a
graphical game $\mathcal{G}$ so that there is a polynomial-time computable
surjective mapping from the set of Nash equilibria of $\mathcal{G}$ to the set
of Nash equilibria of $A$.
\iffalse Moreover, the problem of computing a Nash equilibrium in an action-graph game is polynomial-time reducible to the problem of computing a Nash equilibrium of a 2-player game.\fi
\end{theorem}
\begin{proof}
Let us define a bounded division-free straight-line program to be an arithmetic
binary circuit with nodes performing addition, subtraction, or multiplication on their
inputs, or evaluating to pre-set constants, with the additional constraint that the values
of all the nodes remain in [0, 1].

We will show that there exists a bounded division-free staight-line program of polynomial size in the description of the action graph game which, given a mixed strategy profile $M:= \{(p_{i,1},\ldots,p_{i,|S_i|})\}_{i=1}^n$, computes, for every agent $i$, $i=1,\ldots,n$, and for every pure strategy $s_i$, $s_i \in S_i$, of that agent, the expected utility that this agent gets for playing pure strategy $s_i$. The proof then follows from Theorems 1 and 2 of \cite{DasFabPap:ICALP06}.

Without loss of generality, we will show that there exists a straight-line program of polynomial size for computing the expected utility of agent $1$ for playing pure strategy $s_{1,1}$. For this purpose, let $\mathcal{N}:=\nu(s_{1,1})$ and $\Delta:=\Delta(\nu(s_{1,1}))$. Also, for any subset $P' \subseteq P$ of the agents, let $\Delta_{P'}$ be the set of valid configurations of the agents of the set $P'$ to the strategies in $\mathcal{N}$, represented as $|\mathcal{N}|$-tuples of numbers; then, for every $D \in \Delta_{P'}$, let $\Pr_{P'}[D]$ be the probability that configuration $D$ arises from the set of agents $P'$, where the measure $\Pr_{P'}$ is taken over the mixed strategies of agents in $P'$. Using this notation, the expected payoff of agent $1$ for playing $s_{1,1}$ can be written as follows

\begin{align}
\mathcal{U}_{1,s_{1,1}}:=\sum_{D \in \Delta_{P\setminus\{1\}}} u_{s_{1,1}}(D + 1_{s_{1,1}}) \Pr{}_{P\setminus \{1\}}[D], \label{eq:costis1}
\end{align}
where $1_{s_{1,1}}$ is an $|\mathcal{N}|$-tuple of numbers having a $1$ at the coordinate corresponding to strategy $s_{1,1}$ and $0$ everywhere else, and where $D + 1_{s_{1,1}}$ represents coordinate-wise addition.

From Equation \eqref{eq:costis1}, it follows that, if there is a bounded division-free straight-line program of polynomial size which computes the values $\{\Pr{}_{P\setminus\{1\}}[D]\}_{D \in \Delta_{P\setminus\{1\}}}$, a straight-line program for computing $\mathcal{U}_{1,s_{1,1}}$ can be constructed at an additional cost of $O(|\Delta_{P\setminus\{1\}}|) = O(|A|)$ arithmetic gates. To conclude the proof, we prove the following lemma.

\begin{lemma}
Let $P_j=\{j+1,\ldots,n\} \subseteq P$ and suppose that there exists a bounded division-free staight-line program computing the values $\{\Pr_{P_j}[D]\}_{D \in \Delta_{P_j}}$. Also, suppose that the size of this straight-line program is bounded by $g$. Then there exists a straight-line program of size bounded by $g+O(|A|\cdot(|A|+|S|))$ which computes the values $\{\Pr_{P_j \cup \{j\}}[D]\}_{D \in \Delta_{P_j \cup \{j\}}}$.
\end{lemma}

\begin{proof}
Note first that $|\Delta_{P_j \cup \{j\}}| = O(|A|)$, where $|A|$ is the description size of the action graph game. Then, for every $D\in\Delta_{P_j \cup \{j\}}$, it holds that
\begin{align}
\Pr{}_{P_j \cup \{j\}} [D] &= \sum_{s_{j,k} \in S_j \setminus \mathcal{N}}{\Pr{}_{\{j\}}[\text{$j$ plays $s_{j,k}$}] \Pr{}_{P_j}[D]}\notag\\&~~~~~~~~~~~~~~~~~~~~ +\sum_{\begin{minipage}{2.5cm}\centering $s_{j,k} \in S_j \cap \mathcal{N}$,\\ $D' \in \Delta_{P_j}$:\\ $1_{s_{j,k}}+D' = D$ \end{minipage}}{ \Pr{}_{\{j\}}[1_{s_{j,k}}] \Pr{}_{P_j}[D']}, \label{eq:costis2}
\end{align}
where in the above expression $\Pr_{P_j}[D]=0$, if $D \notin \Delta_{P_j}$. Observe that in \eqref{eq:costis2} the first summation has at most $|S|$ terms and the second at most $|A|$ terms. Hence, given the values $\{\Pr_{P_j}[D]\}_{D \in \Delta_{P_j}}$, the above expression can be evaluated with $O(|A|+|S|)$ arithmetic operations. The result follows.
\end{proof}

From the lemma above it follows that there exists a straight-line program of size bounded by $O(n\cdot|A|\cdot(|A|+|S|)) = O(|A|^3)$ for computing $\{\Pr{}_{P\setminus\{1\}}[D]\}_{D \in \Delta_{P\setminus\{1\}}}$. This concludes the proof of the theorem, since all the intermediate values of the computations described above are in $[0,1]$.
\end{proof}