# Efficient Resource Scheduling for Distributed Infrastructures Using
Negotiation Capabilities

Junjie Chu Prashant Singh Salman Toor

Department of Information Technology, Uppsala University

###### Abstract

In the past few decades, the rapid development of information and internet
technologies has spawned massive amounts of data and information. The
information explosion drives many enterprises or individuals to seek to rent
cloud computing infrastructure to put their applications in the cloud.
However, the agreements reached between cloud computing providers and clients
are often not efficient. Many factors affect the efficiency, such as the
idleness of the providers’ cloud computing infrastructure, and the additional
cost to the clients. One possible solution is to introduce a comprehensive,
bargaining game (a type of negotiation), and schedule resources according to
the negotiation results. We propose an agent-based auto-negotiation system for
resource scheduling based on fuzzy logic. The proposed method can complete a
one-to-one auto-negotiation process and generate optimal offers for the
provider and client. We compare the impact of different member functions,
fuzzy rule sets, and negotiation scenario cases on the offers to optimize the
system. It can be concluded that our proposed method can utilize resources
more efficiently and is interpretable, highly flexible, and customizable. We
successfully train machine learning models to replace the fuzzy negotiation
system to improve processing speed. The article also highlights possible
future improvements to the proposed system and machine learning models. All
the codes and data are available in the open-source repository.

##  1 Introduction

In the past few years, the rapid development of information and internet
technology has spawned massive amounts of data and information. It is not
economical for most enterprises and individuals to update and maintain
hardware devices for data-intensive applications. Therefore, many enterprises
or individuals seek to rent cloud computing infrastructure to put their
applications in the cloud to reduce costs and gain better flexibility. Many
cloud computing infrastructure providers build lots of data centers and lease-
related resources to meet the needs of the above tenants [30, 29]. The most
famous case of tenants is Netflix. The organization spent years migrating data
from its data centers to AWS [9]. Well-known representatives of infrastructure
providers include Amazon Web Services, Microsoft Azure, and Huawei Cloud [26,
22].

Cloud services have a range of advantages, but they are still far from
perfect. For example, in the process of buying and selling, such a basic
assumption is followed: the more consumers buy, the more discounts the sellers
will give, and the lower the unit price of goods purchased by consumers. When
infrastructure tenants and providers negotiate offers, tenants may
underestimate the potential future resource demand and purchase resources at a
higher unit price when further capacity expansion occurs. For the providers,
the excess resources have been idle, and cannot make a profit. In addition,
idle resources create inefficient utilization of the resources which leads to
unnecessary costs and carbon emissions [10, 5].

One possible new solution is to introduce a comprehensive, win-win autonomous
bargaining process (a type of negotiation) and schedule resources according to
the results of the process. In this comprehensive negotiation, the interests
of both parties are resolved through a negotiation process oriented towards
cooperation and information exchange. This is a well-known way to find win-win
agreements between providers and tenants [15]. On the condition that the basic
requirements of the tenants are met, the participants regard the negotiation
as a “problem to be solved,” then approach a solution acceptable to both
parties through negotiation, and finally reach a win-win agreement. In the
case of cloud computing resources, it may even be a win-win-win. In addition
to tenants and infrastructure providers, the environment can benefit from more
efficient resource utilization due to the negotiation game.

The solution suffers from the following two challenges:

  * •

How to implement an effective agent-based autonomous negotiation system?

  * •

How to speed up the entire negotiation process while keeping the offering
mechanism explainable?

In this article, a negotiation system based on fuzzy logic is designed and
developed. In this system, we design two agents to simulate different actors,
roles, and responsibilities within distributed infrastructure settings. We
have identified two main actors: infrastructure providers and application
owners (tenants). The aim is to offer cost-effective execution plans to
application owners while maximizing infrastructure providers’ resource
utilization and economic benefits. Storage, VCPU, and RAM will be considered
parameters in the negotiation process. Multiple levels of information volumes
are exchanged between the agents running on behalf of the tenants and
suppliers. In the end, an offer that satisfies both parties based on a
specific level of mutual information will be reached through negotiation.
Moreover, multiple machine learning models are selected and trained, which can
replace the negotiation game and achieve similar results with higher
efficiency. It is important to note that the choice of these particular
parameters is based on the way current service providers offer services. The
presented framework is not limited to only these parameters.

Fuzzy negotiation systems are a promising solution to infrastructure resource
scheduling. The negotiation function can be a dynamic entity better
represented using fuzzy logic compared to crisp functions. Machine learning
and fuzzy logic are considered two separate approaches to solving problems.
They can combine but rarely replace each other. Therefore, another highlight
of this article is the systematic presentation of the feasibility (probably
the only one so far, as far as we know) of replacing fuzzy negotiation systems
with machine learning.

In typical business activities, participants need trustworthy ways to make
decisions. A fuzzy logic negotiation system could introduce important
interpretability, which satisfies the requirements of business activities.
Machine learning models viewed as black boxes, although difficult to
interpret, provide very high efficiency. Our article has the best of both
worlds and therefore has strong practicality in business.

The main contributions of the article are:

  * •

A comprehensive fuzzy logic-based negotiation system that supports multiple
cases and custom parameters to get offers and provide resource scheduling
indications.

  * •

A workflow that uses neural network models (surrogate model) to replace fuzzy
negotiation systems to speed up.

  * •

Extensive experiments to prove the feasibility of the neural network model to
replace the fuzzy negotiation system and compare the performance.

  * •

Overall, we propose a trustworthy, interpretable, and efficient scheduling
method for resources that combines machine learning models and fuzzy
negotiation.

The remainder of this article is organized as follows: Section 2 presents the
scenarios, concepts, and technical tools in the article. Section 3 introduces
the design of fuzzy negotiation systems and machine learning workflow. Section
4 explains the details of related experiments, including the settings and
results. Section 5 reviews related literature. In Section 6, we conclude the
work, and further possible improvements are discussed.

##  2 Preliminaries

###  2.1 Scenario

Tenants who order large quantities tend to enjoy discounts on unit prices,
which is a widely used promotion method in business activities. There is also
such a situation in the field of infrastructure services. Whether it is Google
Cloud or Huawei Cloud, they all provide more favorable unit prices to
customers who rent a lot according to their price tables [6][8]. In our
article, we imitate Huawei Cloud’s pricing system and set up a simplified
simulated one as Table 1.

In this article, we use _client’s agent_ to represent tenants and _provider’s
agent_ to represent infrastructure service providers in our negotiation
systems. The scenario can be described in detail as follows: After reading
Table 1, the tenant inputs its requirements and other related parameters to
the client’s agent, and then the agent submits this information to the
provider’s agent directly. The provider’s agent then negotiates with the
client’s agent to provide new offers based on the input provided by the
client’s agent. Compared with the tenant’s requirements, the new offer should
have a higher total price, lower unit prices, and more resources.

According to the amount of information provided by the client in the
negotiation, the scenario can be subdivided into the following three cases:

Case 1: In each round, after receiving the new offer from the provider, the
client only replies whether to accept it or not.

