Dynamics of Coalition Formation in Combinatorial Trading

1 Introduction

The pervasive connectivity of the Internet and the powerful architecture of World Wide Web are changing many market conventions. Tremendous opportunities for conducting business on the Internet are emerging. Intelligent agents will play a crucial role in electronic commerce where dynamic and heterogeneous interactions between thousands of or­ ganizations and millions of individuals are involved. So far, we have already witnessed the involvements of e-commerce agents in traditional business settings. Furthermore, this involvement is re-shaping the way in which business is con­ ducted in areas such as comparison shopping, dynamic pric­ ing, negotiation, auction, and brokerages, to name a few. The automation brought by e-commerce agents will dra­ matically reduce certain types of frictional costs and time incurred in the exchange of commodities.

In e-commerce, the virtual distance separating produc­ ers, wholesalers, distributors, retailers, and consumers has collapsed to near zero. All of the parties involved are faced with rich choices, and it is natural for them to util­ ize situations to their best advantage. As the population of e-commerce agents increases, automated negotiations among them on behalf of their parties will be prevalent. One of the areas in which agent negotiations will be heavily involved is combinatorial markets, where combi­ nations of goods and services are being traded and effi­ ciently allocated. For example, a trading agent can be constructed to perform real-time procurement of bundles of complementary goods and services on multiple simul­ taneous Internet auctions and exchanges. Alternatively, a travel service agent can be constructed to provide combi­ nations of hotel and flight arrangements to potential cus­ tomers. Recently, research on combinatorial auctions has attracted considerable attention (Fujishima et a! 1999; Leyton-Brown et a! 2000; Klemperer 1999; Sandholm 1999; Lehmann 1999; Rassenti 1982; Rothkopf 1998; Yokoo et a! 2001) due to the sheer interconnectedness of the Inter­ net. One way to analyze combinatorial auctions is to use search algorithms such as branch and bound. This ap­ proach can produce optimal solutions, however, it is ex­ ponential in the worst-case. An alternative approach, which uses approximation algorithms, is typically poly­ nomial but the quality of the solutions cannot be guaran­ teed.

This paper addresses the issue in a combinatorial market where the retailer prefers to sell bundles of goods. A large number of buyer's agents dynamically form coalitions to exploit the benefits of grouping based on their complemen­ tary needs. The transaction is done at the coalition level such that the price for each buyer's agent is cheaper than if buying independently. Coalition formation has been ad­ dressed by researchers from both the game theory commu­ nity and the multi-agent community. Game theory empha­ sizes the issues of N-persori games formation under differ­ ent settings and the distribution of the benefits among play­ ers (Kraus et a! 1991 ). It concentrates on the stability and fairness issues for given coalitions. Multi-agent research emphasizes the special properties of a multi-agent environ­ ment and considers the effects of communication costs and limited computation time on the coalition formation process (Sandholm 1999a; Sandholm 1999b).

We use a physics-based approach to study the dynamic behavior of agents in the combinatorial market where coali­ tions are involved. There are efforts to study large-scale multi-agent systems using a physics-based approach (She­ hory et. a!; Lerman et. a!. 1999). For example, Lerman and Shehory (Lerman et. al. 2000) propose a physics-motivated mechanism for coalition formation in non-combinatorial markets. The problem addressed in our work is different because we study the issue where the retailer prefers to sell complementary goods. In contrast, the formulation of Lerman and Shehory deals with the case where the retailer only has one category of goods. Thus, the agents in our study are heterogeneous because they may be interested in different goods. Agents in their study are homogeneous in the sense that they are all interested in one category of goods.

The remainder of this paper is organized as follows. The next section proposes a combinatorial market model and a physics-motivated dynamic equation for structured coalition formation. Section 3 presents simulation experiments to study the global behavior of the system. Section 4 briefly concludes the paper.

2 Combinatorial Market Model

Figure 1 shows the marketplace to be discussed in this paper. Suppose that the retailer has two types of items to sell: item of type a and item of type b . Suppose that there are two categories of agents for buyers in the Marketplace. An agent of category A is only interested in buying one item of type a . An agent of category B is only interested in buy­ ing one item of type b . Each agent represents one buyer and receives instructions from the buyer on what item to buy. Before an agent enters the marketplace, it needs to register and .obtain authorizations from the retailer. Then it can interact with other agents in the marketplace and per­ form purchase related activities. In the rest of this paper, we assume that in the marketplace there are in total m A of A type agents and m a of B type agents registered.

