Saint Petersburg State University
Department of mathematical game theory and statistical decisions
Tsyganov Kirill Vasilyevich
Master’s thesis
A Model of Oligopoly based on a Network
Approach
Specialization 01.04.02
Applied Mathematics and Informatics
Master’s Program Game Theory and Operations Research
Research advisor
PhD, Associate Professor
Sedakov A.A.
Saint Petersburg
2016
Contents
1 Introduction
4
2 Two-stage oligopoly
8
2.1
The model . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.1.1
Strategies . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.1.2
Payoff function . . . . . . . . . . . . . . . . . . . . . .
9
2.2
Equilibrium at fixed network . . . . . . . . . . . . . . . . . . . 10
2.3
Equilibrium in the two-stage game . . . . . . . . . . . . . . . 14
2.4
Preferred equilibria . . . . . . . . . . . . . . . . . . . . . . . . 19
2.5
Sensitivity analysis . . . . . . . . . . . . . . . . . . . . . . . . 21
2.6
2.5.1
Regular networks . . . . . . . . . . . . . . . . . . . . . 28
2.5.2
Example . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Weighted network . . . . . . . . . . . . . . . . . . . . . . . . . 31
3 Cooperative game
3.1
3.2
33
Maximin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.1.1
Characteristic function . . . . . . . . . . . . . . . . . . 37
3.1.2
Cooperative solution . . . . . . . . . . . . . . . . . . . 40
Sensitivity analysis . . . . . . . . . . . . . . . . . . . . . . . . 40
3.2.1
Regular networks . . . . . . . . . . . . . . . . . . . . . 41
4 Two-stage oligopoly with offering costs
42
4.1
Equilibrium at fixed network . . . . . . . . . . . . . . . . . . . 42
4.2
Equilibrium in the two-stage game . . . . . . . . . . . . . . . 43
4.3
Sensitivity analysis . . . . . . . . . . . . . . . . . . . . . . . . 46
5 Alternative characteristic functions of cooperative game
2
48
5.1
Maximization of S’s payoff with Nash equilibrium strategies
for other individuals . . . . . . . . . . . . . . . . . . . . . . . 48
5.2
Equilibrium in the game with |N | − |S| + 1 players . . . . . . 50
6 Conclusion
53
3
1
Introduction
This thesis studies the competition of firms in one product market with network effect under which costs are dependent upon collaborations between
firms. The idea of research is taken from [14], and concerns the question:
what are the incentives of firms in market competition? The mentioned book
covers many cases of market competitions and provides solution techniques.
It discovers the topics of monopoly market and optimal behavior in quantities and prices, competition of many firms in one and many products market,
price discrimination, dynamic competitions and so on. We focus on Cournot
competition in quantities, the approaches of the research and development
adoption of new technologies and cooperative game theory. In the book is
proposed different solution concepts and models which concern these issues.
The paper [2] provides an example of applying a model with research and
development collaborations for non-cooperative and cooperative two-person
games. Authors consider a two-stage game where on different stages actions
of players represent the value of technological partnership and find Nash equilibria of the game. Another way of looking at the firms competition is to look
precisely at their collaborations. A collaboration link can be interpreted as
a partnership which is costly but lower costs of production of the firms involved. There can be many incentives for collaboration. Indeed technological
partnerships, reduction of transportation and holding costs and others. The
collaborations between firms can be represented by a network with firms settled in the nodes. In [9] M. Jackson describes social and economic networks,
constructs models of behavior and analyses them using game theory and optimization methods. He provides allocation rules for cooperative games on
networks as well. Mostly he focuses on the topology structure of equilibrium and stable networks. He discovers network formation stage, provides
4
the conditions for existence of stable networks. He introduces a one-stage
model of the game we discover, the game on a fixed network, but he does
not inspect the two-stage game and consequently the issues of the two-stage
equilibria and cooperative game. We use definitions, concepts and notations
from this book in our work. In [8] authors discover a coordination game
with the endogenous network structure with and costs of maintaining the
collaborations. They examine stochastic stability issue on fixed networks,
characterize stochastically stable states and inspect how the endogenous networks affect stochastic stability. Similar to ours, a non-cooperative model of
network formation with link formation costs is investigated in [3]. There is
considered one-way and two-way flow of benefits. The strict Nash equilibria
are found in both models: for one-way flow model there are empty network
and wheel network and for two-way flow model – empty and star networks.
Also there is considered dynamic process and is proved that it converges
to strict Nash equilibrium. Another close research is done in [6]. There
Cournot oligopoly is considered with addition of opportunity for each firm
to form pair-wise collaborative links with other firms which will lower costs
of production of participants. The result is in the characterization of stable
networks and comparison them with efficient networks. There is found that
the complete network is stable. Authors also show that from a social point
of view the complete network is efficient. The comprehensive overview of
cooperative games and coalitional formations for applications in economics is
provided in [4]. There are discovered general issues of incentives to cooperate,
form a coalition, provided analysis of influence groups of coalitions to other
coalitions, examined the bargaining issue of total payoff of coalition between
players. And there is considered competition of coalitions. In [13] there is an
analysis of cooperative game based on network model with costs for estab-
5
lishing links using an extension of the Myerson value to determine the payoffs
in a 3-player symmetric game and the issue of existence coalition proof Nash
equilibria in the 3-player symmetric game. In [7] authors develop a model
of oligopoly market with the network effect on payoff functions and examine
the incentives of firms to form collaborations with other firms. They find
the nature of collaboration structures that are stable under different market
conditions, and characterized stable structures. Unlike stability issue in [7]
here we inspect Nash equilibria. We decide to discover the firms competition
from the two points of view at the same time: quantities competition and
network formation. As the basis of such analysis we use [11]. The paper provides analysis of links’ influence on strategy choice of a player for a general
payoff function. The issue of dynamic stability of cooperation solutions is
examined.
The dissertation is based on these works. As in [11] we consider a twostage game of n firms where at the first stage players form the network of
collaborations and at the second stage the firms chose quantities of production
as in [7]. After these two stages payoffs are computed and the game ends.
This game illustrates the competition of firms in one-product market. Our
first aim is to find equilibria, characterize them by profitability and network
topology structure. We establish preferred equilibria and provide sensitivity
analysis of the player’s behavior and the market performance. The second
goal is to find the cooperative solution of the game and compare it with
non-cooperative solution. We examine a two-stage oligopoly model from [7]
with offering costs as well. It differs from the previous model in the payoff
function in such a way that an incentive to form a collaboration link induces
additional costs. In this model we find sufficient condition for equilibria.
We should notice that in the papers above the issue of equilibria in two-
6
stages games is not discussed as like as the cooperative solution of firms
competition in two-stages and our work tries to figure out firms equilibrium
behavior and common laws which helps to better understand how firms should
act in one-product market competition: should they play as singletones or
cooperate, how the collaborations influence on different players and what
concrete actions they should do to benefit.
The paper has the following structure. In section 2 we investigate the
non-cooperative two-stage oligopoly. At first we define the model, strategies and payoff functions. Then we find an equilibrium when the network
is fixed. After this we construct a hypothesis of equilibrium network topology structure and test it. Next we answer the question which equilibria are
more profitable for players and how it concerns other players. In sensitivity analysis we explore how the adding or removing the link affect player’s
equilibrium strategies, payoffs and price function. The special case of regular
network is explored in detail and with an example. At the end of this section we adopt the cost function for the weighted networks and say how the
equilibrium action for fixed network will change. Section 3 is a consideration
of cooperative game approach. We investigate both models: with full cooperation on two stages and cooperation only on quantities competition stage.
We give an overview of methods of construction characteristic function, and
introduce solution concepts of the bargaining total payoff which we will use.
The characteristic function then is chosen as the value maximin optimization
problem. The Shapley value [12] and the center-of-gravity of the imputation
set (CIS value) [5] are used as imputations. Finally the sensitivity analysis
of cooperative game is provided. Section 4 introduces the model of two-stage
oligopoly with offering costs which we examined. The methods of analysis
the last model coincide with the previous two-stage oligopoly model.
7
2
2.1
Two-stage oligopoly
The model
We consider a two-stage game of n players. At first stage players offer collaboration links to each other simultaneously. After all players made their offers
pairwise links form a network, one way links are removed. At the end of the
first stage we have a formed undirected network connecting players. At the
second stage there is Cournot competition in quantities. Players choose quantities of production simultaneously. The second stage ends when all players
have made their choices. After second stage the payoffs are calculated. Payoff functions are dependent upon quantities and they also dependent upon
network. After this step the game ends. We now develop the required terminology and provide some definitions.
2.1.1
Strategies
Let N = {1, ..., n} be a finite set of players. A pair (N, g), where N is a set
of players and g setting the topology of collaborations between players, we
call a network.
At the first stage, network formation appears. Players simultaneously
choose their actions – n-dimensional vectors gi = (gi1 , . . . , gin ), i ∈ N with
components defined as:
gij =
1, if player i offers a link to player j ∈ M ,
(1)
0, otherwise.
If an element (i, j) ∈ g, it means that there exists a link between player
i and player j. To simplify notations, we will identify the network g with the
action profile (g1 , . . . , gn ) and denote action profile by g. A link (i, j) will be
8
denoted by ij. Let g−i = (g1 , . . . , gi−1 , gi+1 , . . . , gn ) denotes an action profile
g without player i’s action. Using our notations the equality g = (gi , g−i )
holds. Number of neighbors of player i in the network g is the degree of node
i in the network g and denoted by ηi (g) = |{j ∈ N \ {i} : ij ∈ g}|.
Once the action profile (g1 , g2 , . . . , gn ) has chosen, it defines a network g
in the following way: a link ij is formed and consequently belongs to network
g only if gij = gji = 1, i.e., both players agree to form it. At the end of the
network formation stage, network g is realized.
At the second stage players compete in choosing the quantities, i.e.
Cournot competition is played. The action of player i at the second stage is
quantity qi ∈ [0, q], where q is sufficiently large. Players choose their actions
at the same time. At the end of this stage the action profile q = (q1 , . . . , qn )
is formed.
After two stages player i has two actions – action gi from the first stage
and action qi from the second stage. These actions form the strategy (gi , qi )
player i in the two-stage game. All strategies of all players form the strategy
profile ((g1 , q1 ), . . . , (gn , qn )) in the game.
2.1.2
Payoff function
We come out from the assumption that collaborations lower marginal costs
of production. A network g, therefore, induces a marginal costs for the firms
which is given by c1 (g), c2 (g), . . . , cn (g). We assume that firm i’s marginal
cost in the network g is a function of the number of collaboration links it has
with other firms and is strictly decreasing in the number of these links:
ci (g) = c(ηi (g)), c(ηi (g) + 1) < c(ηi (g)), i ∈ N.
(2)
To rule out uninteresting cases, we will assume that ci (g) > 0, ∀i ∈
9
N, ∀g. We assume that marginal costs are linearly declining in the number
of links, i.e.
ci (g) = γ0 − γηi (g), i ∈ N,
(3)
where γ0 > 0, represents a firm’s marginal cost when it has no links, while
γ > 0 is the cost reduction induced by each link formed by a firm. The
assumption of non-negativeness of the marginal costs leads us to the following
constraint:
γ0 > γ(n − 1).
(4)
Suggest the following linear inverse market demand function:
p(q) = α −
X
qi , α > 0.
(5)
i∈N
We suppose that α is sufficiently large.
And finally define the payoff function on a network g for player i ∈ N
as follows:
πi (g, q) = (p − ci (g))qi .
2.2
(6)
Equilibrium at fixed network
At the second stage we have fixed undirected network g. At this stage player’s
action is its quantity qi . In other words we have Cournot competition in
quantities.
The necessary first-order condition for action profile q ∗ = (q1∗ , q2∗ , . . . , qn∗ )
to be a Nash equilibrium is that for each firm i ∈ N
q∗
(7)
The sufficient second-order condition for action profile q ∗ = (q1∗ , . . . , qn∗ )
to be a Nash equilibrium is that qi∗ yields a maximum of πi (g, q), put differ10
ently, strict concavity of payoff function πi (g), i.e.
q∗
Let us first check the sufficient second-order condition.
∂p
∂ 2 πi (g, q) ∂ qi ∂qi + (p − ci (g))
∂p
∂ 2p
=
=
q
+
2
= −2 < 0
i
∂qi2
∂qi
∂qi2
∂qi
(8)
(9)
We have demonstrated that each firm’s profit is strictly concave for
any given action profile (q1 , q2 , . . . , qn ) and any network g. Therefore the
second-order condition is satisfied and, furthermore, the first-order condition
is sufficient for action profile (q1∗ , q2∗ , . . . , qn∗ ) to be a Nash equilibrium.
Let us find the Nash equilibrium from the necessary first-order condition
for a Nash equilibrium. We have the system of payoff functions for all players:
π1 (g, q) = (p(q) − c1 (g))q1 ,
π2 (g, q) = (p(q) − c2 (g))q2 ,
(10)
...
πn (g, q) = (p(g) − cn (g))qn .
Below the process of finding the equilibrium output is shown.
∂π1 (g,q)
∂p
=
q
+ p − c1 (g) = 0,
1
∂q
∂q
1
1
∂π2 (g,q) = q2 ∂p + p − c2 (g) = 0,
∂q2
∂q2
(11)
...
∂πn (g,q) = qn ∂p + p − cn (g) = 0.
∂qn
∂qn
When we substitute p(q) from (5) and ci (g) from (3) into i-th equation
we obtain:
11
P
q1 (−1) + α − i∈N qi − γ0 + γη1 (g) = 0,
P
q2 (−1) + α −
i∈N qi − γ0 + γη2 (g) = 0,
(12)
...
P
qn (−1) + α −
i∈N qi − γ0 + γηn (g) = 0.
Sum up all equations:
−
X
qi + n(α − γ0 ) − n
i∈N
X
qi + γ
i∈N
n(α − γ0 ) + γ
X
i∈N
ηi (g) = 0
i∈N
ηi (g) = (n + 1)
i∈N
X
X
X
qi
i∈N
P
n(α − γ0 ) + γ i∈N ηi (g)
qi =
n+1
(13)
Look at the i-th equation of system (11):
qi +
X
qi = α − γ0 + γηi (g)
(14)
i∈N
After substitution (13) into (14), we get the following
P
n(α − γ0 ) + γ i∈N ηi (g)
qi +
= α − γ0 + γηi (g)
n+1
(15)
P
n(α − γ0 ) + γ i∈N ηi (g)
qi = α − γ0 + γηi (g) −
n+1
(16)
Finally Cournot equilibrium quantities can be written as follows
α − γ0 + nγηi (g) − γ
qi∗ (g) =
n+1
P
j6=i ηj (g)
, i ∈ N.
(17)
At this point we found the optimal quantity of production for every
12
player. The equilibrium profit (6) for player i is
∗
∗
πi (g, q ) = (p(q ) −
ci (g))qi∗ (g)
= α−
X
− γ0 + γηi (g) qi∗ (g). (18)
qi∗ (g)
i∈N
Comparing the expression in brackets α −
P
i∈N
qi∗ − γ0 + γηi (g) with
the formula (14) we come to the final result. For a given network g, Cournot
profit for firm i ∈ N has the following form
πi (g) = qi∗2 (g).
(19)
Proposition 1. For a fixed network there is a unique equilibrium in competition in quantities. The optimal quantity for firm i is
α − γ0 + nγηi (g) − γ
qi∗ (g) =
n+1
P
j6=i ηj (g)
.
(20)
The payoff function for i-th firm has the form of
πi (g) = qi∗2 (g).
(21)
In order to ensure that each firm produces a strictly positive quantity
in equilibrium, consider the worst case for i-th firm – when firm i has no any
links in formed network, and all the remaining firms N \ {i} form a complete
network. The quantity of firm i has to be positive
qi∗ (g) =
α − γ0 − (n − 1)(n − 2)γ
> 0.
n+1
(22)
Finally by simplifying the last inequality we obtain
(α − γ0 ) − (n − 1)(n − 2)γ > 0.
The inequality (23) actually gives a lower bound for α.
13
(23)
2.3
Equilibrium in the two-stage game
In the two-stage game the strategy of player i is a pair (gi , qi ), where gi is his
pure action at the network formation stage which represents his desirable collaborations with other players and qi is his pure action at the quantity competition stage when collaborations of all players are already fixed after network
formation stage. Consequently we have strategy profile ((g1 , q1 ), . . . , (gn , qn )),
where g is a network which is obtained after all players chose desirable links
gi , and quantities qi , i ∈ N . In a simple form strategy profile can be written
as pair (g, q).
The goal of this section is to find Nash equilibria in the two-stage
game. Of course the problem of finding all Nash equilibria in the infinite set
of strategy profiles is very complex so we will make a hypothesis of structure
Nash equilibria in specific networks and check it.
Assume that network g is a pairwise network, i.e. for any offered link
complementary link is offered as well. In network notations it means gij = gji .
An illustration of such networks with 3 players is shown on Figure 1.
Check whether such network is a Nash equilibrium and which constraints we
should apply to say that such network g is a Nash equilibrium.
When in a pairwise network player i deviates from his action gi∗ with
fixed actions gj∗ , j 6= i, he cannot increase the number of his collaborations.
The number of neighbors of the player may stay the same or may be less than
in pairwise network, because other players do not deviate and consequently
do not propose new links. An example of the deviation is shown on Figure
2. There picture a) demonstrates pairwise network g ∗ and pictures b) and c)
show deviations of player 1. Formally saying, given a pairwise network g ∗ ,
deviation of player i from the action gi∗ to the action gi can be expressed in
14
Figure 1: Pairwise and not pairwise networks.
the following form:
ηi (g ∗ ) − ηi (g ∗ ||gi ) = l, l = 0, 1, . . . , ηi (g ∗ ).
Figure 2: Example of deviations from g ∗ at network formation stage.
15
(24)
By definition, the strategy profile (g ∗ , q ∗ ) is a Nash equilibrium if player
i does not get a surplus from his deviation with fixed strategies of other
players. Formally, (g ∗ , q ∗ ) is a Nash equilibrium if
πi (g ∗ , q ∗ ) > πi (g ∗ , q ∗ ||gi , qi ), ∀gi , ∀qi , ∀i ∈ N
(25)
Fix such qi which maximizes πi (g ∗ , q ∗ ||gi , qi ). It will be sufficient for
holding the inequality above. Indeed if the inequality above holds for all qi
then it holds for such specific qi which maximizes the right-hand side of (25),
i.e.,
max πi (g ∗ , q ∗ ||gi , qi ) > πi (g ∗ , q ∗ ||gi , qi ), ∀gi , ∀qi , ∀i ∈ N.
qi
(26)
By the same logic we can fix such gi that maximizes maxqi πi (g ∗ , q ∗ ||gi , qi )
and consequently get rid off variability in strategies in network formation
stage.
max max πi (g ∗ , q ∗ ||gi , qi ) > max πi (g ∗ , q ∗ ||gi , qi ), ∀gi , ∀i ∈ N
gi
qi
qi
(27)
After combining inequalities (26), (27) and having the reasoning above
the inequality (25) proceeds to the following inequality:
πi (g ∗ , q ∗ ) > max max πi (g ∗ , q ∗ ||gi , qi ), ∀i ∈ N
gi
qi
(28)
At first we need to solve the maximization problem over quantity from
the right-hand side of (25):
maxqi πi (g ∗ , q ∗ ||gi , qi ) =
P
∗ ∗
∗
= maxqi α − j6=i qj (g ) − qi − γ0 + γηi (g ||gi ) qi
(29)
(30)
Actually it is a common maximization problem of one variable and to
16
find the solution it is needed to take the derivative of πi (g ∗ , q ∗ ||gi , qi ) with
respect to qi :
∂
πi (g ∗ , q ∗ ||gi , qi ) = 0
∂qi
X
∂
qj∗ (g ∗ ) − qi − γ0 + γηi (g ∗ ||gi ) qi = 0
α−
∂qi
j6=i
X
qj∗ (g ∗ ) − 2qi − γ0 + γηi (g ∗ ||gi ) = 0
α−
(31)
(32)
(33)
j6=i
Finally we obtain such qi that maximizes πi (g ∗ , q ∗ ||gi , qi ):
qi =
X
1
α−
qj∗ (g ∗ ) − γ0 + γηi (g ∗ ||gi )
2
(34)
j6=i
Substitute qi from the formula above into the πi (g ∗ , q ∗ ||gi , qi ) to obtain
maxqi πi (g ∗ , q ∗ ||gi , qi ):
max πi (g ∗ , q ∗ ||gi , qi ) =
qi
= α −
X
qj∗ (g ∗ ) − qi − γ0 + γηi (g ∗ ||gi ) qi =
j6=i
= α −
X
j6=i
qj∗ (g ∗ ) −
α−
∗ ∗
j6=i qj (g )
P
∗
− γ0 + γηi (g ||gi )
− γ0 + γηi (g ∗ ||gi ) ×
2
P
α − j6=i qj∗ (g ∗ ) − γ0 + γηi (g ∗ ||gi )
×
=
2
17
=
α−
∗ ∗
j6=i qj (g )
P
− γ0 + γηi (g ∗ ||gi ) 2
=
2
2
X
1
qj∗ (g ∗ ) − γ0 + γηi (g ∗ ||gi ) =
α−
4
j6=i
2
X
1
= α −
qj∗ (g ∗ ) + qi∗ (g ∗ ) − γ0 + γηi (g ∗ ||gi ) =
4
=
j∈N
Substitute formula (13) instead of sum
P
j∈N
qj∗ (g ∗ ) and formula (20)
instead of qi∗ (g ∗ ) into the last expression above:
P
n(α − γ0 ) + γ i∈N ηi (g ∗ )
1
=
α−
+
4P
n+1
2
α − γ0 + nγηi (g ∗ ) − γ j6=i ηj (g ∗ )
∗
− γ0 + γηi (g ||gi ) =
+
n+1
P
2
α − γ0 − γ i∈N ηi (g ∗ ) γ
∗
∗
=
+
ηi (g ) + ηi (g ||gi )
=
n+1
2
2
γ
∗ ∗
∗
∗
= qi (g ) +
ηi (g ||gi ) − ηi (g )
2
We obtain the maximum over quantity (when player i is deviating in
quantity) of the right-hand side of the (25):
∗
∗
max πi (g , q ||gi , qi ) =
qi
qi∗ (g ∗ )
2
γ
∗
∗
ηi (g ||gi ) − ηi (g )
+
2
(35)
Now we need to solve the maximization over gi problem:
∗
∗
maxgi maxqi πi (g , q ||gi , qi ) = maxgi
qi∗ (g ∗ )
+
γ
2
2
ηi (g ||gi ) − ηi (g ) (36)
∗
∗
The last expression can be transformed to the following:
2
γ
∗ ∗
∗
∗
ηi (g ||gi ) − ηi (g )
=
max qi (g ) +
gi
2
2
γ
∗ ∗
∗
∗
= qi (g ) + max ηi (g ||gi ) − ηi (g )
2 gi
18
(37)
(38)
According to the (24) we can conclude that:
max ηi (g ||gi ) − ηi (g ) = 0
∗
∗
gi
(39)
Finally we obtain the right-hand side (when player i is deviating at
both stages) of Nash equilibrium definition (25):
max max πi (g ∗ , q ∗ ||gi , qi ) = (qi∗ (g ∗ ))2
(40)
πi (g ∗ , q ∗ ) = (qi∗ (g ∗ ))2 , i ∈ N,
(41)
gi
qi
Since
now we can be sure that the condition for Nash equilibrium (25) is always
satisfied. Consequently we proved the following result.
Proposition 2. All pairwise networks are the Nash equilibrium in the twostage game.
2.4
Preferred equilibria
From the form of the payoff function in equilibrium (19) and the sufficient
condition for Nash equilibrium (Proposition 2) we can conclude that some
equilibria may be more profitable for some players than others.
For example, the regular network is more profitable equilibrium than
the empty network. Moreover the greater degree of node in regular network
the greater payoff players get relatively to the payoff in regular network with
less degree. Figure 3 illustrates that for 6 players 0-regular network is less
profitable than 1-regular network, and that 1-regular network is less profitable
than a complete network for any player.
Indeed, payoffs for the empty network and regular network are in the
19
Figure 3: The greater degree of node in regular network the greater benefit players get.
following relation:
πi (empty) =
α−γ0 2
n+1
k 2
+ γ n+1
2
1
+ γ 1 − n+1
∀i ∈ N
6 πi (k-regular network) =
6 πi (complete) =
α−γ0
n+1
<
α−γ0
n+1
(42)
(43)
Another interesting situation – star network. We call a player in the star
network the central player if he has the highest degree in the star network.
We observed that the star network central player benefits, others do not.
Figure 4 shows that the star network is more profitable for central player.
Figure 4: Only player 1 benefits, others lose.
In this case the following inequality for players’ payoffs hold: for the
player, located in the central node, we have:
πcentral (empty) =
< πcentral (star network) =
20
α−γ0 2
n+1
α−γ0
n+1
<
k
+ γ n+1
2
,
(44)
and for any other player k holds:
πk (empty) =
< πk (star network) =
α−γ0 2
n+1
α−γ0
n+1
<
− γ n−3
n+1
2
∀n > 3
(45)
Hence we come up to the following propositions:
Proposition 3. A k-regular network is more profitable than an l-regular
network for any player i ∈ N if l < k.
Proposition 4. A star network is more profitable than empty network only
for the player located in the central node.
2.5
Sensitivity analysis
We will use equilibrium quantities (17) for given network g which are dependent on a network structure so for the simplification we will discard the
parameter q in the payoff function (6).
Suppose that player i in given network g deletes the link with player j.
After this transformation network g changes and we denote the new network
by g̃. An example of such situation is illustrated on Figure 5.
Figure 5: Example of removing the link in the network.
21
The equilibrium quantity for player i in the new network g̃ has changed
in the following way:
qi∗ (g̃) =
=
=
=
P
α − γ0 + nγ ηi (g) − 1 − γ
η
(g)
−
1
j
j6=i
n+
P1
α − γ0 + nγηi (g) − γ j6=i ηj (g)
n−1
−γ
n+1 P
n+1
α − γ0 + nγηi (g) − γ j6=i ηj (g)
2
−γ 1−
n+1
n+1
2
qi∗ (g) − γ 1 −
n+1
(46)
The quantity qj∗ (g̃) for player j is changed by the same rule. Now let
us consider how removing of the link (ij) affects the equilibrium quantity of
other player k 6= i, j.
P
α
−
γ
+
nγη
(g)
−
γ
η
(g)
−
2
0
k
j
j6=k
qk∗ (g̃) =
n + 1P
α − γ0 + nγηk (g) − γ j6=k ηj (g)
2
=
+γ
n+1
n+1
2
= qk∗ (g) + γ
n+1
(47)
Consider influence of the removing link in the network to the price
function (5):
p(g̃) = α −
X
qi∗ (g̃) =
i∈N
2
2
= α−
+ 2γ 1 −
− (n − 2)γ
=
n+1
n+1
i∈N
X
2
2
= α−
qi∗ (g) + γ 2 1 −
− (n − 2)
=
n+1
n+1
X
qi∗ (g)
i∈N
22
+γ 2−
4
4 − 2n
= α−
+
n+1
n+1
i∈N
X
n
∗
= α−
qi (g) + 2γ 1 −
=
n+1
i∈N
X
2
qi∗ (g) + γ
=
= α−
n+1
X
qi∗ (g)
=
i∈N
= p(g) + γ
2
n+1
(48)
We observe the positive correlation of price with the removing of link.
Consider now players’ payoffs. At first look at the payoff function of
player i (19) in the new network g̃.
πi (g̃) = (qi∗ (g̃))2 =
= qi∗ (g) − γ 1 −
2
2
=
n+1
2
2
2
2
∗
∗
+ γ 1−
= (qi (g)) − 2qi (g)γ 1 −
=
n+1
n+1
2
2
γ 1−
− 2qi∗ (g)
= πi (g) + γ 1 −
n+1
n+1
Let us look under which constraint player i (and player j) benefits from
the removing the link (ij). Due to the form of the payoff function of player
2
i in the network g̃ and non-negativeness of term γ 1 − n+1
, the payoff of
player i has a positive correlation with the deletion of the collaboration if the
next condition holds:
2
γ 1−
n+1
− 2qi∗ (g) > 0,
(49)
or
1
2
qi∗ (g) 6 γ 1 −
.
2
n+1
23
(50)
The payoff of player k 6= i, j in the network g̃ has the following form:
πk (g̃) = (qk∗ (g̃))2 =
= qk∗ (g) + γ
(51)
2
n+1
2
=
2
2
2
+ γ
=
+
=
n+1
n+1
1
4
qk∗ (g) + γ
> πk (g).
= πk (g) + γ
n+1
n+1
(qk∗ (g))2
2qk∗ (g)γ
We can say that payoff for player k 6= i, j does not decrease after players i and
j formed a new connection. In general, if the condition (50) holds, players
i, j profit in the network g̃ in comparison to the network g. In contrast player
k always gains in the network g̃ in comparison to the network g.
Now suppose that player i in given network g suggests a link to some
other player j and the last one accepts it. It means that one new link is
added to the network g. Denote this new network by g̃. An example of such
situation is illustrated on Figure 6.
Figure 6: Example of establishing a new link in the network.
The equilibrium quantity for player i in this new network g̃ has changed
24
in the following way:
qi∗ (g̃) =
=
=
=
P
α − γ0 + nγ ηi (g) + 1 − γ
η
(g)
+
1
j6=i j
n+
P1
α − γ0 + nγηi (g) − γ j6=i ηj (g)
n−1
+γ
n+1 P
n+1
α − γ0 + nγηi (g) − γ j6=i ηj (g)
2
+γ 1−
n+1
n+1
2
qi∗ (g) + γ 1 −
.
n+1
(52)
The quantity qj∗ (g̃) for player j, who has accepted the link offered by
player i, is changed by the same rule. We can make an important conclusion
from the last equation: the number of collaborations of the player is positively
correlated to the equilibrium quantity of production of the player while other
players do not deviate.
Now let us consider how the addition of a new link affects equilibrium
quantity of other player k 6= i, j who is not involved in the new collaboration
between players i and j.
P
α
−
γ
+
nγη
(g)
−
γ
η
(g)
+
2
0
k
j
j6=k
qk∗ (g̃) =
n + 1P
α − γ0 + nγηk (g) − γ j6=k ηj (g)
2
=
−γ
n+1
n+1
2
= qk∗ (g) − γ
.
n+1
(53)
We can see that for the player k 6= i, j the equilibrium quantity does
not decrease with appearance of the link between players i and j. And the
amount of this reduce has a negative correlation with the number of players
in the game: the more players in the game the less reduction of quantity
player k should do if players to stay in the Nash equilibrium.
Consideration of the price function uncovers a negative correlation be-
25
tween the quantity with the number of collaborations:
p(g̃) = α −
X
qi∗ (g̃) =
i∈N
=
=
=
=
− 2γ 1 −
2
n+1
2
=
n+1
i∈N
X
2
2
∗
− (n − 2)
=
qi (g) − γ 2 1 −
α−
n+1
n+1
i∈N
X
4
4 − 2n
∗
α−
qi (g) − γ 2 −
+
=
n+1
n+1
i∈N
X
n
∗
qi (g) − 2γ 1 −
=
α−
n+1
i∈N
X
2
α−
=
qi∗ (g) − γ
n+1
= α−
X
qi∗ (g)
+ (n − 2)γ
i∈N
= p(g) − γ
2
n+1
(54)
Consider now players’ payoffs. At first look at the payoff function of
player i (19) in the new network g̃.
πi (g̃) = (qi∗ (g̃))2 =
= qi∗ (g) + γ 1 −
2
2
=
n+1
2
2
2
2
∗
∗
= (qi (g)) + 2qi (g)γ 1 −
+ γ 1−
=
n+1
n+1
2
2
γ 1−
+ 2qi∗ (g) > πi (g)
= πi (g) + γ 1 −
n+1
n+1
It means that addition of a new link (ij) is always profitable for players i and
j.
26
The payoff of player k 6= i, j in the network g̃ has the following form:
πk (g̃) = (qk∗ (g̃))2 =
= qk∗ (g) − γ
(55)
2
n+1
2
=
2
2
2
+ γ
=
−
=
n+1
n+1
1
4
γ
− qk∗ (g) .
= πk (g) + γ
n+1
n+1
(qk∗ (g))2
2qk∗ (g)γ
Hence, we obtain the following inequality:
πk (g̃) > πk (g)
(56)
if the following condition holds:
γ
1
− qk∗ (g) > 0,
n+1
(57)
or
qk∗ (g) 6 γ
1
.
n+1
(58)
We can say that payoff for player k 6= i, j does not increase after players
i and j formed a new connection if the condition (58) holds. In general while
players i, j always gain, player k profits in network g̃ in comparison to the
network g if the condition (58) holds.
We may notice one more interesting property of the game: the more
players are in the game the more quantity and payoff of player increase when
the player establishes a new connection in network. And consequently the
common price of product decreases.
27
2.5.1
Regular networks
Examine how equilibrium quantity, payoff and price functions change in the
special case of regular network g.
Definition 1. A regular network is a network where each node has the same
number of neighbors. A regular network with nodes of degree k is called a
k-regular network or regular network of degree k.
Figure 7: Examples of regular networks.
28
Write down the optimum quantity (17) for k-regular network g:
α − γ0 + nγk − γ(n − 1)k
=
n+1
α − γ0 + γk
.
=
n+1
qi∗ (g) =
(59)
We can notice that in the case of k-regular network the equilibrium
quantity has simple form. Notice that the equilibrium quantity is linearly
dependent upon regularity of the network k. And hence the payoff function
πi (g) has quadratic dependency upon k:
πi (g) = qi∗2 (g) =
α − γ0
k
+γ
n+1
n+1
2
.
(60)
The form of price function for k-regular network can be obtained from
(5) in the following way:
p(g) = α −
X
qi∗ (g) =
i∈N
α − γ0 + γk
=
n+1
(n + 1)α − n(α − γ0 + γk)
=
=
n+1
α + nγ0 − nγk
=
.
n+1
= α−n
2.5.2
(61)
Example
Let us consider the following example. For three cases of network with 11,
12 and 20 players select the parameters according to (23):
α = 574, γ0 = 21, γ = 1.
(62)
Compare equilibrium prices, quantities and profits for different k-regular networks with n players. From the Figure 8 below we can observe a positive
29
correlation between degree of node of regular network and the value of the
payoff function πi (g). And also we see how fast payoff fails with the increasing number of players n while game parameters do not change. The next
Figure 9 demonstrates that the same relations hold for equilibrium quantities. But here we observe that quantity decreases slower than the payoff
with the increasing number of players n. Figure 10 shows us the connection
between price, regularity and the number of players n. We can notice that
price decreases with the degree of the node in a regular network. And having
parameters α, γ0 , γ fixed price fails with the increasing number of players n.
Figure 8: Payoffs for different regular networks.
Figure 9: Quantities for different regular networks.
30
Figure 10: Prices for different regular networks.
2.6
Weighted network
The model under consideration ignores distances between firms since it is far
from the real life. In this section we cover this issue.
Let us assume that there is given a complete weighted network g. Firms
are settled in nodes. We may suppose that our network is complete: every
firm can reach collaboration with any other firm, but it does not always have
a surplus from the collaboration. In order to show this magnitude of profit,
each link has a weight which can mean a cost of one supply of resources
between nodes which are incident to the link. This cost is the aggregation of
length of the link and costs of establishing the link. We do not go further in
describing this aggregation because assume that it can be defined differently
for each industry.
The first approach is based upon the idea that if two firms are located
one close to another they can achieve bigger profit from collaboration with
each other neither they are far from each other. We can write this idea in
terms of the cost function:
ci (g) = γ0 − max dij ,
j∈ηi (g)
31
(63)
where dij is the length of the shortest path from firm i to j. Here the word
”shortest” should be understood as the way of collaboration of firms i and j
which is the most benefit. This ”shortest” collaboration can be better than
others not only because of the distances of roads on travel map but also
because of new conditions in collaboration agreement.
If we repeat the steps which we have done when searched equilibrium
at fixed network we will obtain that the equilibrium quantity of firm i for a
such cost is the following
α − γ0 + n maxj∈ηi (g) dij −
qi∗ (g) =
n+1
P
k6=i maxj∈ηk (g) dkj
.
We can see that the structure of equilibrium quantity does not change
after replacing ηj (g) with dij . And the player i’s payoff stays the same:
πi (g) = qi∗2 (g).
32
3
Cooperative game
When it comes to cooperation the most natural question of players which
decided to cooperate in coalition S ⊆ N is how to maximize they common
payoff:
πS (g, q) =
X
(p(q) − ci (g))qi .
(64)
i∈S
Due to the network structure of our game there are two possible ways
to cooperate. Firms can cooperate from the first stage – and play as the
one union at network formation step and quantity competition step. We call
this type of cooperation a full cooperation. Another way of cooperation is
to play individually at the network formation stage and start to cooperate
only at quantities competition. We call it quantity cooperation. We consider
both types of cooperation. In case of quantity cooperation network is already
formed so we need to construct the characteristic function for the game on the
fixed network – v(g, S), where g is fixed. In case of full cooperation players
are able to choose how to form the network, therefore we need to construct
the characteristic function v(S) that depends only upon coalition S ⊆ N .
Start from the detail consideration of the quantity cooperation. Cooperative game theory provides a rule of how the total payoff (64) of all players
should be split among themselves. It takes into account the relative payoffs
that every possible subset of players could get. A cooperative game is defined
by the set of players N and the characteristic function v, which denotes the
power of each coalition S ⊆ N . The characteristic function v is a mapping
from 2N to real numbers and normalized such that v(∅) = 0. To make cooperation interesting for players characteristic function v has to satisfy the
33
superadditivity condition:
v(g, S ∪ T ) > v(g, S) + v(g, T ),
∀S, T ⊂ N, S ∩ T = ∅
(65)
In this section we examine whether the players would want to cooperate
and we find allocations of expected sum of players’ payoffs (64) using the
cooperative game theory tools adapted for network settings.
There are several ways to define a characteristic value of a coalition
when we want to consider a cooperative version of a normal-form game.
They are:
• The value of the maximin optimization problem, when coalition S attempts to maximize its payoff and complement coalition N \ S tries to
minimize it.
• The value of the maximization problem, when coalition S maximizes its
payoff while players which do not belong to it play fixed strategies, for
example Nash equilibrium strategies.
• The equilibrium payoff of coalition S in game in normal form of |N | −
|S|+1 players where one player is coalition S and others - are individuals.
We will illustrate the first option in detail. The other two options are
discussed further. Since we defined powers of coalitions via characteristic
function the next most straightforward question of how payoffs should be
divided is that the division should be fair. Such fair allocation is called an
imputation.
Definition 2. Vector φ = (φ1 , φ2 , . . . , φn ) such that
P
i∈N
φi = v(g, N ) is
called an imputation if φi > v(g, i), ∀i ∈ N – each player surplus at least
what he can get playing individually.
34
Figure 11: Imputation set for a two-person game.
Figure 12: Imputation set for a three-person game.
We will consider two imputations for our game: the Shapley value and
the CIS value. Shapley value ensures that players which contribute more to
the coalitions than others gain more from cooperation.
Definition 3. Given a cooperative game (N, v), the component of the Shap35
ley value of player i is given by
X
1
φi (g, v) =
|S|!(|N | − |S| − 1)! [v(g, S ∪ {i}) − v(g, S)] .
|N |!
(66)
S⊆N \{i}
Definition 4. CIS (center of gravity of the imputation set) for the game
(N, v) is defined as
CISi (g, v) = v(g, {i}) +
X
1
v(g, N ) −
v(g, {j}) , i ∈ N.
n
(67)
j∈N
We suppose that when firms cooperate with each other, cost of production of one unit for every firm is the minimal cost in the coalition. Put
differently, all firms in the coalition use some resources or technology of the
firm with minimal production cost. We can determine a cost function of
coalition S:
cS (g) = min ci (g) = γ − γ0 max ηi (g).
i∈S
i∈S
(68)
By analogy we determine characteristic function v(S), Shapley and CIS
value φi (v).
3.1
Maximin
Consider the game of quantities of only two players: coalition S and its
complement N \ S. They play a zero-sum game. It means that the first
player S wishes to maximize his payoff and the second player N \ S attempts
to minimize S’s payoff. Since maximin value of a player S is the largest
payoff that the player S can be sure to get regardless of the action of the
other player N \ S. Since players in the coalition play as one big firm they
need to maximize the sum of their payoffs over the sum of their quantities.
36
3.1.1
Characteristic function
We start from quantity cooperation. Suppose that network g is fixed. Let
us formulate the characteristic function for a fixed network g and coalition
S ⊆ N:
v(g, S) = max
min
qi , i∈S qj , j∈N \S
X
πi (g, q1 , . . . , qn ) .
(69)
i∈S
Denote the sum of quantities of players in coalition S as QS , i.e.,
X
qi = Q S ,
(70)
i∈S
and by analogy
X
qi = QN \S .
i∈N \S
In this notations we may write down the problem (69) in shorter form:
v(g, S) = max min
QS QN \S
X
πi (g, q1 , . . . , qn ) = max min QS (p − cS (g)) .
QS QN \S
i∈S
(71)
Eventually, the characteristic function takes the following form.
v(g, S) = max min QS α − QS − QN \S − cS (g) .
QS QN \S
(72)
Compute the characteristic function for different coalitions. Let us start
from grand coalition S = N .
v(g, N ) = max QN (α − QN − cN (g))
QN
(73)
In this case we have maximization problem of the variable QN . To find QN
such that v(g, N ) is the maximum, compute the derivative and equal it to
37
zero according to the necessary condition for an extremum:
∂
(QN (α − QN − cN (g))) = 0.
∂QN
(74)
We obtain the following:
α − cN (g) − 2QN = 0.
(75)
And hence, the optimum quantity for grand coalition N is
Q∗N =
α − cN (g)
.
2
(76)
Due to the economic approach of our game we should hold the constraint of non-negatively of quantity:
Q∗N > 0 ⇒ α > cN (g).
(77)
Finally, the characteristic function for the grand coalition is the following.
v(g, N ) =
2
Q∗N
(α − cN (g))2
=
4
(78)
Let us now compute characteristic function for another coalition S ⊂
N, S 6= N . Consider the expression α − QS − QN \S − cN (g) . Notice that
while in the game there is only one constraint – non-negativeness of price
function, complement coalition N \ S is always able to zero maximin value
by taking its strategy QN \S as follows
QN \S = α − cS (g).
38
(79)
Indeed, after substitution the above replacement into (72) we have:
v(g, S) = max QS (−QS ) = 0
QS
(80)
We obtain that v(g, S) = 0, ∀S ⊂ N, S 6= N .
Now compute characteristic function for full cooperation in the twostage game. In this case we need to find the value of the following maximin
optimization problem:
v(S) = max
min
gi , qi , i∈S gj , qj , j∈N \S
X
πi (g, q1 , . . . , qn ) .
(81)
i∈S
Suppose that actions gS = {gi , i ∈ S} and QS is already chosen. Then the
best option for coalition N \ S to choose gN \S is such that nobody from
N \ S has links with players in coalition S. And the action QN \S for coalition
N \ S is (79). Consequently we obtain that the characteristic function in
the full cooperation coincides with the characteristic function in quantities
cooperation.
One more advantage of maximin construction of characteristic function
is that we do not need to prove superadditivity of our game (N, v) – it is well
known fact. The next aim in cooperative analysis of the game is the Shapley
value.
39
3.1.2
Cooperative solution
Let us substitute the value of the characteristic function into (66) to calculate
the component of the Shapley value of player i ∈ N :
φi (g, N, v) =
=
=
1
|N |!
P
1
|N |! |N
=
S⊆N \{i} |S|!(|N |
− |S| − 1)! [v(g, S ∪ {i}) − v(g, S)] =
\ {i}|!(|N | − |N \ {i}| − 1)! [v(g, N ) − v(g, N \ {i})] =
1
|N |! (|N |
− 1)!(|N | − |N | + 1 − 1)! [v(g, N ) − 0] =
=
v(g,N )
|N |
=
2
=
Q∗N
|N |
=
(α−cN (g))
4|N |
(α−γ0 +γ maxi∈N ηi (g))
4|N |
2
=
2
.
(82)
Compute another solution – component of the CIS vector (67) of player i ∈ N :
h
i
P
CISi (g, N, v) = v(g, {i}) + v(g, N ) − j∈N v(g, {j}) =
1
n
=
(α−γ0 +γ maxi∈N ηi (g))
4|N |
v(g,N )
|N |
=
2
.
(83)
Notice that the CIS value coincides with the Shapley value. It happens
because the value of the characteristic function is not equal to zero only in
the case of grand coalition N . We may conclude that all players get the same
payoff after distribution – no matter whether cost of production is minimal
for some player.
3.2
Sensitivity analysis
From the expression of the Shapley value (82) we can conclude that all players
get equal payoffs. Moreover, these payoffs do not depend on the network
topology. On the Figure 13 we can observe two networks – star and complete
networks of 10 players. The degree of central player in star network coincides
40
with the degree of every player in complete network. Other players in the star
network have less degree but still get the same payoff as the central player.
Figure 13: Star and complete networks.
3.2.1
Regular networks
In case of the k-regular network the maximum node degree maxi∈N ηi (g)
coincides with every node degree ηi (g), ∀i ∈ N and equals to k right from
the definition of the regular network. Hence obtain the following:
φi (g, N, v) =
α − γ0
k
+γ
n+1
n+1
2
∀i ∈ N.
It coincides with the payoff (60) without cooperation at all. Hence, defining
the characteristic value as the value minimax optimization problem and by
applying the Shapley value (and CIS value) as imputation we obtain that
cooperation is not profitable for players relatively to non-coopearation behavior.
41
4
Two-stage oligopoly with offering costs
In previous sections we examined the model of firms competition in oneproduct market on a network in which link offers were cost-free. Costs were
taken only from formed links – when two players offered the collaboration to
each other and consequently start of cooperating. But in real life there are
situations when the offer of the link could cost something for the firm which
proposed it. Even a simple phone call to the potential client may be estimated
as an amount of money and represents the offer cost. Another example of
the offer cost could arise in situation when firm is trying to figure out how
the cooperation could increase its payoff – firms do research of production
techniques, legal documents audit and lawyers consultations and so on. It
may cost significant and firms should think one more time before deciding to
make an offer of collaboration to some other firm.
These thoughts come us to a new cost function of link offer:
li (g) = µηiout (g), µ > 0.
(84)
Here we use new notation ηiout (g) – it is the out-degree of player i in network
g, the number of collaboration offered by player i indeed. The parameter µ
represents the cost of one offer.
And it leads us to the following payoff function:
πi (g, q) = (p(q) − ci (g))qi − li (g).
4.1
(85)
Equilibrium at fixed network
Here we will make a similar analysis of the non-cooperative game to the
analysis provided in the first section but with the new payoff function (85).
Our aim here is to study how the new offer’s costs will influence payoffs,
42
equilibria and optimal strategies.
We start from finding the optimal quantity on fixed network. To find
such optimal quantity, i.e. Nash equilibrium, we should satisfy two conditions: the first order (7) and the second order (8) conditions. But we may
notice that if we take the derivative over q of the new payoff function we will
obtain exactly the same system of equations as (11). It means that this step
has already done and optimal quantity for fixed network in the case of new
model coincides with the same one in the old model (20).
4.2
Equilibrium in the two-stage game
Repeat the same steps as in the first section. We assume that g is a pairwise
network and we will find what conditions on quantity should hold in order
to action profile (g, q) be a Nash equilibrium.
Suppose that given a pairwise network g ∗ , deviation of player i from
the strategy gi∗ to the strategy gi expresses in the form (24). Having the same
reasoning involving expressions (25), (26), (27), (28). We proceed till the we
moment we need to maximize over gi .
Substitute the optimal qi into the πi (g ∗ , q ∗ ||gi , qi ) to obtain
maxqi πi (g ∗ , q ∗ ||gi , qi ):
max πi (g ∗ , q ∗ ||gi , qi ) =
qi
= α −
X
qj∗ (g ∗ ) − qi − γ0 + γηi (g ∗ ||gi ) qi − li (g ∗ ||gi ) =
j6=i
(86)
43
= α −
X
qj∗ (g ∗ ) −
α−
∗ ∗
j6=i qj (g )
P
j6=i
∗
− γ0 + γηi (g ||gi )
− γ0 + γηi (g ∗ ||gi ) ×
2
− γ0 + γηi (g ∗ ||gi )
− µηiout (g ∗ ||gi ) =
×
2
P
∗ ∗
α − j6=i qj (g ) − γ0 + γηi (g ∗ ||gi ) 2
− µηiout (g ∗ ||gi ) =
=
2
2
X
1
= α −
qj∗ (g ∗ ) − γ0 + γηi (g ∗ ||gi ) − µηiout (g ∗ ||gi ) =
4
j6=i
2
X
1
= α −
qj∗ (g ∗ ) + qi∗ (g ∗ ) − γ0 + γηi (g ∗ ||gi ) − µηiout (g ∗ ||gi ) =
4
α−
∗ ∗
j6=i qj (g )
P
j∈N
Substitute formula (13) instead of sum
P
j∈N
qj∗ (g ∗ ) and formula (20)
instead of qi∗ (g ∗ ) into the last expression above:
P
n(α − γ0 ) + γ i∈N ηi (g ∗ )
1
=
α−
+
4
n+1
P
2
α − γ0 + nγηi (g ∗ ) − γ j6=i ηj (g ∗ )
∗
+
− γ0 + γηi (g ||gi ) − µηiout (g ∗ ||gi ) =
n+1
P
2
α − γ0 − γ i∈N ηi (g ∗ ) γ
∗
∗
=
+
ηi (g ) + ηi (g ||gi )
− µηiout (g ∗ ||gi ) =
n+1
2
2
γ
∗ ∗
∗
∗
= qi (g ) +
ηi (g ||gi ) − ηi (g )
− µηiout (g ∗ ||gi )
2
We obtain the maximum over quantity (when player i is deviating in
quantity) of the right-hand side of the (28):
∗
∗
max πi (g , q ||gi , qi ) =
qi
qi∗ (g ∗ )
2
γ
∗
∗
+
ηi (g ||gi ) − ηi (g )
− µηiout (g ∗ ||gi )
2
(87)
Now we need to solve the maximization over gi problem:
maxgi maxqi πi (g ∗ , q ∗ ||gi , qi ) =
2
γ
= maxgi qi∗ (g ∗ ) + 2 ηi (g ∗ ||gi ) − ηi (g ∗ )
− µηiout (g ∗ ||gi )
44
(88)
(89)
Since the inequality below holds
ηiout (g ∗ ||gi ) > ηi (g ∗ ||gi )∀i ∈ N ∀gi
(90)
We have the following:
2
maxgi qi∗ (g ∗ ) + γ2 ηi (g ∗ ||gi ) − ηi (g ∗ )
− µηiout (g ∗ ||gi ) 6
2
γ
− µηi (g ∗ ||gi ) =
6 maxgi qi∗ (g ∗ ) + 2 ηi (g ∗ ||gi ) − ηi (g ∗ )
h
2
= maxgi (ηi (g ∗ ||gi ))2 + ηi (g ∗ ||gi ) γqi∗ (g ∗ ) − µ − γ2 ηi (g ∗ ) +
i
γ2
∗ ∗ 2
∗ ∗
∗
∗ 2
+ (qi (g )) − γqi (g )ηi (g ) − 4 (ηi (g ))
According to the (24) the last expression maximizes when ηi (g ∗ ||gi ) =
ηi (g ∗ ). Finally we obtain the following:
max max πi (g ∗ , q ∗ ||gi , qi ) = (qi∗ (g ∗ ))2 − µηi (g ∗ )
(91)
πi (g ∗ , q ∗ ) = (qi∗ (g ∗ ))2 − µηiout (g ∗ ), i ∈ N
(92)
gi
qi
Since
the Nash equilibrium inequality (25) holds if
(qi∗ (g ∗ ))2 − µηiout (g ∗ ) > (qi∗ (g ∗ ))2 − µηi (g ∗ ), i ∈ N,
or
ηiout (g ∗ ) 6 ηi (g ∗ ) i ∈ N.
But from the definition of ηiout (g)
ηiout (g ∗ ) > ηi (g ∗ ) i ∈ N.
Consequently, (25) holds only when ηiout (g ∗ ) = ηi (g ∗ ).
45
(93)
Proposition 5. Pairwise network g ∗ is the Nash equilibrium if the following
condition holds
ηiout (g ∗ ) = ηi (g ∗ ) ∀i ∈ N.
(94)
Hence we proved that Nash equilibrium inequality (25) holds for new
payoff function. It means that in this new model pairwise networks are the
Nash equilibria, i.e. costs of offering the links do not break this equilibria.
4.3
Sensitivity analysis
We provide the sensitivity analysis of this new model by analogy with the
sensitivity analysis of the previous model in order to compare how the equivalent actions influence quantities, payoffs of different players. As before we
will use equilibrium quantities (17) for given network g which are dependent
on a network structure so for the simplification we will discard the parameter
q in the payoff function (6).
Because the price function in the the model with offering costs depends
only on quantities it does not change from the model without offering costs.
Suppose that player i in given network g deletes the link with player j,
and player j deletes the link with player i as well. After this transformation
network g changes and we denote the new network by g̃. An example of such
situation is illustrated on Figure 5.
Consider players’ payoffs. At first look at the payoff function of player
i (19) in the new network g̃. The payoff of player j is changed by the same
46
rule:
πi (g̃) = (qi∗ (g̃))2 − µηiout (g̃) =
2
2
γ 1−
−2 +µ=
= (qi∗ (g))2 − µηiout (g) + γ 1 −
n+1
n+1
2
2
= πi (g) + γ 1 −
γ 1−
−2 +µ
n+1
n+1
πi (g̃) = (qi∗ (g̃))2 − µηiout (g̃) =
2
2
∗
= qi (g) − γ 1 −
− µ(ηiout (g) − 1) =
n+1
2
2
γ 1−
− 2qi∗ (g) + µ
= πi (g) + γ 1 −
n+1
n+1
Let us find out under which constraint player i (and player j) benefits from the removing the link (ij). The payoff of player i has a negative
correlation with the deletion of the collaboration if the next condition holds:
2
γ 1−
n+1
γ 1−
2
n+1
− 2qi∗ (g) + µ < 0.
(95)
The analysis of the payoff of player k 6= i, j in the network g̃ does not
change from the analysis provided for the previous model because ηiout (g̃) =
ηiout (g). We obtain that if the condition (95) holds, players i, j lose in the
network g̃ in comparison to the network g. In contrast, player k never loses
in the network g̃ in comparison to the network g.
47
5
Alternative characteristic functions of cooperative
game
As we said in the Section 3 there are several options for defining a characteristic function. Here we construct characteristic function for the two left
variants.
5.1
Maximization of S’s payoff with Nash equilibrium strategies
for other individuals
We have a quantity competition game of |N | − |S| + 1 players, in which one
player is the coalition S and other players choose fixed Nash equilibrium
actions (17) as if they played as singletons. Players which do not belong
to the coalition S suppose that they play with individuals like they are. It
means that they do not know that some players silently formed a coalition
and play as one player. For the simplicity let us say that the first |S| players
in the initial non-cooperative game of |N | players belong to coalition S in the
cooperative game. Then
v(g, S) = max
qi ,i∈S
X
∗
πk (g, q1 , . . . , q|S| , q|S|+1
, . . . , qn∗ ).
(96)
k∈S
We may rewrite this expression in more convenient form using short
notation (70) as follows
v(g, S) = max α − cS (g) − QS −
QS
X
qj∗ QS .
(97)
j∈N \S
According to the necessary condition for an extremum of quadratic function
48
we found optimal quantity of coalition S:
Q∗S
=
α − cS (g) −
P
∗
j∈N \S qj
2
.
(98)
To express equilibrium quantity Q∗S through initial parameters of the
game, we substitute qi∗ from (17):
X α − γ0 + nγηi (g) − γ
1
∗
QS =
α − cS (g) −
2
n+1
P
j6=i ηj (g)
.
i∈N \S
Let us compute separately the sum in brackets from the last equation:
P
=
P
α−γ0 +nγηi (g)−γ
i∈N \S
n+1
P
j6=i
P
ηj (g)
=
α−γ0 −γ j∈N ηj (g)
n+1
γηi (g) +
=
P
P
P
P
1
= γ i∈N \S ηi (g) + n+1
i∈N \S (α − γ0 ) − γ
i∈N \S
j∈N ηj (g) =
P
P
|N |−|S|
= γ i∈N \S ηi (g) + n+1 (α − γ0 ) − γ j∈N ηj (g) =
P
P
n−|S|
= n+1 (α − γ0 ) − γ j∈S ηj (g) + |S|+1
γ
i∈N \S ηi (g)
n+1
i∈N \S
Now we are able to substitute this sum into (98).
P
|S|+1 P
(α
−
γ
)
−
γ
η
(g)
−
γ
η
(g)
=
Q∗S = 12 α − cS (g) − n−|S|
0
j∈S j
i∈N \S i
n+1
n+1
P
|S|+1 P
= 12 α − γ0 + γ maxj∈S ηj (g) − n−|S|
(α
−
γ
)
−
γ
η
(g)
−
γ
η
(g)
=
0
j∈S j
i∈N \S i
n+1
n+1
n−|S| P
|S|+1 P
= 21 |S|+1
j∈S ηj (g) − n+1 γ
i∈N \S ηi (g)
n+1 (α − γ0 ) + γ maxj∈S ηj (g) − n+1 γ
For grand coalition N , the sum of qi∗ there is no in the formula (97). So
the expression for optimal Q∗N is significantly shorter and coincides with corresponding expression for the first case of constructing characteristic function
– (76) and has the following form:
Q∗N =
α − cN (g)
.
2
49
(99)
5.2
Equilibrium in the game with |N | − |S| + 1 players
Here to determine characteristic function v(g, S) we consider the game of
(|N | − |S| + 1) players, where one player represents coalition S and other
players are individuals. Unlike from the previous way of defining characteristic function here all players know that one player actually represents a group
of players. Suppose that first |S| players of N are in coalition S. Players
have the following payoff functions:
πS (g, g, QS , q|S|+1 , . . . , qn ) = (p − cS (g)) QS , for player-coalition S
πi (g, g, q|S|+1 , . . . , qn ) = (p − ci (g)) qi , ∀i ∈ N \ S.
Then the characteristic function v(g, S) is the equilibrium payoff of
coalition S when quantities of production are fixed optimal quantities in
Nash equilibrium.
X
v(g, S) = α − Q∗S −
qj∗ − cS (g) Q∗S
(100)
j∈N \S
Now let us find Nash equilibrium in this game:
P
∂πS (g = α − 2QS −
for player S
j∈N \S qj − cS (g) = 0,
∂QS
∂πi (g) = α − Q − q − P
S
i
j∈N \S qj − ci (g) = 0, ∀i ∈ N \ S
∂qi
P
α − QS −
j∈N
qj − cS (g) = 0
α − q − P
i
j∈N qj − ci (g) = 0,
(101)
∀i ∈ N \ S
Here we can notice an interesting connection between individual quan-
50
tity qi , ∀i ∈ N \ S and coalition quantity QS from the system (101) above
α − cS (g) − QS =
X
qj = α − ci (g) − qi .
j∈N
From which we obtain the following:
cS (g) + QS = ci (g) + qi , ∀i ∈ N \ S.
When we sum equations for i ∈ N \ S we obtain the following.
(n − |S|)α −
X
qi − (n − |S|)
X
qj −
j∈N
i∈N \S
X
ci (g) = 0
i∈N \S
After addition first equation to this sum we get this expression.
(n − |S| + 1)α − (n − |S| + 2)
X
qj − cS (g) −
j∈N
X
ci (g) = 0
i∈N \S
From this equation we express the sum of all quantities.
X
j∈N
qj =
X
1
(n − |S| + 1)α − cS (g) −
ci (g)
n − |S| + 2
i∈N \S
Finally, let us substitute the last expression into the first equation of the
system.
QS = α −
X
qj − cS (g)
j∈N
QS = α − cS (g) −
(n − |S| + 1)α − cS (g) −
P
i∈N \S ci (g)
n − |S| + 2
We found optimal Q∗S in Nash equilibrium.
Q∗S =
α − (n − |S| + 1)cS (g) +
P
i∈N \S ci (g)
n − |S| + 2
For the case of grand coalition N we have the following short form, which also
51
coincides with corresponding expressions for the other ways of constructing
characteristic function.
Q∗N =
α − cN (g)
2
By substituting the expression of sum of quantities into the remaining equations of the system.
qi = α −
X
qj − ci (g), ∀i ∈ N \ S
j∈N
qi = α − ci (g) −
(n − |S| + 1)α − cS (g) −
P
j∈N \S cj (g)
n − |S| + 2
, ∀i ∈ N \ S
Finally we found optimal quantities for remaining individual players i ∈ N \S.
q∗i =
α + cS (g) − (n − |S| + 1)ci (g) +
P
j∈N \(S∪{i}) cj (g)
n − |S| + 2
, ∀i ∈ N \ S
Now we are able to write down characteristic function because we already know all optimal quantities.
v(g, S) = α − Q∗S −
X
j∈N \S
52
2
qj∗ − cS (g) Q∗S = Q∗S
(102)
6
Conclusion
In this thesis we investigated the one-product market competition in quantities of n firms. In our model firms are able to establish collaborations
between themselves and chose quantities of production. The set of pairwise
collaborations defines the network. As the payoff function we use profit from
production and selling goods. The network effect appears in payoff function
and more precisely in marginal costs. The marginal cost of firm is negatively
correlated with the number of formed collaboration links of the firm. We
considered both non-cooperative and cooperative games and used Nash equilibrium as a non-cooperative solution of the two-stage game and the Shapley
value as a cooperative solution. At first we found the equilibrium quantity of
player when the network is fixed. Then we considered the two-stage game and
found the equilibrium strategies: they are pairwise networks and equilibrium
quantities which coincides with the equilibrium quantities for fixed network.
Since there are too many equilibria in the two-stage game we provided an
analysis of some specific networks and compared different configurations. We
characterized and compared firms’ payoffs under different collaboration structures: the empty network, a regular network, the complete network, and a
star-like network. To uncover how the collaborations influence the price function and payoffs of players we provided the sensitivity analysis of removing
and adding a collaboration link. There was found the amount of surplus for
players who were involved in the establishing of the new collaboration link.
And it was found how much the common market price decreases with the
degree of the node in a regular network and obtained that price increases
with the number of firms in the market. For the special case of the regular networks we found explicit formulas of the equilibrium quantity and the
price and provided a sensitivity analysis, in which we showed on the numer53
ical example how the degree of node and the number of players affect on
the market price, quantities and payoffs of players. We also introduced an
approach of the model to the weighted networks and showed that in this case
the structure of the equilibrium quantity was not changed.
After the non-cooperative game we considered a cooperative game. We
illustrated options of choosing the characteristic function. We defined the
value of the characteristic function as the solution of the maximin optimization problem. Then we found the Shapley value and the CIS value as solutions. It did happen that they coincide. It means that in the cooperative
game all players get equal payoffs. Moreover, for the regular network the
payoff of the player in the cooperative game coincides with his payoff in the
non-cooperative game. We also obtained that in the cooperative game for the
maximin characteristic function, players are indifferent to the network structure whether maximum degree of the node in the network does not change.
Next we additionally examined an extended version of the model: twostage oligopoly with offering costs. This model can emerge from numerous
economic applications when the offer of the collaboration leads to extra costs,
without confidence that it will be accepted. We justified that the equilibrium
strategies for the prior model are the equilibrium strategies but with one
condition.
54
References
[1] Aumann, R., Myerson, R. Endogenous formation of links between players
and coalitions: an application of the Shapley Value // The Shapley
Value. Cambridge Univ. Press, Cambridge, 1989.
[2] d’Aspremont, C., Jacquemin, A. Cooperative and non-cooperative Research and Development in duopoly with spillovers // American Economic Review, 1988. No 78. P. 1133–1137.
[3] Bala, V., Goyal, S. A non-cooperative model of network formation //
Econometrica, 2000. No 68. P. 1181–1231.
[4] Bloch, F. Non-cooperative models of coalition formation with spillovers
// The Economic Theory of the Environment. Cambridge Univ. Press,
Cambridge, 1997.
[5] Driessen T., Funaki Y. Coincidence of and collinearity between game
theoretic solutions // ORSpektrum, 1991. No. 13. P. 15–30.
[6] Goyal, S., Joshi, S. Collaboration and competition in networks // Center
for Development Economics, Delhi, Working Paper 1999. No. 64.
[7] Goyal S., Joshi S. Networks of collaboration in oligopoly // Games and
Economic Behavior, 2003. Vol. 43, No. 1. P.57-85.
[8] Jackson M., Watts A. On the formation of interaction networks in social
coordination games // Games and Economic Behavior. 2002. Vol. 41 (2).
P. 265–291.
[9] Jackson M. Social and Economic Networks // Princeton University
Press, 2008.
55
[10] Leyton-Brown K., Shoham Y. Essentials of Game Theory // Morgan
and Claypool, 2008.
[11] Petrosyan L., Sedakov A. Bochkarev A. Two-stage network games //
Mathematical Game Theory and Applications, 2013. Vol. 5, No. 4, P.
84-104.
[12] Shapley L. A value for n-person games // In: Kuhn W., Tucker A.W.
(Eds.) Contributions to the Theory of Games II, Princeton. Princeton
University Press. 1953. P. 307–317.
[13] Slikker, M., van den Nouweland, C. Network Formation Models With
Costs for Establishing Links // FEW Research Memorandum, 1999. Vol.
771.
[14] Tirole J. The Theory of Industrial Organization // The MIT Press, 1988.
56
Отзывы:
Авторизуйтесь, чтобы оставить отзыв