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

ISSN 1884-9946

2019 年 1 月

RISS Discussion Paper Series
No.68 January, 2019

VCG Mechanism for Multi-unit Auctions andAppearance of Information: An Experiment
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

VCG Mechanism for Multi-unit Auctions andAppearance of Information: An Experiment
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

VCG Mechanism for Multi-unit Auctions andAppearance of Information: An Experiment
Satoshi Takahashi∗

Yoichi Izunaga†

Naoki Watanabe‡

January 19, 2019

Abstract
This paper investigates whether, in multi-unit auctions, diﬀerent types ofappearance of information associated with bidding generate diﬀerent levels of
allocative eﬃciency and sellers’ revenue when VCG mechanism is applied tosubject experiments of those auctions. We examine two types of appearance of
information about bidders’ valuations of the item given to them and their bids
asked to submit; One type is unit valuations and unit bids themselves and theother type is unit valuations and unit bids multiplied by the units. We observedthat there was no significant diﬀerence on average in allocative eﬃciency and inseller’s revenue between those two types of appearance of information. Rather,in each appearance of information, there was a significant diﬀerence in subjects’
bidding behavior between diﬀerent displays of draws of unit valuations, but
this behavioral diﬀerence did not significantly aﬀect the diﬀerence in allocativeeﬃciency.
Keywords: multi-unit auctions, VCG mechanism, experiment
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 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

This paper investigates whether, in multi-unit auctions, diﬀerent types of appearance
of information associated with bidding generate diﬀerent levels of allocative eﬃciency
and sellers’ revenue when Vickrey-Clarke-Groves (VCG) mechanism is applied tosubject experiments of those auctions. We examine two types of appearance of
information about bidders’ valuations of the item given to them and their bids asked
to submit; One type is unit valuations and unit bids themselves and the other typeis valuations and bids, i.e., unit valuations and unit bids multiplied by the units.
In various auctions VCG mechanism attains allocative eﬃciency but suﬀers fromits computational complexity, and thus approximation algorithms for VCG mechanism has been developed. Takahashi and Shigeno (2011), for instance, developed
a greedy based approximation (GBA) algorithm for multi-unit auctions. Takahashi
et al. (2018) reported that in their subject experiment VCG mechanism attained
higher allocative eﬃciency than GBA algorithm, although there was no significant
diﬀerence in seller’s revenue between GBA algorithm and VCG mechanism; Theaverage rate of eﬃciency was 97.37% in VCG and it was 93.65% in GBA.
In the experiment conducted by Takahashi et al. (2018), bidders submitted theirunit bids after confirming their unit valuations on computer screens, because thistype of appearance of information was considered as a key feature for the GBA towork well; In GBA, a bidder who submits the highest unit bid is given a priority toobtain some units of the item in the process of the item allocation. In many experiments, however, bidders submitted bids after confirming their valuations. Thus, weneed to investigate whether diﬀerent types of appearance of information associatedwith bidding generate diﬀerent levels of allocative eﬃciency and sellers’ revenue. In
this paper, we examine the performance of VCG.
Our main observation is that there was no significant diﬀerence on average inallocative eﬃciency and in seller’s revenue between those two types of appearance
of information. Rather, in each appearance of information, there was a significant
diﬀerence in subjects’ bidding behavior between diﬀerent displays of draws of unit
valuations, but this behavioral diﬀerence did not significantly aﬀect the diﬀerence
in allocative eﬃciency.
2

The rest of this paper is organized as follows. Section 2 explains VCG mechanism
for multiunit auctions for a single item. Section 3 describes the experimental design,
and Section 4 shows the results. Section 5 closes this paper with some remarks forfurther research.

2

VCG Mechanism

