Applying inferential processes to partner selection in large agents communities Pasquale De Meoa , Rino Falconeb and Alessandro Sapienzab a Department of Ancient and Modern Civilizations (University of Messina), Messina, 98122, Italy b Institute of cognitive sciences and technologies (ISTC-CNR), Rome, 00185, Italy Abstract The current literature clearly highlighted the need to define a fast and efficient tool for trust assessment, even in lack of direct information, as much as possessing mechanisms allowing a matching between a selected task and a reliable agent able to carry it out. Direct experience plays a big part, yet it requires a long time to offer a stable and accurate performance and this characteristics may represents a strong drawback especially within huge agents’ communities. We support the idea that category-based evaluations and inferential processes represent a useful resource for trust assessment. Within this work, we exploit simulations to investigate how efficient this inferential strategy is, with respect to direct experience, focusing on when and to what extent the first prevails on the latter. Our results suggest that in some situations categories represent a valuable asset, providing even better results. Keywords trust, inference, multi-agent systems 1. Introduction and Background A great deal of effort has been made to assess trust within agents’ societies [1][2][3][4]. The great majority of the approaches makes extensive use of direct experience as the main source of information, considering recommendation/reputation and inferential processes just later, as a secondary mechanism to refine trust assessment. Unfortunately, direct experience might not always represent the best solution to assess trustworthiness. For instance, using direct experience within huge networks may become unfeasible, because of their very nature: it is hard and extremely costly to possess enough experience to judge a sufficient number of agents. It is therefore fundamental to find an effective approach for trust assessment even in lack of direct experience [5]. In particular, we argue that category-based evaluations and inferential processes may represent an effective solution. Let us then introduce the formal framework within which we will work. We consider a population of agents π’œ = {π‘Ž1 , . . . , π‘Žπ‘› } which can collaborate by reciprocally delegating the execution of some tasks. We suppose that any agent π‘Žπ‘– ∈ π’œ needs to achieve a goal 𝑔, which identifies a state of the environment (in short, the world) which the agent π‘Žπ‘– plans to achieve. The agent π‘Žπ‘– can reach WOA 2020: Workshop β€œFrom Objects to Agents”, September 14–16, 2020, Bologna, Italy " pdemeo@unime.it (P. D. Meo); rino.falcone@istc.cnr.it (R. Falcone); alessandro.sapienza@istc.cnr.it (A. Sapienza)  0000-0001-7421-216X (P. D. Meo); 0000-0002-0300-458X (R. Falcone); 0000-0001-9360-779X (A. Sapienza) Β© 2020 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings http://ceur-ws.org ISSN 1613-0073 CEUR Workshop Proceedings (CEUR-WS.org) 15 Pasquale De Meo et al. 15–27 the goal 𝑔 by executing a task 𝜏 , which affects the world. The most interesting case occurs if the agent π‘Žπ‘– want/must delegate the execution of 𝜏 . At an abstract level, each agent possesses some skills and resources, defined here as features which determine its ability in carrying out the tasks it has to face. Nevertheless, not all the features associated with an agent are crucial for the execution of 𝜏 and the majority of these will not even be necessary. If I were to ask someone to cook for me, it would be interesting to know how fast she/he is, how good is her/his culinary imagination or if she/he knows how to cook specific dishes; however, knowing that she/he loves reading astrophysics books would not be of any help. It is therefore a fundamental precondition that an agent π‘Žπ‘– identifies which features are necessary to carry out 𝜏 . Then, π‘Žπ‘– needs a mental representation of any other π‘Žπ‘— , which comprises, at least, the subset of the features which are relevant to execute 𝜏 . It is also important to underline that just the possession of these features is not enough, it is also very relevant π‘Žπ‘— ’s willingness (following its motivations) to actually realize 𝜏 . Of course, two different tasks, say 𝜏1 and 𝜏2 , require different features to be efficiently addressed. Thanks to its mental model, π‘Žπ‘– is able to estimate the likelihood πœ‘(𝑖, 𝑗) that π‘Žπ‘— will positively bring to completion that specific agreed task, for each agent π‘Žπ‘— ∈ π’œ. The function πœ‘(𝑖, 𝑗) measures the degree of trust [6] that π‘Žπ‘– (hereafter, the trustor) puts in π‘Žπ‘— (hereafter the trustee), i.e., quantifies to what extent π‘Žπ‘– is confident that π‘Žπ‘— is capable of successfully executing 𝜏 . It is crucial to point out that the assessment of trust is not only task-dependent but also context-dependent, because external causes may amplify or downsize the trust between the trustor and trustee. For instance, assume that π‘Žπ‘– wants to get to the airport one hour before the departure of her/his flight and suppose that π‘Žπ‘– is confident that π‘Žπ‘— is able to safely drive and she/he is knowledgeable of obstacles to traffic flow (e.g., limited access roads), and thus, π‘Žπ‘– puts a high degree of trust in π‘Žπ‘— . However, unforeseen circumstances (e.g., π‘Žπ‘— stucks in a traffic jam) may prevent π‘Žπ‘– from being at the airport at the scheduled time: such an event negatively influence the trust from π‘Žπ‘– to π‘Žπ‘— , even if, of course, the liability of π‘Žπ‘— is limited. The procedure to select the agent to which the task 𝜏 has to be delegated is thus entirely driven from the calculation of the function πœ‘(𝑖, 𝑗): the trustor should select the agent π‘Žβ‹†π‘— for which πœ‘(𝑖, 𝑗) achieves its largest value, i.e., 𝑗 ⋆ = arg max𝑗 πœ‘(𝑖, 𝑗). Such a protocol is, unfortunately, infeasible in real-life applications: in fact, π‘Žπ‘– is capable of estimating the trust of those agents – in short 𝐸𝑖 – with which it interacted in the past and of which it knows features. In real-life applications, we expect that the size of π’œ is much larger than that of 𝐸𝑖 and, thus, the search of a successful partner is likely to end up in a failure. An elegant solution to the problem of selecting partners in large agent communities is described in [7, 8] and it relies on the concept of agent category or, in short, category. Broadly speaking, a category is a subset of agents in π’œ such that each category member possesses homogeneous features. Their unique nature makes categories very interesting and particularly useful. Since the members of a category possess similar features, even their perfor- mance concerning the same task will be similar. For sure, we have to consider a certain degree of uncertainty, due to the specific peculiarities of the individuals. The specific categories to take into consideration change with the context and with the task of interest. For instance, suppose that π’œ correspond to a community of people working in food service with different roles; chefs, waiters, and sommeliers are possible examples of categories 16 Pasquale De Meo et al. 15–27 in this context. Because of the existence of categories, the set of agents that the trustor can evaluate signifi- cantly expands in size and it consists of the following type of agents: 1. The aforementioned set 𝐸𝑖 , which consists of the agents with which π‘Žπ‘– has had a direct experience. 2. The set 𝐢𝑖 of agents, such that each agent π‘Žπ‘— ∈ 𝐢𝑖 belongs to at least one of the categories 𝐢𝑆 = {𝐢1 , 𝐢2 , . . . , 𝐢𝑝 }; here we suppose that π‘Žπ‘– has had a direct experience with at least one agent in each of the categories in 𝐢𝑆. 3. The set of agents 𝑅𝑖 with which π‘Žπ‘– had no direct experience but which have been recommended to π‘Žπ‘– by other agents in π’œ (for instance, on the basis of their reputation). 4. The set of agents 𝑅𝐢𝑖 , such that each agent in 𝑅𝐢𝑖 belongs to a category which contain at least one agent in 𝑅𝑖 . Advantages arising from the introduction of categories have been extensively studied in past literature [9, 8, 7]: the trustor, in fact, could be able to estimate the performance of any other agent π‘Žπ‘— , even if it has never met this agent (and, as observed in [7] without even suspecting its existence), through an inferential mechanism. As the authors of [9] say, it is possible to take advantage of categories just if a few conditions are met. First of all, π’œ must be partitioned into the categories π’ž = {𝐢1 , 𝐢2 , . . . πΆπ‘š }, classifying the agents according to their features. We assume that this classification is given and accepted by all the agents in π’œ. It must be possible to clearly and unequivocally link π‘Žπ‘— to a category 𝑐𝑙 . Finally, we must somehow identify the average performance of the category 𝐢𝑙 with respect to the task 𝜏 : we will discuss in detail in Section 3 a procedure to estimate the performance – called true quality – πœƒπ‘™ (𝜏 ) of the category 𝐢𝑙 for task 𝜏 . When all three of these conditions are met, then the category 𝐢𝑙 ’s evaluation can be used for the agent π‘Žπ‘— , concerning the task 𝜏 since, by definition of category, all agents in 𝐢𝑙 will share the same features of π‘Žπ‘— and, thus, if the other agents in 𝐢𝑙 are able to successfully execute the task 𝜏 (or not), we can reasonably assume that even π‘Žπ‘— can do it (or not). Of course, only some of the categories 𝐢1 , . . . , πΆπ‘š possess the qualities to successfully execute the task 𝜏 while others do not. As a consequence, the first step to perform is to match the task 𝜏 with a set of categories capable of executing 𝜏 . At a basic level, such a matching could be implemented through a a function πœ“(𝐢𝑙 , 𝜏 ) which takes a category 𝐢𝑙 and a task 𝜏 and returns True if agents in 𝐢𝑙 are capable of executing 𝜏 , False vice versa. The computation of the function πœ“ requires an analytical and explicit specification of: (a) the chain of actions to perform to execute 𝜏 and (b) for each action mentioned in (a), the features an agent should possess to perform such an action. The protocol above easily generalizes to the case in which the trustor has a limited experience (or, in the worst case it has no previous experience): in this case, in fact, the trustor π‘Žπ‘– could leverage the sets of agents 𝑅𝑖 and 𝑅𝐢𝑖 . 2. Related Work The growing need to deal with bigger and bigger agents’ networks makes it difficult to find reliable partners to delegate tasks. It becomes clear that, in such situations, direct experience 17 Pasquale De Meo et al. 15–27 [10] is not enough to allow us facing this problem. Going beyond this dimension becomes essential, on the light of the knowledge we already have, identifying models and methodologies able to evaluate our interlocutors and possibly to select adequate partners for the collaborative goals we want to pursue. Several authors proposed trust propagation as a solution to this topic. Trust propagation [11][12] starts from the assumption that if π‘Žπ‘– trusts π‘Žπ‘— and π‘Žπ‘— trusts π‘Žπ‘˜ , then it is reasonable to assume that π‘Žπ‘– can trust π‘Žπ‘˜ to some extent. Exploiting this and other assumptions, this technique allows propagating a trust value from an agent to another one, without requiring a direct interaction. The confusion in the reasoning process here is due to the consideration of a generic trust value for an individual, leaving aside the reason why we trust it: the task we want to delegate to it. Many articles have discussed the use of categories/stereotypes in trust evaluations [13][14]. This is a very useful instrument, allowing to generalize an individual’s evaluation, concerning a specific task to other agents owning similar characteristics. It represents a useful proxy for individuating knowledge about specific trustees [15], elicited in particular in all those circumstances precluding the development of person-based trust [16]. Here the intuition is that, given a specific task 𝜏 , the performance of the agent we are evaluating are related to the values of the features it needs to carry out the task itself. Along these lines, it is natural to assume that other individual owning similar values, i.e. belonging to the same category, have the same potential to solve 𝜏 . Pursuant to these considerations, our contribution within this work concerns the investigation of how efficient this inferential strategy is, with respect to direct experience, focusing on when and to what extent the first prevails on the latter. 3. Inferring the quality of categories In this section we illustrate our procedure to estimate the performance (in short called the true quality) πœƒπ‘™ (𝜏 ) of agents in the category 𝐢𝑙 to successfully execute a particular task 𝜏 . Because of the assumptions of our model (illustrated in Section 1), agents belonging to the same category share the same features and, thus, their performances in executing 𝜏 are roughly similar; this implies that if an agent π‘Žπ‘— ∈ 𝐢𝑙 is able (resp., not able) to execute 𝜏 , then we expect that any other agent π‘Žπ‘ž ∈ 𝐢𝑙 is also able (resp., not able) to execute 𝜏 . In the following, we suppose that agents in 𝐢𝑙 are able to execute 𝜏 , i.e. in compliance with notation introduced in Section 1, we assume that πœ“(𝐢𝑙 , 𝜏 ) = True. In contrast, if πœ“(𝐢𝑙 , 𝜏 ) = False, it does not make sense to estimate πœƒπ‘™ (𝜏 ). The next step of our protocol consists of selecting one of the agents, i.e., the trustee, in 𝐢𝑙 to which delegate 𝜏 ; to this purpose, we could select, uniformly at random, one of the agents in 𝐢𝑙 , as illustrated in [7]. However, agents are individual entities and, thus, slight differences in their features exist. Because of these differences, an agent (say π‘Žπ‘— ) may have better (resp., worse) performance than another agent (say, π‘Žπ‘ž ) in executing 𝜏 . In the light of the reasoning above, the true quality πœƒπ‘™ (𝜏 ) quantifies the expected performance of an arbitrary trustee in 𝐢𝑙 in the execution of 𝜏 . We assume that πœƒπ‘™ (𝜏 ) ranges in (βˆ’βˆž, +∞): positive (resp., negative) values of πœƒπ‘™ (𝜏 ) are an 18 Pasquale De Meo et al. 15–27 indicator of good (resp., bad) performances. The first step to compute πœƒπ‘™ (𝜏 ) consists of modelling the performance 𝑓𝑗 (𝜏 ) of an arbitrary agent π‘Žπ‘— ∈ 𝐢𝑙 in executing 𝜏 . To capture uncertainty in the performance of π‘Žπ‘— , we represent 𝑓𝑗 (𝜏 ) as a Gaussian random variable with mean πœ‡π‘— and variance πœŽπ‘—2 . The assumption that all of the agents in the same category should reach the same performance implies that πœ‡π‘— = πœƒπ‘™ (𝜏 ) for each agent π‘Žπ‘— ∈ 𝐢𝑙 . The variance πœŽπ‘—2 controls the amount of variability in the performances of the agent π‘Žπ‘— : large (resp., small) values in πœŽπ‘—2 generate significant (resp., irrelevant) deviations from πœƒπ‘™ (𝜏 ). In this paper we considered two options for πœŽπ‘—2 , namely: 1. Fixed Variance Model: we suppose that πœŽπ‘—2 = 𝜎 2 for each π‘Žπ‘— ∈ 𝐢𝑙 . 2. Random Variance Model: we suppose that πœŽπ‘—2 is a uniform random variable in the interval [𝛼, 𝛽]. Based on these premises, the procedure to estimate πœƒπ‘™ (𝜏 ) is iterative and, at the π‘˜-th iteration it works as follows: a) We select, uniformly at random, an agent, say π‘Žπ‘— from 𝐢𝑙 b) We sample the performance 𝑓^ 𝑗 (π‘˜) ∼ 𝑓𝑗 (𝜏 ) of π‘Žπ‘— Steps a) and b) are repeated 𝑁 times, being 𝑁 the number of agents we need to sample before making a decision. In addition, in Step a), agents are sampled with replacement, i.e., an agent could be selected more than once. The algorithm outputs the average value of sampled performances, i.e.: 𝑁 ^πœƒπ‘™ (𝜏 ) = 1 βˆ‘οΈ 𝑓^ 𝑗 (π‘˜) (1) 𝑁 π‘˜=1 Our algorithm actually converges to the true value πœƒπ‘™ (𝜏 ) as stated in the following theorem: Let 𝑁 be the number of agents queried by our algorithm and let ^πœƒπ‘™ (𝜏 ) be the estimation of the true quality πœƒπ‘™ (𝜏 ) the algorithm returns after 𝑁 rounds. We have that in both the fixed variance and random variance models ^πœƒπ‘™ (𝜏 ) converges to πœƒπ‘™ (𝜏 ) at a rate of convergence of √1𝑁 . Let us first analyze the individual agent performances 𝑓𝑗 (𝜏 ) and we are interested in com- puting the mean and variance of 𝑓𝑗 (𝜏 ). If we opt for the Fixed Variance Model, then 𝑓𝑗 (𝜏 ) is a Gaussian random variable with mean πœƒπ‘™ (𝜏 ) and the variance is equal to a constant value 𝜎 2 . In contrast, if we are in the Random Variance Model, then the estimation of the mean and the variance of 𝑓𝑗 (𝜏 ) can be obtained by law of total mean and the law of total variance [17], which state that for two arbitrary random variables 𝑋 and π‘Œ , the following identities hold true: E(𝑋) = E(E(𝑋 | π‘Œ )) (2) Var(π‘Œ ) = E(Var(π‘Œ | 𝑋)) + Var(E(π‘Œ | 𝑋)) (3) 19 Pasquale De Meo et al. 15–27 We apply Equations 2 and 3 to 𝑋 = 𝑓𝑗 (𝜏 ) and π‘Œ = 𝜎; if we condition on 𝜎 = 𝜎, then 𝑓𝑗 (𝜏 ) is a Gaussian random variable with mean equal to πœƒπ‘™ (𝜏 ) and variance equal to 𝜎 and therefore: E(𝑓𝑗 (𝜏 )) = E(E(𝑓𝑗 (𝜏 ) | 𝜎 = 𝜎)) = E(πœƒπ‘™ (𝜏 )) = πœƒπ‘™ (𝜏 ) In addition, 𝛼+𝛽 E(Var(𝑓𝑗 (𝜏 ) | 𝜎 = 𝜎)) = E(𝜎) = 2 and Var(E(𝑓𝑗 (𝜏 ) | 𝜎 = 𝜎)) = Var(E(πœƒπ‘™ (𝜏 ))) = Var(πœƒπ‘™ (𝜏 )) = 0 which jointly imply 𝛼+𝛽 Var(𝑓𝑗 (𝜏 )) = 2 As a consequence, independently of the agent π‘Žπ‘— , we have that the agent performances 𝑓𝑗 (𝜏 ) have the same distribution which we denote as 𝑓 (𝜏 ). Therefore, in both the Fixed Variance Model and Random Variance Model, the algorithm selects a random sample of agents 𝑍1 , 𝑍2 , . . . , 𝑍𝑁 of size 𝑁 in which, for each π‘˜ such that 1 ≀ π‘˜ ≀ 𝑁 , π‘π‘˜ is the average performance of the agent selected at the π‘˜-th iteration and it is distributed as 𝑓 (𝜏 ). The algorithm calculates: 𝑍1 + 𝑍2 + . . . + 𝑍𝑛 𝑆𝑁 = (4) 𝑁 Because of the Central Limit Theorem [17], the distribution of 𝑆𝑁 gets closer and closer to a Gaussian distribution with mean πœƒπ‘™ (𝜏 ) as 𝑁 β†’ +∞ with a rate of convergence in the order of √1 and this end the proof. 𝑁 4. Experimental Analysis We designed our experiments to answer two main research questions, namely: RQ1 What are the benefits arising from the introduction of categories in the selection of a trustee against, for instance, a pure random search or a direct-experience based strategy? RQ2 How quickly our algorithm to estimate πœƒπ‘™ (𝜏 ) converges? In what follows, we first describe a reference scenario in which our task consists of recruiting a chef from a database of applicants (see Section 4.1). Then, in Sections 4.2 and 4.3, we provide an answer to RQ1 and RQ2 . 4.1. The reference scenario We assume that features associated with our task are as follows: (i) Culinary Education, measured as the (overall) number of hours spent in training courses with qualified chef trainers, (ii) Expertise, i.e., the number of years of professional experience, (iii) Language Skills, defined as the number of foreign languages in which the applicant is proficient, (iv) Culture, measured on 20 Pasquale De Meo et al. 15–27 Table 1 Some tasks associated with the recruitment of a professional chef and their requirements Task Culinary Expertise Language Culture Creativity Education Skills 𝜏1 150 5 2 6 7 𝜏2 200 4 2 6 6 𝜏3 300 4 2 7 6 Table 2 Some features associated with categories 𝐢1 - 𝐢5 Category ID. Culinary Expertise Language Culture Creativity Education Skills 𝐢1 250 5 2 8 7 𝐢2 250 3 2 6 5 𝐢3 300 3 1 4 5 𝐢4 100 6 1 4 5 𝐢5 400 3 1 4 5 a scale from 0 (worse) to 10 (best) and which is understood as the ability of preparing different kind dishes (e.g. fish, meat, vegetarian and so on) in different styles (e.g. Indian, Thai or Italian) and (v) Creativity, measured on a scale from 0 (worse) to 10 (best). The list of features is, of course, non-exhaustive. We suppose that each feature is associated with a plausible range: for instance, in Table 1, we consider three potential tasks and the corresponding requirements. In the following, due to space limitations, we concentrate only on the task 𝜏1 and we suppose that five categories exist, namely: Professional Chefs - 𝐢1 , who are trained to master culinary art. Members in 𝐢1 are able to provide creative innovation in menu, preparation and presentation, Vegan Chefs - 𝐢2 , specialized in the preparation of plant-based dishes, Pastry Chefs - 𝐢3 , who are capable of creating chocolates and pastries, Roast Chefs - 𝐢4 , who have expertise in preparing roasted/braised meats and Fish Chefs - 𝐢5 , who are mainly specialized in the preparation of dish fishes. Each category consists of 100 agents and, thus, the overall number of agents involved in our experiments is 500. Features associated with categories 𝐢1 -𝐢5 are reported in Table 2. In our scenario, only agents in 𝐢1 are able to fulfill 𝜏1 ; agents in other categories are, for different reasons, unable to execute 𝜏1 : for instance, the expertise of agents in categories 𝐢2 , 𝐢3 and 𝐢5 is not sufficient while agents forming categories 𝐢3 -𝐢5 correspond to applicants with a high level of specialization in the preparation of some specific kind of dishes (e.g., fish-based dishes) but they are not sufficiently skilled in the preparation of other type of foods and, thus, agents in these categories showcase an insufficient level of culture. To simplify discussion we suppose that, through a proper normalization, the performance 𝑓 (𝜏1 ) (see Section 3) of an individual agent as well as the true quality πœƒπ‘™ (𝜏1 ) of a category 𝐢𝑙 (for l = 1 . . . 5) range from 0 to 1. Here, the best performance of an agent can provide (resp., the highest true quality of a category) is 1. 21 Pasquale De Meo et al. 15–27 Figure 1: Feedback 𝑓 (𝜏 ) provided by the trustee. Fixed Variance Model with 𝜎 = 0.05 4.2. A comparison of category-based search with random-based search and direct-experience search In our first experiment, we compare three strategies to search for a trustee, namely: a) Random- Based Search: here, the trustor selects, uniformly at random, a trustee to execute 𝜏1 . The trustor measures the performance 𝑓 (𝜏1 ) provided by the trustee in the execution of 𝜏1 . b) Category- Based Search: here, the trustor considers only agents in the most appropriate category (which in our reference scenario coincides with 𝐢1 ); as suggested in [7], the trustor selects, uniformly at random, one of the agents in 𝐢1 to act as trustee. Once again, the trustor measures the performance 𝑓 (𝜏1 ) provided by the trustee in the execution of 𝜏1 . (c) Direct-Experience Search: we suppose that the trustor consults up to 𝐡 agents in the community, being 𝐡 a fixed integer called budget. The trustor records the performance of each consulted agent but it does not memorize its category (it may be that the trustor is unable to perceive/understand the trustee’s category). At the end of this procedure, the trustor selects as trustee the agent providing the highest performance 𝑓 (𝜏1 ) among all consulted agents. The Direct-Experience Search strategy can be regarded as an evolution of the Random-Based Search strategy in which the trustor learns from its past interactions it uses its knowledge to spot the trustee. Here, the budget 𝐡 regulates the duration of the learning activity the trustor pursues. In our experimental setting, we considered two values of 𝐡, namely 𝐡 = 10 and 𝐡 = 30 and we discuss only results in the Fixed Variance Model with 𝜎 = 0.05 and 𝜎 = 0.15. We applied the Random-Based, the Category-Based and the Direct-Experience Search strategies 20 times; a sketch of the probability density function (pdf) of 𝑓 (𝜏1 ) for each strategy is shown in Figure 1 and 2. As expected, Category-Based Search performs consistently better than the Random-Search one. In addition, the standard deviation of 𝑓 (𝜏1 ) in Category-Based Search is much smaller than that observed in the Random-Based strategy and such a behaviour depends on the different degree of matching of categories 𝐢1 -𝐢5 with the task 𝜏1 : in other words, if the trustee is in 𝐢1 , the performances it provides are constantly very good; in contrast, in Random-Based Search strategy, the measured performance may significantly fluctuate on the basis of the category to 22 Pasquale De Meo et al. 15–27 Figure 2: Feedback 𝑓 (𝜏 ) provided by the trustee. Fixed Variance Model with 𝜎 = 0.15 which the trustee belongs to and this explains oscillations in 𝑓 (𝜏1 ). The analysis of the Direct-Experience Search strategy offers many interesting insights which are valid for both 𝜎 = 0.05 and 𝜎 = 0.15. Firstly, notice that if 𝐡 = 10, then the Direct- Experience Search strategy achieves significantly better performances than the Random-Based strategy, which indicates that an even short learning phase yields tangible benefits. If 𝐡 increases, the trustor is able to see a larger number of agents before making its decision and, in particular, if 𝐡 is sufficiently large, then the trustor might encounter the best performing agent π‘Žβ‹† in the whole community. In this case, the Direct-Experience strategy would outperform the Category- Based Search strategy: in fact, in the Category-Based strategy, the trustor chooses, uniformly at random, one of the agents in 𝐢1 which provides a performance worse than (or equal to) π‘Žβ‹† . In short, for large values of 𝐡, the Direct-Experience strategy achieves performances which are comparable and, in some cases, even better than those we would obtain in the Category-Based strategy, as shown in Figure 1 and 2. However, the budget 𝐡 has the meaning of a cost, i.e., it is associated with the time the trustor has to wait before it chooses the trustee and, thus, in many practical scenarios, the trustor has to make its decisions as quick as possible. It is also instructive to consider a further strategy, called Mixed-Based Search, which combines the Random-Based Search strategy with the Category-Based Search strategy. In Mixed-Based Search, we assume the existence of a warm-up phase in which the trustor selects the trustee by means of the Random-Based Search strategy; unlike the Direct-Experience Search strategy, the trustor collects not only 𝑓 (𝜏1 ) but it also records the category of the trustee. In this way, the trustor is able to identify (after, hopefully, a small number of steps) the category with the highest true quality, i.e., 𝐢1 . From that point onward, the trustor switches to a Category-Based strategy and it selects only agents from 𝐢1 . From a practical standpoint, we suppose that a performance 𝑓 (𝜏1 ) β‰₯ 0.6 is classified as an indicator of good performance (in short, positive signal); as soon as the trustor has collected 2 positive signals, it makes a decision on the best performing category and it switches to the Category-Based Search strategy. We are interested at estimating, through simulations, the length β„“ of the warm-up phase, i.e., the number of agents that the trustor has to contact before switching to the Category-Based search strategy. In Figure 3 and 4 we plot the pdf of β„“. 23 Pasquale De Meo et al. 15–27 Figure 3: Probability Density Function of the Warm-up length (β„“) in the Mixed-Search strategy. Fixed Variance Model with 𝜎 = 0.05 Figure 4: Probability Density Function of the Warm-up length (β„“) in the Mixed-Search strategy. Fixed Variance Model with 𝜎 = 0.15 Here, the variance 𝜎 has a minor impact and we notice that, the pdf achieves its largest value at β„“ ≃ 10, i.e., 10 iterations are generally sufficient to identify the best performing category. 4.3. The rate of convergence of our algorithm We conclude our study by investigating how the Fixed Variance Model and the Random Variance model influence the rate at which our algorithm estimates the true quality πœƒπ‘™ (𝜏 ) of a category. To make exposition of experimental outcomes simple, we suppose that πœƒπ‘™ = 1 (which models a scenario in which agents in 𝐢1 showcase an exceptionally high ability in executing 𝜏1 ). We considered the Fixed Variance Model with 𝜎 ∈ {0.05, 0.1, 0.15} and the Random Variance Model in which 𝜎 is uniformly distributed in [0.01, 0.3]. We investigated how ^πœƒπ‘™ (𝜏 ) varied as function of the number 𝑁 of queried agents; obtained results are reported in Figure 5. The main conclusions we can draw from our experiment are as follows: 24 Pasquale De Meo et al. 15–27 Figure 5: Variation of ^πœƒπ‘™ (𝜏 ) as function of 𝑁 . 1. Individual agent variability (modelled through the parameter 𝜎) greatly affects the rate at which ^πœƒπ‘™ (𝜏 ) converges to πœƒπ‘™ (𝜏 ). Specifically, Figure 5 suggests that less than 5 iterations are enough to guarantee that |πœƒ^𝑙 (𝜏 ) βˆ’ πœƒπ‘™ (𝜏 )| < 10βˆ’2 if 𝜎 = 0.05. In addition, as 𝜎 gets larger and larger, we highlight more and more fluctuations in ^πœƒπ‘™ (𝜏 ): as an example, if 𝜎 = 0.15 (green line), we highlight the largest fluctuation in ^πœƒπ‘™ (𝜏 ) and, at a visual inspection, at least 𝑁 = 30 queries are needed to achieve a significant reduction in |πœƒ^𝑙 (𝜏 ) βˆ’ πœƒπ‘™ (𝜏 )|. 2. An interesting case occurs in the Random Variance Model: in some iterations of the algorithm, agents with a small variability are selected (i.e., we would sample agents with 𝜎 ≃ 0.01) while in other cases agent with a larger variability are selected (here 𝜎 ≃ 0.3). Overall, agents with small variability fully balance agents with high variability and, thus, the algorithm converges to πœƒπ‘™ (𝜏 ) (red line) generally faster than the case 𝜎 = 0.1 (orange line) and 𝜎 = 0.15 (green line). 5. Conclusions Although highly populated networks are a particularly useful environment for agents’ collabo- ration, the very nature of these networks may represent a drawback for trust formation, given the lack of data for evaluating the huge number of possible partners. Many contributions in the literature [8, 18] showed that category-based evaluations and inferential processes represent a remarkable solution for trust assessment, since they allow agents to generalize from trust in individuals to trust in their category and vice versa, basing on their observable features. On that note, we cared about stressing the tight relationship between trust and the specific task, target of the trust itself. With the purpose of investigating the role of agents’ categories, we considered a simulated scenario, testing in particular the performance of a category-based evaluation, with respect to a random-based search - which it is easily outperformed - and a direct-experience one, showing that, in case of little direct experience, categories grant a better result. Moreover, we proved that, if not available, it is possible to estimate the category’s true quality πœƒπ‘™ (𝜏 ) in a 25 Pasquale De Meo et al. 15–27 reasonably short amount of time. Future research will attempt to test these findings on a real data set. References [1] J. Yan, D. Wu, S. Sanyal, R. Wang, Trust-oriented partner selection in d2d cooperative communications, IEEE Access 5 (2017) 3444–3453. [2] F. Messina, G. Pappalardo, C. Santoro, D. Rosaci, G. M. SarnΓ©, A multi-agent protocol for service level agreement negotiation in cloud federations, International Journal of Grid and Utility Computing 7 (2016) 101–112. [3] F. Messina, G. Pappalardo, D. Rosaci, G. M. SarnΓ©, A trust-based, multi-agent architecture supporting inter-cloud vm migration in iaas federations, in: International Conference on Internet and Distributed Computing Systems, Springer, 2014, pp. 74–83. [4] A. Sapienza, R. Falcone, Evaluating agents’ trustworthiness within virtual societies in case of no direct experience, Cognitive Systems Research 64 (2020) 164–173. [5] S. Abar, G. K. Theodoropoulos, P. Lemarinier, G. M. O’Hare, Agent based modelling and simulation tools: A review of the state-of-art software, Computer Science Review 24 (2017) 13–33. [6] C. Castelfranchi, R. Falcone, Trust theory: A socio-cognitive and computational model, volume 18, John Wiley & Sons, 2010. [7] R. Falcone, A. Sapienza, Selecting trustworthy partners by the means of untrustworthy recommenders in digitally empowered societies, in: Proc. of the International Conference on Practical Applications of Agents and Multi-Agent Systems, Springer, Avila, Spain, 2019, pp. 55–65. [8] R. Falcone, A. Sapienza, C. Castelfranchi, The relevance of categories for trusting informa- tion sources, ACM Transactions on Internet Technology (TOIT) 15 (2015) 13. [9] R. Falcone, M. Piunti, M. Venanzi, C. Castelfranchi, From manifesta to krypta: The relevance of categories for trusting others, ACM Transactions on Intelligent Systems and Technology (TIST) 4 (2013) 27. [10] C.-W. Hang, Y. Wang, M. P. Singh, Operators for propagating trust and their evaluation in social networks, Technical Report, North Carolina State University. Dept. of Computer Science, 2008. [11] R. Guha, R. Kumar, P. Raghavan, A. Tomkins, Propagation of trust and distrust, in: Proceedings of the 13th international conference on World Wide Web, 2004, pp. 403–412. [12] M. Jamali, M. Ester, A matrix factorization technique with trust propagation for recommen- dation in social networks, in: Proceedings of the fourth ACM conference on Recommender systems, 2010, pp. 135–142. [13] W. L. Teacy, M. Luck, A. Rogers, N. R. Jennings, An efficient and versatile approach to trust and reputation using hierarchical bayesian modelling, Artificial Intelligence 193 (2012) 149–185. [14] H. Fang, J. Zhang, M. Sensoy, N. M. Thalmann, A generalized stereotypical trust model, in: 2012 IEEE 11th International Conference on Trust, Security and Privacy in Computing and Communications, IEEE, 2012, pp. 698–705. 26 Pasquale De Meo et al. 15–27 [15] R. M. Kramer, Collective trust within organizations: Conceptual foundations and empirical insights, Corporate Reputation Review 13 (2010) 82–97. [16] B. D. Adams, R. D. Webb, Trust in small military teams, in: 7th international command and control technology symposium, 2002, pp. 1–20. [17] D. Bertsekas, J. Tsitsiklis, Introduction to probability, Athena Scientific, 2008. [18] R. Falcone, A. Sapienza, C. Castelfranchi, Trusting information sources through their categories, in: International Conference on Practical Applications of Agents and Multi- Agent Systems, Springer, 2015, pp. 80–92. 27