# On the Conformal Lens Map

Vicente Ahumada  Facultad de Ingeniería y Ciencias
Universidad Adolfo Ibáñez
Av. Padre Hurtado 750, Viña del Mar, Chile<EMAIL_ADDRESS>,
Eduardo Behm  Facultad de Ingeniería y Ciencias
Universidad Adolfo Ibáñez
Av. Padre Hurtado 750, Viña del Mar, Chile<EMAIL_ADDRESS>,  Rodrigo
Hernández  Facultad de Ingeniería y Ciencias
Universidad Adolfo Ibáñez
Av. Padre Hurtado 750, Viña del Mar, Chile<EMAIL_ADDRESS>and
Dubalio Pérez  Facultad de Ingeniería y Ciencias
Universidad Adolfo Ibáñez
Av. Padre Hurtado 750, Viña del Mar, Chile<EMAIL_ADDRESS>
###### Abstract.

It is well-known that lens maps are convex mappings defined in the unit disc
to itself. In this brief note, we show that these mappings are convex of order
$\alpha>0$, and starlike of order $\beta>0$, and establish the precise orders
in terms of opening angle of the lens map.

The authors were partially supported by Fondecyt Grants # 1190756. Key words:
Convex Mappings, Lens Maps. 2020 AMS Subject Classification. Primary: 30C45,
30C99; Secondary: 31C05.

##  1\. Introduction

The study of conformal functions has been very extensive in the last century
and many applications can be described by these functions. For instance, the
author in [4] uses these kind of mappings to understand the visual field,
which is represented in the brain by mappings which are, at least
approximately, conformal. Since conformal mappings preserve essential visual
information, [1] states that they are used for the solutions of 2D potential
problems on conservative fields, while they are also used for face recognition
and texture processing in computer graphics. For more detail conformal
mappings, see [7]. In these brief notes, we will study some geometric aspects
of what we call lens maps such as the order of starlikeness and convexity.

Let $\zeta$ be the complex function defined in the unitary disc, where
$z\in\mathbb{D}$: $\zeta(z)=(1+z)/(1-z)$ as a Möbius transformation that maps
the disc into a half plane. Now, we can define the lens function with the
parameter $\alpha\in(0,1]$ as

(1)
$\ell_{\alpha}(z)=\frac{\xi-1}{\xi+1}=\frac{\zeta^{\alpha}-1}{\zeta^{\alpha}+1}=\frac{\left(\dfrac{1+z}{1-z}\right)^{\alpha}-1}{\left(\dfrac{1+z}{1-z}\right)^{\alpha}+1}.$

To see some application of lens maps read [2].

Let $\mathcal{C}$ be the class of holomorphic and univalent functions
normalized by the conditions $f(0)=0$ and $f^{\prime}(0)=1$ that transform the
unitary disc into a convex region in the complex plane. Then, an important
characterization of convex functions is that $f\in\mathcal{C}$ if and only if

(2)
$\operatorname{Re}\left\\{1+z\frac{f^{\prime\prime}(z)}{f^{\prime}(z)}\right\\}>0.$

For more details on convex mappings, refer to[3, 5, 6]. One of the many
extensions of the class of convex functions was provided by Robertson in [8]:
$f$ is a convex function of order $\alpha$, with $0\leq\alpha<1$, if

${\mathbb{R}}\left\\{1+z\,\dfrac{f^{\prime\prime}}{f^{\prime}}(z)\right\\}>\alpha.$

We denote the class of convex function of order $\alpha$ as
$\mathcal{C}_{\alpha}$. Observe that $\mathcal{C}_{0}=\mathcal{C}$ and
$\mathcal{C}_{\alpha}\subset\mathcal{C}$ for all $0\leq\alpha<1$. Robertson
[8] observed that functions $f$ in $\mathcal{C}_{\alpha}$, have the following
geometric property: the ratio of the angle between adjacent tangents of the
unit circle over the angle between the corresponding tangents in the image of
$f$ is less than $1/\alpha$. Hence the closer $\alpha$ is to 1 the “rounder”
is the image. For instance, segments in the boundary of $f({\mathbb{D}})$ are
prohibited as soon as $\alpha>0$.

##  2\. Results

It is a well-known result that lens maps are bounded convex mappings. However,
it is not easy to see that actually is a convex mapping with order $\beta>0$.
This is the main purpose of this notes. In fact, lens maps are a starlike maps
for every $\alpha\neq 0$ and $\alpha\in[-2,2]$, and convex when
$\alpha\in[-1,1]$. In this manuscript we find the order of starlikness and
convexity of the lens maps in terms of the parameter $\alpha$.

###  2.1. Starlikeness

Let $f:{\mathbb{D}}\to{\mathbb{C}}$ be a locally univalent analytic mapping
normalized as before, such that the range of $f({\mathbb{D}})$ is a starlike
domain with respect to the origin. A well known analytical characterization of
starlikeness is given by

$\mbox{Re}\left\\{z\frac{f^{\prime}}{f}(z)\right\\}>0.$

See [3, 5]. For lens map $\ell_{\alpha}$, it is easy to see that

$z\frac{\ell_{\alpha}^{\prime}}{\ell_{\alpha}}(z)=\frac{4\alpha
z}{1-z^{2}}\cdot\frac{\left(\dfrac{1+z}{1-z}\right)^{\alpha}}{\left(\dfrac{1+z}{1-z}\right)^{2\alpha}-1}=\dfrac{4\alpha
z(1-z^{2})^{\alpha-1}}{(1+z)^{2\alpha}-(1-z)^{2\alpha}}.$

Thus, if $\alpha\in(1,2]$ this quantity tends to zero when $z$ goes to $\pm
1$, then

$\inf_{z\in{\mathbb{D}}}\mbox{Re}\left\\{z\frac{\ell_{\alpha}^{\prime}}{\ell_{\alpha}}(z)\right\\}=0,$

which means that $\ell_{\alpha}$ is starlike map with order 0. Since
$\ell_{\alpha}(z)=\ell_{-\alpha}(-z)$ then, for $\alpha\in[-2,-1)$,

$\inf_{z\in{\mathbb{D}}}\mbox{Re}\left\\{z\frac{\ell_{\alpha}^{\prime}}{\ell_{\alpha}}(z)\right\\}=\inf_{w\in{\mathbb{D}}}\mbox{Re}\left\\{w\frac{\ell_{-\alpha}^{\prime}}{\ell_{-\alpha}}(w)\right\\}=0.$

Now, for $\alpha\in[-1,1]$ the corresponding lens map is a convex mapping,
therefore is a starlike map with order $1/2$ at least. This is the fact in the
following theorem.

######  Theorem 1.

For $\alpha\in[-1,1]$, $\ell_{\alpha}$ is a starlike mapping with order
$\beta$, given by

$\beta=\dfrac{\alpha}{\sin\left(\dfrac{\pi}{2}\alpha\right)}.$

###### Proof.

A direct calculation shows that, for $|z|=1$ with $z\neq 1$ we have that

$\mbox{Re}\left\\{z\frac{\ell_{\alpha}^{\prime}}{\ell_{\alpha}}(z)\right\\}=2\alpha\cdot\mbox{Im}\left\\{\dfrac{z}{1-z^{2}}\right\\}\left(\dfrac{\mbox{Im}\\{\xi\\}}{|\xi-1|^{2}}+\dfrac{\mbox{Im}\\{\xi\\}}{|\xi+1|^{2}}\right).$

By the symmetry of the lens maps, we consider $z=e^{it}$ with $t\in(0,\pi)$
and its follows that

$\operatorname{Im}\left\\{\frac{z}{1-z^{2}}\right\\}=\frac{2\operatorname{Im}\\{z\\}}{\lvert
1-z^{2}\rvert^{2}}=\frac{1}{2\sin(t)},$

and

$\frac{\operatorname{Im}\\{\xi\\}}{\lvert
1+\xi\rvert^{2}}=\frac{b(t)\sin(\frac{\pi}{2}\alpha)}{1+2b(t)\cos(\frac{\pi}{2}\alpha)+b(t)^{2}},$

and

$\frac{\operatorname{Im}\\{\xi\\}}{\lvert
1-\xi\rvert^{2}}=\frac{b(t)\sin(\frac{\pi}{2}\alpha)}{1-2b(t)\cos(\frac{\pi}{2}\alpha)+b(t)^{2}}.$

where
$b(t)=|\xi(t)|=(\sin(t)/(1-\cos(t)))^{\alpha}=((1+\cos(t))/\sin(t))^{\alpha}$.
Thus

(3)
$\mbox{Re}\left\\{z\frac{\ell_{\alpha}^{\prime}}{\ell_{\alpha}}(z)\right\\}=\alpha\sin\left(\dfrac{\pi}{2}\alpha\right)\frac{b(t)}{\sin(t)}\left(\dfrac{2(b^{2}(t)+1)}{(b^{2}(t)+1)^{2}-4b^{2}(t)\cos^{2}\left(\dfrac{\pi}{2}\alpha\right)}\right),$

then

$\beta=\alpha\sin\left(\dfrac{\pi}{2}\alpha\right)\cdot\inf_{t\in(0,\pi)}\frac{b(t)}{\sin(t)}\left(\dfrac{2(b^{2}(t)+1)}{(b^{2}(t)+1)^{2}-4b^{2}(t)\cos^{2}\left(\dfrac{\pi}{2}\alpha\right)}\right).$

The relationship between $b(t)$ and $\sin(t)$ is given by

(4) $\sin(t)=\dfrac{2b(t)^{\frac{1}{\alpha}}}{1+b(t)^{\frac{2}{\alpha}}},\quad
t\in(0,\pi).$

Therefore, for any $t\in(0,\pi)$, let $x=b(t)$ be the real number that
decrease from $\infty$ to $0$, then the right hand in (3) is given by

$\alpha\sin\left(\dfrac{\pi}{2}\alpha\right)\cdot\frac{(1+b^{2/\alpha}(t))(b^{2}(t)+1)}{b^{1/\alpha-1}(t)\left((b^{2}(t)+1)^{2}-4b^{2}(t)\cos^{2}\left(\dfrac{\pi}{2}\alpha\right)\right)},$

which goes to infinity when $b(t)$ tends to 0, and when $b(t)$ tends to
$\infty$. Hence, the infimum is attained for some $t\in(0,\pi)$, therefore it
is a minimum named $m(\alpha)$. Thus

$\beta=\alpha\sin\left(\frac{\alpha\pi}{2}\right)\cdot m(\alpha).$

Let $g(x):(0,\infty)\to{\mathbb{R}}$ the real functions given by

$g(x)=\frac{x\left(1+x^{2}\right)}{\left(1+x^{2}\right)^{2}-4x^{2}\cos^{2}\left(\frac{\alpha\pi}{2}\right)}\cdot\frac{\left(1+x^{2/\alpha}\right)}{x^{\frac{1}{\alpha}}}=f(x)\cdot\frac{\left(1+x^{2/\alpha}\right)}{x^{\frac{1}{\alpha}}},$

then

$g^{\prime}(x)=f^{\prime}(x)\cdot\frac{\left(1+x^{2/\alpha}\right)}{x^{\frac{1}{\alpha}}}+f(x)\cdot\frac{2(x^{1/\alpha-1}-x^{3/\alpha-1})}{\alpha(1+x^{2/a})^{2}}.$

Here,

