# Applying Graph Theory to Some Problems of Economic Dynamics

Authors: S. I. Hamidov
Journal: Discrete Dynamics in Nature and Society
 (2019)

---

## Abstract

This paper studies dynamic models of production and exchange on graph with consideration of transportation costs. Using graph and set of matrices, we introduce superlinear multivalued mappings which describe the exchange ratio in considered system. Effective trajectories of these models are studied. It is shown that trajectories can be constructed using the simplest equilibrium type mechanisms. Characteristics of effective trajectories in Neumann type models are given. Conditions for the existence of equilibrium state of the considered model are found.


---

## Body

## 1. Introduction

A lot of works appeared lately dealing with the applications of graph theory to some models of economic dynamics [1–3] and related extremal problems [2, 4–9]. In this paper, an attempt is made to apply the elements of graph theory to the models of economic dynamics with consideration of transportation costs. We consider production mappings which define the Neumann-Gale model [10].Consider a digraph with no multiple arcsɣ=(J,G), where J={1,2…m} is a set of vertices andG⊂ J x J is a set of arcs. Multivalued mapping with the graphic G is denoted by the same symbol G. Thus,G (i) consists of those verticesj for which there exists an arc fromitoj. For convenience, we will assume that each vertex is provided with a loop, i.e.,i∈G(i)for everyi. The simulated economic system operates withnproducts. If there is a product vector yj=(yj1,yj2,…,yjn)∈R+n at the vertexj∈G, where R+n={x∈Rn:x≥0} then any part ujk of this vector (0≤ujk≤yj) can be transferred (transported) to the vertex k∈G(j). Each arc (j, k)∈G is associated with some nonnegative matrix Сjk, by means of which “transport costs” are taken into account in some generalized sense. This means that if the vector ujk at the vertex j is selected for transmission to the vertex k, then the vector Cjkujk moves to the latter vertex. The additional vector ujk -Cjkujk, in case of its nonnegativity, can be considered as a transportation fee, which is withdrawn from the system. We can assume that Cjk is a diagonal matrix with nonnegative diagonal elements vjkl≤1, where 1-vjkl coincides with the fraction of the unit of thel-th product, which should be paid for the transportation of this unit along the arc(j, k). But this kind of matrix Сjk will not be used in the sequel. We assume below that Сjj coincides with the identity matrixE for allj∈J (no need to pay for the transportation from a vertex to itself).Consider the complete graphγ~ with the same set of vertices J, and associate every pair (j, k)∈J x J with the matrix C~jk by letting C~jk=Cjk if (j, k)∈G and C~jk=0 otherwise. The problems below may be considered on a complete graph γ; i.e., instead of the system (J,G,Cjk(j,k)∈G) one may consider (J,J x J,Cjk(j,k)∈J). In other words, the arc (j, k)∈J x J is obviously forbidden in these problems if C~jk=0. But it would be convenient for us to express the set of arcs G in explicit form. Using the graph γ=(J,G) and the set of the matrices Cjk(j,k)∈G, we can introduce the mapping В, which describes the exchange relation in the simulated system. This mapping is defined on the cone R+nm. Let Y=(y1,y2,…,ym), where yi is a vector of products in the vertex i. Then(1)BY=Z=z1,…,zm:zk=∑j∈G-1kcjkujkK=1,2,…,m;uij≥0foralli,j∈G∑j∈Giuij=yi,i=1,2,…,m.It is easy to verify that the mapping В is superlinear, i.e., it has the following three properties:(1)
B(Y1+ Y2)⊃ B(Y1) + B(Y2)(2)
B(λY) = λB(Y); λ≥0(3)
The graph of the mapping В, i.e., the setgrB={(Y,Z):Z∈B(Y)}, is closed; besides, the following conditions are satisfied:(4)
B(0) ={0}(5)
B(R+nm)=R+nmEquality (9) follows from the fact that Y∈B(Y) for all Y. Production capabilities of the vertex j∈J are described by the superlinear mapping aj: R+n→2R+n.It is assumed thataj(0)=0 for all j. Production capabilities of the entire system are given by the mapping A defined on the cone R+nm.If X=(X1,…,Xm)∈R+nm, then(2)АХ=a1х1·a2х2·…·amxm,In other words,(3)AX=Y=y1,y2,…,ym:yi∈aiXi,i=1,2,…,mMain Part. The operations performed by the entire system over a period of time consist of production and exchange. These operations can be carried out in different order. If the production comes first followed by the exchange, then the work of the system is described by the composition a = В∘А of the mappings A and B:(4)aX=⋃Y∈AXBY,X∈R+nm.Conversely, if the exchange happens first and then comes production, then we should consider the composition b = A∘B of the mappings B and A:(5)bY=⋃Z∈BYAZ,Y∈R+nm.It is obvious that the mappingsaandb are superlinear and, besides, a(0) = b(0) = {0}However, since the equality a(R+nm)=R+n may not be satisfied, the relation a(R+nm)=R+nm may not hold. If it is true, then the mappingadefines the Neumann-Gale model [11]. The same is also true for the mappingb.In what follows, we will need description of the mappings conjugate toa andb. Recall that, for the superlinear mapping c: R+n → 2R+k, its conjugate c∗ is defined by the equality(6)c∗g=f∈R+k:f,x≥g,y∀x,y∈cx,g∈R+kThe symbol [x, y] denotes the scalar product of the vectors x and y. Sometimes, instead of the conjugate c∗, it is convenient to use its inverse mapping c′, called the dual mapping [11]:(7)c′f=g∈R+k:g,y≤f,x∀x,y∈cx,f∈R+kThe following statements are valid.Proposition 1 (see [10]).
LetG=(g1,g2,…,gm)∈R+nm.(8)ThenA∗G=F=f1,…,fm∈R+nm:fi∈ai∗gi.Let us introduce the following notations. Let H – (h1,…,hm)∈R+nm and (9)qiH=supi∈Gj⁡cji∗hi;The supremum of the vectors cji∗h is calculated here coordinatewise (∗ is a sign of matrix transposition). Further, let(10)QH=q1H,…,qmH.Proposition 2.
LetH=(h1,...,hm)∈R+nm, then (11)B∗H=QH+R+nm;Inotherwords,B∗H=G=g1,…,gm:gk≥qkH,k=1,2,…,m.Proof.
LetSH(Y)=maxz∈B(Y)⁡[H,Z]. It is well known that the set B(H) coincides with the super differential ∂SH={G:[G,Y]≥SH(Y),Y∈R+nm} of the superlinear functional SH. Let us calculate this functional. First we find the quantity [H,Z], where Z∈B(Y); i.e., Z is representable in the form Z=(z1,z2,…,zm), where zi=∑j∈G-1(i)cjiuji, and the elements uji≥0 are such that ∑j∈G-1(i)uji=yi, j=1,2,…,m.
We have(12)H,Z=∑i=1mhi,zi=∑ihi,∑j∈G-1icjiuji=∑j,i∈Ghi,cjiuji=∑j∑i∈Gjhi,cjiuji=∑j∑i∈Gjcji∗hi,uji.It follows that SH(X)=max⁡H,Z=max∑i∈G(j)uji=yj;uji≥0∑j∑i∈G(j)[cji∗hi,uji].
The maximum here is calculated over independent sets; that is, the elements on which the maximum is attained for some j depend only onyj.Therefore,(13)SHY=∑jmax∑uji=yj;uji≥0⁡∑i∈Gjcji∗hi,uji.
It is known from the theory of semiordered spaces [5] that the maximum under the first sign of sum can be written in the form [qi(H), yj], qi(H) where is the element defined by (9). Thus,(14)SH=∑jqjH,yj=QH,Y,i.e., the functional SH is linear and is determined by the element Q(H). It immediately follows that ∂SH=Q(H)+R+nm. This completes the proof.Remark 1.
Since j∈G(j) and Cjj is an identity operator, we have qi(H)≥hj for all j, and, consequently, Q(H)≥H.Proposition 3.
Letz-∈B(Y-), where(15)Z-=z-1,z-2,…,z-m,Y-=y-1,y-2,…,y-mand the elements u-ji(i,j∈G) are such that (16)y-j=∑i∈Gju-ji,z-=∑j∈G-1icjiu-ji
Further, letG∈B∗(H), where G=(g1,…,gm), H=(h1,…,hm). Then the equality [H,Z-]=[G,Y-] is valid if and only if when (17)qi-cji∗hj,u-ji=0for all (j,i)∈G.Proof.
It follows from (12) that(18)H,Z-=∑j,i∈Gcji∗hj,u-ji.At the same time, (19)G,Y-=∑jqj,y-j=∑j,i∈Gcji∗hj,qj,u-jiBy Proposition 2, each term in the last sum is nonpositive. Therefore, the sum is zero if and only if each term is zero.
The proposition is proved.Proposition 4.
Suppose that under the conditions of Proposition3 all the matrices cji(j,i)∈G coincide with the identity matrix and, in addition, the vector Y is strictly positive. Then G=Q(H)=H.Proof.
From Proposition2 and Remark 1 it follows that G≥Q(H)≥H. On the other hand, since cji is an identity operator, it follows from (17) that(20)gj–hj,yj=gj–hj,∑i=1muji=∑gj–hj,yj=0Strict positivity of the vector yj implies the validity of the equality gj=hj.
The proposition is proved.The results obtained make it possible to describe the characteristics of the effective trajectories in Neumann type models defined by the production mappings of the form (4) and (5). Therefore, these models can be called models of production and exchange on graph.Consider the modelZa defined by the mapping a of the form (4). Let T be a positive integer. As is known [1], Т-step trajectory of the model Za is defined as a finite sequence such that Xt+1∈at(Xt)(t=0,1,…,T-1). Let F=(f1,..., fm) be a price vector. The trajectory X0,X1,...,XТ is called optimal in the sense of F if [F,X]=max⁡[F,X~T] where the maximum is taken over all the trajectories (X~0,…,X~t,…,X~T) starting at the point X0. Under natural conditions, the optimal trajectory in the sense of F admits a characteristic [1]; that is, there exists a sequence(21)F0,F1,…,FT,suchthatFT=FF,X0=…=FT,XT,F,X~0≥…≥FT,X~Tfor every Т-step trajectory (X~0,…,X~T).Consider the trajectory X0, X1,...,XТ. Denote by yti, utji (t=1,…,T; (j,i)∈G) the elements R+n, with the property(22)yti∈atxt-1i,yti=∑j∈G-1iutji,xti=∑j∈G-1icjiutji.Theorem 1.
The sequenceF0,...,FT, where Ft=(fti,…,ftm), is a characteristic of the trajectory X0,...XT if and only if (23)1ft-1i∈ati∗qiFtt=1,2,…,T;i=1,m-;here qi is an operator defined by (9).(24)2qiFt-cji∗fij,utji=0∀j,i∈GProof.
Let (Ft) be a characteristic for the trajectory (Xt). Then for every t=0,1,…,T we have(25)1Ft+1∈a∗Ft;2Ft-1,Xt-1=Ft,XtSincea=В∘A, by the theorem on the conjugate to the composition [1], we have a∗=B∗∘A∗. Therefore, there exists a price vector Gt=(gt1,…,gtm) such that(26)Gt≥QFti.e.qti≥qiFtandft-1i∈ai∗qi
The inequalitygti≥qti(Ft) implies the inclusion ai∗(gi)⊂ai∗(fti). The validity of this simple statement was proved, e.g., in [1]. The validity of relation (23) follows immediately from this statement.
The inclusionsyti∈a(xt-1i), ft-1i∈ai∗(qi(Ft)) imply the inequality [Q(Ft), Yt] ≤ [Ft-1,Xt-1], which, in turn, combined with (25) implies the inequality (27)QFt,Yt≤Ft,Xt.At the same time, the relation Q(Ft)∈B∗(Ft) shows that [Ft,Xt] ≤ [Q(Ft), Yt].
Thus, [Q(Ft), Yt] = [Ft,Xt]. Then, by virtue of Proposition 3, we get the validity of (24). So, if F0, F1,…,FT are the characteristics of the trajectory X0,…,XT then relations (23) and (24) are true. Converse statement can be easily verified.Remark 2.
The statement of Theorem1 remains valid for infinite trajectories, as well as in the case where the production mappings at of the model Za depend on time.Characteristic prices of the effective trajectory can be interpreted as the equilibrium prices in some model of distribution economy.Now recall the definition of fixed income distribution model. This model contains m participants (consumers), withi-th participant defined by his utility function ui and his income λi. It is assumed that the resource vector of the entire economy X is known. This model is denoted as (u, λ, x), where u=(u1,u2,…,um), λ=(λ1, λ2,…, λm).Equilibrium state of the model (u,λ, x) is defined as the set (x1,x2,…,xm,p), where P is a price vector, x1,x2,…,xm is a resource vector with xi≥0,(28)∑xi=xand xi is a solution of the problem (29)uix→maxp,x≤λi⁡subjecttox≥0In the sequel, we will assume that all utility functions ui are first degree positively homogeneous functions. Suppose λi>0. In this case, the vector xi is a solution of problem (29) if and only if it satisfies the equality [p,xi]=λi and in addition is a solution of the problem(30)uixp,x=maxsubject to x ≥ 0.The quantity [p,x] represents the cost of resources at the prices P. Ifui(x) may be interpreted as a cost of production (at some price) and ui(x) – [p,x] may be interpreted as an income, then the problem (30) is reduced to the maximization of the growth rate of profit.Consider problem (30) under the assumption that λi = 0 and this problem has a solution.Then the equality [p,x]=0 impliesui(x)=0 (otherwise the solution does not exist). Assume that 0/0=0. Then every vector x ≥ 0 with [p,x]=0 is a solution of both problem (29) and problem (30). Let us define the nonfixed income distribution model. As above, this model has m participants. However, thei-th participant is characterized only by the utility function ui. This function is assumed to be positively homogeneous of the first degree. Besides, we are given a total resources vector X. Assuming u=(u1,u2,…,um), we denote this model by (u, x).The equilibrium state of the model (u, x) is a set (x1,x2,…,xm,p), where xi is a solution of problem (30) and ∑xi=x.When considering problem (30), we assume 0/0=0; c/0=+∞, for c > 0. Let the set (x1,x2,…,xm,p) be an equilibrium state of the model (u, x) and λi=[p,xi]λ=(λ1, λ2,…, λm).Then this set is an equilibrium state of the model (u,λ, x). On the other hand, the equilibrium state of (u, λ, x) is the equilibrium state of (u, x) for any λ.Back to the above considered mappings A, B. Letb=A∘В. Using the theorem on the mapping conjugate to the composition [1], we obtain b∗=В∗∘A∗. In other words, if F=(f1,f2,…,fm) G=(g1,g2,...,gm) are price vectors and F∈b∗(G), then there exists a price vector H=(h1,h2,…,hm), such that H∈A∗(G), F∈b∗(H). By Proposition 1, hi∈ai∗(gi), i.e., [gi,y]≤[hi,z] for all z and y∈ai(z).The last relation can be rewritten as(31)Viz≤hi,zz≥0,where(32)Viz=maxy∈aiz⁡gi,y.Proposition 5.
Let the vectorsX-=(x-1,x-2,…,x-m), Y-=(y-1,y-2,…,y-m), and Z-=(z-1,z-2,…,z-m) and the price vectors F=(f1,f2,…,fm), H=(h1,h2,…,hm), and G=(g1,g2,…,gm) satisfy Z-∈B(X-), Y-∈A(Z-), H∈A∗(G), F∈B∗(H), and, in addition, [F,X-] = [G,Y-]. Then the vector Z is a solution of the problem(33)Vizhi,z→max,subjecttoZ≥0.Here Vi is a function defined by equality (32), and, as above, it is assumed that 0/0=0.Proof.
Since(34)F∈B∗H,H∈A∗Gwe have(35)F,X-≤H,Z-≤G,Y-.Then it follows from the condition of the proposition that [F,X-] = [H,Z-]=[G,Y-]. Using relations (32) and (33), we get(36)G,Y-≤∑gi,y-i≤∑Vi,Z-i≤∑hi,Z-=H,Z-.As [G,Y-]=[H,Z-], we have Vi(Z-) for all i. Then it follows from (31) that Z- is a solution of problem (33).Remark 3.
It immediately follows from the proof that the value of problem (33) coincides with either zero or unity.
Consider the case where under the conditions of Proposition5 the graph γ = (J, G) is complete, all the matrices Cji(i,j∈J) coincide with the identity matrices, and the vector X is strictly positive. Then, as follows from Proposition 4, Q(H)=H.Leth=sup⁡(H). Since the graph is complete, we have qj(H)=H. Thus, the equality h=qj(H)=hj holds for every j, and therefore problem (33) may be rewritten in the form (37)Vjzh,z→maxsubjecttoZ≥0.It follows that the set (z-1, z-2,…, z-m, h) is an equilibrium state of the model (V,x), where V=(V1,V2,…,Vm), x=∑x-i. The last relation means that there exist the elements uji≥0 such that (38)∑i,juji=x,∑j=1muji=x-i,i=1,2,…,m.We now consider the general situation, that is, the model of distribution economy on the graph (J, G) with the system of matrices Cji, (i,j)∈G. The participant i in this model is defined by the utility function ui(i∈J)={1,2,…,m} and the resource vector xi. Denote the considered model by (U, X), where U=(u1,u2,…,um), X=(x1,x2,…,xm). Proposition 5 suggests the following definition.Definition. By the equilibrium state for the model (U, X) we mean a set (Z, H) with Z=(z1,z2,…,zm), H=(h1,h2,…,hm) where zi is a resource vector, hi is a price vector, Zi is a solution of the problem Ui(Z)/[hi,z]→max subject to Z ≥ 0, and there exist the vectors uji, (j,i)∈G such that(39)∑i∈Gjuji=xi,∑j∈G-1icjiuji=zi.The vector H=(h1,h2,…,hm) is related to the vectors uji by the relations of type (40)qiH-cji∗h,uji=0where qj(H) is a vector defined by (9).Consider the Neumann-Gale modelZb given by the production mapping b = A∘B. Also consider the Neumann type modelm that has B as a production mapping at even moments of time and A as a production mapping at odd moments of time. Let (Xt) be the effective trajectory of the model Zb admitting the characteristics (Ft). Then there exist the resource vectors Zt and the price vectors Ht such that the sequences(41)X0,Z0,X1,Z1,…,Xt,Zt,Xt+1,…F0,H0,F1,H1,…,Ft,Ht,Ft+1,…are the trajectories of the model m and its dual m′, respectively, with the second sequence being a characteristic of the first one. Besides, the sequence Z0,Z1,…,Zt… makes a trajectory of the model Zb, while the sequence H0,H1,…,Ht… forms the characteristics of this trajectory.It follows directly from Proposition4 that the pair (Ht,Zt) represents the equilibrium in a nonfixed income model defined by the resource vector Xt=(xt1,xt2,…,xtm) and utility functions Vt=(Vt1,Vt2,…,Vtm), where Vti is given by the formula (32) for gi=ft+1i. This equilibrium is characterized by the fact that the value of the problem max⁡Vti(z)/[hti,z] coincides with either zero or unity.Suppose that we have a graph (J, G) equipped with a system of matrices (cji) (j,i∈G), each i being associated with the resource vector xi and the utility function Ui. Using the theorem on characteristics, under some conditions it is possible to prove the existence of an equilibrium (Z, H) for the model (U, X) with an additional property that the value of the problem max⁡Ui(z)/[hi,z] coincides for all i with either zero or unity. Let us give the outlines of the proof. Consider some strictly positive vectors(42)G=g1,g2,…,gmandⱲ=ⱳ1,ⱳ2,…,ⱳmwhich satisfy the condition gi,ⱳi=1. Define the mapping ai by letting ai(x)=y:0≤y≤Uxⱳi. Let Vi be a function given by (32). Then, by definition, U(x)=Vi(x) for all х ≥ 0.Suppose that the vectorsxi are strictly positive and consider one-step trajectory of the model Zb starting at the point X and maximizing the price vector G on the set Zb(X), where, as above, b = A∘B, the mapping B is defined in (1) by the graph (J, G) and the matrices cji, and the mapping A is defined in (4) by the mapping ai. Let this trajectory have the form (X, Y). Then there exists a vector Z such that Z∈B (X), Y∈A (Z). By the well-known theorems [1], there exists a price vector F such that the pair (F,G) is a characteristic of the trajectory (X, Y). There exists a vector H such that F∈B∗(H), H∈A∗(G)(43)F,X=H,Z=G,Y.It is clear that the pair [Z,H] is the sought one.


## 2. Conclusions

The results obtained in this work allow applying well-known facts about graph theory to some models of production and exchange. A description of the characteristics of the effective trajectories of the Neumann type models is given. It is shown that the characteristic prices can be considered as equilibrium prices in some distribution models. Besides, the resource vector of considered problem is a solution of some extremal problem. The existence of equilibrium is proved under some conditions.



---

*Source: 7974381-2019-06-02.xml*