Robust Multi-unit Auction Protocol against False-name Bids

1 Introduction

Internet auctions have become an especially popular part of Electronic Commerce (EC). The Internet provides an excellent infrastructure for executing much cheaper auctions with many more sellers and buyers from all over the world. However, in [Sakurai et al., 1999], the authors pointed out the possibility of a new type of cheating called false-name bids, i.e., an agent may try to profit from submitting false bids made under fictitious names, e.g., multiple e-mail addresses. Such a dishonest action is very difficult to detect since identifying each participant on the Internet is virtually impossible. Compared with collusion [Rasmusen, 1994; Varian, 1995], a false-name bid is easier to execute since it can be done by someone acting alone, while a bidder has to seek out and persuade other bidders to join in collusion.

Auctions can be classified into three types by the number of items/units auctioned: (i) single item, single unit, (ii) single item, multiple units, and (iii) multiple items. In [Sakurai et al., 1999; Yokoo et al., 2000a], we analyzed the effects of false-name bids on auction protocols. The obtained results can be summarized as follows.

• For multi-unit auctions, where the demand of a participant can be multiple units, or for combinatorial auctions of multiple items, the generalized Vickrey auction protocol (GVA) [Varian, 1995] is not robust against falsename bids.
• There exists no auction protocol that simultaneously satisfies incentive compatibility, Pareto efficiency, and individual rationality for all cases in the above situations if agents can submit false-name bids.

In this paper, we concentrate on private value auctions [Mas-Colell et al., 1995]. In private value auctions, each agent knows its own evaluation values of goods, which are independent of the other agents' evaluation values. We define an agent's utility as the difference between the true evaluation value of the allocated goods and the payment for the allocated goods. Such a utility is called a quasi-linear utility [Mas-Colell et al., 1995]. These assumptions are commonly used for making theoretical analyses tractable.

In a traditional definition [Mas-Colell et al., 1995], an auction protocol is (dominant strategy) incentive compatible, if bidding the true private values of goods is the dominant strategy for each agent, i.e., the optimal strategy regardless of the actions of other agents. The revelation principle states that in the design of an auction protocol we can restrict our attention to incentive compatible protocols without loss of generality [Mas-Colell et al., 1995; Yokoo et al., 2000a]. 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., the combination of dominant strategies of agents, the property can also be achieved using an incentive compatible auction protocol.

In this paper, we extend the traditional definition of incentive-compatibility so that it can address false-name bid manipulations, i.e., we define that an auction protocol is (dominant strategy) incentive compatible, if bidding the true private values of goods by using the true identifier is the dominant strategy for each agent. Also, we say that auction protocols are robust against false-name bids if each agent cannot obtain additional profit by submitting false-name bids. If such robustness is not satisfied, the auction protocol lacks incentive compatibility.

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. In a more general setting, Pareto efficiency does not necessarily mean maximizing the social surplus. In an auction setting, however, agents can transfer money among themselves, and the utility of each agent is quasi-linear; thus the sum of the utilities is always maximized in a Pareto efficient allocation.

An auction protocol is individually rational if no participant suffers any loss in a dominant strategy equilibrium, i.e., the payment never exceeds the evaluation value of the obtained goods. In a private value auction, individual rationality is indispensable; no agent wants to participate in an auction where it might be charged more money than it is willing to pay.

In this paper, we concentrate on multi-unit auctions, in which multiple units of an identical item are sold. Multi-unit auctions have practical importance and are widely executed already in current Internet auction sites such as eBay, Yahoo!. In current Internet auctions, a participant is assumed to want only one unit of an item. By allowing a participant to bid on multiple units, e.g., he/she needs two units of the item at the same time, as in combinatorial auctions [Sandholm, 1999; Fujishima et al., 1999; Lehmann et al., 1999], we can increase both the utility of the participants and the revenue of the seller.

The GVA protocol [Varian, 1995] is one instance of the well-known Clarke mechanism [Mas-Colell et al., 1995]. It satisfies incentive compatibility, Pareto efficiency, and individual rationality in multi-unit auctions when there exists no false-name bid; however, this protocol is not robust against false-name bids [Sakurai et al., 1999].

