=Paper=
{{Paper
|id=Vol-223/paper-50
|storemode=property
|title=Self-Organization Amongst Non-Altruistic Agents for Distribution of Goods: Comparing Bartering and Currency Based Exchange
|pdfUrl=https://ceur-ws.org/Vol-223/25.pdf
|volume=Vol-223
|authors=David Cabanillas (Technical University of Catalonia),Steven Willmott (Technical University of Catalonia)
|dblpUrl=https://dblp.org/rec/conf/eumas/CabanillasW06
}}
==Self-Organization Amongst Non-Altruistic Agents for Distribution of Goods: Comparing Bartering and Currency Based Exchange==
https://ceur-ws.org/Vol-223/25.pdf
Self–Organization Amongst Non–Altruistic Agents for Distribution of
Goods: Comparing Bartering and Currency Based Exchange
David Cabanillas Steven Willmott
Technical University of Catalonia, Software department,
Campus Nord, Omega building
Jordi Girona Salgado, 1-3, Barcelona (08034), Spain
{dconrado, steve}@lsi.upc.edu
Abstract
The distribution of a set of goods (such as finite allowed numbers of electronic goods, phys-
ical objects or fixed 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 in-
formation 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 (specifically 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 affected by the heterogeneity of agent preferences for goods in the population. The
results also confirm that bartering is clearly outperformed in most settings by more flexible
currency based approaches.
1 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 so-
lution. 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 = {a0 , a1 , . . . , a|N | }
and F = {f0 , f1 , . . . , f|M | } 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 |A| x |F | is to find the particular total assignment mapping Γ : A ⇒ F such that
P|N |
for ai , aj ∈ A, i 6= j implies Γ(ai ) 6= Γ(aj ), and the total satisfaction Stot = i=0 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 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 in-
dividual 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 frame-
work. 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 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, 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 file–
swap. 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
3 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.
1 More information about the model is available in [3].
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 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 offering (f ilex , 2.500). It will implies that agentA will offer f ile1 , f ile2 , f ile3 and f ile4 .
• 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 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
offering (f ilex , 2.500). It will implies that agentA will offer 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 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 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 offering (f ilex , 2.500). It will implies that
agentA will offer 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 benefit 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 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 indepen-
dently – that is, each agent may have different preferences. Example: agentA and agentB are
interested in f ile1 and they worth the file in 2.000.
Heterogeneous preferences Homogeneous preferences
Monetary – Least restrictive Scenario 1.1 a Scenario 1.1 b
Monetary – Medium restrictive Scenario 1.2 a Scenario 1.2 b
Monetary – Most restrictive Scenario 1.3 a Scenario 1.3 b
Bartering Scenario 2 a Scenario 2 b
Table 1: Scenarios analyzed
10000
8000
GLOBAL LEVEL OF BENEFIT
6000
4000
2000 Optimal assignment
Simulation 1.1 a
Simulation 1.2 a
Simulation 1.3 a
Simulation 2 a
0
5 10 15 20 25 30 35 40 45 50
TICKS (TIME)
Figure 1: Global satisfaction in scenarios with heterogeneous preferences
• 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 file has a value of 3.000.
The table, scenarios analyzed shows the different scenarios studied.
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
10000
8000
GLOBAL LEVEL OF BENEFIT
6000
4000
2000 Optimal assignment
Simulation 1.1 b
Simulation 1.2 b
Simulation 1.3 b
Simulation 2 b
0
5 10 15 20 25 30 35 40 45 50
TICKS (TIME)
Figure 2: Global satisfaction in scenarios with homogeneous preferences
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 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 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.
4 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 fb ) > benefit (B of fa ) and benefit (B of
fa ) > benefit (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 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.
4.1 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 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 some-
thing the other party demands. 2
• Another problem in this type of market is related to the concept of 1 to 1 trades. Supposing
a configuration 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 finally
agentC has the goods a3 , b1 , b2 and it prefers goods c1 , c2 , c3 (in this order). The first trade
2 http://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 offer 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 offer
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 certifies that the bartering system only
works 1 to 1.
4.2 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 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 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.
5 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.
6 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 market–
based 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 com-
pared. The classical one, what obtains a optimal result but has inherent limitations such as cen-
tralization 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.
7 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.
References
[1] R. E. Burkard, Y. He, and H. Kellerer. A linear compound algorithm for uniform machine
scheduling. Computing, 61(1):1–9, 1998.
[2] R. Buyya, D. Abramson, J. Giddy, and H. Stockinger. Economic models for resource manage-
ment and scheduling in grid computing, 2002.
[3] David Cabanillas and Steven Willmott. Studying viable free markets in peer–to–peer file
exchange applications without altruistic agents. Technical Report LSI-06-12-R, Department
of Computer Science, University of Catalonia, March 2006.
[4] Yann Chevaleyre, Paul E. Dunne, Ulle Endriss, Jérôme Lang, Michel Lemaı̂tre, Nicolas
Maudet, Julian Padget, Steve Phelps, Juan A. Rodrı́guez-Aguilar, and Paulo Sousa. Issues in
multiagent resource allocation. Informatica, 30(1):3–31, 2006.
[5] George Christodoulou and Elias Koutsoupias. The price of anarchy of finite congestion games.
In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pages
67–73, New York, NY, USA, 2005. ACM Press.
[6] W. Cook and A. Rohe. Computing minimum-weight perfect matchings. INFORMS Journal
on Computing, 11:138–148, 1999.
[7] Vijay Kumar David Abraham, Ning Chen and Vahab Mirrokni. Assignment problems in rental
markets, December 2006.
[8] Ulle Endriss and Nicolas Maudet. Multiagent resource allocation and welfare engineering.
AgentLink News 18, pages 3–4, August 2005.
[9] D. Ferguson, C. Nikolaou, J. Sairamesh, and Y. Yemini. Economic models for allocating
resources in computer systems, 1996.
[10] S. Kakade, M. Kearns, L. Ortiz, R. Pemantle, and S. Suri. Economic properties of social
networks, 2005.
[11] Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. Lecture Notes in Com-
puter Science, 1563:404–413, 1999.
[12] Rachel E. Kranton and Deborah F. Minehart. A theory of buyer-seller net-
works. American Economic Review, 91(3):485–508, June 2001. available at
http://ideas.repec.org/a/aea/aecrev/v91y2001i3p485-508.html.
[13] H.W Kuhn. The hungarian method for the assignment problem. Naval Research Logistics
Quarterly, 2:83–97, 1955.
[14] Sepandar Kamvar Mario. Incentives for combatting freeriding on p2p networks., 2003.
[15] James Munkres. Algorithms for the assignment and transportation problems. 5(1):32–38,
March 1957.
[16] Noam Nisan. Algorithms for selfish agents. Lecture Notes in Computer Science, 1563:1–15,
1999.
[17] Kiam Tian Seow and Khee Yin How. Collaborative assignment: A multiagent negotiation
approach using bdi concepts. In AAMAS ’02: Proceedings of the first international joint
conference on Autonomous agents and multiagent systems, pages 256–263, New York, NY,
USA, 2002. ACM Press.
[18] Gilad Zlotkin and Jeffrey S. Rosenschein. Cooperation and conflict resolution via negotiation
among autonomous agents in noncooperative domains. IEEE Transactions on Systems, Man,
and Cybernetics, 21(6):1317–1324, December 1991.
[19] Gilad Zlotkin and Jeffrey S. Rosenschein. A domain theory for task oriented negotiation. In
Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, pages
416–422, Chambery, France, August 1993.