Preference-based resource reservation method for resource allocation in full distributed systems

Abstract

Multiagent Resource Allocation (MARA) is a field to find out solutions that distribute a set of resources among agents. Heretofore, lots of utility- and reputation-based approaches have been proposed. In this paper, we develop a preference-based resource reservation approach for resource allocation in a system that consists of entirely selfless agents. Preference, defined as the satisfaction of required resources, has a crucial impact on resource allocation. The importance degree is also adopted to represent the extent to which a particular attribute is needed. In the system, agents communicate with semi-local friends to exchange information as well as reserving resources. Finally, a confirmation or cancelation message is sent to obtain or release the reserved resources. Numerical examples are given to show the rationality and effectiveness of the proposed method.

Keywords

Multiagent system resource allocation reservation preference

1. Introduction

Resource allocation is a crucial concern in the fields of both computer science and economics. Computer scientists often concentrate on how to find a satisfying distribution, while economists usually care about how to make a beneficial allocation [7]. With the rapid development of agents, the multiagent system (MAS) is an appropriate tool to emphasize the issues in resource allocation. MAS consists of multiple agents and their environment. Typically, agents refer to computer programs that can act on behalf of humans, robots, objects, or human-object teams. The field which illustrates the allocation of resources in MASs is known as MARA.

MARA is defined as the process of distributing a set of resources among various agents [7, 35]. Generally, there are two main models in MARA, namely centralized and distributed models [4, 14, 18, 33]. In a centralized approach, one of the agents is appointed as the controller taking charge of collecting individuals’ preferences and making optimal decisions [26]. Compared with centralized approaches, agents are of equal roles in distributed approaches. Meanwhile, they could only realize the information or knowledge about their friends locally [13, 29]. In practice, distributed approaches are more applicable in many large-scale distributed environments, for instance, train ticket booking. Meanwhile, distributed methods are more economically as a centrale controller is no longer required [23]. Also, distributed approaches are more humanized and ensure privacy for individuals in the system. As a result, distributed systems have a wide range of applications, including industrial procurement, earth observation satellites, manufacturing systems, and grid computing. In this paper, we study MARA in a fully distributed environment.

The existing researches related to negotiations and coordination mechanisms in MARA are numerous. Generally, these approaches might firstly be Market-based approaches where service demanders and providers are of peer roles as clients and suppliers in markets. Auctions, contract mechanisms, games theory are often adopted [19]. Cui et al. propose a game theory-based negotiation method for task allocation in multiple robots’ systems [12]. Scheléen and Pink illustrate a method for pursuing the required resources where clients can make reservations through agents responsible for advance admission control [39]. Lewis et al. present a novel market-based approach that is inspired by the retail market for MARA [25]. After that, agent-based approaches play a critical role in resource allocation where resources are distributed among agents; they dialogue and exchange resource information as well as resources autonomously. Usually, agents acknowledge what resources their friends have occupied and make decisions based on the perceived information. Savla and Frazzoli consider a novel dynamical queue approach to intelligent task management for human operators [38]. They consider a model of a dynamical queue, where the service time depends on the server utilization history. Vig and Adams propose a heuristic-based coalition formation algorithm to operate in precedence ordered cooperative environments [40]. Afterward, society-based approaches are also essential. Such as coalition formation, group mechanisms and so on [27, 42, 1]. In the literature [1], a generic model for task/resource-constrained multiagent stochastic planning that analyzes dependent task/resource. Ye et al. propose a multiagent coalition formation-based energy dispatch mechanism [42]. Finally, some other approaches where nodes negotiate and coordinate mutually for their goals, where trust, social welfare, preference are taken into account. Nongaillard and Mathieu provide an adaptive, anytime, and scalable algorithm to hold efficient egalitarian negotiations for discrete and indivisible resource allocation [32]. The literature [8] studied a framework for MARA where agents negotiate autonomously. They give particular consideration to scenarios where the preferences of agents are modeled in terms of k-additive utility functions. Chevaleyre et al. studied the convergence properties for distributed mechanisms for allocating indivisible goods when used as fair division procedures [10]. Trust has a significant impact on agents’ decision making, which intuitively reflects the risk level when one agent relay on the provided information or resource of the particular agent for the fulfillment of their goals. Du et al. investigated the trust model in online social media networks where individuals share options, communicate, and provide services [15]. In this paper, we adopt agent-based resource reservation approaches combined with the flexible preferences for resource allocation.

Resources in MARA have a lot of characters when concerning the resource types. For example, the shared resources could be visible or invisible. On the other side, some resources could be better featured by the allocation models, such as the property of being sharable or not relies mainly on the allocation procedures [3, 41, 44, 10]. Thus far, MARA researchers have devoted considerable efforts to resource allocation of indivisible and nonsharable resources [7, 10]. In this setting, resources are distributed among agents, and acquaintances may offer compensations to make use of some resources. In the literature [2], Airiau and Endriss studied a particular MARA system where resources are indivisible and nonsharable. In their model, agents share resources also share the control of those resources, and they prove the existence of distributed protocol that leads to optimal social welfare. In this paper, we study a model where agents are wholly selfless and cooperative, and resources are stable and indivisible. Agents control several resources, and they share resources by sharing the utilization of the resources rather than sharing its control to the particular resources. Once a demander accomplishes its tasks, the obtained resources are returned to its owner agent.

