アイテム入札による組合せオークションのナッシュ均衡

全文

(1)Vol.2013-AL-144 No.9 2013/5/17. 情報処理学会研究報告

(2) . アイテム入札による組合せオークションのナッシュ均衡梅田博之. . 浅野孝夫. . 概要：人プレイヤーのアイテム入札による組合せオークションのナッシュ均衡を議論する．具体的には，評価関数が対称的で劣加法性を満たすときに，ナッシュ均衡が存在するための必要十分条件を与える．これからナッシュ均衡が存在するかどうかを判定するアルゴリズムも得られることになる．キーワード：ナッシュ均衡，組合せオークション，第二価格オークション，劣加法性，無秩序の対価.

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16) .

(17) !

(18)

(19) . はじめに. 組合せオークションとアイテム入札. 各アイテムに対して，第二価格オークションを行うという単純な.

(20) のアイテム入札. による組合せオークションでは，評価関数に劣加法性制約. 本節では組合せオークションとアイテム入札に関する基本的な定義といくつかの補題を与える．人のプレイヤーの集合 . . と個のア. 衡については成立しない例が挙げられているものの，成立. およびの各部分集合に対する各プレイヤーの非負の評価を表すからなる組合せオークションを考評価関数 . 条件について深くは言及されていない．したがって，これ. える．まず，アイテム入札について定義する．. が，入札に超過入札なし制約が課されていて，無秩序の代. 価が最大であることが示されている．一方，ナッシュ均. を求めることは非常に興味深いと思われる．. 著者らは，対称性制約を加えて，プレイヤー数がのと. きに，ナッシュ均衡が存在するための必要十分条件を与え，それに基づいて，ナッシュ均衡が存在するかどうかを判定する効率的なアルゴリズムが得られることを示した．本. 論文では，プレイヤー数の条件を取り去って，与えられた. 人のプレイヤーのアイテム入札による組合せオーク. ションに，ナッシュ均衡が存在するための必要十分条件を与える．さらに，それに基づいて，ナッシュ均衡が存在するかどうかを判定するアルゴリズムが得られることを示す．中央大学東京都文京区春日 .

(21)

(22)

(23) !

(24) !. . イテムの集合 . 各プレイヤーの各アイテムに対する入札額. と表記する．すると，各プレイヤーと書ける．そして，全プレイヤーの入札をと表記する．さらに，入札において，は非負であるとし，. . プレイヤー .

(25)

(26) . . 以外の全プレイヤーのアイテム . に対する最高入札額を . と表記する．すなわち，. . . . . とする．そして. . の入札は，. . . とする．入札の実行可能性は以下のように定義される．.

(27) Vol.2013-AL-144 No.9 2013/5/17. 情報処理学会研究報告

(28) . 定義. . プレイヤーの入札は，アイテムの部分. 集合に対して. . .

(29) . . とする．このとき，から得られるプレイヤーの利得は，落札するアイテム集合に対する評価から落札するアイテムの価格の総和を引いた値の. . であるとき，に対して超過入札であると呼ばれる．入札. . は，どの部分集合に対しても超過入札でない（す. べてのに対して. . である）とき，. 実行可能であると呼ばれる．さらに，全プレイヤーの入札. は，すべてのプレイヤーの入札が実行可能であるとき，実行可能であると呼ばれる． ¾. アイテム入札の組合せオークション. では，アイテム. ごとに第二価格オークションが行われ，アイテムの落札. . 定義. . ¾. 全プレイヤーの実行可能入札. とする．さらに，プレイヤーのみがを. とする．すなわち，. とする．さらに，この入札. 以外は落札できない）．このとき，アイテムの価格. の実行可能入札. . の入札額がのときには，アイテムは誰にも落札されな. . に対して入札. 額が正で，最大となるプレイヤーが二人以上いる場合である．このときには，アイテム . . に対して最大の入札. に対して，プレイヤーの落札するアイテムの集合をとする．すると上記の議論より，. となる．このとき，プレイヤーの利得とナッシュ均. の各 . . 仮定のの対称性より，すべての . となる任意のを用いてと定義して，は対称的な評価関数として簡潔に表現できる．対称的な評価関数を用いると，仮定の ∼ と定義に対して，. の利得は，以下のように書ける．. 衡は以下のように定義される．定義. . 全プレイヤーの実行可能入札. . に対して，プレイヤーの落札するアイテムの集合を. .

