Procurement Auction with Supplier Coalitions: Validity

Requirements and Mechanism Design

Mingzhou Jin and S. David Wu
Department of Industrial and Systems Engineering
P.C. Rossin College of Engineering, Lehigh University

Abstract: We study the formation of supplier coalitions in the context of a buyer-centric

procurement market. Considered under a second-price descending seal-bid auction, we
propose a two-stage auction mechanism that allows suppliers to form coalitions with one
another. Building on the foundations of core games and bidding-rings, we explore the idea of
managed collusion which provides a means to enhancing bidder profitability. We identify
six basic requirements for a valid coalition mechanism including characteristics such as
individual rationality, welfare compatibility, maintaining competition, and financial
balancedness. We show that such mechanism could be constructed so that the buyer does not
loose the advantage from supplier competition, and that a stable coalition structure could be
formed. We propose a profit distribution scheme among members in the supplier coalition and
show that the proposed scheme provides proper incentive such that (1) the best strategy for a
coalition member is to comply with the coalition agreement, and (2) bidding the true cost is
the best strategy so long as the bids are uniformly distributed and the bidders cost is above a
certain threshold.

We also investigate the stable coalition structure under the proposed

mechanism and show that under symmetric information there exists one unique strongly stable
coalition structure.
Keywords: Supply Chain Management, Coalition Structures, e-Commerce, Procurement
Auctions, Mechanism Design

1. Introduction
Business-to-business electronic commerce, the use of electronic means to conduct business
transactions within or across business entities, has been touted as the most important economic
development of the decade. The 2001-2002 economic downturn has significantly dampened the
development of eCommerce initiatives. Nonetheless, according to a June 2002 survey by AMR
research [2], leading companies are continuing to deploy on-line commerce application such as
Private Trading Exchanges (PTXs), while others have implemented more basic means of on-line
transactions. They surveyed companies in several industry sectors including Chemical, Industrial
Equipment, High-Tech and Electronics, Oil and Gas, and Consumer Goods. These companies
report an average investment of $6.57M in building their on-line commerce system, while the
expected Return on Investment (ROI) averages around 7%. The survey cited the (lack of)
readiness and acceptance of supply partners as the two biggest hurdles to implement B2B
eCommerce. Moreover, 52% rated value creation and enablement for supply partners as being
the most critical.

From the viewpoint of supply chain management, an on-line market such as PTX includes three
main parties: the buyers, the suppliers and the market maker. The role of the three parties can be
simply stated as follows: the buyer tries to find the most economical ways to fill his orders, the
supplier desires to improve his market share while protecting his profit margin, the market maker
extracts transaction fees or delivers packaged services by matching the buyers with the suppliers.
The market makers short-term goal maybe to establish credibility in niche commerce areas, and
in the long-run increase market participations, therefore higher profit potentials. Of interest to all
three parties is market efficiency. We will define market efficiency more precisely in our
analysis, but intuitively efficiency is built on the premise of fair competition and fair distribution
of surplus among market participants. In existing eProcurement markets, the buyers tend to be
represented by a few large firms. The suppliers, on the other hand, are much more numerous and
the competition among them is fierce. For example, Freemarkets [1] report that in the first
quarter of 2002 that a total of 125 buyers traded in their procurement auctions, with some 21,000
suppliers participating. All auctions were triggered by buyers demand, and each auction has one

buyer and many more suppliers. Freemarkets claimed a total saving of $800 million (for the
buyers) during this period, over a total auction value of about $4 billion. One may infer from the
above that the buyer has significant advantage over the suppliers, and the suppliers margin may
erode significantly.

Many would attribute the early success of eProcurement to the apparent savings it brings to the
buyers. Through electronic markets, the buyers have direct access to a large number suppliers
and therefore lower prices. They would urge their existing supply partners to join the on-line
market, who may do so just to secure the customer base. Once joining the market, the supplier
may quickly lose previous benefits from long-term business relations, while facing fierce
competition in a global scale. These suppliers are likely to suffer from undercut profit margins,
and facing the dilemma of staying in or fleeing the market. Suppliers who have leverage other
than that of pricing (e.g., unique technology) are likely to avoid on-line commerce altogether. As
suggested by Wise and Morrison (2000) the above buyer-dominant phenomenon is among the
fatal flaws of earlier B2B model. This observation echoes the findings from the AMR survey,
as the main difficulty in implementing on-line commerce is to convince the supply partners that
the new business paradigm creates value for them as well. Otherwise, there is little incentive for
the supplier to invest in the multi-million dollar infrastructure required for long-term, stable online transactions. A main purpose of this paper is to explore mechanisms that would
systematically improve the suppliers margin without sacrificing competition, thus market
efficiency. We believe such mechanisms are crucial to sustain the long-term viability of on-line
commerce.

We submit that market efficiency and stability are the keys to its long-term success. We examine
a mechanism for procurement auction where suppliers are encouraged to form coalitions with
one another under market rules with the goal of increasing supplier profits but without degrading
market efficiency. We will show that such mechanism could be constructed so that the buyers
do not loose the advantage from supplier competition, and that a stable coalition structure could
be formed.

