1 Competitive Equilibrium for Dynamic Multi-Agent Systems Social Shaping and Price Trajectories

2025-04-30 0 0 2.53MB 13 页 10玖币

侵权投诉

Competitive Equilibrium for Dynamic Multi-Agent

Systems: Social Shaping and Price Trajectories

Zeinab Salehi, Yijun Chen, Elizabeth L. Ratnam, Ian R. Petersen, and Guodong Shi

Abstract—In this paper, we consider dynamic multi-agent

systems (MAS) for decentralized resource allocation. The MAS

operates at a competitive equilibrium to ensure supply and

demand are balanced. First, we investigate the MAS over a ﬁnite

horizon. The utility functions of agents are parameterized to

incorporate individual preferences. We shape individual prefer-

ences through a set of utility functions to guarantee the resource

price at a competitive equilibrium remains socially acceptable,

i.e., the price is upper-bounded by an affordability threshold.

We show this problem is solvable at the conceptual level. Next,

we consider quadratic MAS and formulate the associated social

shaping problem as a multi-agent linear quadratic regulator

(LQR) problem which enables us to propose explicit utility sets

using quadratic programming and dynamic programming. Then,

a numerical algorithm is presented for calculating a tight range of

the preference function parameters which guarantees a socially

accepted price. We investigate the properties of a competitive

equilibrium over an inﬁnite horizon. Considering general utility

functions, we show that under feasibility assumptions, any com-

petitive equilibrium maximizes the social welfare. Then, we prove

that for sufﬁciently small initial conditions, the social welfare

maximization solution constitutes a competitive equilibrium with

zero price. We also prove for general feasible initial conditions,

there exists a time instant after which the optimal price, corre-

sponding to a competitive equilibrium, becomes zero. Finally, we

speciﬁcally focus on quadratic MAS and propose explicit results.

Index Terms—Competitive equilibrium, multi-agent systems,

resource allocation, social welfare optimization, dynamic pro-

gramming, linear quadratic regulator (LQR).

I. INTRODUCTION

EFFICIENT resource allocation is a fundamental prob-

lem in the literature that can be addressed by MAS

approaches [1], [2]. Resource allocation problems are of great

importance when the total demand must equal the total supply

for safe and secure system operation [3]–[5]. Depending on

the application, there exist two common approaches: (i) social

welfare where agents collaborate to maximize the total agents’

utilities [6]–[8]; (ii) competitive equilibrium in which agents

compete to maximize their individual payoffs [9], [15]. At

the competitive equilibrium, the resource price along with

the allocated resources provides an effective solution to the

allocation problem, thereby clearing the market [10].

Z. Salehi, E. L. Ratnam, and I. R. Petersen are with the Research

School of Engineering, The Australian National University, Canberra,

Australia (e-mail: zeinab.salehi@anu.edu.au; elizabeth.ratnam@anu.edu.au;

ian.petersen@anu.edu.au).

Y. Chen and G. Shi are with the Australian Center for Field Robotics,

School of Aerospace, Mechanical and Mechatronic Engineering, The Uni-

versity of Sydney, NSW, Australia (e-mail: yijun.chen@sydney.edu.au;

guodong.shi@sydney.edu.au).

Some preliminary results of this paper are accepted for presentation at

the 61st IEEE Conference on Decision and Control [24], and the 12th IFAC

Symposium on Nonlinear Control Systems [25].

A fundamental theorem in classical welfare economics

states that the competitive equilibrium is Pareto optimal,

meaning that no agent can deviate from the equilibrium to

increase proﬁts without reducing another’s payoff [11]–[14].

It is also proved that under some convexity assumptions,

the competitive equilibrium maximizes social welfare [15]–

[17]. Mechanism design is a well-known approach to social

welfare maximization [18]–[20]. The key point in achieving

a competitive equilibrium is efﬁcient resource pricing that

depends on the utility of each agent. The corresponding price,

however, is not guaranteed to be affordable for all agents. If

some participants select their utility functions aggressively,

the price potentially increases to the point that it becomes

unaffordable to other agents who have no alternative but to

leave the system [21], [22]. A recent example is the Texas

power outage disaster in February 2021, when some citizens

who had access to electricity during the period of rolling power

outages received inﬂated (and in some cases, unaffordable)

electricity bills for their daily power usage [23].

In this paper, we consider MAS with distributed resources

and linear time-invariant (LTI) dynamics. Over a ﬁnite horizon,

