著者

横尾 真 岩崎 敦 櫻井 祐子 岡本 吉央

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.29, no.2, pp.2_65-2_68, 2012-04-25 (Released:2012-06-25)

著者

横尾 真 岩崎 敦 櫻井 祐子 岡本 吉央

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.29, no.4, pp.4_15-4_31, 2012-10-25 (Released:2012-12-25)

---

本稿では,メカニズムデザイン(基礎編)として,メカニズムデザイン理論について概説する.メカニズムデザイン理論は不完備情報ゲームの枠組みを用いて,自身の利得の最大化を目指して行動するプレイヤの集団が,あるルール(メカニズム)の元でどのように振る舞うかを分析すると共に,どのようにメカニズムを設計すれば社会的に望ましい結果,もしくは設計者の目的を満たす結果を達成できるかを扱う理論である.本稿では,まずメカニズムデザインの基礎となる不完備情報ゲームを説明する.そして,メカニズムデザインの代表的な適用例であるオークションに即して,メカニズムデザインの考え方,およびただ1つの商品を販売するオークションにおけるメカニズムデザイン理論の主要結果を概説する.

著者

横尾 真 岩崎 敦 櫻井 祐子 岡本 吉央

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.29, no.2, pp.2_69-2_84, 2012-04-25 (Released:2012-06-25)

---

本稿では,ゲーム理論の基礎となる標準形の非協力ゲームについて概説する.標準形の非協力ゲームでは,複数のプレイヤが,自身の利得の最大化を目指して,独立かつ同時に行動を選択する.各プレイヤの利得は,自身の行動と他のプレイヤの行動の組合せにより決定される.非協力ゲームの帰結を予測するために,様々な均衡概念が提案されている.本稿では,標準形の非協力ゲームの基礎となる用語と均衡概念について概説する.また,単純に標準形の非協力ゲームを記述した場合,その記述量はプレイヤの数に対して指数的に増加する.本編では,ゲームの簡潔な記述方法であるグラフィカルゲームと混雑ゲーム,およびこれらのゲームにおいて均衡を計算するためのアルゴリズム/計算量について概説する.

著者

横尾 真 岩崎 敦 櫻井 祐子 岡本 吉央

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.30, no.1, pp.1_34-1_52, 2013-01-25 (Released:2013-03-25)

---

本稿では,メカニズムデザイン(応用編)として,前回の基礎編に対して,現実からの要請にもとづく社会的に望ましい結果,もしくは設計者の目的を満たす結果,をもたらすための市場や制度をメカニズムとしてどう考えるかに焦点をあてる.まず,メカニズムデザイン理論における代表的な応用である,異なる種類の商品を同時に販売するためのオークション,いわゆる組合せオークションを,もっともよく知られているVickrey-Clarke-Grovesメカニズムを通して説明する.次に,従来は考えられていなかった課題を解決するためのメカニズムをどのように設計するかを解説するために,架空名義入札を取り上げる.加えて,メカニズムデザイン理論のよく知られた実践例である,検索連動型広告オークションとマッチングメカニズムの主要な結果に関して述べる.

著者

岩崎 敦 東藤 大樹 Atsushi Iwasaki Taiki Todo

雑誌

人工知能学会誌 = Journal of Japanese Society for Artificial Intelligence (ISSN:09128085)

巻号頁・発行日

vol.28, no.3, pp.389-396, 2013-05-01

著者

岩崎 敦

出版者

公益社団法人 計測自動制御学会

雑誌

計測と制御 (ISSN:04534662)

巻号頁・発行日

vol.58, no.7, pp.548-551, 2019-07-10 (Released:2019-07-12)

参考文献数

7

著者

横尾 真 岩崎 敦 櫻井 祐子 岡本 吉央

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.29, no.3, pp.3_39-3_53, 2012-07-25 (Released:2012-09-25)

---

本編では非協力ゲーム(発展編)として,非協力ゲームの均衡概念で最も重要なものであるナッシュ均衡について詳しく述べる.2人ゼロサム標準形ゲームでは,プレイヤが選択可能な純粋戦略の個数に関する多項式時間でナッシュ均衡を計算できる.しかしながら,プレイヤが交互に行動を繰り返し選択するような複雑なゲームでは純粋戦略の個数が膨大となる.本編では,このような複雑な2人ゼロサムゲームの均衡を計算する例として,ポーカー等のカードゲームにおいてナッシュ均衡を計算するアルゴリズムを紹介する.一方,一般の有限2人標準形ゲームでは,ナッシュ均衡が多項式時間で計算可能かどうかが分かっていない.しかしながら,ナッシュ均衡の存在自体は証明されているので,PやNPのような判定問題に関する概念は,ナッシュ均衡計算問題の難しさを議論するためには適切ではない.本編では,ナッシュ均衡計算問題の難しさを議論する際に有用な問題のクラスであるPPAD,およびPPAD完全性について解説する.

