# Social Shaping of Dynamic Multi-Agent Systems over a Finite Horizon

Zeinab Salehi, Yijun Chen, Ian R. Petersen, Elizabeth L. Ratnam, and Guodong
Shi This work was supported by the Australian Research Council under grants
DP190102158, DP190103615, and LP210200473.Z. Salehi, I. R. Petersen and E. L.
Ratnam are with the Research School of Engineering, The Australian National
University, Canberra, Australia. (E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Y. Chen and G. Shi are
with the Australian Center for Field Robotics, The University of Sydney, NSW,
Australia. (E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

This paper studies self-sustained dynamic multi-agent systems (MAS) for
decentralized resource allocation operating at a competitive equilibrium over
a finite horizon. The utility of resource consumption, along with the income
from resource exchange, forms each agent’s payoff which is aimed to be
maximized. Each utility function is parameterized by individual preferences
which can be designed by agents independently. By shaping these preferences
and proposing a set of utility functions, we can guarantee that the optimal
resource price at the competitive equilibrium always remains socially
acceptable, i.e., it never violates a given threshold that indicates
affordability. First, we show this problem is solvable at the conceptual level
under some convexity assumptions. Then, as a benchmark case, we consider
quadratic MAS and formulate the associated social shaping problem as a multi-
agent LQR problem which enables us to propose explicit utility sets using
quadratic programming and dynamic programming. Finally, a numerical algorithm
is presented for calculating the range of the preference function parameters
which guarantee a socially accepted price. Some illustrative examples are
given to examine the effectiveness of the proposed methods.

##  I INTRODUCTION

Control and analysis of multi-agent systems (MAS) have received great
attention among researchers due to their wide application in different areas
such as economics [1], water systems [2], carbon markets [3], robotics [4],
power systems [5], and smart grids [6]. In general, a MAS consists of a group
of agents who collaborate through a network to achieve a common objective or
compete to reach an individual goal [7]. MAS are capable of solving complex
problems in a distributed manner which are much harder or impossible to be
solved by a single agent in a centralized way.

One of the most fundamental problems in the literature is efficient resource
allocation, which can be addressed by MAS approaches [8, 9]. Depending on the
application, there exist two common approaches: (i) social welfare where
agents collaborate to maximize the total agents’ utilities [10, 11]; (ii)
competitive equilibrium in which agents compete to maximize their individual
payoffs [17, 12]. In this paper, distributed resource allocation is treated as
an optimization problem in which each agent maximizes its payoff under some
constraints and the decision variable determines the amount of resource
dedicated to each agent. Considering systems with dynamical states, this
optimization problem becomes an optimal control problem. A competitive
equilibrium, which is the pair of allocated resource and resource price, is
proven to be an efficient solution to resource allocation problems by clearing
the market [13].

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 achieve more profit without reducing other’s payoff
[14, 15, 16]. It is also proved that under some convexity assumptions, the
competitive equilibrium maximizes social welfare [18, 19, 17]. Mechanism
design is a well-known approach for social welfare maximization [20]. For
instance, the Groves mechanism maximizes social welfare in a way that truth-
telling of personal information by all agents forms a dominant strategy [21].
The key point in achieving competitive equilibrium is efficient 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. In such cases, the
available resources are consumed by a limited number of affluent agents, which
is not socially fair in societies where it is deemed that all entities are
entitled to equal access [22, 23]. A recent example is the Texas power outage
disaster in February 2021, when some citizens who had access to electricity
during the power outage received outstanding electricity bills for their daily
power usage, resulting in the dissatisfaction of customers [24].

In this paper, we investigate how socially acceptable resource pricing at a
competitive equilibrium is achievable for self-sustained dynamic MAS with
distributed resource allocation over a finite horizon. Agents allocate their
resources in a way that their payoff, which consists of the utility from
resource consumption and the income from resource exchange, is maximized over
the whole horizon. The utility functions selected by agents affect resource
pricing at the competitive equilibrium. By parameterizing these utility
functions considering the preferences of agents and proposing some bounds on
the parameters, we control the resource price such that it never exceeds a
given threshold, so we achieve affordability. We face an optimization problem
and address it from three points of view.

  * •

A conceptual scheme, based on dynamic programming, is presented to show how
the social shaping problem is solvable implicitly under some convexity
assumptions for general classes of utility functions. Also, it is proved that
when the price is positive, the total supply and demand are balanced across
the network.

  * •

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 preferences of agents which
are proved to be socially admissible; i.e., they lead to socially acceptable
resource prices.

  * •

A numerical algorithm based on the bisection method is presented that provides
accurate and practical bounds on the preferences of agents, followed by some
convergence results.

The rest of the paper is organized as follows. In Section II, we review the
multi-agent model, the system-level equilibria, and the concept of social
shaping for dynamic MAS. In Section III, we present a conceptual scheme for
solving the social shaping problem. In Section IV, we introduce quadratic MAS
and the LQR problem that follows. Then, we propose two explicit sets of
agents’ preferences using optimization methods. In Section V, we present a
numerical algorithm which provides accurate bounds on agents’ preferences.
Finally, Section VI includes some simulation results and Section VII contains
conclusions.

Notation: We denote by $\mathbb{R}$ and $\mathbb{R}^{\geq 0}$ the fields of
real numbers and non-negative real numbers, respectively. $\mathbf{I}$ is the
identity matrix with a suitable dimension. The symbol $\mathbb{1}$ represents
a vector with an appropriate dimension whose entries are all $1$. We use
$\left\|\mathbf{\cdot}\right\|$ to denote the Euclidean norm of a vector or
its induced matrix norm.

##  II Problem Formulation

In this section, we introduce the multi-agent system model, system level
equilibria, and the concept of social shaping.

###  II-A The Dynamic Multi-agent Model

Consider a dynamic MAS with $n$ agents indexed in the set
$\mathcal{V}=\\{1,2,\dots,n\\}$. This MAS is studied in the time horizon $N$.
Let time steps be indexed in the set $\mathcal{T}=\\{0,1,\dots,N-1\\}$. Each
agent $i\in\mathcal{V}$ is a subsystem with dynamics represented by

$\mathbf{x}_{i}(t+1)=\mathbf{A}_{i}\mathbf{x}_{i}(t)+\mathbf{B}_{i}\mathbf{u}_{i}(t),\quad
t\in\mathcal{T},$

where $\mathbf{x}_{i}(t)\in\mathbb{R}^{d}$ is the dynamical state,
$\mathbf{x}_{i}(0)\in\mathbb{R}^{d}$ is the given initial state, and
$\mathbf{u}_{i}(t)\in\mathbb{R}^{m}$ is the control input. Also,
$\mathbf{A}_{i}\in\mathbb{R}^{d\times d}$ and
$\mathbf{B}_{i}\in\mathbb{R}^{d\times m}$ are fixed matrices. Upon reaching
the state $\mathbf{x}_{i}(t)$ and employing the control input
$\mathbf{u}_{i}(t)$ at time step $t\in\mathcal{T}$, each agent $i$ receives
the utility
$f_{i}(\mathbf{x}_{i}(t),\mathbf{u}_{i}(t))=f(\cdot;\theta_{i}):\mathbb{R}^{d}\times\mathbb{R}^{m}\mapsto\mathbb{R}$,
where $\theta_{i}\in\Theta$ is a personalized parameter of agent $i$. The
terminal utility achieved as a result of reaching the terminal state
$\mathbf{x}_{i}(N)$ is denoted by
$\phi_{i}(\mathbf{x}_{i}(N))=\phi(\cdot;\theta_{i}):\mathbb{R}^{d}\mapsto\mathbb{R}$.
At each time step $t\in\mathcal{T}$, agent $i$ provides a local energy supply
$a_{i}(t)\in\mathbb{R}^{\geq 0}$, and consumes an amount of energy
$h_{i}(\mathbf{u}_{i}(t)):\mathbb{R}^{m}\mapsto\mathbb{R}^{\geq 0}$ as a
result of taking the control action $\mathbf{u}_{i}(t)$. The overall network
supply $C(t)>0$ is then defined as $C(t):=\sum_{i=1}^{n}a_{i}(t)$ for
$t\in\mathcal{T}$. Agents are interconnected through a network to sell (or
buy) their surplus (or shortage) of energy. This means each agent
$i\in\mathcal{V}$ can decide how much of their extra energy
$a_{i}(t)-h_{i}(\mathbf{u}_{i}(t))$ is going to be traded through the network
leading to a new decision variable named _strategic trading decision_ ,
denoted by $e_{i}(t)\in\mathbb{R}$. There is a physical constraint indicating
the traded resource for each agent can never be greater than the surplus of
resource, i.e., $e_{i}(t)\leq a_{i}(t)-h_{i}(\mathbf{u}_{i}(t))$. The price
for unit resource exchange across the network at each time step
$t\in\mathcal{T}$ is denoted by $\lambda_{t}$. Then, the income or cost from
resource exchange for agent $i$ is represented by $\lambda_{t}e_{i}(t)$.

###  II-B System-level Equilibria

Let
$\mathbf{U}_{i}=(\mathbf{u}_{i}^{\top}(0),\dots,\mathbf{u}_{i}^{\top}(N-1))^{\top}$
and $\mathbf{E}_{i}=(e_{i}(0),\dots,e_{i}(N-1))^{\top}$ denote the vector of
control inputs and the vector of strategic trading decisions associated with
agent $i$ over the whole time horizon, respectively. Also, let
$\mathbf{u}(t)=(\mathbf{u}_{1}^{\top}(t),\dots,\mathbf{u}_{n}^{\top}(t))^{\top}$
and $\mathbf{e}(t)=(e_{1}(t),\dots,e_{n}(t))^{\top}$ denote the vector of
control inputs and the vector of strategic trading decisions associated with
all agents at time step $t\in\mathcal{T}$, respectively. Let
$\mathbf{U}=(\mathbf{u}^{\top}(0),\dots,\mathbf{u}^{\top}(N-1))^{\top}$ and
$\mathbf{E}=(\mathbf{e}^{\top}(0),\dots,\mathbf{e}^{\top}(N-1))^{\top}$ be the
vector of all control inputs and the vector of all strategic trading decisions
at all time steps, respectively. Let
$\bm{\lambda}=(\lambda_{0},\dots,\lambda_{N-1})^{\top}$ denote the vector of
resource prices throughout the entire time horizon.

###### Definition 1

The competitive equilibrium for a dynamic MAS is the triplet
$(\bm{\lambda}^{\ast},\mathbf{U}^{\ast},\mathbf{E}^{\ast})$ which satisfies
the following two conditions.

  * (i)

Given $\bm{\lambda}^{\ast}$, the pair $(\mathbf{U}^{\ast},\mathbf{E}^{\ast})$
maximizes the individual payoff function of each agent; i.e., each
$(\mathbf{U}_{i}^{\ast},\mathbf{E}_{i}^{\ast})$ solves the following
constrained maximization problem

$\begin{aligned}
\max_{{\mathbf{U}}_{i},{\mathbf{E}}_{i}}\,\,\,&\phi(\mathbf{x}_{i}(N);\theta_{i})+\sum_{t=0}^{N-1}\Big{(}f(\mathbf{x}_{i}(t),\mathbf{u}_{i}(t);\theta_{i})+\lambda_{t}^{\ast}e_{i}(t)\Big{)}\\\
{\rm
s.t.}\quad&\mathbf{x}_{i}(t+1)=\mathbf{A}_{i}\mathbf{x}_{i}(t)+\mathbf{B}_{i}\mathbf{u}_{i}(t),\\\
&e_{i}(t)\leq a_{i}(t)-h_{i}(\mathbf{u}_{i}(t)),\quad
t\in\mathcal{T}.\end{aligned}$

(1)

  * (ii)

The optimal strategic trading $\mathbf{E}^{\ast}$ balances the total traded
resource across the network at each time step; that is,

$\sum_{i=1}^{n}e_{i}^{\ast}(t)=0,\quad t\in\mathcal{T}.$ (2)

###### Definition 2

The social welfare equilibrium for a dynamic MAS is the pair
$(\mathbf{U}^{\ast},\mathbf{E}^{\ast})$ which solves the following
optimization problem

$\displaystyle\max_{\mathbf{U},\mathbf{E}}$
$\displaystyle\sum_{i=1}^{n}\left(\phi(\mathbf{x}_{i}(N);\theta_{i})+\sum_{t=0}^{N-1}f(\mathbf{x}_{i}(t),\mathbf{u}_{i}(t);\theta_{i})\right)$
(3) $\displaystyle{\rm s.t.}$
$\displaystyle\mathbf{x}_{i}(t+1)=\mathbf{A}_{i}\mathbf{x}_{i}(t)+\mathbf{B}_{i}\mathbf{u}_{i}(t),$
$\displaystyle e_{i}(t)\leq a_{i}(t)-h_{i}(\mathbf{u}_{i}(t)),$
$\displaystyle\sum_{i=1}^{n}e_{i}(t)=0,\quad
t\in\mathcal{T},\,\,\,i\in\mathcal{V}.$

In the social welfare equilibrium, the total agent utility functions are
maximized.

###### Assumption 1

$f(\cdot;\theta_{i})$ and $\phi(\cdot;\theta_{i})$ are concave functions for
all $i\in\mathcal{V}$. Additionally, $h_{i}(\cdot)$ is a non-negative convex
function such that $h_{i}(\mathbf{z})<b$ represents a bounded open set of
$\mathbf{z}$ in $\mathbb{R}^{m}$ for $b>0$ and $i\in\mathcal{V}$. Furthermore,
assume $\sum_{i=1}^{n}a_{i}(t)>0$ for all $t\in\mathcal{T}$.

######  Proposition 1 (as in [17])

Suppose Assumption 1 holds. Then the competitive equilibrium and the social
welfare equilibrium exist and coincide. Additionally, the optimal price
$\lambda^{\ast}_{t}$ in (1) is obtained from the Lagrange multiplier
associated with the balancing equality constraint $\sum_{i=1}^{n}e_{i}(t)=0$
in (3).

###  II-C Social Shaping Problem

The optimal price $\lambda^{\ast}_{t}$, which is the Lagrange multiplier
corresponding to the equality constraint in (3), depends on the utility
functions of agents. If there are no regulations on the choice of utility
functions, the price may become extremely high and unaffordable for some
agents. In this case, those who have found 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.
This is indeed socially unfair and not sustainable. So we need a mechanism,
called social shaping, which ensures the price is always below an acceptable
threshold denoted by $\lambda^{\dagger}\in\mathbb{R}^{>0}$. The problem of
social shaping is addressed for static MAS in [22] and [23]. Now, we define an
extended version of the social shaping problem for dynamic MAS as follows.

######  Definition 3 (Social shaping for dynamic MAS)

Consider a dynamic MAS whose agents $i\in\mathcal{V}$ have
$f(\cdot;\theta_{i})$ and $\phi(\cdot;\theta_{i})$ as their running utility
function and terminal utility function, respectively. Let
$\lambda^{\dagger}\in\mathbb{R}^{>0}$ be the given price threshold accepted by
all agents. Find a range $\Theta$ of personal parameters $\theta_{i}$ such
that if $\theta_{i}\in\Theta$ for $i\in\mathcal{V}$, or
$(\theta_{1},\dots,\theta_{n})\in\Theta^{n}$, then we yield
$\lambda_{t}^{\ast}\leq\lambda^{\dagger}$ at all time steps $t\in\mathcal{T}$.

##  III Conceptual Social Shaping

In this section, we examine how the social shaping problem of dynamic MAS can
be solved conceptually.

###### Lemma 1

Consider the dynamic MAS. If Assumption 1 is satisfied, then
$\lambda^{\ast}_{t}\geq 0$ for all $t\in\mathcal{T}$.

###### Proof:

The proof is similar to the proof of Proposition 2 in [17]. ∎

###### Proposition 2

Consider the dynamic MAS. Let Assumption 1 hold. If $\lambda^{\ast}_{t}>0$
then the total demand and supply are balanced at time step $t$; that is,

$\sum_{i=1}^{n}h_{i}(\mathbf{u}_{i}^{\ast}(t))=C(t).$ (4)

###### Proof:

Since Assumption 1 is satisfied, Proposition 1 holds. Therefore, either the
competitive problem or the social welfare problem can be solved. Consider the
competitive optimization problem in (1). Let $s_{i}(t)\in\mathbb{R}^{\geq 0}$
be the slack variable for agent $i$ at time step $t\in\mathcal{T}$ and
$\mathbf{S_{i}}=(s_{i}(0),...,s_{i}(N-1))^{\top}$ be the vector of slack
variables for agent $i$ throughout the whole time horizon. We can write the
inequality constraint $e_{i}(t)\leq a_{i}(t)-h_{i}(\mathbf{u}_{i}(t))$ in (1)
as the equality $e_{i}(t)=a_{i}(t)-h_{i}(\mathbf{u}_{i}(t))-s_{i}(t)$ for
$t\in\mathcal{T}$. Then, substituting
$e_{i}(t)=a_{i}(t)-h_{i}(\mathbf{u}_{i}(t))-s_{i}(t)$ into (1) results in an
equivalent form for the optimization problem as

$\displaystyle\max_{{\mathbf{U}}_{i},{\mathbf{S}}_{i}}$
$\displaystyle\phi(\mathbf{x}_{i}(N);\theta_{i})+\sum_{t=0}^{N-1}f(\mathbf{x}_{i}(t),\mathbf{u}_{i}(t);\theta_{i})$
(5)
$\displaystyle+\sum_{t=0}^{N-1}\lambda_{t}^{\ast}\big{[}a_{i}(t)-h_{i}(\mathbf{u}_{i}(t))-s_{i}(t)\big{]}$
$\displaystyle{\rm s.t.}$
$\displaystyle\mathbf{x}_{i}(t+1)=\mathbf{A}_{i}\mathbf{x}_{i}(t)+\mathbf{B}_{i}\mathbf{u}_{i}(t),$
$\displaystyle s_{i}(t)\in\mathbb{R}^{\geq 0},\quad t\in\mathcal{T}.$

Since $\lambda^{\ast}_{t}>0$, the resulting objective function is strictly
decreasing with respect to $s_{i}(t)$. Consequently, the optimal slack
variable maximizing the objective function is $s_{i}^{\ast}(t)=0$, meaning
that the associated inequality constraint is active; that is,

$e_{i}^{\ast}(t)=a_{i}(t)-h_{i}(\mathbf{u}^{\ast}_{i}(t)).$ (6)

The summation of (6) over $i$, from $1$ to $n$, along with the balancing
equality $\sum_{i=1}^{n}e_{i}^{\ast}(t)=0$ in (2), yields
$\sum_{i=1}^{n}h_{i}(\mathbf{u}^{\ast}_{i}(t))=C(t)$. ∎

Now, let us work out how the social shaping problem can be solved
conceptually. Suppose Assumption 1 holds and $f(\cdot;\theta_{i})$,
$\phi(\cdot;\theta_{i})$, and $h_{i}(\cdot)$ are continuously differentiable.
Then Proposition 1 is satisfied. In this paper, we focus on the competitive
optimization problem in (1). According to Lemma 1, there holds
$\lambda^{\ast}_{t}\geq 0$. We can skip the case $\lambda_{t}^{\ast}=0$,
because a zero price is always socially resilient. Therefore, it is sufficient
to only examine $\lambda^{\ast}_{t}>0$. Following from Proposition 2, the
total demand and supply are balanced at time step $t$, meaning that
$\sum_{i=1}^{n}h_{i}(\mathbf{u}_{i}^{\ast}(t))=C(t)$; additionally, we have
$s_{i}^{\ast}(t)=0$. Substituting $s_{i}(t)=0$ into (5) yields an equivalent
form for the competitive optimization problem in (1) as

$\displaystyle\max_{{\mathbf{U}}_{i}}$
$\displaystyle\phi(\mathbf{x}_{i}(N);\theta_{i})+\sum_{t=0}^{N-1}f(\mathbf{x}_{i}(t),\mathbf{u}_{i}(t);\theta_{i})$
(7)
$\displaystyle+\sum_{t=0}^{N-1}\lambda_{t}^{\ast}\big{[}a_{i}(t)-h_{i}(\mathbf{u}_{i}(t))\big{]}$
$\displaystyle{\rm s.t.}$
$\displaystyle\mathbf{x}_{i}(t+1)=\mathbf{A}_{i}\mathbf{x}_{i}(t)+\mathbf{B}_{i}\mathbf{u}_{i}(t),\quad
t\in\mathcal{T},$

which is valid for $\lambda^{\ast}_{t}>0$. Please note that even if
$\lambda^{\ast}_{t}=0$ then (5) can be written in the form of (7), although
the equality in (4) turns into the inequality
$\sum_{i=1}^{n}h_{i}(\mathbf{u}^{\ast}_{i}(t))\leq C(t)$. This fact causes no
change to the upcoming analysis. The optimization problem in (7) is in essence
an unconstrained optimal control problem which can be solved by the dynamic
programming approach. First, introduce the cost-to-go function for agent $i$
from time $k$ to $N$ as

$\begin{aligned} &J_{i}^{k\longrightarrow
N}(\mathbf{x}_{i}(k),\mathbf{u}_{i}(k),\dots,\mathbf{u}_{i}(N-1),\lambda^{\ast}_{k},\dots,\lambda^{\ast}_{N-1};\theta_{i})\\\
&=\phi(\mathbf{x}_{i}(N);\theta_{i})+\sum_{t=k}^{N-1}\Big{(}f(\mathbf{x}_{i}(t),\mathbf{u}_{i}(t);\theta_{i})+\lambda_{t}^{\ast}\big{[}a_{i}(t)-h_{i}(\mathbf{u}_{i}(t))\big{]}\Big{)}.\end{aligned}$

Then, the optimal cost-to-go at time $k$ for agent $i$, which is also called
the value function, is represented as

$\begin{aligned}
&V_{i,k}(\mathbf{x}_{i}(k),\lambda^{\ast}_{k},\dots,\lambda^{\ast}_{N-1};\theta_{i})\\\
&=\max_{\mathbf{u}_{i}(k),\dots,\mathbf{u}_{i}(N-1)}\quad
J_{i}^{k\longrightarrow
N}(\mathbf{x}_{i}(k),\mathbf{u}_{i}(k),\dots,\mathbf{u}_{i}(N-1),\lambda^{\ast}_{k},\dots,\lambda^{\ast}_{N-1};\theta_{i})\\\
&\quad\quad\quad\quad{\rm
s.t.}\,\,\,\quad\quad\quad\mathbf{x}_{i}(t+1)=\mathbf{A}_{i}\mathbf{x}_{i}(t)+\mathbf{B}_{i}\mathbf{u}_{i}(t),\quad
t=k,\dots,N-1.\end{aligned}$

Now, we go one step backward in time. According to the principle of
optimality, the optimal cost-to-go from time $k-1$ to $N$ is obtained by
optimizing the sum of the running cost at time $k-1$ and the value function at
time $k$; that is,

$\begin{aligned}
&V_{i,k-1}(\mathbf{x}_{i}(k-1),\lambda^{\ast}_{k-1},\dots,\lambda^{\ast}_{N-1};\theta_{i})\\\
&=\max_{\mathbf{u}_{i}(k-1)}\quad
f(\mathbf{x}_{i}(k-1),\mathbf{u}_{i}(k-1);\theta_{i})+\lambda_{k-1}^{\ast}\big{[}a_{i}(k-1)-h_{i}\big{(}\mathbf{u}_{i}(k-1)\big{)}\big{]}\\\
&\quad\quad\quad\quad\quad+V_{i,k}(\mathbf{x}_{i}(k),\lambda^{\ast}_{k},\dots,\lambda^{\ast}_{N-1};\theta_{i})\\\
&\quad\quad\,\,\,{\rm
s.t.}\quad\,\,\,\mathbf{x}_{i}(k)=\mathbf{A}_{i}\mathbf{x}_{i}(k-1)+\mathbf{B}_{i}\mathbf{u}_{i}(k-1).\end{aligned}$

(8)

Based on the system dynamics, $\mathbf{x}_{i}(k)$ depends on
$\mathbf{x}_{i}(k-1)$ and $\mathbf{u}_{i}(k-1)$. Consequently, the only
decision variable in (8) is $\mathbf{u}_{i}(k-1)$. The resulting value
function depends on $\mathbf{x}_{i}(k-1)$ and $\lambda^{\ast}_{t}$ where
$t=k-1,\dots,N-1$. Now, let us start with the final time $k=N$. The terminal
value function is

$\displaystyle
V_{i,N}(\mathbf{x}_{i}(N);\theta_{i})=\phi\big{(}\mathbf{x}_{i}(N);\theta_{i}\big{)}.$

Moving backward in time and substituting
$\mathbf{x}_{i}(k)=\mathbf{A}_{i}\mathbf{x}_{i}(k-1)+\mathbf{B}_{i}\mathbf{u}_{i}(k-1)$
into the cost function, we obtain

$\displaystyle V_{i,N-1}(\mathbf{x}_{i}(N-1),\lambda^{\ast}_{N-1};\theta_{i})$
$\displaystyle=\max_{\mathbf{u}_{i}(N-1)}\quad
f(\mathbf{x}_{i}(N-1),\mathbf{u}_{i}(N-1);\theta_{i})$
$\displaystyle\quad\quad\quad\quad\quad+\lambda_{N-1}^{\ast}\big{[}a_{i}(N-1)-h_{i}\big{(}\mathbf{u}_{i}(N-1)\big{)}\big{]}$
$\displaystyle\quad\quad\quad\quad\quad+V_{i,N}(\mathbf{A}_{i}\mathbf{x}_{i}(N-1)+\mathbf{B}_{i}\mathbf{u}_{i}(N-1);\theta_{i}),$
$\displaystyle\vdots$ $\displaystyle
V_{i,0}(\mathbf{x}_{i}(0),\lambda_{0}^{\ast},\dots,\lambda_{N-1}^{\ast};\theta_{i})$
$\displaystyle=\max_{\mathbf{u}_{i}(0)}\quad
f(\mathbf{x}_{i}(0),\mathbf{u}_{i}(0);\theta_{i})+\lambda_{0}^{\ast}\big{[}a_{i}(0)-h_{i}\big{(}\mathbf{u}_{i}(0)\big{)}\big{]}$
$\displaystyle\quad\quad\quad\quad\quad+V_{i,1}(\mathbf{A}_{i}\mathbf{x}_{i}(0)+\mathbf{B}_{i}\mathbf{u}_{i}(0),\lambda_{1}^{\ast},\dots,\lambda_{N-1}^{\ast};\theta_{i}).$

To obtain the optimal control at time step $k=0$, the derivative of the
associated objective function with respect to $\mathbf{u}_{i}(0)$ must equal
zero; that is,

$\frac{\partial
f(\mathbf{x}_{i}(0),\mathbf{u}_{i}(0);\theta_{i})}{\partial\mathbf{u}_{i}(0)}-\lambda_{0}^{\ast}\nabla
h_{i}\big{(}\mathbf{u}_{i}(0)\big{)}\\\ +\frac{\partial
V_{i,1}(\mathbf{A}_{i}\mathbf{x}_{i}(0)+\mathbf{B}_{i}\mathbf{u}_{i}(0),\lambda_{1}^{\ast},\dots,\lambda_{N-1}^{\ast};\theta_{i})}{\partial\mathbf{u}_{i}(0)}=0.$

Proposition 1 implies that such an optimal solution exists, although it might
not be unique. Without loss of generality, suppose the optimal solution is
unique. Thus, we can write $\mathbf{u}_{i}^{\ast}(0)$ as a function of
$\mathbf{x}_{i}(0)$ and all $\lambda^{\ast}_{t}$ where $t\in\mathcal{T}$,
parameterized by $\theta_{i}$; that is,

$\mathbf{u}_{i}^{\ast}(0)=l_{i}^{0}(\mathbf{x}_{i}(0),\lambda_{0}^{\ast},\dots,\lambda_{N-1}^{\ast};\theta_{i}).$
(9)

Substituting (9) into the equality
$\sum_{i=1}^{n}h_{i}(\mathbf{u}_{i}^{\ast}(t))=C(t)$ in (4), we yield

$\sum_{i=1}^{n}h_{i}(l_{i}^{0}(\mathbf{x}_{i}(0),\lambda_{0}^{\ast},\dots,\lambda_{N-1}^{\ast};\theta_{i}))=C(0).$

Similarly, for any other time step $k\in\mathcal{T}$ we achieve

$\mathbf{u}_{i}^{\ast}(k)=l_{i}^{k}(\mathbf{x}_{i}(0),\lambda^{\ast}_{0},\dots,\lambda_{N-1}^{\ast};\theta_{i}),\,\,\,\,k\in\mathcal{T},$

and

$\sum_{i=1}^{n}h_{i}(l_{i}^{k}(\mathbf{x}_{i}(0),\lambda^{\ast}_{0},\dots,\lambda_{N-1}^{\ast};\theta_{i}))=C(k),\,\,\,\,k\in\mathcal{T}.$
(10)

We aim to obtain
$\bm{\lambda^{\ast}}=(\lambda^{\ast}_{0},\dots,\lambda^{\ast}_{N-1})^{\top}$.
According to (10), we have $N$ equations with $N$ variables. Let
$\mathbf{x}(k)=(\mathbf{x}^{\top}_{1}(k),\dots,\mathbf{x}^{\top}_{n}(k))^{\top}$,
$\bm{\theta}=(\theta_{1},\theta_{2},\dots,\theta_{n})$, and
$\mathbf{C}=(C(0),C(1),\dots,C(N-1))$. According to Proposition 1, there
exists $\bm{\lambda}^{\ast}$ which satisfies (10) although it might not be
unique. Among different possible prices that satisfy the equilibrium, we
consider the maximum one at each time step. In the rest of this paper, by
optimal price we mean the maximum possible price associated with a fixed
$\bm{\theta}$ meeting the equilibrium conditions. Solving (10), the optimal
price at each time step $k\in\mathcal{T}$ is obtained as

$\lambda^{\ast}_{k}=g_{k}(\mathbf{x}(0),\mathbf{C};\bm{\theta}),\quad
k=0,\dots,N-1.$

Additionally, for different values of agent preferences $\bm{\theta}$ we would
obtain different optimal prices at each time step. Let us define the maximum
value of the set of all possible optimal prices at each time step $k$, when
$\theta_{i}$ takes values in the set $\Theta$ (or $\bm{\theta}\in\Theta^{n}$),
as

$\chi^{\Theta}_{k}:=\max_{\bm{\theta}\in\Theta^{n}}g_{k}(\cdot;\bm{\theta}),\quad
k=0,\dots,N-1.$

Next, we introduce

$\mathbf{G}_{\Theta}:=\big{(}\chi^{\Theta}_{0},\chi^{\Theta}_{1},\dots,\chi^{\Theta}_{N-1}\big{)}^{\top}.$

Each element $k$ in the vector $\mathbf{G}_{\Theta}$ is the maximum value of
optimal prices at time step $k$, when agent preferences are taken from
$\bm{\theta}\in\Theta^{n}$. This leads to the following result.

###### Theorem 1

Consider a dynamic MAS. Let Assumption 1 hold. Suppose $f(\cdot;\theta_{i})$,
$\phi(\cdot;\theta_{i})$, and $h_{i}(\cdot)$ are continuously differentiable.
Let $\lambda^{\dagger}\in\mathbb{R}^{>0}$ represent the given price threshold
accepted by all agents. Then any set $\Theta$ satisfying
$\mathbf{G}_{\Theta}\leq\lambda^{\dagger}\mathbb{1}$ ensures that
$\lambda^{\ast}_{t}\leq\lambda^{\dagger}$ for $t\in\mathcal{T}$, and thus,
solves the social shaping problem of agent preferences.

##  IV Quadratic Social Shaping

In this section, we examine quadratic utility functions for dynamic MAS and
explicitly propose two sets of personal parameters which guarantee that the
optimal prices at all time steps are socially resilient.

###### Assumption 2

Consider the dynamic MAS introduced in Section II-A. Let
$\theta_{i}:=(\mathbf{Q}_{i},\mathbf{R}_{i})$, where
$\mathbf{Q}_{i}\in\mathbb{R}^{d\times d}$,
$\mathbf{Q}_{i}=\mathbf{Q}_{i}^{\top}>0$ and
$\mathbf{R}_{i}\in\mathbb{R}^{m\times m}$,
$\mathbf{R}_{i}=\mathbf{R}_{i}^{\top}>0$. Assume for all $i\in\mathcal{V}$ we
have

$\begin{gathered}\begin{aligned}
f(\mathbf{x}_{i}(t),\mathbf{u}_{i}(t);\theta_{i})&=-\mathbf{x}_{i}^{\top}(t)\mathbf{Q}_{i}\mathbf{x}_{i}(t)-\mathbf{u}_{i}^{\top}(t)\mathbf{R}_{i}\mathbf{u}_{i}(t),\\\
\phi(\mathbf{x}_{i}(N);\theta_{i})&=-\mathbf{x}_{i}^{\top}(N)\mathbf{Q}_{i}\mathbf{x}_{i}(N),\\\
h_{i}(\mathbf{u}_{i}(t))&=\mathbf{u}_{i}^{\top}(t)\mathbf{H}_{i}\mathbf{u}_{i}(t),\end{aligned}\end{gathered}$

where $\mathbf{H}_{i}\in\mathbb{R}^{m\times m}$,
$\mathbf{H}_{i}=\mathbf{H}_{i}^{\top}>0$.

###### Assumption 3

Consider the dynamic MAS in Assumption 2 with a given initial state
$\mathbf{x}_{i}(0)$ such that
$\left\|{{\mathbf{x}_{i}}(0)}\right\|\leq\gamma$,
$\left\|\mathbf{A}_{i}\right\|\leq\alpha$,
$\left\|\mathbf{B}_{i}\right\|\leq\beta$, and
$\mathbf{H}_{i}\geq\rho\mathbf{I}$ for $i\in\mathcal{V}$. Suppose that
$\gamma,\alpha,\beta,\rho\in\mathbb{R}^{>0}$.

We aim to solve the following social shaping problem.

Dynamic & Quadratic Social Shaping Problem. Suppose Assumptions 2 and 3 hold.
Let $\lambda^{\dagger}\in\mathbb{R}^{>0}$ be the given price threshold
accepted by all agents, and $\delta_{\rm max}\in\mathbb{R}^{>0}$ be an upper
bound for the norm of the personal parameter $\mathbf{Q}_{i}$. We propose an
admissible set for $\delta_{\rm max}$ such that all utility functions
satisfying $\left\|\mathbf{Q}_{i}\right\|\leq\delta_{\rm max}$ (or
$\mathbf{Q}_{i}\leq\delta_{\rm max}\mathbf{I}$) lead to socially acceptable
energy prices at all time steps; i.e.,
$\lambda^{\ast}_{t}\leq\lambda^{\dagger}$ for $t\in\mathcal{T}$.

To address this problem, we use two approaches: quadratic programming and
dynamic programming.

###  IV-A Quadratic Programming Approach

Since Assumption 2 is satisfied, Proposition 1 holds. We examine the
competitive optimization problem in (1). According to Lemma 1, there holds
$\lambda^{\ast}_{t}\geq 0$. We skip the case $\lambda_{t}^{\ast}=0$, because a
zero price is always socially resilient. Hence, it is sufficient to only study
$\lambda^{\ast}_{t}>0$. According to (7), the optimization problem in (1) can
be reformulated as

$\displaystyle\max_{{\mathbf{U}}_{i}}$
$\displaystyle-\mathbf{x}_{i}^{\top}(N)\mathbf{Q}_{i}\mathbf{x}_{i}(N)+\sum_{t=0}^{N-1}\big{[}\big{.}-\mathbf{x}_{i}^{\top}(t)\mathbf{Q}_{i}\mathbf{x}_{i}(t)$
(11)
$\displaystyle-\mathbf{u}_{i}^{\top}(t)\mathbf{R}_{i}\mathbf{u}_{i}(t)+\lambda_{t}^{\ast}\big{(}a_{i}(t)-\mathbf{u}_{i}^{\top}(t)\mathbf{H}_{i}\mathbf{u}_{i}(t)\big{)}\big{.}\big{]}$
$\displaystyle{\rm s.t.}$
$\displaystyle\mathbf{x}_{i}(t+1)=\mathbf{A}_{i}\mathbf{x}_{i}(t)+\mathbf{B}_{i}\mathbf{u}_{i}(t),\quad
t\in\mathcal{T}.$

###### Theorem 2

Consider the dynamic MAS described in Assumptions 2 and 3 on the time horizon
$N$. Suppose $\delta_{\rm max}\in\mathbb{R}^{>0}$ is selected from the
following set

$\displaystyle\mathscr{S}_{\ast}=\left\\{\Bigg{.}\right.\delta_{\rm
max}\in\mathbb{R}^{>0}:\delta_{\rm
max}\sum_{t=k+1}^{N}\Bigg{[}\Bigg{.}\gamma\alpha^{2t-k-1}$
$\displaystyle+\beta{\sum_{\begin{subarray}{c}j=0\\\ j\neq
k\end{subarray}}^{t-1}}\sqrt{\frac{C(j)}{\rho}}\alpha^{2t-j-k-2}\Bigg{.}\Bigg{]}\leq\frac{\sqrt{C(k)\rho}}{n\beta}\lambda^{\dagger}\,\,\,\,{\rm
for}\,\,\forall k\in\mathcal{T}\left.\Bigg{.}\right\\}.$

Then for all quadratic utility functions satisfying
$\left\|\mathbf{Q}_{i}\right\|\leq\delta_{\rm max}$ (or
$\mathbf{Q}_{i}\leq\delta_{\rm max}\mathbf{I}$), the resulting optimal price
is socially resilient, i.e.,
$\bm{\lambda}^{\ast}\leq\lambda^{\dagger}\mathbb{1}$.

###### Proof:

Considering the equality in (4), we obtain

$\sum_{i=1}^{n}\mathbf{u}_{i}^{\ast\top}(t)\mathbf{H}_{i}\mathbf{u}_{i}^{\ast}(t)=C(t),\quad
t\in\mathcal{T}.$ (12)

Furthermore, the following inequality holds

$\sigma_{\rm
min}(\mathbf{H}_{i})\left\|\mathbf{u}_{i}^{\ast}(t)\right\|^{2}\leq\mathbf{u}_{i}^{\ast\top}(t)\mathbf{H}_{i}\mathbf{u}_{i}^{\ast}(t),$
(13)

where $\sigma_{\rm min}(\mathbf{H}_{i})$ is the smallest eigenvalue of
$\mathbf{H}_{i}$. Additionally, since
$\mathbf{u}_{i}^{\ast\top}(t)\mathbf{H}_{i}\mathbf{u}_{i}^{\ast}(t)\geq 0$,
the equality in (12) yields
$\mathbf{u}_{i}^{\ast\top}(t)\mathbf{H}_{i}\mathbf{u}_{i}^{\ast}(t)\leq C(t).$
Following from (13), we obtain

$\sigma_{\rm
min}(\mathbf{H}_{i})\left\|\mathbf{u}_{i}^{\ast}(t)\right\|^{2}\leq C(t).$
(14)

According to Assumption 3, we have $\mathbf{H}_{i}\geq\rho I$, meaning that
$\sigma_{\rm min}(\mathbf{H}_{i})\geq\rho$. Consequently, inequality (14)
results in

$\left\|\mathbf{u}_{i}^{\ast}(t)\right\|\leq\sqrt{\frac{C(t)}{\rho}}.$ (15)

Additionally, from the dynamical equation in (11), we obtain

$\mathbf{x}_{i}(t)=\mathbf{A}_{i}^{t}\mathbf{x}_{i}(0)+\sum_{j=0}^{t-1}{\mathbf{A}_{i}^{t-j-1}\mathbf{B}_{i}\mathbf{u}_{i}(j)},\quad
t\in\\{1,2,...,N\\}.$ (16)

Substituting (16) into (11) yields an unconstrained optimization problem, in
which the only decision variable is ${\mathbf{U}}_{i}$. The associated
objective function $J$ is

$\small\begin{split}&J:=\sum_{t=1}^{N}\Bigg{[}\Bigg{.}-\Bigg{(}\mathbf{A}_{i}^{t}\mathbf{x}_{i}(0)+\sum_{j=0}^{t-1}\mathbf{A}_{i}^{t-j-1}\mathbf{B}_{i}\mathbf{u}_{i}(j)\Bigg{)}^{\top}\mathbf{Q}_{i}\\\
&\times\Bigg{(}\mathbf{A}_{i}^{t}\mathbf{x}_{i}(0)+\sum_{j=0}^{t-1}\mathbf{A}_{i}^{t-j-1}\mathbf{B}_{i}\mathbf{u}_{i}(j)\Bigg{)}\Bigg{.}\Bigg{]}-\mathbf{x}_{i}^{\top}(0)\mathbf{Q}_{i}\mathbf{x}_{i}(0)\\\
&+\sum_{t=0}^{N-1}\Bigg{[}\Bigg{.}-\mathbf{u}_{i}^{\top}(t)\mathbf{R}_{i}\mathbf{u}_{i}(t)+\lambda_{t}^{\ast}\Bigg{(}a_{i}(t)-\mathbf{u}_{i}^{\top}(t)\mathbf{H}_{i}\mathbf{u}_{i}(t)\Bigg{)}\Bigg{.}\Bigg{]}.\end{split}$

Let $k$ denote a time interval indexed in $\mathcal{T}$. Let $\frac{\partial
J}{\partial\mathbf{u}_{i}(k)}=0$, which yields

$\lambda^{\ast}_{k}\mathbf{H}_{i}\mathbf{u}_{i}(k)=-\sum_{t=k+1}^{N}\Bigg{[}\Bigg{.}\Bigg{(}\mathbf{A}_{i}^{t-k-1}\mathbf{B}_{i}\Bigg{)}^{\top}\mathbf{Q}_{i}\\\
\times\Bigg{(}\mathbf{A}_{i}^{t}\mathbf{x}_{i}(0)+\sum_{j=0}^{t-1}\mathbf{A}_{i}^{t-j-1}\mathbf{B}_{i}\mathbf{u}_{i}(j)\Bigg{)}\Bigg{.}\Bigg{]}-\mathbf{R}_{i}\mathbf{u}_{i}(k).$
(17)

Multiply (17) by $\mathbf{u}_{i}^{\top}(k)$ and then taking the summation over
$i$, where $i\in\\{1,\dots,n\\}$, we obtain

$\begin{gathered}\lambda^{\ast}_{k}\sum_{i=1}^{n}\mathbf{u}_{i}^{\top}(k)\mathbf{H}_{i}\mathbf{u}_{i}(k)=-\sum_{t=k+1}^{N}\Bigg{[}\sum_{i=1}^{n}\mathbf{u}_{i}^{\top}(k)\Bigg{.}\Bigg{(}\mathbf{A}_{i}^{t-k-1}\mathbf{B}_{i}\Bigg{)}^{\top}\mathbf{Q}_{i}\\\
\times\Bigg{(}\mathbf{A}_{i}^{t}\mathbf{x}_{i}(0)+\sum_{j=0}^{t-1}\mathbf{A}_{i}^{t-j-1}\mathbf{B}_{i}\mathbf{u}_{i}(j)\Bigg{)}\Bigg{.}\Bigg{]}-\sum_{i=1}^{n}\mathbf{u}_{i}^{\top}(k)\mathbf{R}_{i}\mathbf{u}_{i}(k).\end{gathered}$

(18)

Substitute
$\sum_{i=1}^{n}\mathbf{u}_{i}^{\top}(k)\mathbf{H}_{i}\mathbf{u}_{i}(k)=C(k)$
in (12) into (18), then

$\begin{aligned}
&\lambda^{\ast}_{k}=-\frac{1}{C(k)}\sum_{t=k+1}^{N}\Bigg{[}\sum_{i=1}^{n}\Bigg{.}\Bigg{(}\mathbf{A}_{i}^{t-k-1}\mathbf{B}_{i}\mathbf{u}_{i}(k)\Bigg{)}^{\top}\mathbf{Q}_{i}\Bigg{(}\mathbf{A}_{i}^{t}\mathbf{x}_{i}(0)\\\
&+\sum_{j=0}^{t-1}\mathbf{A}_{i}^{t-j-1}\mathbf{B}_{i}\mathbf{u}_{i}(j)\Bigg{)}\Bigg{.}\Bigg{]}-\frac{1}{C(k)}\sum_{i=1}^{n}\mathbf{u}_{i}^{\top}(k)\mathbf{R}_{i}\mathbf{u}_{i}(k).\end{aligned}$

(19)

Since $\mathbf{Q}_{i}>0$, we obtain

$-(\mathbf{A}_{i}^{t-k-1}\mathbf{B}_{i}\mathbf{u}_{i}(k))^{\top}\mathbf{Q}_{i}\mathbf{A}_{i}^{t-k-1}\mathbf{B}_{i}\mathbf{u}_{i}(k)\leq
0.$

Similarly, $\mathbf{R}_{i}>0$, and
$-\mathbf{u}_{i}^{\top}(k)\mathbf{R}_{i}\mathbf{u}_{i}(k)\leq 0$.

Next, we seek an upper bound for $\lambda^{\ast}_{k}$. First, let these two
terms equal zero. Then use Assumption 3 and the inequality in (15), and by
substitution into (19), we yield

$\lambda^{\ast}_{k}\leq\frac{1}{C(k)}\sum_{t=k+1}^{N}\Bigg{[}\Bigg{.}n\alpha^{2t-k-1}\beta\sqrt{\frac{C(k)}{\rho}}\delta_{\rm
max}\gamma\\\ +n\beta^{2}\sqrt{\frac{C(k)}{\rho}}\delta_{\rm
max}\sum_{\begin{subarray}{c}j=0\\\ j\neq
k\end{subarray}}^{t-1}\alpha^{2t-j-k-2}\sqrt{\frac{C(j)}{\rho}}\Bigg{.}\Bigg{]}.$
(20)

By assumption, the right-hand side of (20) is less than or equal to
$\lambda^{\dagger}$. Therefore, we obtain
$\lambda^{\ast}_{k}\leq\lambda^{\dagger}$. ∎

###  IV-B Dynamic Programming Approach

Similar to Section IV-A, we only consider $\lambda^{\ast}_{t}>0$ and we deal
with the optimization problem in (11) which is equivalent to

$\displaystyle\max_{{\mathbf{U}}_{i}}$
$\displaystyle-\mathbf{x}_{i}^{\top}(N)\mathbf{Q}_{i}\mathbf{x}_{i}(N)+\sum_{t=0}^{N-1}\big{[}\big{.}-\mathbf{x}_{i}^{\top}(t)\mathbf{Q}_{i}\mathbf{x}_{i}(t)$
(21)
$\displaystyle-\mathbf{u}_{i}^{\top}(t)\bigg{(}\mathbf{R}_{i}+\lambda^{\ast}_{t}\mathbf{H}_{i}\bigg{)}\mathbf{u}_{i}(t)+\lambda_{t}^{\ast}a_{i}(t)\big{.}\big{]}$
$\displaystyle{\rm s.t.}$
$\displaystyle\mathbf{x}_{i}(t+1)=\mathbf{A}_{i}\mathbf{x}_{i}(t)+\mathbf{B}_{i}\mathbf{u}_{i}(t),\quad
t\in\mathcal{T}.$

###### Theorem 3

Consider the dynamic MAS on the time horizon ${N}$. Let Assumptions 2 and 3
hold. Suppose $\delta_{\rm max}\in\mathbb{R}^{>0}$ is selected from the
following set

$\mathscr{S}_{\ast}=\left\\{\Bigg{.}\right.\delta_{\rm
max}\in\mathbb{R}^{>0}:\delta_{\rm
max}\sum_{t=1}^{N}\gamma\alpha^{2t-1}\leq\frac{\sqrt{C(0)\rho}}{n\beta}\lambda^{\dagger},\\\
\delta_{\rm
max}\sum_{t=k+1}^{N}\Bigg{[}\Bigg{.}\gamma\alpha^{2t-k-1}+\beta{\sum_{\begin{subarray}{c}j=0\end{subarray}}^{k-1}}\sqrt{\frac{C(j)}{\rho}}\alpha^{2t-j-k-2}\Bigg{.}\Bigg{]}\\\
\leq\frac{\sqrt{C(k)\rho}}{n\beta}\lambda^{\dagger}\,\,\,\,{\rm
for}\,\,\forall k\in\mathcal{T},k\neq 0\left.\Bigg{.}\right\\}.$

Then the resulting $\bm{\lambda}^{\ast}$ is socially resilient for all utility
functions satisfying $\left\|\mathbf{Q}_{i}\right\|\leq\delta_{\rm max}$ (or
$\mathbf{Q}_{i}\leq\delta_{\rm max}\mathbf{I}$).

###### Proof:

Similar to the previous section, (12) and (15) are satisfied. Since
$\lambda^{\ast}_{t}>0$, we obtain
$\mathbf{R}_{i}+\lambda^{\ast}_{t}\mathbf{H}_{i}>0$. Consequently, the
optimization problem in (21) is a _standard LQR problem_. Therefore, at each
time step $k\in\mathcal{T}$, the optimal control solution is obtained as

$\mathbf{u}_{i}^{\ast}(k)=-\big{(}\mathbf{B}_{i}^{\top}\mathbf{P}_{i,k+1}\mathbf{B}_{i}+(\mathbf{R}_{i}+\lambda^{\ast}_{k}\mathbf{H}_{i})\big{)}^{-1}\mathbf{B}_{i}^{\top}\mathbf{P}_{i,k+1}\mathbf{A}_{i}\mathbf{x}_{i}(k),$

where

$\mathbf{P}_{i,k}=\mathbf{A}_{i}^{\top}\mathbf{P}_{i,k+1}\mathbf{A}_{i}+\mathbf{Q}_{i}-\mathbf{A}_{i}^{\top}\mathbf{P}_{i,k+1}\mathbf{B}_{i}\big{(}\mathbf{B}_{i}^{\top}\mathbf{P}_{i,k+1}\mathbf{B}_{i}\\\
+(\mathbf{R}_{i}+\lambda^{\ast}_{k}\mathbf{H}_{i})\big{)}^{-1}\mathbf{B}_{i}^{\top}\mathbf{P}_{i,k+1}\mathbf{A}_{i}.$
(22)

The Riccati difference equation in (22) is initialized with
$\mathbf{P}_{i,N}=\mathbf{Q}_{i}$ and is solved backward from $k=N-1$ to
$k=0$. Additionally, since the last term on the right-hand side of (22) is
negative semi-definite (NSD), we obtain

$\mathbf{P}_{i,k}\leq\mathbf{A}_{i}^{\top}\mathbf{P}_{i,k+1}\mathbf{A}_{i}+\mathbf{Q}_{i},$

and therefore,

$\left\|\mathbf{P}_{i,k}\right\|\leq\alpha^{2}\left\|\mathbf{P}_{i,k+1}\right\|+\left\|\mathbf{Q}_{i}\right\|.$

Starting from $k=N-1$, we obtain

$\displaystyle\left\|\mathbf{P}_{i,N-1}\right\|\leq$
$\displaystyle(\alpha^{2}+1)\left\|\mathbf{Q}_{i}\right\|,$ (23)
$\displaystyle\vdots$ $\displaystyle\left\|\mathbf{P}_{i,N-p}\right\|\leq$
$\displaystyle(\alpha^{2p}+\alpha^{2(p-1)}+\dots+\alpha^{2}+1)\left\|\mathbf{Q}_{i}\right\|.$

On the other hand, to find the optimal control input, we start from $k=0$ and
proceed in a forward manner. In the first step, we get

$\mathbf{u}_{i}^{\ast}(0)=-\big{(}\mathbf{B}_{i}^{\top}\mathbf{P}_{i,1}\mathbf{B}_{i}+\mathbf{R}_{i}+\lambda^{\ast}_{0}\mathbf{H}_{i}\big{)}^{-1}\mathbf{B}_{i}^{\top}\mathbf{P}_{i,1}\mathbf{A}_{i}\mathbf{x}_{i}(0).$
(24)

Multiply (24) by
$\mathbf{u}_{i}^{\ast\top}(0)\big{(}\mathbf{B}_{i}^{\top}\mathbf{P}_{i,1}\mathbf{B}_{i}+\mathbf{R}_{i}+\lambda^{\ast}_{0}\mathbf{H}_{i}\big{)}$
and then taking the summation over $i$, where $i\in\\{1,\dots,n\\}$, we obtain

$\sum_{i=1}^{n}\mathbf{u}_{i}^{\ast\top}(0)\big{(}\mathbf{B}_{i}^{\top}\mathbf{P}_{i,1}\mathbf{B}_{i}+\mathbf{R}_{i}+\lambda^{\ast}_{0}\mathbf{H}_{i}\big{)}\mathbf{u}_{i}^{\ast}(0)\\\
=-\sum_{i=1}^{n}\mathbf{u}_{i}^{\ast\top}(0)\mathbf{B}_{i}^{\top}\mathbf{P}_{i,1}\mathbf{A}_{i}\mathbf{x}_{i}(0).$
(25)

Substitute (12) into (25), and yield

$\small\lambda_{0}^{\ast}=-\frac{1}{C(0)}\sum_{i=1}^{n}\mathbf{u}_{i}^{\ast\top}(0)\mathbf{B}_{i}^{\top}\mathbf{P}_{i,1}\mathbf{A}_{i}\mathbf{x}_{i}(0)\\\
-\frac{1}{C(0)}\sum_{i=1}^{n}\mathbf{u}_{i}^{\ast\top}(0)\big{(}\mathbf{B}_{i}^{\top}\mathbf{P}_{i,1}\mathbf{B}_{i}+\mathbf{R}_{i}\big{)}\mathbf{u}_{i}^{\ast}(0).$
(26)

To obtain an upper bound for $\lambda^{\ast}_{0}$, we can omit the second term
on the right-hand side of (26) which is always non-positive. Additionally,
using norm properties and considering Assumption 3 and the inequalities in
(15) and (23), we obtain

$\displaystyle\lambda_{0}^{\ast}$
$\displaystyle\leq\frac{n}{C(0)}\sqrt{\frac{C(0)}{\rho}}\beta\gamma\delta_{\rm
max}\sum_{t=1}^{N}\alpha^{2t-1}.$ (27)

Moving forward to the time step $k>0$, we obtain

$\lambda^{\ast}_{k}\leq\frac{n}{\sqrt{C(k)\rho}}\beta\delta_{\rm
max}\sum_{t=k+1}^{N}\Bigg{[}\Bigg{.}\gamma\alpha^{2t-k-1}\\\
+\beta\sum_{\begin{subarray}{c}j=0\end{subarray}}^{k-1}\sqrt{\frac{C(j)}{\rho}}\alpha^{2t-j-k-2}\Bigg{.}\Bigg{]}.$
(28)

By assumption, the right-hand side of (27) and (28) is less than or equal to
$\lambda^{\dagger}$, which confirms $\lambda^{\ast}_{k}\leq\lambda^{\dagger}$
for $k\in\mathcal{T}$. ∎

##  V Numerical Algorithm

The two proposed sets in Theorems 2 and 3 are conservative but they give a
concrete idea about how the trade-off between utility functions’ parameters
and the price threshold is achievable. To obtain more accurate and practical
results, we propose a numerical algorithm which provides less conservative
bounds on the parameters. This algorithm proceeds based on the bisection
method.

Numerical Social Shaping Problem. Consider the social welfare problem in (3).
Let $\delta_{\rm max}\in\mathbb{R}^{>0}$ be the designing parameter. Suppose
Assumption 2 holds with $\mathbf{Q}_{i}=q_{i}\mathbf{I}$ where agents have the
freedom to select $q_{i}\in\left(0,\delta_{\rm max}\right]$. Assume
$\lambda^{\dagger}$ is the given price threshold accepted by all agents and
$\mathbf{R}_{i}$ is specified for each $i\in\mathcal{V}$. We aim to find the
upper bound $\delta_{\rm max}$ by a numerical approach such that if
$q_{i}\in\left(0,\delta_{\rm max}\right]$ for $i\in\mathcal{V}$ then
$\lambda^{\ast}_{t}\leq\lambda^{\dagger}$ for $t\in\mathcal{T}$. The key steps
to reach this purpose are illustrated in Algorithm 1.

Input: System parameters $\mathbf{A}_{i}$, $\mathbf{B}_{i}$, and
$\mathbf{H}_{i}$, the initial state $\mathbf{x}_{i}(0)$, the time horizon $N$,
the penalty matrix $\mathbf{R}_{i}$, and the local supply $a_{i}(t)$ for
$i\in\mathcal{V}$ and $t\in\mathcal{T}$.

Structure: Consider $\mathbf{Q}_{i}=q_{i}\mathbf{I}$. Define
$\bar{\lambda}^{\ast}(\delta)=\max_{q_{1},\dots,q_{n}\in\left(0,\delta\right]}\max_{t\in\mathcal{T}}\lambda^{\ast}_{t}.$
(29)

Initialize: Set $k=0$, $b_{0}=0$, and $d_{0}=d_{\varrho}>0$ such that
$d_{\varrho}$ is sufficiently large to satisfy
$\bar{\lambda}^{\ast}(d_{\varrho})>\lambda^{\dagger}$.

while  _True_ do

$L_{k}=(b_{k}+d_{k})/2$, $\lambda_{k}=\bar{\lambda}^{\ast}(L_{k})$;

if  _$\lambda_{k} >\lambda^{\dagger}$_ then

$b_{k+1}=b_{k}$ and $d_{k+1}=L_{k}$;

$k=k+1$;

else if  _$\lambda_{k} <\lambda^{\dagger}$_ then

$b_{k+1}=L_{k}$ and $d_{k+1}=d_{k}$;

$k=k+1$;

else

$\delta_{\rm max}=L_{k}$;

break

end if

end while

Output: $\delta_{\rm max}=L_{k}$ if the algorithm stops after a finite number
of steps. Otherwise, $\delta_{\rm max}=\lim_{k\rightarrow\infty}L_{k}$.

Algorithm 1 Bisection-Based Social Shaping

###### Lemma 2

The function $\bar{\lambda}^{\ast}(\delta)$ in (29) is monotonically
increasing.

###### Proof:

When $\delta$ increases, the domain of agents’ preferences expands
respectively. Therefore, the maximum possible price can never decrease. ∎

###### Theorem 4

The auxiliary variable $L_{k}$ in Algorithm 1 converges to $L^{\ast}$ for some
$L^{\ast}\in\left(0,d_{\varrho}\right)$ when $k\rightarrow\infty$.

###### Proof:

From the update rules in Algorithm 1, we obtain

$b_{k+1}\geq b_{k},\quad\quad d_{k+1}\leq d_{k},$ (30)

and

$b_{0}\leq b_{k}<L_{k}<d_{k}\leq d_{0}.$ (31)

Inequalities in (30) and (31) imply that $b_{k}$ is monotonically increasing
and bounded above by $d_{0}=d_{\varrho}$. Similarly, $d_{k}$ is monotonically
decreasing and bounded below by $b_{0}=0$. Consequently, $b_{k}$ and $d_{k}$
converge when $k\rightarrow\infty$.

Additionally, from the algorithmic steps, we obtain

$|b_{k}-d_{k}|=0.5^{k}d_{\varrho}.$

Therefore,

$\lim_{k\rightarrow\infty}|b_{k}-d_{k}|=0.$ (32)

Considering (30), (31), and (32), we conclude

$\lim_{k\rightarrow\infty}b_{k}=\lim_{k\rightarrow\infty}d_{k}=\lim_{k\rightarrow\infty}L_{k}=L^{\ast},$
(33)

where $b_{k}<L^{\ast}<d_{k}$ at each iteration, and
$L^{\ast}\in\left(0,d_{\varrho}\right)$. ∎

###### Theorem 5

Suppose there exists $\delta^{\dagger}>0$ such that
$\bar{\lambda}^{\ast}(\delta^{\dagger})=\lambda^{\dagger}$. Then $\delta_{\rm
max}$ obtained from Algorithm 1 satisfies $\bar{\lambda}^{\ast}(\delta_{\rm
max})=\lambda^{\dagger}$.

###### Proof:

If the algorithm stops when $\lambda_{k}=\lambda^{\dagger}$, we end with
$\delta_{\rm max}=L_{k}$ and $\bar{\lambda}^{\ast}(\delta_{\rm
max})=\lambda^{\dagger}$. Otherwise, we obtain $\delta_{\rm
max}=\lim_{k\rightarrow\infty}L_{k}=L^{\ast}$. By contradiction, suppose
$\bar{\lambda}^{\ast}(L^{\ast})\neq\lambda^{\dagger}$ leading to
$L^{\ast}\neq\delta^{\dagger}$. First, consider $L^{\ast}<\delta^{\dagger}$.
According to (33), we obtain

$\exists\,l>0\quad{\rm s.t.}\quad d_{k}<\delta^{\dagger}\quad{\rm
for}\quad\forall\,k\geq l.$

Following Lemma 2, we obtain
$\bar{\lambda}^{\ast}(d_{k})\leq\bar{\lambda}^{\ast}(\delta^{\dagger})=\lambda^{\dagger}$,
which contradicts the assumptions in Algorithm 1. On the other hand, if
$L^{\ast}>\delta^{\dagger}$, a similar analysis can be made for $b_{k}$ which
leads to a contradiction. Consequently, it follows that
$\bar{\lambda}^{\ast}(L^{\ast})=\bar{\lambda}^{\ast}(\delta_{\rm
max})=\lambda^{\dagger}$. ∎

##  VI Simulation Results

###### Example 1

Consider a dynamic MAS with $3$ agents who satisfy Assumptions 2 and 3 in the
time horizon $N=6$, with the system parameters which are selected as

$\displaystyle{\mathbf{A}_{1}}=\left[{\begin{array}[]{*{20}{c}}{-0.6}&{-0.1}&{0.2}\\\
{0.3}&{-0.7}&{0.2}\\\
{0.2}&{-0.3}&{0.8}\end{array}}\right],\,{\mathbf{B}_{1}}=\left[{\begin{array}[]{*{20}{c}}2&1\\\
1&7\\\ 1&6\end{array}}\right],$
$\displaystyle{\mathbf{A}_{2}}=\left[{\begin{array}[]{*{20}{c}}{0.5}&{0.1}&{-0.1}\\\
{0.3}&{-0.2}&{-0.2}\\\
{-0.2}&{0.3}&{-0.3}\end{array}}\right],\,{\mathbf{B}_{2}}=\left[{\begin{array}[]{*{20}{c}}4&1\\\
1&6\\\ 3&4\end{array}}\right],$
$\displaystyle{\mathbf{A}_{3}}=\left[{\begin{array}[]{*{20}{c}}{-0.4}&{0.2}&{0.2}\\\
{-0.3}&{0.8}&{0.2}\\\
{0.2}&{0.3}&{-0.5}\end{array}}\right],\,{\mathbf{B}_{3}}=\left[{\begin{array}[]{*{20}{c}}9&2\\\
2&3\\\ 4&5\end{array}}\right],$

and the initial states

$\small{\mathbf{x}_{1}}(0)=\left[{\begin{array}[]{*{20}{c}}{10}\\\ {40}\\\
{70}\end{array}}\right],\,{\mathbf{x}_{2}}(0)=\left[{\begin{array}[]{*{20}{c}}{20}\\\
{50}\\\
{80}\end{array}}\right],\,{\mathbf{x}_{3}}(0)=\left[{\begin{array}[]{*{20}{c}}{30}\\\
{60}\\\ {90}\end{array}}\right].$

Additionally, suppose agents have the representative local resources
$a_{1}(t)=\sin(\frac{\pi}{6}t)+1.2$, $a_{2}(t)=2\sin(\frac{\pi}{6}t)+2.2$, and
$a_{3}(t)=0$. The total network generation is obtained as
$C(t)=\sum_{i=1}^{3}a_{i}(t)=3\sin(\frac{\pi}{6}t)+3.4$ and depicted in Fig.
1.

Figure 1: The network generation $C(t)$ over time steps.

Also, let $\lambda^{\dagger}=30$,
$\mathbf{R}_{1}=\mathbf{R}_{2}=\mathbf{R}_{3}=0.05\mathbf{I}$, and

$\small\begin{split}{\mathbf{H}_{1}}=\left[{\begin{array}[]{*{20}{c}}5&1\\\
1&8\end{array}}\right],\,{\mathbf{H}_{2}}=\left[{\begin{array}[]{*{20}{c}}3&2\\\
2&7\end{array}}\right],\,{\mathbf{H}_{3}}=\left[{\begin{array}[]{*{20}{c}}2&{-1}\\\
{-1}&1\end{array}}\right].\end{split}$

We aim to design $\mathbf{Q}_{i}$ for $i\in\mathcal{V}$ such that
$\lambda^{\ast}_{t}\leq\lambda^{\dagger}$ at all time steps.

Analytical approach: For this example, the upper bound $\delta_{\rm max}$ of
the personalized parameter $\mathbf{Q}_{i}$ is obtained from Theorems 2 and 3
as $0.00055$ and $0.0010$, respectively. We observe that Theorem 3 provides a
larger upper bound compared to Theorem 2 so we assign $\delta_{\rm
max}=0.001$. Next, we must select $\mathbf{Q}_{i}$ such that
$\left\|\mathbf{Q}_{i}\right\|\leq\delta_{\rm max}$ (or
$\mathbf{Q}_{i}\leq\delta_{\rm max}\mathbf{I}$) for $i\in\mathcal{V}$. Let us
carefully choose
$\mathbf{Q}_{1}=\mathbf{Q}_{2}=\mathbf{Q}_{3}=0.001\mathbf{I}$. The optimal
prices obtained from solving the social welfare problem in (3) are depicted in
Fig. 2(a) at different time steps.

(a) $\delta_{\rm max}=0.001$, obtained from Theorem 3.

(b) $\delta_{\rm max}=0.202$, obtained from Algorithm 1.

Figure 2: The optimal price $\lambda^{\ast}_{t}$ over time steps.

As indicated, the optimal prices are much less than $30$, and therefore,
socially resilient; this confirms that Theorems 2 and 3 are valid but they
provide conservative results.

Numerical approach: On the other hand, we run Algorithm 1 for 20 steps with
the choice of $d_{\varrho}=1$. This value of $d_{\varrho}$ is sufficiently
large that satisfies
$\bar{\lambda}^{\ast}(d_{\varrho})=148.6>\lambda^{\dagger}$. The output of the
algorithm is $\delta_{\rm max}=0.202$. Setting
$\mathbf{Q}_{1}=\mathbf{Q}_{2}=\mathbf{Q}_{3}=0.202\mathbf{I}$, the obtained
optimal prices are as Fig. 2(b), which are less than or equal to $30$ and
socially resilient. The maximum value of the price throughout the entire time
horizon is $\lambda^{\ast}_{1}=30.0$ happening at time step $t=1$. If we
select $\mathbf{Q}_{i}=q_{i}\mathbf{I}$ such that $q_{i}>0.202$ for
$i\in\mathcal{V}$, then we obtain $\lambda^{\ast}_{1}>30$, which is not
socially acceptable. This shows the proposed numerical algorithm works well in
practice.

##  VII CONCLUSIONS AND FUTURE WORKS

In this paper, we have studied the issue of social shaping for dynamic MAS
over finite horizons. The system under consideration was a self-sustained
dynamic MAS with distributed resource allocations operating at a competitive
equilibrium. We presented a conceptual scheme which shows how the social
shaping problem is solvable implicitly under some convexity assumptions. As a
typical case in the literature, we examined quadratic MAS. Dealing with an LQR
problem using quadratic programming and dynamic programming, we proposed two
sets of quadratic utility functions under which the resource pricing at the
competitive equilibrium is guaranteed to be socially acceptable, i.e., below a
prescribed threshold. Finally, we presented a numerical algorithm which
provides more accurate bounds on the agents’ preferences compared to the
proposed analytical sets. As future work, it is suggested to extend the
results to the infinite horizon case and consider network constraints in the
framework.

## References

  * [1] J. Zhang and C. Xia, “Structured multi-agent-based model for bankruptcy contagion with cash flow,” in IEEE Access, vol. 8, pp. 171716–171729, 2020.
  * [2] R. R. Negenborn, P. J. van Overloop, T. Keviczky, and B. De Schutter, “Distributed model predictive control of irrigation canals,” Netw. Heterogeneous Media, vol. 4, no. 2, pp. 359–380, 2009.
  * [3] J. B. Narciso de Sousa, Z. Kokkinogenis, and R. J. Rossetti, “Carbon market multi-agent simulation model,” in EPIA Conference on Artificial Intelligence, pp. 661–672, 2021.
  * [4] R. Cheng, M. J. Khojasteh, A. D. Ames, and J. W. Burdick, “Safe multi-agent interaction through robust control barrier functions with learned uncertainties,” in Proc. 59th IEEE Conference on Decision and Control (CDC), 2020, pp. 777–783.
  * [5] A. Falsone, K. Margellos, J. Zizzo, M. Prandini, and S. Garatti, “New results on resource sharing problems with random agent arrivals and an application to economic dispatch in power systems,” in Proc. 60th IEEE Conference on Decision and Control (CDC), 2021, pp. 5130–5135.
  * [6] M. Pipattanasomporn, H. Feroze, and S. Rahman, “Multi-agent systems in a distributed smart grid: Design and implementation,” in Proc. IEEE Power Systems Conf. and Expo., 2009, pp. 1–8.
  * [7] D. Deplano, M. Franceschelli, and A. Giua, “Lyapunov-free analysis for consensus of nonlinear discrete-time multi-agent systems,” in IEEE Conference on Decision and Control (CDC), 2018, pp. 2525–2530.
  * [8] J. Ebegbulem and M. Guay, “Resource allocation for a class of multi-agent systems with unknown dynamics using extremum seeking control,” in IEEE Conference on Decision and Control (CDC), 2018, pp. 2496–2501.
  * [9] K. Lu, H. Xu, and Y. Zheng, “Distributed resource allocation via multi-agent systems under time-varying networks,” Automatica, vol. 136, p.110059, 2022.
  * [10] N.-T. Nguyen, T. T. Nguyen, M. Roos, and J. Rothe, “Computational complexity and approximability of social welfare optimization in multiagent resource allocation,” Auton. Agents Multi-Agent Syst., vol. 28, no. 2, pp. 256–289, 2014.
  * [11] Y. Chevaleyre, P. E. Dunne, U. Endriss, J. Lang, N. Maudet, and J. A. RodrÍGuez-Aguilar, “Multiagent resource allocation,” The Knowledge Engineering Review, vol. 20, no. 2, pp. 143–149, 2005.
  * [12] S. Bikhchandani and J. W. Mamer, “Competitive equilibrium in an exchange economy with indivisibilities,” J. Econ. Theory, vol. 74, no. 2, pp. 385–413, 1997.
  * [13] E. Wei, A. Malekian, and A. Ozdaglar, “Competitive equilibrium in electricity markets with heterogeneous users and price fluctuation penalty,” in Proc. 53rd IEEE Conference on Decision and Control (CDC), 2014, pp. 6452–6458.
  * [14] D. Acemoglu, D. Laibson, and J. List, Microeconomics, 2nd edition, Pearson, 2018.
  * [15] K. J. Arrow and G. Debreu, “Existence of an equilibrium for a competitive economy,” Econometrica: Journal of the Econometric Society, vol. 22, no. 3, pp. 265–290, 1954.
  * [16] G. Debreu, “A social equilibrium existence theorem,” Proc. Nat. Acad. Sci., vol. 38, no. 10, pp. 886–893, 1952.
  * [17] Y. Chen, R. Islam, E. Ratnam, I. R. Petersen, and G. Shi, “Social shaping of competitive equilibriums for resilient multiagent systems,” in Proc. 60th IEEE Conference on Decision and Control (CDC), 2021, pp. 2621–2626.
  * [18] A. Mas-Colell, M. D. Whinston, and J. R. Green, Microeconomic Theory. London, U.K.: Oxford Univ. Press, 1995.
  * [19] S. Li, J. Lian, A. J. Conejo, and W. Zhang, “Transactive energy systems: The market-based coordination of distributed energy resources,” in IEEE Control Systems Magazine, vol. 40, no. 4, pp. 26–52, Aug. 2020.
  * [20] K. Ma and P. R. Kumar, “Incentive compatibility in stochastic dynamic systems,” IEEE Transactions on Automatic Control, vol. 66, no. 2, pp. 651–666, 2021.
  * [21] T. Groves, “Incentives in teams,” Econometrica, vol. 41, no. 4, pp. 617–631, 1973.
  * [22] Z. Salehi, Y. Chen, E. Ratnam, I. R. Petersen, and G. Shi, “Social shaping of linear quadratic multi-agent systems,” in Proc. 2021 Australian & New Zealand Control Conference (ANZCC), 2021, pp. 232–237.
  * [23] Z. Salehi, Y. Chen, E. Ratnam, I. R. Petersen, and G. Shi, “Social shaping for transactive energy systems,” Preprint at arXiv:2109.12967, 2021.
  * [24] S. Blumsack, “What’s behind $15,000 electricity bills in Texas,” https://theconversation.com, 2021.