we achieve affordability by parameterizing utility functions

and proposing some limits on the parameters such that the

resource price at a competitive equilibrium never exceeds a

given threshold, leading to the concept of social shaping. We

design an optimization problem and propose a conceptual

scheme, based on dynamic programming, which shows how

the social shaping problem is solvable implicitly for general

classes of utility functions. Next, the social shaping problem is

reformulated for quadratic MAS, leading to an LQR problem.

Solving the LQR problem using quadratic programming and

dynamic programming, we propose two explicit sets for the

utility function parameters such that they lead to socially

acceptable resource prices. Then, a numerical algorithm based

on the bisection method is presented that provides accurate and

practical bounds on the utility function parameters, followed

by some convergence results.

Over an inﬁnite horizon, we examine the behavior of

resource price under a competitive equilibrium. We extend our

previous work in [15] which considered a ﬁnite horizon, by

showing that in the inﬁnite horizon problem, the competitive

equilibrium maximizes social welfare if feasibility assump-

tions are satisﬁed. We also prove that for sufﬁciently small

initial conditions, the social welfare maximization constitutes

a competitive equilibrium with zero price; implying adequate

resources are available in the network to meet the demand

of all agents. Furthermore, we show for any feasible initial

condition, there exists a time instant after which the optimal

arXiv:2210.11064v1 [eess.SY] 20 Oct 2022

price, corresponding to the competitive equilibrium, is zero.

Next, as a special case, we study quadratic MAS for which

the system-level social welfare optimization becomes a classi-

cal constrained linear quadratic regulator (CLQR) problem.

Finally, we investigate how the results can be extended to

tracking problems.

Some preliminary results of this paper are accepted for

presentation at the 61st IEEE Conference on Decision and

Control [24], and the 12th IFAC Symposium on Nonlinear

Control Systems [25]. We discussed the problem of social

shaping for dynamic MAS over a ﬁnite horizon in [24], where

the proofs of the proposed theorems were omitted due to

the page limits. In [25], we discussed the existence of a

competitive equilibrium and the behavior of the associated

resource price over an inﬁnite horizon. In this paper, we extend

our prior works in the following ways: (i) we introduce two

real-world applications for the problem formulation; (ii) we

present the missing proofs of the proposed theorems in [24];

(iii) we investigate tracking problems; and (iv) we provide

new, and a more extensive series of numerical examples.

The remainder of this paper is organized as follows. In

Section II, we introduce the problem formulation and its real-

world applications. In Section III, we present a conceptual

scheme for solving the social shaping problem over a ﬁnite

horizon. In Section IV, we address the social shaping problem

for quadratic MAS over a ﬁnite horizon. In Section V, we

examine the existence and properties of a competitive equilib-

rium over an inﬁnite horizon. Then, we investigate how the

results can be extended to tracking problems. Finally, Section

VI provides numerical examples and Section VII contains

concluding remarks.

Notation: We denote by Rand R≥0the ﬁelds of real

numbers and non-negative real numbers, respectively. Let I

denote the identity matrix with a suitable dimension. The

symbol 1

1represents a vector with an appropriate dimension

whose entries are all 1. We use k·k to denote the Euclidean

norm of a vector or its induced matrix norm. Let σmin(·)and

σmax(·)represent the minimum and maximum eigenvalues of

a square matrix, respectively.

II. PROBLEM FORMULATION

A. The Dynamic Multi-agent Model

Consider a dynamic MAS with nagents indexed in the set

V={1,2, . . . , n}. This MAS is studied in the time horizon

N. Let time steps be indexed in the set T={0,1, . . . , N −1}.

Each agent i∈ V is a subsystem with dynamics represented

xi(t+ 1) = Aixi(t) + Biui(t), t ∈ T ,

where xi(t)∈Rdis the dynamical state, xi(0) ∈Rdis

the given initial state, and ui(t)∈Rmis the control input.

Also, Ai∈Rd×dand Bi∈Rd×mare ﬁxed matrices.

Upon reaching the state xi(t)and employing the control input

ui(t)at time step t∈ T , each agent ireceives the utility

fi(xi(t),ui(t)) = f(·;θi) : Rd×Rm7→ R, where θi∈Θ

is a personalized parameter of agent i. The terminal utility

achieved as a result of reaching the terminal state xi(N)is

denoted by φi(xi(N)) = φ(·;θi) : Rd7→ R. Let ai(t)∈R