Preferences express the relative or absolute satisfaction of an individual when faced with a choice between different alternatives [7, 36]. In MARA, these alternatives are of all potential allocation of resources. A preference structure represents an agent’s preference or demands over all the choices. There are many mathematical representations regarding preference management, especially in decision theory [11, 16, 28]. Namely, preference representation can be a cardinal preference structure that adopts the utility function to evaluate various bundles of alternatives. In the ordinal preference structure, a comparison relationship, ‘Not worse than’ represented by ‘ $\preceq$ ’ is used to show preference relationship. Meanwhile, all alternatives are classified as “Like” and “Dislike” sets to illustrate their preference in binary preference approaches. Lastly, the fuzzy preference structure, which has drawn various researchers’ eyes these years utilizes a fuzzy relationship to express the preference degree of available alternatives. These mathematical models have widely been applied in artificial intelligence [34], in fields spanning from recommender systems to automatic planning, from non-monotonic reasoning to computational social choice and algorithmic decision theory. In MARA, preference also has crucial impacts on resource allocation. Ana-Maria Nogareda, Juan I. Cano used preference to solve educational resource allocation [6, 31]. Saito and Sugawara allocated resources based on multiple bid declaration with preference [37]. Iijima et al. analyzed task allocation based on social utility and incompatible individual preference [17]. However, fuzzy and qualitative approaches are rarely adopted compared to cardinal preference structure and ordinal preferences in MARA [9, 22]. One of the most intuitive representations of a utility function is bundle form, which assigns a non-zero to all possible bundles of alternatives. However, it might be up to $2^{n}$ choices for overall representation that leads to severe computational problems. Chevaleyre et al. illustrated K-additive, which is particularly suitable in the preference representation where agents are unsure about their accurate preferences [9, 8]. These utility functions are often regarded as the standard when optimizing social welfare. However, agents’ evaluation towards received resources also plays an essential role, and works relate to fuzzy preference still need trial and error.

In this paper, uncertainty in preference representation is emphasized for the allocation of resources. The generated resource requirements demand some resources rather than a fixed number. Moreover, flexibility in required characters is also stressed during the distribution. In the proposed dynamic and distributed systems, an agent communicates with its acquaintances for needed resources. Meanwhile, their friends reserve needed resources cooperatively. The rest of the paper is organized as follows. Some preliminaries and explanations used in this paper are exhibited in Section 2, including dynamic and distributed network structure and resource representation. In Section 3, the proposed uncertain preference-based approach for resource allocation are detailed stressed. The simulation and results are shown in Section 4 to show the effectiveness of the proposed method. Discussions on the results are presented in Section 5. Conclusion and future works conclude the paper in the last part.

2. Preliminaries and explanation

In this part, some necessary concepts and definitions of distributed network architecture, agents, friends, and resources are detailed introduced and explained.

2.1 Distributed network architecture

Distributed network architecture consists of various computing structures that are modeled as intelligent agents. They are described schematically as abstract functions that are similar to computer programs. Agents are capable of taking actions and making decisions on behalf of users or other entities. In this paper, a dynamic social network $G$ , where nodes represent agents, and edges illustrate the agents’ friendships are adopted. Some explanations are given as follows,

1.
$A:\{a_{1},a_{2}\ldots a_{i}\ldots\}\Rightarrow$ Set of agents (nodes);
2.
$\forall a_{i}\in A,F_{i}:\{a_{1},a_{2}\ldots a_{\textit{card}(F_{i})}\}\Rightarrow$ Finite set of friends to $a_{i}$ . The subscripts do not have to be continuous;

Agents in the dynamic distributed network have several operations. To make it clear, we adopt a random social network shown in Fig. 1 for a detailed explanation.

Figure 1.
A social network with 8 nodes: Two connected nodes show that they are friends.

1.
An agent can join in the system successively. It makes friends with all other agents by probability $p_{1}$ . As is shown in Fig. 1, another agent $a_{x}$ joins in the system and tries to make friends with other members. It is capable of demanding and reserving resources when it has friends.
2.
The long-term lived agents in the system can make new friends occasionally by probability $p_{2}$ . However, agents are only allowed to interact with others by the referrals through their adjacent friends. For instance, Olivia may make friends with all other agents except Kevin as no one may recommend Olivia to Kevin directly in Fig. 1.
3.
An agent who is not in interaction may break up relationships by probability $p_{3}$ . It flees the system when it no longer has any friends.

2.2 Resources

As explained, various resources are distributed in intelligent agents that are capable of implementing different proposals. However, one of the challenges is about what a resource is and how to represent a resource in MARA.

In our opinions, resources relate to attributes and the corresponding values. An attribute is defined as a quality or feature regarded as a natural or inherent part of someone or something. When representing a resource, the first attribute refers to the resource type, which defines the resource area. The resource area discussed in this paper can be transportation, sport, stationery, and so on. The rest attributes are used for the detailed description. For instance, languages, subjects, and authors are often used to describe a book. Thus, a detailed resource consists of resource attributes and the exact values. In this paper, we discuss physical resource allocation in real life, such as bikes, computers, books, and houses. Thus, resources can be formally summarized as follows.

1.
$R:\{r_{1},r_{2}\ldots r_{j}\ldots r_{\textit{card}(R)}\}\Rightarrow$ Finite set of resource types;
2.
$\forall r_{j}\in R:c_{r_{j}}:\{c_{(j,1)},c_{(j,2)}\ldots c_{(j,k)}\ldots c_{(j% ,\textit{card}(c_{r_{j}}))}\}\Rightarrow$ Finite set of characters to resource type $r_{j}$ and $c_{(j,k)}$ represents the $k$ th character;

Corresponding, to the agent $a_{i}$ , it owns several resources and the correspondent characters can be represented by

1.
$R_{i}:\{r_{1},r_{2}\ldots r_{j}\ldots r_{\textit{card}(R_{i})}\}\Rightarrow$ Finite set of all acquired resource types;
2.
$C_{i}=\bigcup_{j=1}^{\textit{card}(R_{i})}(c_{r_{j}})\Rightarrow$ Finite union set of all characters to the agent $a_{i}$ .

As is explained, resources with distinguishing attribute values are placed among agents. To the agent $a_{i}$ , all its resource types $R_{i}$ , the corresponding characters $C_{i}$ and their values are summarized in the following list,