Case 2: In each round, after receiving the new offer from the provider, the
client replies whether to accept it or not and the advice (which resource
needs to be reduced).

Case 3: At the very beginning of the negotiation, the client tells the
provider the priorities of the various resources (VCPU, RAM, and storage). In
each round, after receiving the new offer from the provider, the client
replies with whether to accept it or not and the same advice as in Case 2.

Table 1: Simplified daily rental prices VCPU | RAM | Storage
---|---|---
Number | €(per VCPU) | Number | €(per GB) | Number | €(per GB)
0-10 | level-1: 0.2 | 0-20 | level-1: 0.1 | 0-100 | level-1: 0.02
11-30 | level-2: 0.1 | 21-60 | level-2: 0.05 | 101-300 | level-2: 0.01
31-90 | level-3: 0.05 | 61-180 | level-3: 0.025 | 301-900 | level-3: 0.005

###  2.2 Core components

##### Fuzzy negotiation system

We design and implement a fuzzy negotiation system (FNS) based on a one-to-one
auto-negotiation model. The parties involved are two agents representing
_Provider_ and _Client_. Both agents are assumed to be rational beings
[18][23]. The client’s original requirement is used as the input of FNS. The
final offer obtained by the auto-negotiation process is considered as the
output of FNS.

A typical architecture of fuzzy logic consists of four parts: rule base,
fuzzification, inference engine, and defuzzification. The fuzzy logic
components are based on psychological and economic factors common in
negotiation. Each part of the fuzzy system can be checked and understood by a
human being, which is the source of interpretability [2].

Based on the above-mentioned, the working process of FNS can be described as:
the client submits the original requirement as the input of FNS. The final
offer obtained through the auto-negotiation process is used as the output of
FNS. During each round of negotiation, the provider’s agent updates the offer
through specific algorithms, and the client’s agent uses fuzzy logic to
determine whether the updated offer is acceptable.

##### Surrogate modeling

Given a specific client, for any input, the FNS could generate a corresponding
output. The way of using FNS is quite similar to that of machine learning
models. On the other side, in previous studies [1][31][7], the neural network
model has shown us that it works well in simulating human decision-making. We
conjecture that the neural network should also have good performance in
fitting the FNS that simulates the human way of thinking. The study by Carbo
et al. [3] partially verified our conjecture. Thus, we explore the feasibility
of replacing the FNS with neural network models. We emphasize _entire_ to
distinguish it from previous studies that used machine learning models to
evaluate the offer in a single round.

Training a neural network model can be briefly described as follows: one input
(client’s original requirement) and its corresponding output (final offer)
from the FNS are combined and considered a data record. The input is the
_feature_ , and the output is the _label_ during the training process.

A dataset could be obtained using different inputs and recording them and
their corresponding outputs. Then we split the dataset into a test set and a
training set to train the neural network models. The target of training is to
make the output of the FNS and the model as close as possible.

Although auto-negotiation greatly speeds up the negotiation, each negotiation
still requires dozens of rounds. In particular, in fuzzy logic, if the number
of fuzzy rules is increased, the processing speed will be significantly
reduced. Based on the above, we consider using both the fuzzy negotiation
system and the neural network model. The fuzzy negotiation system provides
interpretability and anthropomorphism. Then we use a black-box neural network
model to replace the white-box fuzzy negotiation system, which greatly
improves efficiency. Since the output of a machine learning model is similar
to the fuzzy negotiation system, interpretability is preserved throughout the
workflow.

##  3 System architecture

###  3.1 Overall design

Figure 1 is an overview of the methods involved in the article. It is
unrealistic to rely entirely on manual negotiation. Therefore, we propose two
other methods. The inputs of the three methods are consistent. Ideally, the
output of the other two methods should be close to manual negotiation and they
could speed up or partially replace manual negotiation.

###  3.2 Fuzzy negotiation system

####  3.2.1 System workflow

Figure 1: Overview of different methods

(a) The workflow in Case 1.

(b) The workflow in Case 2 and 3. The introduction of advice and priority is
an important feature that distinguishes Case 1.

Figure 2: Flow charts in different cases. Algorithm 3 has multiple versions
according to different cases.

We use a direct-negotiation model in our fuzzy negotiation system. Different
from indirect negotiation, two agents exchange information directly instead of
submitting information to an intermediary. Therefore, the entire structure is
simplified. The core parts are related algorithms and the fuzzy decision-
making system. Figure 2 shows the specific flow charts.

####  3.2.2 Fuzzy decision-making system

##### Parameters

There are two types of parameters: crisp parameters and fuzzy parameters.
Subscription plans from companies like Google, and Spotify, and some past
studies [17] [25] have shown that unit price and total order price are key
factors in negotiation. In addition, Kristensen et al. [13] show that in both
the roles of buyers and sellers, subjects adopt an initial offer as a
reference point. After comprehensively considering the above factors, we
design four ratios ($ru_{c/0}^{VCPU}$, $ru_{c/0}^{RAM}$, $ru_{c/0}^{Storage}$,
$rt_{0/c}$) to be the input of the system and use the client’s tendency as the
output. We set the client agent’s original requirement as the reference point.
Table 2(b) shows the definition of crisp parameters. All crisp inputs are
between 0 and 1, so the dimension effect is eliminated. Fuzzy values can be
obtained by fuzzing crisp inputs using membership functions. The possible
fuzzy values of each input and output of the fuzzy system are organized in
Table 2(b). While describing the parameters, once again we would like to
highlight that the choice of these particular parameters is based on the way
current service providers offer services. The presented framework is not
limited to only these parameters.

Table 2(a): Definition of crisp parameters Crisp parameters | Definition
---|---
$pu_{0}^{VCPU},pu_{0}^{RAM},pu_{0}^{Storage}$ | Resources’ unit prices in original requirements
$pu_{c}^{VCPU},pu_{c}^{RAM},pu_{c}^{Storage}$ | Resources’ unit prices in current offers
$pt_{0}$ | Total price of the original requirement
$pt_{c}$ | Total price of the current offer
$ru_{c/0}^{VCPU}$ | $ru_{c/0}^{VCPU}=pu_{c}^{VCPU}/pu_{0}^{VCPU}$
$ru_{c/0}^{RAM}$ | $ru_{c/0}^{RAM}=pu_{c}^{RAM}/pu_{0}^{RAM}$
$ru_{c/0}^{Storage}$ | $ru_{c/0}^{Storage}=pu_{c}^{Storage}/pu_{0}^{Storage}$
$rt_{0/c}$ | $rt_{0/c}=pt_{0}/pt_{c}$

Table 2(b): Possible values of fuzzy parameters Input | Corresponding fuzzy values
---|---
VUPR (VCPU unit price ratio, current/original) | cheap | medium | expensive
RUPR (RAM unit price ratio, current/original) | cheap | medium | expensive
SUPR (Storage unit price ratio, current/original) | cheap | medium | expensive
TPR (Total price ratio, original/current) | high | medium | low
Output | Corresponding fuzzy values
Tendency | low | medium | high

##### Membership functions