If the marginal utility of a unit always decreases for all agents, the GVA is robust against false-name bids [Sakurai et al., 1999]. The marginal utility of an itemmeans an increase in the agent's utility as a result of obtaining one additional unit. If the number of units becomes very large, the marginal utility of a unit tends to decrease. For example, if we already have one million units of an item, the utility of having additional one unit would be close to zero. On the other hand, if the number of units are relatively small, which is common in many auction settings, we cannot assume that the marginal utility of each agent always decreases. A typical example where the marginal utility increases is an all-or-nothing case, where an agent needs a certain number of units, otherwise the good is useless (e.g., airplane tickets for a family trip).

In [Yokoo et al., 2000b], we developed a combinatorial auction protocol called the Leveled Division Set (LDS) protocol. This protocol satisfies incentive compatibility and individual rationality even if agents can submit false-name bids. We can modify the LDS protocol so that it can handle multiunit auctions. As far as the authors know, this is the only existing non-trivial multi-unit auction protocol that is robust against false-name bids. However, this protocol is complicated and requires the auctioneer to carefully pre-determine the combination of bundles in order to obtain a high social surplus or revenue.

In this paper, we develop a new multi-unit auction protocol that satisfies incentive compatibility and individual rationality. We call this protocol the Iterative Reducing (IR) protocol. In this protocol, the combination of bundles is automatically determined in a flexible manner according to the declared evaluation values of agents.

In the following, we first show how the LDS protocol can be modified to handle multi-unit auctions. Then, we describe the details of the IR protocol and prove that it satisfies incentive compatibility. Furthermore, we compare the obtained social surplus of the IR protocol with that of the LDS protocol.

2 Leveled Division Set Protocol

We show how the LDS protocol can be modified for multiunit auctions. In the following, we define several terms and notations. To help readability, we use two different types of parentheses to represent sets: {} and [].

• A set of agents: {1, 2, . . .,N}
• The number of units of an item: M
• A declared evaluation value of agent i for j units of an item: bi↪j (which may or may not be true).
• An auctioneer determines a reservation (minimal) price r for one unit of an item.
• A reservation price of a bundle of j units is r × j.
• A division D is defined as a set of bundles {m1,m2, . . .}, where ∑l ml ≤ M. For example, a division {8, 2} means that the auctioneer is going to sell a bundle of 8 units and a bundle of 2 units.

Also, an auctioneer determines a leveled division set. Figure 1 shows examples of leveled division sets. Case 1 shows one instance where there exist three units of an item, and cases 2 and 3 show instances where there exist ten units of an item. A leveled division set is defined as follows.

• Levels are defined as 1, 2, . . .,max level.
• For each level k, a division set SDk = [Dk1,Dk2, . . .] is defined so that the sum of multiple bundles that appear in a division must appear in an earlier level. For example, In case 2 of Figure 1, there is a division {1,1,1,1,1,1,1,1,1,1} in level 3. Therefore, the sum of the multiple bundles of this division, i.e., 2, 3, . . ., or 10, appears in earlier levels.

To execute the LDS protocol, the auctioneer must predefine the leveled division set and the reservation price of one unit r. Each agent i declares bi↪j for all 1 ≤ j ≤ M. The winners and payments are determined by calling the procedure LDS(1). LDS(k) is a recursive procedure defined as follows.

Procedure LDS(k)

• Step 1: If there exists only one agent i whose evaluation value of a bundle of j units satisfies bi↪j ≥ r × j,

and j is included in an element of SDk, then compare the results obtained by the procedure GVA(k) and by LDS(k + 1), and choose the one that gives the larger utility for agent i.

• Step 2: If there exist at least two agents i, i′ whose evaluation values bi↪j, bi′↪j ′ of bundles of j and j ′ units satisfy bi↪j ≥ r × j and bi′ ↪j ′ ≥ r × j′ , and j, j ′ are included in elements of SDk , then apply the procedure GVA(k).
• Step 3: Otherwise: call LDS(k + 1), or terminate if k = max level.