1.
$\{Rt_{1}=r_{1},c_{(1,1)}=\textit{value}_{(1,1)},c_{(1,2)}=\textit{value}_{(1,2% )}\ldots c_{(1,k)}=\textit{value}_{(1,k)}\}$
2.
$\{Rt_{2}=r_{2},c_{(2,1)}=\textit{value}_{(2,1)},c_{(2,2)}=\textit{value}_{(2,2% )}\ldots c_{(2,k)}=\textit{value}_{(2,k)}\}$
3.
…
4.
$\{Rt_{i}=r_{i},c_{(i,1)}=\textit{value}_{(i,1}),c_{(i,2)}=\textit{value}_{(i,2% )}\ldots c_{(i,k)}=\textit{value}_{(i,k)}\}$
5.
…

where $Rt_{i}$ means the $i$ th resource type, $\textit{value}_{(i,k)}$ denotes the exact value to the character $c_{(i,k)}$ .

.

For instance, an agent has two completely the same bikes and one book, the bikes are blue and tall while the book written in English is about ‘History’. Here $R_{i}=\{\textit{bike},\textit{book}\}$ and $C_{i}=\{\textit{color},\textit{size},\textit{language},\textit{theme}\}$ . Then its resources list can be rewritten as,

1.
$\{Rt_{1}=\textit{bike},\textit{Color}=\textit{blue},\textit{size}=\textit{tall}\}$
2.
$\{Rt_{2}=\textit{bike},\textit{Color}=\textit{blue},\textit{size}=\textit{tall}\}$
3.
$\{Rt_{3}=\textit{book},\textit{Language}=\textit{English},\textit{Theme}=% \textit{History}\}$

3. Fuzzy preference requirements for resource sharing in distributed and dynamic systems

In this section, we propose an uncertain preference-based resource reservation approach for resource allocation in dynamic and distributed systems. The proposed method is analyzed from mainly two aspects, the preference representation, and resource allocation.

3.1 Proposed uncertain resource requirements

Agents in the fully distributed systems send acquaintances messages to ask for resources. A message mainly consists of several needed resources, and each resource contains attributes and values as well as their degrees of importance. To the agent $a_{i}$ , the set of needed resources is represented by $R^{\prime}_{i}(R^{\prime}_{i}\subseteq R)$ while the set of characters is represented by $C^{\prime}_{i}$ correspondingly. For the exact resource type $r^{\prime}_{j}\in R^{\prime}_{i}$ , we adopt interval numbers and importance degree to represent the details.

(Interval numbers).

An interval number is a set of real numbers with the property that any number that lies between the two numbers in the set is also included in the set, where,

$\displaystyle\left[x_{r^{\prime}_{j}}^{-},x_{r^{\prime}_{j}}^{+}\right]=\left% \{x|x_{r^{\prime}_{j}}^{-}\leqslant x\leqslant x_{r^{\prime}_{j}}^{+}\right\}.$ (1)

In this paper, interval numbers are used to represent the needed amount of different resource types. When an agent generates a resource requirement, it needs a minimum number of the resources for the task implement. However, if the obtained resource amount reaches the maximum value, the task can be perfectly accomplished.

(Degree of importance).

The degree of importance is defined as the fact of being important, or the degree to which something or some characters are important. In this article, we adopt the degree of importance $d_{x}$ to represent the degree to which some detailed required resources or some necessary characters are important, where,

$\displaystyle d_{x}\in[0,1]$ (2)

$d_{x}$ is closer to 1, the resource type or character is more important.

(Resource requirement message).

A complete requirement consists of several needed resources. Each resource comprises attributes and the exact values together with the degrees of importance. Meanwhile, deadlines and needed processing time are also included for an individual required resource.

To simplify the representation, we use a two-element tuple $\langle[x_{r^{\prime}_{j}}^{-},x_{r^{\prime}_{j}}^{+}],d_{r^{\prime}_{j}}\rangle$ to represent the resource type, the needed amount and the degree of importance. The first element $[x_{r^{\prime}_{j}}^{-},x_{r^{\prime}_{j}}^{+}]$ shows the required amount for the resource $r^{\prime}_{j}$ . It is to say, an agent demands resource $r^{\prime}_{j}$ and the minimum amount is $x_{r^{\prime}_{j}}^{-}$ which must be 100% met. At the same time, if the agent receives $x_{r^{\prime}_{j}}^{+}$ resource $r^{\prime}_{j}$ , it would be 100% degree satisfied with the obtained resources. The degree of importance to the amount which is in the range of $[x_{r^{\prime}_{j}}^{-},x_{r^{\prime}_{j}}^{+}]$ is $d_{r^{\prime}_{j}}$ . Similarly, to a detailed character, a two elements tuple which shows the exact value and its degree of importance is adopted. Concurrently, the deadline to obtain the required resource and the processing time are represented by $dl_{r^{\prime}_{j}}$ and $pt_{r^{\prime}_{j}}$ respectively. Thus, to the agent $a_{i}$ , all its required resource $R^{\prime}_{i}$ , their corresponding characters and values as well as degrees of importance are represented by matrix $MR(i)$ as follows,

$\displaystyle\bordermatrix{&\textit{resource∼{}type}&c_{1}&\cdots&c_{k}&\cdots% &dl&\textit{ptime}\cr r^{\prime}_{1}&\langle[x_{r^{\prime}_{1}}^{-},x_{r^{% \prime}_{1}}^{+}],d_{r^{\prime}_{1}}\rangle&\langle c_{(1,1)},d_{c_{(1,1)}}% \rangle&\cdots&\langle c_{(1,k)},d_{c_{(1,k)}}\rangle&\cdots&dl_{r^{\prime}_{1% }}&pt_{r^{\prime}_{1}}\cr r^{\prime}_{2}&\langle[x_{r^{\prime}_{2}}^{-},x_{r^{% \prime}_{2}}^{+}],d_{r^{\prime}_{2}}\rangle&\langle c_{(2,1)},d_{c_{(2,1)}}% \rangle&\cdots&\langle c_{(2,k)},d_{c_{(2,k)}}\rangle&\cdots&dl_{r^{\prime}_{2% }}&pt_{r^{\prime}_{2}}\cr&\cdots&&&\cdots&\cr r^{\prime}_{j}&\langle[x_{r^{% \prime}_{j}}^{-},x_{r^{\prime}_{j}}^{+}],d_{r^{\prime}_{j}}\rangle&\langle c_{% (j,1)},d_{c_{(j,1)}}\rangle&\cdots&\langle c_{(j,k)},d_{c_{(j,k})}\rangle&% \cdots&dl_{r^{\prime}_{j}}&pt_{r^{\prime}_{j}}\cr&\cdots&&&\cdots&\cr},$ (3)

