The distribution of a set of goods (such as ¯nite allowed numbers of electronic goods, physical objects or ¯xed roles in an organization) amongst a set of agents with varying preferences is a complex combinatorial problem. While algorithms such as the Hungarian method exist to solve this type of Assignment Problem, these rely on central allocation with complete information about preferences, compliance by agents to allocations and altruistic acceptance of agents of their assignment for the greater goods. Unfortunately however, these assumptions are unrealistic in most operational settings. In this paper, we compare a number of economically inspired (speci¯cally virtual currency based markets and bartering) approaches which allow the redistribution of goods amongst agents using self organization and do not require complete global information or centralized processing. Results show that in a range of scenarios 1) such techniques can get close to the optimal solutions produced by centralized algorithms, 2) their stability and optimality are radically a®ected by the heterogeneity of agent preferences for goods in the population. The results also con¯rm that bartering is clearly outperformed in most settings by more °exible currency based approaches.
Koutsoupias ([
Standard optimization methods to solve this problem ([
A simpler mechanism to model such environments is de¯ning exchange protocols which allow individual agents to act locally and maximize their own utility. Candidate approaches include bartering methods (in which agents swap items 1 for 1) and currency based markets (in which agents sell their own goods for pro¯t and buy other goods of higher utility). The questions which arise however are: Can such methods achieve optimal results? and What are the properties of individual approaches?
The problem statement for the type of system studied is as follows. Let A = fa0, a1, . . . , ajNjg and F = ff0, f1, . . . , fjMjg denote a set of agents and goods respectively; and sij = s[ai; fj], be a measure of the level of satisfaction that an agent ai can obtain for a goods fj. Then formally, the objective of the jAj x jF j is to ¯nd the particular total assignment mapping ¡ : A ) F such that for ai, aj 2 A, i 6= j implies ¡(ai) 6= ¡(aj), and the total satisfaction Stot = PjiN=0j s[ai; ¡(ai)] is maximized over all possible permutations of ¡. Intuitively, ¡ is a one{to{one mapping of tasks to resources. Each permutation represents an assignment (or allocation) set. In our case, with respect the classical de¯nition, only we have added that an agent can hold more than one goods.
This paper focuses on the study of the environment of goods{sharing that has multiple users deciding how to distribute their budget amongst multiple available goods according to their individual preferences, where the aim of the members is to maximize their individual utility. The experiments described show the e®ects of a number of di®erent exchange policies and compare their performance to optimal allocations.
The remainder of this paper is organized as follows. Section 2 introduces the modeling framework. Section 3 shows the experimental setup and establishes the results. After looking at general problems related with the use of market approach in Section 4, Section 5 covers related work. Finally, Section 6 summarizes the paper and Section 7 discussed future work. 2
The underlying system studied models an environment composed of agents which wish to obtain goods to maximize their satisfaction (utility). Each agent has a preference for each goods in the system and will always prefer to obtain goods with the most suitable preference for it. Agents are autonomous agents in a game{theoretic sense, they always try to obtain the maximum bene¯t. In this case, the bene¯t is related to the utility that agents achieve when they have a certain goods. However, depending on the mechanism in force for the exchange of goods (bartering or a market based on tokens which can be exchanged for goods), agents use di®erent strategies to improve their situations. Speci¯cally, agents can chose: when to o®er their own goods, when to obtain goods from others and, in bartering, which goods to exchange.
At the level of the agent a trade is possible (in a currency based market), if and only if, agentA wants a goods from agentB, agentA has tokens to buy the goods and agentB is interested in selling the goods. In bartering scenario, both agents must stand to gain (or at least not loose) in a ¯le{ swap. In the simple model applied here further, simulations start with a forced step which ensures that a certain number of agents o®ers goods initially (to ensure trading begins) - without this in certain scenarios no trading begins and/or continues. 1 3
A simulator has been developed to model an agent based goods{sharing system as a market and
bartering environment. The simulations capture the step{by{step evolution of the distribution of
goods amongst all agents in the system. For the sake of simplicity, number abstractions have been
made:
² The price of each goods is always the same for whatever goods is in the market, and also
these prices do not vary in function of demand.
² Agents can o®er/not o®er their goods or buy goods from others; however they cannot, for
example, who they o®er goods to (everybody or nobody).
² In bartering, only two way swaps are allowed { that is a single agent exchanging goods with
a single other agent.
1More information about the model is available in [
Experiments reported here use the following settings (however the results are stable across variations of the parameters such as greater populations of agents, di®erent starting conditions in terms of funds etc.): ² Number of agents: 500 ² Number of di®erent goods: 1.500 ² Number of goods in which an agent is interested in: 3 ² Quantity of tokens per agent (initial step): 4.000 ² Quantity of tokens per goods: 500 ² Quantity of satisfaction associated per goods: From 0 to 10.000 ² Quantity of goods assigned at the initial step per agent: 3
For currency{based approaches, three di®erent market strategies are studied with respect to the o®ering action: ² Monetary { Least restrictive: The o®ering strategy in this case is that when some goods in the market which is better than any of the agent's own goods, everything that belongs to this agent is o®ered to the market. This scenario is the most risk assuming, because in many cases, the agent could lose more satisfaction selling their better goods that the possible satisfaction obtained with the desired goods. Example: An agentA is owner of the pairs (goods, value) such as: (f ile1, 1.000), (f ile2, 2.000),(f ile3, 3.000) and (f ile4, 4.000) and where the market is o®ering (f ilex, 2.500). It will implies that agentA will o®er f ile1, f ile2, f ile3 and f ile4. ² Monetary { Medium restrictive: In this case, the agents only o®er goods that have less satisfaction than the max. satisfaction o®ered by the market. With this approach, agents are limiting the risk of losing satisfaction, because they are not o®ering more than can be recovered from the market. Even so, they are assuming risk, since when an agent sells a goods, the agent loses the associated satisfaction of the goods and it could be possible that in the high value goods in the market have in the meantime been purchase by someone else or removed by their owner. Example: An agentA is owner of the pairs (goods, value) such as: (f ile1, 1.000), (f ile2, 2.000), (f ile3, 3.000) and (f ile4, 4.000) and where the market is o®ering (f ilex, 2.500). It will implies that agentA will o®er f ile1, f ile2. ² Monetary { Most restrictive: In this case, the worst goods is not scored in terms of agents' satisfaction. Also this goods is only o®ered if the system o®ers something better (as in the previous scenario). Using this policy, agents are not assuming risk since satisfaction for the agent is always equal or higher. However, the negative aspect of this approach is that the quantity of o®ered goods will be lower than in the previous scenario and it could restrict the number of trades being carried out or the time being consumed in this scenario. Example: An agentA is owner of the pairs (goods, value) such as: (f ile1, 1.000), (f ile2, 2.000), (f ile3, 3.000) and (f ile4, 4.000) and where the market is o®ering (f ilex, 2.500). It will implies that agentA will o®er f ile1.
For the bartering{based approach, the strategy is straightforward, the agents only trades goods by goods and only in the case that both parties bene¯t from the exchange. Example: An agenta has (f ile1, 2.000) and in its list of preferences (f ile2, 3.000). And another agent, agentb has (f ile2, 1.500) and in its list of preferences (f ile1, 2.500). In this situation both agents can interchange their goods since both agents obtain bene¯t from the trade.
The last parameter is related to the distribution of preferences for goods amongst agents. This element re°ects the popularity of goods in the system. Two di®erent scenarios are analyzed: ² Heterogeneous preferences lists: In this case, agents each value goods in the system independently { that is, each agent may have di®erent preferences. Example: agentA and agentB are interested in f ile1 and they worth the ¯le in 2.000.
Monetary { Least restrictive Monetary { Medium restrictive
Monetary { Most restrictive
Bartering
Scenario 2 a
Scenario 2 b ² Homogeneous preferences lists: In this case, agents have the same valuations for each goods as other agents do { that is, all agents value each goods in the same way. Example: agentA and agentB are interested in f ile1. In this case, agentA worths f ile1 in 2.000 and for the agentB the same ¯le has a value of 3.000.
The two ¯gures relate the economic scenarios versus the optimal assignment obtained by means of the centralized and altruistic acceptance Hungarian Algorithm. Values that appear in the ¯gures correspond to the mean value of 5 di®erent simulations. Furthermore, the period of time shows from the initial step (time 0) until the moment where no one is o®ering goods in the market. With these two ¯gures we wish to show the global level of satisfaction obtained following a centralized approach versus a distributed one. The information o®ered allows us to compare how far away from the optimum the di®erent scenarios are and how the scenarios are ranked with respect to one another.
Figure 1 shows the global satisfaction in the di®erent scenarios with the passing of time when agents have di®erent preferences per goods (i.e. heterogeneous preferences). With respect to Scenario 1.1 a), agents start in the market with an initial level of satisfaction, the same one as in the rest of scenarios. This initial level of satisfaction concerns the initial random distribution of goods. After this, agents trade in order to improve this level of satisfaction. However, they get to a moment in tick 25, where agents have a goods level of satisfaction and it is di±cult to make trades. At the end, the lack of bene¯t in trading cuts out all interchanges. In Scenario 1.2 a), agents will trade in order to improve their level of satisfaction. The results are similar with the previous scenario. The di®erence with respect to the previous scenario is the quantity of trades. In the ¯rst scenario in many cases a huge quantity of goods are o®ered in the market but many of these trades do not improve the global level of satisfaction. Finally in Scenario 1.3 a), the agents get lower values, with respect to previous scenarios. In may seem that a less risky policy should obtain better results than the rest of policies, which are assuming more risk. The problem is that a market where no one wants to assume risk and few goods are o®ered, in a short time will stop T I F E N E FB 6000 O L E V LE 4000 L A B O L G 2000 0 5
Optimal assignment
Simulation 1.1 b Simulation 1.2 b Simulation 1.3 b
Simulation 2 b 10 15 20 the chain of trades. In Scenario 2 a), where tokens are not used, the conditions to make a trade are more di±cult to ful¯l. In order to make a trade both parties involved in the process should be agree - requiring the double coincidence of wants.
Figure 2 shows the global satisfaction in the di®erent scenarios with the passing of time when agents have the same preferences per goods. With respect Scenario 1.1 b), many trades are carried out - however the level of satisfaction is not improved because the goods change from owner but they do not change the satisfaction that produces. In Scenario 1.2 b) between ticks 5 and 35 a smooth decrease appears, the reason for this result is related to the capacity of agents to hold goods and to the forced step. In the initial step the goods is distributed by their members: to each agent between 0..3 goods are assigned. During the forced step, when agents have 3 goods and buy a goods, in global terms the whole level of satisfaction decreases. They are removing the satisfaction o®ered by the goods to its owner and also they are removing the satisfaction o®ered by the worst of their goods, because only three of them are scored (note that while this is an obvious property of the scenario the important thing to note is that interactions produce a large number of trades { even if there can be no overall gain { since individual agents seek to optimize their scores). Scenario 2 b) is the only case where the market does not trade at all.
Scenario 1.1 a) and scenario 1.2 a) get results near the 8.500 and the optimum is 9.200. The optimal value is only 8% better, in global terms. During the ¯rst's steps of the simulations, in both cases, the market is crowded with goods that are interchanged, making the level of satisfaction increase rapidly. However, scenario 1.3 a) and scenario 2 a) only get 5.700, a value far from the optimal. The optimal allocation obtains a 39% better result. In both scenarios the problem is the lacks of trades, but for di®erent reasons. In the scenario 1.3 a) forced steps mean that some members will have a large set of goods and others have few goods making it di±cult for some to \trade up". In scenario 2 a) the reason of the lack of trades is because not many matches are made during the simulation due to a double coincided of wants in a market.
In all the scenarios where homogeneous preferences list were studied, a great di®erence between the satisfaction obtained, around 4.600, and the optimal allocation 7.800 can be seen. In this case, the optimal allocation obtains a 58% better result. 4
From the experiments, a number of clear e®ects can be seen. The following illustrates these e®ects: ² In the Hungarian algorithm with homogeneous preferences a good has the same value for everyone. On the others, with heterogeneous preferences, a good has di®erent value for each agent in the community. This di®erence implies that the global level of satisfaction will be di®erent in both cases. In the ¯rst case, the matching process between goods and agents, in global terms is not important, because for a global point of view the algorithm gets the same social welfare if a goods is assigned to one or another agent. On the contrary when each agent has its own preferences, the matching process is relevant and the best assignment should be achieved (following the requirement that everyone has their own preferences). ² With homogeneous preferences lists, popular goods, with bartering based approach, nobody wants to trade because the condition bene¯t (A of fb) > bene¯t (B of fa) and bene¯t (B of fa) > bene¯t (A of fb) where A, B are agents and fx is the goods that belongs to the agent x, will never hold true. ² Using heterogeneous preferences lists, unpopular goods, with the bartering based approach, not many trades will be carried out. A slight improvement is detectable with respect the level of satisfaction. However, due to the small amount of agents and goods, the social level of satisfaction is far from the social optimum. ² With homogeneous preferences lists, popular goods, with the currency based approach, since goods having the same contribution for any node in the market the global level, the satisfaction is not in fact change through trade. ² With respect to the quantity of goods o®ered in the system with homogeneous/heterogeneous preferences list. In the former, a large quantity of goods is o®ered in the less and medium restrictive policies, however with the restrictive policy, goods are only o®ered during the forced step. In the heterogeneous approach, in the ¯rst steps, many goods are o®ered with all three policies but as the system obtains goods global levels of satisfaction less goods will be o®ered in the market. Only the least restrictive policy follows a di®erent pattern with agents o®ering a goods as long as they do not have those they would like { however, often not ¯nding the goods they would like. ² Given a random initial assignment, a token-based approach and currency based approach did not guarantee an optimal solution. ² In the currency approach the di®erent policies o®er more or less goods in the market. This o®er has a direct relation to the quantity of goods traded in the market. However, a least restrictive policy could imply a set of lost trades or non{signi¯cant trades because the same goods is bought and sold many times.
In general terms, currency based approaches perform signi¯cantly better than the bartering approach. But the preferences for goods in the population has a great impact in the quantity of trades made in the market and therefore at the distance with respect to the optimal is a®ected by this variation in the taste of the users. 4.1
In barter economies, users directly trade resources between each other which provide simultaneous and equally satisfying returns. This system has some bene¯ts such as a simple, decentralized, memory{less and is based directly on evidence of cooperation. But the results also clearly show problems: ² An important disadvantage appears when agentA wants something from agentB and agentA does not necessarily have anything that agentB needs (the lack of a double coincidence of wants). Before any transaction can be undertaken, each party must be able to supply something the other party demands. 2 ² Another problem in this type of market is related to the concept of 1 to 1 trades. Supposing a con¯guration where agentA has the goods c1; c2; c3 and it prefers goods a1; a2; a3 (in this order), agentB has the goods a1; a2; b3 and it prefers goods b1; b2; b3 (in this order) and ¯nally agentC has the goods a3; b1; b2 and it prefers goods c1; c2; c3 (in this order). The ¯rst trade 2http://economics.about.com/library/glossary/bldef-double-coincidence-of-wants.htm is made between agentA and agentC , changing c1 and a3. It means that agentA will have the goods a3; c2 and c3 and agentC will have goods c1; b1 and b2. So after that, agentA and agentB try to make a trade, but agentA has not anything interesting to o®er to agentB and the trade does not take place. The next trade could be between agentC and agentB but they do not have anything to trade. The reason is because agentB has nothing of interest to o®er to agentC , and agentC has the same problem. If, in the previous step, agentB had sold goods to agentA (e.g. a1 by c2), agentB would have now some interesting goods for agentC , that it could have negotiated in this step with agentC . This certi¯es that the bartering system only works 1 to 1. 4.2
This section covers the e®ect of the preference list parameter in the experiments studied. The
optimum allocation changes depending on preferences of the users. Basically two possible policies,
totally opposed, are studied such as: homogeneous and heterogeneous preferences list. In the
homogeneous case it is easy to know whichever goods the agents desire (i.e. n), to arrange the
goods available and assigning the goods to the agents until arriving at the number n. In the
heterogeneous case, this is not possible with this algorithm because a goods has a di®erent value
for each agent and the previous algorithm could obtain a solution, but probably this solution will
not be the optimal one, in global terms. This means, that it is not possible to follow a linear
approach and other algorithms should be used. Some of these approaches amongst others are the
Munkres algorithm [
In [
In [
This paper shows preliminary results for a variety of economically inspired resource distribution mechanisms which can be used by self-organizing agents to distributed goods.
The ¯rst important aspect of this is to show that in a range of scenarios results from distributed,
non{altruistic members in a system can produce close to optimal allocations. The majority of
¯le sharing applications (for example) rely heavily on the presence of altruistic users. However,
especially in systems which do not allow copies to be retained after passing on a ¯le. The danger
of the presence of too many free-riders will reduce or force to zero the number of altruists in the
population, thus stopping a system from functioning [
The most important objective of goods distribution application is that its users have everything that they need/want from the market. The important issue was in this case to know how a market{ based approach is successful with respect to the optimum assignment.
With respect to the market rules at the moment to o®er goods, a least restrictive policy is to assume more individual risks than a most restrictive policy. However, on the other hand the quantity of goods o®ered in this market is greater than in a most restrictive approach. More available goods imply more opportunities to improve for members in the community and means that more trades will be done in the system, making the variations of level of satisfaction greater than in a conservative approach. The last parameter studied, the popularity of goods show a great relevance in the results obtained (homogeneous versus heterogeneous) in the scenario section. In the heterogeneous approach implies less quantity of possible trades, because in many cases the seller will not agree with making a trade.
Summarizing, in the paper two di®erent approaches for the assignment problem has been
compared. The classical one, what obtains a optimal result but has inherent limitations such as
centralization and altruistic acceptance of agents of their assignment. And the approach has based on
tokens, which does not get optimal results but breaks these restrictions. A natural environment to
apply these techniques qould be in P2P ¯le{sharing application and the rental markets when rights
management restrictions limit the number of copies. [
Future work planned includes:
² Adopting di®erent policies at the moment of o®ering goods. To assume more individual risk
implies that more goods are available in the market. However, at the same time in global
terms it is more likely that the level of satisfaction is higher with respect to policies that
assume less risk.
² Considering that trades are expensive how can one modify the market strategies to o®er/buy
in order to reduce the quantity of intermediate and not fruitful trades?
² To consider open questions related with the market such as: Is this system stable, or are the
fees generally decreasing until no one are willing to contribute? Do such markets become
more e±cient as the number of participants increases? Are such markets more e±cient as the
variety of goods increases?
² Many interactions, both economic and social ([