Procedure GVA(k): For a divisionD = {m1,m2, . . .} and one possible allocation of units G, we say G is allowed under D if each bundle in D is allocated to different agents in G. Also, we allow that some bundles are not allocated to any agent. In that case, we assume that the bundles are allocated to the auctioneer (denoted by 0), whose evaluation value for a bundle of j units is equal to r × j. The declared evaluation value of agent i for an allocation G (represented as ei(G)) is defined as bi↪j , if j units are allocated to agent i in G, otherwise ei(G) = 0. Choose an allocation G∗ such that it is allowed under the divisions in SDk and it maximizes ∑x∈{0↪1↪▷▷▷↪N} ex(G). The payment of agent i (represented as pi) is calculated as ∑x̸=i ex(G∗∼i ) - ∑x̸=i ex(G∗ ), where G∗∼i is the allocation that is allowed under the divisions in SDk and maximizes the sum of all agents' (including the auctioneer 0) evaluation values except that of agent i. This procedure is basically identical to the GVA.

In this case, the evaluation values of agent 1,2, and 3 are allor-nothing, i.e., they need three units at once. Other agents need only one unit, and agents 7, 8, . . ., 13 have identical evaluation values. Also, let us assume the reservation price for one unit is 10 and the leveled division set is defined as case 3 in Figure 1. Since there exists no evaluation value that is larger than the reservation price in levels 1 and 2, units are sold using the level 3 division. As a result, each of the agents 1,2, and 3 obtains a bundle of three units, and each pays the reservation price 30.

The intuitive explanation that the LDS protocol is robust against false-name bids is as follows. Let us assume that an agent uses two identifiers, and obtains one unit by each identifier in the level 5 of case 3. If this agent uses a single identifier, it can obtain a bundle of two units in the level 4 by paying the reservation price, which is the minimum price for obtaining two units.

3 IR Protocol

3.1 Limitations of LDS Protocol

One limitation of the LDS protocol is that the auctioneer must pre-define the possible combinations of bundles as a leveled division set. To increase the social surplus or the revenue, the auctioneer must choose an appropriate leveled division set, but this task is not easy. Even if the auctioneer has some knowledge of the distributions of agents' evaluation values, the auctioneer must solve a very complicated optimization problem to find an appropriate leveled division set.

Also, in the LDS protocol, if there exists an evaluation value that is larger than the reservation price for any single bundle in the level, the auctioneer must sell units using the current level. For example, in the situation of Example 1, when the reservation price for a unit is 10 and the leveled division set of case 2 in Figure 1 is used, there exists an evaluation value for a bundle of three units. Therefore, the auctioneer must sell units using the divisions of level 2. In this case, only three units can be sold, although there exist many participants whose evaluation values for a single unit are larger than the reservation price.

When there are many demands for smaller bundles, such as for two or three units, using the leveled division set of case 2 in Figure 1 is inappropriate. If we use the leveled division set of case 3, the result would be better, but we still must pre-define the possible combinations of bundles and cannot flexibly combine bundles according to demands.

3.2 Overview of IR Protocol

In our newly developed Iterative Reducing (IR) protocol, instead of determining the possible divisions of units in advance, we determine the allocations of bundles sequentially from larger bundles. More specifically, as in the LDS protocol, we first check whether there exists an agent whose evaluation value for a bundle of M units is larger than the reservation price r ×M. If not, we reduce the number of units in a bundle one by one. When some bundles of k units are allocated, and there exist enough remaining units, we allocate smaller bundles.

3.3 Details of IR Protocol

The protocol is executed by calling the procedure IR(M,M, {1, 2, . . ., N}), which is defined as follows.

Procedure IR (m, j, Participants)

