Introduction

Koutsoupias ([5], [11]) coined the term the "price of anarchy" to refer to the increase in cost caused by independent selfish behavior [16] with respect to a social welfare-maximizing solution. Classical approaches to the Assignment Problem (AP) strive for just such a social welfare-maximizing solution. Specifically the problem consists of allocating a finite set of goods to a finite set of agents where each agent has a specific utility for each goods. The challenge in typical AP scenarios is to maximize the overall social welfare (utility) over the whole population of agents.

Standard optimization methods to solve this problem ( [13], [1] and others) however make several important assumptions. The first is that allocations are made by a centralized process which has A) access to the preference information of all agents, and B) is empowered to make this allocation. Secondly, the methods thereby implicitly assume that agents in the population accept results of the allocation -even if their own utility may decrease in a particular global solution (they act in an altruistic manner towards the overall population). However, in a distributed environment where agents try to obtain maximum benefit in an independent way, classical AP methods are unrealistic since they deal with the problem of allocation at community level and ignore the autonomy of the individual. Further in large-scale systems (as in goods-exchange systems which do no allow copies or markets for unique durable goods) the number of agents could be huge, hindering information access and processing.

A simpler mechanism to model such environments is defining 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 profit 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 = {a 0 , a 1 , . . . , a |N | } and F = {f 0 , f 1 , . . . , f |M | } denote a set of agents and goods respectively; and s ij = s[a i , f j ], be a measure of the level of satisfaction that an agent a i can obtain for a goods f j . Then formally, the objective of the |A| x |F | is to find the particular total assignment mapping Γ : A ⇒ F such that for a i , a j ∈ A, i = j implies Γ(a i ) = Γ(a j ), and the total satisfaction

S tot = |N | i=0 s[a i , Γ(a i )]

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 definition, 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 effects of a number of different 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.

System model

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 benefit. In this case, the benefit 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 different strategies to improve their situations. Specifically, agents can chose: when to offer 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, agent A wants a goods from agent B , agent A has tokens to buy the goods and agent B is interested in selling the goods. In bartering scenario, both agents must stand to gain (or at least not loose) in a fileswap. In the simple model applied here further, simulations start with a forced step which ensures that a certain number of agents offers goods initially (to ensure trading begins) -without this in certain scenarios no trading begins and/or continues. 1

Simulation

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 offer/not offer their goods or buy goods from others; however they cannot, for example, who they offer 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.

Experiments reported here use the following settings (however the results are stable across variations of the parameters such as greater populations of agents, different starting conditions in terms of funds etc.):

• Number of agents: 500

• Number of different 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 different market strategies are studied with respect to the offering action:

• Monetary -Least restrictive: The offering 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 offered 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 agent A is owner of the pairs (goods, value) such as: (f ile 1 , 1.000), (f ile 2 , 2.000),(f ile 3 , 3.000) and (f ile 4 , 4.000) and where the market is offering (f ile x , 2.500). It will implies that agent A will offer f ile 1 , f ile 2 , f ile 3 and f ile 4 .

• Monetary -Medium restrictive: In this case, the agents only offer goods that have less satisfaction than the max. satisfaction offered by the market. With this approach, agents are limiting the risk of losing satisfaction, because they are not offering 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 agent A is owner of the pairs (goods, value) such as: (f ile 1 , 1.000), (f ile 2 , 2.000), (f ile 3 , 3.000) and (f ile 4 , 4.000) and where the market is offering (f ile x , 2.500). It will implies that agent A will offer f ile 1 , f ile 2 .

• Monetary -Most restrictive: In this case, the worst goods is not scored in terms of agents' satisfaction. Also this goods is only offered if the system offers 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 offered 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 agent A is owner of the pairs (goods, value) such as: (f ile 1 , 1.000), (f ile 2 , 2.000), (f ile 3 , 3.000) and (f ile 4 , 4.000) and where the market is offering (f ile x , 2.500). It will implies that agent A will offer f ile 1 .

For the bartering-based approach, the strategy is straightforward, the agents only trades goods by goods and only in the case that both parties benefit from the exchange. Example: An agent a has (f ile 1 , 2.000) and in its list of preferences (f ile 2 , 3.000). And another agent, agent b has (f ile 2 , 1.500) and in its list of preferences (f ile 1 , 2.500). In this situation both agents can interchange their goods since both agents obtain benefit from the trade.

The last parameter is related to the distribution of preferences for goods amongst agents. This element reflects the popularity of goods in the system. Two different scenarios are analyzed:

• Heterogeneous preferences lists: In this case, agents each value goods in the system independently -that is, each agent may have different preferences. Example: agent A and agent B are interested in f ile 1 and they worth the file in 2.000. The two figures relate the economic scenarios versus the optimal assignment obtained by means of the centralized and altruistic acceptance Hungarian Algorithm. Values that appear in the figures correspond to the mean value of 5 different simulations. Furthermore, the period of time shows from the initial step (time 0) until the moment where no one is offering goods in the market. With these two figures we wish to show the global level of satisfaction obtained following a centralized approach versus a distributed one. The information offered allows us to compare how far away from the optimum the different scenarios are and how the scenarios are ranked with respect to one another.

