The 19th Annual Conference of the Japanese Society for Artiﬁcial Intelligence, 2005

3E2-04

開環境での協力ゲームにおける解概念の提案
A New Solution Concept for Cooperative Games in Open, Anonymous Environments
横尾真½Vincent Conitzer¾

Tuomas Sandholm¾

大田

Makoto Yokoo直樹½

Naoki Ohta

½

岩崎敦½

Atsushi Iwasaki

九州大学大学院システム情報科学研究院

Graduate School of Information Science and Electrical Engineering, Kyushu University

¾

Computer Science Department, Carnegie-Mellon University                                                                                                                !      "   
1. 序論

要のある公理的な条件を示し，これらの公理的な条件を満たす唯一の解概念である匿名操作不可能コアを提案する (4 章)．

協力ゲームは，複数の利己的な主体 (エージェント) が協力する際に，どのように提携を形成し，提携内でどのように利得を配分するかに関する，フォン・ノイマン以来の伝統ある研究分野である [1, 2]．複数の自律的なエージェントから構成されるマルチエージェントシステムにおいて，協力ゲームの理論を応用する研究が進められている [3, 4, 5, 6]．
近年のインターネットの普及により，複数の企業，組織が動的，迅速に提携を構成することが可能／必要となったことから，協力ゲーム理論の適用分野は今後さらに拡大していくことが予想される．
一方，従来の協力ゲームでは，提携の安定性を主眼としたコアに代表される様々な解概念が提案されているが，これらの解概念は，いずれも各参加者の能力が既知であることを前提としており，能力が知られていない新しい参加者が動的にゲームに参加するといった, インターネットのような匿名性が強い開環境での実行を考慮していない．
本論文では，匿名性が強い環境における既存の解概念の適用可能性について考察する．具体的には，一人のエージェントが架空名義を用いて複数のエージェントのように振舞ったり,複数のエージェントが共謀し，単一のエージェントのように振舞う等の不正行為を考える．インターネットのような環境では各エージェントの名義を確認することは事実上不可能であるので，協力ゲームの解概念は，エージェントがこのような不正行為を行っても利得が増加しないように定義される必要がある．
このような匿名性が存在する環境での，不正行為の影響を受けない制度の設計に関しては，オークションに関しては研究事例があるが [7]，協力ゲームに関しては従来 検討がなされていなかった．
本論文ではまず協力ゲームの基本的な概念を説明し，代表的な解概念であるコア，最小コアについて説明する (2 章)．次に匿名の開環境でエージェントが実行可能な不正行為／操作を定式化するため，スキルの特性関数という概念を提案し，既存の解概念が これらの操作に対して頑健でないことを示す (3 章)．
次に，このような不正行為の影響を受けない解概念が満たす必

2. 既存の協力ゲームの解概念
本章では協力ゲームで用いられる基本的な用語を示し，代表的な解概念であるコアと最小コアについて説明する．
定義 1 (協力ゲーム) 複数のエージェントが戦略を決定する際に，エージェント間で拘束的合意が可能なゲームを協力ゲームという．
拘束的合意を得るためには，ゲームの結果手に入れた利得をエージェント間でいかに分配するかが課題となる．協力ゲーム
では，あるエージェントの集合 (提携) が協力することによって得られる利得を定義するため，以下に示す特性関数を用いる．
定義 2 (提携) ゲームに参加する全てのエージェントの集合をとする．
を満たす集合を提携という．



定義 3 (特性関数) 特性関数 は，任意の提携 に対して，提のメンバが協力した結果 得られる利得   を与える．
携

エージェントが協力する場合，より多くのエージェントが協力した方が，より大きな利得が得られることが自然である．このような性質を持つ特性関数を優加法的な特性関数という．

      

# を満たす任意の提携
定義 4 (優加法的な特性関数)について，   $  
 を満たすような特性関数を優加法的な特性関数という．

 