We deal with an auction, where a seller wishes to sell M units of a single item andsolicits bids from n buyers each of whom can purchase up to M units of the item.
Let N = {1, ..., n} be the set of buyers (bidders). For each bidder i ∈ N , denote hisor her anchor values on the quantity by {dki | k = 0, ..., ℓi }, where dk−1
< dki for allik with 1 ≤ k ≤ ℓi , and denote his or her unit bids by {bki | k = 1, ..., ℓi }, where bki isa buyer price in half-open range (dk−1, dki ] for k = 1, ..., ℓi . It is assumed that d0i = 0
iand dℓi i ≤ M for every bidder 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 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 standfor its discontinuous points. For each bidder i ∈ N , denote his or her unit valuationsby {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 any0i ∈ N 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 by(AP )B maximize
subject to

∑
i∈N
∑

Bi (xi )xi ≤ Mi∈N

xi ≥ 0 (∀i ∈ N ).
3

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 ),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 ).
In 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 his or her unit valuations; Thus, the solutions of (AP )B maximize the total sumof valuations in (AP )V as well, which leads the allocative eﬃciency.

3

Experimental Design

This laboratory experiment is a computerized one whose software (cgi script) iscoded with Python. This experiment has 4 sessions and each session consists of 20
rounds in total. In each round, 5 units of a virtual item are auctioned oﬀ to 3 bidders,
where for every bidder i, the number of anchor values is set as ℓi = 5, and thus hisor her anchor values are d0i = 0, d1i = 1, ..., d5i = 5. For each bidder i ∈ N , his or
her unit valuations, {vik | k = 1, ..., ℓi }, are independently and uniformly distributed
over integers between 1 and 200. Bids are made by non-negative integers.
In 2 out of 4 sessions , at the beginning of each round, each bidder i ∈ N isgiven his or her unit valuations {vik | k = 1, ..., ℓi } by the experimenter, which are4

privately shown only in his or her computer screen. 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 )Band (3). When k units of the item is allocated to bidder i, he or she receives thepoints that amounts vik · k minus his or her payment. In the other 2 sessions, eachbidder i is given his or her valuations {vik ∗ k | k = 1, ..., ℓi } and submits his or
her bids {bki ∗ k | k = 1, ..., ℓi }. Table 1 shows the diﬀerence in appearance of theinformation given to bidder i in the case of 3 units, as an example, in Appearance
1 of which ∗k (k = 1, 2, 3) is put automatically in his or her computer screen.
Table 1: Diﬀerent appearance of information.
Appearance 1

vik shown; bki bid# of units

1

2

3

valuation

80*1

60*2

55*3

bid

70*1

55*2

50*3

bidder ivik ∗ k shown; bki ∗ k bid

Appearance 2# of units
bidder i

1

2

3

valuation

80

120

165

bid

70

110

150

In each round, there is a 120-second time limit for submitting bids. If no bidderbids within the time limit, all three bidders then obtain zero point at that round.
When some allocations attain the maximum total amount of bids, an allocationis chosen at random. 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 points ofbidders are not shown to them. Subjects were not allowed to take notes throughout
the session.
For each appearance of information, 2 sessions are paired in this experiment; In
one session, each bidder’s unit valuation of the item is drawn at random for each
unit 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 realigned in the monotone decreasing(non-increasing) order from k = 1 to k = 5 and given to each bidder as his or her

5

unit valuations in that order. The displays of draws are changed between the firstand second 10 rounds in the other paired session. Every subject thus bids underboth displays in the same session. In analysis, however, the data should be mergedin order to cancel the eﬀect of the order of the displays on the results.
The instruction is given at the beginning of each session, where how VCG mechanism works is demonstrated with an example. (See the Appendix.) 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 selectedby a computer at the end of the session they participated in, with the pre-determinedexchange rate in addition to the show-up fee. The exchange rate was 1 point = 1 JPY
and the show-up fee was 1500 JPY. Before proceeding to the experiment, subjects
play 1 round for practice to familiarize themselves with the software.

4

Results

