修士論文 要旨

一様価格オークションの拡張とその効率指標の評価
数理情報学専攻 48196202
指導教員

1 はじめにオークションとは資産を分配するメカニズムであり,

阿曽田 良介平井 広志 准教授

算 B∗ ∈ Rn+ をもとに, 参加者への品物の割り当て x ∈ Rn+と支払い額 π ∈ Rn+ を決めるものである.

3.2 参加者の効用

オークション理論は社会への多大な経済的効果をもた参加者の効用とは, オークションに参加することにらす研究である. 本研究では参加者が予算を持つ予算制よって参加者が得られる利益を意味する. 参加者 i の真約下のオークション理論を考える. 近年盛んである広告の評価額を v∗i とする. 本研究では, オークション参加者オークションなどが予算制約下でのオークションであi の効用 ui を以下のように定義する.

り, 重要な設定である.

定義 1 (効用).

ui B xi v∗i − πi

2 既存研究予算制約下ではオークションメカニズムの分配効率を評価する際に, 伝統的な効率指標である Social Welfare(社会効用) では上手く評価できないことが知られている. そこで 1 つの指針として, メカニズムの分配効率の最大化を目指す代わりにパレート最適性といった分配結果に対する性質を満たすメカニズムの研究も行われている [1, 3, 4]. この方向の研究では, パレート最適性を満たすオークションメカニズムをより現実に則した設定である参加者への分配量にポリマトロイド制約を課した設定への拡張がなどがなされている [3, 5]. 別の方向として, Dobzinski and Paes Leme [2] によって Liquid(1)

これは, 割り当てられた量の品物に対して参加者自身が評価している価格から支払額を引いたものである.

4 オークションメカニズムの性質
4.1 誘因両立性
誘因両立性とは, 参加者は正直な申告をするときが自身の効用を最大化するという性質である.

4.2 個人合理性
個人合理性とは, 参加者は真の評価額 v∗i に基づく, ある評価額 vi を申告することで効用を非負とすることができるという性質である.

Welfare (リキッド効用) という効率指標が考案された.

補題 1 (Myerson [8]). メカニズム M が誘因両立性と個

これにより, Liquid Welfare を用いて既存のオークショ人合理性を満たすことは, 以下の 1, 2 を満たすことと同ンメカニズムの効率評価やより効率のよいオークショ値である.

ンメカニズムの考案が行われている [2, 6, 7].

3 オークションの設定
本研究では, 一様価格オークションを拡張したメカニズムを提案し, Liquid Welfare を用いて提案メカニズム

1. xi (vi , v−i ) が vi に対して単調非減少である.
∫ vi
2. πi (vi , v−i ) = vi xi (vi , v−i ) − 0 xi (u, v−i )du
ただし, メカニズム M において (vi , v−i ) を申告したときの参加者 i の分配量を xi (vi , v−i ) と表すとする.

を評価する. まず始めに本研究で考えるオークションの設定について説明する.

3.1 設定n 人の参加者に m 個の同一の品物を分配するメカニズム M を考える. 参加者 i はそれぞれが品物 1 つあたりに対して真の評価額 v∗i ∈ R+ と予算 B∗i ∈ R+ を持っている. 参加者 i は品物への評価額 vi を申告する. ここで, 参加者は偽の評価額 (vi , v∗i ) を申告することができる. また, 参加者の予算 B∗i については公開された情報として真の予算は知ることができるとする. メカニズム M
は参加者から申告された評価額 v ∈ Rn+ と公開情報の予

5 効率指標定義 2 (Liquid Welfare [2]). メカニズム M の結果 (x, π)に対して, Liquid Welfare W(x) は以下のように定義される.

W(x) B∑min(xi vi , Bi )(2)i

6 本研究で提案するメカニズム
以上の背景を踏まえ，本研究では一様価格オークションを以下の設定へ拡張した．

一様価格オークションの拡張とその効率指標の評価 (阿曽田 良介)

6.1 設定6.4.1

Liquid Welfare の上界

n 人の参加者に 1 個の分割可能の同一の品物を分配するメカニズム M を考える. 参加者から v が申告され, 公