著者

横尾 真 岩崎 敦 櫻井 祐子 岡本 吉央

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.30, no.2, pp.2_33-2_51, 2013-04-25 (Released:2013-08-25)

---

本稿では,ゲーム理論の主要領域の1つである協力ゲームについて解説する.協力ゲームは,主に2つの研究領域からなる.1つは,提携内のプレイヤ間で,協力によって得られた利益をどのように分配するかである.本編では,解概念と呼ばれる,協力的なエージェント間で利得を配分する望ましい方法について概説する.古典的な協力ゲーム理論では,コア,シャプレイ値,仁など,さまざまな解概念が提案されている.これらの解概念によって与えられる利得の配分を求めるアルゴリズムと計算量について考察する.2つ目は,全体提携が最適ではない場合,プレイヤがどのような協力関係(提携)を形成するかである.これは,提携構造形成問題(CSG)と呼ばれる.本編では,CSGを効率的に解く制約付き最適化アルゴリズムを紹介する.また,本編ではゲームの簡潔表現法を利用することで解概念やCSGに関する問題を効率的に解くことができるため,協力ゲームの簡潔な記述方法を概説する.

著者

横尾 真 神取 道宏 田村 明久 船木 由喜彦 関口 格 坂井 豊貴 平山 勝敏 尾山 大輔 安田 洋祐 岡本 吉央 岩崎 敦 川崎 雄二郎 小野 廣隆 櫻井 祐子 東藤 大樹 上田 俊 伊藤 孝行 小島 武仁 小原 一郎

出版者

九州大学

雑誌

基盤研究(S)

巻号頁・発行日

2012-05-31

---

本研究プロジェクトでは、我が国の持続可能な発展のために、計算機科学とミクロ経済学の技術を統合/発展させ、経済的、社会的、環境的な観点からの要求をバランスした、希少な資源の望ましい配分を実現するメカニズムの設計理論を構築することを目的としている。具体的には、資源配分メカニズムの設計、解析、表現技術に関して研究を推進し、特に、制約付き両方向マッチングにおけるメカニズム設計、ノイズのある繰り返しゲームの均衡解析、協力ゲームに関する表現技術に関して顕著な成果が得られている(査読付き国際会議87件、国際論文誌74件、国内論文誌11件、著書8件、教科書の執筆4件、招待講演40件)。

著者

ジョヨンジュン 岩崎 敦 神取 道宏 小原 一郎 横尾 真

出版者

情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.53, no.11, pp.2445-2456, 2012-11-15

---

