自動交渉AIから見る"AI同士がつながる世界"

Mercari Advent Calendar 2017の7日目です。
今回は、まだあまり知られていないAI同士の交渉についてメルカリでインターンをしている@keita0qがお話しします。

自動交渉とは

自動交渉とはマルチエージェントシステムモデルの一つであり、AI同士がそれぞれの合理性に従って合意形成を行うことを指します。
自動交渉において重要な構成要素は以下の４つです。

1. 交渉の目的

交渉の目的となる結果は、合意(Agreement)です。
交渉に参加するエージェントはその社会において個人的、社会的に満足の行く合意形成を行うために交渉します。

2. 交渉に参加するエージェント

二者の場合は二者間交渉、複数の場合はマルチパーティー交渉と呼ばれます。
各エージェントは3、4で述べるプロトコル、戦略を実装している必要があります。

3. 交渉プロトコル

交渉を行う場合にエージェントが相互に従うルールです。

• ゲーム理論に基づく相互交換プロトコル

• ヒューリスティックアプローチである仲介プロトコル

• オークション

などが交渉プロトコルとしてあげられます。

4. 選好に基づく戦略

ここでいう選好とはエージェントそれぞれの好みです。
この選好は効用関数と呼ばれるそのエージェントに対する効用値(効用とはそのエージェントが好む評価値のこと)で表すのが一般的で、合意形成の成否に大きく影響します。
戦略には大きく分けて以下の２つです。

• どのような提案をするのか。

• どのような提案に合意するのか。

なぜ自動交渉？？

AIブームは現在かつてないほどの盛り上がりを見せ多くの学術機関、企業において研究開発がなされています。
しかし、現代のAIは単純タスクへの最適化が主流となっています。
例えば機械学習、深層学習をはじめとする、分類、回帰問題タスクなどです。今後もこのような最適化は行われ続け、多くの小さなAIが増えていくと考えられます(筆者の主観です) 。
つまりこういったAI同士が疎通し合い、多様な問題への対応やクリエイティブな活動をしていく未来が来るはずです。よって今回お話したマルチエージェント領域の技術はそのような未来で確実に必要とされ、今後も追っていかなければならないと考えています。
現在、このような技術領域が適応されている実例としては

• スマートグリットシステム

  • 電力の流れを供給側・需要側の両方から制御し、最適化できる送電網

• IoTプラットフォーム

• 交通管理システム

  • 自動運転社会における車間、車とインフラ間(信号や道路)の通信による最適化

• 交渉を要するC2Cサービスへの適応(これからメルカリでやっていきたい！！)

等が挙げられます。
ここからは、最も交渉システムのモデリングとして現実的と思われるゲーム理論的アプローチについて詳しくお話していきます。

ゲーム理論的アプローチ 相互交換プロトコル

相互交換プロトコルは以下の様な図で表すことができます。

すべてのエージェントにおいて合意が得られるまで以下を繰り返します。

- 自己の効用に基づいた戦略による提案。
- 相手から提案を自己の効用値関数を用いた許容戦略によって評価し、合意するかどうかを決める。
- 合意しない場合はカウンターオファーとして再び戦略に基づき提案を行う。

効用値

各エージェントには相手からの提案を評価するために複数の論点に対して選好を持っています。
例を示します。

例： 今晩のメインディッシュ

料理名	論点1(量の多さ)	論点2(価格)	論点3(見た目)
牛丼	0.3	0.7	0
チキンサラダ	0	0.6	0.4
鍋	0.5	0.3	0.2

agent1 : 安くて量が多いものが食べたい

論点1(量の多さ)	論点2(価格)	論点3(見た目)
0.5	0.5	0

料理名	効用値
牛丼	0.5
チキンサラダ	0.42
鍋	0.36

agent2 : 量は少なくても見た目のいいものを食べたい。

論点1(量の多さ)	論点2(価格)	論点3(見た目)
0	0.1	0.9

料理名	効用値
牛丼	0.07
チキンサラダ	0.42
鍋	0.21

交渉戦略

交渉の戦略としては先に述べた通り以下の２つがあります。

提案選択戦略

まず一つ目は「どんな提案をするべきなのか」です。
候補案の中から自分の選好と交渉相手の選好を考慮した提案を決めることを指します。
ゲーム理論的アプローチではプロトコルとして相手の効用値を知ることができないのが一般的であるため、交渉過程から相手の選好を予測することが求められます。
つまり、提案する候補案の選択では相手の効用も高く自分の効用も高い点を探すことが重要となるのです。

提案許容戦略

二つ目の戦略は「どんな提案を受け入れるのか」です。
提案された候補案の効用値を評価し、妥協していい解なのかどうか決めることを指します。
交渉の結果として合意する解には以下の性質が求められます。

(1) 個人合理性

単純に言えばより自分の効用が高い候補案を提案しろと言うことです。
1回前の提案がその次の提案よりも高い効用でないといけないという性質です。
つまり、BよりもAのほうが好きなのに、Bを提案することはこの個人合理性に従っていないということです。

(2) パレート最適性

ある集団が、1つの社会状態を選択するとき、集団内の誰かの効用（満足度）を犠牲にしなければ他の誰かの効用を高めることができない状態を、「パレート効率的(Pareto efficient)」といいます。
要するに社会全体において満足の行く状態を指します。
ゲーム理論的アプローチではナッシュ均衡と密接に関係し、パレート最適でありナッシュ均衡である解を求めることで交渉者全員の満足度が高い解と成り得ます。

この２つの性質が満たされた交渉が最適であり、これを目指した妥協戦略を構成する必要があります。

競技会

あまり知られていませんが、ゲーム理論的アプローチのエージェント間自動交渉を目的とした競技会 ANAC
といわれるものがあります。
この競技会では効用情報非公開下で行われ相互交換プロトコルによってエージェント同士を交渉させます。
交渉ドメイン(何について交渉するのか)、交渉人数、効用値関数は任意に設定することが可能で、多様な場面での交渉を自動化するシステムの構築を目的として作られています。
評価方法としては先程述べました合意解の性質に従っており、

• 個人効用の高さ Individual Utility

• 社会的余剰(交渉者全員の満足度) Nash Product
  によって勝敗を決めます。

余談ではありますが、今年度は IJCAIのコンペの一つとして開催され、本記事の筆者である@keita0qの作成したエージェント(AgentKN)は Nash Product Category で世界2位になりました。

最後に

今回はマルチエージェントシステムの一つである自動交渉技術に関してお話しました。ニッチな世界ですが着実に必要性が増しており、また非常に人間味を持った理論であることから少しでも面白さを感じていただけたら幸いです。

現在メルカリではマルチエージェントだけではなくAI、ブロックチェーン、など様々な領域のテクノロジーの活用に挑戦しています。
テクノロジーを活用し、世の中にインパクトをもたらすことに興味のあるエンジニアを大募集しています。採用情報はこちらです

8日目の明日は、@zaq1tomo です。引き続きよろしくお願いします！！