First- and lower-price における封印型オークション

# はじめに
この記事は [Lumos Advent Calendar](https://qiita.com/advent-calendar/2023/lumos) の Day9 の記事です！

※ 経済学の、しかもオークションに関する理論の話を（需要の有無など考えずに）書いた記事になっております、、！

# FPSBとSPSB
Frist-price sealed-bid auction (FPSB) と Second-price sealed-bid auction (SPSB) はオークション理論を代表するものの一つですが、シミュレーションの様態まで語られることは少ないように思います。
Thirdあるいはそれ以下のpriceを採用したオークションについてもまた然りです。
FPSBとSPSBについてまとめつつ、Third-price以降のオークションについても考えていきたいと思います！！
# First-price seled-bid auction (FPSB)
証明過程などは今回の主眼ではないので、簡単にオークションのフォーマットと定理をまとめます
### オークションフォーマット
- 同時に入札し、二回以上の入札は出来ない
- $b$ に対して、最も高い入札者が財を手に入れる
```math
x_i = \left\{\begin{align*} %数式を書く
         &1 &\text{if $b_i = max\{b_1, ..., b_n\}$}\\
         &0 &\text{otherwise}
      \end{align*}
   \right.
   ```
- 勝者が最も高い入札額を支払い、財を得る
```math
p_i = \left\{\begin{align*} %数式を書く
         &b_i &\text{if $b_i = max\{b_1, ..., b_n\}$}\\
         &0 &\text{otherwise}
      \end{align*}
   \right.
   ```
- 買い手は、評価値 $v_i$ に応じた入札計画 $\beta_i(v_i)$ を持つ
- 全ての $v_i$ の組合せに対して、入札額 $b_i$ は定まる
### 定理
以上のフォーマットをもつ First-price auction における対称ベイジアン均衡は
```math
\beta(v) = E[Y^1 | Y^1 < v]
```
であり、買い手が増え $n \to \infty$ ならば、$\beta(v) = v$ に収束
# Second-price sealed-bid auction (SPSB)
続いて SPSB のオークションフォーマットと定理です
### オークションフォーマット
- 同時に入札し、二回以上の入札は出来ない
- $b$ に対して、最も高い入札者が財を手に入れる
```math
x_i = \left\{\begin{align*} %数式を書く
         &1 &\text{if $b_i = max\{b_1, ..., b_n\}$}\\
         &0 &\text{otherwise}
      \end{align*}
   \right.
   ```
- 勝者が2番目に高い入札額を支払い、財を得る
```math
p_i = \left\{\begin{align*} %数式を書く
         &b_j &\text{if $b_i = max\{b_1, ..., b_n\}$ and $b_j = max\{\{b_1, ..., b_n\} \backslash \{b_i\}\}$} \\
         &0 &\text{otherwise}
      \end{align*}
   \right.
   ```
- 買い手は、評価値 $v_i$ に応じた入札計画 $\beta_i(v_i)$ を持つ
- 全ての $v_i$ の組合せに対して、入札額 $b_i$ は定まる
### 定理
以上のフォーマットをもつ Second-price auction における支配戦略は
```math
\beta_i(v_i) = v_i
```

# FPSB と SPSB のシミュレーション
100人が参加するとして、100000回試行して結果を観察してみます

### 評価値に対する入札額と支払額
```
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns

plt.rcParams.update(plt.rcParamsDefault)

np.random.seed(42)

N = 100
R = 100_00

v = np.random.uniform(0, 1, (N, R))

b_star = lambda vi, N :((N-1)/N) * vi
b = b_star(v, N)

idx = np.argsort(v, axis=0)
v = np.take_along_axis(v, idx, axis=0)  # same as np.sort(v, axis=0), except now we retain the idx
b = np.take_along_axis(b, idx, axis=0)

ii = np.repeat(np.arange(1, N+1)[:, None], R, axis=1)  # the id for the bidders is created.
ii = np.take_along_axis(ii, idx, axis=0)  # the id is sorted according to bid price as well.

winning_player = ii[-1, :]

winner_pays_fpsb = b[-1, :]  # 最高入札額
winner_pays_spsb = v[-2, :]  # 2番目に高い評価値

binned = stats.binned_statistic(v[-1,:], v[-2,:], statistic='mean', bins=20)
xx = binned.bin_edges
xx = [(xx[ii]+xx[ii+1])/2 for ii in range(len(xx)-1)]
yy = binned.statistic

fig, ax = plt.subplots(figsize=(6, 4))

ax.plot(xx, yy, label='SPSB average payment')
ax.plot(v[-1,:], b[-1,:], '--', alpha = 0.8, label = 'FPSB payment')
ax.plot(v[-1,:], v[-2,:], 'o', alpha = 0.05, markersize = 0.1, label = 'SPSB: actual bids')

ax.legend(loc='best')
ax.set_xlabel('Valuation, $v_i$')
ax.set_ylabel('Bid, $b_i$')
sns.despine()
```
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3623043/6e4acb9f-aa1f-8420-2306-17b8abd7b6e8.png)

### 入札額の分布
```
fig, ax = plt.subplots(figsize=(6, 4))

for payment,label in zip([winner_pays_fpsb, winner_pays_spsb], ['FPSB', 'SPSB']):
    print('The average payment of %s: %.4f. Std.: %.4f. Median: %.4f'% (label,payment.mean(),payment.std(),np.median(payment)))
    ax.hist(payment, density=True, alpha=0.6, label=label, bins=100)

ax.axvline(winner_pays_fpsb.mean(), ls='--', c='g', label='Mean')
ax.axvline(winner_pays_spsb.mean(), ls='--', c='r', label='Mean')

ax.legend(loc='best')
ax.set_xlabel('Bid')
ax.set_ylabel('Density')
sns.despine()
```
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3623043/d6bed691-7958-bb14-d7ba-d2f3d6776bfd.png)

以上のようにして、First-price も Second-price もそれぞれほぼ同じになっていることが分かります。先ほどの定理と合致する結果になりました。
しかし、入札額の分布は異なっていて、Second-price のほうが分散が大きくなっています。

# Third-price 以降ではどうなるのか

Wolfstetter(2012) によれば、$k > 2$ な k-price auction における支配戦略は以下のように定義されます。
```math
\beta_k(v) = v + \frac{k-2}{n-k+1} \frac{F(v)}{f(v)}
```
$\beta_k(v)$ は $k$ についての増加関数として定義されるので、$k$ が大きくなるほど、入札額は真の評価値から大きく乖離することが分かります。



# 参考文献
https://papers.ssrn.com/sol3/papers.cfm?abstract_id=253476
https://economatik.com/news/1000063/third-price-auctions-with-auction-theory-and-order-statistics
https://link.springer.com/chapter/10.1007/978-3-030-69575-0_5
https://python.quantecon.org/two_auctions.html