# A Distributed Algorithm for Large-Scale Linearly Coupled Resource Allocation Problems with Selfish Agents

Authors: Dian Yu; Tongyao Wang
Journal: Scientific Programming
 (2021)

---

## Abstract

A decentralized randomized coordinate descent method is proposed to solve a large-scale linearly constrained, separable resource optimization problem with selfish agent. This method has a cheap computational cost and can guarantee an improvement of selected objective function without jeopardizing the others in each iteration. The convergence rate is obtained using an alternative gap benchmark of objective value. Numerical simulations suggest that the algorithm will converge to a random point on the Pareto front.


---

## Body

## 1. Introduction and Motivation

Distributed and parallel optimization techniques have become a powerful tool in solving large-scale resource optimization problems [1–4]. Different from the consensus-based distributed optimization model ([2, 5]), where all agents collectively share the same decision variables, the resource optimization problem usually has a separable structure, i.e., each agent has its own decision variable and own objective function, but all the agents are weakly coupled by equality or inequality constraints [6]. The overall target is to minimize the summation of the agents’ objective functions. One typical example of this kind of model is the optimal coordination problem of the distributed energy resources [4, 5], in which each generator decides the power generation by minimizing the cost function and meeting the overall demand. Recently, Li et al. [6] extended such method to the model of a global inequality constraint.This work is motivated by the observation that resource allocation problems in the digital age are often subject to some new limitations unseen in traditional resource allocation problems. For example, in the area of content distribution or video streaming, many researchers have explored a scheme called parallel access [7] or multiple content distribution servers [8, 9] in a bid to optimize servers’ work load and enhance users’ quality of experience (QoE). Similar problems can also arise in the so-called multihoming problem when users start to compete for resources [10, 11]. This scheme first divides the original content/video into fragments, the replicas of these fragments are stored in a number of servers (often geographically diverse), and then the users are allowed to access/download fragments from multiple servers concurrently. This scheme is characterized by the following features:(i)
Large scale: the number of users could easily hit hundreds of thousands or even millions.(ii)
Bandwidth limit: each server has a total bandwidth limit, so that each user is only given a quota of the total bandwidth.However, there are some practical concerns about this scheme. Specifically, user utilization of bandwidth quota of different servers may vary due to the physical distance or the access quality of different Internet service providers. In this sense, there is a need to reallocate bandwidth quotas of the servers among users to improve user QoE. Unfortunately, there are three major difficulties underlying this optimization problem:(1)
The information necessary (gradients of objective functions, etc.) for the quota optimization is scattered among users and may be only partially available at a given time (e.g., users are inactive or unresponsive).(2)
Even if all the information is readily available, considering the large scale of the problem, an overall one-shot optimization could be computationally prohibitive and may lack timeliness, which is especially crucial for the enhancement of video viewing experience.(3)
Considering (2), a distributed algorithm that adaptively and progressively optimizes quota allocation among users should be preferred; however, here the crux is that the users in no way can accept a deteriorating QoE during the optimizing process, i.e., the users (agents) are selfish: one would not be too happy when he knows his own QoE is compromised for the QoE of someone else or for the “greater good” of the overall system.The goal of this paper is to develop an efficient distributed method for solving resource allocation problem with selfish agents. Since the complete information of first and second order information necessary for a one-shot optimization is usually not available in many real world large-scale applications, we develop a randomized coordinate descent (RCD) algorithm that partially updates a pair of objective functions in each iteration (the RCD algorithm coincides with the distributed network optimization model, where only a subset of nodes can communicate with each other and can be optimized in one iteration). Our algorithm can be vaguely viewed as a multiobjective (MO) extension of the single-objective randomized coordinate descent algorithm [12]. Different from the single-objective optimization problem, the MO problem aims to optimize multiple objectives simultaneously in the sense of Pareto optimality (see [13, 14]).Our RCD method has the following prominent features: first, it optimizes the selected objective functions in each iteration without affecting other objective functions, and the optimization at each iteration is required to be such that none of the selected objective functions should deteriorate. As a result, the value of each objective function should be non-deteriorating over the whole optimizing process, and the solution of each iteration can be applied in real time to progressively improve the objective function of each agent. Second, compared to the centralized MO methods such as [15, 16], our algorithm takes full advantage of the separability of the problem structure, and the update has a very cheap cost per iterate and can be easily implemented in a parallel setting. Perhaps more significantly, this work also focuses on the convergence analysis of the multiobjective RCD algorithm. Although the convergence results of single-objective algorithms are well established ([17, 18]), similar discussions for its MO counterparts are unexpectedly scarce. It was not until very recently that a few works have succeeded in obtaining the convergence rates for certain unconstrained MO algorithms ([19–21]). In fact, as will be evident in our analysis, the limiting point generated by our RCD algorithm will converge to a random point on the Pareto front; as a result, all the tools used in single-objective algorithm analysis are generally rendered useless. To conquer this difficulty and complete the missing piece, we develop a framework of convergence analysis for the RCD method, which generalizes the existing analysis for scalar optimization problem [12]. Under a mild condition, we show that the RCD algorithm has a sublinear convergence rate. If agents’ cost functions are all strongly convex, then the RCD algorithm has a linear convergence rate.The paper is organized as follows. In Section2, we present the constrained MO optimization problem. In Section 3, we present the RCD algorithm. An analysis of the convergence rate of this RCD algorithm for different cases is given in Section 4. Some numerical examples are given in Section 5. We conclude the paper and discuss the future research in Section 6. Throughout this paper, the following notations are used. The vector is denoted by the bold letter. We use the following notation to denote the order of the vectors. Given u=u1…unT and v=v1…vnT, u≺v means that ui≤vi, for all i=1,…,n and u≺v means that ui<vi, for i=1,…,n.


## 2. Problem Formulation

