Characterization of Strategy/False-name Proof Combinatorial Auction Protocols: Price-oriented, Rationing-free Protocol

1 Introduction

Internet auctions have become an integral part of Electronic Commerce and a promising field for applying AI technolo­ gies. Among various studies related to Internet auctions, those on combinatorial auctions have lately attracted consid­ erable attention (an extensive survey is presented in [de Vries and Vohra, 2003 ]). Although conventional auctions sell a sin­ gle item at a time, combinatorial auctions sell multiple items with interdependent values simultaneously and allow the bid­ ders to bid on any combination of items. In a combinatorial auction, a bidder can express complementary/substitutable preferences over multiple bids. By taking into account com­ plementary/substitutable preferences, we can increase the participants' utilities and the revenue of the seller.

One important characteristic of an auction protocol is that it is strategy-proof A protocol is strategy-proof if, for each bidder, declaring his/her true evaluation values is a dominant strategy, i.e., an optimal strategy regardless of the actions of other bidders. In theory, the revelation principle states that in the design of an auction protocol, we can restrict our attention to strategy-proof protocols without loss of generality [Myer­ son, 1981]. In other words, if a certain property (e.g., Pareto efficiency) can be achieved using some auction protocol in a dominant-strategy equilibrium, i.e. , a combination of domi­ nant strategies of bidders, the property can also be achieved using a strategy-proof auction protocol.

Furthermore, a strategy-proof protocol is also practically useful for applying to Internet auctions. For example, if we use the first-price sealed-bid auction (which is not strategy­ proof), the bidding prices must be securely concealed until the auction is closed. On the other hand, if we use a strategy­ proof protocol, knowing the bidding prices of other bidders is useless; thus, such security issues become less critical.

Also, the author pointed out the possibility of a new type of fraud called false-name bids, which utilizes the anonymity available in the Internet [Yokoo eta!., forthcoming; 200la; 2000; Sakurai et al., 1999]. False-name bids are bids sub­ mitted under fictitious names, e.g., multiple e-mail addresses. Such a dishonest action is very difficult to detect, since identi­ fying each participant on the Internet is virtually impossible.

We say a protocol is false-name-proof if, for each bidder, declaring his/her true evaluation values using a single iden­ tifier (although the bidder can use multiple identifiers) is a dominant strategy. As for strategy-proof protocols, the reve­ lation principle holds for false-name-proof protocols [Yokoo eta/., forthcoming; 2000]. Thus, we can restrict our attention to false-name-proof protocols without loss of generality.

Given that strategy/false-name proof protocols are impor­ tant both in theory and practice, obvious questions we need to answer are, how can we design such protocols and what features do these protocols have in common, i.e., charac­ terization of the protocols. Although there have been sev­ eral works on characterizing strategy-proof protocols (e.g., [Roberts, 1979; Holmstrom, 1979 ]), as far as the author is aware, there is no work on characterizing false-name-proof protocols.

In this paper, we introduce an innovative characterization of strategy/false-name proof protocols by introducing a new distinctive class of combinatorial auction protocols called price-oriented, rationing-free (PORF) protocols. The outline of a PORF protocol is as follows.

• For each bidder, the price of each bundle of goods is determined independently of his/her own declaration, while it can depend on the declarations of other bidders.
• We allocate each bidder a bundle that maximizes his/her utility independently of the allocations of other bidders (i .e., rationing-free).

A PORF protocol looks quite different from traditional protocol descriptions. In a traditional protocol, the alloca­ tions of goods are usually determined first, and then the pay­ ments of the winners are determined. On the other hand, in a PROF protocol, the prices of bundles for each bidder are determined first, and then the allocation is determined inde­ pendently based on these prices.

However, surprisingly, a PORF protocol captures all the es­ sential features of a strategy-proof protocol, i.e., if a protocol can be described as a PORF protocol, it is strategy-proof, and vice versa. Also, if a protocol can be described as a PORF protocol that satisfies additional conditions, it is false-name­ proof, and vice versa.