In traditional supply chain operations, where each buyer tends to deal with a limited number of
suppliers via long-term, off-line negotiations, the interaction among the suppliers is limited (and
sometimes considered as illegal collusion). From a modeling viewpoint, it is sufficient to
consider supply chain coordination via one-buyer one-supplier negotiation pairs, as is the case in
a majority of the supply chain literature. However, the emergence of on-line commerce makes
inter-supplier interactions more direct and much more critical. It is of importance to consider not
only supplier-buyer interactions but also the interactions among competing suppliers who may be
at the same time collaborating. It is our intention to examine how this interaction could be
directed toward improved market efficiency.

2. Related Literature
We will review three areas of research that are directly related to the paper: auction
mechanisms of various forms, coalition formation in non-cooperative games, and bidding-rings.
Auction is a popular form of price determination in eCommerce, owing to its simplicity and low
information requirements. Basic forms of auction exist in human economy for a long time, but
the research literature on auction theory exploded after the seminal paper by Vickrey [1961],
which proposes the concept of the second-price sealed-bid auction. Second-price auction awards
the lowest bidder the second lowest bid price, which is proposed as a means to encouraging all
sellers to bid at their true costs. Vickrey proves analytically that this scheme is incentive
compatible since neither bidding above nor below the true cost would make the bidder better off.
Sandholm [1996] point out some limitation of the Vickrey auction in computational multi-agent
systems. For other well-known forms of auctions the readers are refer to surveys such as the one
given by Rasmusen et al [1992]. More recently, Beam and Segev [1998] and Herschlag and
Zwick [2000] provide surveys on various Internet auctions.

McMillan [1994] discusses

mechanism design for the spectrum auction and compared open vs. sealed-bid auction,
simultaneous vs. sequential auction, and several stopping rules. Milgrom [1998] discusses the
simultaneous ascending auction for radio frequency spectrum in some detailed. Klemperer
[1999] provides an excellent survey on the economic theory of auctions.

Coalition formation has been studied intensively by the game theorists. A primary motivation
for players in a game to form coalitions is to improve their surplus. There are three basic
problems in coalition formation in a given game: whether a stable coalition exists, how to share
profit among the participants, and who should be in which coalition (coalition generation).
Among various theoretic developments, the core introduced by Gillies [1953] is the earliest and
most well accepted for coalition formation problems. The core is the set of all feasible payoffs to
the players that no player or group of players could improve upon by acting unilaterally. The
existence of a nonempty core implies that the game will have a stable solution and the players
will have incentive to form the grand coalition. For the detailed discussion on the core, refer to
Kannai [1992], Peleg [1992], Anderson [1992] and Gabszewicz [1992]. The literature on core
game typically considers the stability of the grand coalition in a game, and does not offer
practical solution for coalition formation.

Another related line of literature in economic theory is collusion in auctions. A primary focus of
this literature is the presence of illegal cartels among bidders (also known as bidding-rings),
who try to optimize joint expected profits, thus undercut the sellers profit. A typical assumption
(under single item auction) is that the cartel would select a designated winner who follows a
particular bidding strategy, while requesting other members to be inactive during the auction.
There are various strategies possible for the bidders to conceal the existence of the cartel by
creating bidding patterns that mislead the seller. However, there are enforcement issues in the
cartel as the designated losers may have incentive to deviate from the cartel agreement.
Robinson [1985] shows that cartels are stable (i.e., incentive-compatible) if the seller uses open
ascending-bid auctions, but not if he uses sealed high-bid auctions (e.g., Dutch auctions). Under
the latter setting, McAfee and McMillan [1992] make the distinction between weak and strong
cartels, where only the latter can exclude new entrants and make transfer payments among cartel
members. They show that only the strong cartel could indeed achieve efficiency (maximize
the bidders expected profit), but in effect re-auctions the good among its members. Graham and
Marshall [1987] examine collusion in second-price auctions. In their setting, the identity of the
winning bidder and the price paid (which was the second highest bid) are common knowledge,
while the information concerning bid valuation is private. All members share the gains obtained
by the ring. They propose a second-price pre-auction knock out (PAKT) within the ring, which

generates the bid to be used in the main auction. They show that it is a dominant strategy for the
bidders to corporate in the ring, and that an all-inclusive ring is optimal. Malaith and Zembsky
[1991] also examine collusion in second-price auctions. Guth and Peleg [1996] consider the
second-price auction setting where PAKT precedes the main auction. They introduce the notion
of envy-freeness (i.e., no bidder prefers another bidders net trade to his own) in this context, and
offered an impossibility theorem, which states that none of the transfer payment scheme
satisfying envy-freeness condition is incentive compatible, i.e., bidders do not bid truthfully; A
ring member will overbid his true value to induce a higher transfer payment from the rings
representative, and underbid if he believes that he will be chosen as the representative.

In this paper, we examine the idea of managed collusion as a means of coalition formation in
reverse auctions, with the purpose of improving the bidders expected profit. Building on the
theoretical foundation established in auction theory, core games, and bidding rings, we intent to
offer an analytical framework that tackles the theoretical underpinnings of this problem.

3. Coalition in an Auction Market

3.1 Settings of the Auction Market