Figure 1 shows the global satisfaction in the different scenarios with the passing of time when agents have different 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 difficult to make trades. At the end, the lack of benefit 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 difference with respect to the previous scenario is the quantity of trades. In the first scenario in many cases a huge quantity of goods are offered 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 offered, in a short time will stop the chain of trades. In Scenario 2 a), where tokens are not used, the conditions to make a trade are more difficult to fulfil. 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 different 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 offered by the goods to its owner and also they are removing the satisfaction offered 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 tradeseven 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 first'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 different 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 difficult 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 difference 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.

Analysis of Results

From the experiments, a number of clear effects can be seen. The following illustrates these effects:

• In the Hungarian algorithm with homogeneous preferences a good has the same value for everyone. On the others, with heterogeneous preferences, a good has different value for each agent in the community. This difference implies that the global level of satisfaction will be different in both cases. In the first 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 benefit (A of f b ) > benefit (B of f a ) and benefit (B of f a ) > benefit (A of f b ) where A, B are agents and f x 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 offered in the system with homogeneous/heterogeneous preferences list. In the former, a large quantity of goods is offered in the less and medium restrictive policies, however with the restrictive policy, goods are only offered during the forced step. In the heterogeneous approach, in the first steps, many goods are offered with all three policies but as the system obtains goods global levels of satisfaction less goods will be offered in the market. Only the least restrictive policy follows a different pattern with agents offering a goods as long as they do not have those they would like -however, often not finding 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 different policies offer more or less goods in the market. This offer 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-significant trades because the same goods is bought and sold many times.

In general terms, currency based approaches perform significantly 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 affected by this variation in the taste of the users.

Bartering market problems

In barter economies, users directly trade resources between each other which provide simultaneous and equally satisfying returns. This system has some benefits 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 agent A wants something from agent B and agent A does not necessarily have anything that agent B 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.

Agent preferences

This section covers the effect of the preference list parameter in the experiments studied. The optimum allocation changes depending on preferences of the users. Basically 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 different 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 [15], the Hungarian method [13], the Blossom algorithm [6]. Thus, we will use the maximum weight matching algorithm to compute the social optimum. Maximum weight matching is a classical network problem and can be solved in polynomial time. We have chosen to implement the classical AP the Hungarian algorithm [13] because of its simplicity. A distributed version of the algorithm was studied in [17] using the agent reasoning metaphor of Belief-Desire-Intention, however this approach also assumes altruistic agents accepting decisions.

Related Work

In [9] and [2] cover economic models for allocated resources. The economic approach is based on the decentralized control of resources in complex computer system using the concept of price. From those theoretical studies real systems such as Mojo Nation, eMule, Kazaa were developed. Mojo Nation was one of the first systems that introduced an artificial money called "Mojo". Mojo can be earned by offering resources. This money can be used for downloading or publishing goods. These real examples provided to us notions that we can apply in our simulator.

In [4] and [8] the allocation of resources and welfare engineering were studied. These works offer an approach to the allocation of indivisible resources amongst autonomous agents and provide us with a useful description about the different parameters that characterize a system for Multiagent Resource Allocation. Also [19] and [18] covers negotiation and interaction environments which provide useful structures for design of exchange policies.

Conclusions

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 first 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 file 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 file. 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 [14]. On the other hand, if altruistic nodes offer a great quantity of goods, the system could be transformed from a distributed to a centralized system. Using a system of tokens in order to exchange goods, agents in the market follow an economic behavior where a rational agent only spends tokens on those goods that the agent has interest. And the agent will only sell goods when the sale strategy considers that is opportune depending in which scenario the agent is offering. For example, in scenario 1.2 a) is opportune to offer goods if and only if the market offers some interesting goods. What could happen if the agent wants to follow other behavior?

• If an agent follows an altruistic behavior: In this case, an agent with tokens is offering goods an it implies a certain cost associated. If the agent assumes this increasing cost, the agent could participate with the members in the market, in other case the agent can not interact in the market.

• If an agent follows a selfish behavior: In this case, the agent can spend the money that has, buying goods from the market. Increasing its satisfaction. But the agent that follows this behavior, in a certain moment, will be broke. Because only using up tokens and is not earning nothing due to nothing is offering to the rest of the members in the market.

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 marketbased approach is successful with respect to the optimum assignment.

With respect to the market rules at the moment to offer 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 offered 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 different 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 file-sharing application and the rental markets when rights management restrictions limit the number of copies. [7] for example covers P2P application which use token based approach in order to interchange goods.

Future work

Future work planned includes:

• Adopting different policies at the moment of offering 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 offer/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 efficient as the number of participants increases? Are such markets more efficient as the variety of goods increases?

• Many interactions, both economic and social ( [10], [12]), involve network relationships. Most importantly, in many interactions the specifics of the network structure are important in determining the outcome. A future area of research is to verify with respect to the topology what the impact of changes in topology would have on outcomes.