Wl∗ = max W(x)開情報として B が得られる. (v, B) を用いてメカニズム

M によって (x, π) を決定する. また参加者への分配量に,∀i, xi ≤ l(3)という制約が課されている. ただし, l は 0 < l ≤ 1 であx∈X

ただし, X = {x ∈ Rn+ |∑i xi ≤ 1|xi ≤ l} である.

定理 3. 提案メカニズムの Liquid Welfare W(x) に関して, W(x) ≥ 21 Wl∗ である.
証明の方針としては, Wl∗ と W(x) を計算し, 展開する

る実数.

6.2 メカニズム

ことで差となっている項を評価することで示した.

Algorithm 1 提案メカニズム

7Input: (v, B) (v1 ≥ · · · ≥ vn )Output: (x, π)p (∈ R+ ) に対して, vi > p を満たす最大の i を k とする

f (p) =(4)∑kBi
i=1 min( p , l) とする

p を０から上昇させていき, 初めて f (p) ≤ 1 となった
ときの p, k を p∗ , k∗ とする

if f (p) = 1 thenCase1
xi = min( Bp∗i , l) (1 ≤ i ≤ k∗ )∗xi = 0 (i ≥ k + 1)
else
Case2
vi = p∗ を満たす i の個数を s∗ とする()
xi = min Bp∗i , l (1 ≤ i ≤ k∗ )(B ))(min p∗i ,l∑∗(B ) 1 − kxi = ∑k∗ +s∗x(k∗ + 1 ≤ i ≤ k∗ + s∗ )jj=1i
j=k∗ +1 min p∗ ,lxi = 0 (i ≥ k∗ + s∗ + 1)
end ifπ に関しては, Myerson [8] の補題に基づき定めるとする.

6.3 メカニズムの性質
ここでは, 提案メカニズムの性質について紹介する.
定理 2. 提案メカニズムは誘因両立性と個人合理性を満たす
証明の方針としては, Myerson の補題から xi (vi , v−i )が vi に対して単調非減少であることを示した.

6.4 メカニズムの効率評価
ここでは, 提案メカニズムの効率について紹介する.

今後の展望
本研究では, 一様価格オークションを ∀i, xi ≤ l という簡易な制約へと拡張したが, 最終的にはパレート最適性を満たすオークションメカニズムの研究で行われたように, ポリマトロイド制約へと拡張したい. ポリマ
トロイド制約下という複雑な制約下では, 一様価格オークションの拡張自体に工夫が必要であり, また LiquidWelfare の評価も難しいという問題があり今後の課題である.

参考文献[1] Lawrence M. Ausubel. An eﬃcient ascending-bid auction
for multiple objects. American Economic Review, 94:1452–1475, 2004.
[2] Shahar Dobzinski and Renato Paes Leme. Eﬃciency guarantees in auctions with budgets. In International Colloquium on Automata, Languages, and Programming, pages
392–404. Springer, 2014.
[3] Gagan Goel, Vahab Mirrokni, and Renato Paes Leme. Polyhedral clinching auctions and the adwords polytope. Journalof the ACM, 62:18, 2015.
[4] Gagan Goel, Vahab Mirrokni, and Renato Paes Leme.
Pareto eﬃcient auctions with interest rates. In Proceedings of the AAAI Conference on Artiﬁcial Intelligence, volume 33, pages 1989–1995, 2019.
[5] Hiroshi Hirai and Ryosuke Sato. Polyhedral clinching auctions for two-sided markets. Mathematics of Operations Research, to appear.
[6] Pinyan Lu and Tao Xiao. Improved eﬃciency guarantees
in auctions with budgets. In Proceedings of the Sixteenth
ACM Conference on Economics and Computation, pages
397–413, 2015.
[7] Pinyan Lu and Tao Xiao. Liquid welfare maximization inauctions with multiple items. In International Symposium
on Algorithmic Game Theory, pages 41–52. Springer, 2017.
[8] Roger B. Myerson. Optimal auction design. Mathematicsof Operations Research, 6:58–73, 1981.