Sequential First-Price Auction with Randomly Arriving Buyers

Shulin LIU; Xiaohu HAN

doi:10.21078/JSSI-2018-029-06

PDF(103 KB)

Journal of Systems Science and Information ›› 2018, Vol. 6 ›› Issue (1) : 29-34. DOI: 10.21078/JSSI-2018-029-06

Sequential First-Price Auction with Randomly Arriving Buyers

Author information +

History +

Abstract

In this paper we reanalyze Said’s (2011) work by retaining all his assumptions except that we use the first-price auction to sell differentiated goods to buyers in dynamic markets instead of the second-price auction. We conclude that except for the expression of the equilibrium bidding strategy, all the results for the first-price auction are exactly the same as the corresponding ones for the second-price auction established by Said (2011). This implies that the well-known "revenue equivalence theorem"holds true for Said’s (2011) dynamic model setting.

Key words

sequential first-price auction / sequential second-price auction / dynamic market / symmetric Markov equilibrium / the difference equation

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations

Shulin LIU , Xiaohu HAN. Sequential First-Price Auction with Randomly Arriving Buyers. Journal of Systems Science and Information, 2018, 6(1): 29-34 https://doi.org/10.21078/JSSI-2018-029-06

1 Introduction

Sequential auctions have been long studied in the economics literature. The detailed review of most related works, such as Wolinsky^[1], De Fraja and S

\overset{´}{a}

kovics^[2], Satterthwaite and Shneyerov^[3], can be found in [4]. This paper follows Said and use all his assumptions except that the first-price auction¹ has been used to sell differentiated goods to buyers in dynamic markets in which the buyers and new goods arrive randomly to the market, instead of the second-price auctions. We do the same studies as Said did. We make comparison between our results and the corresponding ones obtained by [4]. Surprisingly, we find that the expected values to a buyer under both the first-price and the second-price auctions are the same. Therefore, under the model setting of Said's^[4] the "revenue equivalence theorem" holds. The second-order nonhomogeneous linear difference equation with a boundary condition which the expected value to a buyer satisfies is exactly the same under these two types of auction formats. Thus, the unique symmetric Markov equilibrium under the first-price auction can be characterized by the identical explicit expression used by Said^[4], since it is derived from the identical difference equation mentioned above.

¹Albano and Spagnolo^[5] indicated that sequential first-price auctions for multiple objects are very common in procurement, electricity, tobacco, timber, and oil lease markets.

2 Main Results

In order to facilitate the comparison between our results and the ones obtained by Said^[4], we use the same notations as Said's^[4] except for the notations with superscript of

f

for the first-price auction (which correspond to the notations without superscript of

f

for the second-price auction). For example,

V^{f} (v_{i}^{t}, n)

denotes the maximum expected payoff to a buyer with valuation

v_{i}^{t}

, which corresponds to

V (v_{i}^{t}, n)

for the second-price auction. Other notations such as

W^{f} (n)

have the similar meanings.

We retain all the assumptions made by Said^[4] except that we make the following two new assumptions.

Assumption Ⅰ We use the first-price auction to sell differentiated goods to buyers instead of the second-price auction used by Said^[4].

Assumption Ⅱ Each buyer

i \in {1, 2, \dots, n}

has a private valuation

v_{i}^{t}

for the object at time

t

, where

v_{i}^{t}

is independently (across buyer

i

and period

t

) drawn from the distribution function

F

[\underline{v}, \bar{v}]

with a continuous density function

f

and finite variance,

\underline{v}

and

\bar{v}

are the lowest and highest possible valuations of a buyer, respectively.²

²Said^[4] assumed that

F

was defined on

R_{+}

but integrate over

(- \infty, \infty)

to compute the expectation with respect to

v_{i}^{t}

(see his second lemma). We think that it is more suitable for us to define

F

[\underline{v}, \bar{v}]

. We indicate that all the results obtained by Said^[4] still apply for our Assumption Ⅱ.

Similar to Said^[4], we have the expression of

W^{f} (n)

for all

n \geq 2

\begin{array}{rcl} W^{f} (n) & = & p q E [V^{f} (v_{i}^{t}, n + 1)] + p (1 - q) E [V^{f} (v_{i}^{t}, n)] \\ + (1 - p) q δ W^{f} (n + 1) + (1 - p) (1 - q) δ W^{f} (n), \end{array}

(1)

since

W^{f} (n)

