修士論文 要旨

双方向市場に対する多面体的クリンチングオークション
数理情報学専攻 48166213
指導教員

1 はじめに佐藤 良亮
平井 広志 准教授

通じて取引できる品物の量を制約している．F ⊆ Ej に対し，fj (F ) が辺の部分集合 F を通じて取引できる最複数財のオークションで買い手が入札額とは別に全大量に対応する．なお，fj (Ej ) は売り手 j の品物数を体での予算を持つのは自然な設定であり，広告オーク意味する．fj に対応するポリマトロイドを Pj とする．

ションへの応用から実用上重要だと捉えられて近年研このとき仲介者に与えられる情報は I究が進められている．売り手が 1 名のみの単方向市場((N, M, E), {vi′ }i∈N ,{Bi }i∈N , {ρj }j∈M , {fj }j∈M ) とでは Goel et al. [4] においてポリマトロイド理論を駆使な る ．こ の 情 報 か ら 仲 介 者 は オ ー ク シ ョ ン の 割 当した多面体的クリンチングオークションという汎用的A := (w, p, r) を与える．ただし，w := (wij )ij∈E は取な設定に適用可能な優れた性質を持つメカニズムが提引量に対応し，wij ∈ R+ が買い手 i と売り手 j の間案されている．このメカニズムは Dobzinski et al. [2]の取引量を表す．p = (pi )i∈N は買い手の支払額に対応で提案された Ausubel [1] のクリンチングオークショ

し，pi ∈ R+ が買い手 i の支払額を表す．r = (rj )j∈Mンの枠組を応用したメカニズムの一般化となっている．

は売り手の支払額に対応し，rj ∈ R+ が売り手 j の収

これらの研究は全て売り手が 1 名のみの単方向市場を入を表す．なお，割当は予算制約 pi ≤ Bi (i ∈ N ) とポ対象としているが，売り手が複数名存在する双方向市場リマトロイド制約 w|Ej ∈ Pj (j ∈ M ) を満たす必要がも証券取引や Web 上のディスプレイ広告の割当などのある．ただし，w|Ej は w の Ej への制限である．

:=

応用があり，実用上極めて重要な設定である．本研究で割当 A に応じて買い手と売り手の効用を定める．買は多面体的クリンチングオークションを拡張し，双方向

い手 i，売り手 j の効用をそれぞれ ui (A)，uj (A) とし市場の汎用的な予算制約を伴う設定に適用可能なメカて次のように定義する：

 ∑wij − pi if pi ≤ Bi ,
 vi

ニズムを提案する．提案メカニズムは買い手の誘引両立性，個人合理性，パレート最適性，収支バランスなどの望ましい性質を満たしている．これらの性質の証明には Lawler and Martel [5] で導入されたポリマトロイ

ui (A) :=ij∈Ei−∞otherwise.
∑uj (A) := rj + ρj (fj (Ej ) −wij ).

ド流問題の枠組をオークション理論において初めて利ij∈Ej

用しており，この点も技術的な貢献として挙げられる．

仲介者は買い手と売り手の両方に配慮した割当を与え2 問題設定ることが求められるので，両者の効用に対してよい理論

n 人の買い手と m 人の売り手からなる双方向市場を考える．買い手の集合を N := {1, 2, . . . , n}，売り手の集合を M := {1, 2, . . . , m} とする．買い手 i ∈ N が売保証を伴うような情報 I から割当 A を定めるメカニズ
ムを設計したい．

3 主結果

り手 j ∈ M と取引したい場合に両者を辺 (i, j) で結ぶ．

双方向市場のオークションにおいて重要な性質としこのようにして得られた辺集合を E ⊆ N × M とする．て，誘引両立性，個人合理性，パレート最適性，収支バ

このとき，市場は二部グラフ (N, M, E) として表されランスが挙げられ，このうち誘引両立性と個人合理性にる．以後，辺 (i, j) ∈ E を ij と表し，買い手 i，売り手ついては買い手と売り手のそれぞれで考えられる．一j と接続する辺の集合をそれぞれ Ei , Ej とする．

方で，それら全てを満たすメカニズムは存在しないこと

買い手や売り手にとっての各品物の単位量あたりのが知られている [6]．

価値は同一であるとする．買い手 i の評価額を vi ∈ R+

本研究では売り手が応札額を正直に申告すると仮定とし，入札額 vi′ ∈ R+ と予算 Bi ∈ R+ ∪ {∞} を仲介者することで売り手の誘引両立性は考慮せず，その他の性に申告する．売り手 j の評価額を ρj ∈ R+ とし，応札質を全て満たすメカニズムを与えた．また，これらの性額を ρj として正直に仲介者に申告する．また，単調劣質は Goel et al. [3] で導入されている一般化された予算モジュラ関数 fj : 2Ej → R+ が与えられており，Ej を制約のもとでも成立することを示した．