Consider the following standard multiobjective (MO) optimization problem with linear equality constraints:(1)Pmo:minFX≡f1x1…fMxMTs.tX∈C≔X∈ℝkM|∑m=1Mxm=0,where X=x1⋮xM∈ℝkM with xm∈ℝk and fm:ℝk⟶ℝ is a continuous function satisfying certain conditions for j∈M≔1,2,…,M (notation 0 denotes the vector with all elements being zero). Clearly, function F·:ℝkM:⟶ℝM is separable, i.e., xm only affects fmxm. However, these decision variables are weakly coupled by the global equality constraint. Note that although the right-hand side of the equality constraint is 0, there is no difficulty to generalize the results to the non-zero case using some affine transformation. In the context of the above bandwidth allocation problem, here xm can be viewed as the bandwidth quotas of k servers allocated to agent m; fm is a function that represents the negative of the utility (QoE) brought by quotas xm; and the equality constraint represents the total bandwidth limitation of each server 1,…,k. Model Pmo arises in various network optimization problems (see, e.g., [22–27]).ProblemPmo aims to optimize the multiple objectives simultaneously in the sense of Pareto optimality (see [13, 14]). Indeed, a feasible point X∗∈C is a Pareto optimal solution of problem Pmo if there exists no other feasible solution such that FX′≺¯FX∗ and FX′≠FX∗. The traditional way to solve Pmo is to aggregate objective functions fm into a weighted summation social welfare, say, ∑mωmfmxm with ωm>0,∀m=1,…,M; then, solve the following single-objective optimization problem using classical methods (e.g., gradient descent method, Newton method, etc.):(2)min∑mωmfmxms.tX∈C≔X∈ℝkM|∑m=1Mxm=0.But this scheme suffers two major drawbacks for the reasons we stated previously: first, the large scale of the underlying problem (a very largeM) may prevent this scheme from responding in a timely manner; second, this scheme does not guarantee a progressively non-deteriorating allocation evolution during the optimizing process, so that it is possible that the individual welfares of some agents get sacrificed for the “greater good,” i.e., the maximization of social welfare ∑mωmfmxm, and hence they could become discontent and discard the service for good. Therefore, to address these issues, we present the following randomized block coordinate descent method.


## 3. Randomized Block Coordinate Descent Method

### 3.1. The RCD Algorithm

Throughout this paper, we assume that the following condition holds true.Assumption 1.
Eachfm· has Lipschitz continuous gradient with constant L>0, i.e., for all xm,ym∈ℝk,m∈M, it has(3)∇fmxm−∇fmym≤Lxm−ym,where · is the Euclidean norm (note that here the Lipschitz coefficient can be agent-specific, e.g., L1,…,LM; in this case, we can let L=maxL1,…,LM; on the other hand, one can also modify our algorithm scheme accordingly with respect to these agent-specific Lipschitz coefficients and obtain an improved convergence rate).
Note that the Lipschitz property implies the following inequality:(4)fmxm+d≤fmxm+∇fmxmTd+L2d2,for any d∈ℝk and m∈M. Given the current solution X, the classical gradient-based method needs to compute the whole Jacobian to generate a feasible step that simultaneously decreases all objectives. Obviously, this step is expensive when the problem size is large. To conquer this difficulty, we propose the following RCD method. In each iteration, we randomly select two objectives pair i,j with probability pi,j to update their objective values for i,j∈M. To ensure convergence of the algorithm, we need the following condition on the sampling probability, pi,ji,j=1M.Assumption 2.
For anypi,j, there exists i1,i2,…,ik∈M such that sampling probabilities pi,i1,pi1,i2,…,pik,j are all strictly positive.
Graphically, one can think of a strictly positivepi,j>0 as an “edge” between node i and j, and if pi,j=0, it means that there is no edge between node i and j. Assumption 2 means that the communication network among the nodes is connected, i.e., any two nodes in the network are either directly connected by an edge or indirectly connected by at least one path formed by several intermediate edges. If the network is complete, i.e., each node is directly connected to every other node, pi,j>0 for all edges, the above condition is automatically satisfied. Some other options are available, for example, the cyclic network (see Figure 1). In a cyclic network, each node is connected in a circular fashion: Node1⟶Node2⟶Node3⟶Node4⟶Node1…. Another one is the so-called central coordinator network, in which one node is chosen as a central coordinator (see Figure 2), and the rest of the nodes are connected to this central coordinator while do not share direct connections among themselves. The implication of a connected network is that any local change can eventually ripple through the whole network instead of being contained.
Once a pairi,j is chosen, the following problem for the convex optimization problem is solved:(5)Pi,jX:mindi,j,ti,jti,js.t.∇fixiTdi,j+L2di,j2≤ti,j,(6)−∇fjxjTdi,j+L2di,j2≤ti,j.
It is not hard to see that due to inequality (4), the solution of problem Pi,jX provides a descent direction to improve the objective values for both i and j. The key difference between Pi,j and its single-objective RCD counterpart is that a single-objective RCD algorithm will aggregate (5) and (6) and attempt to minimize such aggregate cost. Unlike our multiobjective method, this single-objective scheme does not necessarily generate non-deteriorating solution for both agents. We use di,j∗ to denote the optimal solution of problem Pi,jX and use xi+ and xj+ to denote the updated solution points for the i-th and j-th objective functions, respectively. Let X+=x1+⋮xM+ be the updated solution vector. The RCD algorithm updates the solution points as follows: xi+=xi+di,j∗, xj+=xj−di,j∗, and keeps all the others unchanged xm+=xm, for m≠i,j and m∈M. One prominent feature of the method is that problem Pi,jX admits explicit solution.Figure 1
A cyclic network where each node is connected in a circular fashion.Figure 2
A central coordinator network where nodes do not have direct connections but are connected indirectly by a central node.Lemma 1.
GivenX and pair i,j, the optimal solution of Pi,jX is(7)di,j∗=−1Lλi,j∗∇fixi−1−λi,j∗∇fjxj,where(8)λi,j∗=max0,min1,∇fjxjT∇fixi+∇fjxj∇fixi+∇fjxj2.Furthermore,X∗ is Pareto optimal only if the optimal solution of Pi,jX∗ is di,j∗=0 for all pairs i,j, and the reverse direction holds true if all fm are convex.Proof.
Checking the Karush–Kuhn–Tucker (KKT) condition of problemPi,jx yields(9)di,j∗=−1Lλi,j∇fixi−1−λi,j∇fjxj,where λi,j∈0,1 is the Lagrange multiplier. Substituting di,j∗ back into the constraints gives ti,j∗ as(10)ti,j∗=minλi,j∈0,11Lmaxgiλi,j;∇fixi,∇fjxj,gjλi,j;∇fixi,∇fjxj,where(11)gik;a1,a2=12k2a1+a22−ka1+a22+a1Ta2+12a22gjk;a1,a2=12k2a1+a22−12a22.
It can be easily verified thatgik;a1,a2 is strictly decreasing for k∈0,1 and gjk;a1,a2 is strictly increasing for k∈0,1; after checking the boundary values, we obtain λi,j∗ as in (10). Clearly, when each fm is convex and di,j∗=0, it implies the Pareto optimality, i.e., λi,j∗∇fixi=1−λi,j∗∇fjxj,λi,j∗∈0,1 for any pair i,j, which satisfies the KKT condition of Pmo. The other direction is straightforward.
The algorithm is summarized in the following pseudo-code.
A distributed algorithm for large-scale linearly-coupled resource allocation problems with selfish agents. Algorithm1
SincePmo is assumed to be a large-scale problem, the computational cost of methods [15, 16] could become intimidating because an overall optimization that involves all objectives is required to compute an update direction. Also, the methods of [15, 16] would require all the objective function information to be transmitted to a central coordinating agent, where the optimization is conducted. But this could create excessive communication overheads in the central coordinating agent. In contrast, our method is able to take advantage of the separability of the problem structure, and the update has an analytical form and can be parallelized by optimizing multiple pairs concurrently; moreover, the pairwise optimization can be easily implemented in a peer-to-peer manner. The cost per iteration is Ocf+c, where cf is the maximum cost of computing the gradient of each fi, and c is the cost of updating xi. When compared with the single-objective randomized coordinate descent method, the main difference is that the optimization procedure guarantees that ti,j≤0 for any pair; as a result, the update is always non-deteriorating for each of the agents and hence can be applied in real time.Algorithm 1: Multiobjective adaptation.
Initialization: setX=X0;while True doRandomly select a matching pairi,j according to some network structureSolvedi,jast from problem:Pi,jX:mindi,j,ti,jti,js.t.∇fixiTdi,j+L/2di,j2≤ti,j−∇fjxjTdi,j+L/2di,j2≤ti,jUpdate:xi=xi+di,j∗,xj=xj−di,j∗.Remark 1.
When all information is available, one may also consider to follow the idea of [15], that is, to simultaneously optimize all agents, the update directions are given by solving the following problem:(12)PallX:mind1,…,dM,tts.t.∇f1x1Td1+L2d12≤t,⋮∇fMxMTdM+L2dM2≤t,∑i=0Mdi=0.
However, the cost per iteration of this problem will beOMcf+Mc. Also note that Pall generally does not have an analytical solution form; therefore, an additional algorithm for quadratic programming is needed to find its solution.


## 3.1. The RCD Algorithm

Throughout this paper, we assume that the following condition holds true.Assumption 1.
Eachfm· has Lipschitz continuous gradient with constant L>0, i.e., for all xm,ym∈ℝk,m∈M, it has(3)∇fmxm−∇fmym≤Lxm−ym,where · is the Euclidean norm (note that here the Lipschitz coefficient can be agent-specific, e.g., L1,…,LM; in this case, we can let L=maxL1,…,LM; on the other hand, one can also modify our algorithm scheme accordingly with respect to these agent-specific Lipschitz coefficients and obtain an improved convergence rate).
Note that the Lipschitz property implies the following inequality:(4)fmxm+d≤fmxm+∇fmxmTd+L2d2,for any d∈ℝk and m∈M. Given the current solution X, the classical gradient-based method needs to compute the whole Jacobian to generate a feasible step that simultaneously decreases all objectives. Obviously, this step is expensive when the problem size is large. To conquer this difficulty, we propose the following RCD method. In each iteration, we randomly select two objectives pair i,j with probability pi,j to update their objective values for i,j∈M. To ensure convergence of the algorithm, we need the following condition on the sampling probability, pi,ji,j=1M.Assumption 2.
For anypi,j, there exists i1,i2,…,ik∈M such that sampling probabilities pi,i1,pi1,i2,…,pik,j are all strictly positive.
Graphically, one can think of a strictly positivepi,j>0 as an “edge” between node i and j, and if pi,j=0, it means that there is no edge between node i and j. Assumption 2 means that the communication network among the nodes is connected, i.e., any two nodes in the network are either directly connected by an edge or indirectly connected by at least one path formed by several intermediate edges. If the network is complete, i.e., each node is directly connected to every other node, pi,j>0 for all edges, the above condition is automatically satisfied. Some other options are available, for example, the cyclic network (see Figure 1). In a cyclic network, each node is connected in a circular fashion: Node1⟶Node2⟶Node3⟶Node4⟶Node1…. Another one is the so-called central coordinator network, in which one node is chosen as a central coordinator (see Figure 2), and the rest of the nodes are connected to this central coordinator while do not share direct connections among themselves. The implication of a connected network is that any local change can eventually ripple through the whole network instead of being contained.
Once a pairi,j is chosen, the following problem for the convex optimization problem is solved:(5)Pi,jX:mindi,j,ti,jti,js.t.∇fixiTdi,j+L2di,j2≤ti,j,(6)−∇fjxjTdi,j+L2di,j2≤ti,j.
It is not hard to see that due to inequality (4), the solution of problem Pi,jX provides a descent direction to improve the objective values for both i and j. The key difference between Pi,j and its single-objective RCD counterpart is that a single-objective RCD algorithm will aggregate (5) and (6) and attempt to minimize such aggregate cost. Unlike our multiobjective method, this single-objective scheme does not necessarily generate non-deteriorating solution for both agents. We use di,j∗ to denote the optimal solution of problem Pi,jX and use xi+ and xj+ to denote the updated solution points for the i-th and j-th objective functions, respectively. Let X+=x1+⋮xM+ be the updated solution vector. The RCD algorithm updates the solution points as follows: xi+=xi+di,j∗, xj+=xj−di,j∗, and keeps all the others unchanged xm+=xm, for m≠i,j and m∈M. One prominent feature of the method is that problem Pi,jX admits explicit solution.Figure 1
A cyclic network where each node is connected in a circular fashion.Figure 2
A central coordinator network where nodes do not have direct connections but are connected indirectly by a central node.Lemma 1.
GivenX and pair i,j, the optimal solution of Pi,jX is(7)di,j∗=−1Lλi,j∗∇fixi−1−λi,j∗∇fjxj,where(8)λi,j∗=max0,min1,∇fjxjT∇fixi+∇fjxj∇fixi+∇fjxj2.Furthermore,X∗ is Pareto optimal only if the optimal solution of Pi,jX∗ is di,j∗=0 for all pairs i,j, and the reverse direction holds true if all fm are convex.Proof.
Checking the Karush–Kuhn–Tucker (KKT) condition of problemPi,jx yields(9)di,j∗=−1Lλi,j∇fixi−1−λi,j∇fjxj,where λi,j∈0,1 is the Lagrange multiplier. Substituting di,j∗ back into the constraints gives ti,j∗ as(10)ti,j∗=minλi,j∈0,11Lmaxgiλi,j;∇fixi,∇fjxj,gjλi,j;∇fixi,∇fjxj,where(11)gik;a1,a2=12k2a1+a22−ka1+a22+a1Ta2+12a22gjk;a1,a2=12k2a1+a22−12a22.
It can be easily verified thatgik;a1,a2 is strictly decreasing for k∈0,1 and gjk;a1,a2 is strictly increasing for k∈0,1; after checking the boundary values, we obtain λi,j∗ as in (10). Clearly, when each fm is convex and di,j∗=0, it implies the Pareto optimality, i.e., λi,j∗∇fixi=1−λi,j∗∇fjxj,λi,j∗∈0,1 for any pair i,j, which satisfies the KKT condition of Pmo. The other direction is straightforward.
The algorithm is summarized in the following pseudo-code.
A distributed algorithm for large-scale linearly-coupled resource allocation problems with selfish agents. Algorithm1
SincePmo is assumed to be a large-scale problem, the computational cost of methods [15, 16] could become intimidating because an overall optimization that involves all objectives is required to compute an update direction. Also, the methods of [15, 16] would require all the objective function information to be transmitted to a central coordinating agent, where the optimization is conducted. But this could create excessive communication overheads in the central coordinating agent. In contrast, our method is able to take advantage of the separability of the problem structure, and the update has an analytical form and can be parallelized by optimizing multiple pairs concurrently; moreover, the pairwise optimization can be easily implemented in a peer-to-peer manner. The cost per iteration is Ocf+c, where cf is the maximum cost of computing the gradient of each fi, and c is the cost of updating xi. When compared with the single-objective randomized coordinate descent method, the main difference is that the optimization procedure guarantees that ti,j≤0 for any pair; as a result, the update is always non-deteriorating for each of the agents and hence can be applied in real time.Algorithm 1: Multiobjective adaptation.
Initialization: setX=X0;while True doRandomly select a matching pairi,j according to some network structureSolvedi,jast from problem:Pi,jX:mindi,j,ti,jti,js.t.∇fixiTdi,j+L/2di,j2≤ti,j−∇fjxjTdi,j+L/2di,j2≤ti,jUpdate:xi=xi+di,j∗,xj=xj−di,j∗.Remark 1.
When all information is available, one may also consider to follow the idea of [15], that is, to simultaneously optimize all agents, the update directions are given by solving the following problem:(12)PallX:mind1,…,dM,tts.t.∇f1x1Td1+L2d12≤t,⋮∇fMxMTdM+L2dM2≤t,∑i=0Mdi=0.
However, the cost per iteration of this problem will beOMcf+Mc. Also note that Pall generally does not have an analytical solution form; therefore, an additional algorithm for quadratic programming is needed to find its solution.


## 4. Convergence Rate Analysis

### 4.1. Convergence Rate Analysis: Non-convex Case

We investigate the convergence rate of the RCD algorithm in this section. We first introduce the potential functionh:ℝkM⟶ℝ as hX=∑m=1Mfmxm. For the optimal updating vector di,j∗ and the associated Lagrange multiplier λi,j∗, the Lipschitz continuity of fm implies(13)fixi+di,j∗+fjxj−di,j∗≤fixi+fjxj+∇fixiTdi,j∗+L2di,j∗2−∇fjxjTdi,j∗+L2di,j∗2≤fixi+fjxj+λi,jast∇fixiTdi,j∗+L2di,j∗2+1−λi,jast−∇fjxjTdi,j∗+L2di,j∗2≤fixi+fjxj−12Lλi,j∗∇fixi−1−λi,j∗∇fjxj2,where the second inequality follows from the observation that ti,j∗≤0. Therefore, under the preceding updating rule, we can estimate the expected decrease of potential function as(14)hX−EhX+|X=∑i,jpi,jfixi+fjxj−fixi+di,j∗+fjxj−di,j∗≥12L∑i,jpi,jλi,j∗∇fixi−1−λi,j∗∇fjxj2.Now, we introduce the following criteria as a metric,D·:ℝkM⟶ℝ, as(15)Da≔12L∑i,jpi,jλi,jaai−1−λi,jaaj21/2,with λi,jamax0,min1,ajTai+aj/ai+aj2 for some a=a1T…aMTT∈ℝkM, am∈ℝk,∀m. Using D·, the preceding inequality (10) becomes(16)hX−EhX+|X≥D∇hX2.One can viewD· as an improvement potential indicator. Specifically, we have the following lemma.Lemma 2.
D∇hX∗=0 only if X∗ is a Pareto optimal solution of Pmo, and the reverse direction holds true if each fm is convex.Proof.
We first prove one direction thatD∇hX∗=0 implies X∗ is a Pareto optimal solution by contraposition. Assume that X with ∑i=mMxm=0 is not Pareto optimal; then, there exist i and j≠i such that ∇fixi≠t·∇fjxj, ∀t∈ℝ+, which implies D∇hX>0. The other direction in this lemma is straightforward. We omit the detail.
We now turn to investigate the convergence rate of the RCD algorithm. Convergence rate of methods for single-objective problem such asminx∈Cfx is usually measured with respect to the gap from its optimal value f∗. However, different from the single objective-based optimization problem, the generated sequence of the MO algorithm may converge to different points in the Pareto optimal frontier, and there is no a priori way to determine which point the sequence converges to; this property will be further substantiated by the numerical simulations. Therefore, one needs to construct an alternative benchmark that measures the convergence rate (the construction of such alternative gap function for multiobjective optimization problems is also discussed by Dutta et al. and Tanabe et al. [28–30] recently). We define the following two measures (functions):(17)h†X=minFY≼¯FX,Y∈ChY,v†X=maxFY≼¯FX,Y∈ChX−hY=hX−h†X,where h†X provides a lower bound of the potential function hX and v†X measures the gap between the current value of potential function and such a lower bound. These two measures have the following properties.Lemma 3.
For anyX1,X2∈C, if FX2≺¯FX1, it has h†X2≥h†X1 and v†X2≤v†X1. Furthermore, the solution X∗ is a Pareto optimal point only if v†X∗=0, and the reverse direction holds true if each fm is convex.Proof.
The first half follows directly from the observation thatFX2≺¯FX1 implies Y∈C:FY≺¯FX2⊆Y∈C:FY≺¯FX1. The rest of the proof is straightforward, and we omit the details.
Althoughh†,v† are only tangential to the following convergence result for non-convex objective functions, they are pivotal to obtain convergence rate for convex and strongly convex objective functions. Then, we have the following preliminary convergence rate result for generally non-convex objective functions given as follows.Theorem 1.
If level setℒ≔X∈C:FX≺¯FX0 is bounded, then the following holds:(18)mink=1,…,nED∇hXk|X0≤hX0−h†X0n.Proof.
Taking expectation of both sides of (17) with respect to X0 and summing up to n, we arrive at the following:(19)n·mink=1,…,nED∇hXk|X02≤∑kE2D∇hXk|X0≤∑kED2∇hXk|X0≤hX0−EhX1|X0+EhX1|X0−EhX2|X0+⋯+EhXn−1|X0−EhX1|X0=hX0−EhX1|X0≤hX0−h†X0,where the second inequality follows from Jensen’s Inequality. Since ℒ is bounded, we know that hX0−h†X0 is also bounded, and hence (18) follows.
Note that in the non-convex case, the stationary point could only be a local minimum.