• Step 1: When j = 0, terminate the protocol.
• Step 2: Set k to the largest integer where j × k ≤ m holds. Set Candidates ← {i | i ∈ Participants, bi↪j ≥ r × j}, n ← |Candidates|.
• Step 3: When n > k:
• 3.1: Set Winners to a set of agents i, where i ∈ Candidates and bi↪j is within k-th highest evaluation values in Candidates, and set p to the k + 1-th highest evaluation value in Candidates (ties are broken randomly).
• 3.2: Each agent i ∈ Winners gets a bundle of j units, and pays p. Terminate the protocol.
• Step 4: When n = k:
• 4.1: Set Winners ←Candidates, and p ← r × j.
• 4.2: For each i ∈ Winners, compare its utility for obtaining a bundle of j units by paying p, and that for the result of IR(m-j×(n-1), j-1, (ParticipantsWinners) ∪ {i}), and choose the one that gives the higher utility for agent i. Terminate the protocol.
• Step 5: When n < k:
• 5.1: Set Winners ←Candidates, and p ← r × j.
• 5.2: For each i ∈ Winners, compare its utility for obtaining a bundle of j units by paying p, and that for the result of IR(m-j×(n-1), j-1, (ParticipantsWinners) ∪ {i}), and choose the one that gives the higher utility for agent i.
• Call IR(m - j × n, j - 1, Participants - Winners).

When the result of IR(m-j ×(n-1), j -1, (ParticipantsWinners) ∪ {i}) is used in Step 4.2 or Step 5.2, although we calculate the allocated units and payment of agent i as if agents other than Winners could obtain some units, we don't assign any units nor transfer money to agents except Winners.

3.4 Examples of Protocol Application

Example 2 Let us assume there are 12 units of an item, and the reservation price of one unit is 10. The evaluation values of agents are identical to Example 1. From IR(12, 12, {1, 2, . . . , 13}) to IR(12, 4, {1, 2, . . ., 13}), n becomes 0 in Step 2. In IR(12, 3, {1, 2, . . . , 13}), the condition of Step 5 holds. Each of the agents 1,2, and 3 obtains a bundle of three units and pays the reservation price 30. Then, IR(3, 2, {4, . . ., 13}) is called. In IR(3, 1, {4, . . ., 13}), the condition of Step 3 holds, and each of the agents 4, 5, and 6 obtains one unit bundle and pays 11.

Example 3 Let us assume there are 12 units of an item and the reservation price of one unit is 10. The evaluation values of agents are defined as follows.

In IR(12, 5, {1, 2, 3}), the condition of Step 4 holds. Each of the agents 1 and 2 obtains a bundle of five units at the reservation price 50. However, in the procedure of Step 4.2, agent 2 prefers the result of IR(7, 4, {2, 3}), i.e., obtaining a bundle of four units at 48. Thus, this result is applied for agent 2.

Example 4 The procedures in Steps 4.2 and 5.2, which compare the results and choose the one that gives higher utility for an agent, are necessary to guarantee incentive compatibility.

Let us assume we omit these procedures. Then, in the situation of Example 3, agent 2 obtains a bundle of five units when it truthfully declares its evaluation values and its utility is 51 - 50 = 1. When agent 2 understates its evaluation values as 49 for a bundle of four and five units, then agent 2 can obtain a bundle of four units and its utility becomes 51 - 48 = 3. Thus, for agent 2, declaring its true evaluation value cannot be a dominant strategy without these procedures.

Example 5 In Steps 3 and 4, even if there exist remaining units, the protocol is terminated. This might seem wasteful, but it is necessary to guarantee incentive compatibility. Let us assume the protocol is continued as long as there exists at least one remaining unit. In the situation of Example 3, agent 3 cannot obtain any unit when it truthfully declares its utility, thus its utility is 0. On the other hand, agent 3 can use a false name agent 4 and changes its declarations as follows.

Then, in IR(12, 5, {1, 2, 3, 4}), the condition of Step 3 holds, and each of the agents 3 and 4 obtains a bundle of five units. When the protocol is continued as long as there exists at least one remaining unit, we must apply a similar comparison procedure in Step 3 as well as in Steps 4 and 5. Since these agents prefer obtaining a bundle of two units, each agent obtains a bundle of two units by paying the reservation price 20. In reality, agent 3 obtains four units by paying 40 and its utility is 48 - 40 = 8, thus using a false-name bid is profitable.

