An Experimental Study of VCG Mechanism
for Multi-unit Auctions:Competing with Machine Bidders
Satoshi Takahashi, Yoichi Izunaga, Naoki Watanabe
U. Electro-Com., Kanagawa U., Keio Business School

Oct. 24, 2020 at Hosei Univ. DC on-line meeting

1 / 24

1. Introduction: Motivation

Do we not need to induce bidders to report their true preferencesin order to attain the allocative eﬃciency?
▶ Takahashi, Izunaga, Watanabe (2019, EIER) examined how

VCG mechanism works in multi-unit auctions.
▶

The eﬃciency rates were, again, more than 90% in anysessions. (ref. Takahashi, Izunaga, Watanabe, 2018, ORD)
▶ The rates of 95% approximately truth-telling bids were,
however, 31.8-43.1% in those sessions.
▶ Many eﬃcient allocations were not generated even byapproximately truth-telling bids.

2 / 24

1. Introduction: Question

When subjects compete with human bidders, it may be diﬃcult forthem to realize that truth-telling is their dominant strategy.
Main Hypothesis: When subjects compete with truth-tellingmachine bidders in multi-unit auctions, the VCG induces subjects
to choose truth-telling bids more frequently, and eﬃcient
allocations are observed more frequently, as compared to thesituation where they compete with human bidders.

3 / 24

1. Introduction: Result

Main Result: Main Hypothesis was confirmed in approximately
truth-telling bids and approximately eﬃcient allocations, when unit
valuations are shown to subjects and their unit bids are submitted
in multi-unit auctions.
An important factor is appearance of information.

4 / 24

1. Introduction: Appearances of Information

Table: Diﬀerent appearance of information.

Appearance 1# of units
bidder iAppearance 2# of units
bidder ivaluation
bidvaluation
bidvik shown; bik bid
123480×1 60×2 55×3 43×470×1 55×2 50×3 43×4
vik · k shown; bik · k bid
123480120
16517270110150
172

577×572×55385
360

5 / 24

1. Introduction: Background▶ Garey, M. R., Johnson, D. S. (2000): In multi-unit auctions,each of the item allocation problems can be formulated as amultiple-choice knapsack problem, which is NP-hard.
▶

Takahashi, S., Shigeno, M. (2011, JSIAM Letters) proposed apolynomial-time 2-approximation algorithm, which is called aGBA (greedy-based algorithm), after Kothari et al. (2005).
▶ Takahashi, Izunaga, Watanabe (2018, ORD): How GBA works.
▶ Takahashi, Izunaga, Watanabe (2019, EIER): How VCG works.
▶ Rothkopf, M. H., Pekeč, A., and Harstad, R. M. (1998,Manag Sci): In “combinatorial” auctions, each of the item
allocation problem can be formulated as a weighted-set
packing problem, which is NP-hard.
▶ Munkres, (1957, J. SIAM): In multi-object auctions, each ofthe item allocation problems can be formulated as amaximum-weight matching problem on bipartite graph, which
is not NP-hard.
6 / 24

2. The Item Allocation in VCG: Instruction
Table: Example.

# of units
Bidder 1
Bidder 2

valuation
bidvaluation
bid

1
80×1
70×1
40×1
40×1

2
60×2
55×2
70×2
60×2

3
55×3
50×3
65×3
65×3

