An Experimental Study of an Approximate DGS
Mechanism: Price Increment, Allocative
Efficiency, and Seller’s Revenue
Y. Izunaga1 , S. Takahashi2 , N. Watanabe3
1 Kyusyu U., 2 Electro-Com. U., 3 Keio U.

Jan 22, 2022 at Waseda U. (on-line)
24th Conference on Exp. Soc. Sci

1 / 27

1. Introduction: Research Questions
Question: To find an appropriate increment of prices under anapproximate DGS algorithm in simultaneous ascending auctions
with bidders under the unit-demand constraint
I larger increment of prices ⇒ (1) allocative efficiency andseller’s revenue? (2) subjects’ behavior? (3) satisfiability of
DGS boundary formula (approximation error)?
Vickrey-Clarke-Groves (VCG) mechanism: difficult tounderstand, one-shot bids
I Demange-Gale-Sotomayor (DGS) algorithm: easy tounderstand, multi-stage bids ⇒ saving time by large
increments of prices
I

I an approx DGS: bidding one by one in turn⇒ bidders can take their own time for decision⇒ more important to save time for practical use: secured real
property auctions conducted by the Japanese courts
2 / 27

1. Introduction: Key Concepts
Experiment
I 2 (= m) items are auctioned off to 3 (= n) bidders.
I Increments of prices are 50, 20, 10 (= d).
I Every bidder can place a bid for 1 item.
I Time limit for placing a bid is 10 sec.
I Valuations are independently distributed between 0 and 500.

Key Concepts
I sincere bidding: bidding on the item the difference between

the valuation and the offered price of which is larger
I DGS bounds (DGS, 1986): under approx DGS, the difference

between the price settled by sincere bidders and the minimum
price at the Walrasian equilibria should be smaller thand · min(n, m) = 2d.
3 / 27

1. Introduction: Main Results(1) efficiency rates = 95% (d = 50), 98% (d = 20, 10)(2) seller’s revenue = 99% (d = 50), 104% (d = 20, 10),compared to the case under VCG(3) When d = 50, significantly more cases of overbids andunderbids ⇒ large standard deviation in the case of d = 50
(4) max t/T = 3.0 (d = 50), 7.0 (d = 20), 13.5 (d = 10)
T = the computed number of bids assuming that all bidders
place sincere bids
I t = the observed number of bids that are placed by subjectsI(5) frequency of sincere bids increased as t/T increased.
(6) DGS boundary formula was satisfied at the rates of 85%(d = 50) and 71% (d = 20, 10).
I

When d = 10, it was satisfied at 100% for item 1, but the rate
decreased to 71% for item 2. (visual position for items onsubjects’ monitors?)

Ans.: We recommend d = 20 as an appropriate price increment.
4 / 27

2. Experimental Design: Session Info
I venue: ISER, Osaka University
I participants: undergraduate students
I 5 groups of 3 bidders, randomly matched in every auction.
I 2 practice rounds + 13 rounds for 2 virtual items
I points subjects earned were selected by the computer

randomly from 4 out of the 13 rounds
I

The total amount of payment was total points for those 4rounds in JPY (1 point = 1 JPY) plus a compensation of
1,800 JPY for their participation.

I Data obtained in the last 10 auctions are used for our analysis.
I average Raven score of subjects = about 12.5 for 16 questions

excerpted from the 48 questions of the Raven APM test
(measuring subjects’ ability of pattern recognition).

5 / 27

2. Experimental Design: Raven Score of Non-students
The Raven scores of non-student general public were collected at
the northern Osaka prefecture.
Num. of Obs.
934

Std. Dev.
3.283

Min.
0Max.
160.05density.1.15

2016.4-2018.3

Mean
7.935

0510

15

Raven’s score

6 / 27

Table: Features of the experimental sessions.
session
no.
1
2
3
4
5
6
7
8
9
10
11
12
13
14

amount ofincrement
5050
50
50
2020
20
20
10101010
sim. 1st pricesim. 1st price# ofsubj.
1515151515
15151515
15
15151515

session
date
Apr. 23, 2018
Apr. 23, 2018
Apr. 24, 2018
Apr. 24, 2018
Oct. 26, 2018
Oct. 26, 2018
Nov. 30, 2018
Nov. 30, 2018
Mar. 19, 2019
Mar. 19, 2019
Mar. 20, 2019
Mar. 20, 2019Nov. 4, 2020
Nov. 4, 2020