denote the amount of excess resource generated by agent

iin addition to the supply they need to stay at the origin

at time t∈ T . The amount of consumed resource by the

same agent for taking the control action ui(t)is denoted by

hi(ui(t)) : Rm7→ R≥0. The total excess network supply is

represented by C(t) := Pn

i=1 ai(t)such that C(t)>0at

each time interval t∈ T .

Agents are interconnected through a network without any

external resource supply. They share resources at the price

λt, which denotes the price of unit traded resource across the

network at time step t∈ T . The traded resource for agent i

is denoted by ei(t)∈Rwhich can never be greater than the

net supply, i.e., ei(t)≤ai(t)−hi(ui(t)). Then, each agent i

receives a payoff which consists of the utility from resource

consumption and the income λtei(t)from resource exchange.

B. Competitive Equilibrium

Let Ui= (u>

i(0),...,u>

i(N−1))>and Ei=

(ei(0), . . . , ei(N−1))>denote the vector of control inputs

and the vector of trading decisions associated with agent i

over the whole time horizon, respectively. Also, let u(t) =

(u>

1(t),...,u>

n(t))>and e(t)=(e1(t), . . . , en(t))>denote

the vector of control inputs and the vector of trading decisions

associated with all agents at time step t∈ T , respectively. Let

U= (u>(0),...,u>(N−1))>and E= (e>(0),...,e>(N−

1))>be the vector of all control inputs and the vector

of all trading decisions at all time steps, respectively. Let

λ= (λ0, . . . , λN−1)>denote the vector of optimal resource

prices throughout the entire time horizon.

Deﬁnition 1. The competitive equilibrium for a dynamic MAS

is the triplet (λ∗,U∗,E∗)which satisﬁes the following two

conditions.

(i) Given λ∗, the pair (U∗,E∗)maximizes the individual

payoff function of each agent; i.e., each (U∗

i,E∗

i)solves

the following constrained maximization problem

max

Ui,Ei

φ(xi(N); θi) +

N−1

t=0 f(xi(t),ui(t); θi) + λ∗

tei(t)

s.t.xi(t+ 1) = Aixi(t) + Biui(t),

ei(t)≤ai(t)−hi(ui(t)), t ∈ T .

(1)

(ii) The optimal trading E∗balances the total traded resource

across the network at each time step; that is,

i=1

e∗

i(t)=0, t ∈ T .(2)

C. Social Welfare Maximization

In the context of a society, the beneﬁt of the whole com-

munity is important, not just a single agent. It is desirable

to ﬁnd an operating point (U∗,E∗)at which social welfare

is maximized. The objective can be attained by solving the

following social welfare maximization problem

max

U,E

i=1 φ(xi(N); θi) +

N−1

t=0

f(xi(t),ui(t); θi)!

s.t.xi(t+ 1) = Aixi(t) + Biui(t),

ei(t)≤ai(t)−hi(ui(t)),

i=1

ei(t)=0, t ∈ T , i ∈ V,

(3)

where the total agent utility functions are maximized.

Assumption 1. f(·;θi)and φ(·;θi)are concave functions for

all i∈ V. Additionally, hi(·)is a non-negative convex function

such that hi(z)< b represents a bounded open set of zin Rm

for b > 0and i∈ V. Furthermore, assume Pn

i=1 ai(t)>0

for all t∈ T .

Proposition 1 (as in [15]).Suppose Assumption 1 holds. Then

the competitive equilibrium and the social welfare equilibrium

exist and coincide. Additionally, the optimal price λ∗

tin (1)

is obtained from the Lagrange multiplier associated with the

balancing equality constraint Pn

i=1 ei(t)=0in (3).

D. Social Shaping Problem

The optimal price, λ∗

t, is the Lagrange multiplier corre-

sponding to the equality constraint in (3), which depends on

the utility functions of agents. Without regulation on the choice

of utility functions, the price may become extremely high and

unaffordable for some agents. In such cases, agents who ﬁnd

the price unaffordable cannot compete in the market and have

no alternative but to leave the system. Consequently, all of

the resources will be consumed by a limited number of agents

who have dominated the price by aggressively selecting their

utilities — which we consider to be socially unfair and not

sustainable. To improve the affordability of the price for all

agents we require a mechanism, called social shaping, which

ensures the price is always below an acceptable threshold

denoted by λ†∈R>0. The problem of social shaping is

addressed for static MAS in [21] and [22]. In this paper, we