We consider an electronic market where the auctioneer uses auction as a pricing mechanism to
identify the lowest possible supply price for the item specified by the buyer. The buyer may
specify a reserve price, and is entitled to reject the auction outcome if the final price exceeds the
reserve price. The item for auction is a buyer- specified order, where the suppliers must respond
to one order at a time via an auction mechanism. The buyer must announce a priori all order
parameters before the auction starts. Each supplier computes pricing based on his own cost
structure relative to the announced specifications. The suppliers may form alliance with one
another under a coalition mechanism instigated by the auctioneer. Such coalition mechanism
must satisfy a number of basic properties so that it not only improve the suppliers margin but
also improve overall efficiency of the market, thus protecting the buyers interests. This will be
the focus of the following analysis.

Several different auction mechanisms are possible in this environment as described in Section
2. We will focus our analysis on the second-price, seal-bid simultaneous descending auction
similar to that of Milgrom [1998]. In each round of the auction, the auctioneer decreases the
price by one unit, the bidders whose intended bid higher than the current price will immediately
drop out. The auction continues until there is only one supplier left in the system, and this
supplier is rewarded the price when the last supplier drops out, i.e., one unit below the second
lowest price among all participating suppliers.

We now explain the basic principle that provides the surplus to sponsor a supplier coalition.
Consider the cost scenario for a two-supplier example depicted in Figure 1. The buyer announces
in the market an order with specification q, which could be any attribute describing the order,
such as quantity or quality. For all orders to be considered in the market, q is a random variable
described by density function f(q). s1(q) and s2(q) represent the cost functions of supplier s1 and
s2 in q, respectively. The buyers reserve price is r(q). Define sm(q) as the collective cost function
of all other suppliers in the market S, i.e., sm(q) represents integrated market information.
s2(q)

Cost

s1(q)

sm(q)

b
c

B
A

f(q)

Figure 1. An Example Cost Structure for Suppliers in the Market

7

The second-price descending seal-bid simultaneous auction is used to determine which

supplier(s) wins a given order in the market. As shown in the example, when the order attribute q
falls into region A, supplier s1 would win the order and awarded the bid min{s2(q),sm(q)}; when
the order fall into region B, supplier s2 would win the order and awarded min{s1(q),sm(q)}. Thus,
the expected profit for s1 is defined by area a, and the expected profit for s2 is b. If suppliers s1
and s2 form a coalition, (i.e., they still bid at their true costs, but now they win the bid for the
coalition) they will win the orders fall in either region A or B, and gain additional expected profit
represented by area c, which they may share. This provides the basic incentive for suppliers to
form coalition in the auction market.
3.2 Previous Results on Coalition Formation: The Core Game
Our proposed specification for supplier coalition mechanism rooted from the principles in a
classical core game. A detailed discussion on various aspects of the core can be found in
[Kannai, 1992]. Let N={1,2,...n} be the set of all players. A subset of N is called a coalition.
The characteristic function is a real-valued function v() defined on the coalition which
represents the outcome for and v()=0. An outcome of the game is an n-dimensional vector
x={x1,,xn}, which represents how much each player iN receives as payoff. Almost all existing
coalition theory requires the assumption that v() is well defined, i.e., the value of a specific
coalition is independent from the other coalitions. Gillies [1953] proposed the concept of core
game for the grand coalition. A core is the set of all feasible outcomes that no player or group of
players could improve upon by forming a subset coalition. An outcome is in the core when it
satisfies the following:

v( )

(1)

Much of the theoretical development in the core game sets out to answer the question: Whether
the core is empty for a the set of players N in a given game? If the core is nonempty, the grand
coalition has one or more stable outcome solutions. An important concept in the core game is
that of a balanced collection of coalitions. A collection {1, ,k} of coalitions is balanced if
there exists positive numbers (called balancing weights) 1,,k such that for every

i N,

j , i j

= 1 . Shapley [1967] and Bondareva [1963] give the following theorem for this

classical problem:
Theorem The core of the game v is non-empty iff for every balanced collection {1, ,k} with
balancing weights {1,,k}, the following inequality holds:
k

v(
j

j)

v( N ) .

(2)

j =1

Clearly, the core for a given set of players N could be empty. Shapley and Shubik [1973] suggest
constraints for coalition formation such that non-empty coalitions could be formed.

The core game assumes that the coalition maximizes some measure of systems welfare, and
studies whether the players in the system have proper incentives to form such coalition.
However, answering the question whether the core exist may not be sufficient to model
coalition formation in an auction market. Additional insights might be gained by modeling the
players choice based on the profit distribution scheme within the coalition. Later in Section 4,
we propose such a mechanism. Note that the classical core game does not model this aspect of
coalition formation. In the following, we first specify the requirements for a proper coalition
mechanism in the auction market.
3.3 Required Properties of the Coalition Mechanism
In this section, we define basic requirements for a supplier coalition mechanism in the auction
market specified above. These requirements form the criteria through which we may evaluate the
design of a coalition mechanism. We first define as follows the expected profit of supplier si S
before he joins any coalition:
E[p i (q)] =

[ min {r(q),s j (q) | j S {i}} s i (q)]

f(q)dq

(3)

A coalition mechanism defines the basic rules that allow suppliers to form efficient alliances
with one another. Specifically, we define a coalition mechanism as two basic components:
(1) coalitions generation, where the membership of each coalition is indentified,
(2) profit distribution (among coalition members) once the coalitions are formed.

We argue that profit distribution is the key to a coalition mechanism.

Once the profit

distribution scheme is properly defined, coalition generation follows by considering each