### 4.2. Convergence Rate: Convex Case

When eachfm is convex, an accelerated convergence rate can be obtained. But first we need some preliminary results. In the same spirit of the dual norm, for a non-empty compact set ℬ⊂ℝkM, we define the dual function of D· on ℬ as(20)Dℬ∗d=maxY∈AℬdYTd,where Aℬd=Y=y1T…yMTT∈ℬ:0≤DY≤1,ymTdm≥0,∀m∈M. Then, the following lemma gives the counterpart of Cauchy–Schwarz inequality with respect to the feasible set C of problem pmo.Lemma 4.
Givend∈C and a non-empty compact set ℬ⊂ℝkM, for all Y∈ℬ∩Y=y1T…yMTT∈ℝkM|ymTdm≥0,∀m∈M, the following inequality holds true:(21)YTd≤DY·Dℬ∗d.Furthermore, there exists a numberΓℬ≤0 such that Dℬ∗d≤Γℬd for all d∈C.Proof.
SinceAℬd is a compact set, then Dℬ∗· is well defined. Depending on the value of DY, we have two cases as follows:(1)
IfDY=0, from (17), we know Y must be in form of Y=t1g⋮tMg for some g∈ℝk and t1,…,tM∈ℝ+. Suppose there exists a d∈C such that YTd>0, which implies gTdm>0 for some m. However, this leads to ∑m=1MgTdm=gT∑m=1Mdm>0, which is a contradiction to the fact that d∈C. Therefore, DY=0 implies YTd=0 for all d∈C such that ymTdm≥0, ∀m∈M.(2)
IfDY>0, let A˜ℬd=Y∈ℬ|0<DY≤1,ymTdm≥0,∀m∈M. Clearly, it has A˜ℬd⊆Aℬd. Then, inequality (21) follows from(22)YTd=YTd·DYDY≤DY·supY∈A˜ℬdYTd≤DY·maxY∈AℬdYTd=DY·Dℬ∗d,where the second equality follows from the fact that λi,jkY=λi,jY, ∀k∈ℝ, and hence it has DkY=kDY.
As for the last part of the lemma, we can compute the lower bound valueΓℬ as(23)Γℬ=supd>0Dℬ∗dd≤maxd:d≤1Dℬ∗d=maxd:d≤1maxa∈AℬdaTd,where Aℬ=Y,d|Y∈Aℬd,d∈C,d≤1 is a compact set.Theorem 2.
Given an initial solutionX0, if the level set ℒ≔X∈C|FX≺¯FX0 is bounded, then the solution Xn generated by the n-th iteration of RCD algorithm satisfies(24)Ev†Xn|X0≤Γℬ2RX02n,where RX0≔maxY∈ℒX0−Y and Γℬ is defined with respect to Dℬ∗ in Lemma 4 with ℬ≔∇hX:X∈ℒ. Furthermore, Γℬ is bounded by(25)Γℬ≤∇hX0+L·maxZ∈ℒ∑m=1Mxm0−zm≤∇hX0+LM·RX0.Proof.
As the level setℒ is bounded, problem pmo always admits solution. On the other hand, the Lipschitz property in Assumption 1 implies(26)∇hX−∇hZ≤∑m=1M∇fmxm−∇fmzm≤L∑m=1Mxm−zm,which further implies the boundedness of the set ℬ. Therefore, Γℬ satisfies the following inequality:(27)Γℬ=maxY,d∈AℬYTd≤maxY,d∈AℬY·d≤maxY∈ℬY≤∇hX0+maxZ∈ℒ∇hX0−∇hZ.
Then, it has(28)0≤v†Xn=maxFY≼¯FXn,Y∈ChXn−hY≤maxFY≼¯FXn,Y∈C∇hXnTXn−Y≤maxFY≼¯FXn,Y∈CD∇hXn·DℬastXn−Y=D∇hXn·maxFY≼¯FXn,Y∈CDℬastXn−Y≤D∇hXn·Γℬ·RX0,,where the second inequality is from the convexity of h·, and the third inequality is from (24). Inequality (28) together with (17) gives(29)hXn−EhXn+1|Xn≥v†Xn2Γℬ2RX02⟹EhXn+1−h†Xn|Xn≤v†Xn−v†Xn2Γℬ2RX02.
Since it hasFXn+1≺¯FXn, applying Lemma 3 to the preceding inequality gives(30)Ev†Xn+1|Xn≤EhXn+1−h†Xn|Xn≤v†Xn−v†Xn2Γℬ2RX02.
Taking expectation of both sides of the above inequality and applying Jensen’s inequality,Ev†Xn2|X0geEv†Xn|X02, it has(31)Δn+1≤Δn−Δn2Γℬ2RX02,where Deltan=Ev†Xn|X0. Since Δn+1≤Δn, it has(32)1Δn≤1Δn+1−ΔnΔn+1·1Γℬ2RX02⟹1Γℬ2Rx02≤1Δn+1−1Δn⟹Δn≤Γℬ2RX02n.


### 4.3. Convergence Rate: Strongly Convex Case