本論文では以下，特性関数は優加法的であることを仮定する．
次に代表的な解概念であるコアについて説明する．直感的には，コアとは，任意の提携に対してゲームから逸脱する誘因を与えないような利得の分配方法 (配分) の集合である．
定義 5 (コア) ゲームに参加するエージェントの集合を ，# , 特性関数を ，各エージェントの配分を # とした時，以下の条件を満たす配分の集合をコアと言う．

   

連絡先: 横尾 真，九州大学，812-8581 福岡県福岡市東区箱崎6-10-1，(092) 642-4065，yokoo@is.kyushu-u.ac.jp

1.

1



   The 19th Annual Conference of the Japanese Society for Artiﬁcial Intelligence, 2005
2.

 #  

3.2 エージェントの可能な操作

本論文では，主催者と呼ばれる特別なエージェントが存在することを仮定する．主催者はゲームに参加しうる全てのスキルの集合 を知っており，かつ の任意のサブセット に対してスキル上の特性関数   を知っていることを仮定する. ゲームに参加を希望するエージェントは，自分の持つスキルを主催者に対して申告し，主催者がエージェントに与える利得を決定するが，その際にエージェントは以下の操作が可能である.

ある提携 に関して，最初の条件が満たされない場合， に属するエージェントは集団としてゲームから逸脱し， 内で利得を分配した方が得られる利得が大きくなる．二番目の条件は，配分が実現可能であることを示す．
コアはゲームによっては空となる場合もあるし，逆に非常に多くの配分がコアに属する場合もある．
次に最小コアについて説明する．最小コアを定義するために， -コアを導入する．



定義 10 (スキルの隠蔽) あるエージェント は自分の持つスキル  の任意の部分集合 
 を持つと申告することができる．

定義 6 ( -コア) ゲームに参加するエージェントの集合を ，特 とし性関数を ，各エージェントの配分を # た時，以下の条件を満たす配分の集合を -コアと言う．

1.
2.

        

定義 11 (架空名義) あるエージェント は自分の持つスキル を分割して，複数のエージェントであるかのように振舞うことができる．

  #  

が共謀し，スキルの和定義 12 (共謀) エージェントの集合
集合    を持つ単独のエージェントのように振舞うことができる．

が正ならば， -コアはコアの条件を強めたものとなり，逆にが負ならば， -コアはコアの条件を弱めたものとなる．
定義 7 (最小コア) 以下の条件を満たす配分を最小コアと呼ぶ．



一方，あるエージェントは自分の所持していないスキル
に関して， を所持していると申告することはできない (そのような虚偽の申告は露見する).

 #       エージェントおよびエージェントの集合は，上記の 3 つの行為を組み合せることが可能である．

1. ある に関して， は -コアに属する.

3.3 既存の解概念が脆弱である例

2. 任意の 

以下に，既存の解概念を用いた場合に，これらの操作によりエージェントが利得を増加させ得る状況の例を示す．

に関して，  -コアは空集合となる．

 