$f^{\prime}(x)=\frac{2\left((3x^{2}+1)\left(\left(1+x^{2}\right)^{2}-4x^{2}\cos^{2}\left(\frac{\alpha\pi}{2}\right)\right)-(x^{3}+x)(4x(x^{2}+1)-8x\cos^{2}(\frac{\pi\alpha}{2}))\right)}{\left(\left(1+x^{2}\right)^{2}-4x^{2}\cos^{2}\left(\frac{\alpha\pi}{2}\right)\right)^{2}}$

A straightforward calculation gave as the

$f^{\prime}(x)=\dfrac{2(1-x^{2})\left((1+x^{2})^{2}+4x^{2}\cos^{2}(\frac{\pi\alpha}{2})\right)}{\left(\left(1+x^{2}\right)^{2}-4x^{2}\cos^{2}\left(\frac{\alpha\pi}{2}\right)\right)^{2}}.$

Thus, evaluating at $x=1$ we have that

$g^{\prime}(1)=2f^{\prime}(1)=0.$

Moreover, for all $x\in(0,1)$ we have that $g^{\prime}(x)<0$ and for all $x>1$
it is follows that $g^{\prime}(x)>0$, therefore $g(x)$ has a unique critical
point at $x=1$ for positive real line, which is a minimum. Thus

$g(x)\geq g(1)=\frac{2}{4-4\cos^{2}(\frac{\pi\alpha}{2})}\cdot
2=\frac{1}{\sin^{2}(\frac{\pi\alpha}{2})}=m(\alpha),$

so the proof is finished. ∎

###  2.2. Convexity

Since, $\ell_{\alpha}$ is an analytic convex mappings, the real part is an
harmonic mappings with lower bound 0, therefore the minimum value of this real
part is attained in some point in $|z|=1$, then

$\beta=\inf_{z\in{\mathbb{D}}}\mbox{Re}\left\\{1+\frac{z\ell_{a}^{\prime\prime}}{\ell_{a}^{\prime}}(z)\right\\}=\min_{z\in\partial{\mathbb{D}}}\mbox{Re}\left\\{1+\frac{z\ell_{a}^{\prime\prime}}{\ell_{a}^{\prime}}(z)\right\\}.$

A direct calculation shows that

(5)
$\frac{\ell_{a}^{\prime\prime}}{\ell_{a}^{\prime}}=\frac{\xi^{\prime}}{\xi}+\frac{2z}{1-z^{2}}-\frac{2\xi^{\prime}}{\xi+1}=\frac{2\alpha}{1-z^{2}}+\frac{2z}{1-z^{2}}-\frac{4\alpha\xi}{\left(1-z^{2}\right)(\xi+1)},$

thus

$\displaystyle 1+\frac{z\ell_{a}^{\prime\prime}}{\ell_{a}^{\prime}}(z)$
$\displaystyle=1+\frac{2z^{2}}{1-z^{2}}+\frac{2\alpha
z}{1-z^{2}}-\frac{4\alpha z\xi}{\left(1-z^{2}\right)(1+z)}$
$\displaystyle=\frac{1+z^{2}}{1-z^{2}}+\frac{2\alpha z(1+\xi)-4\alpha\xi
z}{\left(1-z^{2}\right)(1+\xi)}$
$\displaystyle=\frac{1+z^{2}}{1-z^{2}}+\frac{2\alpha z-2\alpha
z\xi}{\left(1-z^{2}\right)(1+\xi)}$
$\displaystyle=\frac{1+z^{2}}{1-z^{2}}-\frac{2\alpha
z}{1-z^{2}}\cdot\frac{\xi-1}{\xi+1}.$

Therefore, taking the real part in the unit circle $|z|=1$ with $z\neq\pm 1$,
we have that

$\operatorname{Re}\left\\{\frac{1+z^{2}}{1-z^{2}}-\frac{2\alpha
z}{1-z^{2}}\cdot\frac{\xi-1}{\xi+1}\right\\}=-2\alpha\operatorname{Re}\left\\{\frac{z}{1-z^{2}}\cdot\frac{\xi-1}{\xi+1}\right\\}.$

Since $\operatorname{Re}\left\\{z/(1-z^{2})\right\\}=0$ when $|z|=1$, then

$-2\alpha\operatorname{Re}\left\\{\frac{z}{1-z^{2}}\cdot\frac{\xi-1}{\xi+1}\right\\}=2\alpha\operatorname{Im}\left\\{\frac{z}{1-z^{2}}\right\\}\operatorname{Im}\left\\{\frac{\xi-1}{\xi+1}\right\\}$

Then, we are searching for:

$\min_{z\in\partial{\mathbb{D}}}\left\\{2\alpha\operatorname{Im}\left\\{\frac{z}{1-z^{2}}\right\\}\operatorname{Im}\left\\{\frac{\xi-1}{\xi+1}\right\\}\right\\}.$

Is not difficult to see that, for all $|z|=1$ we have that

$\operatorname{Im}\left\\{\frac{z}{1-z^{2}}\right\\}=\frac{\operatorname{Im}\\{z\\}(1+|z|^{2})}{\lvert
1-z^{2}\rvert^{2}}=\frac{2\operatorname{Im}\\{z\\}}{\lvert
1-z^{2}\rvert^{2}},$

and

$\operatorname{Im}\left\\{\frac{\xi-1}{\xi+1}\right\\}=\operatorname{Im}\left\\{\frac{(\xi-1)(\bar{\xi}+1)}{\lvert\xi+1\rvert^{2}}\right\\}=\frac{2\operatorname{Im}\\{\xi\\}}{\lvert\xi+1\rvert^{2}}.$

Thus, an alternative version of the real part, for all
$z\in\partial{\mathbb{D}}$, is given by

$\operatorname{Re}\left\\{1+\frac{z\ell_{a}^{\prime\prime}}{\ell_{a}^{\prime}}(z)\right\\}=8\alpha\frac{\operatorname{Im}\\{z\\}\operatorname{Im}\\{\xi\\}}{\lvert\xi+1\rvert^{2}\lvert
1-z^{2}\rvert^{2}}.$

The following theorem is the main results of this manuscript.

######  Theorem 2.

$\ell_{\alpha}$ is a convex mapping with order $\beta$, given by

$\beta=\dfrac{\alpha\sin\left(\dfrac{\pi}{2}\alpha\right)}{1+\cos\left(\dfrac{\pi}{2}\alpha\right)}.$

###### Proof.

Let $z=e^{it}$ and $\xi(t)=\left(\dfrac{1+e^{it}}{1-e^{it}}\right)^{\alpha}$ ;
$t\in[0,2\pi]$

(6)
$f(t)=2\alpha\operatorname{Im}\left\\{\frac{e^{it}}{1-e^{2it}}\right\\}\operatorname{Im}\left\\{\frac{\xi(t)-1}{\xi(t)+1}\right\\}.$

Now, our effort will be to compute the minimum value of this positive
function. Since $\zeta(t)=(1+e^{it})/(1-e^{it})=i\sin(t)/(1-\cos(t))$ and
putting $\operatorname{Im}\\{\xi(t)\\}=b(t)\sin(\alpha\pi/2)$, we have that