As is explained in the above parts, we are discussing indivisible and non-sharable resource allocation. Therefore, detailed requirements can also be rewritten in a single resource list. An individual requires resources that consist of attributes and the corresponding values as well as the degree of importance. At the same time, deadline and processing time are also necessary to obtain a needed resource. The details are shown as follows,

$\{(Rt_{1}=r^{\prime}_{1},d_{r^{\prime}_{1}}),(c_{1}=c_{(1,1)},d_{c_{(1,1)}}),(% c_{2}=c_{(1,2)},d_{c_{(1,2)}}),\ldots(c_{k}=c_{(1,k)},d_{c_{(1,k)}})\ldots dl_% {r^{\prime}_{1}},pt_{r^{\prime}_{1}}\}$

$\{(Rt_{2}=r^{\prime}_{2},d_{r^{\prime}_{2}}),(c_{1}=c_{(2,1)},d_{c_{(2,1)}}),(% c_{2}=c_{(2,2)},d_{c_{(2,2)}}),\ldots(c_{k}=c_{(2,k)},d_{c_{(2,k)}})\ldots dl_% {r^{\prime}_{2}},pt_{r^{\prime}_{2}}\}$

…

$\{(Rt_{j}=r^{\prime}_{j},d_{r^{\prime}_{j}}),(c_{1}=c_{(j,1)},d_{c_{(j,1)}}),(% c_{2}=c_{(j,2)},d_{c_{(j,2)}}),\ldots(c_{k}=c_{(j,k)},d_{c_{(j,k)}})\ldots dl_% {r^{\prime}_{j}},pt_{r^{\prime}_{j}}\}$

…

3.2 Distributed approach for resource sharing

In the proposed system, agents act as both resource providers and demanders, or both simultaneously. When a requirement is generated, the resource demander firstly sends it to its friends.

Distributed network architecture has a significant influence on the efficiency of resource allocation. In this paper, agents have dynamic numbers of friends in the system and each time, an agent sends its requirements to friends one after another. If the friend $a_{j}$ who owns some of the needed resources, it is to say, their required attributes whose degrees of importance are 100% are all included, and simultaneously, the state of the owned target resources are “Free” (Not reserved) or “Not Free” but will be “Free” before the deadline, the friend acts collaboratively and reserves the resource automatically. Thus, the target resource is no longer available before the confirmation or cancelation messages sent by the resource demander. Afterward, a response $\textit{reply}(a_{j})$ consists of the reserved resource is sent back to the demander. If the resource demander is satisfied with the degree of satisfaction (Discussed in the next subsection) obtained from the requirement and reserved resource, the agent removes the required resource which has been booked and sends the rest requirements to other friends. At the same time, the historical reserved resources are free again and available for other resource demands. Otherwise, it sends the unmodified requirement to a next friend to pursue a more satisfying resource.

Most of the time, all the required resources can be reserved before having interacted with all its friends. In this situation, the diffusion implementation is reduced by permitting agents to communicate with a subset of its friends. However, all the needed resources may not be reserved, even all its friends act selfless and generous enough because agents in the system have limited resources. Under this circumstance, the demander cheekily asks its friends to send requirements to their acquaintances sequentially. It is to say, the demander has to interact with the acquaintance of its friends if not all the needed resources are being reserved.

After the interaction, if the demander is content with the egalitarian degree of satisfaction calculated from the reserved resources, the demander sends a confirmation message to its acquaintances to obtain the reserved resources. Thus, the resources are decremented at the friends concerned and incremented at the demander. Otherwise, a cancelation message is sent to release the resources they have possibly reserved. Of course, the demander cannot implement its task because of not having received enough resources.

The proposed distributed approach for resources reservation is summarized in Algorithm 3.2. As is shown, $S_{i}$ and $\overline{S_{i}}$ are exclusive sets consist of acquaintances (The set of its friends and the friends of its friends) to the agent $a_{i}$ , they represent the friends who have and have not communicated respectively. After communication, an updated resource requirement is obtained.

[h] Resource reservation (RB(MR(i)))[1] Input: $a_{i}$ , $F_{i}$ , $MR(i)$ ; Output: Updated $MR(i)$ ; $F_{i}=S_{i}\bigcup\overline{S_{i}}$ $a_{i}$ generates a resource requirement $MR(i)$ (see Eq. (3)) card( $S_{i}$ ) $=$ 0 Or $MR(i)=\phi$ Break; Send $MR(i)$ to $a_{\beta}$ randomly, $a_{\beta}\in S_{i}$ $a_{\beta}$ owns satisfied and available resources before the deadline Reserve the resource for $a_{i}$ & Send back the reserved resource; $S_{i}=S_{i}\backslash a_{\beta}$ , $\overline{S_{i}}=\overline{S_{i}}\cup\{a_{\beta}\}$ ; $a_{i}$ is satisfied with the reserved resource Free the reserved resource; Remove the reserved required resource;

As described above, a confirmation or cancelation message is finally sent when the interaction is completed. The proposed approach for resource sharing in dynamic and distributed systems is concluded in Algorithm 3.2 as follows. The dynamic system, resource reservation and confirmation or cancelation messages are all included.