例 1 & つのスキルが存在すると仮定する．また，& つのスキルがそろった場合に 利得 % が得られ，他の場合に利得は' であるとする．また，エージェント % がスキル を持ち,エージェント ( がスキル を持つとする．エージェントの特性関数において，エージェント % とエージェント ( は対称となり，最小コアおよび仁は，エージェント % ( に それぞれ % (の利得を与える．
一方，エージェント % が % % なる架空名義を用いて，それぞれの名義が および を持つと申告すると，エージェントの特性関数において，% % ( は対称となり，最小コアおよび仁は，エージェント % % ( に それぞれ % & の利得を与える．
よって，架空名義を用いることにより エージェント % の利得は増加する．

最小コアは非空であることが保証されるが，複数の要素からなる場合も存在する．最小コアの条件をさらに厳しくした概念として仁 (nucleolus) がある [1, 2]. 仁は必ず一意に決まることが保証される．





3. 匿名の開環境での既存の解概念の脆弱性
本章では，匿名の開環境下でエージェントが実行可能な操作について定式化し，コア，最小コア，仁等の既存の解概念が，これらの操作に対し頑健性を持たないことを示す．

3.1 スキルの特性関数
匿名の開環境において，エージェントが実行可能な操作について厳密に定義するために，スキルという概念を導入し，スキルに関する特性関数を定義する．

    が存在すると仮定する．スキルの特例 2 & つのスキル性関数は以下で与えられる．

定義 8 (スキルとエージェント) それぞれのエージェントが持つ，個々の分割不可能な技能をスキルと呼ぶ．各エージェントはそれぞれ % つ または複数のスキルを持つ．簡単のため，各スキルはユニークであり，重複するものはないことを仮定する．

   #    #     # %  #   #   #    # 'また，エージェント % がスキル ，エージェント ( がスキル，エージェント & がスキル  を持つと仮定する．この場合のコアは唯一の配分からなり，エージェント % の利得が %, エージェント ( & の利得は ' となる．この理由は，エージェント(  もしくは & に正の利得が与えられた場合，エージェント %と &  もしくは ( がゲームから逸脱する誘因を持つためであ

定義 9 (スキルの特性関数) スキルの特性関数 は，任意のスキルの集合 に対して， を持つエージェントが協力した場合に得られる利得   を与える．

 に関して， の持つスキルの和集合を  とすれば，  #    が成立する．スキルの特性関数 が与えられれば，エージェントの特性関数  は一意に決定されるが，逆は提携る．この場合の最小コアおよび仁は，コアと同じ配分となる．
を持つ単独
一方，エージェント ( と & が共謀し，スキルのエージェントであるエージェント ( として振舞う場合，エー 

成立しない．すなわち，スキルの特性関数が持つ情報は，エージェントの特性関数が持つ情報よりも詳細なものとなっている．

2

The 19th Annual Conference of the Japanese Society for Artiﬁcial Intelligence, 2005
ジェントの特性関数において，エージェント % とエージェント( は対称となり，最小コアおよび仁は，エージェント % ( にそれぞれ % ( の利得を与える．よって，共謀によりエージェント ( & の利得は増加する．

3.

 はスキルの隠蔽に対して頑健である:   を満たす，につい任意の   及び任意のスキルの集合の集合    て   
5.  は架空名義及び共謀に対して頑健である:     , #    ,       #      .
上記の条件は，コアの条件を拡張したものとなっている．

4.2 匿名操作不可能コア

上記の方法を用いれば，エージェントの利得は，自分の持つスキルの集合により決まるため，架空名義を用いたり，共謀を行っても利得は変化しない．しかしながら，スキルの隠蔽により利得が増加する可能性がある．以下に例を示す．

本節では，協力ゲームの新しい解概念として，匿名操作不可能コアを提案し，匿名操作不可能コアが，前章で示した公理的な条件を満たす唯一の解概念であることを示す．
以下，スキルのコアの定義を示し，このスキルのコアを用いて匿名操作不可能コアを定義する．



例 3 スキルは例 ( と同様とし，エージェント % がスキル を，を持つと仮定する．この場合，スエージェント ( がスキルキルの特性関数を用いてスキルのコアを求めると， の利得が% となり, の利得は ' となる．一方，エージェント ( がスキル を隠蔽した場合，スキル と は対称となり，最小コアおよび仁は，それぞれのスキルに % ( を与える．よって，エージェント ( の効用はスキルを隠蔽した場合の方が大きい．

  

本章では，匿名の開環境下で利用できる新しい解概念を提案する．まず，解概念が示すべき公理的な条件を示し，これらの条件を満たす唯一の解概念である，匿名操作不可能コアを示す．

 



2.

               を満たす任意のスキルの集合について，   
ルの集合の集合が成立する.

  及び任意のスキ       

トルが，エージェントに対する利得の分配に用いられることを，( の条件は，エージェントがスキルを隠蔽する誘因を持たないことを示す．
以下に  の例を示す．

  



例 4 前章の例 ( と同じ状況を考える．以下の利得関数  は匿名操作不可能コアに属する．

     #             #       # %,#

その他の引数に対する利得関数の値は '次に匿名操作不可能コアは，前節に示した公理的条件を全て満たす唯一の解概念であることを示す．まず，匿名操作不可能コアが公理的条件をすべて満たすことを示す．

 は匿名である．


2. あるゲームに対し， によって与えられる配分は実行可能である:  #        % の条件は, あるスキルのコアの要素が存在し，その利得ベク

1.

      



 

1. 任意のスキルの集合  に対するスキルのコアが存在す  さる．すなわち  #  ½ ¾
らに，   #  を満たす任意のスキルのプロファイル# ,  # について，以下の条件が成立する:     #  

主催者はゲームで申告される可能なスキルの集合 の上界値を知っているが，実際にエージェントが持つスキルの集合はの部分集合となる．このため主催者は，任意のに関して，配分を決定する利得関数 を定義しておく必要がある．
本論文では， は匿名であると仮定する．
利得関数 が匿名であるとは，エージェント が得られる
利得は， および他のエージェントの持つスキルにのみ依存して決まり， および他のエージェントの名義には無関係であることを意味する．匿名である利得関数は，あるエージェントの持つスキルの集合を  ，他のエージェントの集合 が持つスキルの集合の集合を
 として，    として表現できる．この値は， が  , 他のエージェントの集合 がを持つ場合に， に与えられる利得を示す．
存在を申告したすべてのエージェントの集合を , 各エー
ジェントが申告したスキルのプロファイルを # とする．  はエージェント が持っていると申告したスキルの集合である．  を， に属するエージェントの申告したスキルの和集合，  を， に属するエージェントの申告したスキルの集合の集合，  を， 以外のエージェントが申告したスキルの集合の集合とする．の満たすべき公理的な条件として以下が考えられる．

 ¼    定義 14 (匿名操作不可能コア) 以下の条件を満たす利得関数
 は 匿名操作不可能コアに属する．

4.1 解概念が満たすべき条件






   #

4. 匿名の開環境で利用可能な解概念の提案      に対す
定義 13 (スキルのコア) スキルの集合 #  とは，以下の条件を満たす，それぞるスキルのコア の集れのスキルに対する利得のベクトル  #  ½ ¾合である．

 



4.

スキルの特性関数を用いて，スキルに与えられる配分のコアを求める．エージェントに与えられる利得は，そのエージェントが持つスキルに与えられる配分の総和とする．

    

架空名義および共謀を防ぐ方法として，エージェントの特性関数ではなく，スキルの特性関数を用いる方法が考えられる．以下にその具体的な方法を示す．

 



によって与えられる配分は，全ての提携に対して独立す,    る誘因を与えない:
 



定理 1 匿名操作不可能コアに属する  は， の満たすべき公理的条件をすべて満足する．

3

The 19th Annual Conference of the Japanese Society for Artiﬁcial Intelligence, 2005      #   が成立する．さらに補助定理 1 より，      #   が成立する．

証明:  は匿名のため，条件 % は満たされている．また の定義の条件 ( により，公理的条件の 4 が満たされていることは自明である．
#  
に
次に任意のスキルのプロファイル
ついて，   #  , # 

たす  に対して，                       #          #   が成立する．これにより  は匿名操作不可能コアの条件 % を

補助定理 1 及び公理的条件の 5 より任意のスキル#  ,   #  ,の プ ロ ファイ ルについて   # 
  #                と お く．こ の 時  の 定 義 の 条 件 % よ り，#½  ¾        となるようなスキルの配分 が存在し，     #    が成立する．よって    ,        #      #       が成立し，公理的条件の & が満たさ

満たすことが得られる．
従って，公理的条件をすべて満足する利得関数 は，匿名操作不可能コアに属することが示された.
定理 1, 2 より，匿名操作不可能コアは，5 つの公理的条件を全て満たす唯一の解概念となることが示された．





れる．
さらに

     

 #

 #  

 #   より，公理的条件 ( が満たされる．
最後に，    ,  #    ,       # #   から公理的条件)が満   たされる. ¾5. 結論
本論文では，コア，最小コア，仁等の，伝統的な協力ゲームの解概念が，インターネット等の匿名性の強い開環境で可能な操作 (架空名義, 共謀，スキルの隠蔽) に対して脆弱であることを示した．架空名義および共謀は，解概念をスキルの特性関数を用いて再定義することにより回避することが可能であるが，スキルの隠蔽の問題は解決されない．本論文では，このような操作に対して頑健性が保証される解概念が満たすべき公理的条件を示し，これらの公理的条件を満足する唯一の解概念として匿名操作不可能コアを提案した．
コアは提携の安定性を主眼とした解概念であり，本論文で提案した匿名操作不可能コアは，コアをベースに定義されている．今後の課題として，他の解概念，例えば公平性を主眼とした Shapley 値 [1, 2] をベースに，匿名の開環境で利用できる新しい解概念を提案することが挙げられる．

つぎに，公理的条件を全て満たす任意の利得関数は，匿名操作不可能コアの条件を満足することを示す．まず，以下の補助定理を導入する．

補助定理 1 ある利得関数 が ) つの公理的条件を満たすな
 及び，らば，任意のスキルのプロファイル # 
につい #   #  , 及びて，    #      が成立する．

                       

証明: 公理的条件の 2 より次式が成立する:

   #    $#     $      
上式と公理的条件の 5 より      #      が成立するので，    #      

参考文献[1] 鈴木光男, ゲーム理論入門, 共立全書,1981[2] 岡田章, ゲーム理論, 岡田章, 有斐閣,1996が成立する. ¾
この補助定理は，エージェントの の利得は，エージェントの所持するスキル, および他のエージェントの所持するスキルの和集合によって決定され，他のエージェントの所持するスキルが，他のエージェントに対してどのように分配されるかには無関係であることを示している．
次に，この補助定理を利用して，公理的条件を全て満たす利得関数は，匿名操作不可能コアに属することを示す．

[3] Vincent Conitzer and Tuomas Sandholm. Complexity of determining nonemptiness of the core. In Proceedings of theEighteenth International Joint Conference on Artiﬁcial Intelligence (IJCAI), pages 613–618, Acapulco, Mexico, 2003.
[4] Vincent Conitzer and Tuomas Sandholm. Computing Shapley values, manipulating value division schemes, and checking core membership in multi-issue domains. In Proceedingsof the National Conference on Artiﬁcial Intelligence (AAAI),
pages 219–225, San Jose, CA, USA, 2004.

定理 2 ある利得関数  が公理的条件をすべて満たすならば，
 は匿名操作不可能コアに属する．
証明:  は公理的条件の * を満足するため， が匿名操作不可[5] Onn Shehory and Sarit Kraus. Methods for task allocation
via agent coalition formation. Artiﬁcial Intelligence, 101(1–2):165–200, 1998.

能コアの定義中の条件 ( を満たすことは明らかである．以下，

 が匿名操作不可能コアの定義中の条件 % を満たすことを示す．
#   
スキルの集合 #        に対して，
 とする．ここで各エージェントは に含まれるスキルをそれぞれ 1 つずつ持っている状況を考える．この場合， が公理[6] Gilad Zlotkin and Jeffrey S Rosenschein. Coalition, cryptography and stability: Mechanisms for coalition formationin task oriented domains. In Proceedings of the National
Conference on Artiﬁcial Intelligence (AAAI), pages 432–437,
Seattle, WA, July 1994.

的条件の 2, 3 を満足することから，以下の条件が成立する．

         #       , ¼[7] Makoto Yokoo, Yuko Sakurai, and Shigeo Matsubara. Theeffect of false-name bids in combinatorial auctions: Newfraud in Internet auctions. Games and Economic Behavior,
46(1):174–188, 2004.

この条件はスキルのコアの条件と一致しており， のコアは非  を満空となる．よって，ある  #  ½ ¾

  4