players incentive via computed expectation of the players profit. Thus, our discussion in the
rest of the paper will focus on the properties of profit distribution. Following the convention of
the core game, if under mechanism the total profit for any given coalition is independent from
all other coalitions, we say mechanism is well defined. Denote a specific supplier collation j,
where j S. A coalition structure is a set of coalitions {j} that are mutually exclusive and
exhaustive, i.e., U j j = S and j k = . Clearly, the possible number of coalition among n
suppliers is 2n1. Under a specific coalition mechanism , we denote supplier sis profit as
p,i(,q). We now list requirements for a valid coalition mechanism:
1. Individual Rationality: A fundamental requirement for a coalition membership is that all
members in the coalition have an expected profit higher than his own expected profit by acting
alone. In other words, the coalition mechanism should satisfy individual rationality, which is
defined as follows:
E[ p,i ( , q )] E[ pi (q )] i

(4)

where E[ p ,i ( , q )] is the expected profit of supplier si after joining coalition under mechanism

.
2. Private and Distributed Information: The coalition mechanism should not require the
members to reveal their cost structure or other private information. Although information could
be communicated rapidly and conveniently in the electronic market, information essential for a
firms competitiveness must be kept private. As in normal game theoretic assumptions, even if
an agent is asked to provide pricing information, there is no guarantee that the information
provided is truthful.
3. Observability and Controllability: Since each player maintains his private information in a
distributed fashion, only information observable by all could be utilized by the coalition
mechanism, i.e., the mechanism must be implemented solely on observable information. Further,
all actions to be taken by the mechanism should be controllable by the market, e.g., a meaningful
punishment could be imposed on the members who violate the market rules.

10

4. Social Welfare Compatibility: From the viewpoint of the buyers, an efficient market is one
where every order is processed with the lowest achievable cost in regard to the order. A cartel in
the tradition sense doesnt satisfy this condition as it might intentionally assign some orders to
members with higher cost for the interest of increasing profit. Such coalition is unlikely to
survive in a competitive market.
5. Maintaining Competition: Most countries prevent monopoly by anti-thrust regulations, as
monopoly diminishes the incentive for true competition. Thus, the coalition forming mechanism
must maintain competition among its members, i.e., regardless of which coalition they belong;
every player in the market should have the incentive to reduce cost in order to compete with
other players.
6. Financially Blancedness: The mechanism should guarantee that the formed coalition is
financially balanced, i.e., the market maker doesn't need to provide subsidy to any coalition
under the mechanism.

,i ( , q)

= v ( , q )

for any and q

(5)

4. An Auction Mechanism with Supplier Coalitions

In the following, we describe an auction mechanism that facilitates supplier coalitions. We
propose a profit distribution scheme, which we will show providing the proper incentives for
suppliers to form valid coalitions, i.e., a coalition mechanism defined based on this profit
distribution scheme is well defined and satisfies the six basic requirements specified above.

We first define the meaning of profit distribution for supplier coalitions.

Definition 1. Profit distribution within a supplier coalition refers to the splitting of the portion of
the overall profit exceeding what any individual suppliers could achieve by acting alone.

We now describe an auction mechanism in conjunction with a profit distribution scheme given a
coalition structure {i}. The mechanism consists of three main phases that includes two subauctions both supervised by the market maker.

11

Auction Mechanism with Supplier Coalitions (AMSC)

Phase 1. All suppliers compute their bids based on their own cost structure for a posted buyer
order. A supplier coalition submits the bid that is the lowest among its members, and will be
viewed as a single supplier during the auction. The second-price, seal-bid simultaneous
descending auction takes place, i.e., in each round of the auction; the auctioneer decreases the
price by one unit if the number of bidders is more than one. The auction stops when there is only
one supplier left in the system. This is the lowest-cost supplier who will be reward the second
lowest bid price (outside his coalition). Note that suppliers belonging to the same coalition do not
compete against each other in the view of the auctioneer.
Phase 2. Suppose supplier si wins the order with price p1 and sij, we say that coalition j wins
this order with price p1 (since supplier sis bid is not compared against other member of his
coalition, the second lowest bid price p1 is offered by a supplier outside coalition j). The market
maker starts a second-price sealed bid auction within coalition j for this order and the supplier
with the lowest bid wins the order with the second lowest price p2. If there is a tie for the lowest
bid within the coalition, then the players with the lowest bid has equal probability to process the
order. Furthermore, allocation of profits within the coalition is based on the lowest among the
bids that are strictly greater than the lowest bid, not on the second number in a sorted list of all
bids.
Phase 3. The coalition shares the addition profit (p1 p2) evenly among the members, i.e., each
receives ( p1 p2)/|j|.
Again, consider the example in Figure 1. Suppose an order described by q falls into region A.
The bid would be won by the s1-s2 coalition (due to supplier s1) with reward p1=sm(q) (since s2
does not compete against s1) given to the coalition. In the Phase 2 auction within the coalition,
supplier s1 win the bid with reward p2=s2(q). The two suppliers split the additional profit (p1 p2)
evenly. As a result, supplier s1 receives profit s2(q) s1(q)+( sm(q) s2(q))/2, supplier s2 receives (
sm(q) s2(q))/2.

12