We choose two types of membership functions: the triangular membership
function and the Gaussian membership function. In the same system, we use only
one type of membership function instead of mixing two types. For Gaussian
membership functions, we apply the 3-sigma rule [20]. The starting point, the
highest point, and the ending point of the triangular function are obtained at
$a$, $b$, and $c$, respectively. The mean of the corresponding Gaussian
function is $m$ and the standard deviation is $\sigma$, then
$m=b,a=b-3\sigma,c=b+3\sigma$. The three ratios share the same membership
functions while the tendency uses a unique one.

##### Fuzzy rule set

We design two fuzzy rule sets based on prior knowledge: a 7-rule set and a
30-rule set. The 7-rule set refers to Table 3. Complex rules lead to better
anthropomorphism, but performance decreases. We conduct relevant experiments
to compare and analyze the two rule sets. Fuzzy outputs could be obtained
according to fuzzy rule sets.

##### Defuzzification

It converts fuzzy sets obtained by the inference engine into crisp values.
Usually, a specific defuzzification method is selected and combined with a
specific expert system to improve accuracy. We apply the Center of Gravity
(CoG) method [28] during defuzzification to transfer fuzzy inference results
into crisp outputs (tendency score).

##### Threshold of the final scores

The threshold is used to evaluate whether the offer is accepted. According to
Table 1, for crisp input parameters, the unit price ratio is in the range
[0.389, 1], and the ratio of the total price is in the range [0.0238, 1]. So
in the worst case (VUPR:1, RUPR:1, SUPR:1, TPR:0.0238), the final score is
about 14.79. While in the best case (VUPR:0.389, RUPR:0.389, SUPR:0.389,
TPR:1), the final score is about 61.63. In fact, the best and worst cases
cannot happen, so the final score ranges between 14.79 and 61.63. For the
original requirement, the score is 50.00. Given the above, the threshold
should be set to a number close to 50.00 based on some prior knowledge.

Table 3: The seven-rule set | Fuzzy input | Fuzzy output
---|---|---
Rule index | VUPR | RUPR | SUPR | TPR | Tendency
1 | $\backslash$ | $\backslash$ | $\backslash$ | high | low
2 | $\backslash$ | $\backslash$ | $\backslash$ | medium | medium
3 | $\backslash$ | $\backslash$ | $\backslash$ | low | high
4 | cheap | cheap | cheap | $\backslash$ | high
5 | expensive | $\backslash$ | $\backslash$ | $\backslash$ | medium
6 | $\backslash$ | expensive | $\backslash$ | $\backslash$ | medium
7 | $\backslash$ | $\backslash$ | expensive | $\backslash$ | medium

####  3.2.3 Algorithms

##### Algorithm 1

Both the client agent’s original requirements and the provider agent’s offers
consist of the quantities of VCPU, RAM, and storage. The motivation for
clients to rent more resources is lower unit prices. Therefore, when the
provider agent generates the first offer, the unit price of all parameters in
it should be lower than the client agent’s original requirement. To achieve
this goal, the quantity of each parameter needs to be increased by $p$ so that
a cheaper unit price can be adopted. Thresholds for different levels of prices
determine $p$. For example, if the number of VCPU is increased from 5 to 15,
the unit price used is level 2 instead of level 1. The details are available
in Algorithm 1 in the appendix.

##### Algorithm 2

During negotiation, if the client agent rejects the offer, it could advise the
provider agent on how to update the offer. In real life, clients often require
the quantities of different resources to be in a specific ratio, that is:

$\frac{n_{c}^{VCPU}}{n_{0}^{VCPU}}=\frac{n_{c}^{RAM}}{n_{0}^{RAM}}=\frac{n_{c}^{Storage}}{n_{0}^{Storage}}$
(1)

Equation 1 could be rewritten as follows:

$\frac{max(\frac{n_{c}^{VCPU}}{n_{0}^{VCPU}},\frac{n_{c}^{RAM}}{n_{0}^{RAM}},\frac{n_{c}^{Storage}}{n_{0}^{Storage}})}{min(\frac{n_{c}^{VCPU}}{n_{0}^{VCPU}},\frac{n_{c}^{RAM}}{n_{0}^{RAM}},\frac{n_{c}^{Storage}}{n_{0}^{Storage}})}=1$
(2)

where:

$n_{0}^{VCPU},n_{0}^{RAM},n_{0}^{Storage}$ ${}:{}$ |  the quantities of VCPU, RAM, and storage in the original requirement
---|---
$n_{c}^{VCPU},n_{c}^{RAM},n_{c}^{Storage}$ ${}:{}$ |  the quantities of VCPU, RAM, and storage in the current offer

For the negotiation to continue, we slightly relax the conditions of Equation
2, namely:

$\frac{max(\frac{n_{c}^{VCPU}}{n_{0}^{VCPU}},\frac{n_{c}^{RAM}}{n_{0}^{RAM}},\frac{n_{c}^{Storage}}{n_{0}^{Storage}})}{min(\frac{n_{c}^{VCPU}}{n_{0}^{VCPU}},\frac{n_{c}^{RAM}}{n_{0}^{RAM}},\frac{n_{c}^{Storage}}{n_{0}^{Storage}})}<d_{max}$
(3)

where:

$d_{max}$ ${}:{}$ |  the maximum deviation value, usually slightly larger than 1, specified by the client
---|---

If Equation 3 is satisfied, the client agent gives the advice _random_.
Otherwise, the client agent uses the parameter with the largest quantity as
the advice. The details are shown in Algorithm 2 in the appendix.

##### Algorithm 3

To speed up the negotiation, a search problem, a method that draws on the idea
of stochastic gradient descent is applied. In each round, we randomly select
one of the three parameters in the offer to reduce with some probability.
Given the amount of changing $c^{Para}$ in each parameter per round, the
selected parameter will be reduced by $c^{Para}$ to update the offer. In
different cases, we have slightly different algorithms for calculating the
probabilities and selecting the parameters.

##### Case a

At a given round of negotiations, the original requirement, current offer, and
final offer satisfy:

$\displaystyle n_{c}^{Para}\approx q\cdot n_{0}^{Para},\quad 1\leq q,\quad
q\in\mathbb{R}$ (4) $\displaystyle n_{f}^{Para}\approx k\cdot
n_{0}^{Para},\quad 1\leq k\leq q,\quad k\in\mathbb{R}$ (5)

where:

$n_{c}^{Para}$ ${}:{}$ |  the quantity of a specific parameter in the current offer
---|---
$n_{0}^{Para}$ ${}:{}$ |  the quantity of the same parameter in the original requirement
$n_{f}^{Para}$ ${}:{}$ |  the quantity of the same parameter in the final offer

From the current offer to the final offer, the number of rounds required can
be expressed as:

$\displaystyle rd^{Para}=(q-k)\cdot n_{0}^{Para}/c^{Para}$ (6)

where:

$c^{Para}$ ${}:{}$ |  the amount of change of the same parameter per round
---|---

In this case, we use the ratio of the number of rounds needed for each
parameter to represent the ratio of the probabilities corresponding to each
parameter. With the assumption that the ratios remain consistent with the
initial ratios in the original requirement, all the parameters should share
the same $q$ and $k$ at the same round. Then the probabilities satisfy:

$\displaystyle\begin{split}&\ pb^{VCPU}:pb^{RAM}:pb^{Storage}\\\ =&\
rd^{VCPU}:rd^{RAM}:rd^{Storage}\\\ =&\
\frac{n_{0}^{VCPU}}{c^{VCPU}}:\frac{n_{0}^{RAM}}{c^{RAM}}:\frac{n_{0}^{Storage}}{c^{Storage}}\end{split}$
(7)

where:

$pb^{VCPU},pb^{RAM},pb^{Storage}$ ${}:{}$ |  the probability of choosing the parameter in a round
---|---

The details can be found in Algorithm 3.a in the appendix.

##### Case b

The ratio of the number of parameters in the offer may deviate a lot from the
client’s requirement during the negotiation. At this time, with Algorithm 3.a,
it may not be possible to obtain an offer that meets a specific proportion.
Therefore, we introduce _Advice_ on the client side to help the provider to
revise the offer by Algorithm 2. If the _Advice_ given by the client is
’randomly’, parameters requiring a reduction in amount are selected according
to Algorithm 3.a. If the _Advice_ is the name of a certain parameter, the
number of that parameter will be reduced. Details can be found in Algorithm
3.b in the appendix.

##### Case c

In real life, the client thinks that different parameters have different
priorities. This means that when a customer considers both offers acceptable,
the customer will prefer the offer with higher high-priority parameters. We
introduce the parameter _priority_ to modify the probability so that the offer
could fit the client’s requirement more. Each parameter has its respective
_priority_. The value of _priority_ is greater than or equal to 1. A parameter
with a higher priority has a larger value of _priority_. The algorithm using
adjusted probabilities is described in Algorithm 3.c in the appendix.

###  3.3 Machine learning process

####  3.3.1 Workflow

We aim to replace the entire fuzzy negotiation system with a neural network
surrogate model. We use fuzzy negotiation systems to generate the training and
test datasets: each original requirement and its corresponding output of the
fuzzy negotiation system is treated as a record and stored in the database.
These data are normalized. We treat this process as a regression problem. The
original requirement is considered as the input of models while the output of
the fuzzy system (a vector consisting of the amounts of three sources) is
considered as the label. The mean squared error (MSE) is used to measure the
distance (loss) between the label vectors and the model’s output vectors.
After training, we input the same original requirements into the trained model
and the fuzzy negotiation system, respectively, and compare the outputs of the
two systems. Refer to Figure 3 for the entire workflow.

####  3.3.2 Model architecture

For regression problems, activation functions (e.g., Softmax, Sigmoid, etc.)
are not used in the last layer of the neural network model. We try two types
of models with different structures and layers.

Type 1 is the multilayer perceptron (MLP). It consists of four linear layers.
It expands the input three features to 128 dimensions and then scales to 64
dimensions and 27 dimensions, and the final output contains three dimensions.
Furthermore, we change the number of layers of the model to analyze the effect
of the depth of the neural network model.

Type 2 uses a 7-layer architecture. Among them, the fourth layer is the Relu
layer, and the others are linear layers. The role of the Relu layer is to
introduce nonlinear components. It is generally believed that fuzzy logic is
suitable for nonlinear systems. So we conjecture Type 2 will have better
performance than Type 1.

Figure 3: Workflow of training machine learning models

##  4 Results and discussion

###  4.1 Settings

We use three sizes of input datasets to analyze the results or performance.
Details of these datasets can be found in Table 4. Table 5 shows the
information on the different systems we use. The cases are defined in Section
2.1. The experiments are based on Python and its library Scikit-fuzzy. The
associated codes and datasets can be found in the open source repository.

Table 4: Different input datasets used in the experiment Index | No. records | Note
---|---|---
Dataset 1 | 1 | The input is (10,20,200)
Dataset 2 | 200 | Test dataset, total fee from low to high.
Dataset 3 | 10000 | Training dataset, No overlap with Dataset 2.
Table 5: Configuration of different systems Version | Case | Membership function | Fuzzy rule set | Threshold (final score)
---|---|---|---|---
System 1 | Case 2 | Triangular | 7-rule set | 50.0
System 2 | Case 2 | Gaussian | 7-rule set | 50.0
System 3 | Case 2 | Gaussian | 30-rule set | 50.0
System 4 | Case 1 | Gaussian | 30-rule set | 50.0
System 5 | Case 3 | Gaussian | 30-rule set | 50.0

###  4.2 Experiments of fuzzy negotiation system

####  4.2.1 Different membership functions

In this experiment, all parameters are the same except for the membership
functions used in the client agent. We compare System 1 and System 2 in Table
5 on Dataset 2.

The ratios of the total fee (final offer: original requirement) are shown in
5(a). If the ratio is 1.0, the negotiation fails. The negotiation success
rates of versions with different membership functions are almost the same
(61.5%). However, compared with the triangular membership function, the total
fees of the final offers output by the system with the Gaussian membership
function are higher, and the fees fluctuate more. We observe similar phenomena
with the amounts of other parameters. Therefore, we believe the client agent
using the Gaussian membership function is more flexible.

Table 6: Performance of different membership functions Version | Dataset | Records number | Rounds number | Time
---|---|---|---|---
System 1 (Triangular) | Dataset 1 | 1 | 42 | 1.316s
System 1 (Triangular) | Dataset 2 | 200 | $\backslash$ | 1m12s
System 1 (Triangular) | Dataset 3 | 10000 | $\backslash$ | 1h6m24s
System 2 (Gaussion) | Dataset 1 | 1 | 27 | 0.051s
System 2 (Gaussion) | Dataset 2 | 200 | $\backslash$ | 3.012s
System 2 (Gaussion) | Dataset 3 | 10000 | $\backslash$ | 2m56s

In addition, we test the performance of the two versions on three datasets.
Table 6 shows the results. The version of the Gaussian membership function has
better performance on all datasets. The number of negotiation rounds between
the two versions is not much different (42 vs. 27) on Dataset 1. But the time-
consuming difference is dozens of times (1.316s vs. 0.051s). We draw similar
conclusions from other datasets.

####  4.2.2 Different fuzzy rule sets

In this experiment, we test System 2 and System 3 in Table 5 on Dataset 2. The
difference between them lies in different fuzzy rule sets.

The output trends of the two versions are similar as shown in 5(b). Compared
with the 7-rule version, the total fee ratio of the 30-rule version fluctuates
more, which means that the 30-rule version simulates the thinking of a real
human being to a higher degree. The 30-rule version is slightly lower than the
7-rule version in success rate (60% vs. 61.5%).

Table 7: Performance test of different fuzzy rule sets Version | Dataset | Number of records | Number of rounds | Time
---|---|---|---|---
System 2 (7-rule) | Dataset 1 | 1 | 27 | 0.051s
System 2 (7-rule) | Dataset 2 | 200 | $\backslash$ | 3.012s
System 2 (7-rule) | Dataset 3 | 10000 | $\backslash$ | 2m56s
System 3 (30-rule) | Dataset 1 | 1 | 55 | 0.342s
System 3 (30-rule) | Dataset 2 | 200 | $\backslash$ | 48.011s
System 3 (30-rule) | Dataset 3 | 10000 | $\backslash$ | 39m04s

