Customer Coalitions in Electronic Markets Maksim Tsvetovat Katia Sycara May 18, 2000 Abstract 1 In the last few years, the electronic marketplace has witnessed an ex- ponential growth in worth and size, and projections are for this trend to intensify in coming years. Yet, the tools available to market players are very limited, thus imposing restrictions on their ability to exploit mar- ket opportunities. While the Internet o ers great possiblities for creation of spontaneous communities, this potential has not been explored as a means for creating economies of scale among similar-minded customers. In this paper, we report on coalition formation as a means to formation of groups of customers coming together to procure goods at a volume discount (\buying clubs") and economic incentives for creation of such groups. We also present a exible test-bed system that is used to imple- ment and test coalition formation and multi-lateral negotiation protocols, and show use of the test-bed system as a tool for implementation of a real-world \buying club". 1 Introduction A coalition is a set of self-interested agents that agree to cooperate to execute a task or achieve a goal. Such coalitios were thoroughly investigated within game theory [9, 10, 14, 11]. There, issues of solution stability, fairness and pay- o disbursements were discussed and analyzed. The formal analysis provided there can be used to compute multi-agent coalitions, however only in a central- ized manner and with exponential complexity. DAI researchers [11, 14] have adopted some of the game-theoretical concepts and upon them developed coali- tion formation algorithms, to be used by agents within a multi-agent system. These algorithms concentrate on distribution of computations, complexity re- duction, eÆcient task allocation and communication issues. Nevertheless, some of the underlying assumptions of the coalition formation algorithms, which are essential for their implementation, do not hold in real-world multi-agent sys- tems. 1 This material is based on work supported in part by MURI contract N00014-96-1222 and CoABS Darpa contract F30602-98-2-0138 and NSF grants IRI-9612131 and IRI-9712607 1 In this paper, we report on coalition formation as a means to achievement of economies of scale among customer agents. In particular, we concentrate on formation of \buying clubs" - groups of customers coming together to procure goods at a volume discount. The paper is organised as follows: We begin by presenting the economic models that show how both suppliers and customers can bene t from advent of such buying clubs (i.e. incentives to create buying clubs), which are critical in any real-world system. In section 5, we discuss the issues that need to be addressed in creation of a coalition protocol, and provide and critique several distinct coalition models. We proceed in section 6 to describe test-bed that can be used to test di erent coalition formation protocols and coalition models, as well as a real-world system that was implemented using the test-bed. We conclude by describing future experiments that will be conducted using the test-bed system. 2 Prior Work Auctions are the predominant electronic commerce models on the Internet but they are not the most suited for the wholesale marketplace. Research centers like MIT Media Labs have been trying to address the issue of cooperative market models (Tete-a-Tete system [6]) but there is still a lot of research that needs to be done. Currently there are no implementations of a wholesale agent market where agents collaborate and do many-to-many multi-attribute negotiations on behalf of buyers and sellers. However, research is being done on some issues of this market. Some systems, such as MAGNET ([3]) attempt to address aggregarion of multiple suppliers in order to form a supply chain and complete a task. Other examples of electronic markets are Fast Parts Trading and Kasbah [2]. Fast Parts Trading Exchange is a product that allows wholesale sellers to meet and exchange o ers. The main functionality of Fast Parts Trading is to act as an electronic exchange and it does not incorporate automated negotiation nor does allow collaboration between buyers. Kasbah is an agent marketplace that allows agents to negotiate the price of goods on behalf of consumers. There are several di erences between the proposed framework and Kasbah. The rst is that Kasbah only allows negotiation based on price while our framework implements multi-attribute preferences. Also, Kasbah does not allow buyers to form coalitions. Most important, Kasbah uses only one speci c protocol and strategy for negotiation, while our work provides a exible test-bed where di erent strategies can be experimented with. A lot of research has been devoted to studying game-theoretic properties of coalitions[9, 11]. The main topics of this work has been coalition stability, fairness, payo distribution, methods for eÆcient formation of coalitions, as well as methods for manipulating results of coalition processes. However, most of this work has concentrated on theoretical aspects of coalitions, and thus there is currently no work or implemented system in the context of buyer coalition formation. However, recently there has also been some commercial work in the area. 2 Accompany.com (www.accompany.com, [1]) allows customers to join together during a \buying cycle", and obtain a volume discount dependent on the size of the group. However, the company functions as a retailer (i.e. is responsible for breaking up volume shipments and shipping retail-sized packages to individual customers) - which signi cantly a ects the costs and bene ts of buyer coalitions. Also, Accompany.com functions by pre-negotiating volume discounts with a handful of suppliers, thus leaving the user out of the bidding process. 3 Incentives for Customer Coalitions When one studies an electronic commerce system, especially one dependent on a novel approach such as buyer coalitions, one has to consider the incentives involved in this system. In short - what would be a compelling reason for a person to move to a new commerce paradigm. Such incentives are usually monetary - reduction of cost, or increased pro t, although they can include less tangible bene ts such as reduction of risk (or allowing someone else to assume the risk), or increase in market size or market share. In this section, we will outline the economic incentives that could compel both suppliers and customers to join an electronic commerce system based on buyer coalitions. 3.1 Supplier Incentive to Sell Wholesale Let us assume that suppliers are (a) rational and (b) self-interested, i.e. they will attempt to sell their goods at maximum pro t. As new opportunities present themselves, seller agents will conduct some sort of cost-bene t analisys and take advantage of all opportunities to raise their pro ts. As a simplifying assumption, let us also say that the manufacuring cost of one item is constant and, above some threshold, independent of the amount of units sold. This is true if the supplier's production facility is working at or near capacity. Now, let us suppose that an agent is selling its goods retail. Let:  U item be the utility (pro t) of selling one item retail.  P item be the sale price of the item (or reservation price in an iterative negotiation)  C retail be the cost of manufacturing one item. 3 Lot Size Supplier Incentive for Wholesale N_retail N_wholesale Figure 1: Supplier's Incentive to Sell Wholesale The utility an agent receives from selling one item can be expressed as U item = P item n = P item  n wholesale (i.e to one buyer instead of many) can be expressed as U wholesale n = P item  n ove expressions, we then infer that the agent has insentive to sell wholesale if Cwholesale Since marketing to one buyer is usually less expensive then market- ing to multiple buyers, the incentive to sell wholesale will usually be present. However, wholesale marketing to one customer will be more expensive then retail marketing to one customer, due to more protracted negotiation and other factors. Up to some lot size N retail , the supplier has a negative incentive for selling at a wholesale price, as marketing costs will be nearly identical to retail and lowering the price to wholesale level is not justi ed (see gure 1) As the size of the lot increases past that point, selling wholesale lots becomes bene cial for supplier. 4 Quantity, n Utility Figure 2: Customer Total Utility This pattern can repeat as the lot size increases, resulting in multiple price breakpoints. For example, one could purchase an item at retail quantities (by pack), by case (12 packs), by box (50 cases), pallet of boxes or truck-load. All of these packaging options have di erent costs for the supplier, and are likely to result in di erent wholesale prices. 3.2 Customer Incentive to Buy Wholesale The customer utility curve (shown on gure 2) is commonly known in the eld of economics and illustrates the law of decreasing returns. It illustrates the fact that utility of each unit acquired is smaller than that of the previous unit. However, a more realistic representation of the utility curve ( g. 3) shows that there is range of acceptable quanities of the good, after which the utility of each additional unit drops sharply. This is due to the additional costs associated with storage or management of surpluses. Customer Utility U = Benef it y Range (MUR) as MUR = (nmin ; nmax ) , a range in which the utility is high while management costs remain low. If the supplier's optimal size of wholesale lot nwholesale 2 MUR, then the customer can purchase a wholesale lot. HOWEVER: If the price of purchasing goods in larger lots remains the same as retail price, the customer has no incentive to buy such lots and might just as well buy through retail channels at a higher marketing/packaging cost to supplier, thus lowering supplier's per- unit pro t margin. 5 Utility Maximum Utility Region (MUR) Management Cost Cumulative Utility Figure 3: Customer Per-Unit Utility and Costs Thus, supplier has an incentive to sell wholesale lots, it must give the cus- tomer an incentive to buy wholesale - which is commonly done by lowering per-unit price at when the requested lot size is large enough. These price decreases are usually represented by a step function such as the one on gure 4. ASSUMPTION: Customer's utility of an item is higher if the price of the item is lower while all other factors remain constant, or U customer = (P ) Thus, if the supplier lowers its price for larger lots, the customer has an incentive to buy wholesale. 4 Coalitions and Wholesale Purchasing In the real world, a single customer rarely wants to buy large enough quantities of goods to justify wholesale purchasing, or Nwholesale = 2 MUR In order to lower the purchase price (and, therefore, increase utility), self- interested customer agents can join in a coalition such that Nwholesale 2 MUR coalition = X MUR i where MUR i is the MUR of each member of the coalition. This would enable the coalition to buy a wholesale lot from the supplier, break it into sub-lots and distribute them to its members, thus raising the utility of each individual member. 6 Retail Pricing Wholesale Pricing Lot Size Incentive Wholesale Lot Size Figure 4: Wholesale and Retail Pricing However, the formation and administration of coalitions, as well as distribu- tion of sub-lots has its costs, represented as C coalition . C coalition consists of number of di erent costs, closely related to the real- world situation where the coalition is formed. In particular, such costs include the cost of administering coalition membership, cost of collecting payments from individual members, and the cost of distributing items to the members when the transaction is complete. In some cases (such as distributing copies of soft- ware) some of the costs can be very small, and in other cases may rise to be prohibitively large. A coalition is only viable if the increase in group's total utility from wholesale purchases is greater than the cost of creating and running a coalition, or U > C coalition 5 Coalition Models It is possible to construct a number of coalition models and protocols, all of which would have di erent properties and requirements. In general, all coalition models include several stages:  Negotiation: The coalition leader or another representative of the coali- tion negotiates with one or more suppliers to provide the good or service. The protocol must address issues such as the choice of suppliers, and eval- uation of competetive bids. 7  Coalition Formation: The coalition leader solicits new members to join his coalition. It is important to note that the coalition must have some admission constraints (such as geographical proximity of the members or their ability to pay for the goods.).  Leader Election/Voting: The members elect a coalition leader or cast direct votes for or against certain bids. Not all coalition formation proto- cols make use of this stage.  Payment Collection: The coalition leader (or elected treasurer, as de- ned by the protocol) collects the payments from coalition members and is responsible for conveying the full amount to the supplier  Execution/Distribution stage: As a transaction is executed and the purchased goods arrive, they must be distributed to the members of the coalition. In design of coalition protocols, the following issues have to be taken into account:  Coalition Stability: Are members of a coalition allowed to leave? If yes, what would be their incentive for leaving? Would a member leaving a coalition incur any costs or penalties - or would these penalties be incurred by the coalition as a whole or the supplier?  Distribution of Gain: How are the gains from the di erence between retail and wholesale prices of a good distributed to the members of the coalition?  Distribution of Costs and Utility: Who bears the cost of goods dis- tribution and how to arrange the logistics of such? If there is a reward for creating a larger coalition, how is this reward distributed?  Distribution of Risk: Who bears nancial risks as the transaction is executed and how large are they? Are there any uncertainties and which parties experience them? What are the strategies for minimizing such risks? Risks can be classi ed into several distinct types: { Risk of Transaction Failure is the probable cost of recovery from a transaction failure such as decommitment of the supplier of choice. { Risk of Coalition Failure is the probable cost of recovery from decommitment of one or more members of the coalition. { Price Uncertainty is a measure of price uctuation due to change in coalition size, a ecting both the coalition and supplier's bottom lines. 8 Ultimately, all risks are interconnected. For example, a decommitment by a supplier results in renegotiation of the deal, which in turn results in a price uncertainty of the members of the coalition and may lead to decommitment of coalition members and ultimately the coalition failure. Probability of such a disastrous chain reaction is largely determined by the distribution of reservation prices among the members of the coalition, number of suppliers in the marketplace and their willingness to bid or renegotiate contracts.  Trust and Certi cation: There are three levels of trust required for the coalition leader - trust in the negotiation stage, payment collection and in the distribution stage. Is such trust critical in the protocol? Is it possible to design a protocol that would not require such trust or minimize the number of stages where trust is required? How can the coalition deal with a breach of trust? In this section, we will discuss a number of protocols for forming customer coalitions and address some of the issues raised above. Most coalition protocols can be divided into two classes (pre-negotiation and post-negotiation), based on the order in which negotiation and coalition formation happen. In pre-negotiated coalitions, the coalition leader negotiates a deal with one or more suppliers using an estimated coalition size or order volume, and then advertises the creation of the coalition and waits for other members to join. In another scenario, the group is formed rst, based on some admission criteria. Then, a group leader negotiates with suppliers, and o ers the resulting deal to the group. One of the chief di erences between the two scenarios is in the distribution of risk between the parties of the negotiation. In a pre-negotiation protocol, the coalition leader must estimate the group size in order to be able to sign a deal with the supplier. If such estimate is wrong, the coalition leader must absorb the loss or through some mechanism make the coalition members pay a higher price. In the post-negotiated mechanism, the group must be able to trust its leader to negotiate on its behalf. Unless the group is formed by a number of people who know each other through other channels (i.e. a group of students in a class), there would have to be an explicit leader selection/veri cation mechanism, or a mechanism for collective negotiation. 5.1 Post-Negotiation A simple post-negotiation protocol involves the following parties: the coalition leader (L), a set of suppliers S = fs 1 ; s 2 ; :::; s n g, a set of potential coalition members M = fm 1 ; m 2 ; :::m n g, and a coalition advertising server CS. 1. L ! CS: Advertise creation of a coalition with speci ed parameters (such as item to be procured, location of the leader, etc.). The coalition is open 9 to members for a limited period of time or until a speci ed group size is reached. 2. CS ! M : The coalition server supplies the coalition advertisement to potential coalition members 3. Each m i 2 M considers whether to join the coalition m i ! L: A \Join the Coalition" message 4. At the expiration of the coalition deadline/size limit, the leader enters the negotiation with the suppliers s i 2 S using its private protocol/strategy and decides on a deal in the best interest of the group. 5. Coalition Leader L collects money from group members, and arranges for the shipping and distribution of goods. This protocol requires an immense amount of trust in the coalition leader. In fact, the protocol is wide-open to representatives of suppliers (\shills") starting coalitions that would act in the behalf of a given supplier rather than groups of customers. If there is no implicit trust in the coalition leader that can be inferred from other sources (such as previous relationships between coalition leader and its members), the protocol must feature mechanisms that help the coalition mem- bers establish this trust or conduct transactions without having to trust the leader. Trust in the coalition leader can be established in a number of ways. Leaders can be elected from the general membership of the group before the negotiation starts. The group could also appoint a trusted third party to conduct negotia- tions on its behalf. Also, the coalition leader could be compelled to open every step of the negotiation to the scrutiny of group members. It is also possible to conduct negotiation by having the members of the group vote on bids. In this mechanism, the result of the negotiation would be acceptable to the majority of members of the coalition, and it would take a large number of \shills" for a supplier to sway the opinion of the coalition. The approaches that utilize voting may not be practical due to the long time it would take to conduct a multi-round negotiation and the amount of communication that is necessary to decide on the outcome of a negotiation. However, they can be very useful if the bid is awarded through a single-round auction. Also, it has been shown that voting systems can be manipulated in a number of ways [5, 9] and thus have to be approached with some caution. 5.2 Pre-Negotiation The simplest pre-negotiation protocol is de ned as following: 1. The coalition leader L conducts a negotiation session with a set of suppliersS, using his private parameters such as reservation prices, bid evaluation and concession strategies. 10 Figure 5: A Step-function Bid from a Supplier 2. L ! CS: After the negotiation stage is complete, the coalition leader opens the coalition to new members, disclosing the details of the deal struck in the negotiation stage. 3. CS ! M : The coalition server supplies the coalition advertisement to potential coalition members 4. Each m i 2 M considers whether to join the coalition m i ! L: A \Join the Coalition" message 5. After a certain period of time elapses, or the coalition gains some mini- mum number of members, the coalition leader closes the coalition to new members and executes the transaction. In this protocol, the coalition leader carries a number of risks. In order to give volume discounts, suppliers must have some idea of the number of members expected to join the coalition (or, alternatively, expected quantity of goods to be sold). While this number can be estimated, the coalition leader carries a risk of not being able to nd enough members to join the group. In this case, the deal must be re-negotiated, resulting in a higher price and, possibly, more members leaving the coalition - a vicious cycle that can, in the worst case, completely destroy the coalition. Another risk factor is inherent in the fact that the coalition leader uses a private reservation price and negotiation strategy - which may be very di erent from the reservation price that the majority of the target population has. Since the details of the discounts are revealed before people join the coalition, the coalition members do not have to trust the coalition leader in the negotiation stage. However, the trust in the payment collection and goods distribution stages is still required. The main problem with this protocol is the risk that the coalition leader has to take while estimating the group size. However, this protocol could be altered to remedy this problem in the following way: In the negotiation stage, the coalition leader presents not his estimated group size, but a range of sizes. In response the supplier bids with a step function 11 P rice = F bid (quantity) (see gure 5). This function can later be revealed to the coalition members if this supplier is awarded a bid. The bid evaluation strategies for operating on step functions are very similar to ones operating on singular bids. When step function bidding is used, most risk in the transaction is shifted onto the coalition members due to the price uncertainty. For example, the poten- tial buyer can have a reservation price that is between the maximum and mini- mum prices of the step function (Pmax coalition  P reservation  Pmin coalition ). In this case the decision on whether to join the coalition depends on the buyer's estimate of the probability that the nal price will be lower than his reservation price, which essentially is an estimate of the nal size of the group. As a result, in this case a dominant strategy for a buyer would be to wait until the coalition is almost closed for new members - which could result in a more accurate esti- mate of the nal coalition size. However, if many buyers use this strategy, the overall behavior of the system may become non-deterministic. 5.3 Distribution of Costs and Utility The coalition leader can operate on several di erent principles:  Non-Pro t: C coalition is distributed either equally among all participants or on the sub-lot size basis. These coalitions can be formed spontaneously for negotiating one partic- ular deal or be stable \buyer's clubs" that exist over time.  For-Pro t: { Consolidator: Pre-negotiates a deal with the supplier given an es- timated group size, and then re-sells the items individually, keeping enough of the savings (P ) to cover the C coalition and make a pro t. Customer's savings P i = P coalition n i n l ot (or customer's share of the coalition costs) This is the business model used by airline consolidators or concert ticket distributors. They can usually obtain fairly accurate estimates of demand given the statistical data (i.e. popularity of certain air routes during a certain season), and absorb any losses resulting from not being able to sell the predicted number of seats. Similar approach has been used by a number of group-buy commer- cial sites, in particular Mercata [8] and Accompany.com [1]. These sites play both the role of a coalition facilitator (a service that helps buyers form coalitions) and a coalition leader (responsible for nego- tiation of volume deals and distribution of product). { Rebater: Sells the items at retail price minus a small rebate, and keeps the rest of the savings. Additional pro ts can be gained by delaying rebates, thus improving the cash ow of the company. 12 Figure 6: Screenshot of the WWW Interface 6 Customer Coalitions for Volume Discounts - an Implementation In order to verify the abovementioned hypotheses, we have designed a exible test-bed that can be used to evaluate di erent coalition creation protocols, as well as determine the real-world feasibility of automated agent-based coalition formation and negotiation protocols. As an initial problem domain, we chose collective book purchasing. Often, in the university setting, one sees large number of students that are enrolled in the same class purchasing large quantities of the same book. This seemed to be a natural application of a coalition-based commerce for a number of reasons. Firstly, the group of students enrolled in the same course has the same or very similar requirements for the book, so the issue of matching customers to correct groups is greatly simpli ed. Secondly, the distribution and payment collection are much easier given the fact that the coalition members have to physically gather in a classroom several times a week. Thirdly, it would provide us with a large base of potential users once the system is ready for real-world tests. 13 Coalition Leader Coalition Leader Coalition Leader Auctioneer session Customers Suppliers session session Coalition Server Figure 7: System Architecture 6.1 Coalition Protocol The system we have implemented uses a pre-negotiation protocol with step- function bids, as described in section 5.2. The coalition leader speci es the product to be bought through a search in the books-in-print database, and submits a request for bids to a set of supplier agents. Auction Session Auction Session Official Clock Protocol Layer Auction Session to Suppliers from Coalition Leader Auctioneer Agent Figure 8: Auctioneer Agent The auctioneer agent ( gure 8) inplements and enforces a simple rst-price sealed bid auction protocol [12] for negotiation between suppliers and the coali- tion leader. We chose this protocol for its simplicity and ease of comprehension for rst-time users. We have already de ned more advanced additional proto- cols (such as open-bid rst price auction, Vickrey auction and a simple leveled commitment protocol [13, 12]) and will incorporate them into the system to experimentally study their comparative performance. 14 Catalog Database KQML messages Supplier Agent Protocol Layer Strategy Layer Implementation Auction Session Auction Session Auction Session Protocol Definition Strategy Definition Figure 9: Supplier Agent Supplier agents ( gure 9) respond to the request for bid by searching in their catalog databases, and applying a pricing policy to each item. The pricing policy can be speci ed through con guration les or a simple interface, thus making the agents easily con gurable. Applying the pricing policy to an item generates a price-vs-quantity step function as described in section 5.2, which is then included in the bid. Before computing the bid price, supplier agent queries an information agent, which acts as an electronic catalog. In order to run our system using real-world data, each of the information agents queries a well-known Internet book retailer (Amazon.com, Borders and Barnes & Noble). In our system we used Retsina information agents ( [16, 15]), which can be easily adapted to serving data from any website. The information retrieved from the agent is then cached by the supplier agent, which greatly speeds up future access. All bids are submitted to the auctioneer agent ( gure 8), which waits for the auction period to expire and then releases the bids to the coalition leader. coalition leader can then apply its private bid evaluation strategy to determine the winner of the auction. After the supplier has been determined, the coalition leader noti es the winning supplier of a tentative accept, and the coalition is opened for new members for a certain period of time (which is pre-set during the initialisation stage). During this time, the coalition is advertised by the coalition server and people are allowed to join it. The nal price of the item is determined after the coalition membership is closed. At this time, a message con rming the quantity and delivery date is sent to the supplier, who responds with a con rmation and executes the transaction. 6.2 Testbed Architecture The testbed system (see gure 7) consists of a coalition server, an auctioneer agent, set of supplier agents, and a web-based interface ( gure 6) for end users. 15 The coalition server is essentially a database that allows coalition leaders to advertise their coalitions to potential members, and allows customers to search for coalitions given their criteria and join a coalition. Both customers and coalition leaders can be either human using the web interface or agents commu- nicating to the server in KQML [4]. 6.3 Implementation of Agents All agents in the system are implemented using a multi-layer approach that separates the de nition of a protocol from de nition of the negotiation strategy of an agent and its implementation. This is accomplished through use of a protocol de nition language to de ne the high-level interactions of the agents, while a built-in Scheme interpreter is used to de ne the agent's strategy and script lower-level behaviors. The protocol de nition language is based on the I/O Automata formalism commonly used for de nition and analisys of cryptographic and communication protocol [7]. However, it also includes a number of enhancements designed speci cally for de nition of negotiation protocols. Input/Output Automata model [7] is a very general mechanism, suitable for describing almost any type of asynchronous concurrent system. The model itself provides very little structure, which allows it to be used for modeling many di erent types of distributed systems. Simple I/O Automata can be combined to form larger automata that represent concurrent systems. An I/O Automaton is a model of a distributed system component that in- teracts with other system components. It is a simple state machine in which state transitions are associated with actions. The actions are classi ed as input, output, or internal. The inputs and outputs are used to communicate to other entities in the automaton's environment. An example of a simple I/O Automaton is a process in an asynchronous distributed system. The automaton is initialized by an internal start input, conducts a set of speech acts with the outside world using external send output and receive input, and returns a result via its internal return output when it terminates. Formally, an I/O Automaton A can be speci ed by its interfaces, a set of states and transitions and a set of actions associated with particular transitions:  signatureS(A) = input(A); output(A); internal(A)  external interface ext(A) = input(A); output(A)  states(A), a set of states  start(A) 2 states(A), a non-empty set of states known as start states  trans(A), a state-transition relation such that for every state s and for every input action , there is a transition (s; ; s 0 ) 2 trans(A) 16  actions(A), a set of actions that the automaton can execute. This includes send and receive actions, as well as all internal actions ( gure 10) P start return send receive external internal Figure 10: A simple I/O Automaton An execution of an I/O Automaton is either a nite sequence, s 0 ;  1 ; s 1 ;  2 ; :::;  f ; s f , or an in nite sequence s 0 ;  1 ; s 1 ;  2 ; :::;  f ; s f ; :::, of alternating states and ac- tions of A such that (s k ;  k + 1; s k + 1) 2 trans(A) for every k  0. The composition operation allows and automaton representing a complex system to be constructed by composing automata representing individual system components. A composition of I/O Automata C is de ned as having a signature S(C) =  i2I S i = finput(C); output(C); internal(C)g input(S) = [ i2I input(S i ); output(S) = [ i2I output(S i ); internal(S) = ([ i2I internal(S i ) Language) Language was designed based on the I/O Automata formalism presented above. It encapsulates de nition of an I/O Au- tomaton or a composition of I/O Automata into a set of productions that can be later shared over a network. The syntax of PiPL is very similar to LISP, making PiPL les easy to parse with existing parsers. The protocol de nition in PiPL consists of two main parts, the agent society de nition and a composition of I/O Automata representing agents in this society. The agent society de nition breaks down an agent group into a set of roles. A role is usually de ned by a set of tasks an agent is capable of performing or is allowed to perform in a given interaction. Thus, an agent playing a role of auctioneer in an e-commerce scenario is capable of administering an auction and is (presumably) trusted to do so. An admission criteria could be speci ed to nd which agents can play a given role. Also, an agent can play more than one role in an interaction, if it can satisfy admission criteria for all roles. Therefore, admission criteria have to be designed to check for conicts of interest (i.e. an auctioneer cannot also be a bidder) 17 Each role de nition also speci es the number of agents allowed to play this role in a given interaction (for example, there can be only one auctioneer, but there could be many bidders), and a start state for the I/O Automaton for this role (see gure 11). (role :cardinality :admission_cond :start ) Figure 11: De nition of a Role After roles of agents participating in the interaction are de ned, the speci- cation de nes I/O Automata for each of the role. Each automaton A is a set of states states(A). A state of A s i (A) 2 states(A) = f; T = ftrans(A; s i )gg, where  is an implemented action of the agent, and T is a set of transitions from a given state to the next state ( gure 12). Action  is executed when an agent enters the state from any other state. (state :roles :action :final ) Figure 12: De nition of a state A transition ( gure 13) is de ned as T = f cond ; ; s 0 g where  cond is a condition that has to be satis ed for a transition to happen,  is an implemented action of the agent and s 0 is the state that the I/O Automaton should transition to. (transition :roles :cond :action :goto ) Figure 13: De nition of a Transition As a result, the agents in the system are not limited to use of hard-coded protocols and it is very easy to implement and add new protocols to the system. 18 7 Conclusions and Future Work In this paper, we have presented the economic incentives that drive coalition formation among self-interested agents, concentrating on formation of buyer coalitions and obtaining volume discounts. We have also discussed variety of coalition models and their properties, and presented an implemented system using one of such models. The system is currently available on the Web and will be used for practical evaluation of coalition models and collection of real- world data. A number of experiments using the coalition formation testbed are planned in the near future. Firstly, we will use a set of distinct coalition formation and negotiation protocols to conduct automated tests of performance of such proto- cols. Secondly, we would like to conduct a test of the real-world capabilities of the system by inviting groups of students to run through the system in a struc- tured experiment. Finally, we plan to extend the formalisms used in creation of the protocol de nition language to allow protocol de nitions to be shared by multiple agents in the marketplace, thus eliminating many compatibility prob- lems. References [1] Accompany.com. Accompany, inc. to revolutionize commerce: Buyers come together for best value, 1999. [2] Anthony Chavez and Pattie Maes. Kasbah: An agent marketplace for buying and selling goods. In Proc. of the First International Conference on the Practical Application of Intelligent Agents and Multi-Agent Technology, London, UK, April 1996. [3] J. Collins, M. Tsvetovat, B. Mobasher, and M. Gini. Magnet: A multi- agent contracting system for plan execution. In Proceedings of Workshop on Arti cial Intelligence and Manufacturing: State of the Art and State of Practice, pages pp 63{68. AAAI Press, August 1998. [4] Tim Finin, Yannis Labrou, and James May eld. Kqml as an agent commu- nication language. In Je Bradshaw, editor, Software Agents. MIT Press, 1997. [5] A. Gibbard. Manipulation of voting schemes: General result. Econometrica, 41(4):587{602, 1973. [6] R. Guttman and P. Maes. Cooperative vs. competitive multi-agent negoti- ations in retail electronic commerce. Berlin:Springer-Verlag, 1998. [7] Nancy A. Lynch. Distributed Algorithms, chapter pages 200-231. Morgan Kaufman, 1996. [8] Mercata.com, 1999. 19 [9] B. Peleg. Game Theoretic Analysis of Voting in Commities. Cambridge University Press, 1984. [10] Je rey S. Rosenschein and Gilad Zlotkin. Rules of Encounter. MIT Press, Cambridge, MA, 1994. [11] T. Sandholm, K. Larson, M. Andersson, O. Shehory, and F. Tohme. Coali- tion structure generation with worst case guarantees. Arti cial Intelligence Journal, 1999. [12] Tuomas W. Sandholm. Negotiation Among Self-Interested Computationally Limited Agents. PhD thesis, University of Massachusetts, 1996. [13] Tuomas W. Sandholm and Victor Lesser. Issues in automated negotia- tion and electronic commerce: Extending the contract net framework. In Proceedings of 1st International Conference on Multiagent Systems, pages 328{335, 1995. [14] O. Shehory and K. Sycara. Multi-agent coordination through coalition for- mation. In Proceedings of the Agent Theories, Languages and Methodologies (ATAL97), 1997. [15] K. Sycara and K. Decker. Designing behaviors for information agents. In Proceedings of the First International Conference on Autonomous Agents, Feb 1997. [16] K. Sycara, K. Decker, and M. Williamson. Intelligent adaptive information agents. In Working Notes of the AAAI-96 Workshop on Intelligent Adaptive Agents, Aug 1996. 20