is relevant to the first-price auction.

Next let us consider the decision made by buyer

i

when there are

n \geq 2

buyers on the market and an available object currently. This buyer, with valuation

v_{i}^{t}

, must choose her bid

b_{i}^{t}

to maximize her expected payoff. Under the first-price auction, she receives the payoff of

v_{i}^{t}

less her bid

b_{i}^{t}

with a winning probability of

P r (b_{i}^{t} > max_{j \neq i} {b_{j}^{t}})

. If she loses, she receives the payoff of

δ W^{f} (n - 1)

with a probability of

P r (b_{i}^{t} \leq max_{j \neq i} {b_{j}^{t}})

. Therefore,

\begin{aligned} V^{f} (v_{i}^{t}, n) = max_{b_{i}^{t}} {P r (b_{i}^{t} > max_{j \neq i} {b_{j}^{t}}) (v_{i}^{t} - b_{i}^{t}) + P r (b_{i}^{t} \leq max_{j \neq i} {b_{j}^{t}}) δ W^{f} (n - 1)} . \end{aligned}

(2)

Solving the optimization problem, we can determine the equilibrium bid function, as shown in the following Lemma 1.

Lemma 1 (Symmetric equilibrium bid strategy) In equilibrium, a buyer with a valuation of $v_{i}^{t}$ who is one of $n \geq 2$ bidders on the market bids $b_{i}^{t} = b^{* f} (v_{i}^{t}, n)$ , where

\begin{aligned} b^{* f} (v_{i}^{t}, n) = v_{i}^{t} - \frac{1}{G_{1}^{(n - 1)} (v_{i}^{t})} \int_{\underline{v}}^{v_{i}^{t}} G_{1}^{(n - 1)} (x) d x - δ W^{f} (n - 1), \end{aligned}

(3)

and $\underline{v}$ is the bidder's lowest possible valuation.

Proof Note that, since

P r (b_{i}^{t} \leq max_{j \neq i} {b_{j}^{t}}) = 1 - P r (b_{i}^{t} > max_{j \neq i} {b_{j}^{t}})

, we may rewrite

V^{f} (v_{i}^{t}, n)

\begin{aligned} V^{f} (v_{i}^{t}, n) = max_{b_{i}^{t}} {P r (b_{i}^{t} + C > max_{j \neq i} {b_{j}^{t} + C}) [v_{i}^{t} - (b_{i}^{t} + C)]} + C, \end{aligned}

(4)

where

C = δ W^{f} (n - 1)

. Furthermore, setting

d_{i}^{t} = b_{i}^{t} + C

yields

\begin{aligned} V^{f} (v_{i}^{t}, n) = max_{d_{i}^{t}} {P r (d_{i}^{t} > max_{j \neq i} {d_{j}^{t}}) (v_{i}^{t} - d_{i}^{t})} + C . \end{aligned}