The item will be allocated to bidders such that the total amount ofbids is maximized as follows. Find an allocation that maximizes
the total amount of bids among all possible allocations; In theexample, (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.
7 / 24

2. The Payment Determination in VCG: Instruction

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.

8 / 24

3. Experimental Design: Basic Setup 1▶ computerized, using cgi script that was coded in Python.
▶ 2 sessions for Appearance 1, 2 sessions for Appearance 2▶ 20 rounds. (10 draws at random, 10 draws in decreasingorder; Engelmann and Grimm (2009)▶ 5 units of a virtual item are auctioned oﬀ to 3 bidders▶ unit valuations are independently and uniformly distributed

over the integers between 1 and 200.
▶ Bids are privately made using non-negative integers.
▶ unit valuations are privately shown only on his or her

computer screen.
▶ When k units of the item are allocated to bidder i, he or she
receives the points in the amount vik · k minus his or her

payment, which is shown to bidder i through his or her
computer screen.
▶ No information on the other bidders are shown there.
9 / 24

3. Experimental Design: Basic Setup 2▶ In the instruction, how the VCG mechanism works isdemonstrated using an example.
▶ The example is carefully made so that it does not imply thedominant strategy of the auction game.
▶ Subjects are paid according to the total points they obtain in

6 rounds (3 from the first 10 rounds and 3 from thesubsequent 10 rounds) randomly selected by a computer atthe end of the session▶ 1 point = 1 JPY, 1500 JPY for show-up .
▶ Subjects play 1 round for practice to familiarize themselveswith the software, before proceeding to each set of 10 rounds
in the session they participate in.

10 / 24

3. Experimental Design: Session Details
Table: Features of the experimental sessions.
session
no.
1
1
2
2
3
3
4
4

appearance
of info.
2
2
2
2
1
1
1
1

display ofdraws
at random
descending
descendingat randomat random
descending
descendingat random# ofsubj.
8

sessiondate
Jan.228Jan.228

Jan.238

Jan.23

avg. payment
per subject
496.541127.89876.87346.65600.12
1285.731306.58
527.61

Note: All the above sessions were conducted in January 2018. The display
type of draws used in the first 10 rounds is listed first in each session withthe same session number. For a companion experiment, at the university ofTsukuba, 2 sessions for Appearance 1 were conducted in February 2015 and2 sessions for Appearance 2 were conducted in January 2017, in eachsession of which 24 subjects participated.
11 / 24

3. Experimental Design: Basic Setup 2▶ In the instruction, how the VCG mechanism works isdemonstrated using an example.
▶ The example is carefully made so that it does not imply thedominant strategy of the auction game.
▶ Subjects are paid according to the total points they obtain in

6 rounds (3 from the first 10 rounds and 3 from thesubsequent 10 rounds) randomly selected by a computer atthe end of the session▶ 1 point = 1 JPY, 1500 JPY for show-up .
▶ Subjects play 1 round for practice to familiarize themselveswith the software, before proceeding to each set of 10 rounds
in the session they participate in.

12 / 24

4. Results: Preparation 1▶ We analyze the data taken from the last 5 out of 10 rounds ineach display type of draws.
▶ The data were thus merged for each display type of draws toincrease our sample size.
Let x̂ = (x̂1 , x̂2 , . . . , x̂n ) be an observed allocation. The rate ofeﬃciency is defined by∑i∈N Vi (x̂i ).
the optimal value of (AP)VThe rate of seller’s revenue (profit) is defined by
the total amount of observed payments.
the total amount of optimal payments

13 / 24

4. Results: Allocative EﬃciencyTable: The rates of eﬃciency.

display of draws
appearance of info.
meanst.dev.
p-value (perm.)

at randomApp. 1 App. 2
0.9892 0.9351
0.0204 0.0601
0.0108decreasing
App. 1 App. 2
0.9987 0.9765
0.0022 0.0251
0.0016

Note: The p-values for the two-sided permutation test are listed in thistable. The null hypothesis is rejected at the 5% significance level.

14 / 24

4. Results: Seller’s Revenue

Table: The rates seller’s revenue.

display of draws
appearance of info.
meanst.dev.
p-value (perm.)

at randomApp. 1 App. 2
0.9966 1.0014
0.0125 0.0693
0.8311decreasing
App. 1 App. 2
1.0101 1.0668
0.0383 0.1487
0.2875

Note: The p-values for the two-sided permutation test are listed in thistable. The null hypothesis is rejected at the 5% significance level.

15 / 24

4. Results: Observation 1Observation 1: (1) Eﬃcient allocations were on average observed
significantly more frequently between Appearance 1 andAppearance 2 for each display type of draws. (2) In seller’s revenue
there was no significant diﬀerence on average between Appearance
1 and Appearance 2 for each display type of draws.

16 / 24

4. Results: Preparation 2

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 valuationand that an allocation is approximately eﬃcient when it satisfies
the rate of eﬃciency ≥ 0.95.

17 / 24

4. Results: Truth-Telling

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

appearance of info.
at randomp-value (Fisher)descending
p-value (Fisher)truth-tellingApp. 1 App. 2
232
148< 0.0001
214119< 0.0001

eﬃciencyApp. 1 App. 278630.0002
74600.0023

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

18 / 24

4. Results: Observation 2Observation 2: For each display of draws, (95%) approximately
truth-telling bids were chosen by subjects significantly more
frequently and (95%) approximately eﬃcient allocations wereobserved significantly more frequently in Appearance 1 than inAppearance 2.

19 / 24

4. Results: Machine vs Human Bidders in TT
Table: Numbers of approximately truth-telling bids

display of draws
opponent biddersApp. 1p-value (Fisher)App. 2p-value (Fisher)at randommachines subjects
232/400 517/1200< 0.0001
148/400 493/1200
0.1576descending
machines subjects
214/400 450/1200< 0.0001
119/400 381/1200
0.4933

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

20 / 24

4. Results: Machine vs Human Bidders in Eﬀ

Table: Numbers of approximately eﬃcient allocations

display of draws
opponent biddersApp. 1p-value (Fisher)App. 2p-value (Fisher)at randommachines subjects
7860< 0.0001
6360
0.7080descending
machines vs. subjects
7457
0.000860
540.3826

Note: The p-values for the two-sided Fisher exact test are listed in thistable. The null hypothesis is rejected at the 5% significance level. InAppearance 1, the p-values for the one-sided test are also less than 0.001.

21 / 24

4. Results: Observation 3
Observation 3: When opponents are truth-telling machinebidders, for each display type of draws in Appearance 1, subjects
chose approximately truth-telling bids more frequently andapproximately eﬃcient allocations realized more frequently, ascompared to the case where opponents were human bidders. There
were no such diﬀerences for each display type of draws inAppearance 2.
Main Result: Main Hypothesis was confirmed when unit
valuations are shown to subjects and their unit bids are submitted
in multi-unit auctions (Appearance 1).
Main Result suggests a possibility that in Appearance 1 subjects
learn their dominant strategy by practicing with machine bidders inexperiments for multi-unit auctions, although the item allocationand payment determination under the VCG mechanism is neverintuitively understandable to subjects.
22 / 24

5. Final Remarks: Overvid or Underbid?

▶ In this experiment (vs. machine bidders), subjects overbid forsome units while they underbid for other units.
▶

Takahashi, Izunaga, and Watanabe (2019, EIER) reports
subjects’ underbidding in Appearance 1 and their overbiddingin Appearance 2. (vs. human bidders)▶ Kagel, Kinross, and Levin (2001, mimeo.) conducted anexperiment in which a human bidder with a flat demand for
two units competes against machine bidders each demanding asingle unit, and they reported overbidding of each humanbidder for both units.
▶ Chen and Takeuchi (2010, GEB) reports subjects’
underbidding in multi-object auctions with package bidding

23 / 24

5. Final Remarks: Other Literature▶ 2 units and 2 bidders: Engelmann and Grimm (2009, EJ)

compared the performances of a uniform-price sealed-bidauction, a uniform-price clock auction, static and dynamic
Vickrey auctions.
▶ Kagel and Levin (2001, Econometrica) was a seminal paper tostudy the demand reduction in uniform-price auctions.

24 / 24