(30)

(31) . . 全プレイヤーの評価関数組は，以下の性質を満たすものとする．（空集合）空集合に対してである．（単調性）

(32) を満たすすべてのに対してである．（劣加法性）すべてのに対してである．（対称性）を満たすすべてのに対 ¾ してである．. 仮定. . 全プレイヤーの実行可能入札. ¾. 本論文では，評価関数に以下の制約を課すことにする．. して最大の入札をしているそれ以外のプレイヤーはアイテ札されたアイテムの価格は最大の入札額になる．. はナッ. シュ均衡であると定義される．. . ．もちろん，このときには，落ムを落札できない）. （および落札集合）に対して，. が成立するとき，実行可能入札. をしているプレイヤーのうちの一人だけがそのアイテム. を落札することになる（したがって，アイテムに対. より真に大きくならないと. . （そのアイテムの価格）となる．. いと考える．問題は，あるアイテム . の落札. き，すなわち，すべてのプレイヤーと上記のすべて. . さらに，アイテムに対して，すべてのプレイヤー. でプレイヤー . するアイテムの集合をとする．このとき，どのプレイヤーもをどのような実行可能入札に変えて. も，得られる利得が . は，他のすべてのプレイヤーの入札額の最高入札額（プレイヤー全体では番目に高い入札額）となる．すなわち，プレイヤーがアイテムを落札したときの支払い額は. を実行. 可能入札に変えて得られる全プレイヤーの実行可能入札. イテムを落札する（したがって，プレイヤー . が最大となっているアイテム . . に対して，プレイヤーの落札するアイテムの集合を. ヤーの実行可能入札. は，自身の入札額 . . と定義される．. と価格（支払い額）は以下のように定義される．全プレイ. において，アイテムへのプレイヤーの入札額が，他のすべてのプレイヤーの入札額より真に大きい（

(33) の）ときには，プレイヤーがア. . 定義. . 全プレイヤーの評価関数組 . . は，以下の性質を満たすものとする．（空集合）である．の各 . .


(35) . を満たすすべてのに対してである．（劣加法性）を満たすすべてのに対してである．¾ （単調性） . . 定義. . 全プレイヤーの実行可能入札. . . . . の利得 . は，. . !. 定義. . 各プレイヤーの定義を満たす対称的. な評価関数をとする．このとき，各プレイヤーに. . . に対して， " として定義し，さらにと定義する． ¾. 対する関数をすべての . . . が実行可能であるための必要十分条件は，すべてのとすべてのに対して， . . . . . ¾. が成立することである．. ¾. と書ける．. が成立することである．したがって，入札. に対して，プレイヤーの落札するアイテムの集合を. とすると，プレイヤー . . ナッシュ均衡の存在本論文の主結果を説明するのに必要となる用語と補題を与え，その後に主結果の証明の概略を与える．詳細な証明は次節以降で与える．本論文のこれ以降の節では，人のプレイヤーの集合集合数組 . . と個のアイテムの. において，全プレイヤーの評価関の各は定義を満. たす対称的な評価関数であり，各は定義. で定義さ. れた関数であるとする．補題. 定義のとを満たす対称的な評価. 関数と定義で定義された関数に対して，. #. . . に対して， . である．さらにすべての . . ならば . 定理関数. と定義. の任意の入札. . ¾. の入札は. . 上の置換を用いて並べられているとする．このとき，が実行可能であるための必要十分条件は，すべてのに対して，の大きいほうの個の入札額の和が以下であること，すなわち，と. .

(36)