(4')

Denote the optimal solution (the symmetric equilibrium bid) of Equation (4

^{'}

) by

D (v_{i}^{t}, n)

. If a buyer has the lowest possible valuation

\underline{v}

, then her surplus is zero, implying

D (\underline{v}, n) = \underline{v}

. Then, we get a standard first-price auction model. By applying Equation (5) in McAfee and McMillan^[6], we have

D (v_{i}^{t}, n) = v_{i}^{t} - \frac{1}{G_{1}^{(n - 1)} (v_{i}^{t})} \int_{\underline{v}}^{v_{i}^{t}} G_{1}^{(n - 1)} (x) d x .

Since

d_{i}^{t} = b_{i}^{t} + C

, the symmetric equilibrium bid can be obtained from Equation (4), denoted by

b^{* f} (v_{i}^{t}, n)

, it is given by Equation (3). The proof of Lemma 1 is completed.□

Based on Lemma 1, we can obtain the expected equilibrium payoff to a buyer from an auction with

n \geq 2

participants, which is parallel to the second lemma in ^[4] and shown below as Lemma 2.

Lemma 2 (Expected equilibrium payoff) The expected payoff to a buyer from an auction with $n \geq 2$ participants is

\begin{aligned} E [V^{f} (v_{i}^{t}, n)] = {\tilde{Y}}^{f} (n) + δ W^{f} (n - 1), \end{aligned}

(5)

where $Y^{f} (n) = \int_{\underline{v}}^{\bar{v}} [G_{1}^{(n - 1)} (x) - G_{1}^{(n)} (x)] d x$ .

Proof We substitute the symmetric equilibrium strategy Equation (3) into Equation (4). Since

\begin{array}{rcl} P r (b^{* f} (v_{i}^{t}, n) + C > max_{j \neq i} {b^{* f} (v_{j}^{t}, n) + C}) \\ = & P r (b^{* f} (v_{i}^{t}, n) > max_{j \neq i} {b^{* f} (v_{j}^{t}, n)}) \\ = & P r (v_{i}^{t} > max_{j \neq i} {v_{j}^{t}}) = G_{1}^{(n - 1)} (v_{i}^{t}), \end{array}

we have

V^{f} (v_{i}^{t}, n) = \int_{\underline{v}}^{v_{i}^{t}} G_{1}^{(n - 1)} (x) d x + δ W^{f} (n - 1) .

Thus,

\begin{array}{rcl} E [V^{f} (v_{i}^{t}, n)] & = & \underset{c h a n g e t h e o r d e r o f i n t e g r a l}{\underset{⏟}{\int_{\underline{v}}^{\bar{v}} [f (v_{i}^{t}) \int_{\underline{v}}^{v_{i}^{t}} G_{1}^{(n - 1)} (x) d x] d v_{i}^{t}}} + δ W^{f} (n - 1) \\ = & \int_{\underline{v}}^{\bar{v}} [G_{1}^{(n - 1)} (x) \int_{x}^{\bar{v}} f (v_{i}^{t}) d v_{i}^{t}] d x + δ W^{f} (n - 1) \\ = & \int_{\underline{v}}^{\bar{v}} G_{1}^{(n - 1)} (x) [1 - F (x)] d x + δ W^{f} (n - 1) \\ = & \int_{\underline{v}}^{\bar{v}} [G_{1}^{(n - 1)} (x) - G_{1}^{(n)} (x)] d x + δ W^{f} (n - 1) \\ = & {\tilde{Y}}^{f} (n) + δ W^{f} (n - 1) . \end{array}

The proof of Lemma 2 is completed. □

By substituting Equation (5) into Equation (1) and then solving for

W^{f} (n + 1)

in terms of

W^{f} (n)

and

{\tilde{Y}}^{f} (n)

alone, we have

\begin{array}{rcl} W^{f} (n + 1) & = & \underset{a}{\underset{⏟}{\frac{1 - p q δ - (1 - p) (1 - q) δ}{δ (1 - p) q}}} W^{f} (n) - \underset{b}{\underset{⏟}{\frac{p (1 - q)}{(1 - p) q}}} W^{f} (n - 1) \\ - \underset{c}{\underset{⏟}{\frac{p}{δ (1 - p)}}} {\tilde{Y}}^{f} (n + 1) - \underset{d}{\underset{⏟}{\frac{p (1 - q)}{δ (1 - p) q}}} {\tilde{Y}}^{f} (n) . \end{array}

(6)

From the assumption that this arrival occurs immediately and with probability 1 if there is only a single buyer remaining on the market from previous periods --- There are always at least two buyers present, we have

q = 1

when

n = 1

. Therefore, setting

n = 1

in Equation (1) yields

W^{f} (1) = p E [V^{f} (v_{i}^{t}, 2)] + (1 - p) δ W^{f} (2))

. Recalling by Equation (5), we have

W^{f} (1) = p ({\tilde{Y}}^{f} (2) + δ W^{f} (1)) + (1 - p) δ W^{f} (2)

. Solving for

W^{f} (1)

yields

\begin{aligned} W^{f} (1) = \underset{e}{\underset{⏟}{\frac{p}{1 - δ p}}} {\tilde{Y}}^{f} (2) + \underset{f}{\underset{⏟}{\frac{(1 - p) δ}{1 - δ p}}} W^{f} (2) . \end{aligned}

(7)

A solution to the second-order nonhomogeneous linear difference equation Equation (6) with the boundary condition Equation (7) gives the expected value of buyer. While one could solve this system, the continuous time limit is significantly more tractable. Recalling that

δ = e^{- η Δ}, p = λ Δ,

and

q = ρ Δ

and taking the limits of Equation (6) and Equation (7) as the period length

Δ

goes to zero, for

n \geq 2,

yield³

\begin{aligned} W^{f} (n + 1) = \frac{η + λ + ρ}{ρ} W^{f} (n) - \frac{λ}{ρ} W^{f} (n - 1) - \frac{λ}{ρ} {\tilde{Y}}^{f} (n) and W^{f} (1) = W^{f} (2) . \end{aligned}

(8)

³The limits of coefficients of

a, b, c, d, e, f

are shown in the appendix.

Theorem 1 The expected value for the buyer under the first-price auction is exactly the same as that under the second-price auction, namely, $W^{f} (n) = W (n)$ .

Proof According to Said^[4],

W (n)

is a solution to the following nonhomogeneous linear difference equation

\begin{aligned} W (n + 1) = \frac{η + λ + ρ}{ρ} W (n) - \frac{λ}{ρ} W (n - 1) - \frac{λ}{ρ} \tilde{Y} (n) and W (1) = W (2) . \end{aligned}

(9)

From Said^[4], we have

\tilde{Y} (n) = E [Y_{1}^{(n)}] - E [Y_{1}^{(n - 1)}] .

From Lemma 2, we have

\begin{array}{rcl} {\tilde{Y}}^{f} (n) & = & \int_{\underline{v}}^{\bar{v}} [G_{1}^{(n - 1)} (x) - G_{1}^{(n)} (x)] d x \\ = & [G_{1}^{(n - 1)} (x) - G_{1}^{(n)} (x)] x ∣_{\underline{v}}^{\bar{v}} - \int_{\underline{v}}^{\bar{v}} x d [G_{1}^{(n - 1)} (x) - G_{1}^{(n)} (x)] \\ = & - \int_{\underline{v}}^{\bar{v}} x d G_{1}^{(n - 1)} (x) + \int_{\underline{v}}^{\bar{v}} x d G_{1}^{(n)} (x) \\ = & E [Y_{1}^{(n)}] - E [Y_{1}^{(n - 1)}] . \end{array}

Therefore,

{\tilde{Y}}^{f} (n) = \tilde{Y} (n)

. It follows from Equation (8) and Equation (9) that we have

W^{f} (n) = W (n)

Since the nonhomogeneous linear difference equation for the first-price auction Equation (8) is exactly the same as that for the second-price auction Equation (9), we can use the identical expected value functions of Equation (8) and Equation (9) given by Said^[4] to characterize the unique symmetric Markov equilibrium of the infinite horizon first-price sequential auction game. Namely, under the first-price auction we have exactly the same Theorem and Corollary given by Said^[4].

Recalling Equation (5) and Theorem 1, we have the following corollary easily.

Corollary 1 The expected payoff of a buyer is identical under the first and second price auctions. Namely, $E [V^{f} (v_{i}^{t}, n)] = E [V (v_{i}^{t}, n)] .$

3 Conclusion

Under Said's^[4] dynamic model setting, we use the first-price auction to sell the goods instead of the second-price auction used by Said's^[4]. We find the symmetric equilibrium bid strategy, the expected equilibrium payoff, and the expected equilibrium value. By making comparison between our results and the corresponding results obtained by Said's^[4], we find that except for the expressions of the equilibrium bids, all the remaining results for the first-price auction (mentioned above) are the same as those for the second-price auction. This implies that the traditional "revenue equivalence theorem'' also applies to Said's^[4] dynamic model setting.

Appendix

Recalling that

δ = e^{- η Δ}, p = λ Δ,

and

q = ρ Δ

, we can find the limits of

a, b, c, d, e

, and

f

defined in Equation (6) and Equation (7) as

Δ

goes to zero, as shown below

\begin{array}{rcl} lim_{Δ \to 0} a & = & lim_{Δ \to 0} \frac{1 - p q δ - (1 - p) (1 - q) δ}{(1 - p) q δ} \\ = & lim_{Δ \to 0} \frac{1 - λ ρ Δ^{2} e^{- η Δ} - (1 - λ Δ) (1 - ρ Δ) e^{- η Δ}}{(1 - λ Δ) ρ Δ e^{- η Δ}} \\ = & lim_{Δ \to 0} \frac{1 - e^{- η Δ}}{(1 - λ Δ) ρ Δ e^{- η Δ}} - lim_{Δ \to 0} \frac{λ ρ Δ^{2} e^{- η Δ} + e^{- η Δ} (- λ Δ - ρ Δ + λ ρ Δ^{2})}{(1 - λ Δ) ρ Δ e^{- η Δ}} \\ = & lim_{Δ \to 0} \frac{η}{(1 - λ Δ) ρ e^{- η Δ}} - lim_{Δ \to 0} \frac{λ ρ Δ + (- λ - ρ + λ ρ Δ)}{(1 - λ Δ) ρ} = \frac{η + λ + ρ}{ρ} . \end{array}

\begin{array}{rcl} lim_{Δ \to 0} b = lim_{Δ \to 0} \frac{p (1 - q)}{(1 - p) q} = lim_{Δ \to 0} \frac{λ Δ (1 - ρ Δ)}{(1 - λ Δ) ρ Δ} = lim_{Δ \to 0} \frac{λ (1 - ρ Δ)}{(1 - λ Δ) ρ} = \frac{λ}{ρ} . \\ lim_{Δ \to 0} c = lim_{Δ \to 0} \frac{p}{δ (1 - p)} = lim_{Δ \to 0} \frac{λ Δ}{e^{- η Δ} (1 - λ Δ)} = \frac{0}{1} = 0. \\ lim_{Δ \to 0} d = lim_{Δ \to 0} \frac{p (1 - q)}{δ (1 - p) q} = lim_{Δ \to 0} \frac{λ Δ (1 - ρ Δ)}{e^{- η Δ} (1 - λ Δ) ρ Δ} = lim_{Δ \to 0} \frac{λ (1 - ρ Δ)}{e^{- η Δ} (1 - λ Δ) ρ} = \frac{λ}{ρ} . \\ lim_{Δ \to 0} e = lim_{Δ \to 0} \frac{p}{1 - δ p} = lim_{Δ \to 0} \frac{λ Δ}{1 - e^{- η Δ} λ Δ} = \frac{0}{1} = 0. \\ lim_{Δ \to 0} f = lim_{Δ \to 0} \frac{(1 - p) δ}{1 - δ p} = lim_{Δ \to 0} \frac{(1 - λ Δ) e^{- η Δ}}{1 - e^{- η Δ} λ Δ} = \frac{1}{1} = 1. \end{array}

References

Publishing order | Descend order by publishing year | Descend order by cited within

1	Wolinsky A. Dynamic markets with competitive bidding. Review of Economic Studies, 1988, 55 (55): 71- 84. Cited in this article [1]

2	De Fraja G, Sakovics J. Walras retrouve. Journal of Political Economy, 2004, 109 (4): 842- 863. Cited in this article [1]

3	Satterthwaite M, Shneyerov A. Convergence to perfect competition of a dynamic matching and bargaining market with two-sided incomplete information and exogenous exit rate. Game and Economic Behavior, 2008, 63, 435- 467. https://doi.org/10.1016/j.geb.2008.04.014 Cited in this article [1]

4	Said M. Sequential auctions with randomly arriving buyers. Games and Economic Behavior, 2011, 73 (1): 236- 243. https://doi.org/10.1016/j.geb.2010.12.010 Cited in this article [20]

5	Albano G L, Spagnolo G. Collusive drawbacks of sequential auctions. Journal of Public Procurement, 2011, 11, 139- 170. Cited in this article [1]

6	McAfee R P, McMillan J. Auctions and bidding. Journal of Economic Literature, 1987, 25 (2): 699- 738. Cited in this article [1]

Acknowledgements

The authors gratefully acknowledge the Editor and two anonymous referees for their insightful comments and helpful suggestions that led to a marked improvement of the article.

Funding

the National Natural Science Foundation of China(71171052)

PDF(103 KB)

201

Accesses

Citation

Detail

Sections

Recommended

Abstract
Key words
Cite this article
1 Introduction
2 Main Results
3 Conclusion
Appendix
References
Acknowledgements
Funding

Received	Accepted	Published
2016-10-10	2017-02-07	2018-02-25
Issue Date
2018-02-25

Please choose a citation manager

Content to export

Abstract

Key words

Cite this article

1 Introduction

2 Main Results

3 Conclusion

Appendix

{{custom_sec.title}}

{{custom_sec.title}}

References

{{custom_fnGroup.title_en}}

Footnotes

Acknowledgements

{{custom_ack.title_en}}

Funding

Share

模态框（Modal）标题

Please choose a citation manager

Content to export

Abstract

Key words

Cite this article

1 Introduction

2 Main Results

3 Conclusion

Appendix

{{custom_sec.title}}

{{custom_sec.title}}

References

{{custom_fnGroup.title_en}}

Footnotes

Acknowledgements

{{custom_ack.title_en}}

Funding