(7) $|\xi(t)|=\left|\frac{\sin(t)}{1-\cos(t)}\right|^{\alpha},\quad
b(t)=\left\\{\begin{array}[]{ll}\quad\left(\frac{\sin(t)}{1-\cos(t)}\right)^{\alpha},&t\in(0,\pi)\\\\[8.5359pt]
-\left(\frac{-\sin(t)}{1-\cos(t)}\right)^{\alpha},&t\in(\pi,2\pi).\end{array}\right.$

From where, for any $\alpha\in(0,1]$, $b(t)$ decrease from $\infty$ to 0 when
$t$ runs from $0$ to $\pi$, and continuing been decreasing functions from 0 to
$-\infty$ when $t$ goes from $\pi$ to $2\pi$. Since, imaginary parts are given
by

$\operatorname{Im}\left\\{\frac{z}{1-z^{2}}\right\\}=\frac{2\operatorname{Im}\\{z\\}}{\lvert
1-z^{2}\rvert^{2}}=\frac{1}{2\sin(t)},$

and

$\operatorname{Im}\left\\{\frac{\xi(t)-1}{\xi(t)+1}\right\\}=\frac{2\operatorname{Im}\\{\xi\\}}{\lvert
1+\xi\rvert^{2}}=\frac{2b(t)\sin(\frac{\pi}{2}\alpha)}{1+2b(t)\cos(\frac{\pi}{2}\alpha)+b(t)^{2}}.$

Then

$f(t)=\frac{2\alpha
b(t)\sin\left(\frac{\pi}{2}\alpha\right)}{1+2b(t)\cos\left(\frac{\pi}{2}\alpha\right)+b(t)^{2}}\cdot\frac{1}{\sin(t)}.$

For $t\in(0,\pi)$, $b(t)$ satisfies that

$b(t)=\left(\dfrac{\sin(t)}{1-\cos(t)}\right)^{\alpha}=\left(\dfrac{1+\cos(t)}{\sin(t)}\right)^{\alpha}.$

Thus, if $t\to 0^{+}$ then

$f(t)=\frac{2\alpha
b(t)\sin\left(\frac{\pi}{2}\alpha\right)}{1+2b(t)\cos\left(\frac{\pi}{2}\alpha\right)+b(t)^{2}}\cdot\frac{b(t)^{1/\alpha}}{(1+\cos(t))}\sim
b(t)^{1/\alpha-1},$

and $f(t)\to\infty$, since $b(t)$ goes to infinity. On the other hand, if
$t\to\pi^{-}$, then

$f(t)=\frac{2\alpha\sin(t)^{\alpha}\sin\left(\frac{\pi}{2}\alpha\right)}{1+2b(t)\cos\left(\frac{\pi}{2}\alpha\right)+b(t)^{2}}\cdot\frac{1}{(1-\cos(t))^{\alpha}\sin(t)}\sim\dfrac{1}{\sin(t)^{1-\alpha}},$

goes to infinity. Now, if $t\in(\pi,2\pi)$ we have that

$f(t)=-\frac{2\alpha(-\sin(t))^{\alpha}\sin\left(\frac{\pi}{2}\alpha\right)}{1-2b(t)\cos\left(\frac{\pi}{2}\alpha\right)+b(t)^{2}}\cdot\frac{1}{(1-\cos(t))^{\alpha}\sin(t)}\sim\frac{1}{(-\sin(t))^{1-\alpha}},\quad
t\sim\pi^{+}.$

Therefore $f(t)\to\infty$ when $t\to\pi^{+}$. Analogously, one can proved that
$f(t)\to\infty$ when $t\to 2\pi^{-}$. Hence, the minimum value of $f(t)$ is
attained for $t\in(0,\pi)\cup(\pi,2\pi)$. From equation (7), its follows that
the relationship between $b(t)$ and $\sin(t)$ is given by

(8) $\sin(t)=\dfrac{2b(t)^{\frac{1}{\alpha}}}{1+b(t)^{\frac{2}{\alpha}}},\quad
t\in(0,\pi);\quad\quad\sin(t)=\dfrac{-2(-b(t))^{\frac{1}{\alpha}}}{1+(-b(t))^{\frac{2}{\alpha}}},\quad
t\in(\pi,2\pi).$

$b(t)^{1/\alpha}\sin(t)=1+\cos(t)$. Thus, for all $t\in(0,\pi)$ or
$t\in(\pi,2\pi)$ we obtain

$b^{\frac{1}{a}}\sin{t}=1\pm\sqrt{1-\sin{t}^{2}},$

which implies that
$b^{\frac{2}{\alpha}}\sin^{2}(t)-2b^{\frac{1}{\alpha}}\sin(t)=-\sin^{2}(t)$,
therefore

$\sin(t)=\frac{2b(t)^{\frac{1}{\alpha}}}{1+b(t)^{\frac{2}{\alpha}}}.$

Now, using the first part of (8) we can rewrite $f(t)$ for all $t\in(0,\pi)$
as:

(9)
$g(b)=f(t(b))=\frac{2\alpha(1+b^{\frac{2}{\alpha}})\sin{(\frac{\pi}{2}\alpha)}}{b^{\frac{1}{\alpha}-1}+2b^{\frac{1}{\alpha}}\cos{(\frac{\pi}{2}\alpha)}+b^{1+\frac{1}{\alpha}}}:[0,\infty)\to{\mathbb{R}}^{+}.$

Thus, the minimum value of $f(t)$ in $t\in(0,\pi)$ is the minimum value of
$f(b)$ in $b\in(0,\infty)$. We shall show that

$\min_{b\in(0,\infty)}f(b)=f(1)=\dfrac{4\sin\left(\dfrac{\pi}{2}\alpha\right)}{1+\cos\left(\dfrac{\pi}{2}\alpha\right)}.$

Consider $x=b^{1/\alpha}$, then $x$ left in the same interval. Thus, the
corresponding function $g(x)=f(x^{\alpha})/\alpha\sin(\alpha\pi/2)$ satisfies
that $g:(0,\infty)\to{\mathbb{R}}$ and

$g(x)=\dfrac{1+x^{2}}{x^{1-\alpha}+2x\cos(\alpha\pi/2)+x^{1+\alpha}},\quad\alpha\in[0,1].$

Thus, a straightforward calculations show that

$g^{\prime}(x)=\dfrac{(1+\alpha)x^{\alpha}(x^{2-2\alpha}-1)+2\cos(\alpha\pi/2)(x^{2}-1)+(1-\alpha)x^{-\alpha}(x^{2+2\alpha}-1)}{(x^{1-\alpha}+\cos(\alpha\pi/2)x+x^{1+\alpha})^{2}},$

which is positive when $x>1$, since every terms in the numerator of
$g^{\prime}(x)$ is positive, and is negative when $x<1$, for same reason as
before. However, one can see that $g^{\prime}(1)=0$ which implies that $g$
attained its minimum value at $x=1$. Thus, the minimum value of $f$ is
$\alpha\sin(\alpha\pi/2)g(1)=f(1)$.

Now, for values $t\in(\pi,2\pi)$ by the symmetry of lens-shape, the arguments
as holds. ∎

## References

  * [1] Baricco, G.A.; Rodríguez Ringach, E.; Sanz, J.; Olivero, A.M.; Safar, F. Conformal mapping-based image processing: theory and applications. Journal of Visual Communication and Image Representation, 6 (3), 88-92, (1994).

  * [2] Chuaqui, M.; Hernández, R.; Martín, M. J. Affine and linear invariant families of harmonic mappings. Math. Ann. 367, número 3-4, 1099–1122, (2017).

  * [3] Duren P. L., Univalent functions, Springer-Verlag, New York, (1983).

  * [4] E. Schwartz and C. Frederick, Vision: Conformal Image Warping, IEEE Computer Graphics and Applications, 10 (2), 54-61, (1990).

  * [5] Graham, I., Kohr, G., Geometric Function Theory in One and Higher Dimensions, Marcel Dekker Inc., New York, (2003).

  * [6] Nehari, Z., A property of convex conformal maps. J. Analyse Math. 30, 390–393, (1976).

  * [7] Nehari, Z., Conformal Mapping, Dover Publications, New York, (1972).

  * [8] Robertson, M.I.S., On the theory of univalent functions. Annals of Mathematics 37(2), 374–408, (1936).


# A Game Theoretic Perspective on Network Topologies

Shaun Lichter, Christopher Griffin, and Terry Friesz

(April 4, 2011)

###### Abstract

We extend the results of Goyal and Joshi (S. Goyal and S. Joshi. Networks of
collaboration in oligopoly. Games and Economic behavior, 43(1):57-85, 2003),
who first considered the problem of collaboration networks of oligopolies and
showed that under certain linear assumptions network collaboration produced a
stable complete graph through selfish competition. We show with nonlinear cost
functions and player payoff alteration that stable collaboration graphs with
an arbitrary degree sequence can result. As a by product, we prove a general
result on the formation of graphs with arbitrary degree sequences as the
result of selfish competition. Simple motivating examples are provided and we
discuss a potential relation to Network Science in our conclusions.

##  1 Introduction

In this paper we model the emergence of collaborations among players (e.g.,
firms) as a strategic network formation game [DM97], by allowing selfish
agents to choose with which other agents they would like to form a link. Each
agent has the option to deny a link to another agent, so the formation of a
link requires the cooperation of both players. A value function assigns a
value to each particular graph and this value is distributed to agents by an
allocation function (or allocation rule). This distribution of value drives a
player’s preference for particular graph structures. The primary objective of
this paper is to extend and generalize a model by Goyal and Joshi [GJ03] for
collaboration of oligopolistic firms to provide a model that, under different
conditions, admits a stable collaboration graph with symmetric or asymmetric
degree distributions. The primary contribution of this work is showing that
nonlinear pricing and collaboration incentives exist to create arbitrary
stable network structures. This extends the work of Goyal and Joshi who showed
that linear pricing schemes lead to stable graphs that are complete only. Thus
the occurrence of exotic graphs (e.g., power law graphs) in natural
collaborations may simply be the result of nonlinear incentives.

In particular circumstances a modeler may wish to predict how a network will
change if it is perturbed in some way. Specifically, a network may be changed
by a player entering or exiting the game or when a link is added or deleted.
For example, Verizon might be interested in knowing if AT&T and T-Mobile
merged, whether the new network would be stable and how the merger might
affect the market. Models that take a statistical in nature provide forecasts
for the behavior of large networks, since bulk measures are used, but have
difficulty predicting the stability of smaller network of interest.
Unfortunately, the models developed in this paper also have some limitations
in that they require some knowledge of the objective functions of players.
Further, the models developed in this paper are static models which provide
insight into the stability of particular networks, but predictive capabilities
may require a dynamic model of objective functions. These two limitations are
discussed further in Section 6 and are the driving motivation of continued
work in this area. Nonetheless, the models developed in this paper provide a
foundation to develop modeling approaches that can predict the reaction of
networks to specific changes that may take place.

The research on network formation games is extensive. We summarize a few key
results germane to our presentation. Myerson [Mye77] considers cooperation
structures, which we call graphs, but he considers only whether agents are
connected, not the structure of the graph of connections. Nonetheless, Myerson
was the first to consider the strategic formation of networks.

Jackson and Wolinsky model social relationships where each player receives
benefits at a cost from their friends and a lower benefit from friends of
friends, but with no cost. Jackson and Wolinsky investigate network formation
via the stability of particular graph structures [JW96]. An efficient graph
structure is one with the maximum value, that is, the total value of all
agents is maximized (see Section 2 for a mathematical definition). Jackson and
Wolinksy found that efficient graph structures are not always stable, but
their analysis used pairwise stability (see Section 2), which restricts the
capabilities of agents and assumes a symmetric allocation rule.

Dutta and Mutuswami construct an allocation rule that ensures the existence of
a strongly stable efficient graph where the allocation rule is symmetric on
this subset of strongly stable graphs [DM97]. Bala and Goyal [BG00] consider a
model where links allow access to a noncompetitive product such as
information. The cost of a link is attributed to the agent initiating the
formation of the link.

Furusawa and Konishi [FK07] model free trade networks in which a link between
countries represents a free trade agreement and the absence of a link results
in a tariff. The supply and demand functions then induce a value function and
allocation rules over the countries. Belleflamme and Bloch [BB04] model market
sharing between firms where a link between two firms represents an agreement
not to infringe on each other’s market and the absence of a link implies the
firms will compete in the same market. Again, supply and demand induce a value
function and an allocation rule over the firms. Labor markets [CAJ07] and co-
author networks [JW96] have also been modeled using game theoretic networks.

Networks allow a model to portray intricate relationships among players that
cannot otherwise be described. For example, non-transitive relationships may
be modeled as in the case when (e.g.), Player 1 is connected to Players 2 and
3, but Players 2 and 3 are not connected to one another. This generality leads
to another important aspect of a network model: how do relationships of one
pair of players affect a third player? In some cases, a positive benefit may
be reaped by an outside party; other times, a negative affect may be imposed
on an outside party. Networks allow relationships to be modeled as an
externality for outside players, but the nature of the externality is
dependent on the application and the model. Currarini [Cur02] investigates the
nature of externalities in networks by modeling the value of a graph as a
function of the components of the graph. Particularly, any graph is
partitioned into one or more components and the value may be a function of the
partition.

The remainder of this paper is organized as follows: In Section 2 we provide
notation used throughout the remainder of this paper. In Section 3 we state
and prove a general result on game theoretic constructions of graphs with
arbitrary degree sequences. In Section 4 we apply this result to extend the
work of Goyal and Joshi [GJ03] and provide the main results of the paper. In
Section 5 we provide conclusions and suggest a bridge between this work and
recent work in Network Science. Finally in Section 6 we discuss future
directions of this research as well as new research directions that would make
this work more applicable to the analysis of real-world organizations.

##  2 Notational Preliminaries

We follow the notational conventions common in the graph formation literature
[JW96, DM97, Jac03]. Let $N=\\{1,2,\ldots n\\}$ be the set of nodes in a
graph, which will represent the players. In the case of oligopolies, a firm is
considered a player. The set of links in the graph is a set of pairs of nodes
(subsets of $N$ of size two). A graph $g$ is a set of links (set of subsets of
$N$ of size two). The graph $g^{c}$ is the complete graph (all subsets of $N$
of size two) and $G$ is the set of all graphs over the node set $N$, that is,
$G=\\{g:g\subseteq g^{c}\\}$. For a graph $g\in G$, the graph $g+ij$ is the
graph in which link $ij$ is added to $g$ while $g-ij$ is the graph in which
link $ij$ is removed from graph $g$. Let $\eta_{i}(g):G\rightarrow\mathbb{R}$
denote the degree of node $i$ in graph $g$ and
$\eta(g):G\rightarrow\mathbb{R}^{n}$ be the degree sequence of the graph $g$;
i.e., $\eta(g)=(\eta_{1}(g),\eta_{2}(g),\ldots,\eta_{n}(g))$. Let $[g]_{\eta}$
be the equivalence class of graphs with the same degree sequence as $g$. A
degree sequence $\mathbf{d}=\\{d_{1},\dots,d_{n}\\}$ on $n$ nodes is
graphical, if there exists a graph $g$ with $n$ nodes that has degree sequence
$\mathbf{d}$. Equivalently, a degree sequence $\mathbf{d}$ is graphical if
$\eta^{-1}(\mathbf{d})\neq\emptyset$.

The value of a graph $g$ is the total value produced by agents in the graph;
we denote the value of a graph as the function $v:G\rightarrow\mathbb{R}$ and
the set of all such value functions as $V$. A graph $g$ is strongly efficient
if $v(g)\geq v(g^{\prime})\;\;\forall\;g^{\prime}\in G$. An allocation rule
$Y:V\times G\rightarrow\mathbb{R}^{N}$ distributes the value $v(g)$ among the
agents in $g$. Denote the value allocated to agent $i$ as $Y_{i}(v,g)$. Since,
the allocation rule must distribute the value of the network to all players,
it must be balanced; i.e., $\sum_{i}Y_{i}(v,g)=v(g)$ for all $(v,g)\in V\times
G$. The allocation rule governs how the value of the graph is distributed and
thus plays a significant role in the model. The allocation rule may be used to
model a free market, utilities of players, or system rules such as taxation or
the provision of subsidies to particular players. Throughout this paper, we
denote the game $\mathcal{G}=\mathcal{G}(v,Y,N)$ as the game played with value
function $v$ and allocation rule $Y$ over nodes $N$.

The strategy set of Player $i$, $S_{i}$, is the set of nodes to which Player
$i$ may request to link and $S=\prod_{i\in N}{S_{i}}$ is the strategy space
for all players. The graph $g$ induced by strategy $s\in S$ is
$g(s)=\\{ij:j\in s_{i},i\in s_{j}\\}$. Here $s_{i}\in S_{i}$ is the strategy
for Player $i$ in the overall strategy $s$.

The payoff of Player $i$ is defined as $f^{\mathcal{G}}_{i}(s)=Y_{i}(v,g(s))$.
This is interpreted as the payoff that player $i$ receives from the strategy
$s$ in game $\mathcal{G}$ and is the proportion of the value $v(g(s))$
distributed by $Y$. This model admits a Nash equilibrium in which each player
chooses to link with no other players and no network forms. Various authors
argue that this is an inadequacy and therefore it is necessary to make
refinements to the notion of equilibrium [Jac03, DM97].

Jackson and Wolinksy use pairwise stability to model stable networks without
the use of non-cooperative Nash equilibrium [JW96].

######  Definition 2.1.

A network $g$ with value function $v$ and allocation rule $Y$ is pairwise
stable if (and only if):

for all $ij\in g$, $Y_{i}(v,g)\geq Y_{i}(v,g-ij)$ and

for all $ij\not\in g$, if $Y_{i}(v,g+ij)>Y_{i}(v,g)$, then
$Y_{j}(v,g+ij)<Y_{j}(v,g)$

Pairwise stability implies that in a stable network, for each link that
exists, (1) both players must benefit from it and (2) if a link can provide
benefit to both players, then it in fact must exist. Jackson notes that
pairwise stability may be too weak because it does not allow groups of players
to add or delete links, only pairs of players [Jac03]. Deletion of multiple
links simultaneously has been considered in [BB04].

Goyal and Joshi [GJ06] provide a model that allows a player’s allocation to be
dependent on the number of links the player has. That is:

$Y_{i}(g)=\pi_{i}(g)-\gamma\eta_{i}(g)$ (1)

Here $\pi_{i}$ is a profit function, $\eta_{i}(g)$ is the number of links
player $i$ has in $g$, and $\gamma$ is a link maintenance cost. However,
$\gamma$ may be negative to model a benefit of having more links. The value
function is then defined implicitly so that $Y_{i}(g)$ is a balanced
allocation rule.

##  3 A General Result on Graph Stability

In this section, we show how to construct an allocation rule $Y_{i}(g)$ to
ensure that a graph with a given degree sequence is stable. To do this, we
present a set of properties for the objectives of players that result in a
stable graph with an arbitrary degree sequence. Recall, a stable network is
one in which no player has an incentive to drop a link or request an
additional link to a player who reciprocates such an incentive. Consider the
scenario where for $i=1,\dots,n$, Player $i$ has a desired degree $k_{i}$. For
example, some scientific authors may like to collaborate with only a few
individuals, while some like to collaborate with many others. Ultimately, when
a collaboration network is formed, each player $i$ receives the number of
links given by $\eta_{i}(g)$. In the game where each player’s objective
penalizes them for incurring a degree $\eta_{i}(g)$ not equal to their desired
degree $k_{i}$ (under some conditions), the graph with a degree distribution
of $k=(k_{1},k_{2},\ldots,k_{n})$ will be stable.

With a slight abuse of the notation from Section 2, we first define an
allocation (payoff) to each player $i$ as $Y_{i}:G\rightarrow\mathbb{R}$ which
is consistent with an allocation function $Y:G\times V\rightarrow\mathbb{R}$
and an induced value function $V:G\rightarrow\mathbb{R}$ with
$v(g)=\sum_{i}{Y_{i}(g)}$.

######  Theorem 3.1.

Let $\mathbf{d}=(k_{1},\dots,k_{n})$ be a desired degree sequence for $n$
players in the node set $N$. Assume that Player $i$ wishes to maximize
objective $Y_{i}(g)=-f_{i}(\eta_{i}(g))=-f(\eta_{i}(g)-k_{i})$ (or minimize
$f_{i}(\eta_{i}(g))=f(\eta_{i}(g)-k_{i})$), where
$f:\mathbb{R}\rightarrow\mathbb{R}$ is a convex function with minimum at $0$.
Let $v$ be the balanced value function induced from the allocation rule
$Y=(Y_{1},\dots,Y_{n})$. If $\eta^{-1}(\mathbf{d})$ is non-empty (i.e.,
$\mathbf{d}$ is graphic) then any graph $g$ such that $\eta(g)=\mathbf{d}$ is
pairwise stable for the the game $\mathcal{G}(v,Y,N)$.

###### Proof.

Let $g\in\eta^{-1}(\mathbf{d})$ be a graph so that $\eta_{i}(g)=k_{i}$ and let
$g-ij$ be the graph $g$ after the link $ij$ is dropped from $g$ and define
$g+ij$ to be the graph $g$ after the link $ij$ is added to graph $g$. Observe
that:

$\displaystyle\eta_{i}(g-ij)=k_{i}-1,\quad\eta_{j}(g-ij)=k_{j}-1,\quad\eta_{l}(g-ij)=k_{l},$
$\displaystyle\eta_{i}(g+ij)=k_{i}+1,\quad\eta_{j}(g+ij)=k_{j}+1,\quad\eta_{l}(g+ij)=k_{l}$

where $l\not\in\\{i,j\\}$

Since $f$ is convex with minimum at $0$ and each $f_{i}$ are simply shifts of
$f$ so that they are minimized at $k_{i}$, we know that $f_{i}(k_{i})$ is a
minimum of the function $f_{i}$. Thus $Y_{i}(g)$ is maximized when
$g\in\eta^{-1}(\mathbf{d})$. It now suffices to confirm pairwise stability:

$\displaystyle
Y_{i}(\eta_{i}(g-ij))-Y_{i}(\eta_{i}(g))=Y_{i}(k_{i}-1)-Y_{i}(k_{i})<0$
$\displaystyle
Y_{i}(\eta_{i}(g+ij))-Y_{i}(\eta_{i}(g))=Y_{i}(k_{i}+1)-Y_{i}(k_{i})<0$

Thus graph $g\in\eta(\mathbf{d})$ is stable because there is no firm $i$
willing to drop an arbitrary existing link $ij$ or add an arbitrary missing
link $ij$. ∎

######  Remark 3.2.

From Theorem 3.1 it is interesting to note that the stability of the class
$\eta^{-1}(\mathbf{d})$ is not unique. We can illustrate this fact using the
following counterexample. Let $\mathbf{d}=(1,1,1,2,3)$ with
$N=\\{1,\dots,5\\}$ and let $f(x)=x^{2}$, a simple convex function with
minimum at zero, from the theorem. The following two networks are both
pairwise stable solutions to the game $\mathcal{G}=(v,Y,N)$:

Figure 1: We illustrate two graphs that are both pairwise stable for degree
sequence $\mathbf{d}=(1,1,1,2,3)$ with $f(x)=x^{2}$ in Theorem 3.1

.

It should be clear however, that the second graph is not a Pareto optimal
solution to the problem. Pareto optimality of the class of graphs
$\eta^{-1}(\mathbf{d})$ follows a posteriori from the proof of Theorem 3.1.

######  Corollary 3.3.

Assume the conditions from Theorem 3.1. A graph $g$ is a pairwise stable and
Pareto optimal solution to the game $\mathcal{G}(v,Y,N)$ if and only if
$\eta(g)=\mathbf{d}$.

###### Proof.

The fact that $\mathbf{d}$ is graphic implies that there is some graph
$g\in\eta^{-1}(g)$ and furthermore $Y_{i}(g)$ is maximized for all
$i=1,\dots,n$. Therefore any change in strategy cannot improve any player’s
current payoff. Thus, $g$ is Pareto optimal and pairwise stable.

If $g^{\prime}\not\in\eta^{-1}(\mathbf{d})$ then while $g^{\prime}$ may be
pairwise stable, it cannot be Pareto optimal since there is some other graph
$g\in\eta^{-1}(\mathbf{d})$ so that $Y_{i}(g)>Y_{i}(g^{\prime})$ for some
$i\in N$. ∎

######  Example 3.4.

Suppose that we want the degree distribution of a stable graph that results
from playing the game described in Theorem 3.1 to have a power law degree
distribution. We embed this into the objectives of the players, so the
resulting graph has the proper distribution. Let $N=100$ players attempt to
minimize their cost function

$f(\eta_{i}(g))=(\eta_{i}(g)-k_{i})^{2}+\psi$

where $\psi=2$ and the parameters of each player ($k_{i}$) are given in the
following table:

Node(s) | $k_{i}$
---|---
1-75 | 1
76-89 | 2
90-94 | 3
95-96 | 4
97 | 5
98 | 6
99 | 7
100 | 8

The distribution of values of $k_{i}$ forms an approximate (with rounding to
integers) power law distribution. This is illustrated in Figure 2:

Figure 2: The empirical desired distribution of the degrees of the players.
This degree distribution follows an approximate power law distribution.

Figure 3 illustrates one realization of a power law graph with the desired
degree distribution.

Figure 3: Sample pairwise stable collaboration Network for 100 nodes.

We can test the stability of any graph $g$ with $\eta_{i}(g)=k_{i}$. In doing
so, we observe that any graph with this distribution must be both stable
(since there is no motivation for any player to alter her configuration within
the network) and Pareto optimal.

We can experimentally analyze this simple game to determine the nature of the
average network produced during play. For a simple experiment, 100 pairwise
stable graphs were generated and some of their properties analyzed. To build
these pairwise stable graphs, we used the following procedure:

An empty graph was initialized.

Two vertices that had degree less than their desired degree were chosen at
random without replacement.

These two vertices were joined by an edge.

The graph was checked for pairwise stability. If the graph was pairwise
stable, the graph was returned. Otherwise, we continued at Step 2. Results are
shown in Figure 4.

Figure 4: Experimental results from 100 pairwise stable graphs that result
when the given degree distribution is used with the objective
$f(\eta_{i}(g))=(\eta_{i}(g)-k_{i})^{2}+\psi$.

The left histogram shows the similarity between the degree specified degree
distribution and the mean degree distribution of the ensemble of graphs
generated. A more interesting plot is the mean objective function value on a
per-player basis (with error bars). This graph indicates that most players
successfully minimize their objective value (to zero) and that the players
with the worst ability to optimize their objective functions are players with
high degree requirements. It is interesting to note that these results are a
function of the routine used to compute pairwise stable graphs. We also tried
using a modified version of the preferential attachment algorithm:

An empty graph was initialized.

Two vertices that had degree less than their desired degree and with highest
desired degree where chosen at random.

These two vertices were joined by an edge.

The graph was checked for pairwise stability. If the graph was pairwise
stable, the graph was returned. Otherwise, we continued at Step 2. Using this
algorithm, in 100 simulation runs a graph with the proscribed degree sequence
was always returned111Maple code for these experiments is available upon
request from the authors..

##  4 Application to Collaboration in Oligopoly

We present an application of the network formation game to firm collaboration
in oligopolies, which is an extension to the firm collaboration presented by
Goyal and Joshi in [GJ03]. We show the conditions under which a firm
collaboration network with an arbitrary degree sequence will be stable.

The number of firms participating in collaborative agreements (e.g., sharing
resources such as equipment, laboratory space, office space, engineers and
scientists through separate R & D subcompanies) has significantly increased
within industries that are R & D intensive [HS90, Hag93, HS94, Hag96, HLV00,
Hag02], sparking research investigating the incentives for such collaboration.

Goyal and Joshi examine the incentives for collaboration and the interaction
of these incentives under market competition using a model of horizontal
oligopolistic firm collaboration. In this model, firms compete in the market
after choosing collaborators [GJ03]. Goyal and Joshi provide theoretical
analysis on various models with varying levels of link formation costs
relative to production costs. They assume that collaboration requires a fixed
cost from each firm. These models investigate collaboration agreements where
the collaboration reduces the cost of production. This prior work assumes a
constant return to scale cost function, which they admit is a restrictive
assumption, although it has been made by others in the collaborative R & D
literature [Blo95].

###  4.1 Previous Results on Network Stability in Oligopoly

Following [GJ03], consider an oligopoly composed of $n$ firms, each of whom
may collaborate with any of the other $n-1$ firms. Firm $i$ produces a
quantity $q_{i}$ of a product. Collaboration among firms affects the marginal
cost of production. Thus a particular (collaboration) graph $g$ induces a
marginal cost vector $c(g)\in\mathbb{R}^{n}$ in which $c_{i}(g)$ is the
marginal cost of firm $i$ under collaboration graph $g$. It is assumed that
the marginal cost decreases for a firm $i$ as the number of collaborators
increase. For many of the models in [GJ03], it is assumed that the marginal
cost of firm $i$ linearly decreases with the number of collaborators for firm
$i$:

$c_{i}(g)=\gamma_{0}-\gamma\eta_{i}(g)$ (2)

where, as before, $\eta_{i}(g)$ is the number of links for firm $i$ and
$\gamma_{0}$ is the marginal cost of production when a firm has no links.
Notice that $\gamma_{0}$ is constant for all firms. Given a network $g$, there
is an induced set of costs which, along with the demand functions, produces a
set of profit functions for each firm, $Y_{i}(g)$ (the allocation of payoff
for player $i$). These profit functions then induce a Nash equilibrium of
production, which provides the precise allocation rule (i.e., profit) for each
firm on the graph. The stability of the collaboration network can then be
analyzed as in Section 3.

One example that Goyal and Joshi [GJ03] study is that of a homogenous product
oligopoly. The market marginal price function (dependent on quantity produced)
is given by

$P(Q)=\alpha-\sum_{i\in N}q_{i}$ (3)

where $Q=\sum_{i\in N}q_{i}$. Using Equation 2, the resulting profit to Player
$i$ is:

$Y_{i}(g)=\left(\alpha-\sum_{i\in
N}q_{i}\right)q_{i}-\left(\gamma_{0}-\gamma\eta_{i}(g)\right)q_{i}=(\alpha-\gamma_{0})q_{i}-\left(\sum_{i\in
N}q_{i}\right)q_{i}-\left(-\gamma\eta_{i}(g)\right)q_{i}$ (4)

Given a collaboration network $g$ and marginal cost and demand induced by
network $g$ we can use Expression 4 to find the quantity produced by each firm
at Cournot equilibrium using the standard Cournot oligopoly production
formulation [Tri88, GJ03]:

$q_{i}=\frac{\alpha-\gamma_{0}+n\gamma\eta_{i}(g)-\gamma\sum_{j\neq
i}\eta_{j}(g)}{n+1}$ (5)

The fact that $q_{i}$ is a function of the collaboration graph $g$ implies
that the quantities: $P$, $Q$ and $c_{i}$ are all functions of $g$. We will
refer to these quantities in this way in the sequel.

There is no natural market force in this model to ensure that a firm does not
produce a negative quantity. Instead, Goyal and Joshi restrict the parameters
by looking at the case where firm $i$ has no collaborators ($\eta_{i}(g)=0$)
and all others have a maximum number of collaborators ($\eta_{j}(g)=n-2$ for
all $j\neq i$) and forcing the quantity production to remain non-negative;
i.e.:

$\alpha-\gamma_{0}-\gamma(n-1)(n-2)\geq 0$ (6)

Goyal and Joshi show that with marginal cost (2) and market demand (3), the
complete network is the unique stable network [GJ03]. They point out that the
positive contribution to profit obtained by a collaboration link is on the
order of $n\gamma$ and the negative contribution to profit is on the order of
$\gamma$, so the net profit is on the order of $(n-1)\gamma$, which leads to a
firm’s incentive to saturate all of its possible links, thus making the
complete graph stable.

######  Example 4.1.

We present a numerical example of the result from [GJ03]. Let $N=5$ firms
compete in an oligopoly with inverse demand function $P=100-Q$, fixed cost
$\gamma_{0}=5$, and $\gamma=1$. Then we can see that:

$\alpha-\gamma_{0}-\gamma(n-1)(n-2)=100-5-(4)(3)=95-12=83>0$ (7)

This enforces the non-negativity of production. Since the marginal cost of
Player $i$ ($i=1,\dots,5$) decreases as its degree increases (from Equation 2)
it is easy to see that players will prefer as many links as possible. Thus,
the complete graph must be stable.

######  Remark 4.2.

The fundamental limitation to Goyal and Joshi’s work lies in the model
complexity. Maintaining collaborations is costly and each additional
collaboration may contribute less to the marginal cost than the collaboration
before it. Additionally, Goyal and Joshi’s model admits only complete
collaboration networks, omitting any other type of collaboration network. The
remainder of the paper illustrates how to generalize this result to graphs
with arbitrary degree sequences.

###  4.2 Results of Nonlinear Cost on Stability

In this section we study the effect a nonlinear variation on the marginal cost
function has on the stability of collaboration structures. We consider a
marginal cost function:

$c_{i}(g)=\gamma_{0}+f_{i}(\eta_{i}(g))$ (8)

where $f_{i}$ is some function $f_{i}:\mathbb{R}\rightarrow\mathbb{R}$. We
present two Theorems:

Theorem 4.11 extends the results from Goyal and Joshi [GJ03] to the case where
firms receive decreasing marginal benefit from collaboration via a nonlinear
decrease in production cost. This extension allows the parameter space to be
considerably less restricted than the result in [GJ03].

Theorem 4.7 shows that if the functions $f_{i}$ have minima and the parameter
space is restricted to keep production quantities nonnegative, then the
collaboration network in the oligopolistic competition model will have a graph
corresponding to the arbitrary degree sequence in the prior section. As a
result, this is a particular application of Theorem 3.1, to a general
collaboration game. To prove our theorems, we alter the assumptions on the
functions $f_{i}$ from the marginal cost (Expression 8). Theorem 4.7 requires
convex functions $f_{i}$ where as Theorem 4.11 requires $f_{i}$ to be a
decreasing and convex function.

######  Lemma 4.3.

Suppose we have an oligopoly consisting of $n$ firms in which collaboration is
defined by the graph $g$ and the profit function (allocation rule) for Firm
$i$ in that oligopoly is given by:

$Y_{i}(g,q(g))=(\alpha-\gamma_{0})q_{i}(g)-\left(\sum_{j\in
N}q_{j}\right)q_{i}(g)-(f_{i}(\eta_{i}(g)))q_{i}(g)$ (9)

then the quantity produced for firm $i$ is:

$q_{i}(g)=\frac{\alpha-\gamma_{0}-nf_{i}(\eta_{i}(g))+\sum_{j\neq
i}f_{j}(\eta_{j}(g))}{n+1}$ (10)

###### Proof.

From [Tri88], for any oligopoly with profit function of the form:

$Y_{i}(q)=aq_{i}-\left(\sum_{j\in N}q_{j}\right)q_{i}-b_{i}q_{i}$ (11)

The resulting Cournot equilibrium point on quantities is:

$q_{i}=\frac{a-nb_{i}+\sum_{j\neq i}b_{j}}{n+1}$ (12)

In our case, we have:

$\displaystyle a=\alpha-\gamma_{0}$ $\displaystyle
b_{i}=f_{i}(\eta_{i}(g))\quad\forall i$

Substituting these definitions into Expression (12) yields Expression (10).
This completes the proof. ∎

######  Remark 4.4.

It is worth noting that when for each firm $i$, $b_{i}=-\gamma\eta_{i}(g)$
then the cost function (2) and induced equilibrium quantity (5) is retrieved
from Goyal and Joshi.

######  Corollary 4.5.

Suppose that $f$ is a convex function that has a minimum at $0$. Further,
suppose $f_{i}(\eta_{i}(g))=f(\eta_{i}(g)-k_{i})$ where
$k_{i}\in\\{1,2,\ldots,n-1\\}$. If the parameters $\alpha$ and $\gamma_{0}$
and the function $f$ are such that:

$\alpha-\gamma_{0}-n\max(f(n-1),f(1-n))-\frac{1}{2}(n-1)\max(f(1)-f(0),f(-1)-f(0))>0$
(13)

and $n\geq 2$, then the Cournot equilibrium point quantities (10) are
nonnegative for all firms and for all collaboration graphs and the two
inequalities are true:

$\displaystyle 2q_{i}(g)-\frac{n-1}{n+1}[f(1)-f(0)]$ $\displaystyle>0$ (14)
$\displaystyle 2q_{i}(g)-\frac{n-1}{n+1}[f(-1)-f(0)]$ $\displaystyle>0$ (15)

###### Proof.

Since $n\geq 2$ and $f$ is convex and has a minimum at $0$, this implies that
$\frac{n-1}{n+1}[f(1)-f(0)]$ and $\frac{n-1}{n+1}[f(-1)-f(0)]$ are non-
negative. Hence, (14) and (15) imply that $q_{i}(g)$ is non-negative and hence
it suffices to only show that (14) and (15) are implied by (13).

For all $i$, function $f_{i}$ is a convex function of the degree of node $i$
in the graph $g$; the degree of node $i$ must take an integer value between
$0$ and $n-1$, which due to the convexity of $f_{i}$ and the fact that
$k_{i}\in\\{1,2,\ldots n-1\\}$ implies that the maximum of $f_{i}$ is
equivalent to $\max(f(n-1),f(-n+1))$. That is,

$f_{i}(\eta_{i}(g))\leq\max(f(n-1),f(-n+1))$

This means that (13) implies:

$\alpha-\gamma_{0}-nf_{i}(\eta_{i}(g))-\frac{1}{2}(n-1)\max(f(1)-f(0),f(-1)-f(0))>0\quad\forall
i$ (16)

Since, all $f_{i}(\eta_{i}(g))\geq 0$, we may add $\sum_{j\neq
i}f_{j}(\eta_{j}(g))$ to the left side of (16) without harming the inequality,
implying:

$\alpha-\gamma_{0}-nf_{i}(\eta_{i}(g))+\sum_{j\neq
i}f_{j}(\eta_{j}(g))-\frac{1}{2}(n-1)\max(f(1)-f(0),f(-1)-f(0))>0\quad\forall
i$ (17)

Now we divide by $n+1$:

$\frac{\alpha-\gamma_{0}-nf_{i}(\eta_{i}(g))+\sum_{j\neq
i}f_{j}(\eta_{j}(g))}{n+1}-\frac{1}{2}\frac{n-1}{n+1}\max(f(1)-f(0),f(-1)-f(0))>0\quad\forall
i$ (18)

The term on the left of (18) is $q_{i}(g)$:

$q_{i}(g)-\frac{1}{2}\frac{n-1}{n+1}\max(f(1)-f(0),f(-1)-f(0))>0\quad\forall
i$ (19)

Multiply through by two and note:

$\displaystyle 2q_{i}(g)>\frac{n-1}{n+1}\max(f(1)-f(0),f(-1)-f(0))$
$\displaystyle>\frac{n-1}{n+1}[f(1)-f(0)]\quad\forall i$ $\displaystyle
2q_{i}(g)>\frac{n-1}{n+1}\max(f(1)-f(0),f(-1)-f(0))$
$\displaystyle>\frac{n-1}{n+1}[f(-1)-f(0)]\quad\forall i$

Now (14) and (15) immediately follow. ∎

######  Remark 4.6.

This essentially means that the steeper a function $f$ around zero and on the
interval $(-n+1,n-1)$, the greater the quantity $\alpha-\gamma_{0}$ is needed
to ensure the theorem proved later in this section. It is worth pointing out
that this bound may often not be tight (i.e., the inequalities may hold true
and production quantities may be positive even when the condition is not not
met).

######  Theorem 4.7.

Suppose that $f$ is a convex function that has a minimum at $0$. Further,
suppose $f_{i}(\eta_{i}(g))=f(\eta_{i}(g)-k_{i})$. Define the change in $f$ as
$\triangle^{-}f_{i}(k_{i})=f_{i}(k_{i}-1)-f_{i}(k_{i})=f(-1)-f(0)=\triangle^{-}f(0)$
and
$\triangle^{+}f_{i}(k_{i})=f_{i}(k_{i}+1)-f_{i}(k_{i})=f(1)-f(0)=\triangle^{+}f(0)$.
Suppose $n\geq 2$ firms compete in an oligopoly with market demand
$p=\alpha-\sum_{i\in N}q_{i}$ and marginal costs
$c_{i}(g)=\gamma_{0}+f_{i}(\eta_{i}(g))$. If the parameters $\alpha$ and
$\gamma_{0}$ and the function $f$ obey condition (13), then the equivalence
class of graphs $[g]_{\eta}$ such that $\eta_{i}(g)=k_{i}$ is an equivalence
class of stable collaboration graphs.

###### Proof.

Let $g$ be a graph $g$ such that $\eta_{i}(g)=k_{i}$ for all firms $i$.
Consider a firm $i$ who may consider dropping its link with node $j$. If node
$i$ drops its link with node $j$ leading to graph $g-ij$, then
$\eta_{i}(g-ij)=k_{i}-1$ and $\eta_{j}(g-ij)=k_{j}-1$, while
$\eta_{r}(g-ij)=k_{r}$ for $r\not\in\\{i,j\\}$. Using Lemma 4.3

$q_{i}=\frac{\alpha-\gamma_{0}-nf_{i}(\eta_{i}(g))+\sum_{j\neq i\in
N}f_{j}(\eta_{j}(g))}{n+1}$ (20)

Calculate:

$\displaystyle q_{i}(g-ij)$
$\displaystyle=q_{i}(g)-\triangle^{-}f_{i}(k_{i})\left(\frac{n}{n+1}\right)+\triangle^{-}f_{j}(k_{j})\left(\frac{1}{n+1}\right)$
$\displaystyle q_{j}(g-ij)$
$\displaystyle=q_{j}(g)-\triangle^{-}f_{j}(k_{j})\left(\frac{n}{n+1}\right)+\triangle^{-}f_{i}(k_{i})\left(\frac{1}{n+1}\right)$
$\displaystyle q_{r}(g-ij)$
$\displaystyle=q_{r}(g)+\triangle^{-}f_{i}(k_{i})\left(\frac{1}{n+1}\right)+\triangle^{-}f_{j}(k_{j})\left(\frac{1}{n+1}\right)$

It then follows that

$\displaystyle Q(g-ij)$
$\displaystyle=Q(g)-\left(\frac{1}{n+1}\right)(\triangle^{-}f_{i}(k_{i})+\triangle^{-}f_{j}(k_{j}))$
$\displaystyle P(g-ij)$
$\displaystyle=P(g)+\left(\frac{1}{n+1}\right)(\triangle^{-}f_{i}(k_{i})+\triangle^{-}f_{j}(k_{j}))$
$\displaystyle c_{i}(g-ij)$ $\displaystyle=c_{i}(g)+\triangle^{-}f_{i}(k_{i})$

Now, we can calculate $Y_{i}(g-ij)$ in terms of $Y_{i}(g)$:

$\displaystyle Y_{i}(g-ij)$ $\displaystyle=q_{i}(g-ij)[P(g-ij)-c_{i}(g-ij)]$
$\displaystyle=Y_{i}(g)+q_{i}(g)\left(\frac{2}{n+1}\right)[\triangle^{-}f_{j}(k_{j})-n\triangle^{-}f_{i}(k_{i})]+\left(\frac{[\triangle^{-}f_{j}(k_{j})-n\triangle^{-}f_{i}(k_{i})]}{n+1}\right)^{2}$

Since $f_{i}(\eta_{i}(g))=f(\eta_{i}(g)-k_{i})$ this implies that
$\triangle^{-}f_{i}(k_{i})=\triangle^{-}f_{j}(k_{j})$ leading to (21) and then
(22) and (23) through algebraic manipulation. Finally, by the assumptions of
the theorem and condition (13) each of the quantities
$\triangle^{-}f_{i}(k_{i})$, $\frac{n-1}{n+1}$, and
$2q_{i}(g)-\frac{n-1}{n+1}\triangle^{-}f_{i}(k_{i})$ are nonnegative implying
(24).

$\displaystyle Y_{i}(g-ij)-Y_{i}(g)$
$\displaystyle=2q_{i}(g)\triangle^{-}f_{i}(k_{i})\left(\frac{1-n}{n+1}\right)+(\triangle^{-}f_{i}(k_{i}))^{2}\left(\frac{1-n}{n+1}\right)^{2}$
(21)
$\displaystyle=\triangle^{-}f_{i}(k_{i})\left(\frac{1-n}{n+1}\right)\left(2q_{i}(g)+\frac{1-n}{n+1}\triangle^{-}f_{i}(k_{i})\right)$
(22)
$\displaystyle=-\triangle^{-}f_{i}(k_{i})\left(\frac{n-1}{n+1}\right)\left(2q_{i}(g)-\frac{n-1}{n+1}\triangle^{-}f_{i}(k_{i})\right)$
(23) $\displaystyle<0$ (24)

This implies that if firm $i$ attempts to drop link $ij$, then
$Y_{i}(g)>Y_{i}(g-ij)$ and thus firm $i$ decreases its profit. The same will
be true for firm $j$. Hence, no firm has an incentive to drop a link from
graph $g$. Now, we will consider the case where firm $i$ attempts to add a
link to the graph $g$, giving $g+ij$ under the assumption that the link $ij$
does not exist in graph $g$. This analysis will follow closely the analysis
for $g-ij$. First note that $\eta_{i}(g)=k_{i}$ for all firms $i$ and
$\eta_{i}(g+ij)=k_{i}+1$ and $\eta_{j}(g+ij)=k_{j}+1$, while
$\eta_{r}(g+ij)=k_{r}$ for $r\not\in\\{i,j\\}$. We define
$\triangle^{+}f_{i}(k_{i})$ as
$\triangle^{+}f_{i}(k_{i})=f_{i}(k+1)-f_{i}(k)$; note the subtle difference
from the definition of $\triangle^{-}f_{i}(k_{i})$. Again using Lemma 4.3, we
calculate the production quantity for each node in graph $g+ij$:

$\displaystyle q_{i}(g+ij)$
$\displaystyle=q_{i}(g)-\triangle^{+}f_{i}(k_{i})\left(\frac{n}{n+1}\right)+\triangle^{+}f_{j}(k_{j})\left(\frac{1}{n+1}\right)$
$\displaystyle q_{j}(g+ij)$
$\displaystyle=q_{j}(g)-\triangle^{+}f_{j}(k_{j})\left(\frac{n}{n+1}\right)+\triangle^{+}f_{i}(k_{i})\left(\frac{1}{n+1}\right)$
$\displaystyle q_{r}(g+ij)$
$\displaystyle=q_{r}(g)+\triangle^{+}f_{i}(k_{i})\left(\frac{1}{n+1}\right)+\triangle^{+}f_{j}(k_{j})\left(\frac{1}{n+1}\right)$

We can then calculate the corresponding total production quantity $Q$, the
market price $P$ and marginal costs for each player for the graph $g+ij$:

$\displaystyle Q(g+ij)$
$\displaystyle=Q(g)-\left(\frac{1}{n+1}\right)(\triangle^{+}f_{i}(k_{i})+\triangle^{+}f_{j}(k_{j}))$
$\displaystyle P(g+ij)$
$\displaystyle=P(g)+\left(\frac{1}{n+1}\right)(\triangle^{+}f_{i}(k_{i})+\triangle^{+}f_{j}(k_{j}))$
$\displaystyle c_{i}(g+ij)$ $\displaystyle=c_{i}(g)+\triangle^{+}f_{i}(k_{i})$

Now, we can calculate $Y_{i}(g+ij)$ in terms of $Y_{i}(g)$:

$\displaystyle Y_{i}(g+ij)$ $\displaystyle=q_{i}(g+ij)[P(g+ij)-c_{i}(g+ij)]$
$\displaystyle=Y_{i}(g)+q_{i}(g)\left(\frac{2}{n+1}\right)[\triangle^{+}f_{j}(k_{j})-n\triangle^{+}f_{i}(k_{i})]+\left(\frac{[\triangle^{+}f_{j}(k_{j})-n\triangle^{+}f_{i}(k_{i})]}{n+1}\right)^{2}$

Since $f_{i}(\eta_{i}(g))=f(\eta_{i}(g)-k_{i})$ this implies that
$\triangle^{+}f_{i}(k_{i})=\triangle^{+}f_{j}(k_{j})$ leading to (25) and then
(26) and (27) through algebraic manipulation. Finally, by the assumptions of
the theorem and condition (13), each of the quantities
$\triangle^{+}f_{i}(k_{i})$, $\frac{n-1}{n+1}$, and
$2q_{i}(g)-\frac{n-1}{n+1}\triangle^{+}f_{i}(k_{i})$ are positive implying
(28).

$\displaystyle Y_{i}(g+ij)-Y_{i}(g)$
$\displaystyle=2q_{i}(g)\triangle^{+}f_{i}(k_{i})\left(\frac{1-n}{n+1}\right)+(\triangle^{+}f_{i}(k_{i}))^{2}\left(\frac{1-n}{n+1}\right)^{2}$
(25)
$\displaystyle=\triangle^{+}f_{i}(k_{i})\left(\frac{1-n}{n+1}\right)\left(2q_{i}(g)+\frac{1-n}{n+1}\triangle^{+}f_{i}(k_{i})\right)$
(26)
$\displaystyle=-\triangle^{+}f_{i}(k_{i})\left(\frac{n-1}{n+1}\right)\left(2q_{i}(g)-\frac{n-1}{n+1}\triangle^{+}f_{i}(k_{i})\right)$
(27) $\displaystyle<0$ (28)

This implies that if firm $i$ attempts to add a link $ij$, then
$Y_{i}(g)>Y_{i}(g+ij)$ and the firm decreases its profit. The same will be
true for firm $j$. Hence, no firm has an incentive to add a link to graph $g$.
Since no firm has an incentive to add or drop a link to graph $g$, it is
stable. This completes the proof. ∎

######  Example 4.8.

We present a numerical example of Theorem 4.7. Let $N=5$ firms compete in an
oligopoly with inverse demand function $P=100-Q$, fixed cost $\gamma_{0}=5$,
and $f(\eta(g))=(\eta(g))^{2}+\psi$ where $\psi=2$. Each firm has the shifted
function
$f_{i}(\eta_{i}(g))=f(\eta_{i}(g)-k_{i})=(\eta_{i}(g)-k_{i})^{2}+\psi$ where
$\mathbf{k}=[2,3,4,3,2]^{T}$ and . We want to test the stability of a graph
$g$ with $\eta_{i}(g)=k_{i}$ and
$f_{i}(\eta_{i}(g))=(\eta_{i}(g)-k_{i})^{2}+\psi$ for each node $i$. In order
to apply theorem (4.7), we must ensure condition (13) is met. We calculate:

$\displaystyle f(-n+1)=f(-4)=18,\quad f(-1)=3,\quad f(0)=2,$ $\displaystyle
f(1)=3,\quad f(n-1)=f(4)=18,\quad$

Hence,

$\displaystyle\max(f(n-1),f(1-n))=18,\quad\max(f(1)-f(0),f(-1)-f(0))=1,\quad$
$\displaystyle n\max(f(n-1),f(1-n))=5\cdot
18=90,\quad(n-1)\max(f(1)-f(0),f(-1)-f(0))=4\cdot 1=4,\quad$

$\alpha-\gamma_{0}-n\max(f(n-1),f(1-n))-\frac{1}{2}(n-1)\max(f(1)-f(0),f(-1)-f(0))=\\\
100-5-90-\frac{1}{2}\cdot 4=3>0$

Two stable isomorphic graphs, shown in Figure 5, have a degree sequence
equivalent to $\mathbf{k}$.

Figure 5: Two stable and isomorphic graphs that are possible configurations
for collaboration in the example oligopoly.

However, for the given parameters, there are 33 stable graphs of which only
the two shown have degree sequence equal to $\mathbf{k}$. These graphs were
computed using Maple and are shown in Figure 6.

Figure 6: The 29 stable graphs that arise from the parameters given.

It is interesting to investigate the other stable networks with degree
sequences different from $\mathbf{k}$. The graph in Row 7, Column 2 of Figure
6 shows a stable configuration where both nodes 3 and 4 would prefer one more
link, but they are already linked together and no other node requires an
additional link. Hence, the network is stable because each node is either
satisfied or no pair of nodes can bilaterally improve themselves through the
addition or removal of a link. It is interesting to note that in the case of
the graph shown, if both nodes 1 and 5, were to give up their link with one
another and instead link to nodes 4 and 3 respectively, then each node would
have minimized its marginal costs. While it is the case that nodes 1 and 5
would not benefit from such a trade that would help nodes 3 and 4. These nodes
would indirectly hurt themselves via the decreased market price as a result of
the additional quantity produced by nodes 3 and 4. Nonetheless this analysis
brings out the fact that the manner in which nodes link to one another and the
manner in which stability is analyzed, greatly affects which networks are
deemed to be stable.

######  Example 4.9.

For small numbers of firms $<7$ generating the set of stable graphs takes
seconds (even in an interpreted language like Maple). Consider the case of a
firm (in this case Firm 3) who determines that collaboration is desired, but
recognizes there may be a sink cost (not included in the model) associated
with initializing such a collaboration. For example, the time taken to
establish industry connections will cost in terms of human labor. Assuming
Firm 3 is a selfish profit maximizer and assumes that all other firms are
selfish profit maximizers who will play to a stable configuration, then the
analysis of the potentially stable graphs will inform Firm 3 on the potential
payoffs it might receive. If the network is already in a stable configuration,
then since there are three stable configurations in which Firm 3 is not
connected to any other players, then it may not be worthwhile to even explore
collaboration. On the other hand, if there is no collaboration (an unstable
condition), then Firm 3 may hope to steer the network evolution and will
evaluate its various payoffs in each possible stable configuration. The
possible payoffs are shown in Figure 7:

Figure 7: The possible payoffs Player 3 can obtain in the various stable
configurations. From Figure 6, graphs are numbered from left-to-right, top-to-
bottom.

Note that there is a substantial variation in the payoff the Player 3 may
receive. In the empty graph, Player 3 receives a payoff of $169/4$. Notice
that some collaborative scenarios disadvantage Player 3 ($3$ of the $33$)
while most improve Player 3’s payoff.

######  Remark 4.10.

Goyal and Joshi show that in a market with homogenous products and under
quantity competition, the uniquely stable network is the complete network for
specific cost functions under some parameter restrictions [GJ03]. Theorem 4.11
extends the result in Goyal and Joshi [GJ03] by using nonlinear costs and
decreasing the restriction on parameters necessary for the model to be
feasible.

######  Theorem 4.11.

Suppose the marginal cost for firm $i$ on graph $g$ is
$c_{i}(g)=\gamma_{0}+f(\eta_{i}(g))$. Define $\triangle f(k)=f(k+1)-f(k)$.
Further suppose each firm reduces its marginal cost for each additional
collaboration (Condition (1)), the collaboration cost reduction function $f$
is convex (Condition (2)), collaboration cost reduction function $f$ is
positive (Condition (3)), the production quantity is positive (Condition (4)),
and the collaboration cost reduction function $f$ is not too steep (Condition
(5)):

$x_{1}>x_{2}$ implies $f(x_{1})<f(x_{2})$;

$f$ is convex;

$f$ is positive;

$\alpha-\gamma_{0}>nf(0)$; and

$\triangle f(k_{1})-n\triangle f(k_{2})>0$ for all
$k_{1},k_{2}\in\\{0,1,\ldots n-1\\}$ Then the complete network $g^{c}$ is a
stable graph.

###### Proof.

The production quantity and profit can be calculated as before in (10) and
(9), respectively, by using that fact that $f_{i}=f$ for all $i$.

$\displaystyle q_{i}(g)$
$\displaystyle=\frac{\alpha-\gamma_{0}-nf(\eta_{i}(g))+\sum_{j\neq i\in
N}f(\eta_{j}(g))}{n+1}$ $\displaystyle Y_{i}(g)$
$\displaystyle=q_{i}(g)\left(P(Q)-c_{i}(g)\right)=q_{i}(g)\left(\alpha-\left(\sum_{j}q_{j}(g)\right)-\gamma_{0}-f(\eta_{i}(g))\right)$

Observe through algebraic manipulation that $P(Q)-c_{i}(g)=q_{i}(g)$, which
implies that
$Y_{i}(g)=q_{i}(g)\left(P(Q)-c_{i}(g)\right)=\left(q_{i}(g)\right)^{2}$.

For a complete network $g^{c}$, $\eta_{j}(g)=n-1$ for all $j$. Given $g^{c}$:

$q_{i}(g^{c})=\frac{\alpha-\gamma_{0}-f(n-1)}{n+1}$

Now for a complete network missing a link $(i,j)$, denoted as $g=g^{c}-ij$,
for nodes $i$ and $j$, $\eta_{i}(g)=\eta_{j}(g)=n-2$ but all other nodes $k$
have $\eta_{k}(g)=n-1$. Thus:

$q_{i}(g^{c}-ij)=\frac{\alpha-\gamma_{0}+(n-2)f(n-1)-(n-1)f(n-2)}{n+1}$

It follows that:

$q_{i}(g^{c})-q_{i}(g^{c}-ij)=\frac{(n-1)[f(n-2)-f(n-1)]}{n+1}$

Since $n-1>n-2$, Condition (1) implies $f(n-1)<f(n-2)$ which implies
$f(n-2)-f(n-1)>0$. Hence, $q_{i}(g^{c})-q_{i}(g^{c}-ij)>0$. By Condition (4),
$\alpha-\gamma_{0}>nf(0)$, which implies $q_{i}>0$ by Corollary 4.5 using
$f_{i}=f$. Further, since $q_{i}(g^{c})+q_{i}(g^{c}-ij)>0$, which combined
with $q_{i}(g^{c})-q_{i}(g^{c}-ij)>0$, implies
$Y_{i}(g^{c})-Y_{i}(g^{c}-ij)>0$. This implies that any firm $i$ will decrease
its profit by dropping link $ij$, hence the graph $g^{c}$ is stable. Now to
show that it is the only stable graph, suppose there is another graph $g\neq
g^{c}$ that is also stable. This implies that there exists a pair of firms
$(i,j)$ such that $ij\not\in g$. Let us consider the graph $g+ij$ relative to
the graph $g$.

$q_{i}(g+ij)-q_{i}(g)=\frac{-n}{n+1}\triangle
f(\eta_{i}(g))+\frac{1}{n+1}\triangle f(\eta_{j}(g))$

and thus that:

$Y_{i}(g+ij)-Y_{i}(g)=q_{i}(g+ij)^{2}-q_{i}(g)^{2}=[q_{i}(g+ij)-q_{i}(g)][q_{i}(g+ij)+q_{i}(g)]\\\
=q_{i}(g)\left(\frac{2}{n+1}\right)\left[\triangle f(\eta_{j}(g))-n\triangle
f(\eta_{i}(g))\right]+\left(\frac{1}{n+1}\right)^{2}\left[\triangle
f(\eta_{j}(g))-n\triangle f(\eta_{i}(g))\right]^{2}$

By Condition (5), $\triangle f(\eta_{j}(g))-n\triangle f(\eta_{i}(g))>0$ and
hence $Y_{i}(g+ij)-Y_{i}(g)\geq 0$. Similarly, $Y_{j}(g+ij)-Y_{j}(g)\geq 0$,
which implies that both nodes $i$ and $j$ may increase their profit by linking
together and so graph $g$ is not stable. This is a contradiction and so
$g^{c}$ is the only stable graph. This completes the proof. ∎

######  Example 4.12.

We present a numerical example of Theorem 4.11. Let $N=5$ firms compete in an
oligopoly with demand function $P=30-Q$, fixed cost $\gamma_{0}=5$, and
$f(\eta_{i}(g))=\frac{1}{\eta_{i}(g)+3}$. We want to test the stability of the
complete graph $g^{c}$. Conditions (1)-(4) are easy to check:

$\tfrac{df}{d\eta}=\frac{-1}{(\eta_{i}(g)+3)^{2}}<0$, which implies $f$ is
decreasing;

$\tfrac{d^{2}f}{d\eta^{2}}=\frac{2}{(\eta_{i}(g)+3)^{3}}>0$, which implies
that $f$ is convex;

$f(\eta_{i}(g))=\frac{1}{\eta_{i}(g)+3}>0$, which implies $f$ is positive;

$\alpha-\gamma_{0}=30-5=25>nf(0)=5\left(\frac{1}{3}\right)$ Condition (5) can
be verified with the below table:

$\eta_{i}(g)$ | $\eta_{j}(g)$ | $\triangle f(\eta_{i}(g))$ | $\triangle f(\eta_{j}(g))$ | $n\triangle f(\eta_{i}(g))-\triangle f(\eta_{j}(g))$ | $n\triangle f(\eta_{j}(g))-\triangle f(\eta_{i}(g))$
---|---|---|---|---|---
0 | 4 | -0.08 | -0.02 | 0.0059 | 0.4
4 | 0 | -0.02 | -0.08 | 0.3988 | 0.01

All conditions of Theorem 4.11 are met. The stability of the complete graph
can be verified exhaustively and was done using Matlab.

######  Remark 4.13.

The functions described in Theorem 4.11 generalizes the result of Goyal and
Joshi [GJ06], since it is clear that a linear function of the vertex degrees
(as assumed in [GJ06]) will satisfy the given criteria. Furthermore, Theorem
4.7 is a further generalization since we define conditions under which a
collaboration graph with an arbitrary degree distribution will be stable. This
is not possible with Goyal and Joshi’s model.

##  5 Conclusions

In this paper we showed that networks with specific structure properties may
form as a result of game theoretic interactions. Specifically, we showed a
simple way of constructing a game whose pairwise stable solutions are those
graphs with a given degree distribution. As a particular application of
network formation via game theoretic principles, we investigated the formation
of collaboration networks in oligopolistic competition. We extended the model
of Goyal and Joshi [GJ03] with a nonlinear cost function that, under
particular conditions, admits stable collaboration graphs with an arbitrary
degree sequence as well. One limitation of this approach is that we cannot
specify an exact graph structure. The degree distribution specification
generates a class of stable graphs rather than a single graph. We do not view
this as a problem since it can help explain variation in observed situations
with the same parameters.

###  5.1 Potential Relation to Network Science

Special structure in networks has been considered in several recent papers
[BA99, New03, DM02, AB02], that have cut across various subjects including
social networks, information networks, and biological networks as well as
physical networks such as power grids and road networks. A review of networks
in these disciplines may be found in various articles (see [New03, DM02, AB02]
and the references therein).

The network science literature was largely inspired by the observation of
macroscopic structural properties (e.g., small world, power law degree
distribution) of networks that occurred in several distinct network types
(e.g., social, information, biological networks), which have diverse
microscopic properties. The network science literature has largely been
devoted to finding the mechanisms by which networks form and/or evolve in
order to generate the structural properties that are observed. The momentum in
this direction has largely been driven by the statistical physics community
[BA99, New03, DM02], who argue that the phenomena of complex networks (e.g.,
power laws) may be explained by laws that reach across all complex networks
because they are phenomena that are inherent to the complexity of the
networks.

Alternatively, there has been recent interest in the structural properties of
networks that have been designed via optimization [Ald08, Nag08, ADGW03]. This
perspective is motivated largely by the fact that many networks (in the
abstract sense) are models for physical networks that are designed by humans
to function with particular objectives (or even designed by nature to serve an
evolutionary purpose). These networks are distinctly different from social
networks, which are abstract models that describe interactions between actors
(e.g., people talking, writing scientific papers or dating). These networks
(e.g., power grids, communication networks) are not designed through central
coordination, but arise as a result of the objectives of multiple independent
actors. As a result there are structural properties that often exist in these
networks that are not explained by models that do not account for these
functioning characteristics [DAL+05].

The work presented in this paper is motivated by this new work. Our
perspective is that some networks are formed as a result of the interacting
strategies of multiple players, rather than a universal rule for network
formation. This is consistent with certain recent observations on (e.g.) power
law networks [SP12]. This occurs in collaboration networks. The formation of
the collaboration network results from the strategic decisions of the players.
The network will still have particular structural properties that are
explained via game theoretic principles. In this paper, we illustrated that an
important property to the Network Science community, namely the degree
distribution, can emerge as a result of designed game mechanism. As an
explanatory model, we suggest that certain networks with interesting degree
distributions form as a result of strategic player interactions in which each
node degree in embedded (or hidden) in the objective function of the node
player. The formulation in this paper is simply an explicit representation. In
[LGF11] we illustrate a class of games that generate specific degree
distributions in which the degree is not an explicit part of the objective
functions of the players.

##  6 Future Directions

There are several directions this research could take. In [LGF11] we begin the
investigation of graph formation games with specific link bias and identify a
game theoretic mechanism that does not explicitly encode the degree
distribution of interest into the players’ objective functions and yet is
still capable of having graphs with arbitrary degree distributions as stable
solutions. This work is extended in [LFG12]. We also investigate the graph
formation game in the presence of spatial oligopolies in [LFG11]. Clearly
investigating the mechanism design problem for additional graph properties,
such as the clustering coefficient is of interest. Recent work on generation
of graphs with specific clustering coefficients [GRKF11] may provide insight
into game theoretic mechanisms for solving the same problem.

Another equally interesting future direction lies in the extraction of game
theoretic mechanisms from real-world data. Solving such a problem may take two
forms. In the first form, small real world human networks are evaluated using
traditional psycho-social interviewing techniques in an attempt to identify
objective functions or constraints consistent with the model presented in this
paper and theoretical extensions (e.g., [LFG12]). This work is planned in
collaboration with social psychologists at the authors’ parent institution. A
second form of objective function inference would be completely observational
in which, given a network that appeared to be stable, one would attempt to
infer the set of potential objective functions (and player constraints
[LGF11]) that would generate the given stable graph. Observation of network
evolution would also be useful. In this case, statistical techniques would
have to be applied to the determination of the objective function structure.

A final direction of investigation lies in the evaluation of dynamic network
formation. That is, investigating this problem in a dynamic context in which
the objective functions of players may change. We propose that this problem
can be analyzed in discrete time using techniques from competitive Markov
decision theory [JAF97]. However, the combinatorial properties of the graph
structures (for all but the simplest networks) make a brute force analysis
approach intractable. Thus a more sophisticated analysis technique may be
necessary to obtain any useful results.

## References

  * [AB02] R. Albert and A.L. Barabási.  Statistical mechanics of complex networks.  Reviews of modern physics, 74(1):47–97, 2002.
  * [ADGW03] D. Alderson, J. Doyle, R. Govindan, and W. Willinger.  Toward an optimization-driven framework for designing and generating realistic internet topologies.  ACM SIGCOMM Computer Communication Review, 33(1):46, 2003.
  * [Ald08] D.L. Alderson.  Catching the’Network Science’Bug: Insight and Opportunity for the Operations Researcher, 2008.
  * [BA99] A.L. Barabasi and R. Albert.  Emergence of scaling in random networks.  Science, 286(5439):509, 1999.
  * [BB04] P. Belleflamme and F. Bloch.  Market sharing agreements and collusive networks.  International Economic Review, 45(2):387–411, 2004.
  * [BG00] V. Bala and S. Goyal.  A noncooperative model of network formation.  Econometrica, 68(5):1181–1229, 2000.
  * [Blo95] F. Bloch.  Endogenous structures of association in oligopolies.  The RAND Journal of Economics, 26(3):537–556, 1995.
  * [CAJ07] A. Calvó-Armengol and M.O. Jackson.  Networks in labor markets: Wage and employment dynamics and inequality.  Journal of Economic Theory, 132(1):27–46, 2007.
  * [Cur02] S. Currarini.  Stable organizations with externalities.  Fondazione Eni Enrico Mattei, 2002.
  * [DAL+05] J.C. Doyle, D.L. Alderson, L. Li, S. Low, M. Roughan, S. Shalunov, R. Tanaka, and W. Willinger.  The robust yet fragile nature of the Internet.  Proceedings of the National Academy of Sciences of the United States of America, 102(41):14497, 2005.
  * [DM97] B. Dutta and S. Mutuswami.  Stable networks.  Journal of Economic Theory, 76(2):322–344, 1997.
  * [DM02] S.N. Dorogovtsev and J.F.F. Mendes.  Evolution of networks.  Advances in Physics, 51(4):1079–1187, 2002.
  * [FK07] T. Furusawa and H. Konishi.  Free trade networks.  Journal of International Economics, 72(2):310–335, 2007.
  * [GJ03] S. Goyal and S. Joshi.  Networks of collaboration in oligopoly.  Games and Economic behavior, 43(1):57–85, 2003.
  * [GJ06] S. Goyal and S. Joshi.  Unequal connections.  International Journal of Game Theory, 34(3):319–349, 2006.
  * [GRKF11] C. Gounaris, K. Rajendran, I. Kevrekidis, and C. Floudas.  Generation of networks with prescribed degree-dependent clustering.  Optimization Letters, 5:435–451, 2011.
  * [Hag93] J. Hagedoorn.  Understanding the rationale of strategic technology partnering: Nterorganizational modes of cooperation and sectoral differences.  Strategic management journal, 14(5):371–385, 1993.
  * [Hag96] J. Hagedoorn.  Trends and patterns in strategic technology partnering since the early seventies.  Review of industrial Organization, 11(5):601–616, 1996.
  * [Hag02] J. Hagedoorn.  Inter-firm R&D partnerships: an overview of major trends and patterns since 1960.  Research policy, 31(4):477–492, 2002.
  * [HLV00] J. Hagedoorn, A.N. Link, and N.S. Vonortas.  Research partnerships1.  Research Policy, 29(4-5):567–586, 2000.
  * [HS90] J. Hagedoorn and J. Schakenraad.  1\. Inter-firm partnerships and co-operative strategies in core technologies.  New explorations in the economics of technical change, page 1, 1990\.
  * [HS94] J. Hagedoorn and J. Schakenraad.  The effect of strategic technology alliances on company performance.  Strategic Management Journal, 15(4):291–309, 1994.
  * [Jac03] M.O. Jackson.  A survey of models of network formation: Stability and efficiency.  Game Theory and Information, 2003.
  * [JAF97] Koos Vrieze Jerzy A. Filar.  Competitive Markov decision processes.  Springer, 1997.
  * [JW96] M.O. Jackson and A. Wolinsky.  A strategic model of social and economic networks.  Journal of economic theory, 71(1):44–74, 1996.
  * [LFG11] S. Lichter, T. Friesz, and C. Griffin.  Collaborative network formation in spatial oligopolies.  arXiv:1108.4114, 2011.
  * [LFG12] S. Lichter, T. Friesz, and C. Griffin.  The calculation and simulation of the price of anarchy for network formation games.  Submitted to Military Operations Research [arXiv:1108.4115v2], 2012.
  * [LGF11] S. Lichter, C. Griffin, and T. Friesz.  Link biased strategies in network formation games.  In Third IEEE International Conference on Social Computing, October 9 - 11 2011.
  * [Mye77] R.B. Myerson.  Graphs and cooperation in games.  Mathematics of Operations Research, 2(3):225–229, 1977.
  * [Nag08] A. Nagurney.  Comment on Catching the Network Science Bug by David L. Alderson.  In OPERATIONS RESEARCH (ONLINE FORUM COMMENTARY), volume 56, page 5, 2008.
  * [New03] MEJ Newman.  The structure and function of complex networks.  SIAM Review, 45:167–256, 2003.
  * [SP12] Michael P. H. Stumpf and Mason A. Porter.  Critical Truths About Power Laws.  Science, 335:665–666, Febrary 2012.
  * [Tri88] J. Triole.  The Theory of Industrial Organization.  MIT Press, 1988.