(37) . ". として，. . . . のとき. それ以外のとき. #. 本論文の主結果が得られる．. で定義された関数と全プレイヤーに対して，各プレイヤー. . . と定義する．このとき，以下の補題（証明は後述）から，. 定義のとを満たす対称的な評価. . !. . . が成立する．. 個の任意の部分集合への分割，. . を， . . の. に対して，プレイヤーの入札 . である．したがって，. . . 補題. . 式 # で定義される. 定理. . 定義. 人のプレイヤーの入札. ¾. は実行可能入札である．. を満たすにナッ. シュ均衡が存在するための必要十分条件は，式 # で定義される. 人のプレイヤーの実行可能入札 . の個の部分集合への分割が存在することである． ¾ がナッシュ均衡となるような. 定理の証明の概略を与える．以下の記法を用いる．. において，各プレイヤーの落札するアイテムの集合をとし，実行可能入札. . . とする．すると， .


(39) . . と並べられているとする．すると，以下の補題が成立する. ．（定理を用いて容易に証明できる）. である（これは落札の定義より自明である）．そこで，. $ $ $ と定義する．すなわち，. . . のときのとき. と定義する．したがって，はの. . 個の部. とおけば式 !，" をを式 # で. 分集合への分割であり，満たす．さらに，. 定義したプレイヤーの入札とする．したがって，. . . は，として，. . とすると，. . .

(40)

(41). のとき. . ¾. の証明：この補題から，定理の証明は直ちに. 得られる．実行可能入札が存在して，ある実行可能入札の. がナッシュ均衡であるならば，補題より，式で定義したもナッシュ均衡であるので，必要性はすべてのでとおいて得られる．. 十分性は明らかである．式 # で定義される. 人のプレ. イヤーの実行可能入札がナッシュ均衡. となるようなの. . ¾. におけるナッシュ均衡であるからである．. 実行可能入札の基本的な性質. と補題の証明の概略を与えるために，最. 初に実行可能入札の基本的な性質を調べる．これ以降，. は. 人のプレイヤーの実行可能入札で. あり，各入札は，定理の式で述べているように，. 上の置換 . を用いて. と並べられているとする．同様に，式. の . も，上の置換 . .

(42)

(43) . ¼. . !. であるとき，. ¼. . . ". ¾. が成立する．この補題を用いて補題の証明を以下に与える．補題. の証明式 !，" を満たすを. ½ ¾ 義される. とする．さらに式 # で定. 人のプレイヤーの入札は，. と. . #. 上の置換を用いて並べられているとする．する. と，任意の . に対して，. . が成立する．これは，の定義式 # と式 # から . ¼. であるので明らかである．さらに，の実行可能性も以下. のように得られる．補題の式の. から，任意ので . である．一方，任意の

(44) では，であるので， ¼¼. . を用いて，. . ½ ¾ . 個の部分集合への分. 割が存在するときには，それが実際に . ¼. 実行可能入札. ナッシュ均衡である．. 補題. . が成立する．したがって，個のアイテムの任意の集合 ½ ¾ に対しての値の小さいほうの個の和は，. 以下である．すなわち，式のの置換のもとで， . . がナッシュ均衡であるならば，式で定義したも定理. 以下である．すなわち，. . となる．このとき，以下の補題が言える（証明は後述する）．補題. 任意の . ¼. . それ以外のとき. . と任意のに対して，の大きいほうの個のうちで，小さいほうの個の和は，. 補題. . . ¼¼. . . . である（不等式は補題の式より得られる）．した. がって，定理の式より，は実行可能である．¾. .


(46) . . 補題の証明のための準備次に，補題を証明するために，式で定義される. . とする．したがって，. かつ . . . についての基本的な性質を調べる． . 式によるの定義より，のときには，アイテムはどのプレイヤー. である．このとき，式の . にも落札されないので，. の和に対して. .

(47). . . において，各プレイヤーの落札するアイテムの集合をとすると， . . . . . . と書くことにする．したがって，式より，. . の定義と式の仮定より，. . . . の定義より，. . の小さい順に並べる．すなわち，.

(48). . ". の値の小さいほうの個. ¼. #. ¾. が成立する．. . からプレイヤーのを実行可能入札に置き換えて得られる実行可能入札をとする．さらに，において，プレイヤーの落札集合をは，を満たすとする．このとき，実行可能入札 . . . .

(49). さらに，実行可能入札. . に対して，. . . と対称性より仮定できる．このとき以下の補題が成立する. ．（証明は補題を用いてできるが，省略する）. 任意のに対して，をの任意の部分集合とする．さらに，.

