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

ISSN 2434-9445

2020 年 7 月

RISS Discussion Paper Series
No.88 July, 2020

An Experimental Study of VCG Mechanism for
Multi-unit Auctions: Competing with Machine Bidders

Satoshi Takahashi, Yoichi Izunaga, Naoki Watanabe

文部科学大臣認定

共同利用・共同研究拠点

関西大学ソシオネットワーク戦略研究機構
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 Experimental Study of VCG Mechanism for
Multi-unit Auctions: Competing with Machine Bidders
Satoshi Takahashi∗

Yoichi Izunaga†

Naoki Watanabe‡

October 22, 2020

Abstract
This paper complements the main experimental result reported in Takahashi et al.
(2019) in order to understand subjects’ bidding behavior under the VCG mechanism
more deeply. In this experiment, there are two types of appearance of information aboutbidders’ valuations of the item given to them and the bids they are asked to submit:
One is unit valuations and the unit bids themselves (Appearance 1) and the other isunit valuations and the unit bids multiplied by the number of units (Appearance 2).
When subjects compete with truth-telling machine bidders in multi-unit auctions, we
confirmed that in Appearance 1, they choose truth-telling bids more frequently, andeﬃcient allocations are observed more frequently, as compared to the situation where
they compete with human bidders. This result suggests a possibility that in Appearance
1 subjects learn their dominant strategy not by practicing with other subjects but
by practicing with machine bidders in experiments for multi-unit auctions, although
the item allocation and payment determination under the VCG mechanism is neverintuitively understandable to subjects.
Keywords: multi-unit auction, VCG mechanism, experiment, human and machinebidders, truth-telling bids
JEL Classification: C92, D44, D82∗

Graduate School of Informatics and Engineering, The University of Electro-Communications, Chofu,

Tokyo, Japan. E-mail: stakahashi@uec.ac.jp†
Faculty of Engineering, Kanagawa University, Kanagawa, Yokohama, Kanagawa, Japan.

E-mail:izunaga@kanagawa-u.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 theory, Vickrey-Clarke-Groves mechanism (VCG) attains allocative eﬃciency by inducing
bidders to represent their true valuation for each unit of the item auctioned oﬀ. However,the VCG suﬀers from its computational intractability when the number of units of theitem to be traded is large. This drawback is one of the reasons why we have not found
any report that VCG was used in practice, although there are many practical examples ofmulti-unit auctions: oil and timber sales, flower markets, spectrum auctions, etc. Thus, theapproximation algorithms that reduce the computational complexity were proposed by Dyer
(1984) and Kothari et al. (2005). Based on the Dyer’s work, Takahashi and Shigeno (2011)
developed a greedy-based approximation (GBA) algorithm that is much faster than VCG
in computation time. VCG has another drawback; it is diﬃcult for bidders to intuitively
infer how it allocates the item with their own bids. In the GBA, however, a bidder who
submits the highest unit bid is given priority for obtaining the units of the item, and thus
bidders can infer how it allocates the item with their own bids more easily.
In order to confirm the practical performance of GBA, Takahashi et al. (2018) conducteda subject experiment where five units of an identical item were auctioned oﬀ to threebidders. They reported that there was no significant diﬀerence in seller’s revenue between
VCG and GBA, but VCG attained higher allocative eﬃciency than GBA; on average, theeﬃciency rate was 97.37% in VCG and it was 93.65% in GBA. These eﬃciency rates in VCG
were remarkably higher than expected, even though it is diﬃcult for subjects to intuitively
understand how the VCG works. There are, unfortunately, few papers on the experimentsof the VCG for multi-unit auctions, and thus we cannot compare our result with others in
diﬀerent sessions. The eﬃciency rates in VCG were, however, not higher in experimentsfor other types of auction (Kagel and Levin, 2016), as compared to our observation. Whatfactors generate higher allocative eﬃciency in the VCG for multi-unit auctions?
To seek for the answer to this question, Takahashi et al. (2019) next investigated whether
the performance of the VCG is robust against changes of appearance of information in whichbidders submit “total bids” confirming their “total valuation” for each unit. Their main
result is that there was no significant diﬀerence on average in either allocative eﬃciency
or seller’s revenue between those two types of appearance of information. Rather, for each2