The reason that the Phase 1 and Phase 2 auctions are both needed in the mechanism is due to the
truth revealing property of the second-price seal-bid auction. An implicit but important property
here is that the second-price auction will always induce the suppliers participating in the auction
to reveal their true costs. Suppose we eliminate Phase 2 auction but simply record in Phase 1 the
lowest bid and the second lowest bid in each coalition, say pmin and pmis, respectively. At the end
of the auction, the supplier with bid pmin would win a bid at p1 for the coalition. Since the second
lowest bid in the coalition is already recorded, (pmis =p2), we would have no problem computing
the additional profit (p1 p2) brought by the coalition. This makes the Phase 2 auction seemly
unnecessary. Nevertheless, without the Phase 2 auction supplier smis who has a true cost of pmis
would not actually participate in the auction since the supplier with pmin would represent the
coalition. Consequently, there is no proper incentive that would ensure supplier smis to reveal his
true cost. For example, in the case of equal profit sharing described in Phase 3, supplier smis
actually has the incentive to lower his bid below his true cost in order to increase his share of the
coalition profit (p1 p2)/|j|.
4.1 Incentive Compatibility
Recall that Guth and Pelegs [1996] impossibility theorem states that none of the transfer
payment scheme (in our case, (p1 p2)/|j|) satisfying envy-freeness condition is incentive
compatible. Applying their results in our situation, it would imply the following: if a coalition
member believes he is the second lowest cost supplier in the coalition, he will underbid his true
value (to lower p2) to induce a higher transfer payment from the coalition, but he must be careful
not to lower his bid below the lowest cost in the coalition otherwise he will suffer the winners
curse. In the following, we will show that our proposed profit distribution mechanism provides
proper incentive such that (1) the best strategy for the suppliers in the same coalition is not to
complete with one another, and (2) bidding the true cost is the best strategy so long as the bids
are uniform distributed and the bidders cost is above a certain threshold. Given the auction
mechanism described above, and a coalition structure {i}, we state the following proposition:
Proposition 1. (Compliance) In a second-price, seal-bid simultaneous descending auction
participated by all suppliers, if profit distribution (Definition 1) is used among coalition

13

members, the best strategy for a supplier si in coalition j is not to compete with other members
in the same coalition j during the auction.
Proof:

Suppose the first and second lowest cost suppliers are smin and smis, respectively.

Coalition j may only win the bid if the lowest cost supplier smin is in the collation. When
coalition j wins the order characterized by q, the reward p1 will be
p1( j ,q) = min {r(q),s i (q)|i j }

(6)

If p1 (j ,q) < si(q) ij, coalition j will not win this order in the first place. If coalition j
does win the order, it is sufficient to consider two cases:(1) the second lowest cost supplier smis
(where smis(q) < p1) is also in j, and (2) otherwise
When (1) is the case, it is the best interest for thej suppliers other than smin (including smis) not to
participate in the auction since the profit to be distributed in the coalition is the difference
between the second lowest cost outside the coalition, p1 (j ,q) and the second lowest cost inside
the coalition smis(q), i.e., p1 (j ,q) smis(q). If any supplier sk in coalition j with cost sk(q)< p1
(j ,q) competes in the auction, sk(q) would replace p1 (j ,q)and his profit would decreases. On
the other hand, for a supplier sl in coalition j with cost sl(q) p1(j ,q), competing in the auction
will not increase his profits.
When (2) is the case, it is again the best interest for thej suppliers other than smin not to
participate in the auction since all profits p1 (j ,q) smin(q) go to supplier smin in any case.
The above proposition answers a fundamental question: If all suppliers in a coalition participate
directly in the auction, do they have the incentive to act collaboratively as a member of the
coalition? The answer is yes. Thus, the rule of participation in the above auction mechanism is
indeed incentive compatible. In the following, we show that giving the true cost during the
auction is the best strategy for the suppliers.

Proposition 2. (Incentive Compatibility) Given the profit distribution scheme defined by AMSC,
the best strategy for a supplier si in coalition is to reveal his true cost in both Phase 1 and
Phase 2 auctions, so long as the bids are uniformly distributed and his cost is greater than ||/2.

14

Proof. To prove that players will tell the truth during the second stage auction.
Suppose coalition wins the order in the first stage auction and this auction has n members.
Thus, a supplier i would fall into one of the following categories (1) the lowest cost in , (2)
the second lowest cost in , or (3) otherwise. Thus, the expected profit for supplier i with the
placed price si(q) is as follows:

(min {s j (q)|j s {i}} s i (q) +

p1 min {s j (q)|j s {i}}

||

) Pr[min {s j (q)|j s {i}} > s ' i (q)]

p1 s ' i (q)
) Pr[min {s j (q)|j s {i}} s ' i (q) and mis{s j (q)|j s {i}} > s ' i (q)]
||
p1 mis{s j (q)|j s {i}}
+
Pr[mis{s j (q)|j s {i}} s ' i (q)]
||
+(

We assume that no supplier knows which category he actually belongs to. However, it should be
clear that if i happen to fall into categories (1) and (3), there is no incentive for him to lie (i.e., to
report a si(q) different from the true cost si(q)) as this will not increase his profit in any way.
The only supplier who may influence the coalition profit (as defined by the two-stage auction
mechanism) is supplier in category (2). We will analyze this (second-lowest price) suppliers
incentive as follows.
First of all, there is no incentive for this supplier to report a higher cost (si(q)> si(q)) since this
will decrease his profit. However, there may be incentive for him to report a lower cost to
increase overall coalition profit (therefore his own share), but he needs to take the risk of the
winners curse, in which case he will have to process the order with price lower than his true
cost. To examine this case further, we introduce the following setting: As defined in the secondprice, seal-bid simultaneous descending auction, stated bids are discrete and in a range, say,
1..m. The coalition has ||=n players. For a category (2) supplier si with cost l+1 (between 1
and m), the expected gain to lower his announced cost with one unit is as follows:
Ei =

1 1 1
l 1 1
(r1 ) [( ) r1 +
l n
l 2 n

n 1

r ( j + 1 n )]
1

j =2

15

(m l) n k 1
n

Here rk = n 1
j

(m l) n j 1
n

j =1

Where rk represents the probability that k members in the coalition has the lowest cost when
supplier i with cost l+1 has the second lowest price. Recall that if there is a tie for the lowest bid
within the coalition, then the players with the lowest bid has equal probability to process the
order, thus the expected production cost is shared evenly. Since supplier si has the second lowest
price in the coalition, the lowest price in the coalition may be any discrete number between 1 and
l, with equal probability (independent to the number of suppliers in the coalition). When k=1 and
min(sj(q)j)< l, supplier i can get 1/n additional units of profit based on the profit sharing
scheme. When min(sj(q)j)=l, supplier i would have 1/(k+1) to process the order and lose
one unit. By simplifying the equation, we have
Ei =

When l

2l n
1
r1
nl
2nl

n 1

r (
j

j =2

n j 1
)
j +1

n
, E i is negative given that r 1 0
2

Thus, the supplier whose cost si(q)=l+1>n/2 satisfy the above condition will always tell the
truth.

We show that for a second lowest price player with cost above a certain threshold value, truth
telling is an optimal response when all other bidders are telling the truth.
If we only consider the cases where k=1 and 2 (r1 and r2) we have
Ei

3(2l n)(m l ) (n 3)(n 2)

r2
3nl

In theory, the coalition may control the amount of decrement in each iteration of the auction to
influence the value of l, thus force the players to tell the truth. If the resulting price from the first
auction is P1 and possible lowest price is Pmin, the coalition could set decrement as 2(P1-Pmin)/n
to guarantee truth revealing. In practice, when n is large enough, the second lowest price supplier
may not reach the threshold value and would have the incentive to lie.

16

For continuous price auction, Guth and Peleg [1996] show that the dominating strategy is for the
player to bid slightly below his true cost. A player can always find a small enough amount and
get more profit, but this may not be relevant from the mechanism design point of view. The
coalition can always adjust the unit decrement such that it is larger than this small amount thus
force the truth telling behavior. The above results verify two important properties for the auction
mechanism with supplier coalitions. In the following, we will evaluate this mechanism against
basic requirements for coalition formation.
4.2 Properties of AMSC
As pointed out earlier, a coalition mechanism includes coalitions generation, and profit
distribution. While we do not address the issue of coalition generation in this paper, the profit
distribution scheme described by AMSC is sufficient to evaluate the basic properties of the
coalition mechanism. In the following, we will verify all the mentioned requirements for AMSC.

Proposition 3. AMSC mechanism is a well-defined mechanism.

E [v ( , q ) ] =

[min {r (q ), s

j (q )

| j mis {s i ( q ) | i } + f ( q ) dq

(8)

Proof. Under mechanism AMSC, the expected profit for a coalition is as follows:
Obviously, v(,q) is independent from other supplier coalition structures, however, it relies on
aggregated market information on second lowest price defined by min{r (q), s j (q ) | j }.
This feature is critical to simplify the coalition generation problem.

Proposition 4. Any coalition under the AMSC mechanism satisfies the Individual Rationality
requirement
Proof. For a supplier si in coalition , he can always get more profit than acting alone in the
market. Because for any q, the profit for one specific member i in is as follows:

[ {

pi ( , q) = pi (q) + min r (q), s j (q) | j mis{s i (q) | i } + / | |

(9)

Where pi(q) is sis profit by acting alone. Define the additional profit for a given coalition as

[ {

d ( , q ) = min r ( q ), s j ( q ) | j mis{s i ( q ) | i } +

(10)

17

Clearly, by acting alone, di({i},q)=0.

The remaining requirements can be stated in the following propositions and can be verified in
words.

Proposition 5. A coalition operates under AMSC require only distributed information that are
observable and controllable.

In AMSC, there is no private information required from the suppliers. All information required
for the mechanism can be obtained from the auctions and therefore observable by the market
maker. As following the coalition rule is incentive compatible (Propositions 1 and 2), while
AMSC satisfies individual rationality (Proposition 4), the behavior of the suppliers is consistent
with the mechanism's intent, because such behavior can lead to the maximal benefit for the
suppliers. Thus, the coalition structure is also controllable, i.e., exclusion from a coalition is a
meaningful punishment, as the player will suffer from less profit.

Proposition 6. Any coalition structure operates under AMSC satisfies Society Welfare

AMSC does not avoid competition among members of the same coalition. Every supplier has the
incentive to decrease cost. Only when a supplier has the lowest cost in the market and when this
price is less than the reserved price of the buyer, can his coalition win the order in phase1 of
AMSC. In the phase2 auction, only the supplier with the lowest cost for this specific order can
win the order. Thus, the supplier with the lowest cost will process any given order, therefore
AMSC satisfies the society welfare requirement.

Proposition 7. Any coalition operates under AMSC is financially-balanced.

It is easy to verify that coalition operates under AMSC is financially balanced. This is because
the coalition only distributes additional profit from the current transaction to its members, thus,
equation (5) is always satisfied. The coalition is balanced not only in a long-run, but also for
each order. A potential benefit from AMSC is that the market maker such as an eCommerce

18

company may potentially profit from the coalition's additional profit. All features of AMSC
mechanism remain, if the eCommerce companies charge, say, one fixed percent of d(,q).

5. Stable Coalition Structure

We verify in the previous section the profit distribution scheme for AMSC satisfy all
requirements for a valid coalition mechanism. A related issue is that of coalition generation, the
formation of the coalition. While we do not address the mechanism involved in coalition
generation, we will establish that AMSC sustains a stable coalition structure. First, consider the
following proposition.

Proposition 8. Under AMSC, the additional profit for the coalition satisfies the additivity
property.
Proof. Given (10), we may write the additional profit for any member in the coalition as
d i ( , q ) = d ( , q) / | |

(11)

For any two coalitions and with = , we have

[ {

d ( , q ) = min r ( q ), s j ( q ) | j mis{s i (q ) | i } +

{ {

and , furthermor e

min r ( q ), s j (q ) | j max min r ( q ), s j (q ) | j , min r ( q ), s j ( q ) | j

mis{si (q ) | i } min{mis{s i ( q ) | i }, mis{si ( q ) | i }}

}}

and

thus, the following additivity property holds:

d ( , q) d ( , q) + d ( , q) for any coalition , where =

(12)

The additivity property seems to imply that all coalitions have the incentive to merge with other
coalitions and eventually lead to a grand collation, i.e., all suppliers in N belong to one coalition.
We will discuss show in the following that the grand coalition is usually not the result under
AMSC. We first need to establish a few results from the collation formation literature.
Definition 2. The set of coalition {i} is a coalition structure if ici=s and i j = for ij,

19

Coalition structure is defined based on the idea of set partitioning. For example, if we have
three players {1,2,3}, the possible coalition will be {1},{2},{3},{1,2},{1,3}, {2,3} and {1,2,3} and
the possible coalition structures will be ({1},{2},{3}), ({1},{2,3}), ({1,2},{3}), ({1,3},{2}) and
({1,2,3}).
Proposition 9. [Sandolhm 1999] The number of coalition structure is O(nn) and (nn/2)
Clearly, to find the optimal coalition structure based on some performance measure is NPhard. Sandolhm [1999] develops several coalition generation heuristics using both the
centralized and distributed viewpoints. If we use xk to represent the current expected additional
profit for supplier k.

Definition 3. A coalition structure c is stable in an n-supplier game if it satisfies the following

condition.
x k max {E[d( i + {k},q)]/| | + 1
E[d( i + {k},q)]/| | + 1 E[d( i ,q)]/| |, i c and k i }

(13)

for any k N

This definition of stable coalition is similar to the notion of Nash Equilibrium. In a stable
coalition, no one can get more profit by just one movement. In other words, no supplier could
gain more profit by joining another coalition that is willing to accept him. Note that this
definition is different from the core of the game. Given the cost structures of all suppliers, there
will be more than one stable coalition structure, so we introduce an additional concept about
stability.

Definition 4 A coalition structure c is strongly stable in an n-supplier game if it satisfies the

following condition.
c, k : E[d ( , q), ] / | | x k

(14 )

If a market reaches the strongly stable coalition structure, no supplier could gain more profits
with any number of movements. Obviously, a strongly stable solution must be a stable solution.

20

This concept is similar to the core discussed earlier. However, the core game only considers the
stability of the grand coalition, but here the strongly stable coalition structure may be any
coalition structure.

If we allow the suppliers to freely make coalitions and all cost structure information is public, we
can state the following.

Proposition 10. Under AMSC there is one unique strongly stable coalition structure.
Proof.
We may construct (in theory) the unique strongly stable coalition structure as follows:
(Assuming all cost structure of the suppliers, order distribution and the reserved price are
known).
Step 0.. Set c= and i=1. Set M as the set of all possible coalition, i.e., M is the set of all subset
of N.
Step 1. Find coalition in M with the highest value of E[d(,q)]/ | | and call this coalition i
Step 2. Set c c i and ii+1
Step 3. Delete from M all coalitions that share the same member of i in M
Step 4. If M, go to step 1. Otherwise, stop.

The coalition structure c resulting from the above procedure is the unique strongly stable
coalition structure in this game. This is true because the coalitions in c would have no incentive
to accept any additional suppliers: members of the coalition with a lower index would not have
the incentive to join the coalitions with higher index. On the other hand, the coalition with a
lower index has no incentive to accept suppliers from the coalition with a higher index. For any
other coalition structure c c, suppliers in the coalition i c with the lowest coalition index i
(which would not have the lowest index in c, by definition) would have the incentive to form a
different coalition identical to i c. Thus, the coalition structure c cannot be a strongly stable
coalition structure.
Since the grant coalition does not necessarily have the highest value of E[d(,q)]/||, the
strongly stable coalition structure under AMSC may not be the grand coalition. This result is
21

important from the viewpoint of market design. A converse result would imply that regardless of
the coalition generation mechanism, the market would gravitate toward one coalition, i.e., no
collation at all. In reality, the cost structure of each supplier is private information not known to
the system. The system is unlikely to reach the strongly stable coalition structure immediately.
In this case, we shall assume that the suppliers are not allowed to switch from one coalition to
another during the auction in order to avoid operational complexity.

6. Conclusions
In this paper, we consider the supplier's coalition problem in buyer-centric procurment auctions.
We specify the requirements for a valid coalition mechanism as individual rationality, private
and distributed information, observability and controllability, society welfare compatibility,
maintaining competition, and financially balancedness. We propose an auction mechanism with
supplier coalitions (AMSC) and we specify a profit distribution scheme under this auction
mechanism. We verify that AMSC satisfies all requirements as a valid coalition mechanism.
Importantly, we show that the proposed profit distribution mechanism provides proper incentive
such that (1) the best strategy for the suppliers in the same coalition is not to complete with one
another (compliance), and (2) bidding the true cost is the best strategy so long as the bids are
uniform distributed and discrete, and the bidders cost is above a certain threshold (incentive
compatibility). We discuss the possibility for the auctioneer to decrease the auction pricing nonuniformly so as to discourage untruthful bidding. For theoretical interest, we show that under
symmetric information, a unique strongly stable coalition structure exists under AMSC.
However, we do not address the issue of coalition generation neither do we discuss the issue of
unique strongly stable coalition structure under asymmetric information. For future study, we
recommend further study of coalition generation mechanisms, and implementable rules that
would force the suppliers to reach a stable coalition structure quickly.

Acknowledgements
This research is supported, in part, by National Science Foundation Grant DMI 0075391 and
DMI 0121395. We are indebt to Professor Robin Roundy at Cornell who provided many

22

valuable suggestions to an earlier version of the paper. We appreciate the comments and
discussions from seminar participants at MIT and Boston University.

References
[1] www.freemarket.com
[2] U.S.

Manufacturing

Companies

Continue

Migration

to

Online

Commerce

AMR Research Report, June 2002.

[3] Anderson, Robert. The Core in Perfectly Competitive Economics, Handbook of Game
Theory with Economic Applications (edited by Robert Aumann and Sergiu Hart), NorthHolland 1992.
[4] Carrie Beam and Arie Segev, Auctions on the Internet: A Field Study, Working Paper 98WP-1032, The Fisher Center for Management and Information Technology, Haas School of
Business, University of California, Berkeley, November 1998.
[5] Cassady, Ralph R. Jr., Auctions and Auctioneering, University of California Press, Berkeley,
CA, 1967.
[6] Gabszewicz, Jean J. and Benyamin Shitovitz. The Core in Imperfectly Competitive
Economies, Handbook of Game Theory with Economic Applications (edited by Robert
Aumann and Sergiu Hart), North-Holland 1992.
[7] Graham, Daniel A., and Robert C. Marshall, Collusive Bidder Behavior at Single-Object,
Second-Price and English Auctions. Journal of Political Economy, 95, p. 1217-1239,
December 1987.
[8] Guth, Werner and Bezalel Peleg. On Ring Formation in Auctions, Mathematical Social
Sciences, 32, p. 1-37, 1996.
[9] Gillies, D. B. Some Theorems on N-Person Games. Ph.D. Dissertation Department of
Mathematics, Princeton University, Princeton, N.J, 1953.
[10] Kannai, Yakar. The Core and the Balancedness, Handbook of Game Theory with Economic
Applications (edited by Robert Aumann and Sergiu Hart), North-Holland 1992.
[11] Klemperer, Paul. Auction Theory: A Guide to the Literature. Journal of Economic Surveys,
13(3), 227-286, July 1999.

23

[12] Mailath, George and Peter Zemsky. Collusion in Second Price Auctions with Heterogeneous
Bidders. Games and Economic Behavior, 3, 467-486, 1991.
[13] McAfee, R. Preston and John McMillan, Bidding Rings, American Economic Review, 82(3),
June p. 579-599, 1992.
[14] McMillan, John. Selling Spectrum Rights. Journal of Economic Perspectives 8(3) p.145162, 1994.
[15] Milgrom, Paul. Game theory and the spectrum auctions. European Economic Review 42,
p.771-778, 1998.
[16] Peleg, Bezalel, Axiomatizations of the Core, Handbook of Game Theory with Economic
Applications (edited by Robert Aumann and Sergiu Hart), North-Holland 1992.
[17] Rasmusen, E., Games and Information, Basil Blackwell, 1989.
[18] Robinson, M., Collusion and the Choice of Auction. Rand Journal of Economics, 16(1),
Spring, p.141-145, 1985.
[19] Sandholm, Tuomas. Limitation of the Vickerey Auction in Computational Multi-Agent
Systems, working paper, Washington University 1996
[20] Sandholm, Tuomas, Kate Larson, Martin Anderson, Onn Shehory, and Fernando Tohme.
Coalition structure generation with worst case guarantees Artificial Intelligence. 111(1), p
209-238, 1999.
[21] Vickrey, W. Counter speculation, auctions and competitive sealed tenders. Journal of
Finance. 16: 8-37,1961.
[22] von Neumann, J. and Morgenstern, O. Theory of games and economic behavior. 2nd
Edition, Princeton University press, 1947.

24