Different fuzzy rule sets also result in different performances. As shown in
Table 7, the 30-rule system spends much longer time on all datasets than the
7-rule system. From a time-consuming perspective, the 7-rule version has
better performance. The curve of the 30-rule system is more complex than that
of the 7-rule system, reflecting that the 30-rule system can be better
anthropomorphic. From the perspective of simulating human thinking, it is
worth mentioning that the 30-rule system using the Gaussian membership
function performs better than the 7-rule one using the Gaussian membership
function.

####  4.2.3 Different cases

We conduct experiments to compare the systems under different cases. The
systems we use are System 3, System 4, and System 5 in Table 5.

##### Case 1 vs. Case 2

We conduct related experiments on Dataset 2. According to 5(c), the results of
these two cases are generally similar. When the number of leased resources is
large (level-3 prices apply), there is no room for negotiation, so the ratio
is always 1.0 (negotiation fails). When the number of rented resources is
relatively tiny (level-1 or level-2 price applies), the negotiation success
rate of Case 2 is slightly lower than that of Case 1. Usually, the total fee
ratio of Case 2 is also a bit lower than that of Case 1. This aligns with our
expectation: Case 1 only considers the client’s financial factors. Case 2 adds
requirements for the ratio of each parameter on this basis, so the negotiation
of Case 2 is more complicated.

##### Case 2 vs. Case 3

In Case 3, we introduce $priority$ to modify the final offer. Case 2 is a
special case of Case 3 when all parameters have the same priority. As shown in
Table 8, the system of Case 3 tends to select offers with more high-priority
parameters among all the offers that satisfy other conditions. We fix the
$priority$ values of RAM and storage (set to 1), change the $priority$ value
of VCPU, and conduct experiments on Dataset 2. As shown in 5(d), the
conclusion is similar to that of the above single-input experiment. The
version with the highest VCPU $priority$ value retains the most VCPUs.

##### Performance

The features we add in case 2 and case 3 aim to make the offer more in line
with the client’s requirements rather than reducing the number of negotiation
rounds. In other words, the parameters given by $advice$ or $priority$ do not
necessarily result in the fastest gradient descent direction. Therefore, the
performance of Case 2 or 3 is not necessarily better than that of Case 1. As
shown in Table 9, the performance of the three cases is close. The time to
process 10,000 entries is typically 40 minutes or more. So it is necessary to
look for a more efficient alternative.

Figure 4: Comparison of the ratios (VCPU)

####  4.2.4 Evaluation of the negotiation results

We test three different versions of the system on Dataset 2. In System 5, the
$priority$ value of VCPU is set to 1.50, and those of other parameters are set
to 1.0. We evaluate the systems based on the total fee ratios and negotiation
success rate. A higher ratio means the provider rents more resources and earns
more profit.

As shown in Table 10, over the entire Dataset 2, the total fee ratios of all
versions increase by more than 10%. We remove the elements in Dataset 2 that
have no negotiation space (that is, the unit price of the resource is already
level 3) to get a new dataset. The total fee ratio improvement on the new
dataset is over 15% for each version. In terms of negotiation success rate,
the success rate on the new dataset is very high. Among them, the least
restrictive version (System 4) has the highest negotiation success rate,
reaching 100%. Providers can earn at least an average of 15% extra in the vast
majority of cases where there is room for negotiation.

Comparing the different ratios in an offer makes the attractiveness of the
offer more intuitive. We use System 5 and Dataset 1 for demonstration. Figure
4 shows the results of VCPU and the total fee for some negotiation rounds. In
the final offer (the 46th round), the client only needs to spend 17.1% more to
get 50% more VCPU. The situation is similar for the other parameters: the
client can also get 30% more RAM and 20% more storage. From these ratios, it
is clear that clients can get a lot of additional resources for only a small
extra cost.

(a) Ratios of total fees in Dataset 2 (different membership functions)

(b) Ratios of total fees in Dataset 2 (different rule sets)

(c) Ratios of total fees in Dataset 2 (different cases)

(d) Ratios of VCPU’s amounts on Dataset 2 (different priorities)

Figure 5: Plots of ratios in different experiments. Horizontal axes represent the index of the input requirement. The vertical axes represent ratios. The baseline is 1.0, which means values in final offers are the same as those in the original requirements. Table 8: Experiments of different priorities in Case 3. The priority of RAM and Storage is set to 1.0, and only the priority values of VCPU are changed. Inputs and outputs are in the format: (number of VCPUs, RAM, and Storage). Input | Priority of VCPU | Output | Score of output | Number of rounds
---|---|---|---|---
10, 20, 200 | 1.00 | 10, 23, 230 | 50.075 | 55
10, 20, 200 | 1.10 | 12, 23, 220 | 50.123 | 54
10, 20, 200 | 1.50 | 15, 26, 240 | 50.610 | 46
10, 20, 200 | 5.00 | 17, 26, 260 | 50.442 | 42
Table 9: Performance test of different cases Version | Dataset | Number of records | Number of rounds | Time
---|---|---|---|---
System 3 (case 2) | Dataset 1 | 1 | 55 | 0.342s
System 3 (case 2) | Dataset 2 | 200 | $\backslash$ | 48.011s
System 3 (case 2) | Dataset 3 | 10000 | $\backslash$ | 39m04s
System 4 (case 1) | Dataset 1 | 1 | 27 | 0.254s
System 4 (case 1) | Dataset 2 | 200 | $\backslash$ | 40.076s
System 4 (case 1) | Dataset 3 | 10000 | $\backslash$ | 41m15s
System 5 (case 3) | Dataset 1 | 1 | 45 | 0.311s
System 5 (case 3) | Dataset 2 | 200 | $\backslash$ | 73.032s
System 5 (case 3) | Dataset 3 | 10000 | $\backslash$ | 54m06s
Table 10: Average total fee ratio Version | Dataset | Num of records | Avg. total fee ratio | Success rate
---|---|---|---|---
System 3 (Case 2) | Dataset 2 | 200 | 1.114 | 60.0%
System 4 (Case 1) | Dataset 2 | 200 | 1.120 | 61.5%
System 5 (Case 3) | Dataset 2 | 200 | 1.108 | 61.0%
System 3 (Case 2) | Dataset 2 | 124 | 1.185 | 97.6%
System 4 (Case 1) | Dataset 2 | 124 | 1.195 | 100.0%
System 5 (Case 3) | Dataset 2 | 124 | 1.176 | 99.2%

###  4.3 Experiments of machine learning

####  4.3.1 Simulate the same system with different models