This experiment was conducted at the University of Tsukuba in Japan; 2 sessions
in February 2015 and 2 sessions in January 2017, respectively. Each session 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 informed of who are in thesame group. 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 for this experiment.
Upon arrival, subjects were provided with a written instruction, and then theexperimenter read it around. (The instruction is available upon request.) Subjects
could ask questions regarding the instruction by raising their hand and the experimenter gave the answers to those questions privately. Any communication among
subjects were strictly prohibited; Thus, their interactions were only through theinformation 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 2.
Let x̂ = (x̂1 , x̂2 , . . . , x̂n ) be an observed allocation. The rate of eﬃciency is
6

Table 2: Features of the experimental sessions.

sessionappearance

show-uppoint-to-# ofsessionavg. pointno.

of info.

fee (JPY)

JPY ratio

subj.

date

per subject

1

1

1500

1.0

24

Feb.14, 2015

475.05

2

1

1500

1.0

24

Feb.14, 2015

691.29

3

2

1500

1.0

24

Jan.26, 2017469.42

4

2

1500

1.0

24

Jan.26, 2017674.05defined by∑i∈N Vi (x̂i )the optimal value of (AP )V.

(4)

The rate of seller’s revenue (profit) is defined by
the total amount of observed payments,
the total amount of optimal payments
where the total amount of optimal payments is represented by(5)∑j∈N pj and pj iscalculated with (3) for each bidder j ∈ N under the assumption that every bidder
truthfully bids his or her (unit) valuations.
In what follows, we analyze the data taken from the last 5 out of 10 rounds
in each display of draws to allow subjects the opportunity to learn better bidding
behavior. There was no case where some allocations attained the same maximum
total amount of bids. The data were merged for each display of draws in order tocancel the eﬀect of the order of displays on the results. Tables 3 and 4 show theaverage rates of eﬃciency and seller’s revenue, respectively, as well as their standard
deviations. The sample size is 80 (5 rounds, 8 groups, 2 sessions) for each rate. The
p-values for the two-sided permutation test (perm.) are also reported in those tables,
where in each display of draws the null hypothesis is that there is no diﬀerence inthose averages between Appearance 1 and Appearance 2. For both rates of eﬃciency
and seller’s revenue, as is seen in Tables 3 and 4, the null hypothesis was not rejected
at the 5% significance level in each displays of draws. Our main observation is thusstated as follows.

7

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.9306

0.93780.91720.9337st.dev.

0.07040.03930.06210.0296p-value (perm.)

0.82930.5567

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.94770.96411.05640.8979st.dev.

0.09320.03740.25810.1418p-value (perm.)

0.6596

0.1120Observation 1 In each display of draws, there was no diﬀerence on average inallocative eﬃciency and in seller’s revenue between Appearance 1 and Appearance
2, respectively.
Note that for both appearance of information, the standard deviation of seller’s
revenue observed in the display with the monotone decreasing order of unit valuations is much larger than the one observed in the other display of draws. This is
the reason why Takahashi et al. (2018) chose the display of draws in which values
drawn at random are put as unit valuations as they are.
As noted at the end of Section 2, VCG mechanism, in theory, induces allocativeeﬃciency by providing every bidder with an incentive to submit his or her true
valuations for each unit. In order to examine this feature, we counted the numberof bids that are approximately truth-telling and the number of allocations that areapproximately eﬃcient. We say that a bid for a unit of the item is approximately
truth-telling when it satisfies8

|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 shows the observed numbers of approximately truth-telling bids andapproximately eﬃcient allocations. For each appearance of information, the sample
size is 1200 (5 rounds, 24 bidders, 5 units, 2 sessions) for approximately truth-tellingbids and it is 80 for approximately eﬃcient allocations in each display of draws. The
p-values for the two-sided Fisher exact test (Fisher) are also reported, where foreach appearance of information the null hypothesis is that there is no diﬀerencein number of approximately truth-telling bids (approximately eﬃcient allocations)
between displays of draws. For the numbers of the approximately truth-telling bids,
the null hypothesis was rejected at the 5% significance level in each appearance of
information, whereas for the numbers of approximately eﬃcient allocations the null
hypothesis was not rejected at the same significance level in each appearance of
information. Our next observation is thus stated as follows.
Table 5: Numbers of approximately truth-telling bids and approximately eﬃcient allocations.
truth-tellingeﬃciency

