This paper explores a general model of economic exchange between heterogeneous agents representing ¯rms, traders, or other socioeconomic entities, that self-organise into coalitions to face speci¯c tasks. In particular, the work addresses coalition formation problems in which many tasks are addressed to the same population over time in an iterative fashion { giving the agents the possibility to organise themselves for speci¯c tasks. In particular, the purpose of the paper is to describe the impact of task and skill heterogeneity in the population on the performance of the agents. Experiments are carried out for two common strategies from the economic world, namely competitive and conservative strategies. Results obtained show that competitive population outperforms conservative population, and that the heterogeneity degree has a direct e®ect on the advantage of the ¯rst strategy versus the second. We analyse experimental results by using a novel data mining technique called collaboration graphs.
The organizational paradigm of our economic model is Coalition Formation. These models have
been extensively studied from a game theoretic perspective initially ([
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 [
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 de¯nition, 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 e®ect of heterogeneity on the strategies outcomes. Section 7 analyses the results on the e®ect of heterogeneity in the collaboration structures between agents. Finally, Section 8 wraps up the results obtained showing the conclusion of the present work. 3
Request For Proposal Systems (RFP Systems from now on) are de¯ned 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 di®erent economic activities such as European Calls for project proposals in di®erent 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 considered 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 payo®. ² Some systems, may also have policies for rewarding 2nd, 3rd, 4th 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 payo® maximization, but might have di®erent strategies for maximizing their utility. 4
A population I = f1; 2; : : : ; ng consists of a ¯nite number of n individuals or agents. Agents compete amongst them given the requirements speci¯ed by a certain task T . A partition ¾ = f¾1; ¾2; : : : ; ¾pg of the population I is a speci¯cation of p coalitions of agents ¾i = f¾i1; ¾i2; : : : ; ¾img, 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 speci¯ed task.
Agents have heterogeneous capabilities, thus having di®erent performance levels in di®erent skills. A ¯nite number of k skills, indexed from 1 to k is set for which each agent ¾ij has a ¯xed value: ¾ij = h¾i1j ; ¾i2j ; : : : ; ¾ikj i. In this way it is possible to de¯ne 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 de¯ned.
A Task T is speci¯ed 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 = hT 1; T 2; : : : ; T ki .
In a coalition, skills of agents are aggregated in such a way that each agent gives the best of itself in a join e®ort 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 e®ort of its members. The aggregation for every skill j : 1 · l · k in the coalition is modelled in the following way: ¾il = max (¾ilj ) : 1 · j · m (1)
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. Each skill is considered as a necessary subtask for performing i task T . In this way, by using the aggregation function shown in equation 1, the agent in a coalition which is the best ¯t 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 di®erent 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 ¯tted for that part of the work. 4.0.1
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 payo® 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 de¯ne a score function scr(¾x; T ) to measure how well agents in coalition ¾x perform together for accomplishing a task speci¯cation T without having into account the rest of coalitions.
As explained in section 4, Tasks are speci¯ed 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: (2) (3) 4.0.2
Once we have the endogenous value of a coalition, it is necessary to assign the payo® depending on its ranking. That constitutes the second steep required for computing the general coalition utility (the coalition's payo®).
The reward function de¯ned 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 2 ¾.
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 ¯xed amount P of payo® to spread amongst the coalitions, independently on the number of coalitions existent. Formally: scr(¾i; T ) =
k X (¾il ¤ T l) l=0
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 re°ects models used for coalition formation in a large part of the current literature.
CR(¾x; ¾) = (P=2rank(¾x;¾)¡2; for the last competent coalition,
P=2rank(¾x;¾)¡1; for all the other competent coalitions.
Amongst the di®erent possibilities for assigning the payo®, this concrete exponential function
has been chosen for two reasons: ¯rst, 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 di®erent populations. The second reason is because this represents a power
law distribution of wealth for which there is empirical evidence from Real Economies (see [
As a simpli¯cation however, Agents within a coalition spread coalition's payo® evenly (and hence methods for di®erential allocation of payo® to individual agents are not applied here). While this removes some complex coalition formation issues it still forces a tradeo® for agents between coalition size (in order to be more competent, thus gain a higher score and being more group pro¯table), and coalition optimality (in order to share the payo® by a reduced set of members, and so being individually pro¯table). This sub-section de¯nes the actions agents can take between di®erent 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 di®erent 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 a®ected coalition, are performed. An agent that is requested to take an action can submit a ¯nite number of requests in an speci¯c 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 ¯ring (expelling) one or more members. ² Leave the current coalition in order to join a di®erent one. ² Leave the current coalition in order to replace one or more agents in a di®erent 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. 4.2
This paper explores the e®ect of two possible agents strategies: ² competitive strategy (score maximizing) ² conservative strategy (payo® maximizing).
For the case of conservative strategy, the agent expects to obtain the maximum payo® at any time, while for competitive strategy, the agent invests for a future better payo® as a side e®ect of being in a highly competent coalition.
In both cases, an agent ¾zi constructs an ordered set of actions proposals if requested: Ãi = h(¾a; Áab); :::(¾p; Ápq)i. 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 satis¯ed:
scr(¾x ¡ Áxy + ¾zi; T ) > scr(¾z; T ) or
scr(¾x ¡ Áxy + ¾zi; T ) = scr(¾z; T ) ^ jf¾x ¡ Áxy + ¾zigj < j¾zj
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 ful¯l the same conditions but changing scr(¾x; T ) by CR(¾x; ¾0), where ¾0 stands for the partition resulting from any modi¯cation has been done to ¾ in the ¯rst argument of the function. (4) (5)
The order between two action proposals (¾a; Áab) and (¾c; Ácd) in the proposals set Ãi for a given agent ¾zi is de¯ned in such a way that (¾a; Áab) > (¾c; Ácd) if and only if one of the following conditions are satis¯ed for the case of competitive strategy:
(src(f¾a ¡ Áab + ¾zig; T ) > (src(f¾c ¡ Ácd + ¾zig; T ) or
(src(f¾a ¡ Áab + ¾zig; T ) = (src(f¾c ¡ Ácd + ¾zig; T ) ^ (jf¾a ¡ Áabgj < jf¾c ¡ Ácdgj) Some proposals cannot be indexed with strict order, that is the case when having the score as a ¯rst ordering criterion and coalition size as a secondary ordering criterion, both proposals have the same characteristics: (src(f¾a ¡ Áab + ¾zig; T ) = (src(f¾c ¡ Ácd + ¾zig; T ) ^ jf¾a ¡ Áabgj = jf¾c ¡ Ácdgj ^ ((a 6= c) _ (b 6= d)) 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; ¾0) 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 speci¯cation 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 ¯xed 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. 5
While the model presented in the previous section is quite speci¯c (using a speci¯c 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 payo®.
For all the experiments performed, a signi¯cant range of variations was tried and results found to be robust across them. These parameters for the results shown here are: (6) (7) (8) ² Population size (jIj): 100 ² Number of Skills (k): 10 ² Total value of an agent (Pk
j=1 ¾xjy): 200 (it means, that the sum of every agent's skill will be 200 for all the agents) ² Total value of a Task (Pk
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=jIj. 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 payo® 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 di®erent 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 di®erent types of populations with di®erent 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 di®erent 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 e®ect of heterogeneity in task requirements and agents population, in this con¯guration a total of 270 experiments have been run. Sets of 30 di®erent LST, 30 di®erent MST and 30 di®erent HST tasks have been generated to cover the space of tasks. The experiments for each set were then run for each of the di®erent populations of agents (LSA, MSA and HSA). 5.1
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 de¯ned tasks, creating partitions of the population for as many games as de¯ned. 2. After each game, the one-to-one relationships established between members of the population are saved in that game. 3. After the ¯nal 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 [
LSA MSA HSA
LST avg:707 stdev:184 avg:567 stdev:215 avg:581 stdev:155
MST avg:519 stdev:172 avg:455 stdev:230 avg:471 stdev:172
HST avg:195 stdev:155 avg:172 stdev:124 avg:212 stdev:163
Competitive population (score maximization strategy) proves to be more e®ective throughout the whole series of experiments, outperforming conservative strategy (payo® maximization) on average. This fact is re°ected in the total payo® obtained by each population in each experiment played. Figure 1 shows how the competitive population gets better payo® than conservative population in the majority of experiments. Table 1 summarizes these results. Values in the table are the average di®erence between what the competitive population obtained in an experiment minus what the conservative population obtained in the same experiment. The same table also re°ects the standard deviation on these di®erent values. The table shows numerically that competitive population outperforms conservative population for every type of heterogeneity combination.
Table 1 (as well as in Figure 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 pro¯t. The more heterogeneous the task, the less advantage competitive population has. The key factor of this e®ect is coalition size. Coalitions formed when the task is heterogeneous have smaller size than when the task is homogeneous, because in the ¯rst 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 bene¯ts. The long term e®ect of this behaviour is that coalitions created by competitive agents turn out to be positioned in the top of the ranking, providing the highest bene¯ts 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 di®erence from the score of conservative agents to the subsequent coalition in the ranking is su±ciently 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 e®ect 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 pro¯ts.
(a) Payo® obtained for each strategy population in a LSA skill setup for every experiment in each one of the three tasks setups (LST, MST and HST). (b) Payo® obtained for each strategy population in a MSA skill setup for every experiment in each one of the three tasks setups (LST, MST and HST). (c) Payo® obtained for each strategy population in a HSA skill setup for every experiment in each one of the three tasks setups (LST, MST and
HST).
The system under study generates di®erent 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 di®erent agents populations across the three di®erent 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 di®erent 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 ¯nds no competence in the conservative population because of the disintegration e®ect explained in previous section. For lower ranking coalitions, competitive agents ¯nd more di±culties 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 di®erent groups. For higher task sharpness levels, given that the disintegration e®ect in conservative agents is cancelled out by the reduced size of the coalitions, they create more stable collaboration structures. 8
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 speci¯cally address the e®ects of heterogeneity using two di®erent 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 de¯nition, 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 speci¯cally 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.
Econometrica,