Table 11: MSE loss of different models’ predictions Version | VCPU | RAM | Storage | Entire offer
---|---|---|---|---
Model 1 | 0.0159 | 0.0055 | 0.0060 | 0.0092
Model 2 | 0.0155 | 0.0057 | 0.0057 | 0.0090
Model 3 | 0.0157 | 0.0055 | 0.0057 | 0.0090
Model 4 | 0.0018 | 0.0009 | 0.0005 | 0.0011
Table 12: MSE loss of predictions on different systems Version | VCPU | RAM | Storage | whole offer
---|---|---|---|---
System 1 (Case 2) | 0.0009 | 0.0004 | 0.0005 | 0.0006
System 2 (Case 2) | 0.0007 | 0.0011 | 0.0003 | 0.0007
System 3 (Case 2) | 0.0011 | 0.0007 | 0.0006 | 0.0008
System 4 (Case 1) | 0.0008 | 0.0010 | 0.0006 | 0.0008
System 5 (Case 3) | 0.0011 | 0.0006 | 0.0006 | 0.0008

We use System 3 as the negotiation system to be replaced. Dataset 2 and its
output in System 3 are combined as the test dataset. Dataset 3 and its output
in System 3 are combined as a training dataset. The number of epochs is 200.
We test four models in total. Models 1, 2, and 3 contain 4, 6, and 7 linear
layers, respectively. The first three models consist of linear layers only.
Model 4 consists of 6 linear layers and 1 Relu layer. We separately evaluate
the predicted quantity for a single parameter and the entire predicted offer
(i.e., a vector of quantities of three items) with mean squared error (MSE).
Table 11 presents these results.

For models with only linear layers, the number of layers slightly improves
prediction accuracy. The gap between the predictions and labels of these
models indicates that these models are insufficient to replace the original
negotiation system. However, the Relu layer significantly improves the
performance of the model. The predictions of the model with the Relu layer are
very close to the labels.

Table 13: Number of VCPUs in intermediate rounds Rounds | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7
---|---|---|---|---|---|---|---|---
Provider offer | 17 | 16 | 15 | 14 | 14 | 14 | 13 | 13
Client requirement | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7
Table 14: Comparison of outputs (final offers) of System 3 and Model 4 for the same inputs (original requirements) from the test dataset. Inputs and outputs are in the format: (number of VCPUs, RAM and Storage). Index of input data | Input | Output of System 3 | Output of Model 4
---|---|---|---
3 | 7, 56, 320 | 13, 107, 320 | 15, 100, 323
23 | 11, 85, 230 | 35, 85, 530 | 34, 79, 506
33 | 13, 47, 720 | 43, 107, 720 | 43, 107, 728
53 | 17, 41, 520 | 47, 101, 520 | 48, 100, 525
63 | 19, 86, 810 | 49, 86, 810 | 49, 87, 817

####  4.3.2 Simulate different systems with the same model

We use Model 4 to simulate the five systems in Table 5. In System 5, the
$priority$ value of VCPU is set to 1.25, and the other $priority$ values are
1.0. The training process of the models and related datasets are consistent
with Section 4.3.1. According to Table 12, Model 4 simulates all systems well.
Different membership functions, rule sets of different complexity, and cases
have very limited impact on the accuracy. Furthermore, on Dataset 2, Model 4
takes less than one second to complete all processing. Model 4 increases the
processing speed dozens of times while maintaining a similar output to these
systems.

We conclude that using the Relu layer in the neural network model can
significantly improve the model’s ability to simulate fuzzy negotiation
systems. Neural network models with Relu layers can replace all versions of
fuzzy negotiation systems and significantly improve processing speed.

####  4.3.3 Interpretability

Model 4 simulates all systems well. We use Model 4 to simulate System 3 to
further explain interpretability. The priority value of VPU is set to 1.5
while the others are 1.0. We randomly selected five data points from Dataset 2
as input, and the corresponding output is listed in Table 14. The outputs of
System 3 and Model 4 are so close that we can approximate that they are the
same. The output of System 3 is interpretable. Taking data point 3 as an
example, Table 13 clearly shows the changes in the number of VCPUs during the
seven rounds of negotiation in System 3. The same goes for other parameters
(RAM and Storage).

Based on the above, it can be concluded that our machine model can obtain good
representative results as the fuzzy negotiation system while significantly
improving the processing speed. The outputs of the fuzzy negotiation system
(including the negotiation results of any intermediate rounds) are observable
and interpretable. Therefore the output of the ML model can also be considered
trustworthy and interpretable.

##  5 Related work

In terms of the application scenarios of auto-negotiation, Pierson et al. [19]
explore the application of negotiation in server operations and power control.
They propose a solution where each side optimizes its objectives, interacting
through a negotiation loop to reach a joint agreement and present DATAZERO, a
project based on the above idea. Thi et al. [27] also focus on power
management, especially green data centers. They propose a buyer-supplier
negotiation game and algorithm for the problem of optimizing server operations
and energy management for data centers entirely powered by renewable energy
sources. Jörn et al. [14] also study distributed computing. They study the
dynamics of on-demand pricing and service usage in a two-stage game model for
a monopoly Infrastructure-as-a-Service (IaaS) market and propose a game-
theoretic model for the IaaS market.

The key to auto-negotiation implementation is judging whether the offer is
accepted. A typical way is to use a utility function to measure the offer.
Scoca et al. [24] define a simple formal language to specify interactions
between offers and requests modeled as dSLAC expressions and propose a way of
determining the cost of agreeing by relying on utility functions. Chokhani et
al. [4] propose a method that introduces the feature of on-demand resource
availability and elasticity using lease auto-negotiation in Haizea. Their work
adds a new class of lease called Dynamic lease which can be renegotiated
according to its current utilization. Masero et al. [16] propose a fuzzy-based
two-layer control architecture. In the lower control layer, there are pairwise
negotiations between agents according to the couplings and the communication
network. A coordinator in the upper control layer collects the resulting
pairwise control sequences and merges them to compute the final ones.
Kolomvatsos et al. [12] propose a fuzzy logic (FL) system with an adaptation
technique that updates the FL rule base and membership functions as necessary.

Another key is how to quickly approach the solution of the negotiation or
estimate the approximate solution. Considering the multi-tenancy market
operation mode competing in the cloud environment, Wei et al. [32] propose a
cloud resource allocation model based on an imperfect information Stackelberg
game using a Hidden Markov model (HMM). Rahman et al. [21] propose a
negotiation-game-based auto-scaling method where tenants and Network Operator
(NO) both engage in the auto-scaling decision via traversal search. They also
propose a proactive Machine Learning (ML) based prediction method to predict
the tendencies of tenants so that the search range can be reduced to improve
efficiency in dynamic scenarios.

Combining the fields of Negotiation, Fuzzy Logic, and Machine Learning is
relatively new, especially in distributed computing infrastructures. Related
research is very limited. Carbo et al. [3] study the application of machine
learning techniques to compare the privacy of preferences function using fuzzy
sets as counter-offers with the classical alternative based on concrete
values. They use ML to evaluate the fuzzy counter-offer in one negotiation
round. Khuen et al. [11] use ML to update the fuzzy rule base.

In comparison to the above-mentioned related work, our study features the
following key points:

  * •