双方向市場に対する多面体的クリンチングオークション (佐藤 良亮)

4 提案メカニズム

6 先行研究との関係

はじめに m 人の仮想の買い手を追加する．買い手仮想の買い手を追加した後に，売り手を全員統合しn + j の入札額と評価額を ρj ，予算を ∞ とし，売り手て 1 人だとみなすことで，[4] の多面体的クリンチング

j とのみ辺で結ぶ．仮想の買い手は対応する売り手とオークションが適用可能となる．このメカニズムは提制約なく取引可能である．そして，この操作に伴って案メカニズムと同じ流れを取るが，各反復でそれぞれの(N, M, E) や Pj を修正する．このとき，買い手 n + j買い手の取引量は総量のみが求められる．一方で，提案の取引量はオークション終了後に売り手 j の売れ残っメカニズムではそれぞれの買い手の各辺を通じての取た品物の量となる．さらに，買い手 n + j と売り手 j の引量を求めることができる．本研究では，ε を等しく定効用の和は最終的な売り手 j の効用となる．

めたときに両メカニズムにおいて各反復での各買い手

この準備の後に，次の操作を行う．以下では概略のみの取引総量と支払額が等しくなることを示した．した

述べる．買い手 i には価格 ci が与えられており，0 からがって，提案メカニズムは [4] での買い手の取引を多次順番に ε ずつ増加する．ある買い手の価格が増加する元へと拡張したものになっている．こうした背景から，たびに各買い手のその反復での取引量が計算され，買い提案メカニズムは [4] のメカニズムと同様に買い手への手 i はその量だけ単位量あたり現在価格 ci で取引する．

割当に関して綺麗な構造を持っており，これらの性質を取引量 w，支払額 p，収入 r は初期値 0 を取り，買い手利用して買い手の誘引両立性，個人合理性，パレート最の取引の度に増加して最終的に出力される．また，価格適性，収支バランスといった性質が示している．と残り予算に対して，需要 di を次のように定義する：[4] の多面体的クリンチングオークションは Goel et{(Bi − pi )/ci if ci < vi′ ,di :=0otherwise.

al. [3] において，買い手の予算制約を凹関数による制約

di は買い手 i の現在の価格 ci のもとで取引したい量のわりに ϕi (0) = 0 を満たすような単調非減少な凹関数を上限を表す．全員の需要が 0 になったらオークション用いて，pi ≤ ϕi (は終了する．終了までの間は次の手順を繰り返す：が課されているとしても，これまでに述べた結果は全て1. 各買い手の品物の取引量を計算する（後述）．
2. 取引に伴い，取引量と支払額を更新する．
3. 買い手 l の価格を ε 増加させる．
4. 各買い手の需要を更新する．
5. l ← l + 1 (mod n + m)．
全員の需要が 0 になったら，仮想の買い手と対応する売り手との取引を全て打ち消して (w, p, r) を出力する．

5 各反復での取引量の計算
i
本研究では，買い手 i が品物を ξi ∈ RE+ だけ落札するときに，i 以外の買い手の以後の取引量の許容集合を変化させないような ξi で極大なものが，買い手 i のその反復での取引量であると定めた．そして，上記の許容集合がポリマトロイドであり，条件を満たすような ξi の許容集合があるポリマトロイドの基多面体をなすことを示した．このことから，各買い手の取引量は多項式時間で計算できる．この結果の導出にはオークション理論で初めてポリマトロイド流問題 [5] の枠組を利用しており，この点は本研究の技術的な貢献であると言える．

へと拡張しても同様の良い性質が成り立つことが示されている．本研究においても，買い手 i は予算 Bi の代∑ij∈Ei wij ) と表される支払額の制約成り立っている．この制約は応用上意義があり，支払額の合計だけではなく，品物 1 つあたりの平均支払額への制約を扱うことも可能としている．

参考文献[1] L. M. Ausubel. An eﬃcient ascending-bid auction
for multiple objects. American Economic Review,
94(5):1452–1475, 2004.
[2] S. Dobzinski, R. Lavi, and N. Nisan. Multi-unit auctions with budget limits. Games and Economic Behavior, 74(2):486–503, 2012.
[3] G. Goel, V. Mirrokni, and R. P. Leme. Clinching auctions beyond hard budget constraints. In Proceedingsof the Fifteenth ACM Conference on Economics andComputation, pages 167–184, New York, 2014.
[4] G. Goel, V. Mirrokni, and R. P. Leme. Polyhedralclinching auctions and the adwords polytope. Journalof the ACM, 62(3):18:1–18:27, 2015.
[5] E. L. Lawler and C. U. Martel. Computing maximal“polymatroidal” network flows. Mathematics of Operations Research, 7(3):334–347, 1982.
[6] R. B. Myerson and M. A. Satterthwaite. Eﬃcientmechanisms for bilateral trading. Journal of Economic Theory, 29(2):265–281, 1983.