ソシオネットワーク戦略ディスカッションペーパーシリーズ
第 50 号

ISSN 1884-9946

2017 年 11 月

RISS Discussion Paper Series
No.50 November, 2017

An Approximation Algorithm for Multi-unit Auctions:
Numerical and Subject Experiments

Satoshi Takahashi, Yoichi Izunaga, Naoki Watanabe

文部科学大臣認定

共同利用・共同研究拠点

関西大学ソシオネットワーク戦略研究機構
The Research Institute for Socionetwork Strategies,
Kansai University
Joint Usage / Research Center, MEXT, Japan
Suita, Osaka, 564-8680, Japan
URL: http://www.kansai-u.ac.jp/riss/index.html
e-mail: riss@ml.kandai.jp
tel. 06-6368-1228
fax. 06-6330-3304

An Approximation Algorithm for Multi-unit Auctions:
Numerical and Subject Experiments

Satoshi Takahashi, Yoichi Izunaga, Naoki Watanabe

文部科学大臣認定

共同利用・共同研究拠点

関西大学ソシオネットワーク戦略研究機構
The Research Institute for Socionetwork Strategies,
Kansai University
Joint Usage / Research Center, MEXT, Japan
Suita, Osaka, 564-8680, Japan
URL: http://www.kansai-u.ac.jp/riss/index.html
e-mail: riss@ml.kandai.jp
tel. 06-6368-1228
fax. 06-6330-3304

An Approximation Algorithm for Multi-unit Auctions:
Numerical and Subject Experiments∗
Satoshi Takahashi†

Yoichi Izunaga‡

Naoki Watanabe§

November 3, 2017

Abstract
In multi-unit auctions for a single item, the Vickrey-Clarke-Groves mechanism (VCG) attains allocative eﬃciency but suﬀers from its computational
complexity. Takahashi and Shigeno (2011) thus proposed a greedy based approximation algorithm (GBA). This paper reports that in a subject experiment
there was truly a diﬀerence in eﬃciency rate but no significant diﬀerence inseller’s revenue between GBA and VCG. It is not clear in theory whether eachbidder will submit his or her true unit valuations in GBA. We show, however,that in a subject experiment there was no significant diﬀerence in the number ofbids that obey “almost” truth-telling between GBA and VCG. As for individual
bidding behavior, GBA and VCG show a sharp contrast when a human biddercompetes against machine bidders; underbidding was observed in GBA, while
overbidding was observed in VCG. Some results in a numerical experiment arealso provided prior to reporting those observations.
Keywords: multi-unit auctions, approximation algorithm, experiment
JEL Classification: C92, D44, D82∗

The authors wish to thank Maiko Shigeno, Tatsuyoshi Saijo, Yoshitsugu Yamamoto, and partic-

ipants in seminars at DC2012, Université d’Aix-Marseille, and SING13 for their helpful comments
and suggestions to the earlier versions of this manuscript. This research is supported by JSPS Grantin-Aid for Young Scientists (B) 26870200 and Grant-in-Aid for Scientific Research (B) 15H02972(Takahashi), and Japan Center for Economic Research and Kansai University RISS (Watanabe).
†
Graduate School of Informatics and Engineering, The University of Electro-Communications,
Chofu, Tokyo, Japan. E-mail: stakahashi@uec.ac.jp‡
Faculty of Business Sciences, University of Tsukuba, Otsuka Bunkyo, Tokyo, Japan. E-mail:izunaga@gssm.otsuka.tsukuba.ac.jp§
Graduate School of Business Administration, Keio University, 4-1-1 Hiyoshi Kohoku, Yokohama, Kanagawa 223-8526, Japan. E-mail: naoki50@keio.jp.

11

Introduction

In multi-unit auctions for a single item, the Vickrey-Clarke-Groves mechanism (VCG)
attains allocative eﬃciency but suﬀers from its computational complexity. In fact,
the item allocation problem is known to be N P-hard, and thus it is necessary for
us to apply some approximation algorithm to that problem. Kothari et al. (2005)
considered the item allocation problem in reverse auctions as a generalized knapsackproblem and proposed a greedy based 2-approximation algorithm with O(ℓ2 ) time,
where ℓ is the total sum of numbers of bidders’ anchor values. As far as non-reverse
auctions are concerned, however, their algorithm does not necessarily return a solution the approximation ratio of which is not bounded by two. (We can provide suchan example upon request.) Takahashi and Shigeno (2011) thus proposed anothergreedy based 2-approximation algorithm (GBA) with O(ℓ(log n + lmax )) time, wherelmax is the maximum number of anchor values among those of bidders.1
In GBA, the highest unit bidder is tentatively given the unit and the other unit
bids of the tentative winner are updated in the process for determining the final
item allocation. This paper reports that in a subject experiment there was truly adiﬀerence in eﬃciency rate but no significant diﬀerence in seller’s revenue between
GBA and VCG. It is not clear in theory whether each bidder has an incentive tosubmit his or her true unit valuations in GBA. In the subject experiment there wasno significant diﬀerence in number of bids that obey “almost” truth-telling between
GBA and VCG. As for individual bidding behavior, GBA and VCG show a sharp
contrast when a human bidder competes against machine bidders; underbidding
was observed in GBA, while overbidding was observed in VCG. Some results in anumerical experiment are also provided prior to reporting our main observations.
In the numerical and subject experiments, it is assumed that for all bidders,each unit valuation is drawn independently of the other unit valuations, i.e., in
random order. We might alternatively assume that unit valuations are given to eachbidder in monotone non-increasing order. In a preliminary experiment for VCG
conducted prior to our main sessions, however, the standard deviation of seller’s
revenue observed in monotone non-increasing order of unit valuations is much larger
than the one observed in random order of those. We thus conducted the experimentswith unit valuations which were drawn in random order.
1