(50) 任意のに対してに注意して，

(51)

(52) . がナッシュ均. 衡であるときに成立する性質を調べる．において各プレイヤー . . に対して，である．このと. の落札するアイテムの集合 . は式で定義したように . き以下の補題が得られる（証明は紙面の都合で省略する）．補題. . 式の . 式の . で， . を満たす置換置換 . で. が複数個存在するときには，そのような. の要素数. が最大となるような置換を改めて . とする．このとき，. がナッシュ均衡であるならば， . であるとする．さらに，任意の . 補題. ¾. 成立する．. は. . . . . である．プレイヤーの落札集合に含まれないアイ. テムを . . . . とすると，. とすると，補題と同じ条件と記法のもので，式 # が. . である．同様に，式と式の . . . . . である．すると，対称性から，. と仮定できる．式の . . 系. である．以下では，記法の単純化のため，. . . である．さらに，. . . . !. である．. ¾. . 落札されないアイテムが存在する（すなわ. 補題. である）とする．このとがナッシュ均衡であり，アイテムがプレイヤーに落札されるならば，

(53) かつである． ¾ ち，き，. 補題を証明を完成するために，最後にこれらの補題に基づいて，安定性と落札可能性の概念を導入する． .


(55) . . に対して，すべてので定義. 各. . . . ¼. . が成立するとき，は. . . . . . . で安定であると. ので，. に対して，すべての小. 選んで得られる和が . 以下であるとき，すなわち，す. 与えられた . さいほうの個の入札額のうちから大きいほうの個を. ¼. . . . . . 定理の証明を与える前に，この定理から補題の証明が得られることを示す．. 補題の証明. がナッシュ均衡であるにもかかわらず，がナッシュ均衡でなかったと仮定する．そこで，あるプレイヤー. . . .

(56) . .

(57) . ¾. が安定であるときには，どのプレイヤーも入札実行可能入札. を（実行可能な入札のみならず，実行不可能な入札）. に変えたとしても，入札において，利得が増加することはない．したがって，が安. 定であるならば，ナッシュ均衡でもある．逆も成立するので，以下の定理が得られる（証明は後述する）．. . の落札集合組がナッシュ均衡であるための必要十分条件は，が安定であることである． ¾ 人のプレイヤーの実行可能入札. 定理と定理から以下が得られる．すなわち，入札. に対して，すべてので式の . がナッシュ均衡であるかどうかは時間で判定できが与えられているとする．このとき，. .

(58)

(59) . . 一般性を失うことなく，. が成立するときは，プレイヤーは個のアイテムは落札. 定理. . ¼. . であるとする．すると，以下に示すように矛盾が得られる．. . 不可能であるという．. が入. を実行可能入札に変えると，人のプレイヤーの実行可能入札でプレイヤーの落札集合の利得がもとの利得より真に大きくなったとする．すなわち，. 能であるという．一方，のあるで ¼. . 札. が成立するとき，プレイヤーは個のアイテムが落札可. ¾. 衡も時間で得ることができる．. . でがで安定であるとき，は安定であると呼ぶ． ¾. べてので. 定義を満たす評価関数組 . 間で判定できる．さらに，存在するときには，ナッシュ均. の. . . に対して，ナッシュ均衡が存在するかどうかは時. 系. 呼び，そうでないときには不安定であると呼ぶ．すべて. 定義. る．さらに，定理とを合わせて以下の系も得られる．. . . と仮定できる．実際，の定義より，任意ので. であるので，の単調性から，を減らすことなく，必要ならばの要素を個除去して，がを含むようにを修正できるからである．ここで，. . . とする．すると，. !. . は，. . . . ". . と書ける．したがって，式，! より，. . . であるので，系を適用することができる．したがって，式，，"，# より，. . . . . .


(61)

(62). . . 般性を失うことなく仮定できる．したがって，式は，. . .

(63). . . はナッシュ均衡で . が得られる．一方，. あるので，定義と定理より，

(64). . . . . となって，式に反する．したがって，がナッシュ均衡であることが得られた． ¾ である．しかし，これらを組み合わせると . を用いて定理を証明する．. . において，プ個のアイテムが落札可能であるが， . 個のアイテムは落札不可能であるとする．さらに，. で . . ¼. . .