deﬁne an extended version of the social shaping problem for

dynamic MAS as follows.

Deﬁnition 2 (Social shaping for dynamic MAS).Consider a

dynamic MAS whose agents i∈ V have f(·;θi)and φ(·;θi)

as their running utility function and terminal utility function,

respectively. Let λ†∈R>0denote a price threshold that is

accepted by all agents. Find a range Θof personal parameters

θisuch that if θi∈Θfor i∈ V, then we yield λ∗

t≤λ†at all

time steps t∈ T .

E. Real-World Applications

In this section, we provide two real-world applications for

our problem formulation.

1) Community Microgrid: Consider a community micro-

grid consisting of nbuildings with rooftop photovoltaic (PV)

generation. Buildings are equipped with air conditioners to

keep their temperature at a desired level, forming a group of

nthermostatically controlled loads (TCL). Each TCL, indexed

by i∈ V, has dynamics represented by xi(t+ 1) = Aixi(t) +

Biui(t) + ˜

Biw, where xi(t)is the internal temperature (℃),

ui(t)is the consumed energy (kWh), and wreﬂects the impact

of the ambient temperature (℃) [26], [27].

In this context, each building i∈ V represents an agent

with excess rooftop PV energy ai(t)in (kWh) at time t∈ T .

Buildings are connected through a network to share their ex-

cess energy at a price λ∗

t(USD/kWh) such that the total excess

PV generation balances the total demand from TCLs at each

time step t∈ T . Depending on the internal temperature xi(t)

and the consumed energy ui(t), each household valuates the

outcome achieved through a utility function fi(xi(t), ui(t));

for example, if the temperature is close to the desired level

or the amount of consumed energy is relatively low then the

household achieves a high level of satisfaction, and therefore,

a high fi(·).

Different choices of utility functions lead to different elec-

tricity prices λ∗

t. Assume that all buildings have the same

class of utility functions but with different parameters; i.e.,

each building is associated with the utility fi(xi(t), ui(t)) =

f(xi(t), ui(t); θi), where θiis the personal parameter of

building iwhich can be selected independently. By social

shaping and imposing some bounds on the choice of θi, the

coordinator guarantees that the electricity price never exceeds

an acceptable threshold, so as to ensure affordability.

2) Carbon Permit Trading System: The well-known RICE

model can be formulated as a dynamic multi-agent model [28],

[29]. Each region captured in the RICE model represents an

agent. Each time step t∈ T represents a 10-year period. Let

xi(t)be each region i’s economic output (USD) at time step t

and ui(t)be the amount of emission (GtCO2) it emits at time

step t. In the RICE model, each region’s economic output at

time step t+ 1 depends on its economic output at time step

tand the emitted emissions at time step t. Thus, each region

i∈ V has its nonlinear dynamics xi(t+ 1) = gi(xi(t),ui(t)).

Upon the states and control actions, each region ievaluates its

social welfare according to a utility function fi(xi(t),ui(t))

capturing the fact that the societal welfare for a region depends

on both the economic output and carbon emissions.

A carbon permit trading bloc scheme has been proposed

using the RICE model [30]. Under the scheme, the total

permitted global emissions at each time step tis assumed

to be less than C(t)(GtCO2). Each region iis assigned

with its carbon permit ai(t)(GtCO2) at time step twith the

relationship Pi∈V ai(t) = C(t). Regions are allowed to buy

or sell carbon permits at a price λ∗

t(USD/GtCO2) such that

the total carbon permits balance the total demand of emissions

to be emitted by each region at each time step t.

Different conﬁgurations of utility functions yield different

prices λ∗

tfor unit carbon permit. Suppose that all regions

adopt the same class of utility functions but with different

choices of parameters; i.e., each region has its utility function

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

1CompetitiveEquilibriumforDynamicMulti-AgentSystems:SocialShapingandPriceTrajectoriesZeinabSalehi,YijunChen,ElizabethL.Ratnam,IanR.Petersen,andGuodongShiAbstractInthispaper,weconsiderdynamicmulti-agentsystems(MAS)fordecentralizedresourceallocation.TheMASoperatesatacompetitiveequilibriumtoensuresupp...

展开>> 收起<<

1 Competitive Equilibrium for Dynamic Multi-Agent Systems Social Shaping and Price Trajectories.pdf

共13页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

1 Competitive Equilibrium for Dynamic Multi-Agent Systems Social Shaping and Price Trajectories

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: