As defined by Whitesides and Ismagilov, a complex system is one whose evolution is very sensitive to initial conditions or to small perturbations, one in which the number of independent interacting components are large, or one in which there are multiple pathways by which the system can evolve. This paper shows results on the research of a complex system studied from an economic point of view. The specific complex system investigated is a general model of economic exchange between heterogeneous entities that form coalitions. These coalitions compete amongst themselves to solve a certain task in order to score as highly possible for the task. A third party thus evaluates the coalitions and ranks them according to their score in terms of skills for the task. Analysis of the macroscopic behaviour of such systems quickly makes it clear that, depending on the properties of the tasks and the agents, different long term Compatibility patterns are established amongst some groups of agents which often work together in successful coalitions. Intuitively also, in a population with a mix of skills, certain combinations of agents intrinsically work well together (i.e. they have compatible skill sets for certain types of task). Concretely, the paper shows that there exists a relationship between heterogeneity in the task definition and similarity of performance between competitive and conservative strategy. The more heterogeneous a task is, the more similar the outcomes of the two strategies. We also show that heterogeneity of the agents does not have the same effect on the outcomes of the strategies. We finally show that in a higher or lower degree, competitive strategy has a better performance than conservative one.
The organizational paradigm of our economic model is Coalition Formation. These models have been extensively studied from a game theoretic perspective initially ( [18,10,9] amongst others) and in the last years, from a multi agent systems perspective ( [2,3,14] amongst others). Game theoretic research of coalitional models focus basically on studying stability properties by analysing different stability solution concepts such as the core, or the kernel [10]. Dynamic Coalition formation further focuses on the study of coalition formation problem of complex systems, this area includes research from a formal mathematical perspective that model with markov chains coalition formation systems to study their properties with several strongly-couples degrees of freedom ( [13,1]). Multi agent systems research is also moving toward this direction in the research of coalition formation systems, and includes papers on the analysis of classical stability concepts of systems not constrained with the necessary rigidity of mathematical models ( [12,17]). The area includes research on a variety of different fronts, including problems such as finding stability properties between coalition structures [8] or finding solutions to a problem in a cooperative way [6]. In general, research on this area does not attach much importance to the topic of heterogeneity, and assume homogeneous individuals competing with homogeneous strategic profiles. An exception to this case is the work by [5], where the author highlights the importance of modelling heterogeneity. Concretely the work focuses on the role of externalities across actors in determining the population-wide behaviour. These externalities, as in our case, are in turn the source of interactions. The cited paper, however, does not focus on a concrete model and study it in deep as is our case, they study the general properties, applications and issues of what they call Interaction Models, from which our model is identified. Other papers such [14] or [3] use some degree of heterogeneity however focus rather on modelling different task valuations for each agent, agent capabilities and greediness levels in the agent's expectations -rather than focusing on heterogeneity per-se.
Our model is driven by complementarities between agents and spillovers between coalitions, thus allows for the analysis of market imperfections in heterogeneous agent contexts.
In the market mechanism suggested in the present work, coalition formation occurs as part of a wider open world and may occur many times during the lifetime of a population of agents. As shown in [15] this fact can in some circumstances be exploited by agents to re-use partial coalition and social relationships over time to improve Coalition Formation efficiency. Such a broader perspective however raises interesting questions for coalition formation environments. This paper goes further in that direction analyzing the dynamics of two concrete rational behaviours, a so called "Competitive Strategy" (agents try to be in a coalition with maximal competence) and a so called "Conservative Strategy" (agents try to be in a coalition with optimal competence / size ratio in order to maximize their benefits) within such an environment. These strategies are common examples of rational behaviour in economic markets. There are, indeed more complex strategies, but, as this paper argues these two strategies already prove sufficient to create two differentiated types of dynamics. In [16] the same two strategies are investigated in an isolated way and together in a general setup. This work extends the cited paper by focusing on the influence of the heterogeneity degree of agents in the performance results as well as on the collaboration structure they show up.
The paper is structured as follows: Section 3 explains the concrete market mechanism in use, the Iterative RFP Coalition Formation method. Section 4 explains the agent based system designed to model the iterative RFP coalition formation method, including the valuation function definition, and the agents' strategies. Section 5 explains the concrete setup used for the experiments as well as the collaboration graph method used in the analysis of results. Section 6 analyses the results of the experiments with respect to the effect of heterogeneity on the strategies outcomes. Section 7 analyses the results on the effect of heterogeneity in the collaboration structures between agents. Finally, Section 8 wraps up the results obtained showing the conclusion of the present work.
Request For Proposal Systems (RFP Systems from now on) are defined as those in which an individual or an entity submits an invitation (RFP) for providers of a product or service to bid on the right to supply that product or service to the individual or entity that issued the RFP. This type of systems is widespread in many different economic activities such as European Calls for project proposals in different frameworks, public contests for concessions of licenses to construct buildings, or to handle a particular marketing campaign and so forth.
Calls in real systems are announced and issued once or more times a year. They can be con-sidered as iterative processes that repeat periodically over time. This way certain individual that participated in a certain call will likely participate in the subsequent one facing a related problem over and over, and adapting to the variations in the requirements and in the environment in order to be more competitive. Summarizing, the characteristics of the RFP System under study are:
• Agents, or groups of agents compete for a given goal.
• The best agents, or groups of agents are rewarded with the award of the contract to carry out the task and its subsequently payoff.
• Some systems, may also have policies for rewarding 2 nd , 3 rd , 4 th etc. ranked agents / groups of agents.
• The process repeats over time.
• Groups might change depending on the market situation.
• Agents are individual utility maximizers and they share the same preference, that is payoff maximization, but might have different strategies for maximizing their utility.
A population I = {1, 2, . . . , n} consists of a finite number of n individuals or agents. Agents compete amongst them given the requirements specified by a certain task T . A partition σ = {σ 1 , σ 2 , . . . , σ p } of the population I is a specification of p coalitions of agents σ i = {σ i1 , σ i2 , . . . , σ im }, where σ ij represents an agent from population I forming part of coalition σ i . By forming coalitions, agents are able to increase their competitivity towards the specified task.
Agents have heterogeneous capabilities, thus having different performance levels in different skills. A finite number of k skills, indexed from 1 to k is set for which each agent σ ij has a fixed value:
In this way it is possible to define a continuum of possibilities between agents that are specialised in the performance of a certain skill being unskilled for the rest of them, and agents that are versatile, being averagely apt for the performance of all the skills defined.
A Task T is specified by a set of k skill requirements. Each of the k skills have a degree of requirement. These requirements are modelled in the form of a number T = T 1 , T 2 , . . . , T k .
In a coalition, skills of agents are aggregated in such a way that each agent gives the best of itself in a join effort to create a group as competitive as possible under the requirements of the Task. The coalition has a value in each skill representing the aggregated effort of its members. The aggregation for every skill j : 1 ≤ l ≤ k in the coalition is modelled in the following way:
In this way, there is always one agent σ ij in coalition σ i that is providing the maximum value for every skill l. This is noted as σ l i . Each skill is considered as a necessary subtask for performing task T . In this way, by using the aggregation function shown in equation 1, the agent in a coalition which is the best fit for performing a certain subtask will be the one that performs it, specializing just in that subtask while others in the coalition perform the other subtasks.
Amongst the different possibilities for aggregating agent skills in a coalition, we have chosen the Maximization function, as we consider it is a reasonable metaphor of many real coalitional processes. For example, if we consider a consortium of partners participating in a call for proposals, each member of the consortium will be representative of a certain part of the proposal, and normally is the partner best fitted for that part of the work.
The value function determines the payout given to each priced coalition. The general properties of function desired are:
1. The function must be monotonically increasing with the size of the coalition. In this way, the function will measure how apt the coalition is to perform a task without considering how optimal is in terms of size. That will be considered in the payoff mechanism.
2. The function must be upper bounded. Corresponding to the idea of having a score for a perfect proposal and all suboptimal ones will have a lower score than that.
3. The function must be deterministic. Hence we model the fact that the evaluation criteria is common knowledge and exclude the need for objective valuation.
With these properties in mind one can formally define a score function scr(σ x , T ) to measure how well agents in coalition σ x perform together for accomplishing a task specification T without having into account the rest of coalitions.
As explained in section 4, Tasks are specified by a set of skill requirements, and each of the k skills has a degree of requirement. For the purposes of this scoring function, those requirement values will be treated as weights, modelling the fact that some skills are more important than other for the accomplishment of a certain task. The score of a coalition can be computed as the weighted sum of the best skill values for each skill that the coalition has. Formally:
It is straightforward to check that this function complies with the three properties named above. While there are other possible value function the one chosen here reflects models used for coalition formation in a large part of the current literature.
Once we have the endogenous value of a coalition, it is necessary to assign the payoff depending on its ranking. That constitutes the second steep required for computing the general coalition utility (the coalition's payoff).
The reward function defined here, allocates wealth in a decreasing fashion depending on the score of the coalitions. To this end, a ranking function creates a strict order between coalitions by using scr(σ x , T ) function as an ordering criterion, and ordering randomly those consecutive coalitions with equal score. This function is expressed formally as: rank(σ x , σ), and it returns the value of the strict order of coalition σ x ∈ σ.
Coalitions are priced with an exponentially decreasing amount from the initial one following the order established by the rank function, and there will always be a fixed amount P of payoff to spread amongst the coalitions, independently on the number of coalitions existent. Formally:
for the last competent coalition, P/2 rank(σx,σ)−1 , for all the other competent coalitions.
(
Amongst the different possibilities for assigning the payoff, this concrete exponential function has been chosen for two reasons: first, because this function has the property that, independently of the number of competent coalitions, the total amount of money spread will always be P . This is an important property for realistic CFP environments and also ensures one can compare the economic behaviour of different populations. The second reason is because this represents a power law distribution of wealth for which there is empirical evidence from Real Economies (see [7]).
As a simplification however, Agents within a coalition spread coalition's payoff evenly (and hence methods for differential allocation of payoff to individual agents are not applied here). While this removes some complex coalition formation issues it still forces a tradeoff for agents between coalition size (in order to be more competent, thus gain a higher score and being more group profitable), and coalition optimality (in order to share the payoff by a reduced set of members, and so being individually profitable).
This sub-section defines the actions agents can take between different issuances of tasks. Each player's strategic variables are his coalition choice σ j and a set of agents in this coalition φ jk ⊂ σ j to eliminate and optimise the coalition. This possibility of optimisation responds to the change of value that certain agents can experiment when in the coalition they are out-skilled by a new member. It is necessary to model this possibility as this model deals with heterogeneous individual capabilities (not only different strategies).
Time is discrete. In each period, a random subset of agents is chosen, and they are asked sequentially to take an action regarding its membership of a coalition, and the way this coalition should be optimised.
The new membership together with the optimisation proposal is not accepted straightforward, it is evaluated by the members of the target coalition. Just those actions accepted by a majority (more than the half) of members in the affected coalition, are performed. An agent that is requested to take an action can submit a finite number of requests in an specific order, in such a way that if an action is not accepted, next action is checked and so on. If none of its action proposals is accepted, the agent stays in the same coalition where it was.
Summarizing, the choices than an agent has are:
• Stay in the current coalition.
• Stay in the current coalition optimizing it by firing (expelling) one or more members.
• Leave the current coalition in order to join a different one.
• Leave the current coalition in order to replace one or more agents in a different one.
• Create a new coalition with itself as the only member.
Each of these actions potentially changes the coalition structures in the society and with many agents taking such actions each turn leads to an evolution of state.
This paper explores the effect of two possible agents strategies:
• competitive strategy (score maximizing)
• conservative strategy (payoff maximizing).
For the case of conservative strategy, the agent expects to obtain the maximum payoff at any time, while for competitive strategy, the agent invests for a future better payoff as a side effect of being in a highly competent coalition.
In both cases, an agent σ zi constructs an ordered set of actions proposals if requested: ψ i = (σ a , φ ab ), ...(σ p , φ pq ) . Those actions are evaluated sequentially until one is accepted or none of them is. For the case of score maximizer agents, ψ i contains all the possible proposals (σ x , φ xy ) for which one of the following conditions is satisfied:
In words, a competitive agent's action proposal set contain every proposal that either improves the score of the coalition the agent is in, or keeps the same score while reducing the size. Analogously, for the case of conservative strategy, all proposals in ψ i fulfil the same conditions but changing scr(σ x , T ) by CR(σ x , σ ), where σ stands for the partition resulting from any modification has been done to σ in the first argument of the function.
The order between two action proposals (σ a , φ ab ) and (σ c , φ cd ) in the proposals set ψ i for a given agent σ zi is defined in such a way that (σ a , φ ab ) > (σ c , φ cd ) if and only if one of the following conditions are satisfied for the case of competitive strategy:
Some proposals cannot be indexed with strict order, that is the case when having the score as a first ordering criterion and coalition size as a secondary ordering criterion, both proposals have the same characteristics:
In that case, a random order is established between consecutive proposals with equal value. Analogously, for the case of conservative strategy, the criteria used is the same but, again, using CR(σ x , σ ) instead of scr(σ x , T ).
Agents are not completely farsighted and neither they have information on the skills of other agents. The only information they have access to in addition to the their own skills and specification of the current task is:
• The potential score of their current coalition for the task.
• The precise outcome of any action they want to consider prior to its submission in terms of coalition score (however they have no information on the evolution of coalitions after its decision, nor the individual skills of agents in other coalitions).
The model considers a certain degree of randomness in the way agents are chosen to make a move. In every game, just a certain fixed number of actions are issued, and agents cannot make considerations on which agents will be elected to make a choice, nor what will be the order of the choices. Given these restrictions, we can consider agents in this model as myopically rational.
While the model presented in the previous section is quite specific (using a specific scoring function, pricing policy, set of strategies, etc.) it represents a good prototype for a variety of iterative coalition formation environments since it contains the major elements one would expect to see in such worlds: regular task arrival, agents slowly changing coalition structures over time to work with others and tension between coalition score and size due to payoff. For all the experiments performed, a significant range of variations was tried and results found to be robust across them. These parameters for the results shown here are: • Total value of a Task ( k j=1 T j ): 100 (it means, that the sum of every task's skill requirement will be 100 for all the tasks under test)
• Number of Games per experiment: 1000
• Number of Agent's decisions per game: 10 (it means, that the number of agents that will be asked to make a decision in one game is 10)
The rest of the parameters are variables related to the issue of heterogeneity discussed in this paper. Those parameters are:
• Heterogeneity of Population: value distribution amongst agents' skills
• Heterogeneity of Tasks: value distribution amongst task's required skills All agents have the same probability of being selected to make a choice, that is 1/|I|. The strategies of agents have been implemented by means of an exhaustive exploratory algorithm. When a competitive agent is requested to make a move, the algorithm checks all the possible actions of an agent. It checks the value of all possible join movements given the current situation, and for each option, checks every possible optimizations (see section 4.2) checking the score and the size of the resulting coalition. The algorithm constructs an ordered list of options that improve the situation the agent is in. Analogously, for conservative agents, it checks the payoff the agent would get instead of the score of the coalition.
In order to create experiments that represent a valid range of heterogeneous properties, three different tasks with different variability level (Sharpness) in their skills values distributions have been characterised. Namely the tasks types studied are: Low Sharp Task (LST ), Medium Sharp Task (MST ), and High Sharp Task (HST ). LST has its 10 skills required with a similar skills value (mean value is 10, and stdev. is 5.). MST has not that similar skills requirements, and two of its skills are not required (mean value is 10, and stdev. is 10, two skills with value 0). HST has widely varying skills requirements, demanding just 4 out of its 10 skills (mean value is 10, and stdev. is 15). Experiments also include three different types of populations with different expertise level. Namely the categories studied are: Low Sharp Agents (LSA), Medium Sharp Agents (MSA) and High Sharp Agents (HSA). Each of the three populations has 100 agents, but populations are created in such a way that there are 50 different skill setups for agents using competitive strategy and the same 50 skill setups duplicated for agents using conservative strategy. LSA is a set of generic abilities, characterised by a low standard deviation in their skill values (mean value is 20 and stdev. is 10). The MSA set has moderate standard deviation in their skill values (mean value is 20 and stdev. is 20 for all of them). HSA is a set of specialised agents, characterised by their high standard deviation in their skill values (mean value is 20 and stdev. is 30 for all of them).
In order to check the effect of heterogeneity in task requirements and agents population, in this configuration a total of 270 experiments have been run. Sets of 30 different LST, 30 different MST and 30 different HST tasks have been generated to cover the space of tasks. The experiments for each set were then run for each of the different populations of agents (LSA, MSA and HSA).
An important aspect of the results shown later is the analysis of compatibilities of agents using collaboration graphs. In order to observe how the population complements, results are shown for a given set of tasks and agents using the following analysis:
1. Agents participate in the coalition formation process sequentially for the defined tasks, creating partitions of the population for as many games as defined.
2. After each game, the one-to-one relationships established between members of the population are saved in that game.
3. After the final game, the frequency of these one-to-one relationships are compiled across all games and used to generates weights in a population graph.
The data generated in this way contains information on which agents often work together for the task set (which is distributed across the space of possible tasks). As a result this can be used to analyse, how agents cluster together for the concrete parameterisation of the experiment. The mechanism used to determine clustering is an implementation of Kamada-Kawai [11] algorithm in Pajek [4]. This algorithm places nodes in a bi-dimensional space in a close position when they are connected with links of relative high value. Graphs are created from data obtained by the clustering algorithm, and for the sake of the clarity, these also distinguish the frequency of cooperation between agents, not only by virtue of their position in the graph, but also with the colour of the arrows in such a way that they look darker when the relationships are more frequent, and lighter otherwise. Throughout the rest of the paper, these graphs are referred to as Collaboration Graphs. Competitive population (score maximization strategy) proves to be more effective throughout the whole series of experiments, outperforming conservative strategy (payoff maximization) on average. This fact is reflected in the total payoff obtained by each population in each experiment played. Figure 1 shows how the competitive population gets better payoff than conservative population in the majority of experiments. Table 1 1), shows that competitive populations do not behave homogeneously well in all the combinations. One can observe that there is a clear relationship between task heterogeneity and population profit. The more heterogeneous the task, the less advantage competitive population has. The key factor of this effect is coalition size. Coalitions formed when the task is heterogeneous have smaller size than when the task is homogeneous, because in the first case, some of the skills are not required, thus less expert agents are required to create a competent coalition. When the task requires many skills, competitive agents are willing to form coalitions which are as competent as possible, growing in size disregarding their benefits. The long term effect of this behaviour is that coalitions created by competitive agents turn out to be positioned in the top of the ranking, providing the highest benefits to their members. Conservative agents, in turn, optimise the competency/size ratio of the coalitions they form, thus reducing the size of the coalition as much as possible while keeping the same position in the competitivity ranking. When the difference from the score of conservative agents to the subsequent coalition in the ranking is sufficiently high, conservative agent's coalition will disintegrate their structures, losing competence, and giving chances to other coalitions to outperform it to occupy its rank. This situation usually happens when coalitions are big in size. The long term effect of this behaviour is that conservative coalitions are unstable and outperformed by competitive coalitions in these scenarios. This disadvantage is diminished when tasks sharpness degree is higher, as coalitions need not to be big, hence relative distances between scores in the competency ranking of coalitions is lower. This will not allow conservative agents to optimise the size of the coalition they are in, behaving like competitive agents, and obtaining very similar profits. The system under study generates different dynamics in the agents that make them create more or less similar coalitions throughout the whole set of experiments. The experiments revealed that it exists less stability and less similarity in coalitions created in the low Sharp tasks scenarios compared to those created in the high Sharp task ones. This could be counter intuitive given the fact that lower Sharp tasks are more similar to each other than higher Sharp tasks. This phenomenon, as in the case of the relationship between advantage of competitive population and sharpness level, is independent of the type of agent sharpness used.
Figure 2 shows the collaboration graphs for two different agents populations across the three different tasks sharpness. One can see that the higher is task sharpness, the more frequent are the relationships between agents (darker arrows between nodes). For HST graph case, it is also possible to distinguish different clusters of frequent collaboration between agents. The reason, as in the previous case, is the reduced size of coalitions formed in the HST scenarios. In the low sharpness setup a clear cluster of competitive agents appears. These agents are the best equipped agents of the population, and they form a stable and competitive coalition that finds no competence in the conservative population because of the disintegration effect explained in previous section. For lower ranking coalitions, competitive agents find more difficulties in stabilising themselves because there are competent conservative agents, that instead of forming a competent coalition, de-stabilise the rest of coalitions optimising their size and re-combining with different groups. For higher task sharpness levels, given that the disintegration effect in conservative agents is cancelled out by the reduced size of the coalitions, they create more stable collaboration structures.
The work presented is based on a model of coalition formation using a RFP protocol for the type of iterative coalition formation environment often found in competitive real world scenarios. While simple, this model can be used to study agent's behaviour in such systems that can be represented by the model abstraction. The results specifically address the effects of heterogeneity using two different coalition change strategies. From the experiments and the analysis performed we draw the following conclusions for these environments:
• Competitive strategy is more advantageous on average than conservative strategy independently of the heterogeneity level in the agent skill setup and the task skill requirements.
• There exists a direct relationship between task heterogeneity and similarity of results obtained by competitive and conservative strategy. I.e. the more heterogeneous is the task definition, the more similar will be the outcomes of the two populations
• Heterogeneous tasks make conservative strategy behave similarly to competitive one given that the optimization opportunities are scarce.
• There is no relationship between agent skill setup heterogeneity level and advantage or disadvantage of none of the strategies.
• It exists a direct relationship between task heterogeneity and frequency of collaboration patterns.
Above and beyond this, the experiments also show the clear result that in such populations the intrinsic compatibilities between agent skills emerge as important structuring criteria even if the agents do not specifically know each others skill sets. While this seems trivially true, it is rarely exploited in coalition formation work to date. In future work, the hope is to develop a more complete model of the evolution of coalition structures in such populations over long running episodes of iterative or continuous varied task arrival.