In the IR protocol, when a bundle of j units are sold, and the number of remaining units is smaller than j, the protocol will be terminated. Therefore, an agent cannot obtain a fraction of units at a lower price nor gather a fraction of units by using multiple identifiers.

4 Proof of Incentive Compatibility

We are now going to prove the following theorem.

Theorem 1 The IR protocol satisfies incentive compatibility.

To prove this theorem, we use the following lemmas.

Lemma 1 If an agent i uses two identifiers i ′ and i′′ , and obtains a bundle of x and y units under the identifiers i ′ and i′′ , respectively, then agent i can obtain z = x+ y units at a price that is less than (or equal to) the sum of the prices for x and y by using a single identifier.

The proof is as follows. For the price of x units px and the price of y units py, px ≥ r × x and py ≥ r × y hold. Since agent i obtains x and y units, M ≥ z holds.

Now, let us consider the situation where agent i (or i ′ , i′′ ) does not participate in the auction. When selling bundles of z units, let us assume the condition of Step 3 or Step 4 holds. In this case, when another agent participates, the agent cannot obtain a bundle smaller than z. This is because the protocol is terminated before or just after selling bundles of z units. This contradicts the assumption that agent i ′ obtains a bundle of x units and i′′ obtains a bundle of y units. Thus, when bundles of z units are sold, the condition of Step 5 must hold.

Now, let us assume that agent i participates and declares its evaluation value for z units bi↪z as r × z + ϵ, where ϵ is a very small amount. Since without i's participation, the condition of Step 5 holds. By adding this declaration, the condition of Step 4 or Step 5 holds. In either case, agent i can obtain a bundle of z units with a payment of p = r × z, which is smaller than (or equal to) px + py, i.e., the sum of the payments when agent i uses multiple identifiers. ✷

Using a similar method of the proof of Lemma 1, we can show that if an agent uses more than two identifiers, it can obtain the same number of units with a smaller (or equal) payment by using a single identifier.

So far, we have shown that an agent cannot increase its utility by using false-name bids. Now, we are going to show that truth-telling is the dominant strategy for each agent under the assumption that the agent uses a single identifier.

Lemma 2 An agent cannot increase its utility by overstating its evaluation value.

The proof is as follows. Assume that agent i's true evaluation value of j units is vi↪j, and it overstates its evaluation value as bi↪j, where bi↪j > vi↪j . It is clear that if agent i cannot be in Winners by declaring bi↪j when selling bundles of j units, overstating is useless. Furthermore, if agent i is in Winners when it declares vi↪j, since its payment is independent from its declared evaluation value, overstating is useless.

The only possible case where overstating might be effective is when agent i declares vi↪j, it is not in Winners, and when it declares bi↪j, it becomes a part of Winners. However, in this case, the payment becomes larger than the true evaluation value vi↪j. Therefore, to obtain a positive utility, the procedures of Step 4.2 or Step 5.2 must be applied and agent i obtains a bundle smaller than j. However, the situations considered in these procedures are identical to the situation when agent i truthfully declares its utility as vi↪j. Thus, overstating is useless. ✷

Lemma 3 An agent cannot increase its utility by understating its evaluation value.

The proof is as follows. Assume that agent i's true evaluation value of j units is vi↪j, and it understates its evaluation value as bi↪j, where bi↪j < vi↪j. It is clear that if agent i cannot be in Winners when declaring vi↪j, understating is useless. Furthermore, if agent i is still inWinners when it declares bi↪j , since its payment is independent from its declared evaluation value, understating is useless.