;;;---·---·-·-·---------·-·-·

There are many ways the retailer may sell its items. It might simply sell an item to a buyer's agent when the agent requests the item. However, retailer can save resources if it can sell items in bundles composed of the two types of items. The retailer can give a cheaper price for each item in the complementary bundle and at the same time still obtain a higher utility value. In order for agents benefit from bun­ dles, they need to form coalitions. We assume that the agents and the marketplace are fully connected. However, agents do not have a global knowledge of the whole situa­ tion, and their decisions are based solely on local condi­ tions.

Now we discuss the dynamics of the changes of coali­ tions in the marketplace. A single agent might join a coalition in order to obtain a discounted price. Since the agent cannot have a global view of the whole marketplace at a given time instant, the coalition chosen might not be the best one for the agent at that time. An agent may also leave a coalition to look for better opportunities. We assume that the retailer is able to monitor the coalitions of the whole marketplace and to decide when to perform the combinato­ rial transactions. Our goal is to study the dynamics of the coalition formations in the marketplace and the effective­ ness of the marketplace.

We first define the price for a given item associated with a given coalition. We consider a coalition formed by n A of type A agent and n a of type B agent. If all of the agents in this coalition voted to perform the coalition transaction (i .e., to buy their items in a bundle), then we use PA ( n A , n a ) to denote the price the seller prefers to set for an item of type A and Pa ( n A , n a ) to denote the price the seller prefers to set for an item of type B. Suppose that the retailer set the prices as follows:

Here Pj 0 l and Pi 0 ) are the base prices for item A and item B respectively. The real price for an item is deter­ mined by the size of the coalition.

MA and Ma are the price reduction rates due to grouping for item of type A and for item of type B respec­ tively. In a coalition, as the number of items of a given type increases, the price per item of that type decreases.

The variable r0 gives the preferred ratio n A/ n a of the two types of items in a bundle for the retailer. The term q A gives the price penalty rate for item of type a if the ratio of the items in the coalition does not match the retailer's pre­ ferred ratio. Similarly, the term q a gives the price penalty rate for item of type b . This kind of combinatorial prefer­ ence is fairly common in traditional commerce as well as in e-commerce. For example, a furniture retailer may prefer to sell a sofa and the accompanying coffee table as a set, rather than sell each piece separately. In this case, the price for a complete bundle (one coffee table and a sofa) may be cheaper than the sum of the prices for the components. The ratio of the number of coffee tables to the number of sofas is important, since the retailer might prefer the ratio to be 1 if there is equal number of table-sofa pairs in the storage. In any case, buyers who are interested in separate pieces can form coalitions to save money. This kind of coalition form­ ing process might be time consuming in traditional com­ merce, because location and time constraints make it diffi­ cult to find complementary buyers. However, it will be to­ tally different in an agent-mediated e-commerce combinato­ rial marketplace. The sheer interconnectedness of the World Wide Web will enable the e-commerce agents to work at any time from anywhere in cyberspace. Furthermore, agents can negotiate instantly provided that the requirements of the task can be clearly specified, and the interaction protocols can be clearly defined among agents and between agents and the corresponding enterprise system (as is assumed in this paper).

In order to study the dynamics, we use N ( n A , n 8 , r) to represent the number of coalitions composed by n A of type A agents and n 8 of type B agents at time r . Different types of coalitions can be represented by a lattice as shown in Figure 2. Where (i, j) represent the value of N(i,j, r) .

The number of different types of coalitions will change while the system approaches equilibrium. Our goal is to study the value of N ( i, j, r) and other associated indica­ tors of the effectiveness of the combinatorial markets as time evolves.

We assume that for a given coalition, at most one agent can join or leave at a time. Thus, the only translation in the coalition lattice is between neighbors as illustrated by the following:

When a category A agent joins a coalition of type ( n A , n ) , this coalition becomes a coalition of type ( n A + f, n 8 ) . When a category A agent leaves a coalition of type ( n A , n 8 ) , this coalition becomes a coalition of type ( n A -1, n 8 ) . Similar analysis can be applied to type B agent.