(65) . . . . . であり，さらに . を. . で. . が成立する．. 証明：背理法で証明する．そこで，. ¾. は. に対して. . . . . . . . . イテムのラベルを変えて，. . そこで，をそのようなの最小値とする．したがって，. . . . . £. . . . は恒等置換で，すべての. でであると仮定する．これは一

(66)

(67) . !. かつすべてので. . . である．一方，プレイヤーは. ". 個のアイテムが落札可能. 個のアイテムは落札不可能であるとしてを考えることがで. いるので，補題 ! で定義されている. きる．すなわち，. は， . で.

(68) を満たすの最小値である．したがって， . ¼. .

(69) . であるので，任意の . が成立する．議論を明快にするために，必要ならばア. . . を満たす．また，プレイヤーは. . . で成立することはない．すなわち，式は，あるで．成立することになる（したがって，と仮定できる）. . あるいは ¼. . である．したがって，式が成立することはない．ま. 安定でなかったと仮定する．したがって，あるとあ.

(70). . . がナッシュ均衡であるならは安定である．.

(71) . ¼. . . る . . 定理の必要性を示す次の補題の証明を与える．補題. . であり，すべてのに対して. であるが，. ば，. .

(72). #. を満たす最小の値とする．すると，すべての . 個のアイテムは落札不可能であるとする．はナッシュ均衡であるので，補題より，と仮定でき，すべてのに対して. た，式は，. 実行可能入札. レイヤーは. 個のアイテムが落札. 可能であるが，. . 次の補題（証明は困難ではないが紙面の都合で省略する）. 補題. と書ける．そこで，プレイヤーは. . 定理の証明. . #. . . 個のアイテムが落札可能. で，. . . . である．ここで，からを何回か引いていくと，幅の区間に値が入るようになる．そこで，を ! 回引いてそのようになったとする．すなわち，. ! . .


(74) . となる．しかし，これは式に矛盾する．. である．そこで，. ! . . ! である．ここで，式 #，を用いて，とのケースに分けて議論する．式 # より

(75) ， ! ，式より式よりであるので，式より，とおく．すると，. . ! ! . . ! . . . . . ¼. . ! . . . . . . . . . . . £. . . . . £. . . であるので， . £. . ! . £. . が得られる．. のとき： ! と式 " より . . . . . . . . . . £. . . . . . . . . . . . . おわりに本論文では，定義. を満たす対称的な評価関数組. にナッシュ均衡が存在するための必要十分条件（定理）を与えた．最後に，定義の式 " で与えた関数がすべてのとで . となる（が対称的で劣モジュラーであるときはこれを満. 謝辞本研究は日本学術振興会科学研究費および中央大学特定課題研究費の助成に基づいて行われたものである．. . . . . .

(76)

(77)

(78)

(79) .

(80) .

(81)

(82) . . $. ,.

(83)

(84) . . . . . . となり，. . . . 参考文献. . . . . ! ! となり，が得られる．しかし，これも式に矛盾する．. したがって，

(85) を満たす正整数は存在しないこと，すなわち，は安定であることが得られた． ¾. £. . ! ! . . £. しておく．. . . . 均衡も容易に多項式時間で求めることができることを注意. ! . . . たす）ときには，常にナッシュ均衡が存在し，そのナッシュ. であるので，式と劣加法性を用いて，. . . . £. . . . £. . . . ¼. . . . . て，式と劣加法性を用いて，. ! . . . . である（これはでも成立する）．したがっ. ! .

(86). . . . が得られる．したがって，式 ! より，. . より，. ¼. . . ¼. . ¼. . . ¼. . ! のとき：とする．すると，式，からとなるので，式 . !!" !# $!. 梅田博之，浅野孝夫，二人プレイヤーのアイテム入札による組合せオークションのナッシュ均衡，情報処理学会研究報告，% $!$&'(&)$ * "+ $!$ 梅田博之，浅野孝夫，複数人プレイヤーのアイテム入札による組合せオークションのナッシュ均衡，日本オペレーションズ・リサーチ学会 $!, 年春季研究発表会，$&&- .-". $!,. .

(87)