本論文では不完全私的観測付き繰返しゲームの均衡を分析するプログラムを提案する.不完全私的観測付き繰返しゲームは,プレイヤが相手の行動についてノイズを含むシグナルを観測し,そのシグナルを他のプレイヤは観測できないという特徴を持つ.こうしたゲームは人工知能や経済の分野において様々な適用領域を持つため,大きく注目されている.しかし,このゲームにおける均衡を求めるには,非常に複雑な統計的推論が必要になるため,従来難しい未解決問題として知られていた.近年,均衡における振舞いを有限状態オートマトン(finite state automaton,FSA)で記述し,部分観測可能マルコフ決定過程(partially observable Markov decision process,POMDP)の理論を用いることで,あるFSAが均衡を構成するかどうかを明らかにできることが示された.しかし,その具体的な実装方法や実際の問題へ適用するためのプログラムは提供されていない.そこで本論文ではまず,標準的なPOMDPソルバのラッパとなるプログラムを開発する.このプログラムでは私的観測付き繰返しゲームの記述とFSAを入力として,そのFSAが対称的均衡を構成するかどうかを自動的に確認できる.さらに,このプログラムを繰返し囚人のジレンマに適用し,k-期相互処罰(k-MP)と呼ぶ新しいFSAのクラスを発見した.k-MPにおけるプレイヤは,初めに協力し相手の裏切りを観測するとそれ以降自分も裏切るが,続けてk回裏切りを観測すると元に戻り協力する.このプログラムを用いて状態数3以下のFSAを全探索した結果,繰返しゲームにおける観測構造パラメータのいくらかの範囲で,2-MPが他の純粋戦略均衡より優れており,従来よく知られている均衡である無限期罰則のトリガ戦略(grim-trigger)よりも効率的,つまり高い平均利得を実現することが分かった.The present paper investigates repeated games with imperfect private monitoring, where each player privately receives a noisy observation (signal) of the opponent's action. Such games have been paid considerable attention in the AI and economics literature. Since players do not share common information in such a game, characterizing players' optimal behavior is substantially complex. As a result, identifying pure strategy equilibria in this class has been known as a hard open problem. Recently, Kandori and Obara (2010) showed that the theory of partially observable Markov decision processes (POMDP) can be applied to identify a class of equilibria where the equilibrium behavior can be described by a finite state automaton (FSA). However, they did not provide a practical method or a program to apply their general idea to actual problems. We first develop a program that acts as a wrapper of a standard POMDP solver, which takes a description of a repeated game with private monitoring and an FSA as inputs, and automatically checks whether the FSA constitutes a symmetric equilibrium. We apply our program to repeated Prisoner's dilemma and find a novel class of FSA, which we call k-period mutual punishment (k-MP). The k-MP starts with cooperation and defects after observing a defection. It restores cooperation after observing defections k-times in a row. Our program enables us to exhaustively search for all FSAs with at most three states, and we found that 2-MP beats all the other pure strategy equilibria with at most three states for some range of parameter values and it is more efficient in an equilibrium than the grim-trigger.

著者

岩崎 敦 東藤 大樹

出版者

一般社団法人 人工知能学会

雑誌

人工知能 (ISSN:21882266)

巻号頁・発行日

vol.28, no.3, pp.389-396, 2013-05-01 (Released:2020-09-29)

著者

沖本 天太 ジョ ヨンジュン 岩崎 敦 横尾 真

出版者

一般社団法人 人工知能学会

雑誌

人工知能学会全国大会論文集

巻号頁・発行日

vol.2011, pp.1F24, 2011

---

<p>分散制約最適化問題(DCOP)はマルチエージェントシステムの様々な問題を表現する代表的な枠組みである. DCOPはNP-hardであるため,大規模な問題に適用可能な非厳密解法が多く提案されているが,これらのほとんどは解品質を保証しない.本論文では解品質を保証する非厳密解法を提案する.実験では本解法が既存の解品質を保証する非厳密解法と比べ,より高品質の解およびバウンドを高速に与えることを示した. </p>

著者

上田 俊 岩崎 敦 横尾 真

雑誌

情報科学技術フォーラム講演論文集

巻号頁・発行日

vol.10, no.1, pp.209-210, 2011-09-07

著者

藤田 悦誌 岩崎 敦 東藤 大樹 横尾 真

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.31, no.3, pp.3_156-3_167, 2014-07-25 (Released:2014-09-10)

---

本論文では,新しい公開型オークションメカニズムのクラスとして,VCG-equivalent in expectationメカニズムを提案する.正直な戦略の組が事後ナッシュ均衡となる公開型オークションメカニズムはクエリの回答が回答者の財の割当と支払額に影響を与えない無関係なクエリを送信する必要がある.露呈される情報に関して参加者が弱い誘因を持つ場合,無関係なクエリを送信するメカニズムは望ましくない.本論文で新しく提案するVCG-equivalent in expectationメカニズムは,割当はVickrey-Clarke-Groves (VCG)メカニズムと等しく,支払額はVCGの支払額の期待値とするメカニズムである.本論文では,VCG-equivalent in expectationメカニズムにおいて,正直な戦略の組が逐次的均衡となること,及び,無関係なクエリを送信しないVCG-equivalent in expectationメカニズムを構築する手法を示した.さらに,提案メカニズムの現実的な応用事例への適用可能性を示すため,日本の第四世代の周波数オークションに適用可能なメカニズムを示した.

著者

岩崎 敦 横尾 真 寺田 賢二

出版者

一般社団法人 人工知能学会

雑誌

人工知能学会論文誌 (ISSN:13460714)

巻号頁・発行日

vol.19, no.4, pp.334-342, 2004 (Released:2004-05-28)

参考文献数

14

被引用文献数

1

---