display of draws

at random

decreasingat random

decreasing

Appearance 1

517

450

60

57

p-value (Fisher)
Appearance 2
p-value (Fisher)

0.0141493

0.1216381< 0.0001

60

54
0.3826

Observation 2 In each appearance of information, there was a significant diﬀerence in numbers of approximately truth-telling bids between displays of draws, but
this behavioral diﬀerence did not significantly aﬀect the diﬀerence in numbers ofapproximately eﬃcient allocations between displays of draws.

9

For both appearance of information in both display of draws, the numbers ofapproximately truth-telling bids were less than a half of 1200 samples, as is seen
Table 5. We thus report more results on the subjects’ bidding behavior. In thisexperiment, each unit valuation was drawn independently of the other unit valuations, and thus we here analyze the data unit by unit. If the absolute value of aunit valuation minus a unit bid falls within 5% of all those absolute values, we thendropped the data as an outlier for our regression analysis.
Tables 6 and 7 show the regression results for Appearance 1 and Appearance 2,
respectively. Figures 1 to 4 plot unit valuations and unit bids observed for Appearance 1 and Appearance 2, respectively. The coeﬃcients on valuations were less than
one and they are statistically significant when values drawn at random and shown
to them as they were, regardless of appearance of information. Some coeﬃcients on
valuations in the other display of draws were, however, more than one and they arestatistically significant. Our last observation is thus stated as follows.
Observation 3 For both Appearance 1 and Appearance 2, subjects underbid whenunit 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 realigned in themonotone decreasing order and given to them as their unit valuations.
Note that Chen and Takeuchi (2010) reported subjects’ underbidding when VCG
was applied, although they studied combinatorial auctions. In a single unit auction,
however, many researchers have reported that subjects overbid in the second-priceauction (VCG mechanism). (See, e.g., Kagel and Levin (2016), which is a comprehensive survey of results in experiments of various auctions.) We observed that
subjects overbid also in multi-unit auctions when VCG was applied in the displayof draws of unit valuations that were aligned in the monotone decreasing order.
Observations 2 and 3 jointly imply that in each appearance of information, there
was a significant diﬀerence in subjects’ bidding behavior between displays of draws,
but this behavioral diﬀerence did not significantly aﬀect the diﬀerence in numbersof approximately eﬃcient allocations.

10

Table 6: Regression results for Appearance 1.
at random# of units

1

2

3

4

5

Constant-5.0432-0.11432.3098-1.6640

2.2452p-value

0.31500.8416

0.67500.75300.6910

Valuation

0.89250.98500.93920.96880.9634p-value< 0.0001< 0.0001< 0.0001< 0.0001< 0.0001

R-squared

0.63700.64800.60500.65800.6300descending# of units

1

2

3

4

5

Constant-11.7126-2.5721-5.3490

1.00012.9950p-value

0.39000.73600.29300.85300.3300

Valuation

0.93950.95281.02470.93590.7826p-value< 0.0001< 0.0001< 0.0001< 0.0001< 0.0001

R-squared

0.36600.55900.66100.42500.3250

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

1

2

3

4

5

Constant

5.1200-4.0728

3.0490-1.0193-0.5544p-value

0.36200.37200.47500.81100.8900

Valuation

0.77410.92520.87230.95510.9505p-value< 0.0001< 0.0001< 0.0001< 0.0001< 0.0001

R-squared

0.49800.67600.690

0.73800.7480descending# of units

1

2

3

4

5

Constant-28.4380-31.3011

27.1133-39.5828-1.4110p-value

0.68200.522

0.07800.13700.9080