appearance of information, there was a significant diﬀerence in subjects’ bidding behavior
between diﬀerent display types of draws of unit valuations. The average rates of eﬃciency
were, again, more than 90% in any sessions. The rates of 95% approximately truth-tellingbids were, however, 31.8-43.1% in those sessions, which implies that many eﬃcient allocations were not generated even by approximately truth-telling bids. Do we not need toinduce bidders to report their true preferences in order to attain the allocative eﬃciency?
When subjects compete with human bidders, it may be diﬃcult for them to realize thattruth-telling is their dominant strategy, because they do not necessarily report their true
preferences. Let us confirm this point introducing truth-telling machine bidders.
Main Hypothesis: When subjects compete with truth-telling machine bidders in multiunit auctions, the VCG mechanism induces subjects to choose truth-telling bids more frequently, and eﬃcient allocations are observed more frequently, as compared to the situation
where they compete with human bidders.
We test Main Hypothesis under two types of appearance of information about bidders’valuations of the item given to them and the bids they are asked to submit: One is unit
valuations and the unit bids themselves (Appearance 1) and the other is unit valuations
and the unit bids multiplied by the number of units (Appearance 2), Takahashi et al.
(2019) reported that the VCG generated no significant diﬀerence in the allocative eﬃciency
between Appearances 1 and 2. In which appearance is the allocative eﬃciency attained
more frequently?
We had the following observations. (1) In seller’s revenue there was no significant difference on average but in allocative eﬃciency there was a significant diﬀerence on average
between Appearance 1 and Appearance 2. (2) Approximately truth-telling bids were more
frequently chosen by subjects and approximately eﬃcient allocations were more frequently
observed in Appearance 1 than in Appearance 2. (3) When opponents are truth-tellingmachine bidders in Appearance 1, subjects chose approximately truth-telling bids more frequently and approximately eﬃcient allocations realized more frequently, as compared to thecase where opponents were human bidders. There were no such diﬀerences in Appearance
2. Thus, Main Hypothesis was confirmed in Appearance 1. This is our main result.

3

The main result suggests a possibility that in Appearance 1 subjects learn their dominant strategy not by practicing with other subjects but by practicing with machine bidders
in experiments for multi-unit auctions, although the item allocation and payment determination under the VCG mechanism is never intuitively understandable to subjects.
The rest of this paper is organized as follows. Section 2 formally describes the VCG
mechanism for multiunit auctions. A numerical example of the mechanism is given in
Appendix 2. Section 3 describes the experimental design, and Section 4 shows the results.
Section 5 closes this paper with some remarks.

2

VCG Mechanism