In this section, we investigate the convergence rate when functionfm· is σ-strongly convex for all m∈M.Assumption 3.
There exists aσ>0 such that(33)fmym≥fmxm+∇fmxmTym−xm+σ2ym−xm2,for all xm,ym∈ℝk.
Summing upfm leads to the strong convexity of the Lyapunov function, i.e.,(34)hY≥hX+∇hXTY−X+σ2Y−X2,∀Y,X∈ℝkM.Theorem 3.
Given an initial feasible solutionX0, if level set ℒ≔X∈C:FX≺¯FX0 is bounded, then the RCD algorithm satisfies(35)Ev†Xn|X0≤1−2σΓℬn·v†X0,where Γℬ is defined in Lemma 4 with respect to the set ℬ=∇hX:X∈ℒ.Proof.
Applying Lemma4 to (34), it has(36)hY≥hY+∇hYTY−X+σ2Y−X2⇒hY≥hX+∇hXTY−X+σ2ΓℬDℬ∗Y−X2⇒∇hXTX−Y−σ2ΓℬDℬ∗X−Y2≥hX−hY.
Let(37)CLX=Y∈C|∇fmxmTxm−ym≥0,∀m∈M,CRX=Y∈C|FY≺¯FX..
Then, one can easily verify thatCRX⊆CLX by using the convexity of fm. Maximizing the left-hand side of (36) with respect to CLX and the right-hand side with respect to CRX yields(38)Γℬ2σD∇hX2=maxt∈ℝD∇fXt−σ2Γℬt2≥maxY∈CLXD∇fx·Dℬ∗X−Yσ2ΓℬDℬ∗X−Y2≥maxY∈CLX∇hXTX−Y−σ2ΓℬDℬ∗X−Y2≥maxY∈CRX∇hXTX−Y−σ2ΓℬDℬ∗X−Y2≥maxY∈CRXhX−hY=v†X,where the second inequality follows from Lemma 4. Letting X=Xn, combining D∇fXn2≥2σ/Γℬv†Xn with (17) yields(39)hXn−EhXn+1|Xn≥2σΓℬv†Xn⇒Ev†Xn+1|Xn≤1−2σΓℬv†Xn.
Taking expectation of both sides and applying the resulting inequality iteratively leads to (35).


### 4.4. Convergence Rate in Probability

Again with the aid of gap benchmarkv†, in this section, we are able to establish the convergence rate in probability for the RCD algorithm. First we introduce the following lemma [31].Lemma 5 (see [31]).
Letxi0>0 be a constant, consider a 0<ϵ<xi0, and let xinn be a non-negative, non-increasing sequence of random variables with one of the following properties:(1)
Eξn+1|ξn≤ξn−ξn2/c for all n>0 and r>ϵ.(2)
Eξn+1|ξn≤1−1/cξn for all n such that ξn≥ϵ and c>1 is a constant.Then, given confidence levelρ∈0,1, if property (1) holds, we can choose ϵ<c and(40)N≥cϵ1+log1ρ+2−cξ0.If property (2) holds, we choose(41)N≥clogξ0ερ.Then, we have(42)ℙξN≤ε≥1−ρ.Proof (see [31], Theorem 1).
This proof is done by applying Markov inequality.
Then, we have the following theorem that quantifies the confidence of reducing the improvement of potential function to no more thanϵ.Theorem 4.
Ifℒ=X∈C:FX≺¯FX0 is bounded and each fm is convex, let ℬ=∇hX:X∈ℒ; then, we can choose(43)N≥Γℬ2R2X0ε1+log1ρ−Γℬ2R2X0v†X0+2,where Γℬ is the corresponding bounding coefficient with respect to ℬ; if each fm is σ-strongly convex, then we may choose(44)N≥Γℬ2σlogv†X0ερ.Under either way, it has(45)ℙv†XN≤ε≥1−ρ.Proof.
This result follows directly from the observation that the gap sequence generated by RCD:v†Xn, satisfies the properties mentioned in Lemma 5, according to (32) and (39).


## 4.1. Convergence Rate Analysis: Non-convex Case

We investigate the convergence rate of the RCD algorithm in this section. We first introduce the potential functionh:ℝkM⟶ℝ as hX=∑m=1Mfmxm. For the optimal updating vector di,j∗ and the associated Lagrange multiplier λi,j∗, the Lipschitz continuity of fm implies(13)fixi+di,j∗+fjxj−di,j∗≤fixi+fjxj+∇fixiTdi,j∗+L2di,j∗2−∇fjxjTdi,j∗+L2di,j∗2≤fixi+fjxj+λi,jast∇fixiTdi,j∗+L2di,j∗2+1−λi,jast−∇fjxjTdi,j∗+L2di,j∗2≤fixi+fjxj−12Lλi,j∗∇fixi−1−λi,j∗∇fjxj2,where the second inequality follows from the observation that ti,j∗≤0. Therefore, under the preceding updating rule, we can estimate the expected decrease of potential function as(14)hX−EhX+|X=∑i,jpi,jfixi+fjxj−fixi+di,j∗+fjxj−di,j∗≥12L∑i,jpi,jλi,j∗∇fixi−1−λi,j∗∇fjxj2.Now, we introduce the following criteria as a metric,D·:ℝkM⟶ℝ, as(15)Da≔12L∑i,jpi,jλi,jaai−1−λi,jaaj21/2,with λi,jamax0,min1,ajTai+aj/ai+aj2 for some a=a1T…aMTT∈ℝkM, am∈ℝk,∀m. Using D·, the preceding inequality (10) becomes(16)hX−EhX+|X≥D∇hX2.One can viewD· as an improvement potential indicator. Specifically, we have the following lemma.Lemma 2.
D∇hX∗=0 only if X∗ is a Pareto optimal solution of Pmo, and the reverse direction holds true if each fm is convex.Proof.
We first prove one direction thatD∇hX∗=0 implies X∗ is a Pareto optimal solution by contraposition. Assume that X with ∑i=mMxm=0 is not Pareto optimal; then, there exist i and j≠i such that ∇fixi≠t·∇fjxj, ∀t∈ℝ+, which implies D∇hX>0. The other direction in this lemma is straightforward. We omit the detail.
We now turn to investigate the convergence rate of the RCD algorithm. Convergence rate of methods for single-objective problem such asminx∈Cfx is usually measured with respect to the gap from its optimal value f∗. However, different from the single objective-based optimization problem, the generated sequence of the MO algorithm may converge to different points in the Pareto optimal frontier, and there is no a priori way to determine which point the sequence converges to; this property will be further substantiated by the numerical simulations. Therefore, one needs to construct an alternative benchmark that measures the convergence rate (the construction of such alternative gap function for multiobjective optimization problems is also discussed by Dutta et al. and Tanabe et al. [28–30] recently). We define the following two measures (functions):(17)h†X=minFY≼¯FX,Y∈ChY,v†X=maxFY≼¯FX,Y∈ChX−hY=hX−h†X,where h†X provides a lower bound of the potential function hX and v†X measures the gap between the current value of potential function and such a lower bound. These two measures have the following properties.Lemma 3.
For anyX1,X2∈C, if FX2≺¯FX1, it has h†X2≥h†X1 and v†X2≤v†X1. Furthermore, the solution X∗ is a Pareto optimal point only if v†X∗=0, and the reverse direction holds true if each fm is convex.Proof.
The first half follows directly from the observation thatFX2≺¯FX1 implies Y∈C:FY≺¯FX2⊆Y∈C:FY≺¯FX1. The rest of the proof is straightforward, and we omit the details.
Althoughh†,v† are only tangential to the following convergence result for non-convex objective functions, they are pivotal to obtain convergence rate for convex and strongly convex objective functions. Then, we have the following preliminary convergence rate result for generally non-convex objective functions given as follows.Theorem 1.
If level setℒ≔X∈C:FX≺¯FX0 is bounded, then the following holds:(18)mink=1,…,nED∇hXk|X0≤hX0−h†X0n.Proof.
Taking expectation of both sides of (17) with respect to X0 and summing up to n, we arrive at the following:(19)n·mink=1,…,nED∇hXk|X02≤∑kE2D∇hXk|X0≤∑kED2∇hXk|X0≤hX0−EhX1|X0+EhX1|X0−EhX2|X0+⋯+EhXn−1|X0−EhX1|X0=hX0−EhX1|X0≤hX0−h†X0,where the second inequality follows from Jensen’s Inequality. Since ℒ is bounded, we know that hX0−h†X0 is also bounded, and hence (18) follows.
Note that in the non-convex case, the stationary point could only be a local minimum.