Valuation

1.2723

1.37990.77971.85441.4011p-value< 0.0001< 0.0001< 0.0001< 0.0001< 0.0001

R-squared

0.03900.06200.104

0.11000.1140

11

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

valuation

150

200

0

250

Figure 1: At random, Appearance 1.

250

50

100

valuation

150

200

250

Figure 2: Descending, Appearance 1.

250

unit1
unit2
unit3
unit4
unit5

200

0

unit1
unit2
unit3
unit4
unit5

200

bid

150

bid

150

100

100

50

50

0

0

50

100

valuation

150

200

0

250

Figure 3: At random, Appearance 2.

0

50

100

valuation

150

200

250

Figure 4: Descending, Appearance 2.

125Final Remarks

As compared to combinatorial or multi-object auctions, there is few literature on
experiments for multi-unit auctions for a single item. Kagel and Levin (2001) studied
subjects’ bidding behavior in multi-unit auctions, but they imposed a uniform priceon all units of the item in their experiment. Allowing diﬀerent prices for diﬀerent
units, we observed that there was no significant diﬀerence in both average rates of
eﬃciency and seller’s revenue between those two types of appearance of information.
In each appearance of information, there was a significant diﬀerence in subjects’
bidding behavior between diﬀerent displays of draws, but this behavioral diﬀerence
did not significantly aﬀect the diﬀerence in allocative eﬃciency.
As noted in the Introduction, Takahashi et al. (2018) examined the performanceof GBA in the display of draws of unit valuations which were given to subjects asthey were, because this type of appearance of information was considered as a key
feature for the GBA to work well. In this paper, we investigated the performanceof VCG in diﬀerent displays of draws. Also for GBA, in another paper, we needto investigate whether diﬀerent types of appearance of information associated withbidding generate diﬀerent levels of allocative eﬃciency and sellers’ revenue.
Kagel et al. (2001) conducted an experiment in which a human bidder with flat
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 is
not appropriate to compare to their result, but our regression analysis showed that
subjects overbid for some units in the display of draws of unit valuations which wererealigned in the monotone decreasing order. On the other hand, Chen and Takeuchi(2010) reported subjects’ underbidding when VCG was applied in combinatorial
auctions. We also observed that subjects underbid in the display of draws of unit
valuations which were given to subjects as they were. What factors induce subjects
to overbid or underbid? This is still an open question for further research.

13

Notes
Acknowledgement
The authors wish to thank Toru Suzuki and Hiroshi Tanaka for their excellent research assistance.

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

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 accordancewith the ethical standards of the institutional and/or national research committee
and with the 1964 Helsinki declaration and its later amendments or comparable
ethical standards. This article does not contain any studies with animals performedby any of the authors.

References
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.
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.
14

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.
Takahashi, S., Izunaga, Y., Watanabe, N., 2018. An approximation algorithm for
multi-unit auctions: Numerical and subject experiments. Operations Research andDecisions 28, 75-95.
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 VCG mechanism with the following example.
Table 8: Diﬀerent appearance of Information in sessions conducted in 2015 and 2017.
2015: values by unit
# 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

2017: by values multiplied by units# 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

Item Allocation
Find an allocation that maximizes the total amount of bids among all possible
allocations. In what follows, ki units of the item are assigned to bidder i = 1, 2 inallocation (k1 , k2 ), and the total amount of bids follows the allocation; (0, 0): 0,15

(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. Thus, VCG mechanism allocates 3 units to bidder 2. The total
amount of bids is 195.

Payment determination
payment of bidder i (winner) =(total amount of bids in the auction that excludes bidder i:
65*3 for bidder 1, 50*3 for bidder 2)− (total amount of bids in the auction)+ (bidder i’s bid for the unit assigned to i)• payment of bidder 1 = (65 ∗ 3) − 195 + 0 = 0• payment of bidder 2 = (50 ∗ 3) − 195 + (65 ∗ 3) = 150

16