As far as the author is aware, a PORF protocol is an in­ novative characterization of strategy-proof protocols and the first attempt to characterize false-name-proof protocols. Such a characterization is not only theoretically significant but also useful in practice, since it can serve as a guideline for devel­ oping new strategy/false-name proof protocols. We present a new false-name-proof protocol based on the idea of a PORF protocol.

2 Problem Settings

Assume there are a set of bidders N = { 1, 2, ... , n} and a set of goods M = { 1, 2, ... , m}. Each bidder i has his/her preferences over B ~ M. Formally, we model this by sup­ posing that bidder i privately observes a parameter, or signal, 8;, which determines his/her preferences. We refer to B i as the type of bidder i . We assume B; is is drawn from a set 8. We assume a quasi-linear, private value model with no a/locative externality, defined as follows.

Definition 1 (utility of a bidder)

The utility of bidder i, when i obtains a bundle, i.e., a subset of goods B ~ M and pays PB,i· is represented as v(B, B;)­ PB, i·

We assume evaluation value vis normalized by v(0, B;) = 0. Also, we assume for all i, B, v(B, B;) ::; oo holds. Further­ more, we assume free disposal, i.e. , v(B', B;) ~ v(B, B;) for all B';;:? B.

In a traditional definition [Mas-Colell eta/., 1995], an auc­ tion protocol is (dominant-strategy) incentive compatible (or strategy-proof) if declaring the true type/evaluation values is a dominant strategy for each bidder, i.e., an optimal strategy regardless of the actions of other bidders.

In this paper, we extend the traditional definition of incen­ tive compatibility so that it can address false-name bid manip­ ulations, i.e., we define that an auction protocol is (dominant­ strategy) incentive compatible if declaring the true type by using a single identifier is a dominant strategy for each bid­ der. To distinguish between the traditional and extended def­ initions of incentive compatibility, we refer to the traditional definition as strategy-proof and to the extended definition as false-name-proof An auction protocol is individually rational if no partici­ pant suffers any loss in a dominant-strategy equilibrium, i.e., the payment never exceeds the evaluation value of the ob­ tained goods. In a private value auction, individual rationality is indispensable; no bidder wants to participate in an auction where he/she might be charged more money than he/she is willing to pay. Therefore, in this paper, we restrict our atten­ tion to individually rational protocols. Also, we restrict our attention to deterministic protocols, which always obtain the same outcome for the same input.

We say an auction protocol is Pareto efficient when the sum of all participants' utilities (including that of the auctioneer), i.e., the social surplus, is maximized in a dominant-strategy equilibrium. The author has proved that there exists no false­ name-proof protocol that satisfies Pareto efficiency and indi­ vidual rationality at the same time [Yokoo eta/., forthcoming; Sakurai et a/., 1999]. Therefore, we need to sacrifice effi­ ciency to some extent when false-name bids are possible.

3 Price-oriented, Rationing-Free (PORF) Protocol

A PORF Protocol is defined as follows.

Definition 2 (PORF Protocol)

• Each bidder i declares his/her type B;, which is not nec­ essarily the true type B;.
• For each bidder i, for each bundle B ~ M, the price PB,i is defined. This price must be determined indepen­ dently of i 's declared type B;, while it can be dependent on declared types of other bidders.
• We assume P0,i = 0 holds. Also, if B ~ B', PB,i < PB',i holds.
• For bidder i, a bundle B* is allocated, where B* argmaxB~M v(B, B;)- PB,i· Bidder i pays PB·,i· If there exist multiple bundles that maximize i 's utility, one of these bundles is allocated.
• The result of the allocation satisfies allocation­ feasibility, i.e., for two bidders i, j and bundles allo­ cated to these bidders B'[ and Bj. B'[ n Bj = 0 holds.

It is straightforward to show that a PORF protocol is strategy­ proof. The price of bidder i is determined independently of i's declared type, and he/she can obtain the bundle that maxi­ mizes his/her utility independently of the allocations of other bidders, i.e., the protocol is rationing-free.

On the other hand, in a PORF protocol, the prices must be determined appropriately to satisfy allocation-feasibility 1 ·

1 Since the price for each bidder can be different and the price of a bundle is not necessarily the sum of the prices of all goods in the bundle, there is no direct relation between the prices that achieve allocation-feasibility and equilibrium prices.

The definition of a PORF protocol requires that if there exist multiple bundles that maximize i's utility, then one of these bundles must be allocated, but it does not specify exactly which bundle should be allocated. Therefore, if there exist multiple choices, the auctioneer can adjust the allocation of multiple bidders in order to satisfy allocation-feasibility.

Next, we provide some examples of PORF protocols. Since a PORF protocol is strategy-proof, in the rest of this paper, we assume each bidder i declares his/her true type 8; .

Example 1 Let us consider the auction of a single unit of a single item.

• The price of the only bundle B = M is defined asp B ,i = max#; v(B, 8j) .

This protocol is identical to the Vickrey auction protocol [Vickrey, 196I].

More specifically, for the bidder with the highest evalua­ tion value, the price of the good is equal to the second highest evaluation value. On the other hand, for other bidders, the price is equal to the highest evaluation value, so nobody ex­ cept the bidder with the highest evaluation value is willing to buy the good.

Example 2 Let us consider a combinatorial auction. To sim­ plify the protocol description, we introduce the following no­ tation. For a set of goods B and a set of bidders X , where 8x is a set of types of bidders in X, we define V *(B, 8x) as the sum of the evaluation values of X when B is allocated optimally among X .

To be precise, for an feasible allocation g = ( B 1 , B2 , . .. ), where UiEX Bj ~ B and for all j =f. j', Bj n Bi' = 0, V*(X, B) is defined as max 9 LjEX v(Bj, 8i), where 8i is the type of bidder j .

The price of bundle B for bidder i is defined as follows:

This protocol is identical to the Vickrey-Clarke-Groves (VCG) mechanism [Vickrey, I96I; Clarke, 1971; Groves, I973], i.e., if B is allocated to i in a Pareto efficient alloca­ tion, then p B ,i is equal to the payment in the VCG; otherwise, PB ,i is larger than v(B, 8;).

Let us describe how this protocol works. Assume there are two goods 1 and 2, and three bidders, bidder I, 2, and 3, whose types are 81 , 82, and 83, respectively. The evaluation value for a bundle v(B, 8;) is determined as follows.

Accordingly, the prices of these bundles for each bidder is given as follows.

As a result, bidder 1 obtains good I with price 3, and bidder 3 obtains good 2 with price 2.

4 Strategy-proof --t PORF

A PORF protocol looks quite different from traditional proto­ col descriptions, in which the allocation of the goods/winners are determined, and then the payments of these winners are determined. In a PROF protocol, the prices of bundles for each bidder is determined first, and then the allocation is determined based on these prices. In a traditional protocol description, the payment of bidder i must be determined in­ dependently of i's type to make the protocol strategy-proof. This is similar to the fact that the price of bidder i in a PORF protocol must be determined independently of i 's declared type. The most distinctive characteristic of a PORF protocol is that it is rationing-free, i.e., each bidder can obtain the op­ timal bundle based on the prices, and the allocation for each bidder is done independently (except when a bidder is totally indifferent between multiple bundles).

Surprisingly, a PORF protocol is not only a sufficient con­ dition that a protocol is strategy-proof, but it is also a neces­ sary condition, i.e., the following theorem holds.

Theorem 1 If a protocol is strategy-proof, then the protocol can be described as a PORF protocol.

The argument presented in this section is very general and requires only the fact that a protocol is deterministic and in­ dividually rational.

The outline of the proof in the remainder of this section can be summarized as follows. First, we show that if a bidder is single-minded (Definition 3), i.e., he/she is interested only in a particular bundle, any strategy-proof protocol can be de­ scribed as a PORF protocol (Lemma 3), i.e., the price of the bundle is determined and the bidder will obtain the bundle if his/her evaluation value is larger than the price. An intuitive explanation for this result is that if such a price does not exist, a single-minded bidder can have an incentive to under/over­ declare his/her evaluation value for the bundle. The only way to make the protocol strategy-proof is to set a fixed threshold based on other bidders' evaluation values, which determines whether the single-minded bidder will obtain the bundle or not.

Next, we show that this result can be extended to the case where a bidder is k-minded (Definition 5), i.e., a bidder is in­ terested in multiple bundles at the same time (Lemma 5). An intuitive explanation for this result is as follows. A single­ minded bidder can pretend to be a k-minded bidder, and vice versa. Therefore, to a k-minded bidder, the protocol must give the results that are basically equivalent to a single­ minded bidder

Any bidder can be represented as a (2m- 1)-minded bid­ der, where m is the number of goods and 2m -1 is the number of all possible bundles (except an empty set). Thus, we can show that any strategy-proof protocol can be represented as a PROF protocol.

In the following, we show the detailed proof of Theorem I. To derive the theorem, we introduce notions such as single­ minded bidder, monotone allocation rule, and critical-value, which are used in [Lehmann et al., 2002; Mu'alem and Nisan,

2002]. The proofs of Lemma 1 and 2 are basically due to [Lehmann eta!., 2002; Mu'alem and Nisan, 2002].

Definition 3 (single-minded bidder)

We say bidder i is single-minded if i requires only one bundle Bi. i.e., for any bundle B, if Bi ~ B, then v(B, Bi) = Vi. otherwise, v(B, Bi) = 0.

If bidder i is single-minded, i.e., the declared type of i can be considered to be single-minded, then a PORF protocol can be described as follows, assuming the set of other bidders and their types are fixed. We denote this protocol as a PORF protocol for a single-minded bidder.

• For bidder i, Pi, which is the price of Bi, is defined. If v( Bi, Bi) > Pi, then Bi (or a superset of Bi) is allocated to bidder i and i pays Pi· If v(Bi, Bi) < Pi, then no good is allocated. If v ( B i, Bi) = Pi, then either Bi (or a superset of Bi) is allocated and i pays Pi, or no good is allocated.

Definition 4 (monotone allocation rule)

We say a protocol is monotone for a single-minded bidder i if the following condition is satisfied, assuming the set of other bidders and their types are fixed.

If bundle Bi (or a superset of Bi) is allocated to bidder i when i 's evaluation value for Bi is Vi, then Bi (or a superset of Bi) is also allocated when i 's evaluation value for B i is v~ >Vi.

The following lemma holds.

Lemma 1 If a protocol is strategy-proof, then the protocol is monotone for a single-minded bidder.

Proof: If a protocol is not monotone, there exists a case where Bi (or a superset) is allocated to bidder i when i's eval­ uation value for Bi is Vi, while Bi (or a superset) is not allo­ cated to bidder i when i's evaluation value for Bi is v~ >Vi· Since the protocol is individually rational, the payment when i's evaluation value is vi must be less than or equal to Vi. Therefore, when i's true evaluation value is v~, ifi truthfully declares his/her type, i's utility is 0, since neither Bi nor a superset is allocated. However, if i declares a false type as a single-minded bidder where the evaluation value forB i is Vi, i can obtain a positive utility. This contradicts the assumption that the protocol is strategy-proof. D

Furthermore, the following lemma holds.

Lemma 2 If a protocol is monotone for a single-minded bid­ der, then there exists critical-value c that satisfies the follow­ ing condition, assuming the set of other bidders and their types are fixed: if Vi > c, Bi (or a superset) is allocated to i, while if Vi < c, no good is allocated.

Proof: Let us assume that no critical value exists. Then, for an arbitrary value c', either one of the following two cases holds.

case i: there exists v' > c', where bidder i cannot obtain Bi when i's evaluation value is v'.

case ii: there exists v" < c', where bidder i can obtain Bi when i 's evaluation value is v".

If we set c' = 0, case ii cannot be true so case i must hold. Let us re-assign c' as v' and repeat this procedure until case ii occurs (if case ii never occurs, then oo becomes a critical value). In this case, bidder i cannot obtain Bi when the eval­ uation value is c', while i can obtain Bi when the evaluation value is v" < c'. This contradicts the assumption that the protocol is monotone. D

Next, we show that the following lemma holds.

Lemma 3 If a protocol is strategy-proof, then, for a single­ minded bidder, the protocol can be described as a PORF pro­ tocol for a single-minded bidder, i.e., if i 's evaluation value for Bi is larger than a given value Pi· then Bi (or a superset) is allocated and i 's payment is Pi· If i 's evaluation value for Bi is smaller than Pi· no good is allocated.

Proof: From Lemma 1 and 2, the protocol is monotone and there exists critical-value c, i.e., Bi (or a superset) is allocated when the evaluation value is larger than c, while no good is allocated when the evaluation value is smaller than c. The only thing we need to show is that the payment is equal to c when Bi (or a superset) is allocated. Let us assume that the payment is c' =/= c and derive a contradiction.

First, let us consider the case c' < c, i.e., when the evalua­ tion value of i is Vi > c, i obtains Bi (or a superset) but the payment is c' < c. When the evaluation value of i is c' + €, if i declares the true type, no good is allocated and the ob­ tained utility is 0, while if i declares a false type where the evaluation value is Vi, i can obtain Bi (or a superset) and the payment is c', thus the obtained utility becomes positive. This contradicts the assumption that the protocol is strategy-proof.

Next, let us consider the case c' > c, i.e., when the evalu­ ation value of i is Vi > c, i obtains Bi (or a superset) but the payment is c' > c. If i declares a false type where the evalu­ ation value is c + €, i can obtain Bi (or a superset) because c is a critical value. Since the protocol is individually rational, the payment must be less than or equal to c + €, which is less than c', i.e., the payment when i declares the true type. This contradicts the assumption that the protocol is strategy-proof.

From the above, the protocol can be described as a PORF protocol for a single-minded bidder where pi = c. D

Definition 5 (k-minded bidder)

We say bidder i is a k-minded bidder if i requires exactly one bundle from k bundles Bi,, ... , Bi 3 , ··· , Bik. Let us repre­ sent i 's evaluation value for Bi 3 as vi 3 . For notation simplic­ ity, let us assume Bio = 0 and Vio = 0. The evaluation value of i for bundle B is defined as follows.

v(B, B;) = maxo~j:5k v; 3 , where B; 3 ~B.

From Lemma 3, if bidder i is a single-minded bidder who requires only Bi 3 , then a strategy-proof protocol must be a PORF protocol for a single-minded bidder. Let us represent the price for bidder i of B; 3 in this protocol as Pi 3 ·

First, we show that the following lemma holds.

Lemma 4 If a protocol is strategy-proof, then, for k-minded bidder i, the payment when i obtains B is given by PB,i = maxo::;j::;kPi 3 · where B; 3 ~B.

Proof: Let us assume that j' = arg maxo::;j::;k Pi 3 where B; 3 ~ B. We derive a contradiction assuming p B, i =/= p; 3 , · First, let us consider the case p B,i < p;J'. Assume that i is a single-minded bidder who requires B i , only, and i 's evalua-' tion value for Bi , is Pi , . In this case, if i declares the true J J type, the obtained utility is 0. On the other hand, if i declares his/her type as a k-minded bidder, i can obtain B ;;;! B ij' and the payment is PB,i < Pij" thus i can obtain a positive utility. This contradicts the assumption that the protocol is strategy-proof.

Next, let us consider the case p B,i > Pij'. If i declares its type as a single-minded bidder who requires only B i , , i J can obtain Bi 1 (or a superset) and the payment is Pi I, which J J is less than PB,i, i.e., the payment when he/she declares the true type. This contradicts the assumption that the protocol is strategy-proof. 0

Finally, we show that the following lemma holds.

Lemma 5 If a protocol is strategy-proof, then, for a k­ minded bidder i, the protocol can be described as a PORF protocol for a k-minded bidder, i.e.,for each Bij' Pij· which is the price for bidder i, is defined, and the protocol assigns Bij· (or a superset), where j* = argmaxo~j~k(Vij - Pij). The payment is Pij·.

Proof: We derive a contradiction assuming that a strategy­ proof protocol assigns B ~ Bij· fork-minded bidder i. Let us choose j" = arg maxo~j~k Vij, where Bij ~ B. From the definition of a k-minded bidder, v(B, Bi) = Vi .11 holds. J Furthermore, from the fact that B ~ Bij·, Vi;- - Pij· > vi II - Pi · II holds. J J

From Lemma 4, the payment when i obtains B is given by PB,i = maxo~j~kPij' where Bij ~B. Obviously, PB,i 2': Pijll holds. Thus, vij· - Pij· > vij11 - Pijll 2': v(B, Bi)- PB,i holds. This formula represents the fact that the utility when i declares the true type (i.e., v(B, Bi) - PB,i) is less than the utility when i declares a false type, where i is a single-minded bidder that requires only Bi · (i.e., vi · -Pi · ). This contrad. h · ' 1' ' 1cts t e assumptiOn that the protoco is strategy-proof. 0

Any bidder can be represented as a (2m- 1)-minded bid­ der, where m is the number of goods and 2m -1 is the number of all possible bundles (except an empty set). Since Lemma 5 holds for all k, from Lemma 5, we can derive Theorem 1.

5 PORF with additional conditions t-t False-name-proof

From the definition, if a protocol is false-name-proof, it is also strategy-proof. Therefore, it is obvious that false-name­ proof --> PORF holds. On the other hand, PORF --> false­ name-proof does not hold in general. For example, the VCG mechanism is strategy-proof, so it can be described as a PORF protocol, but it is not false-name-proof, as shown in [Yokoo eta/., forthcoming; Sakurai eta/., 1999 ].

In this section, we limit our attention to protocols that sat­ isfy the following condition.

Definition 6 (weakly-anonymous pricing rule (WAP))

For bidder i, the price of bundle B is given as a function of types of other bidders, i.e., the price can be described as p(B, Gx ), where X is the set of bidders except i, and 8 xis the set of types of bidders in X.

The above condition requires that iftwo bidders are facing the same types of opponents, their prices must be identical for all bundles. The WAP condition is intuitively natural and virtu­ ally all well-known protocols, including the VCG, satisfy this condition.

For a PORF protocol that satisfies the WAP condition, we define the following additional condition.

Definition 7 (no super-additive price increase (NSA))

For all subset of bidders S ~ N and X = N \ S, and for i E S, let us denote Bi as a bundle that maximizes i 's utility, then 'L,iES p(Bi, UjES\ {i} { Bj} U 8 x) 2': p(UiES Bi , 8 x ).

An intuitive meaning of this condition is that the price of buy­ ing a combination of bundles (the right side of the inequality) must be smaller than or equal to the sum of the prices for buying these bundles separately (the left side).

The next theorem states that for a PORF protocol with the WAP, the NSA is a sufficient condition for a protocol to be false-name-proof.

Theorem 2 If a PORF protocol with the WAP satisfies the NSA condition, then the protocol is false-name-proof

Proof: The proof is rather clear. If a bidder uses a set of identifiers S, then from the NSA condition, the bidder can obtain the same set of goods by using a single identifier, while the payment becomes smaller (or remains the same). 0

We can show that for a PORF protocol with WAP, the NSA is not only a sufficient condition but also a necessary condi­ tion, i.e., the following theorem holds.

Theorem 3 If a protocol is a PORF protocol with the WAP and is false-name-proof, then it satisfies the NSA condition.

Proof: Let us assume that there exists a false-name-proof protocol that can be described as a PORF protocol with the WAP but does not satisfy the NSA condition. More pre­ cisely, for a set of identifiers S, X = N \ S, and for i E S, Bi is the bundle that maximizes i's utility, but 'L,iES p(Bi, UjES\{i} { Bj} U 8 X) < P(UiES Bi, 8 X).

Let us assume the case where bidder i' is facing oppo­ nents whose types are ex. Also, let us assume bidder i' is single-minded for bundle uiES Bi, and the evaluation value is P(UiES Bi, 8 x ). If bidder i' declares his/her true type, the obtained utility is 0 (since if i' can obtain the bundle, the payment is equal to his/her evaluation value). On the other hand, if i' uses a set of identifiers S, and for each i E S, he/she declares the type as ei, then for each identifier i, Bi is obtained.

The sum of the payment is L,iESp(Bi,UjES\{i}{Bj} U Gx), which is less than the evaluation value of i', i.e., p(UiES Bi, 8 x). Thus, bidder i' can obtain positive utility by utilizing false-name bids. This contradicts the assumption that the protocol is false-name-proof. 0

For the protocols that are strategy-proof (SP), false-name­ proof (FP), PORF, WAP, and NSA, the subset/superset rela­ tions can be illustrated as Figure 1. The VCG mechanism can be described as a PORF protocol with WAP, but it does not satisfy the NSA condition. Therefore, it is not false-name­ proof. One example of a false-name-proof protocol that does not use the WAP rule is a dictatorial protocol where all goods are allocated to one special bidder (the dictator) regardless of other bidders' evaluation values.

Due to space limitations, we omit detailed descriptions, but all existing false-name-proof protocols developed so far, e.g., the LDS [Yokoo et al., 2001a], theIR [Yokoo et at., 2001b], and the GAL protocol [Terada and Yokoo, 2003 ], can be de­ scribed as a PORF protocol that satisfies the NSA condition.

6 New False-name-proof Protocol

In this section, we develop a new false-name-proof protocol based on the concept of the PORF protocol. To simplify the protocol description, we introduce a concept called a minimal bundle.

Definition 8 (minimal bundle) Bundle B is called minimal for bidder i if for all B' C B and B' =1- B. v( B', ()i) < v(B, ()i ) holds.

In this new protocol, the price of bundle B for bidder i is defined as follows :

• PB,i = maxs 1 c;,M,#iv(Bj,()j), whereBnBj =1- 0and B1 is minimal for bidder j.

In short, the price of bundle B is equal to the highest evalua­ tion value of a bundle, which is minimal and conflicting with bundle B.

Compared with the LDS protocol [Yokoo eta!., 2001a], this protocol is much simpler and does not require any pa­ rameters to be set by the auctioneer, while in the LDS proto­ col, the auctioneer must carefully determine the reservation price and the way of dividing goods into multiple bundles. If all bidders are single-minded, this protocol is one example of greedy protocols described in [Lehmann et at., 2002].

Let us describe how this protocol works. Let us assume there are three goods 1, 2, and 3, and two bidders, bidder 1 and bidder 2, whose types are () 1 , B2, respectively. The evalu­ ation value for a bundle v(B, ()i) is determined as follows.

These evaluation values mean that bidder 1 is 2-rninded for bundles { 1, 2} and { 3}, while bidder 2 is 2-minded for bun­ dles { 2} and { 3}. These bundles are minimal bundles. The prices of these bundles are given as follows.

As a result, bundle { 1, 2} is allocated to bidder 1 and bundle {3} is allocated to bidder 2.

It is clear that this protocol satisfies the allocation­ feasibility. For each good l, let us choose bidder j * and bun­ dle B* that maximize v(B1, Bj), where l E Bj and Bj is mininial for bidder j. Then, only bidder j * is willing to ob­ tain a bundle that contains good l. For all other bidders, the price of a bundle that contains l is higher than (or equal to) his/her evaluation value.

Furthermore, it is clear that this protocol satisfies the NSA condition. In this pricing scheme, p(B U B',8x) = max(p(B,8x),p(B',8x)) holds for all B,B', and 8x. Therefore, the following formula holds.

Furthermore, in this pricing scheme, prices increase mono­ tonically by adding opponents, i.e., for all X' ;:2 X, p( B' eX') ~ p( B' eX) holds. Therefore, for each i, p(Bi, UjES\{i} {Bj} U 8x) ~ p(Bi, 8x) holds. Therefore, the NSA condition, i.e., LiESp(Bi, ujES\{i} {Bj} u 8x) ~ p(UiES Bi , 8x) holds.

7 Discussions

As far as the author is aware, a PORF protocol is an innova­ tive characterization of strategy-proof protocols and the first attempt to characterize false-name-proof protocols. Here, we discuss several previous works on characterizing strategy­ proof protocols.

In [Lehrnarm eta/., 2002; Mu'alem and Nisan, 2002], it is shown that if there exist only single-minded bidders, a strategy-proof protocol is monotonic and has a critical value. Since their motivation is to develop computationally efficient strategy-proof protocols that can achieve semi-optimal allo­ cations, they do not extend their results to more general cases such as k-minded bidders.

In [Roberts, 1979], a characterization of strategy-proof mechanisms is shown for general social choice problems. It is shown that any strategy-proof protocol can be described as a variation of the Groves mechanisms [Groves, 1973]. On the other hand, in the model used in this paper, we assume that the evaluation values of each bidder satisfy no allocative­ extemality condition. Therefore, the results described in [Roberts, 1979] cannot be applied, i.e., a PORF protocol is not necessarily to be a variation of the Groves mechanisms.

In [Holmstrom, 1979], a characterization of strategy-proof mechanisms is described. It is shown that with the assump­ tion that the preferences of each participant satisfy a condition called smoothly-connected, any strategy-proof protocol that satisfies Pareto efficiency must be an instance of the Groves mechanisms. This result can be applied to the model used in this paper since the smoothly-connected condition still holds. Therefore, if we require that a protocol be Pareto efficient, it is likely that the pricing scheme described in Example 2 is the only way to make a PORF protocol Pareto efficient 2 ·

As well as a PORF protocol is theoretically significant, since it is an equivalent class of strategy-proof protocols, it has practical importance since it can serve as a guideline for developing new strategy/false-name proof protocols. Design­ ing a strategy/false-name proof protocol has been a difficult task. As shown in Section 6, we successfully developed a new false-name-proof protocol based on the idea of a PORF protocol. The simplicity of this newly developed protocol compared with the LOS protocol illustrates the expressive power of a PORF protocol. Of course, we need to prove that a PORF protocol satisfies allocation-feasibility. However, this tends to be much easier than directly proving a protocol is strategy/false-name proof, since we can assume each bidder declares his/her true type by using a single identifier.

As for the computational cost of executing a protocol, a naive implementation of a PORF protocol requires calculat­ ing prices for all bundles of all bidders. However, as in the case of the VCG, we can describe a protocol either as a PORF protocol or in a traditional manner in which an allocation of goods is determined, and then the payments are calculated based on the allocation. We can assume that the description of a PORF protocol is not for actual implementation but for serving as a normative guideline in proving characteristics of a protocol.

8 Conclusions

In this paper, we introduced a new distinctive class of combi­ natorial auction protocols called PORF protocols. Although a PORF protocol looks quite different from traditional proto­ col descriptions, surprisingly, it is a sufficient and necessary condition for a protocol to be strategy-proof. Furthermore, we showed that a PORF protocol satisfying additional conditions is false-name-proof; at the same time, any false-name-proof protocol can be described as a PORF protocol that satisfies the additional conditions.

A PORF protocol is not only theoretically significant but also useful in practice, since it can serve as a guideline for developing new strategy/false-name proof protocols. We suc­ cessfully developed a new false-name-proof protocol based on the idea of a PORF protocol. We are currently extending the obtained results to combinatorial exchange.

Acknowledgements

The author wishes to thank Yoshikatsu Tatamitani, Kenji Ter­ ada, Yuko Sakurai, Atsushi Iwasaki, and Shigeo Matsubara for their helpful discussions.