Figure 3 shows the transitions that could happen with re­ spect to coalition type ( n A, n 8 ) when it is within the lat­ tice. Please note that when ( n A , n 8 ) is at the boundary of the lattice, some of the transitions in Figure 3 will not hap­ pen. The dynamics of the transition can be characterized by the following equation (for all the ( n A, n 8 ) pairs, except (1,0) and (0,1) ):

Here, Ki and K; are rate constants, which depend on the price change for each transition. In the above equa­ tion, the total number of agents of the market is con­ served during the dynamic process. The single agent pool serves as the source sink of the system. Please note that

0 ~ n A ~ m A and 0 ~ n 8 ~ m 8 .

The term K 1 N(1,0,t)N(nA -1,n 8 ,r) gives the rate for a type A agent joins a coalition of category N(nA -1,nB..2 .

The term K3N(n A + 1, nB, r) gives the rate when a category N ( n A + 1, n 8 ) coalition becomes a category N ( n A , n 8 ) coalition. In other words, it gives the rate for a type A agent l!'!aves a N ( n + 1, n 8 ) coalition.

Theterm K3N(1,0,r)N(nA,n ,r) givestheratefora type A agent joins a category i.J( n A , n 8 ) coalition. In other words, it gives the rate for a category N ( n A , n 8 ) coalition becom!'!s a category N ( n A + 1, n 8 ) coalition.

The term K 1 N(nA,n 8 ,r) gives the rate for a type A agent leaves a category N ( n A, n 8 ) coalition. In other words, it gives the rate for a category N ( n A, n 8 ) coalition becomes a category N ( n A -1, n 8 ) coalition.

Other terms in the above equation are related to type B agent and can be similarly explained.

When the value of N(i, j, r) is outside the boundary of the lattice, the corresponding term in the above equation will equal to 0 . In other words, in the above equation, we setN(i,j,r)=O if i<O, or j<O, or i>mA, or j > m 8 , or i = j = 0 .

Now, we need to study the rate constants involved in the dynamic equation.

One simple model would be to let all of the escape rates be the same (i.e., the rate at which an agent leaves a coali­ tion, a.k.a. , the opp,ortuni~t's rates):

We assume that the rate an agent joins a coalition is closely related to the changes in price for this coalition. Let the change in price serves as energy in Boltzman distribu­ tion.

K 1 is a constant that is related to the transition of a coali­ tion from (n A -1, n 8 ) to (n A, n 8 ) . Thus, this constant is only related to type A agent.

At point ( n A -1, n 8 ) , we have the price for a type A agent:

Here, K 0 is the base rate in the above equations. Similarly, we can set other rates:

To analysis the dynamics of the above system, we can study, under different values of parameters, the evolution of N ( n A, n 8 , r) and other indicators of the marketplace as a function of r and at the equilibrium state. Based on the calculated derivatives, we can update a coalition using the following formula (for all the (n A, n 8 ) pairs, except (0,1) and (1,0) ):

During the update process, the time step ~ r should be adaptively selected such that it is small enough and the up­ dated results for any coalitions should not be less than 0 .

The updated value of N(0,1, r + ~ r) and N(l,O, r + ~ r) can be obtained from the following equa­ tion after all the other N ( n A, n 8 , r + ~ r) are updated:

3 Simulation Results

We have conducted various experiments to test the market­ place. At first, we set all the values of N(n.A,, n 8 ,0) equals to 0, exce~t that N(1,0,0)=mA and N(O,l,O)=mg. In our expenments, we set m = m 8 =50, and K 0 = 1. Please note that P~ 0 ) and ~o) have no influence on the derivatives.

In the first set of experiments, we study the evolution of the coalitions in the market as a function of time. Table 1 shows the parameter values that are used.