We have designed and developed a framework for 1-to-1 negotiation to schedule
the resource in a distributed infrastructure. Different negotiation cases are
supported. We apply a fuzzy logic system with novel input parameters and fuzzy
rules on the client’s agent side to evaluate the offers. During the
negotiation process, the offers are updated using several new specific
algorithms.

  * •

We systematically and comprehensively study the feasibility of neural network
surrogate models to replace the entire fuzzy negotiation process. To the best
of our knowledge, this is the only one so far and significantly different from
other studies of single-round outcomes.

##  6 Conclusion and future direction

We propose an auto-negotiation system for resource scheduling based on fuzzy
logic. In the system, the client agent uses fuzzy logic to mimic the human
response to make decisions, while the provider agent dynamically updates the
offer according to the agreed terms. We compare the impact of different member
functions, fuzzy rule sets, and negotiation scenario cases on the final
offers. The framework also includes neural network models to fit the fuzzy
negotiation systems above. The trained model provides a much faster response
time for requests than the fuzzy negotiation system, which is very important
in the real-world cloud environment.

Based on the presented results, we can conclude that the proposed system can
utilize resources more efficiently. It is both interpretable and efficient and
has practical value in business activities.

In the future, we would like to extend our work toward the adaptive fuzzy
rules. The fuzzy rule set depends largely on prior knowledge in the fuzzy
negotiation system. Fuzzy rule sets with adaptive capabilities can modify,
delete, or add new fuzzy rules during negotiation, compensating for the
inaccuracy of prior knowledge and preset rule sets. Together with Fuzzy rules,
we would also like to develop new architectures for machine learning models.
We would like to include making the model aware of handling client priorities,
which can significantly improve the negotiation process.

Machine learning models also remain flawed. For the current machine learning
model, the input features we use are still too few. When the client modifies
the parameters (such as $priority$), we need to retrain and deploy the model.
In the future, we consider adding parameters such as $priority$ to the input
features and increasing the number of input features. Models trained with more
features are more general and easier to transfer and deploy.

## Acknowledgment

We want to acknowledge the Swedish National Infrastructure for Computing
(SNIC) for providing cloud resources and support from the eSSENCE strategic
collaboration in e-science.

## References

  * [1] Oludare Isaac Abiodun, Aman Jantan, Abiodun Esther Omolara, Kemi Victoria Dada, Nachaat AbdElatif Mohamed, and Humaira Arshad.  State-of-the-art in artificial neural network applications: A survey.  Heliyon, 4(11):e00938, 2018.
  * [2] Robert Babuška.  Fuzzy modeling for control, volume 12.  Springer Science & Business Media, 2012.
  * [3] Javier Carbo and Agapito Ledezma.  A machine learning based evaluation of a negotiation between agents involving fuzzy counter-offers.  In International Atlantic Web Intelligence Conference, pages 268–277. Springer, 2003.
  * [4] Pratick Chokhani and Gaurav Somani.  Dynamic resource allocation using auto-negotiation in haizea.  In 2013 Sixth International Conference on Contemporary Computing (IC3), pages 232–238, 2013.
  * [5] Google.  Google cloud carbon-footprint.  https://cloud.google.com/carbon-footprint.
  * [6] Google.  Vm instance pricing.  https://cloud.google.com/compute/vm-instance-pricing.
  * [7] Tim Hill, Leorey Marquez, Marcus O’Connor, and William Remus.  Artificial neural network models for forecasting and decision making.  International journal of forecasting, 10(1):5–15, 1994.
  * [8] Huawei.  Product pricing details.  https://www.huaweicloud.com/intl/en-us/pricing/index.html.
  * [9] Yury Izrailevsky, Stevan Vlaovic, and Ruslan Meshenberg.  Completing the netflix cloud migration.  https://about.netflix.com/en/news/completing-the-netflix-cloud-migration.
  * [10] Nicola Jones.  How to stop data centres from gobbling up the world’s electricity.  Nature, 561(7722):163–167, 2018.
  * [11] Cheng Wai Khuen, Chan Huah Yong, and Fazilah Haron.  A framework for multi-agent negotiation system using adaptive fuzzy logic in resource allocation.  International Journal of Information Technology, 11(4):p35–49, 2005.
  * [12] Kostas Kolomvatsos, Dimitrios Trivizakis, and Stathes Hadjiefthymiades.  An adaptive fuzzy logic system for automated negotiations.  Fuzzy sets and systems, 269:135–152, 2015.
  * [13] Henrik Kristensen and Tommy Gärlinga.  Adoption of cognitive reference points in negotiations.  Acta Psychologica, 97(3):277–288, 1997.
  * [14] Jörn Künsemöller and Holger Karl.  A game-theoretic approach to the financial benefits of infrastructure-as-a-service.  Future Generation Computer Systems, 41:44–52, 2014.
  * [15] Ira B Lobel.  Realities of interest based (win-win) bargaining.  Labor Law Journal, 45(12):771, 1994.
  * [16] Eva Masero, Mario Francisco, José M Maestre, Silvana Revollar, and Pastora Vega.  Hierarchical distributed model predictive control based on fuzzy negotiation.  Expert Systems with Applications, 176:114836, 2021.
  * [17] Celine Nauges and Alban Thomas.  Privately operated water utilities, municipal price negotiation, and estimation of residential water demand: The case of france.  Land Economics, pages 68–85, 2000.
  * [18] Martin J Osborne and Ariel Rubinstein.  A course in game theory.  MIT press, 1994.
  * [19] Jean-Marc Pierson, Gwilherm Baudic, Stéphane Caux, Berk Celik, Georges Da Costa, Léo Grange, Marwa Haddad, Jérôme Lecuivre, Jean-Marc Nicod, Laurent Philippe, et al.  Datazero: Datacenter with zero emission and robust management using renewable energy.  IEEE Access, 7:103209–103230, 2019.
  * [20] Friedrich Pukelsheim.  The three sigma rule.  The American Statistician, 48(2):88–91, 1994.
  * [21] Sabidur Rahman, Tanjila Ahmed, Minh Huynh, Massimo Tornatore, and Biswanath Mukherjee.  Auto-scaling network service chains using machine learning and negotiation game.  IEEE Transactions on Network and Service Management, 17(3):1322–1336, 2020.
  * [22] Yaman Roumani and Joseph K Nwankpa.  An empirical study on predicting cloud incidents.  International journal of information management, 47:131–139, 2019.
  * [23] Stuart J Russell.  Artificial intelligence a modern approach.  Pearson Education, Inc., 2010.
  * [24] Vincenzo Scoca, Rafael Brundo Uriarte, and Rocco De Nicola.  Smart contract negotiation in cloud computing.  In 2017 IEEE 10Th international conference on cloud computing (CLOUD), pages 592–599. IEEE, 2017.
  * [25] Fiona Scott Morton, Jorge Silva-Risso, and Florian Zettelmeyer.  What matters in a price negotiation: Evidence from the us auto retailing industry.  Quantitative Marketing and Economics, 9(4):365–402, 2011.
  * [26] Faith Shimba.  Cloud computing: Strategies for cloud computing adoption.  2010\.
  * [27] Minh-Thuyen Thi, Jean-Marc Pierson, Georges Da Costa, Patricia Stolf, Jean-Marc Nicod, Gustavo Rostirolla, and Marwa Haddad.  Negotiation game for joint it and energy management in green datacenters.  Future Generation Computer Systems, 110:1116–1138, 2020.
  * [28] Ester Van Broekhoven and Bernard De Baets.  A comparison of three methods for computing the center of gravity defuzzification.  In 2004 IEEE International Conference on Fuzzy Systems (IEEE Cat. No. 04CH37542), volume 3, pages 1537–1542. IEEE, 2004.
  * [29] Blesson Varghese and Rajkumar Buyya.  Next generation cloud computing: New trends and research directions.  Future Generation Computer Systems, 79:849–861, 2018.
  * [30] Anthony T Velte, Toby J Velte, Robert C Elsenpeter, and Robert C Elsenpeter.  Cloud computing: a practical approach.  2010\.
  * [31] Sun-Chong Wang.  Artificial neural network.  In Interdisciplinary computing in java programming, pages 81–100. Springer, 2003.
  * [32] Wei Wei, Xunli Fan, Houbing Song, Xiumei Fan, and Jiachen Yang.  Imperfect information dynamic stackelberg game based resource allocation using hidden markov for cloud computing.  IEEE Transactions on Services Computing, 11(1):78–89, 2018.