## 4.2. Convergence Rate: Convex Case

When eachfm is convex, an accelerated convergence rate can be obtained. But first we need some preliminary results. In the same spirit of the dual norm, for a non-empty compact set ℬ⊂ℝkM, we define the dual function of D· on ℬ as(20)Dℬ∗d=maxY∈AℬdYTd,where Aℬd=Y=y1T…yMTT∈ℬ:0≤DY≤1,ymTdm≥0,∀m∈M. Then, the following lemma gives the counterpart of Cauchy–Schwarz inequality with respect to the feasible set C of problem pmo.Lemma 4.
Givend∈C and a non-empty compact set ℬ⊂ℝkM, for all Y∈ℬ∩Y=y1T…yMTT∈ℝkM|ymTdm≥0,∀m∈M, the following inequality holds true:(21)YTd≤DY·Dℬ∗d.Furthermore, there exists a numberΓℬ≤0 such that Dℬ∗d≤Γℬd for all d∈C.Proof.
SinceAℬd is a compact set, then Dℬ∗· is well defined. Depending on the value of DY, we have two cases as follows:(1)
IfDY=0, from (17), we know Y must be in form of Y=t1g⋮tMg for some g∈ℝk and t1,…,tM∈ℝ+. Suppose there exists a d∈C such that YTd>0, which implies gTdm>0 for some m. However, this leads to ∑m=1MgTdm=gT∑m=1Mdm>0, which is a contradiction to the fact that d∈C. Therefore, DY=0 implies YTd=0 for all d∈C such that ymTdm≥0, ∀m∈M.(2)
IfDY>0, let A˜ℬd=Y∈ℬ|0<DY≤1,ymTdm≥0,∀m∈M. Clearly, it has A˜ℬd⊆Aℬd. Then, inequality (21) follows from(22)YTd=YTd·DYDY≤DY·supY∈A˜ℬdYTd≤DY·maxY∈AℬdYTd=DY·Dℬ∗d,where the second equality follows from the fact that λi,jkY=λi,jY, ∀k∈ℝ, and hence it has DkY=kDY.
As for the last part of the lemma, we can compute the lower bound valueΓℬ as(23)Γℬ=supd>0Dℬ∗dd≤maxd:d≤1Dℬ∗d=maxd:d≤1maxa∈AℬdaTd,where Aℬ=Y,d|Y∈Aℬd,d∈C,d≤1 is a compact set.Theorem 2.
Given an initial solutionX0, if the level set ℒ≔X∈C|FX≺¯FX0 is bounded, then the solution Xn generated by the n-th iteration of RCD algorithm satisfies(24)Ev†Xn|X0≤Γℬ2RX02n,where RX0≔maxY∈ℒX0−Y and Γℬ is defined with respect to Dℬ∗ in Lemma 4 with ℬ≔∇hX:X∈ℒ. Furthermore, Γℬ is bounded by(25)Γℬ≤∇hX0+L·maxZ∈ℒ∑m=1Mxm0−zm≤∇hX0+LM·RX0.Proof.
As the level setℒ is bounded, problem pmo always admits solution. On the other hand, the Lipschitz property in Assumption 1 implies(26)∇hX−∇hZ≤∑m=1M∇fmxm−∇fmzm≤L∑m=1Mxm−zm,which further implies the boundedness of the set ℬ. Therefore, Γℬ satisfies the following inequality:(27)Γℬ=maxY,d∈AℬYTd≤maxY,d∈AℬY·d≤maxY∈ℬY≤∇hX0+maxZ∈ℒ∇hX0−∇hZ.
Then, it has(28)0≤v†Xn=maxFY≼¯FXn,Y∈ChXn−hY≤maxFY≼¯FXn,Y∈C∇hXnTXn−Y≤maxFY≼¯FXn,Y∈CD∇hXn·DℬastXn−Y=D∇hXn·maxFY≼¯FXn,Y∈CDℬastXn−Y≤D∇hXn·Γℬ·RX0,,where the second inequality is from the convexity of h·, and the third inequality is from (24). Inequality (28) together with (17) gives(29)hXn−EhXn+1|Xn≥v†Xn2Γℬ2RX02⟹EhXn+1−h†Xn|Xn≤v†Xn−v†Xn2Γℬ2RX02.
Since it hasFXn+1≺¯FXn, applying Lemma 3 to the preceding inequality gives(30)Ev†Xn+1|Xn≤EhXn+1−h†Xn|Xn≤v†Xn−v†Xn2Γℬ2RX02.
Taking expectation of both sides of the above inequality and applying Jensen’s inequality,Ev†Xn2|X0geEv†Xn|X02, it has(31)Δn+1≤Δn−Δn2Γℬ2RX02,where Deltan=Ev†Xn|X0. Since Δn+1≤Δn, it has(32)1Δn≤1Δn+1−ΔnΔn+1·1Γℬ2RX02⟹1Γℬ2Rx02≤1Δn+1−1Δn⟹Δn≤Γℬ2RX02n.


## 4.3. Convergence Rate: Strongly Convex Case