The only possible case where understating might be effective is when agent i declares vi↪j, it is in Winners, and when it declares bi↪j, it can be excluded from Winners. However, in this case, if the condition of Step 3 holds when agent i truthfully declares vi↪j, by understating, either the condition of Step 3 or Step 4 holds. In both cases, the protocol is terminated and agent i cannot obtain any units. On the other hand, let us assume the condition of Step 4 or 5 holds when agent i truthfully declares vi↪j. Then, the situation that occurs when agent i declares bi↪j is identical to the situation considered in Step 4.2 or Step 5.2 when agent i truthfully declares vi↪j. If agent i prefers this result, the result is applied when agent i truthfully declares vi↪j . Thus, understating is useless. ✷

From these lemmas, we can derive Theorem 1.

5 Evaluations

In this section, we compare the obtained social surplus of the IR protocol and that of the LDS protocol using a simulation. We determine the evaluation values of agent i by the following method. This method is based on the binomial distribution used in [Fujishima et al., 1999] for evaluating winner determination algorithms in combinatorial auctions.

• Determine the size of a bundle j that agent i wants to have by using a binomial distribution B(M, p), i.e., the probability that the size of the bundle is j is given by pj (1 - p)M-jM !/(j!(M - j)!).
• Randomly choose vi↪j, i.e., i's evaluation value for the bundle of j, from within the range of [0, j]. We assume that the evaluation values of an agent are all-or-nothing, i.e., the evaluation value for a bundle smaller than j is 0. Also, we set the evaluation value for a bundle larger than j to vi↪j, i.e., having additional units is useless.

We generated 100 problem instances by setting the number of agents N = 10, the number of units M = 10, and p = 0.2. Figure 2 shows the average ratio of the obtained social surplus to the Pareto efficient social surplus by varying the reservation price. We show the results of the IR protocol and those of the LDS protocol, in which the leveled division sets are case 2 and case 3 in Figure 1. Since we set M = 10 and p = 0.2, the size of a bundle is most likely to be 2, and 1 and 3 are also likely to exist. Thus, the leveled division set of case 3 seems to be a reasonable choice.

If the GVA is used and agents cannot submit false-name bids, then the obtained social surplus is Pareto efficient and the ratio becomes 100%. On the other hand, when agents can submit false-name bids, we cannot predict the obtained result of the GVA, since declaring true evaluation values is no longer a dominant strategy for each agent.

As shown in Figure 2, by setting the reservation price to an appropriate value, the social surplus of the IR protocol becomes about 70%of the Pareto efficient social surplus. On the other hand, in the LDS protocol, the social surplus becomes at most 53% of the Pareto efficient social surplus. In both protocols, when the reservation price is small, one bundle of M units is sold to a single agent. By increasing the reservation price, the units are divided among multiple agents. In the IR protocol, the combination of bundles is determined in a flexible manner, and by increasing the reservation price, the protocol can select the combination of bundles that increases the obtained social surplus. On the other hand, in the LDS protocol, the possible combinations of bundles must be pre-defined; thus the protocol cannot adjust to various problem instances. We have obtained very similar results for the problem instances generated using different parameter settings and different distributions of agents' evaluation values.

If the auctioneer has some knowledge of the distributions of agents' evaluation values, optimizing the reservation price for the IR protocol would be relatively easy compared with optimizing both the reservation price and the leveled division set for the LDS protocol. Of course, we cannot say that the IR protocol always achieves a better social surplus than that of the LDS. If agents require very large bundles, then the IR protocol might end up selling only m + 1 units out of M = 2m units. In such a case, the LDS protocol with a carefully designed leveled division set could beat the IR protocol.

6 Conclusions

In this paper, we developed a multi-unit auction protocol (IR protocol) that is robust against false-name bids. Compared with the LDS protocol, this protocol is easier for an auctioneer to use, since he/she only needs to determine the reservation price of one unit, while he/she must pre-define possible combinations of bundles as well as the reservation price in the LDS protocol. We showed that the IR protocol can obtain a much better social surplus than that obtained by the LDS protocol, since it can determine the combination of bundles in a flexible manner according to the declared evaluation values of agents. Our future works will include developing combinatorial and double auction protocols [Yokoo et al., 2001] that are robust against false-name bids based on the IR protocol.