## Appendix

Algorithm 1 Generating the quantity of one parameter in the first offer
(Provider agent)

Input:
$n_{0}$: the quantity in the original requirement;
$T_{1-2}$: the threshold value of the quantity of the level-1 price and the
level-2 price;
$T_{2-3}$: the threshold value of the quantity of the level-2 price and the
level-3 price;
Output:
$n_{1}$: the quantity in the first offer;

1:if $0<n_{0}<=T_{1-2}$ then

2: $n_{1}=n_{0}+T_{1-2}$

3:else if $T_{1-2}<n_{0}<=T_{2-3}$ then

4: $n_{1}=n_{0}+T_{2-3}$

5:else

6: $n_{1}=n_{0}$

7:end if

Algorithm 2 Generating the advice (Client agent)

Input:
$n_{0}^{VCPU},n_{0}^{RAM},n_{0}^{Storage}$: the quantities of VCPU, RAM,
storage in the original requirement;
$n_{c}^{VCPU},n_{c}^{RAM},n_{c}^{Storage}$: the quantities of VCPU, RAM,
storage in the current offer;
$d_{max}$: the maximum deviation value;
Output:
$Advice$: the parameter the client agent advises to reduce or _random_ ;

1:Compute the ratios:

2:$r_{c/0}^{VCPU}=n_{c}^{VCPU}/n_{0}^{VCPU},r_{c/0}^{RAM}=n_{c}^{RAM}/n_{0}^{RAM},$

3:$r_{c/0}^{Storage}=n_{c}^{Storage}/n_{0}^{Storage}$

4:Find the minimum ratio:

5:$r_{min}=min(r_{c/0}^{VCPU},r_{c/0}^{RAM},r_{c/0}^{Storage})$

6:Find the maximum ratio:

7:$r_{max}=max(r_{c/0}^{VCPU},r_{c/0}^{RAM},r_{c/0}^{Storage})$

8:Compute the deviation: $d=r_{max}/r_{min}$

9:if $d<d_{max}$ then

10: $Advice=^{\prime}random^{\prime}$

11:else

12: Find the parameter corresponding to the maximum ratio: $P_{max}$

13: $Advice=P_{max}$

14:end if

Algorithm 3.a Provider agent’s algorithm for selecting the parameter to reduce
(Case a)

Input:
$n_{0}^{VCPU},n_{0}^{RAM},n_{0}^{Storage}$: the quantities of VCPU, RAM,
storage in the original requirement;
$c^{VCPU},c^{RAM},c^{Storage}$: the amount of change per round;
Output:
$P_{reduce}$: the parameter the provider agent selects to reduce;

1:Compute the number of rounds each parameter needs:

2:$rd^{VCPU}=n_{0}^{VCPU}/c^{VCPU},rd^{RAM}=n_{0}^{RAM}/c^{RAM},$

3:$rd^{Storage}=n_{0}^{Storage}/c^{Storage}$

4:Compute the total number of rounds:

5:$rd^{total}=rd^{VCPU}+rd^{RAM}+rd^{Storage}$

6:Compute the probability of each parameter:

7:$pb^{VCPU}=rd^{VCPU}/rd^{total},pb^{RAM}=rd^{RAM}/rd^{total},$

8:$pb^{Storage}=rd^{Storage}/rd^{total}$

9:According to the above probability, randomly select a parameter to reduce:
$P_{reduce}$

Algorithm 3.b Provider agent’s algorithm for selecting the parameter to reduce
(Case b)

Input:
$n_{0}^{VCPU},n_{0}^{RAM},n_{0}^{Storage}$: the quantities of VCPU, RAM,
storage in the original requirement;
$c^{VCPU},c^{RAM},c^{Storage}$: the amount of change per round;
$Advice$: the advice sent from the client agent;
Output:
$P_{reduce}$: the parameter the provider agent selects to reduce;

1:if $Advice=^{\prime}random^{\prime}$ then

2: Jump to Algorithm 3.a

3:else

4: $P_{reduce}=Advice$

5:end if

Algorithm 3.c Provider agent’s algorithm for selecting the parameter to reduce
(Case c)

Input:
$n_{0}^{VCPU},n_{0}^{RAM},n_{0}^{Storage}$: the quantities of VCPU, RAM,
storage in the original requirement;
$c^{VCPU},c^{RAM},c^{Storage}$: the amount of change per round;
$Advice$: the advice sent from the client agent;
$pr^{VCPU},pr^{RAM},pr^{Storage}$: the priority of each parameter;
Output:
$P_{reduce}$: the parameter the provider agent selects to reduce;

1:if $Advice=^{\prime}random^{\prime}$ then

2: Compute the number of rounds each parameter needs:

3: $rd_{0}^{VCPU}=n_{0}^{VCPU}/c^{VCPU},$

4: $rd_{0}^{RAM}=n_{0}^{RAM}/c^{RAM},$

5: $rd_{0}^{Storage}=n_{0}^{Storage}/c^{Storage}$

6: Compute the relative adjusted number of rounds:

7: $rd^{VCPU}=rd_{0}^{VCPU}/pr^{VCPU},$

8: $rd^{RAM}=rd_{0}^{RAM}/pr^{RAM},$

9: $rd^{Storage}=rd_{0}^{Storage}/pr^{Storage}$

10: Compute the total number of rounds:

11: $rd^{total}=rd^{VCPU}+rd^{RAM}+rd^{Storage}$

12: Compute the probability of each parameter:

13: $pb^{VCPU}=rd^{VCPU}/rd^{total},pb^{RAM}=rd^{RAM}/rd^{total},$

14: $pb^{Storage}=rd^{Storage}/rd^{total}$

15: Randomly select $P_{reduce}$ according to the above probability

16:else

17: $P_{reduce}=Advice$

18:end if