This paper develops a new ascending-price multi-unit auction protocol that has following characteristics: (i) it has an open format, (ii) sincere bidding is an equilibrium strategy even if the marginal utilities of each agent can increase and agents can submit false-name bids. False-name bids are bids submitted under fictitious names such as multiple e-mail addresses, which can be done easily in the Internet. This is the first protocol that has these two characteristics. We show that our new protocol outperforms an existing protocol, which satisfies (ii), with respect to the social surplus and the seller's revenue.

著者

上田 俊 岩崎 敦 横尾 真

出版者

FIT(電子情報通信学会・情報処理学会)運営委員会

雑誌

情報科学技術フォーラム講演論文集

巻号頁・発行日

vol.10, no.1, pp.209-210, 2011-09-07

著者

山本 駿 岩崎 敦 横尾 真 趙 登吉

出版者

人工知能学会

雑誌

人工知能学会全国大会論文集 (ISSN:13479881)

巻号頁・発行日

vol.28, 2014

---

不完全私的観測付き繰り返しゲームでは,同じゲームが繰り返しプレイされ,プレイヤは相手の行動を直接観測できず,ノイズを含むシグナルを観測する.本論文では,我々のグループが開発した,均衡判定プログラムをベースに,進化的アルゴリズムを用いて均衡となる戦略を発見するプログラムを提案する.繰り返し囚人のジレンマゲーム等の代表的なゲームに関して,このプログラムによって発見されたいくつかの新しい均衡を示す.

著者

岩崎 敦 野澤 孝之

出版者

京都産業大学

雑誌

京都産業大学論集. 社会科学系列 (ISSN:02879719)

巻号頁・発行日

vol.22, pp.147-170, 2005-03

著者

菅原 俊治 横尾 真 松原 繁夫 岩崎 敦

出版者

日本電信電話株式会社NTTコミュニケーション科学基礎研究所

雑誌

基盤研究(C)

巻号頁・発行日

2005

---

本研究では,ネットワーク上の各リソースを市場原理に基づいて公平かつ効率的に割り当てるプロトコルを,その実装に向けて評価することを目的とする.P2Pや分散センサネットワークなどのアドホックなネットワークにおけるデータ転送では,個々のノードの所有者や規格が異なる.この場合,各ノードにデータを適切に転送するための誘因(報酬)を考慮しなければならない.この報酬の決定にはしばしばオークションプロトコルが用いられる.しかし従来のプロトコルでは,あるノードが架空のノードを用いるか他ノードと共謀することで,不正に報酬を獲得できることを示した.この場合、理論的にもっとも優れているVickrey-Clarke-Grovesプロトコル(VCG)でも、不正行為は防げない。本研究では、さらに、選択されうる経路を所有しているエージェントの数に応じたペナルティをVCGに適用し、Reserve-Costプロトコル(RC)を提案し、このプロトコルが架空名義を用いた操作の影響を受けないことを理論的に明らかにした。計算機上に再現した小世界ネットワークに対して、提案プロトコルを評価し、VCGに対して約60〜80%の効率性を達成することも示した。また実際のネットワークでは,各ノードでオークションなど取得可能な情報に基づいてどこからデータを受ける(送る)べきかを決定する必要がある.これは,入札可能な対象(サーバなど)が複数あるときに,適切な入札箇所をある程度推定することに相当する.しかし、ネットワークの資源割当てのように非常にたくさんの要求が同時に起こり、かつ多くの地点から独立に処理をする必要がある.このような状況で資源割り当てプロトコルで見られる現象の解析も行った。それぞれが合理的に判断をすると全体の効率が落ちる現象があり、このために揺らぎや学習を導入することが一定の効果を上げることを示した。

著者

東藤 大樹 李 潤樅 胡 雪梅 毛利 貴之 岩崎 敦 横尾 真

出版者

人工知能学会

雑誌

人工知能学会全国大会論文集 (ISSN:13479881)

巻号頁・発行日

vol.25, 2011

---

オークションにおける無羨望性とは,誰も他の参加者を羨まない,という公平性の基準である. しかし,組合せオークションでは参加者の選好が複雑となるため,単一の参加者に対する羨望はなくとも,参加者の集合に対する羨望が存在しうる. 本論文では,組合せオークションにおける公平性の新たな基準としてエージェントの集合に対する無羨望性を提案し,この無羨望性を持つ組合せオークションメカニズムを議論する.