avg. payment
per subject
2156.472168.272052.60
2227.60
2118.00
2266.67
2170.132213.272214.872197.872293.202230.132063.87
2056.33

7 / 27

2. Experimental design: approx DGS

I valuation of each item ∼ U[0, 500], independently of the otherbidders’ valuations. private information.
I Each bidder placed a bid or withdraw in turn, corresponding

to the offered prices of the items going up from 0 in
pre-announced increments of d = 50 (20, 10).
I Bidding was subject to a time limit of 10 seconds.
I

Unless any bids were not placed within the time limit, thebidder was automatically withdrawn by the computer.

8 / 27

Figure: Guest 1 can choose to either bid on item 1, bid on item 2, or withdraw,
by pressing on the corresponding button.

9 / 27

Figure: Guest 1 is the tentative winner of item 1. The price of item 1 is raised
up to 50 for the others.

I tie-breaking rule: If Guest 2 bids on item 1, then Guest 2

becomes the new tentative winner.
I After Guest 3 made his or her first decision, if any of thebidders withdraws, then the auction ends.
10 / 27

I If no bidder withdraws, then the auction proceeds.
I In the next step and after, the guest who got out of being atentative winner earlier makes a choice in the same way.
I If any of the bidders withdraws, then the auction ends.

Figure 3

Figure: Guest 1 obtains item 1 at the price of 200. Note that 250 the displayedon the monitor was the price for the other bidders.
11 / 27

3. Results: Efficiency Rate and Seller’s Revenue
We analyze the data taken from the last 10 out of 13 rounds.
Let x̂ = (x̂1 , x̂2 , . . . , x̂n ) be an observed allocation. The rate ofefficiency is defined by
Pi∈N Vi (x̂i ).
(1)
the optimal value of the VCG mechanism
The rate of seller’s revenue (profit) is defined bythe total amount of observed payments,
the total amount of optimal payments(2)

where the total amount of optimal payments is calculated under
the assumption that every bidder truthfully bids his or her (unit)
valuations under the VCG with unit-demand constrained bidders.

12 / 27

Hypothesis 1: As the increment of prices are larger, (1) the rateof efficiency decreases on average, and (2) the rate of seller’s
revenue decreases on average.
Observation 1: The Hypothesis 1 was affirmatively confirmed
between the case of d = 20 and d = 50.

13 / 27

I Sample size = 200 (10 rounds, 5 groups, 4 sessions) for each

price increment.
I The two-sided Brunner-Munzel test (BM)I the null hypothesis is that there is no difference in those

averages between two different price increments, which is
rejected at the 5% significance level.

Table: The rates of efficiency.

price incre.
meanst.dev.
p-value (BM)d=10d=20d=50
0.9762 0.9675 0.9574
0.0773 0.0953 0.1044
0.12020.032314 / 27

Table: The rates seller’s revenue.

price incre.
meanst.dev.
p-value (BM)

d=10
d=20
d=50
1.0433 1.0353 0.9997
0.2496 0.3043 0.6230
0.67920.0024

Overbids were observed. (15x10=150 obs. in a session)
I d = 50: 29, 20, 23, and 30 cases; d = 20: 11, 11, 14, and 7cases; d = 10: 6, 4, 10, and 5 cases
I Not necessarily in early rounds. ⇒ Non-pecuniary benefits?
I In taking the average, the amount of underbids cancelled themagnitude of overbids in d = 50. (The large increment ofprices incurred a larger st. dev. in seller’s revenue.)
15 / 27

3. Results: Subjects’ behavior
Hypothesis 2: Subjects tend to bid more sincerely as auctions
proceed.
Observation2: Affirmatively confirmed.
I T : the desirable number of bids in an auction in which every

bidder sincerely bids for any turn. (derived by simulation)
I t: the observed number of bids in the auction.

t
6= 1 ⇒ Some bidders did not sincerely bid.
TThe label `t indicates whether the player b(t) bids sincerely
according to his or her valuation for each item, that is,(b(t)
0 if argmax{ vi− pit | i ∈ I } = i(t),`t =1 otherwise. (insincere bids)(3)

16 / 27

Figure: Price increment = 50.
17 / 27

Figure: Price increment = 20.
18 / 27

Figure: Price increment = 10.
19 / 27

(Those histograms does not represent the ratio of 0 and 1. They
are imply overlapped.)

xt,1 = t/T ,b(t)xt,2 = v1

b(t)

(4)
− p1t , (valuation - price, item 1)