In this section, we investigate the convergence rate when functionfm· is σ-strongly convex for all m∈M.Assumption 3.
There exists aσ>0 such that(33)fmym≥fmxm+∇fmxmTym−xm+σ2ym−xm2,for all xm,ym∈ℝk.
Summing upfm leads to the strong convexity of the Lyapunov function, i.e.,(34)hY≥hX+∇hXTY−X+σ2Y−X2,∀Y,X∈ℝkM.Theorem 3.
Given an initial feasible solutionX0, if level set ℒ≔X∈C:FX≺¯FX0 is bounded, then the RCD algorithm satisfies(35)Ev†Xn|X0≤1−2σΓℬn·v†X0,where Γℬ is defined in Lemma 4 with respect to the set ℬ=∇hX:X∈ℒ.Proof.
Applying Lemma4 to (34), it has(36)hY≥hY+∇hYTY−X+σ2Y−X2⇒hY≥hX+∇hXTY−X+σ2ΓℬDℬ∗Y−X2⇒∇hXTX−Y−σ2ΓℬDℬ∗X−Y2≥hX−hY.
Let(37)CLX=Y∈C|∇fmxmTxm−ym≥0,∀m∈M,CRX=Y∈C|FY≺¯FX..
Then, one can easily verify thatCRX⊆CLX by using the convexity of fm. Maximizing the left-hand side of (36) with respect to CLX and the right-hand side with respect to CRX yields(38)Γℬ2σD∇hX2=maxt∈ℝD∇fXt−σ2Γℬt2≥maxY∈CLXD∇fx·Dℬ∗X−Yσ2ΓℬDℬ∗X−Y2≥maxY∈CLX∇hXTX−Y−σ2ΓℬDℬ∗X−Y2≥maxY∈CRX∇hXTX−Y−σ2ΓℬDℬ∗X−Y2≥maxY∈CRXhX−hY=v†X,where the second inequality follows from Lemma 4. Letting X=Xn, combining D∇fXn2≥2σ/Γℬv†Xn with (17) yields(39)hXn−EhXn+1|Xn≥2σΓℬv†Xn⇒Ev†Xn+1|Xn≤1−2σΓℬv†Xn.
Taking expectation of both sides and applying the resulting inequality iteratively leads to (35).


## 4.4. Convergence Rate in Probability

Again with the aid of gap benchmarkv†, in this section, we are able to establish the convergence rate in probability for the RCD algorithm. First we introduce the following lemma [31].Lemma 5 (see [31]).
Letxi0>0 be a constant, consider a 0<ϵ<xi0, and let xinn be a non-negative, non-increasing sequence of random variables with one of the following properties:(1)
Eξn+1|ξn≤ξn−ξn2/c for all n>0 and r>ϵ.(2)
Eξn+1|ξn≤1−1/cξn for all n such that ξn≥ϵ and c>1 is a constant.Then, given confidence levelρ∈0,1, if property (1) holds, we can choose ϵ<c and(40)N≥cϵ1+log1ρ+2−cξ0.If property (2) holds, we choose(41)N≥clogξ0ερ.Then, we have(42)ℙξN≤ε≥1−ρ.Proof (see [31], Theorem 1).
This proof is done by applying Markov inequality.
Then, we have the following theorem that quantifies the confidence of reducing the improvement of potential function to no more thanϵ.Theorem 4.
Ifℒ=X∈C:FX≺¯FX0 is bounded and each fm is convex, let ℬ=∇hX:X∈ℒ; then, we can choose(43)N≥Γℬ2R2X0ε1+log1ρ−Γℬ2R2X0v†X0+2,where Γℬ is the corresponding bounding coefficient with respect to ℬ; if each fm is σ-strongly convex, then we may choose(44)N≥Γℬ2σlogv†X0ερ.Under either way, it has(45)ℙv†XN≤ε≥1−ρ.Proof.
This result follows directly from the observation that the gap sequence generated by RCD:v†Xn, satisfies the properties mentioned in Lemma 5, according to (32) and (39).


## 5. Numerical Simulation

In this section, we use simulation method to demonstrate our theoretical results. Consider the following example with 10 quadratic objective functions, each objective function taking the form of (46), form=1,…,10(46)fmxm=12πm1xm12+12πm2xm22+12πm3xm32,for m=1,…,10. The coefficients πm1,πm2,πm3 are randomly generated in each trial of test. The 10-th objective (agent) is selected as a central coordinator, i.e., at each iteration, one of the first 9 objectives is randomly picked with equal probability to communicate with the 10-th objective. For a given initial point X0, we run the algorithm 3 times and record their corresponding potential function value trajectories. The results are summarized in Figure 3.Figure 3
The potential function values for the three runs all stabilize eventually, but they converge to different limiting levels.As is clearly seen, although each of the three runs is convergent, their limiting levels of potential function value differ, indicating that they converge to different points on the Pareto front.To further highlight this point, we run two extra sets of simulations. With the same setting as the preceding simulation (10 quadratic objectives, randomly generatedπm), again we fix an initial point at X0. For the first set of simulation, the communication network is designed to be complete, i.e., at each iterate, any pair i,j can be chosen with equal probability. For the second test, the communication network is the same as the preceding simulation, i.e., the 10-th objective being a central coordinator and one of the rest of the objectives is randomly selected with equal probability to communicate with 10-th objective at each iterate. For each test, we run the RCD algorithm for 10 times, and the resulting value trajectories for the 10-th objective function are recorded in the following figures.As is clearly indicated in Figure4, the limiting levels of the 10 runs differ dramatically from each other. As for the central coordinator network (see Figure 5), the limiting level of the coordinator is relatively more stable at around 0.38. What is interesting is that when compared to the complete network with random pairing, the central coordinator somehow manages to achieve a significantly better level of objective value. Indeed, the lowest level of the 10-th objective in the complete network barely touches 0.47. This is probably because the central coordinator is involved in every single iterate; as a result, its corresponding objective is more heavily optimized.Figure 4
In a complete network, the limiting potential function value varies dramatically from each other.Figure 5
In a central coordinator network, the limiting potential function value is much more stable, and notably the central coordinator is able to achieve a significantly lower limiting value than in a complete network.


## 6. Discussion and Concluding Remarks

We propose a randomized coordinate descent algorithm to solve the large-scale, linearly coupled resource allocation problem with selfish agents. This method has a low computational cost in each iteration and can guarantee convergence to the Pareto optimal solution under mild conditions, and then we derive the convergence rate of such an algorithm. As the sampling probability is fixed exogenously in the current framework, one potential extension is to identify these sampling probabilities with respect to the problem’s parameter, which may further enhance the efficiency of the algorithm. Specifically, it is known in the literature that the selfish/greedy behavior of the individual agents generally leads to efficiency loss from a systemic perspective [27, 32], and hence the design of a sampling probability that will narrow this efficiency gap would be an interesting direction of future research.



---

*Source: 9939805-2021-07-15.xml*