From a computational aspect, the VCG mechanism is formulated in the following way.
There is a seller who wishes to sell M (< ∞) units of an identical item and solicits bids fromn(< ∞) buyers each of whom can purchase up to M units of the item. Let N = {1, ..., n}be the set of all buyers (bidders). For each bidder i ∈ N , denote his or her anchor values on
the quantity 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 . For every bidder i ∈ N , d0i = 0 and dℓi i ≤ M . Let ℓ = i∈N ℓi .
iDefine a function Bi : R+ → R for each i ∈ N by{
bki · y (dk−1< y ≤ dki , k = 1, ..., ℓi ),i
Bi (y) =0(y = d0i , y > dℓi i ).

(1)

The unit bids represent the gradients of this function and the anchor values stand forits discontinuous points. For each bidder i ∈ N , denote his or her unit valuations by{vik | k = 1, ..., ℓi } and define another 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. An item allocation problem (AP )B is to find allocations that maximize the total
amount of bids is formulated by4

(AP )B maximize
subject to

∑
i∈N
∑

Bi (xi )xi ≤ Mi∈N

xi ≥ 0 (∀i ∈ N ).
This item allocation problem is faced with computational intractability, i.e., (AP )B is known
to be N P-hard. Another problem (AP )V is formulated in the same way by(AP )Vmaximizesubject to

∑
i∈N
∑

Vi (xi )xi ≤ Mi∈N

xi ≥ 0 (∀i ∈ N ),to find eﬃcient allocations that maximize the total amount of valuations. When there are
two or more allocation in each of which the total amount of bids is maximized, one of those
allocations is chosen at random as the solution of (AP )B .
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 (AP )−j
B withthe set of bidders N −j = N \ {j}.
(AP )−jB∑maximize−ji∈N∑

subject toBi (xi )xi ≤ Mi∈N −jxi ≥ 0 (∀i ∈ N −j ).
In the VCG mechanism, bidder j’s payment pj is determined by

pj =

∑

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

(3)i∈N −jUnder this payment scheme, it is the dominant strategy for each bidder to truthfully bid hisor her unit valuations; Thus, the solutions of (AP )B maximize the total sum of valuationsin (AP )V as well, which leads to allocative eﬃciency.

5

3

Experimental Design

3.1

Basic Setup

The basic setup of this experiment is the same as that of Takahashi et al. (2019). This
experiment is computerized, using software (cgi script) that is coded in Python. We conducted 4 sessions. Each session consists of 20 rounds. In each round, 5 units of a virtual
item are auctioned oﬀ to 3 bidders, where for each 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. For eachbidder i ∈ N , his or her unit valuations, {vik | k = 1, ..., ℓi }, are independently and uniformly distributed over the integers between 1 and 200. Bids are made using non-negative
integers.
In 2 out of 4 sessions, at the beginning of each round, each bidder i ∈ N is given his
or her unit valuations {vik | k = 1, ..., ℓi } by the experimenter, which are privately shown
only on his or her computer screen (Appearance 1). Then, each bidder i submits his or her
unit bids {bki | k = 1, ..., ℓi } privately to the experimenter. The computer determines the
allocation of the item and bidders’ payments according to (AP )B and (3). In the other 2
sessions, each bidder i is given his or her valuations {vik · k | k = 1, ..., ℓi } privately andsubmits his or her bids {bki · k | k = 1, ..., ℓi } (Appearance 2). When k units of the item
are allocated to bidder i, he or she receives the points in the amount vik · k minus hisor her payment, which is shown to bidder i through his or her computer screen in bothAppearances 1 and 2. Table 1 shows the diﬀerence in appearance of the information given
to bidder i in the case of 5 units, as an example.
In each round, there is a 120-second time limit for submitting bids. If no bidder bids
within the time limit, then all three bidders obtain zero points at that round. If multiple
allocations attain the maximum total amount of bids, then one allocation is chosen at
random. The units assigned to a bidder and his or her payment are shown to the bidderfor 5 seconds at the end of each round. The cumulative points of bidders are not shown tothem, and subjects were prohibited to take notes.
This paper follows the paired setting used in an auction experiment conducted by Engelmann and Grimm (2009). For each appearance of information, 2 sessions are paired in thisexperiment; In one session, each unit valuation of the item is drawn “at random” for each6

Table 1: Diﬀerent appearance of information.
vik shown; bki bid

Appearance 1# of units
bidder i

1

2

3

4

5

valuation

80×1

60×2

55×3

43×4

77×5

bid

70×1

55×2

50×3

43×4

72×5

vik · k shown; bki · k bid

Appearance 2# of units
bidder i

1

2

3

4

5

valuation

80

120

165

172

385

bid

70

110

150

172

360

bidder and given to him or her as it is in the first 10 rounds, while in the second 10 rounds
the values drawn at random are reordered in the monotone non-increasing (“decreasing”)
order from k = 1 to k = 5 and given to each bidder as his or her unit valuations in thatorder. The display types of draws are reversed between the first and second 10 rounds inthe other paired session. Every subject thus bids under both display types in the samesession. In the analysis, we should be careful of the eﬀect of the order of the display types
on the results.
The instruction is given to the subjects at the beginning of each session, where how
the VCG mechanism works is demonstrated using an example (attached in Appendix 2).
The example is carefully made so that it does not imply the dominant strategy of theauction game. Subjects are informed that they will be paid according to the total points
they obtain 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 the session they participated in with thepre-determined exchange rate in addition to the show-up fee. The exchange rate was 1
point = 1 JPY and the show-up fee was 1500 JPY. Subjects play 1 round for practice tofamiliarize themselves with the software, before proceeding to each set of 10 rounds in thesession they participate in.

3.2

Session Details

This experiment was run at the University of Tsukuba in Japan, and 4 sessions were conducted in January 2018. The subjects were undergraduate students recruited from all over7the campus, but economics majors were excluded. Engineering majors were the largest
subgroup of our subjects. In total, 23 male students and 9 female students participated inthis experiment. There was no subjects who had participated in the sessions for multi-unit
auctions conducted in 2015 and 2017. Subjects were randomly assigned to a session. Eachsession involves 8 groups of 3 bidders, one of whom is a human bidder. Subjects were notinformed of truth-telling bids made by machine bidders. The units assigned to machinebidders as well as their payments and points were not shown to subjects’ monitor.
At the beginning of each session, each subject was randomly assigned to a group. In
a companion experiment which was run in 2015 and 2017 (Takahashi et al., 2019), eachsession involves 8 groups of 3 subjects. At the beginning of each round, all subjects wererandomly re-grouped into 8 groups by a computer. Subjects are not informed of who arein the same group with.
Upon arrival at the laboratory, subjects were provided with a written instruction, andthen the experimenter read it around.1 In all sessions, the same experimenter read the
instruction and provided simple review questions to make subjects reconfirm how the experiment proceeds. Subjects could ask questions about the instruction as well as the review
questions and the experimenter gave the answers to those questions privately.
Any communication among subjects was strictly prohibited; their interactions were only
through the information shown on their computer monitors. Each session lasted about 100
minutes including the time for giving the instruction. In no case did subjects fail to makea bid within the time limit. The features of the experimental sessions are summarized inTable 2.

4

Results

We analyze the data taken from the last 5 out of 10 rounds in each display type of draws
in order to exclude the data that might contain outcomes of behavior chosen when subjects
were still learning something on bidding strategies. There were no multiple allocations withthe same maximum total amount of bids. Even if we analyzed the data taken from the last
5 rounds out of the first 10 rounds and those taken from the last 5 rounds out of the second
1

The complete instruction is attached in Appendix 2.

8

Table 2: Features of the experimental sessions.
sessionappearance

display ofshow-uppoint-to-# ofsessionavg. pointno.

of info.

draws

fee (JPY)

JPY ratio

subj.

date

per subject

1

2

at random

1500

1.0

8

Jan.22496.541

2

descending

2

2

descending2

2

at random3

1

at random

3

1

descending

4

1

descending

4

1

at random1127.89
1500

1.0

8

Jan.22876.87346.65

1500

1.0

8

Jan.23600.121285.73

1500

1.0

8

Jan.231306.58
527.61

Note: The display type of draws used in the first 10 rounds is listed first in each session with the samesession number. For a companion experiment, at the university of Tsukuba, 2 sessions for Appearance
1 were conducted in February 2015 and 2 sessions for Appearance 2 were conducted in January 2017, ineach session of which 24 subjects participated.

10 rounds separately, we obtained similar results as far as the allocative eﬃciency, seller’s
revenue, and the number of approximately truth-telling bids. The data were thus merged
for each display type of draws to increase our sample size. We do not consider bidding
behavior for diﬀerent subjects’ attributes (gender, age, and academic major), because thesample size is not large enough for that purpose.
Let x̂ = (x̂1 , x̂2 , . . . , x̂n ) be an observed allocation. The rate of eﬃciency is defined by∑i∈N Vi (x̂i ).
(4)the optimal value of (AP )V
The rate of seller’s revenue (profit) is defined by
the total amount of observed payments,(5)
the total amount of optimal payments∑
where the total amount of optimal payments is represented by j∈N pj and pj is calculatedwith (3) for each bidder j ∈ N under the assumption that every bidder truthfully bids
his or her (unit) valuations. The unit valuations were diﬀerent across diﬀerent rounds indiﬀerent sessions, and thus we analyze those rates.

9

Tables 3 and 4 show the average rates of eﬃciency and seller’s revenue for each auction(appearance of information and display type of draws) as well as their standard deviations.
The sample size is 80 (5 rounds, 8 groups, 2 sessions) for each auction, which is the sameas the sample size in Takahashi et al. (2019). The p-values for the two-sided permutation
test (perm.) are also reported in those tables, where in each display type of draws thenull hypothesis is that there is no diﬀerence in those averages between Appearance 1 andAppearance 2, which is rejected at the 5% significance level.
Table 3: The rates of eﬃciency.
display of draws

at random

decreasing

appearance of info.

Appearance 1

Appearance 2

Appearance 1

Appearance 2

mean

0.98920.9351

0.9987

0.9765st.dev.

0.02040.06010.00220.0251p-value (perm.)

0.01080.0016

Note: The p-values for the two-sided permutation test are listed in this table. The null hypothesis isrejected at the 5% significance level.

Table 4: The rates seller’s revenue.
display of draws

at random

decreasing

appearance of info.

Appearance 1

Appearance 2

Appearance 1

Appearance 2

mean

0.99661.00141.0101

1.0668st.dev.

0.01250.06930.03830.1487p-value (perm.)

0.83110.2875

Note: The p-values for the two-sided permutation test are listed in this table. The null hypothesis isrejected at the 5% significance level.

Observation 1 (1) Eﬃcient allocations were on average observed significantly more frequently between Appearance 1 and Appearance 2 for each display type of draws. (2) Inseller’s revenue there was no significant diﬀerence on average between Appearance 1 andAppearance 2 for each display type of draws.
In the case where the auctions were conducted by 3 human bidders, Observation 1
in Takahashi et al. (2019) states that for there was no diﬀerence on average in either
10allocative eﬃciency or seller’s revenue between Appearance 1 and Appearance 2 for eachdisplay type of draws. At that time, the eﬃciency rates in Appearance 1 were 0.9306 (atrandom) and 0,9172 (decreasing), whereas in Appearance 2 they were 0.9378 (at random)and 0.9337. Thus, when we introduced 2 machine bidders, the eﬃciency rates were improvedin Appearance 1.
The VCG mechanism in theory induces bidders to truthfully bid their own valuationsof the item for each unit, which is a dominant strategy for every bidder. Figure 1 - Figure
8 in Appendix 1 depict bid plots observed in each session and show that those bids wereapparently nearer to the truth-telling bids in Appearance 1 than in Appearance 2. This
point is a major factor with which we obtained Observation 1 (1), in contrast to the resultswith 3 human bidders. We thus next proceed to counting the number of bids that areapproximately truth-telling and the number of allocations that are approximately eﬃcient.
We say that a bid for a unit of the item is approximately truth-telling when it satisfies|unit valuation − unit bid|
≤ 0.05
unit valuation(6)

and that an allocation is approximately eﬃcient when it satisfies
the rate of eﬃciency ≥ 0.95.

(7)

Table 5 presents the numbers of approximately truth-telling bids and approximately
eﬃcient allocations observed in the last 5 periods. For each appearance of information, thesample size is 400 (5 rounds, 8 bidders, 5 units, 2 sessions) for approximately truth-tellingbids and it is 80 (5 rounds, 8 auctions, 2 sessions) for approximately eﬃcient allocations ineach display type of draws. The p-values for the one-sided Fisher exact test (Fisher) arealso reported, where for each display type of draws the null hypothesis is that the number
of approximately truth-telling bids (approximately eﬃcient allocations) in Appearance 1 isless than or equal to the number of those bids in Appearance 2, which is rejected at the 5%
significance level.
Observation 2 For each display of draws, approximately truth-telling bids were chosen by
subjects significantly more frequently and approximately eﬃcient allocations were observed
significantly more frequently in Appearance 1 than in Appearance 2.
11

Table 5: Numbers of approximately truth-telling bids and approximately eﬃcient allocations.
truth-tellingeﬃciency

appearance of info.

Appearance 1

Appearance 2

Appearance 1

Appearance 2

at random

232

148

78

63

p-value (Fisher)< 0.0001

descending214

p-value (Fisher)

0.0002119

74

60< 0.0001

0.0023

Note: The p-values for the one-sided Fisher exact test are listed in this table. The null hypothesis isrejected at the 5% significance level.

By Observation 2, we expect that in Appearance 1, when subjects compete with truthtelling machine bidders, they choose their dominant strategy more frequently, as comparedto the case where they compete with human bidders.
Table 6 presents the observed numbers of approximately truth-telling bids with thosenumbers observed in 2015 and 2017 (Takahashi et al., 2019). For each appearance of
information, the sample size of the data taken in 2015 and 2017 is 1200 (5 rounds, 24 bidders,
5 units, 2 sessions) in each display type of draws. The p-values for the two-sided Fisher
exact test (Fisher) are also reported, where for each display of draws the null hypothesis isthat there is no diﬀerence in number of approximately truth-telling bids between the two
types of appearance of information.
Table 6: Numbers of approximately truth-telling bids
display of draws

at random

descending

opponent bidders

vs. machines

vs. subjects

vs. machines

vs. subjects

Appearance 1

232/400

517/1200

214/400

450/1200p-value (Fisher)
Appearance 2
p-value (Fisher)< 0.0001
148/400

493/1200
0.1576< 0.0001
119/400

381/1200
0.4933

Note: The p-values for the two-sided Fisher exact test are listed in this table. The null hypothesis
is rejected at the 5% significance level. In Appearance 1, the p-values for the one-sided test are alsoless than 0.001. The sample size is 400 for this experiment and it is 1200 for a companion experiment,
respectively.

12

Table 7 shows the observed numbers of approximately eﬃcient allocations with thosenumbers observed in 2015 and 2017 (Takahashi et al., 2019). For each appearance of
information, the sample size is 80 (5 rounds, 8 auctions, 2 sessions) in each display type ofdraws. The p-values for the two-sided Fisher exact test (Fisher) are also reported, wherefor each display type of draws the null hypothesis is that there is no diﬀerence in number
of approximately eﬃcient allocations between the two types of appearance of information.
Table 7: Numbers of approximately eﬃcient allocations
display of draws

at random

descending

opponent bidders

vs. machines

vs. subjects

vs. machines

vs. subjects

Appearance 1

78

60

74

57

p-value (Fisher)
Appearance 2
p-value (Fisher)< 0.0001
63

0.000860

0.708060

540.3826

Note: The p-values for the two-sided Fisher exact test are listed in this table. The null hypothesis isrejected at the 5% significance level. In Appearance 1, the p-values for the one-sided test are also lessthan 0.001.

Observation 3 When opponents are truth-telling machine bidders, for each display type ofdraws in Appearance 1, subjects chose approximately truth-telling bids more frequently andapproximately eﬃcient allocations realized more frequently, as compared to the case where
opponents were human bidders. There were no such diﬀerences for each display type ofdraws in Appearance 2.
Observation 3 may imply that subjects are confused by behavior of human bidders. We
eventually reached the following result.
Main Result: Main Hypothesis was confirmed when unit valuations are shown to subjects
and their unit bids are submitted in multi-unit auctions.
Main Result suggests a possibility that in Appearance 1 subjects learn their dominant
strategy by practicing with machine bidders in experiments for multi-unit auctions, although the item allocation and payment determination under the VCG mechanism is neverintuitively understandable to subjects.
13

5Final Remarks

In economic experiments, the instructors should not suggest desirable actions to subjects.
The purpose of those experiments are, in many cases, to verify various theoretical results or
to find some behavioral features of subjects. If subjects received such an instruction in anexperiment, the purpose of the experiment would then be changed to testing whether they
could believe that the suggested actions were the best ones for themselves. In some cases,
however, it is diﬃcult for subjects to infer the outcomes of their own choice of behavior,when, in particular, those experiments are conducted for verifying the theoretical results
derived in game theory and mechanism design. In fact, for example, It is diﬃcult for
subjects to intuitively understand the item allocation and payment determination under
the VCG mechanism. What we showed by Result 1 is that there is a type of appearance of
information provided to subjects in which they can learn their dominant strategy, not bypracticing with other subjects but by practicing with machine bidders for some periods.
Figures 1 to 8 plot unit valuations and unit bids observed in our sessions. The data
were taken from the last 5 out of 10 rounds in each display type of draws. Tables 8 and 11
show the regression results for the corresponding sessions. As is seen in Table 9, there wasa subject who took an extraordinary biding behavior in Appearance 2. In Appearance 1,some coeﬃcients on valuations were less than one but others were more than one, regardlessof the display types of draws. Thus, we did not have clear evidence for subjects’ overbidding
or underbidding when subjects compete with truth-telling machine bidders.
When subjects compete with human bidders, on the other hand, Observation 3 in Takahashi et al. (2019) states that for both Appearance 1 and Appearance 2, subjects underbid
when unit valuations were drawn at random and shown to them as they were, whereas
they did not necessarily do so when values drawn at random were reordered in monotone
non-increasing order and given to them as their unit valuations.
Kagel et al. (2001) conducted an experiment in which a human bidder with a flat demand
for two units competes against machine bidders each demanding a single unit, and theyreported overbidding of each human bidder for both units. It is not appropriate to makea comparison with their result, but our regression analysis showed that subjects overbid
for some units when each draw of unit valuations was reordered in the monotone non-14

increasing order. As noted above, on the other hand, we sometimes observed that subjects’
underbidding. What are the major factors that induce subjects to overbid or underbid? As
was mentioned, there are few papers on the experiments of the VCG in multi-unit auctions.2
We need to further investigate how the VCG mechanism work in multi-unit auctions.
Finally, we need to reconfirm the same result we observed at diﬀerent experimental sites
to ensure the robustness. This paper simply provided some preparations to investigate how
the VCG mechanism work in multi-unit auctions for the future research.

Acknowledgement
The authors wish to thank Toru Suzuki for their excellent research assistance.

Funding
This research was supported by JSPS Grant-in-Aid for Young Scientists (B) 26870200
and Grant-in-Aid for Scientific Research (B) 15H02972 and 20H04146 (Takahashi), andthe Japan Center for Economic Research, ORA-Plus research project “BEAM”, and JSPS
Grant-in-Aid for Challenging Research (Pioneering) 17H06190 (Watanabe).

Compliance with Ethical Standards
Conflict of Interest
The authors declare that they have no conflict of interest.
Ethical Approval
All procedures performed in studies involving human participants were in accordance withthe ethical standards of the institutional and/or national research committee and with the1964 Helsinki declaration and its later amendments or comparable ethical standards. This
article does not contain any studies with animals performed by any of the authors.
2

In a situation where two units of an item auctioned oﬀ to two bidders, Engelmann and Grimm (2009)

compared the performances of a uniform-price sealed-bid auction, a uniform-price clock auction, a discriminatory auction, a static Vickrey auction, and a dynamic Vickrey auction, including a literature review onlaboratory experiments of multi-unit auctions. Among those studies, Kagel and Levin (2001) was a seminal
paper to study the demand reduction in uniform-price auctions. Thereafter, experiments for multi-unit
auctions have been focused on the demand reduction under uniform-price.

15

References
Dyer, M. E., 1984. An O(n) algorithm for the multiple-choice knapsack linear program,Mathematical Programming 29, 57-63.
Engelmann, D., Grimm, V., 2009. Bidding behavior in multi-unit auctions – An experimental investigation. The Economic Journal 119, 855-882.
Kagel, J. H., Levin, D., 2001. Behavior in multi-unit demand auctions: Experiments withuniform 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 Handbookof 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 and tractable
multi-unit auctions. Decision Support System 39, 105-121.
Takahashi, S., Izunaga, Y., Watanabe, N., 2018. An approximation algorithm for multiunit auctions: Numerical and subject experiments. Operations Research and Decisions
28, 75-95.
Takahashi, S., Izunaga, Y., Watanabe, N., 2019. VCG mechanism for multi-unit auctions
and appearance of information: A subject experiment. Evolutionary and Institutional
Economics Review 16, 357-374.
Takahashi, S., Shigeno, M., 2011. Approximation algorithms for a winner determination
problem of single-item multi-unit auctions. JSIAM Letters 3, 29-32.

16Appendix 1: Bid Plots and Regression Results

250

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
150
valuation

200

0

250

0

50

100
150
valuation

200

250

Figure 1: Appearance 2, session 1, At Random.

Figure 2: Appearance 2, session 1, Descending.

250

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
150
valuation

200

0

250

Figure 3: Appearance 2, session 2, At Random.

17

0

50

100
150
valuation

200

250

Figure 4: Appearance 2, session 2, Descending.

250

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
150
valuation

200

0

250

0

50

100
150
valuation

200

250

Figure 5: Appearance 1, session 3, At Random.

Figure 6: Appearance 1, session 3, Descending.

250

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
150
valuation

200

0

250

Figure 7: Appearance 1, session 4, At Random.

18

0

50

100
150
valuation

200

250

Figure 8: Appearance 1, session 4, Descending.

Table 8: Regression results for Appearance 2: session 1.
at random# of units

1

2

3

4

5

Constant

8.64870.2704-0.0477-1.5924-0.5665

p-value

0.53170.77870.97590.58380.9143

Valuation

1.03461.01111.01761.03851.0495p-value< 0.0001< 0.0001< 0.0001< 0.0001< 0.0001

R-squared

0.36950.99030.9796

0.93680.8387descending# of units

1

2

3

4

5

Constant-2.5882-8.52492.75301.27586.2880p-value

0.54440.20240.47010.70290.0135

Valuation

1.0423

1.07761.01091.00640.8667p-value< 0.0001< 0.0001< 0.0001< 0.0001< 0.0001

R-squared

0.92700.79700.86780.79350.6270

Table 9: Regression results for Appearance 2: session 2.
at random# of units

1

2

3

4

5

Constant

58.7651-4.4447

23.4051

10.8658-21904.1247

p-value

0.10890.40230.09520.7727

0.4814

Valuation

0.86181.06800.8375

1.1039437.3332

p-value

0.0173< 0.0001< 0.0001

0.00150.1079R-squared

0.04710.80910.27790.08250.0218descending# of units

1

2

3

4

5

Constant-3.2232

0.22760.7252-2.79640.0934p-value

0.50800.96080.87080.3046

0.9458Valuation

1.00970.99940.98001.00670.9176p-value< 0.0001< 0.0001< 0.0001< 0.0001< 0.0001

R-squared

0.90270.87150.81680.87250.864219

Table 10: Regression results for Appearance 1: session 3.
at random# of units

1

2

3

4

5

Constant

0.1097-0.8554

1.19030.4402-0.4954

p-value

0.84280.49300.15730.67370.6792

Valuation

1.00491.02761.0002

1.00811.0168p-value< 0.0001< 0.0001< 0.0001< 0.0001< 0.0001

R-squared

0.99690.9867

0.99340.99030.9878descending# of units

1

2

3

4

5

Constant

0.45520.05950.2821-1.5299-0.1532

p-value

0.68770.95980.77190.12420.8355

Valuation

1.00181.0026

0.99801.03131.0040p-value< 0.0001< 0.0001< 0.0001< 0.0001< 0.0001

R-squared

0.99430.99100.99000.98180.9616

Table 11: Regression results for Appearance 1: session 4.
at random# of units

1

2

3

4

5

Constant

0.95780.83115.88401.74310.6277p-value

0.33210.42920.05930.34950.7243

Valuation

0.99240.99010.95920.99550.9992p-value< 0.0001< 0.0001< 0.0001< 0.0001< 0.0001

R-squared

0.99140.99030.91730.9684

0.9724descending# of units

1

2

3

4

5

Constant-1.8971-1.2454-1.4327-0.3842-0.8211p-value

0.10710.25310.08490.54810.0376

Valuation

1.00230.99871.00090.99050.9963p-value< 0.0001< 0.0001< 0.0001< 0.0001< 0.0001

R-squared

0.99400.9921

0.99240.99020.988220

Appendix 2: Instruction3
Welcome to this experiment!
Thank you very much for taking the time to participate in our auction experiment. The
experiment lasts for about 100 minutes, including the payment session.

At First· Please follow the instructions given by the experiment administrators.
· Please remain silent, and do not talk to or exchange notes with other participants.
· Please do not look at what other participants are doing.
· Please do not change your position. Please do not lean in your chair.
· Please do NOT do anything other than what you are instructed to do.
· Please turn oﬀ and refrain from using your cell phones.
· Please quietly raise your hand if you have questions or need help.

In this experiment, a total of 20 auctions will be held and 5 units of a virtual item are
auctioned oﬀ to 3 bidders in each auction.

Compensation
After all the 20 auctions end, a computer will randomly choose 3 auctions each from the
10 auctions in the first and second halves, that is, a total of 6 auctions. You will becompensated on the basis of the total points you earned in the 6 auctions. The final
compensation will be the amount based on those points in addition to a compensation of1500 JPY for participation.

Group Selection
At the beginning, you will be assigned an ID. Your ID will remain the same throughout thesession you participate in, and it will be displayed on your computer screen. You will bematched with two machine bidders. During the experiment this matching will be fixed.

3This is the instruction for the participants in sessions for Appearance 1.

21

Please raise your hand if you have questions on the above contents.

AuctionIn each auction, 5 units of an identical item are auctioned oﬀ to 3 bidders; one is you,and the other two are machine bidders. The bidding strategy of each machine bidder is
programmed in advance. Please bid for all units within 120 seconds. If no one in the samegroup bids within this time limit, all bidders in the group obtain zero points. The outcome
will not be shown until the remaining time is up, even if everyone bids within the time limit.
At the beginning of each auction, each bidder is given unit valuations of the item foreach unit. When the unit valuation is, e.g., 15 for 3 units, the total valuation is 15×3=45.
You are asked to submit your unit bids for each unit. Please press the “bid” button after
you fill in your unit bids on your screen. Then, a pop-up window appears and shows yourtotal bids for each unit. If you click on the “OK” button in the pop-up window, your bids
will then be sent to the server computer to compute the outcome of the auction. If you
click on “cancel” button there, you can then go back to the screen to fill in your unit bids.
For each bidder, unit valuations are drawn as integers independently of those for theother bidders with equal probability between 1 and 200. Please bid in non-negative integers.
The remaining time is displayed on the right upper corner of your screen. When the auction
ends, the outcome is shown on your screen. The next auction will start after 5 seconds.
The rule of the auction is explained next.

Please raise your hand if you have questions on the above content.

Item Allocation in the Auction
Below is an example of the auction in which 3 units of an item auctioned oﬀ to 2 bidders;
In Table 12, valuations (or bids) are displayed as unit valuations (or unit bids) multipliedby the number of units.4 Note that the unit valuations and unit bids shown in this example
do not suggest any bidding strategy in the auctions you participate in.
4

In the instruction, we explained how the VCG mechanism allocate the item with this example for threeunits, in order to reduce the influence of the numerical values on the behavior of our subjects in the auctions
for five units.

22

Table 12: Example.
# of units
Bidder 1
Bidder 2

1

2

3

valuation

80×1

60×2

55×3

bid

70×1

55×2

50×3

valuation

40×1

70×2

65×3

bid

40×1

60×2

65×3

The item will be allocated to bidders such that the total amount of bids is maximized
as follows. Find an allocation that maximizes the total amount of bids among all possible
allocations; In the example, (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): 6×2=120, (0, 3): 65×3=195, (1, 2):
70×1+60×2=190, (2,1): 55×2+40×1 =150. Thus, this auction allocates 3 units to bidder
2. The total amount of bids is 195. When there are two or more allocation in each of which
the total amount of bids is maximized, one of those allocations is chosen at random.

Payment determination in the Auction
The payments of bidders are determined as follows.
payment of bidder i = (total amount of bids in the auction that excludes bidder i)− (total amount of bids in the auction) + (bidder i’s bid for the unit assigned to i).

In the example,• payment of bidder 1 = (65 × 3) − 195 + 0 = 0,
• payment of bidder 2 = (50 × 3) − 195 + (65 × 3) = 150.

Point
The amount of points each bidder earn is calculated as follows.
bidder i’s points = (total valuation for the units bidder i is allocated)− (payment of bidder i).

In the example,23

• bidder 1’s points = 0 − 0 = 0,
• bidder 2’s points = (65 × 3) − 150 = 45.
You will be compensated on the basis of the points you earned. The exchange rate is 1
point = 1 JPY. As mentioned, you will be compensated on the basis of the total points you
earned in the 6 auctions, 3 out of the first 10 auctions and 3 out of the second 10 auctions.

Configuration
In the first 10 auctions, unit valuations are given on your computer screen and you are
asked to submit unit bids there, as shown in the Example (Table 12). In the second 10
auctions, total valuations are given on your screen and you are asked to submit total bids
there, as shown in Table 13.
Table 13: Another display.
# of units
Bidder 1
Bidder 2

1

2

3

valuation

80

120

165

bid

70

110

150

valuation

40

140

195

bid

40

120

195

Practice
At the beginning of each sequence of 10 auctions, an auction is held as a practice so thatyou can familiarize yourself with how to do with the computer. The points you earn in thepractice auctions are not counted as those for the compensation.

Please raise your hand if you have questions.

24