[h] Distributed approach for resource sharing (CCM(MR’(i))[1] Input: $G$ , $A$ , $p_{1}$ , $p_{2}$ , $p_{3}$ ; Output: Confirmation or cancelation messages; True Update the dynamic system $G$ ; $a_{i}\in A$ has resource requirements $MR(i)$ Call for Algorithm 3.2 to reserve needed resources; Return updated $MR^{\prime}(i)$ ; The demander is satisfied with the egalitarian degree of satisfaction Send confirmation messages Send cancelation messages;

3.3 Satisfaction analysis

An acquaintance reserves the required resources for the demander as well as sending the reserved resource back as a response. The demander decides to accept the reserved resources or not according to the individual degree of satisfaction. As the resources requirement is shown, the degree of importance is adopted to show the importance of different attributes. Firstly, the reserved resource will be taken into account only when it owns the required attributes whose importance degree are 100%. Then, the demander will be more contented if more characters whose importance degree in the range of (0,100%) are involved. For a generated resource requirement represented by $\{(r^{\prime}_{j},d_{r^{\prime}_{j}}),(c_{(j,1)},d_{c_{(j,1)}}),(c_{(j,2)},d_{% c_{(j,2})})...(c_{(j,k)},d_{c_{(j,k)}})\}$ . Resource providers have reserved some resources for implementing the request. We use a variable $I_{r^{\prime}_{j}}(c)$ to describe the ownership of an exact character $c_{(j,k)}$ by the reserved resource $r_{j}$ as follows,

$\displaystyle I_{r_{j}}(c_{(j,k)})=\left\{\begin{array}[]{ll}1,&c_{(j,k)}\in r% _{j},\\ 0,&c_{(j,k)}\not\in r_{j};\\ \end{array}\right.$ (4)

If the reserved resource $r_{j}$ owns the character $c_{(j,k)}$ , the value of indicator function is defined as 1, otherwise 0. Meanwhile, we regard the degrees of importance as weights.

(Individual degree of satisfaction to a required resource).

As a result, the degree of satisfaction to a single required resource is defined as,

$\displaystyle s(r_{j})=\frac{\sum_{k=1}^{\textit{card}(C_{i})}(d(c_{(j,k)})*I_% {r_{j}}(c_{(j,k)}))}{\sum_{k=1}^{\textit{card}(C_{i})}(d(c_{j,k}))}$ (5)

where $d(c_{(j,k)})$ is the degree of importance of character $c_{(j,k)}$ , $I_{r_{j}}(c_{(j,k)})$ is the indicate function.

(Egalitarian degree of satisfaction).

As is explained, a requirement may contain several individual resources, here we define an egalitarian degree of satisfaction as follows,

$\displaystyle ds_{e}(MR(i))=\min\{s(r_{j})|r_{j}\textit{ is the reserved % resource}\}$ (6)

.

$a_{1}$ needs two books, the requirements are {(Book, 100%), (English, 70%), (History, 80%), (Well-printed, 60%)} and {(Book, 50%), (English, 70%), (History, 80%)}. Two acquaintances reserved two resources; a French history book is reserved for the first resource while an English history book is reserved for the second. As a result, for the first resource, the degree of satisfaction is

$\displaystyle s(r(1))=\frac{1*100\%+0*70\%+1*80\%+0*60\%}{100\%+70\%+80\%+60\%% }=\frac{1.8}{3.1}$

similarly, $s(r(2))=\frac{50\%*1+70\%*1+80\%*1}{50\%+70\%+80\%}=100\%$ . Finally, the egalitarian degree of satisfaction to the generated requirement can be calculated as

$\displaystyle ds_{e}(MR(1))=\min\left\{\frac{1.8}{3.1},100\%\right\}=\frac{1.8% }{3.1}$

4. Numerical example and simulations

In this section, an illustrative numerical example is firstly given to exhibit the implementation of the proposed method. Next, some comparisons and discussion are provided to show the effectiveness of the proposed method.

4.1 Numerical example for resource reservation

In this paper, a random network $G(n,p)$ is generated by Erös-Rényi model to portray the distributed network architecture. Each edge is included in graph $G$ with probability $p$ independent from every other edge during the initialization phase. Here, $G(40,0.2)$ is adopted to generate the social network, and the initial distributed network structure is shown in Fig. 2.

Figure 2.

The distributed network structure.

In the network, red nodes represent the 40 agents and blue lines which connect two nodes indicate that the two agents are friends. According to the topological structure, node 39 has only four extra edges connected, i.e., as defined in Section 2.1, $\textit{card}(F_{39})=$ 4. For node 2, 4, 15, 21 and 24, they all have 11 friends. The random network is regarded as a social network and it takes actions described in Section 2.1, $p_{1}=p_{2}=p_{3}=5\%$ are used at every time instant.

We suppose that the resource types in this paper are computers, books, bikes and umbrellas, i.e., $R:\{\textit{computer},\textit{book},\textit{bike},\textit{umbrella}\}$ . Their characters and detailed values defined in Section 2.2 are described as follows,

Sharing computers: $\{\textit{Brands}$ $\langle$ Apple, Lenovo, HP, Dell, Other Brand $\rangle$ ; RAM $\langle$ 4G, 8G, 16G, Other RAM $\rangle$ ; Use condition $\langle$ Old, New, Other condition $\rangle\}$ ;

Sharing books: $\{\textit{Theme}$ $\langle$ Science, Culture, Sports, History, Mathematics, Other Book $\rangle$ ; Language $\langle$ English, French, Chinese, Other language $\rangle$ ; Size $\langle$ Big size, Middle size, Small size $\rangle\}$ ;

Sharing bikes: $\{$ Operators $\langle$ Gobee, Ofo, Mobike, Vlille, Other Bike $\rangle$ ; Colors $\langle$ Yellow, Red, White, Blue, Others $\rangle$ ; Basket $\langle$ With, Without $\rangle\}$ ;

Sharing umbrella: $\{\textit{Types}$ $\langle$ Classical, Foldable, Other umbrella $\rangle$ ; Colors $\langle$ Black, Colorful, Transparent, Other color $\rangle\}$ ;

Agents own one to four different resources which have distinguishing characters. Corresponding, an agent demands one to four resources each time. Deadlines and processing times are in the range of [1, 2.5] and [2.5, 5] unit of time. In the first round, $a_{2}$ generates a resource requirement, its demands are as follows:

{(books, 100%), (History, 58%), (English, 93%), (Middle size, 85%), (dl: 1.0), (pt: 3.5)}

{(computers, 56%), (Dell, 95%), (8G, 58%), (Other condition, 94%), (dl: 2.5), (pt: 4.5)}

Judging from its requirements, the agent $a_{2}$ needs two resources, and one of them must be a book, it is better if it is a Middle-size English book about History. It needs to make use of the book for 3.5 units of time and the deadline to obtain the resource is 1 unit of time. Then the agent $a_{2}$ communicates by the methodology proposed in Algorithms 3.2 and 3.2. Once its acquaintance owns some resource that satisfies its requirements. Its friend reserves it for the agent $a_{2}$ cooperatively and sends back the reserved resource. If $a_{2}$ is content with the individual degree of satisfaction obtained from the required and reserved resource, the needed resource is removed, and the agent $a_{2}$ continues asking for the unreserved resources. Finally, both the two resources have been reserved. $a_{2}$ is satisfied with the egalitarian degree of satisfaction, and a confirmation message is sent to receive the resources. To the end, $a_{4}$ reserves it an English Middle size book, and $a_{17}$ reserves another resource. However, more than one agent has reserved the needed resources for the agent $a_{2}$ during interactions, and the degrees of satisfaction of the two individual resources are shown in Fig. 3.

Figure 3.

The individual degree of satisfaction changes with reserved times. a: The satisfaction degrees when demanding the book. b: The satisfaction degrees when demanding the computer.

As is shown in Fig. 3, two subgraphs denote the degree of satisfaction about the two resources, respectively. Take Fig. 3b as an example, it shows the changes of satisfaction to resource demand {(Computer, 56%), (Dell, 95%), (8G, 58%), (Other condition, 94%), (dl: 2.5), (pt: 4.5)}. The agent $a_{2}$ needs a computer of Dell whose RAM is 8 G. When it communicates with its acquaintances, five agents have reserved a resource for the agent $a_{2}$ . Finally, the agent $a_{2}$ chooses the most satisfied resource, and it is $a_{26}$ who allocates the required resource to the agent $a_{2}$ and the degree of satisfaction is 100%.

4.2 Comparisons

For detailed illustration, we provide a comparative study between preference represented by the degree of importance and fixed real numbers when asking for resources. To the best of our knowledge, nearly all the required resource amount representations in MARA rely on fixed real numbers. Most of the time, utility functions are used to stress quality requirements rather than demanded quantity [8, 30]. In [22], the preferences consist of a single propositional formula that represents the agent’s goal and its numerical weights. The proposals can be accepted or rejected are taken into accounted in [20]. However, uncertainty is rarely adopted in preference representation.

For this purpose, we use the numerical example discussed in Section 4.1 to illustrate the degrees of satisfaction between the preference denoted by uncertain information and fixed numbers. Forty agents exist in the system, and they respectively acquire one to four different resources. A demand consists of one to four individual resources. In the proposed method, the degrees of importance to fixed characters are a percentage in [0, 100%] while they are 100% in fixed resources requirement. For instance, $a_{1}$ needs two resources represented by uncertainty presented as follows,

1.
{(computer, 100%), (Lenovo, 100%), (16 $G$ , 82%), (13.3 Inch, 60%), (dl: 1.5), (pt: 3)}
2.
{(bike, 100%), (Ofo, 90%), (child, 100%), (Red, 66%), (dl: 1.0), (pt: 4)}

On the contrary, an agent needs resources with fixed character values are as follows.

1.
{(computer, 100%), (Lenovo, 100%), (16 G, 100%), (13.3 Inch, 100%), (dl: 1.5), (pt: 3)}
2.
{(bike, 100%), (Ofo, 100%), (child, 100%), (Red, 100%), (dl: 1.0), (pt: 4)}

These two resource requirements do exist in real life. Most of the time, agents show the indispensable characters (same as the second requirements). So the received resource owns all the listed characteristics. However, a resource requirement can be more flexible. It is to say, some characters can be needed but not necessary. As is shown in the first requirement, the agent needs a computer of ‘Lenovo,’ and an agent usually does in the previous works. What’s more, the computer’s RAM is 16 G, and the scream size is 13.3 inches could be better. As a result, the two requirements are adopted to analyze the degree of satisfaction to show the efficiency of uncertain preferences.

Figure 4.
The egalitarian degree of satisfaction and total interaction times of the 40 requirements whose preference are denoted by degree of importance.

In Fig. 4, the error bars show the egalitarian degree of satisfaction of 40 demands. The redpoint equals ‘0’ means that the agent does not receive all-satisfying resources. The error of the corresponding point indicates the difference between the average degree of satisfaction and the egalitarian degree of satisfaction. As calculated, the average degree of satisfaction is 81.5% of the 40 resource requirements. In the second subgraph, the red lines indicate the total interaction times of each requirement, averagely agent can receive satisfied resources after 26.10 interactions. As a comparison, the requirement denoted by fixed numbers is considered. The egalitarian degree of satisfaction and number of interacted agents are shown in Fig. 5. As we can see, most of the requirements can not be satisfied, while the average interacted agents are 32.17. Therefore, a resource requirement can be represented by the degree of importance, and it contents agents when demanding resources.

Figure 5.
The egalitarian degree of satisfaction and total interaction times of the 40 requirements whose preference are with fixed attributes.

5. Discussion

In the section as mentioned above, an original social network that consists of 40 agents is adopted for resource allocation. In the resource requirements representation part, resource demanders have fuzzy preferences, for both resource quantity and quality. We illustrate its effectiveness by analyzing the satisfaction of the obtained resource. The results compared with the preference, which is represented by fixed numbers (Utility function), suggests that the proposed method can help resource demanders obtain needed resources effectively.

In this paper, we propose an uncertain preference-based resource reservation method for MARA in a fully distributed systems. Agents communicate with each other to pursue more satisfying resources. There are some related works to the proposed method. An efficiency analysis-based resource allocation method is proposed in [21]. The centralized unit is quite impressive in maximizing the total amount of outputs produced by allocating required resources to individuals. A formal interactive approach based on data envelopment analysis and multiple-object programming to find optimal allocation plan. However, the centralized approaches have its limitation in resource allocation compared with decentralized methods. In this paper, agents in the distributed systems act altruistically and cooperatively. They reserve whatever they own that satisfies their friends’ demands. Moreover, agents in distributed systems cooperate mutually for resource allocation is more applicable in real life. In [24, 5], a formal model for indivisible goods resource sharing without monetary compensations and with arbitrary feasibility constraints are improved. A compact representation language is adopted to represent the preference, especially the dependencies between resources. All agents in the distributed systems would like to maximize their degree of satisfaction. The model is applied to Earth-observing satellites (EOS), and three constraints are taken into account, namely, physical problem constraints, efficiency constraints, and fairness constraints. Compared with the proposed method in this paper, the agent needs to find out the necessary resources which own all the needed characters. Then, agents are more contented if more attributes are covered. Degree of importance is applicable as a compact representation language, and it is more comfortable and more flexible in real-life utilization. Meanwhile, agents are always selfless and cooperative to their acquaintances when sharing some kinds of resources, which is also close to real-world life. In [43], a trust-based method is developed for resource management. However, the article mainly focuses on trust through reinforcement learning. In future work, trust-based resource allocation will be taken into account in a completely selfless and cooperative system.

As is explained, agents’ preferences in MARA are mostly represented in cardinal or ordinal preference structures, fuzzy and qualitative approaches are rarely emphasized. However, fuzziness and uncertainty are always one of the indispensable parts of preference representation. Resource demanders always keep two separated acceptable and ideal amounts for required resources, so it is the same to required characters. The comparisons in this part are efficient in explanation. Anyhow, we would like to put the proposed system in our real world to illustrate its efficiency.

6. Conclusions

In this paper, a preference-based approach for resource allocation is proposed. We introduced interval numbers and importance degrees to represent the detailed resource requirements from both perspectives of resource quantities and properties. In full distributed systems, all agents are collaborative and desire to share their resources. However, agents only act friendly to their acquaintance and never cooperate with strangers. An illustrative example of resource sharing in a distributed network is presented to show the working process and the effectiveness of the proposed distributed method. In future research, the cooperative mode needs to be improved, and agents can reserve resources for both friends and strangers. Agents negotiate for more satisfied resources, and trust-based resource allocation method would be taken into account.

Footnotes

Acknowledgments

This work is supported by CRIStAL (Research center in Computer Science, Signal and Automatic Control of Lille) (UMR 9189) and China Scholarship Council (CSC).

References

Agrawal

Varakantham

and Yeoh

, Scalable greedy algorithms for task resource constrained multi-agent stochastic planning, in: IJCAI, 2016, pp. 10–16.

Airiau

and Endriss

, Multiagent resource allocation with sharable items: Simple protocols and nash equilibria, in: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: Volume 1-Volume 1. International Foundation for Autonomous Agents and Multiagent Systems, 2010, pp. 167–174.

Aorpimai

and Palmer

P.L.

, Repeat-groundtrack orbit acquisition and maintenance for earth-observation satellites, Journal of Guidance Control & Dynamics 30(3) (2012), 654–659.

Blondel

V.D.

Hendrickx

J.M.

Olshevsky

and Tsitsiklis

J.N.

, Convergence in multiagent coordination, consensus, and flocking, in: Decision and Control, 2005 and 2005 European Control Conference. CDC-ECC’05. 44th IEEE Conference on. IEEE, 2005, pp. 2996–3000.

Bouveret

Lemaître

Fargier

and Lang

, Allocation of indivisible goods: a general model and some complexity results, in: Proceedings of the Fourth International Joint Conference on Autonomous Agents and Multiagent Systems. ACM, 2005, pp. 1309–1310.

Cano

J.I.

Sánchez

Camacho

Pulido

and Anguiano

, Using preferences to solve student-class allocation problem, in: International Conference on Intelligent Data Engineering and Automated Learning. Springer, 2009, pp. 626–632.

Chevaleyre

Dunne

P.E.

Endriss

Lang

Lemaitre

Maudet

Padget

Phelps

Rodriguez-Aguilar

J.A.

and Sousa

, Issues in multiagent resource allocation, Informatica 30(1) (2006).

Chevaleyre

Endriss

Estivie

and Maudet

, Multiagent resource allocation in k-additive domains: preference representation and complexity, Annals of Operations Research 163(1) (2008), 49–62.

Chevaleyre

Endriss

Estivie

Maudet

et al., Multiagent resource allocation with k-additive utility functions, in: Proc. DIMACS-LAMSADE Workshop on Computer Science and Decision Theory, Vol. 3, ILLC, 2004, pp. 83–100.

10.

Chevaleyre

Endriss

and Maudet

, Distributed fair allocation of indivisible goods, Artificial Intelligence 242 (2017), 1–22.

11.

Chiclana

Herrera

and Herrera-Viedma

, Integrating three representation models in fuzzy multipurpose decision making based on fuzzy preference relations, Fuzzy Sets and Systems 97(1) (1998), 33–48.

12.

Cui

Guo

and Gao

, Game theory-based negotiation for multiple robots task allocation, Robotica 31(6) (2013), 923–934.

13.

de Weerdt

M.M.

Zhang

and Klos

, Multiagent task allocation in social networks, Autonomous Agents and Multi-Agent Systems 25(1) (2012), 46–86.

14.

Dimarogonas

D.V.

Frazzoli

and Johansson

K.H.

, Distributed event-triggered control for multi-agent systems, IEEE Transactions on Automatic Control 57(5) (2012), 1291–1297.

15.

Lin

Sun

and Yang

, A new trust model for online social networks, in: Computer Communication and the Internet (ICCCI), 2016 IEEE International Conference on. IEEE, 2016, pp. 300–304.

16.

Herrera-Viedma

Chiclana

Herrera

and Alonso

, Group decision-making model with incomplete fuzzy preference relations based on additive consistency, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 37(1) (2007), 176–189.

17.

Iijima

Hayano

Sugiyama

and Sugawara

, Analysis of task allocation based on social utility and incompatible individual preference, in: Technologies and Applications of Artificial Intelligence (TAAI), 2016 Conference on. IEEE, 2016, pp. 24–31.

18.

Jiang

Zhou

and Wang

, Task allocation for undependable multiagent systems in social networks, IEEE Transactions on Parallel and Distributed Systems 24(8) (2012), 1671–1681.

19.

Jiang

, A survey of task allocation and load balancing in distributed systems, IEEE Transactions on Parallel and Distributed Systems 27(2) (2016), 585–599.

20.

Kattan

Ong

Y.-S.

and Galván-López

, Multi-agent multi-issue negotiations with incomplete information: a genetic algorithm based on discrete surrogate approach, in: Evolutionary Computation (CEC), 2013 IEEE Congress on. IEEE, 2013, pp. 2556–2563.

21.

Korhonen

and Syrjänen

, Resource allocation based on efficiency analysis, Management Science 50(8) (2004), 1134–1144.

22.

Lang

, Logical preference representation and combinatorial vote, Annals of Mathematics and Artificial Intelligence 42(1-3) (2004), 37–71.

23.

Leal

Huedo

and Llorente

I.M.

, A decentralized model for scheduling independent tasks in federated grids, Future Generation Computer Systems 25(8) (2009), 840–852.

24.

Lemaître

Verfaillie

and Bataille

, Exploiting a common property resource under a fairness constraint: A case study, in: Proceedings of the 16th International Joint Conference on Artifical Intelligence-Volume 1. Morgan Kaufmann Publishers Inc., 1999, pp. 206–211.

25.

Lewis

P.R.

Marrow

and Yao

, Resource allocation in decentralised computational systems: an evolutionary market-based approach, Autonomous Agents and Multi-Agent Systems 21(2) (2010), 143–171.

26.

Lozano

and Villa

, Centralized resource allocation using data envelopment analysis, Journal of Productivity Analysis 22(1-2) (2004), 143–161.

27.

Mikulski

D.G.

Lewis

F.L.

E.Y.

and Hudas

G.R.

, Trust dynamics in multi-agent coalition formation, in: Unmanned Systems Technology XIII. Vol. 8045. International Society for Optics and Photonics, 2011, p. 80450S.

28.

Morente-Molinera

J.A.

Wikström

Herrera-Viedma

and Carlsson

, A linguistic mobile decision support system based on fuzzy ontology to facilitate knowledge mobilization, Decision Support Systems 81 (2016), 66–75.

29.

Nedic

and Ozdaglar

, Distributed subgradient methods for multi-agent optimization, IEEE Transactions on Automatic Control 54(1) (2009), 48–61.

30.

Netzer

Meisels

and Zivan

, Distributed envy minimization for resource allocation, Autonomous Agents and Multi-Agent Systems 30(2) (2016), 364–402.

31.

Nogareda

A.-M.

and Camacho

, Optimizing satisfaction in a multi-courses allocation problem, in: Intelligent Distributed Computing IX. Springer, 2016, pp. 247–256.

32.

Nongaillard

and Mathieu

, Egalitarian negotiations in agent societies, Applied Artificial Intelligence 25(9) (2011), 799–821.

33.

Pekgün

Griffin

P.M.

and Keskinocak

, Centralized versus decentralized competition for price and lead-time sensitive demand, Decision Sciences 48(6) (2017), 1198–1227.

34.

Pigozzi

Tsoukias

and Viappiani

, Preferences in artificial intelligence, Annals of Mathematics and Artificial Intelligence 77(3-4) (2016), 361–401.

35.

Ramezani

and Endriss

, Nash social welfare in multiagent resource allocation, in: Agent-mediated Electronic Commerce. Designing Trading Strategies and Mechanisms for Electronic Markets. Springer, 2010, pp. 117–131.

36.

Rodríguez

R.M.

Labella

and Martínez

, An overview on fuzzy modelling of complex linguistic preferences in decision making, International Journal of Computational Intelligence Systems 9(sup1) (2016), 81–94.

37.

Saito

and Sugawara

, Allocating resources based on multiple bid declaration with preference, Computer & Information Science 16(4) (2015), 30–40.

38.

Savla

and Frazzoli

, A dynamical queue approach to intelligent task management for human operators, Proceedings of the IEEE 100(3) (2012), 672–686.

39.

Schelén

and Pink

, Sharing resources through advance reservation agents, in: Building QoS into Distributed Systems. Springer, 1997, pp. 265–276.

40.

Vig

and Adams

J.A.

, Coalition formation: from software agents to robots, Journal of Intelligent and Robotic Systems 50(1) (2007), 85–118.

41.

Chen

Liang

and Wang

, Priority-based constructive algorithms for scheduling agile earth observation satellites with total priority maximization, Expert Systems with Applications An International Journal 51 (2016), 195–206.

42.

Zhang

and Sutanto

, Decentralised dispatch of distributed energy resources in smart grids via multi-agent coalition formation, Journal of Parallel and Distributed Computing 83 (2015), 30–43.

43.

Shen

Miao

and Leung

, Filtering trust opinions through reinforcement learning, Decision Support Systems 66 (2014), 102–113.

44.

Zargayouna

Balbo

and Ndiaye

, Generic model for resource allocation in transportation. application to urban parking management, Transportation Research Part C: Emerging Technologies 71 (2016), 538–554.