Figure 4 (a), (b), (c), and (d) show the evolutions of coali­ tions as a function of the iterations. Notice that at beginning, most of the agents are in coalitions that contain small num­ ber of type A and type B agents. Then, as a result of dy­ namic movements of agents, the number of coalitions with small size decreases and the number of coalitions with large size increases until equilibrium is reached. Further note that the distribution of A type agents and B type agents is not symmetric. The reason for this is that the ratio r 0 = 0.5, rather than r 0 = 1 . Thus coalitions with twice as many A agents as B agents receive the least price penalty. Although intuitively most of the agents should stay in large coalitions at equilibrium, Figure 5 shows that this is not the case. This result is different from that of (Lerman et al., 2000) in which most agents join the largest coalitions. One reason for this difference is that the price settings in combinatorial markets are quite different from those in non-combinatorial markets. Our situation is much more complex, and the coa­ lition size is only one of the factors that influence the movements of agents. The escape rate is a parameter that has a bigg-er effect on the size distribution of coalitions. The greater the escape rate, the more the agents escape from the larger coalitions. Compare Figures 6(a), 6(b), and 5(d), we can notice that the number of the small sized coalitions is bigger when the escape rate is larger.

Figure 7 shows the value of entropy as a function of the iterations. We use the same values for parameters as those in Table 1, except that K escaP.,e = 0.005 and r0 = 0.1 . We set the initial prices as P~ 0 l = 2.85 and Pi 0 l = 5.1. Please note that these initial prices are set to make sure that all the prices are positive for any coalitions at any given moment.

To calculate the entropy with respect to the number of coalitions of various sizes, we first calculate the probability that a given sized coalition within the population of all the coalitions:

The entropy with respect to coalition sizes is given by:

Similarly, the entropy for type B agent within different coali­ tion sizes can be calculated as:

We can notice that the values of both entropies increase with the iteration until the system reaches its equilibrium.

The average price per type A item and the average price per type B item are principal indicators of the effectiveness of the proposed combinatorial marketplace. These average prices can be calculated with the following formulae respec­ tively.

Figure 8 and Figure 9 show the evolution of the average prices of a type A item and that of a type B item. We can notice that the average prices keep decreasing until the sys­ tem reaches the equilibrium. This demonstrates the advan­ tages of using agents in combinatorial markets.

4. Conclusions

In this paper, we propose a theoretical framework for coali­ tion formation in combinatorial transactions. A novel phys­ ics-based dynamic equation is proposed to capture the es­ sence of the movements of agents among different sized coalitions as driven by the price differences of these coali­ tions and by the opportunities of joining better coalitions. We perform simulation experiments to evaluate the pro­ posed combinatorial marketplace and the results show that the marketplace can reduce the average prices for the buyer's agents if opportunities are fully explored. Our ap­ proach towards combinatorial trading is different from pre­ vious work because we address the issue from a macro­ scopic point of view.

Our framework is generic, although we make many simpli­ fying assumptions in our current proof of concept model so as to make the simulations easier. We are exploring many more issues with our current model as a starting point. In our model, the rate at which an agent joins a coalition de­ pends only on the price reduction for that agent. Any re­ quest to join a coalition is accepted. Another way of model­ ing the market is to emphasize the coalition an agent is about to join. For example, the rate can be determined by considering how the changes in coalition size change the prices for the "old" members of the coalition, or the total price for the "old" members of the coalition etc. In our cur­ rent model, we simply assume that the escape rates are the same for all the agents. It is interesting to study the situation when the escape rates depend on different types of agents and different sizes and structures of the coalitions. In our current model, the ratio of the two types of agents within a coalition is an important factor in determining the price. It is worth studying the coalition market without perfect ratio of goods. In our current model, the price given by the re­ tailer is fixed. It would be interesting to study the situation where the retailer can perform dynamic pricing according to its knowledge of the coalitions. Our model addresses a very simple combinatorial market where there is only one retailer and two different products. It would be interesting to study the dynamic behaviors in a marketplace where there are a large number of retailer's agents that might form coalitions to offer complementary products and a large number of buyer's agents that might form coalitions to explore the benefits of grouping. It would also be interesting to study the coalition dynamics of open combinatorial markets when agents are allowed to flow in and out of the marketplace. It is important to study the qualitative behaviors of the pro­ posed model throughout in the parameter space. The simula­ tion based on our current simple model already shows some interesting phenomena. We are convinced that the behaviors of the system will be quite rich when more complex models are used.

Acknowledgments

We would like to thank Eric Harley and the IJCAI reviewers for their valuable comments.