xt,3 = v2 − p2t , (valuation - price, item 2)(0 if i(t) = i pre (t),xt,4 =1 otherwise, (bidder i changed options)

(5)
(6)
(7)

where b(t) stands for the bidder at time t, i(t) and i pre (t)represent the item for which b(t) bids and the item for which b(t)bids at the most recent time, respectively. (xt,4 = 0 for t ≤ 3.)

20 / 27

Table: Summaries of dataset and classification by SVM-SM.
price
incre.
502010# ofsamples
1794
5091
10019

w1
-0.6000-0.2385-0.1238

estimates
w2
w3-0.0006 -0.0003-0.0007 -0.0013-0.0017 -0.0016

w40.0039
0.12400.1851

misclassratio
0.76480.77140.7544

I Misclassification ratios were remarkably high in discriminant

analysis.

21 / 27

Table: Results of Logistic Regression Analysis.
priceincre.
50p-val
20p-val10p-valw1-0.5441< 0.0001-0.2689< 0.0001-0.1305< 0.0001

estimates
w2
w3-0.0001
0.00060.88850.08560.0004-0.0001
0.03790.6200-0.0011-0.0009< 0.0001< 0.0001

w4
0.19150.05710.0356
0.58570.3757< 0.0001

PseudoR2-0.0350-0.0685-0.0830

I As t/T increases, the fraction of insincere bids decreases ind = 50, 20, 10. ⇒ How long did the chain of sincere bids last
immediately before the settlement of the auctions?
I When d = 10, bidders who changed options did not placesincere bids.
I

We observed this tendency also in the cases of d = 20, 10
by using another statistical test.
22 / 27

I When the bid immediately before the settlement (last bid)

was a sincere bid, how long did the chain of sincere bids last,counting backwards from the last bid?
IIt was only 1.315 on average, when d = 50.

We are currently counting the number of chains of sincere bids
which last at least 3 immediately before the last bids.

23 / 27

3. Results: Approximation Error in DGS Boundary Formula
The boundary of the outcomes under Approx DGS:|pi − pi∗ | ≤ d · min{n, m},where pi is the final price of item i the winner pays under approx
DGS, and pi∗ represents the minimum price of item i at Walrasianequilibria which attained by exact DGS.
Hypothesis 3: As increment of prices becomes larger, the fractionof approximation errors in the DGS boundary formula increases.
Observation 3: Affirmatively observed between d = 50 and
d = 10: It was satisfied with the cases of 71% (d = 10, 20) to 85%(d = 50) on average.

24 / 27

Table: Summaries of Results: Approximation Formula.

d50
2010|p1 − p1∗ |< 2d0.915
0.815
1.000|p2 − p2∗ |< 2d0.905
0.815
0.710

both0.850
0.710
0.710

p1 > p1∗
0.435
0.490
0.480

p2 > p2∗
0.440
0.515
0.520

p1 < p1∗
0.560
0.4900.470

p2 < p2∗
0.560
0.455
0.445

I In the case of d = 10, the satisfaction rate dropped to 71%

for item 2, although it was 100% for item 1.
I That large drop was not observed in the cases of d = 50, 20.

The visual position for items on subjects’ monitors affects
bidding behavior? (ref. Takahashi et al. (2019) for the case ofmulti-unit auctions)

25 / 27

4. Concluding Remarks: Increment of Prices
I Large increment (d = 50): significantly many overbids andunderbids ⇒ large standard error in seller’s revenue
I Small increment (d = 10): satisfaction rates of the DGS

boundary formula are different between items (confusion?)
We recommend d = 20.
I No significant difference in allocative efficiency and seller’s

revenue in comparison with the case of d = 10. (Obs. 1)
I Time elapsed to settle auctions was, on average, shorter thanthat in the case of d = 10. (Obs. 2+) (We skipped showing
statistical results in this presentation.)
I Satisfaction rates of DGS boundary formula were satisfied

equally likely between items (Obs. 3)

26 / 27

4. Conclusions: vs. Simultaneous-Bid First-Price Auction
Simultaneous-bid first-price auctions are currently being used insecured real property auctions in Japan.
Under unit-demand constraint, we observed
I efficiency rate: mean = 0.8241, and st.dev. = 0.2067.
I seller’s revenue: mean = 1.3765 and st.dev. = 1.4302.

Under approx DGS, the standard deviation in seller’s revenue
ranged from 0.24 to 0.62.
⇒ more difficult to predict the auction outcomes undersimultaneous-bid first-price Auction
In our sessions, demand reduction was not observed even once
among 130 auctions. (We did not expect this result.)

27 / 27