Takahashi and Shigeno (2011) developed another 2-approximation algorithm, which is based on

Dyer’s polynomial time algorithm (Dyer, 1984), and they showed in a numerical experiment that
the GBA computed faster and approximated better than that alternative algorithm.

2

The rest of this paper is organized as follows. Section 2 introduces the modelof multi-unit auctions for a single item and describes how GBA and VCG derive
allocations of the item. Section 3 displays the results of a numerical experiment on
computation time and eﬃciency rate under the assumption of truth-telling bidding.
Section 4 shows our main observations in a subject experiment. Section 5 notes some
remarks, referring to a preliminary experiment for VCG and other papers related toour results.

2

The modelThis session concisely describe the the Vickrey-Clarke-Groves mechanism (VCG)
and its greedy base 2-approximation algorithm (GBA).

2.1

VCG mechanism

Consider a multi-unit auction for a single item, where a seller wishes to sell M unitsof a single item and solicits bids from n buyers. Let N = {1, ..., n} be the set ofbuyers (bidders). For each bidder i ∈ N , denote his or her anchor values on thequantity by {dki | k = 0, ..., ℓi }, where dk−1
< dki for all k with 1 ≤ k ≤ ℓi , and denotei
his or her unit bids by {bki | k = 1, ..., ℓi }, where bki is a buyer price in half-open
range (dk−1, dki ] for k = 1, ..., ℓi . It is assumed that d0i = 0 and dℓi i ≤ M for everyibidder i ∈ N . Each bidder i has a list of his or her anchor values and unit bids, i.e.,∑{dki | k = 0, ..., ℓi } and {bki | k = 1, ..., ℓi }. Let ℓ = i∈N ℓi .
Define bidder i’s bid function: R+ → R by{
bki · y (dk−1< y ≤ dki , k = 1, ..., ℓi ),i
Bi (y) =0(y = d0i , y > dℓi i ).

(1)

Figure 1 illustrates an example of the bid function. For each bidder i ∈ N , denotehis or her unit valuations by {vik | k = 1, ..., ℓi }. Define bidder i’s valuation function
Vi : R+ → R by{
Vi (y) =vik · y (dk−1< y ≤ dki , k = 1, ..., ℓi ),i(2)(y = d0i , y > dℓi i ).
∑A vector x = (x1 , x2 , . . . xn ) that satisfies i∈N xi ≤ M and xi ≥ 0 for any i ∈ N
0

is called an allocation, where xi is the units of the item assigned to bidder i ∈ N in
the allocation.

3

Figure 1: A bid function. The unit bids represent the gradients of the bid function, and theanchor values stand for its discontinuous points.

An item allocation problem (AP )B is to find allocations that maximize the total
amount of bids is formulated by(AP )B maximize
subject to

∑
i∈N
∑

Bi (xi )xi ≤ M(3)i∈Nxi ≥ 0 (∀i ∈ N ).
Another problem (AP )V is formulated in the same way by(AP )Vmaximizesubject to

∑
i∈N
∑

Vi (xi )xi ≤ M(4)i∈Nxi ≥ 0 (∀i ∈ N ),in order to find eﬃcient allocations that maximize the total amount of valuations.
The payment scheme is as follows. Denote by x∗ an optimal solution of (AP )B .
Let x−j be an optimal solution of the following restricted item allocation problem−j = N \ {j}.
(AP )−jB with the set of bidders N(AP )−jB∑maximize−ji∈N∑

subject toBi (xi )xi ≤ Mi∈N −jxi ≥ 0 (∀i ∈ N −j ).

4(5)

In the VCG, bidder j’s payment pj is determined bypj =∑Bi (x−ji )−i∈N −j∑Bi (x∗i ).

(6)i∈N −jUnder this payment scheme, it is the dominant strategy for each bidder to truthfully tell his or her unit valuations by bidding; Thus, the optimal solutions of (AP )B
maximize the total amount of valuations in (AP )V . We have to, however, computeas many as O(n) times in (AP )B to find an optimal solution. It becomes more diﬃcult to compute an allocation and payments in realistic time, as the number of either
bidders or units of the item is larger. We thus need to find faster approximation
algorithms to solve the item allocation problem.

2.2

Greedy based algorithm

This subsection describes a GBA which was proposed by Takahashi and Shigeno(2011). This algorithm uses the slope function pki : R → R, for any i ∈ N and all kwith 0 < k ≤ ℓi . Denote by pki (y) the gradient of bid function Bi between a unit ofy and each anchor value dki , i.e.,pki (y) =(Bi (dki ) − Bi (y)).
(dki − y)(7)

The GBA takes the following process of four steps.
Step 1 Set xi = 0 for any i ∈ N .
∗Step 2 Find a pair (i∗ , k ∗ ) such as pki∗ (xi∗ ) = max{pki (xi ) | i ∈ N, xi < dki }. If∗∗pki∗ (xi∗ ) ≤ 0, then return x, otherwise, update xi∗ = dki∗
Step 3 If∑i∈N xi < M , go to Step 2.

Step 4 Make two solutions x̂ and x̃ by{{
xi(i ̸= i∗ ),0(i ̸= i∗ ),x̂i =and x̃i =∑M − j̸=i∗ xj (i = i∗ ),xi∗ (i = i∗ ).
∑∑If i∈N Bi (x̂i ) > i∈N Bi (x̃i ), then return x̂, otherwise, return x̃
The process is initialized in Step 1. In Step 2, GBA finds a pair (i∗ , k ∗ ) which
maximizes the slope function. If GBA stops in Step 2, i.e. pk∗i∗ (xi∗ ) ≤ 0, no solution
can improve the objective value from the current solution. The returned solution is∑thus optimal. GBA iterates Step 2 until i∈N xi ≤ M . In Step 4, GBA makes two5∑∗
j̸=i∗ xj is allocated to bidder i in x̂,while no unit is allocated to any bidder j ∈ N −i∗ in x̃. GBA compares the objective

solutions x̂ and x̃. The residual units M −values of these two solutions and returns the larger one.
The Ausubel auction (Ausubel, 2004) also has a similar process of updating
the other unit bids of the tentative winners, although the updates are made in
dynamic ascending-bid auctions. The GBA makes the updates in static auctions, as
shown above. This feature of GBA reduces computation time when the number ofbidders or the total sum of numbers of bidders’ anchor values. The GBA finds anapproximate solution of (AP )B , and the objective value obtained by the approximate
solution is at least a half of the optimal objective value in (AP )B . These are formallystated as the following theorem.
Theorem 1 (Takahashi and Shigeno, 2011) GBA finds a 2-approximation solution of (AP )B in O(ℓ(log n + lmax )) time, where lmax = maxi∈N ℓi .
The intuition of Theorem 1 on computation time is explained as follows. The
number of iteration in GBA is clearly at most ℓ. If we store max{pki (xi ) | xi < dki }for all i ∈ N in a heap, Step 2 can be performed in O(log n). After Step 2, we needto compute max{pki∗ (xi∗ ) | xi∗ < dki∗ } for updated xi∗ , which runs in O(ℓi∗ ). The
total running time of Step 2 is thus bounded by O(log n + lmax ). Therefore, the total
running time is bounded by O(ℓ(log n + lmax )).
The payment scheme is as follows. Denote by x̌ an allocation determined by
GBA. Let x̌−j be an allocation determined by GBA when the set of bidders is
restricted to N −j = N \ {j}. In GBA, bidder j’s payment p̌j is determined by
p̌j =

∑

Bi (x̌−ji )−i∈N −j∑Bi (x̌i ).

(8)i∈N −jUnder this payment scheme, it is not clear in theory whether each bidder willtruthfully submit his or her unit valuations by bidding in GBA. It is, however, shown
later that in a subject experiment there was no significant diﬀerence in the numberof bids that obey “almost” truth-telling between GBA and VCG. The definition of
the almost truth-telling bidding is noted later in Section 4.
In this section, we did not explain the intuition of Theorem 1 on approximation
ratio. Instead, the approximation ratio of GBA against VCG can be confirmed aswell as the computation time in a numerical experiment, the results of which are
shown in the next section.

6

3

A numerical experimentThis section displays the results of a numerical experiment which functions as acontrol group against part of the observations in the corresponding subject experiment, where bidders are all truth-telling machine bidders. All computations wereconducted on a personal computer with Core i7 CPU (3.4 GHz) and 16GB memory,and the code was written with python 2.6.5. (The code is available upon request.)
We fix n or M for instances, varying the values of the other variables.
For each bidder i ∈ N , the number of his or her anchor values, ℓi , was independently drawn from the set of 15 integers {1, . . . , 15} with equal probability. Then,for any bidder i ∈ N , anchor values, the number of which is ℓi , were drawn independently from the set of integers {1, . . . , M } with equal probability, arranged inascending order, and indexed from 0 to ℓi to construct {dki | k = 0, ..., ℓi }.2 As ismentioned in Section 1, for any bidder i ∈ N , each unit valuation vik is independently drawn from the set of 100 integers {1, . . . , 100} with equal probability. Bothin GBA and in VCG, truth-telling bidders were assumed.
We conducted this numerical experiment by using dynamic programing. Consider an arbitrary ordering on n bidders. For the first k bidders and m units with0 ≤ m ≤ M , define
T [k, m] := max


k
∑


v( xj ) |

j=1

k
∑
j=1



xj ≤ m, xj ≥ 0 (1 ≤ j ≤ k) ,(9)(k ∈ N, 0 ≤ m ≤ M ).
The following recurrence relation describes how to solve problem (9) with dynamic
programing.
T [0, m] = 0, (0 ≤ m ≤ M ).
{}T [k − 1, m]
T [k, m] = max,
max1≤z≤m {T [k − 1, m − z] + vk (z)}

(10)
(11)

(k ∈ N, 0 ≤ m ≤ M ).
The optimal objective value of (AP )V can be obtained by
max {T [n, m]}.

0≤m≤M
2

(12)

There was no case of a tie observed in this numerical experiment.The description of a tie-breakrule is thus omitted here.

7Let n = 50 or M = 200. Tables 1 and 2 show the averages of computation timeand approximation ratio in GBA against VCG, where the approximation ratio isdefined byapproximate value of (AP )V,
optimal value of (AP )V(13)

which actually measures the eﬃciency rate of GBA against VCG. In Tables 1 and2, VCG is denoted as EXACT in order to indicate that the optimal values are used
there. In subject experiments, human bidders do not necessarily behave in sucha way that the optimal values of (AP )V are derived even in VCG. Figures 2 and3 depict the average computation time which correspond to the instances listed inTables 1 and 2, respectively.
Table 1 shows that as the number of units of the item increases, the computation
time in VCG remarkably increases, whereas the increase in computation time issuppressed in GBA. When the number of bidders, n, does not change, the expected∑values of ℓ = i∈N ℓi and lmax also do not change, respectively. The expected valueof the upper bound of computation time in GBA, O(ℓ(log n + lmax )), is then kept
intact, as far as n is fixed.
As the number of bidders, n, increases, the upper bound of computation time,O(ℓ(log n + lmax )), is expected to go up in GBA, because the expected value of∑ℓ = i∈N ℓi increases, although lmax ≤ 15 always. Even in this case, Table 2 showsthat GBA finds the solution of (AP )B much faster than VCG.
Note that the approximation ratios shown in Tables 1 and 2 are bounded by 0.62
and 0.92. As is mentioned above, those ratios actually measures eﬃciency rates of
GBA against VCG. In the next section, we show that the average rates of eﬃciency
in GBA observed in the subject experiment were more than 0.93, although there
was truly a diﬀerence between GBA and VCG. We also show, however, that there
was no significant diﬀerence in seller’s revenue between GBA and VCG. The rate ofeﬃciency is defined with the observed value and the optimal value (EXACT) bothin GBA and in VCG.

8

Table 1: Averages of computation time and approximation ratio in GBA against VCG. Eachinstance is represented by the numbers of bidders and units, i.e., (n, M ), where n = 50. VCG isnoted as EXACT. As the number of units of the item increases, the computation time in VCG
increases, whereas GBA suppresses the increase in computation time. The expected value of theupper bound of computation time in GBA, O(ℓ(log n+lmax )) is kept intact, because n, the expected∑value of ℓ = i∈N ℓi , and the expected value of lmax are not changed.

Instance

Computation time (sec.)

Approx. ratio

GBA

EXACT

GBA/EXACT(50,50)0.002270.10300

0.727(50,100)

0.00201

0.388640.736(50,150)0.001900.838850.623(50,200)

0.002171.52568

0.723(50,250)

0.002022.36149

0.633(50,300)

0.002223.40518

0.775(50,350)

0.002154.70473

0.815(50,400)

0.002035.919170.874

Figure 2: Number of units of the item and computation time. n = 50. VCG is noted as EXACT.

9

Table 2: Averages of computation time and approximation ratio in GBA against VCG. Eachinstance is represented by the numbers of bidders and units, i.e., (n, M ), where M = 200. VCG
is noted as EXACT. As the number of bidders, n, increases, the upper bound of computation∑
time, O(ℓ(log n + lmax )), is expected to go up in GBA, because the expected value of ℓ = i∈N ℓi
increases, although lmax ≤ 15 always. Even in that case, however, GBA completes the computationmuch faster than VCG.

Instance

Computation time (sec.)

Approx. ratio

GBA

EXACT

GBA/EXACT(10, 200)

0.001190.701540.915(50, 200)

0.004093.446120.804(100, 200)

0.00768

6.813750.837(200, 200)

0.01440

13.54417

0.700(400, 200)

0.02869

27.49757

0.715(800, 200)0.0575455.845500.760(1000, 200)

0.06933

69.442060.760(5000, 200)

0.34113348.4999

0.753(10000, 200)

0.72498698.56540

0.622

Figure 3: Number of bidders and computation time. M = 200. VCG is noted as EXACT.

10

4

The subject experiment

4.1

Experimental design

In this experiment, 5 units of an item are auctioned oﬀ to 3 bidders, where the item
is a virtual object, i.e., n = 3 and M = 5. Each session consists of 20 rounds intotal, and 2 sessions are paired; In a session GBA is applied in the first 10 rounds
and VCG is applied in the second 10 rounds, and the order of GBA and VCG isreversed in another session. (Every subject thus bids in both treatments, although
he or she can participate in only one session. In analysis, the data should be mergedin order to cancel the eﬀect of the order of treatments on the results.)
For every bidder i, the number of anchor values is set as ℓi = 5, and thus his or
her anchor values are d0i = 0, d1i = 1, ..., d5i = 5. As is mentioned in Section 1, foreach bidder i and for each unit of the item, his or her unit valuation for k units of
the item, vik (k = 1, . . . , 5), is independently and uniformly distributed over integers
between 1 and 200. At the beginning of each round, each bidder i is given his or
her unit valuations {vik | k = 1, ..., ℓi } by a computer, which are his or her private
information. Then, each bidder i submits his or her unit bids {bki | k = 1, ..., ℓi }.
When k units of the item is allocated to bidder i, he or she receives the points thatamounts vik · k minus his or her payment.
In each round, there is a 120-second time limit for submitting unit bids. If noneof three bidders bids within the time limit, every bidder of those three then obtains
zero point for that round. The units assigned to a bidder and his or her payment are
shown to the bidder in 5 seconds at the end of each round. The cumulative pointsof bidders are not shown to them (It is thus prohibited for subjects to take notes
throughout the session.
Subjects are informed that they will be paid according to the total points theyobtain in 6 rounds (3 from the first 10 rounds and 3 from the subsequent 10 rounds)
randomly selected by a computer at the end of each session, with the pre-determinedexchange rate in addition to the show-up fee. In this experiment, the exchange rate
was 1 point = 1 JPY and the show-up fee was 1500 JPY.
At the beginning of each session, GBA (or VCG) applied in the first 10 rounds
is explained with the general instruction. There is an intermission after the first
10 rounds so that VCG (or GBA) applied in the second 10 rounds is explained.
Before proceeding to the experiment, subjects play 1 round for practice to familiarize
themselves with the software.

11

4.2

Results

A computerized laboratory experiment was conducted at the University of Tsukuba
in Japan. We developed a software which uses python cgi for the experiment. We had
4 sessions in February 2014 and 4 sessions in January 2016. Each session conducted
in 2016 involves 8 groups of 3 subjects. At the beginning of each round, all subjects
were randomly re-grouped into 8 groups by a computer. Subjects are not informedof who are in the same group. Each session conducted in 2014 involves 8 groupsof 1 subject as a human bidder and 2 machine bidders which were programed astruth-telling bidders. At the beginning of each session, each subject was randomly
assigned to one of 8 groups by a computer. This assignment was fixed throughoutthat session.
Subjects were recruited from all over the campus, and undergraduate students
whose major is engineering were most populous among them. Once a subject participated in a session, he or she was prohibited to participate in any other sessions forthis experiment. Upon arrival, they were provided with a written instruction, andthen the experimenter read it around. (The instruction is available upon request.)
Subjects could ask questions regarding the instruction by raising their hand and theexperimenter gave the answers to those questions privately. Any communication
among subjects were strictly prohibited; Thus, their interactions were only throughthe information they enter in their computer screens. Each session lasted about 100
minutes including the instruction. There was no observation of bidding made after
the time limit. Features of the experimental sessions are summarized in Table 3.
Table 3: Features of the experimental sessions.
sessionmachineshow-uppoint-to-# ofsessionavg. point

no.

biddersfee (JPY)

JPY ratio

subj.

date

per subject

1

yes

1500

1.0

8

Feb.13, 2014

513.75

2

yes

1500

1.0

8

Feb.13, 2014

609.63

3

yes

1500

1.0

8

Feb.14, 2014295.38

4

yes

1500

1.0

8

Feb.14, 2014

169.29

5

no

1500

1.0

24

Jan.30, 2016

510.42

6

no

1500

1.0

24

Jan.30, 2016

641.04

7

no

1500

1.0

24

Jan.31, 2016284.75

8

no

1500

1.0

24

Jan.31, 2016

583.71

12

In Table 3, there were some outliers of unit bids in sessions 3, 4, and 7, whichwere extraordinarily higher than the corresponding unit valuation; Thus, the average
points per subject were lower than those in the other sessions. We dropped extreme
outliers in our regression analysis of subjects’ bidding behavior, the result of whichis shown later in this section.
The rate of eﬃciency in GBA (or in VCG) are defined byobserved value of (AP )V,
optimal value of (AP )V(14)

where the observed value of (AP )V is calculated with an allocation x observed when
GBA (or VCG) is applied. The rate of the seller’s revenue (profit) in GBA (or in
VCG) is defined byobserved total amount of payments.
(15)
optimal total amount of payments∑
The optimal total amount of payments is represented by j∈N pj , where pj is calculated for each j ∈ N according to (6). Our main observation is then stated asfollows.
Observation 1 In the subject experiment, there was a diﬀerence in eﬃciency rate
but no significant diﬀerence in seller’s revenue between GBA and VCG.
Tables 4 and 5 show the average rates of eﬃciency and seller’s revenue (profit)
observed in 2014 and 2016, respectively. We analyzed the data taken from the last 5
rounds in each treatment to allow subjects the opportunity to learn better bidding
behavior in GBA and VCG. Each treatment had 4 sessions, and there were 8 groups
in each session, and thus the sample size is 160 for each treatment. The data weremerged for each treatment in order to cancel the eﬀect of the order of treatmentson the results. The p-values for the permutation test (perm. test) are reported
under each panel which corresponds to the rates of eﬃciency and seller’s revenue,
respectively. The null hypotheses on the rates of eﬃciency was rejected at the 5%
significance level with both data taken in 2014 and in 2016. The null hypotheses on
the rates of seller’s revenue, however, could not be rejected at the 5% significancelevel with both data taken in 2014 and in 2016.

13

Table 4: Average rates of eﬃciency and seller’s revenue (profit) in 2014.
eﬃciency

profit

GBA

VCG

GBA

VCG

mean

0.9341

0.96261.00690.9828st.dev.

0.02770.03450.06510.0402p-value (perm.)

0.00680.1703

Table 5: Average rates of eﬃciency and seller’s revenue (profit) in 2016.
eﬃciency

profit

GBA

VCG

GBA

VCG

mean

0.93650.97370.90370.8978st.dev.

0.03020.02200.09930.0775p-value (perm.)

0.00010.8471

As noted at the end of subsection 2.1, the VCG mechanism, in theory, induces
allocative eﬃciency by providing every bidder with an incentive to submit his or her
valuations truthfully for each unit. In Section 3, the numerical experiment suggeststhat even under the assumption of truth-telling bidding, GBA is inferior to VCG interms of the eﬃciency rate measured by (15). Thus, in order to confirm this featureof GBA also in the subject experiment, we counted the number of unit bids which
satisfy|unit value − unit bid|
≤ 0.05,
unit value(16)

and the number of eﬃciency rates each of which satisfies
eﬃciency rate ≥ 0.95.

(17)

We say that a unit bid obeys 95% truth-telling when it satisfies (16) and that an
auction outcome is 95% eﬃcient when the rate of eﬃciency satisfies (17). The next
observation is similar to the one confirmed in the numerical experiment.
Observation 2 In the subject experiment, there was no significant diﬀerence in
number of bids that obey 95% truth-telling between GBA and VCG, whereas there
was clear diﬀerence in number of 95% eﬃciency between GBA and VCG.
14

Table 6 shows the numbers of 95% truth-telling unit bids and 95% eﬃciency
observed in each pair of 2 sessions. The sample size is 1200 for 95% truth-telling
unit bids and it is 80 for 95% eﬃciency. The p-values for the Fisher exact test
(Fisher test) are reported under each panel which corresponds to truth-telling andeﬃciency. The null hypotheses on 95% truth-telling could not be rejected at the 5%
significance level with both data taken in 2014 and in 2016. The null hypotheses on
95% eﬃciency was rejected at the 5% significance level with both data taken in 2014
and in 2016. Therefore, Observation 2 is consistent with the result in the numericalexperiment. Observation 2 also says that in the subject experiment there was no
significant diﬀerence in number of bids that obey “almost” truth-telling between
GBA and VCG, although it is not clear in theory that each bidder will truthfullytell his or her unit valuations by bidding in GBA.
Table 6: Numbers of 95% truth-telling bidding and in 95% eﬃciency.
truth-tellingsessions 1-2
p-value (Fisher)sessions 3-4
p-value (Fisher)sessions 5-6
p-value (Fisher)sessions 7-8
p-value (Fisher)eﬃciency

GBA

VCG

GBA

VCG

996

964

57

71

0.1019963

975

0.5690498

527

0.23184444260.47040.009548

680.000757

69

0.03255270

0.0014

Finally, we report the regression results on the subjects’ bidding behavior. For
each bidder, each unit valuation is drawn independently of the other unit valuations.
We thus analyze the data unit by unit. If the absolute value of a unit valuation minusa unit bid falls within 5% of all those absolute values, we then dropped the dataas an outlier for our regression analysis. Tables 7 and 8 show the regression resultswith the data taken in 2014 and 2016, respectively. Figures 4 to 7 depict unit
valuations and unit bids observed in 2014 and 2016, respectively. The coeﬃcientson valuations were less than one and they are statistically significant, except in thesession for VCG conducted in 2014.

15

Observation 3 In the subject experiment, subjects would underbid, except in thesessions for VCG in which human bidders bid against truth-telling machine bidders.

Table 7: Results of regression analysis in 2014.
GBA# of units

1

2

3

4

5

Constant-2.5966-3.2360-0.3177-1.8116-2.0598

p-value

0.03700.02100.79300.07900.0140

Valuation

0.98320.98500.95000.98500.9982p-value< 0.0001< 0.0001< 0.0001< 0.0001< 0.0001

R-squared

0.91400.89800.90500.93500.9590

VCG

250# of units

1

2

3

4

5

Constant-1.6190-1.0880-1.1676-0.9239-0.3216

p-value

0.02700.04500.01900.14400.7950

Valuation

1.00291.00691.01141.00851.0233p-value< 0.0001< 0.0001< 0.0001< 0.0001< 0.0001

R-squared

0.96600.98000.98400.97100.9030

250

unit1
unit2
unit3
unit4
unit5

200

unit1
unit2
unit3
unit4
unit5

200

bid

150

bid

150

100

100

50

50

0

0

50

100

valuation

150

200

0

250

Figure 4: GBA in 2014.

0

50

100

valuation

150

200

Figure 5: VCG in 2014.

16

250

Table 8: Results of regression analysis in 2016.
GBA# of units

1

2

3

4

5

Constant-1.1523-3.6660-2.8788-4.0178-6.9879

p-value

0.69800.16200.31100.14900.0000

Valuation

0.86180.90630.88480.9154

0.9761p-value< 0.0001< 0.0001< 0.0001< 0.0001< 0.0001

R-squared

0.70600.77200.72200.75800.8700

VCG

250# of units

1

2

3

4

5

Constant

0.7320-6.3762-6.5492-5.3207-6.4748

p-value

0.84200.04400.04000.09600.0050

Valuation

0.78570.90300.92190.91730.9693p-value< 0.0001< 0.0001< 0.0001< 0.0001< 0.0001

R-squared

0.55900.69400.71300.70600.8170

250

unit1
unit2
unit3
unit4
unit5

200

unit1
unit2
unit3
unit4
unit5

200

bid

150

bid

150

100

100

50

50

0

0

50

100

valuation

150

200

0

250

Figure 6: GBA in 2016.

0

50

100

valuation

150

200

Figure 7: VCG in 2016.

As for individual bidding behavior, GBA and VCG show a sharp contrast whena human bidder competes against machine bidders; underbidding was observed in
GBA, while overbidding was observed in VCG.

17

250

5

Final remarks

There is little literature on subject experiments which investigated how approximation algorithms of the VCG mechanism work in the multi-unit non-reverse auctions
to which Kothari et al. (2005) referred. Kagel and Levin (2001), for instance, studied subjects’ bidding behavior in multi-unit auctions, but they imposed a uniform
price on all units of the item.3 We thus carefully prepared for the experimental
design. In this paper, it is assumed that for all bidders, each unit valuation is drawn
independently of the other unit valuations. As is mentioned in Section 1, we foundthat it was better for us to do so from a result of a preliminary experiment.
The preliminary experiment was conducted also at the University of Tsukuba.
We had 4 sessions on February 13 and 14 in 2015. Each session consists of 20 rounds
in total, and 2 sessions are paired; In a session unit valuations were drawn in random
order in the first 10 rounds and they were drawn in monotone non-increasing order inthe second 10 rounds, and the order of the display of unit valuations was reversed inanother session. The other part of the experimental design was completely the sameas the one described in this paper. In the data taken from last 5 rounds in eachtreatment, the average rate of seller’s revenue was 0.977 with standard deviation
0.0132 when unit valuations are drawn in random order, whereas it was 1.0564 withstandard deviation 0.2581. We will show more detail comparisons between those
two treatments in another paper.
At the end, we leave two remarks for future investigation. Chen and Takeuchi(2010) reported underbidding in VCG, although they studied combinatorial auctions. Kagel et al. (2001) conducted an experiment in which a human bidder withflat demand for two units competes against machine bidders each demanding a single unit, and they reported overbidding of each human bidder for both units. It isinteresting that Observation 3 is similar to these results, although the direct comparison to them is not appropriate. The other remark is on Observation 2; Not only
in VCG but also even in GBA, the number of 95% truth-telling unit bids in theenvironment of a human budder and two machine bidders is about twice as many as
the one in the environment of all human bidders, although it is not clear in theory
whether each bidder has an incentive to submit his or her true unit valuations in
GBA. Thus, it is an open question to identify some reason why subjects learned
such a bidding behavior.
3

Kagel and Levin (2016) is a comprehensive survey of experimental results in various auctions

and mechanisms. Dobzinski and Nisan (2015) showed the latest theory in multi-unit auctions.

18

References
Ausubel, L. M., 2004. An eﬃcient ascending-bid auction for multiple objects. American Economic Review 9, 1452-1475.
Chen, Y., Takeuchi, K., 2010. Multi-object auctions with package bidding: An experimental comparison of iBEA and Vickrey. Games and Economic Behavior 68,
557-569.
Dobzinski, S., Nisan, N., 2015. Multi-unit auctions: Beyond Roberts. Journal of
Economic Theory 156, 14-44.
Dyer, M. E., 1984. An O(n) algorithm for the multiple-choice knapsack linear program. Mathematical Programming 29, 57-63.
Kagel, J. H., Levin, D., 2001. Behavior in multi-unit demand auctions: Experimentswith uniform price and dynamic Vickrey auctions. Econometrica 69, 413-451.
Kagel, J. H., Kinross, S., and Levin, D.. 2001. Comparing eﬃcient multi-object
auction institutions. mimeo., Ohio State University.
Kagel, J. H., Levin, D., 2016. Auctions: A survey of experimental research. In
Handbook of Experimental Economics vol. II, Kagel, J. H., Roth, A. E. (eds.)
Princeton University Press, 563-637.
Kothari, A., Parkes. D. C., Suri, S., 2005. Approximately-strategy proof andtractable multi-unit auctions. Decision Support System 39, 105-121.
Takahashi, S., Shigeno, M., 2011. Approximation algorithms for a winner determination problem of single-item multi-unit auctions. JSIAM Letters 3, 29-32.

Appendix: Examples in the instruction
In the instruction, we explained GBA and VCG with the following examples.

GBA
Item allocation problem: 5 steps in total. Unit valuations are given as below. Bidders are asked to bid per unit for each unit.

19

!

!

!!

"!

#!

$%&&'(!!!

)*+,*-%./!

012!!

312"!

442#!

5%&!

642!!

442"!

712#!

)*+,*-%./!

712!!

612"!

342#!

5%&!

712!!

3#2"!

342#!

$%&&'(!"!

Fig. 1

1. Find the highest unit bid. Give “tentatively” the unit to the highest unit
bidder.
2. Update the other unit bids of the highest unit bidder in the following way;
The highest unit bid is 75 cast by bidder 1 for 1 unit.
55 ∗ 2 − 75 ∗ 1= 35(2 − 1)40 ∗ 3 − 75 ∗ 1• updated unit bid for 3 units == 22.5.
3−1• updated unit bid for 2 units =

!

!

!!

"!

#!

$%&&'(!!!

)*+,*-%./!
5%&!

012!!
!

312"!
#42"!

442#!
""642#!

$%&&'(!"!

)*+,*-%./!

712!!

812"!

342#!

5%&!

712!!

3#2"!

342#!

Fig. 2

3. Find the highest (updated) unit bid. Give tentatively the corresponding unit
to the highest (updated) unit bidder.
This bidder is also called a “tentative winner”.
4.

• If all units are just assigned, the assignment is then implemented.
• If some units are not assigned, go to step 2.
• If the number of units is less than the sum of assigned units (there is the“excess demand”), then go to step 5.
The highest (updated) unit bid is 65 cast by bidder 2 for 3 units. In the firstround, bidder 1 was assigned 1 unit as a tentative winner, and thus there is
the excess demand. Thus, go to step 5.

5. Choose such an allocation that maximizes the total amount of bids among theallocations of tentative winners.
• 1 unit to bidder 1 and 2 units to bidder 2.
Total amount of bids = 75 ∗ 1 + 63 ∗ 2 = 20120• 0 unit to bidder 1 and 3 units to bidder 3.
Total amount of bids = 65 ∗ 3 = 195
Choose Allocation 1.

GBA: payment
Payment Determination: in the same way as in Exact VCG.
payment of bidder i (winner) =(total amount of bids in the auction that excludes bidder i:
65*3 for bidder 1, 75*1+35*2 for bidder 2)− (total amount of bids in the original auction)+ (bidder i’s bid for the unit assigned to i)(Allocation 1) · · · 1 unit to bidder 1 unit and 2 units to bidder 2.
• payment of bidder 1 = (65 ∗ 3) − 201 + (75 ∗ 1) = 69
• payment of bidder 2 = (75 ∗ 1 + 35 ∗ 2) − 201 + (63 ∗ 2) = 70

Exact VCG
!

!

!!

"!

#!

$%&&'(!!!

)*+,*-%./!

012!!

312"!

442#!

5%&!

612!!

442"!

412#!

)*+,*-%./!

712!!

612"!

342#!

5%&!

712!!

312"!

342#!

$%&&'(!"!

Fig. 3Choose such an allocation that maximizes the total amount of bids among all
possible allocations; (0, 0): 0, (1, 1): 70*1+40*1=110 (1, 0): 70*1=70, (2, 0):55*2=110, (3, 0): 50*3=150, (0, 1): 40*1=40, (0, 2): 60*2=120: (0, 3): 65*3=195,(1, 2): 70*1+60*2=190, (2,1): 55*2+40*1 =150.
Choose (0, 3). The total amount of bids is 195, which is less than the value GBA
gives, i.e., 201.

21