著者
横尾 真 岩崎 敦 櫻井 祐子 岡本 吉央
出版者
日本ソフトウェア科学会
雑誌
コンピュータ ソフトウェア (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メカニズムを通して説明する.次に,従来は考えられていなかった課題を解決するためのメカニズムをどのように設計するかを解説するために,架空名義入札を取り上げる.加えて,メカニズムデザイン理論のよく知られた実践例である,検索連動型広告オークションとマッチングメカニズムの主要な結果に関して述べる.
著者
横尾 真 岩崎 敦 櫻井 祐子 岡本 吉央
出版者
日本ソフトウェア科学会
雑誌
コンピュータ ソフトウェア (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.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.32, no.5, pp.AG16-E_1-9, 2017-09-01 (Released:2017-09-01)
参考文献数
18

The cake cutting problem is concerned with the fair allocation of a divisible good among agents whose preferences vary over it. Recently, designing strategy-proof (SP) cake cutting mechanisms has caught considerable attention from AI and MAS researchers. Previous works assumed that an agent’s utility function is additive so that theoretical analysis becomes tractable. However, in practice, agents have non-additive utility over a resource. In this paper, we consider the all-or-nothing utility function as a representative example of non-additive utility because it can widely cover agents’ preferences for such real-world resources as the usage of meeting rooms, time slots for computational resources, bandwidth usage, and so on. We first show the incompatibility between envy-freeness (EF) and Pareto efficiency (PE) when each agent has all-or-nothing utility. We next propose a SP mechanism that satisfy PE, which is based on the serial dictatorship mechanism, at the sacrifice of EF. To address computational feasibility, we propose a heuristic-based allocation algorithm to find a near-optimal allocation in time polynomial in the number of agents, since the problem of finding a PE allocation is NP-hard. As another approach that abandons PE, we develop an EF and SP mechanism. Furthermore, we argue about false-name-proofness (FNP), which is the expansion of SP, and propose FNP and EF cake cutting mechanism. Finally, we evaluate our proposed mechanisms by computational experiments.
著者
岩崎 敦 横尾 真 寺田 賢二
出版者
一般社団法人 人工知能学会
雑誌
人工知能学会論文誌 (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.
著者
和田 凌司 八尋 健太郎 山口 知晃 東藤 大樹 横尾 真
出版者
一般社団法人 人工知能学会
雑誌
人工知能学会全国大会論文集 第33回全国大会(2019)
巻号頁・発行日
pp.4L2J1305, 2019 (Released:2019-06-01)

マッチング問題に関する既存研究の多くは,学生や学校の持つ選好が厳密に順序付けられている問題を前提としている.しかしながら,学生や学校が数多く存在する現実的な仮定の下で,互いの正確な情報を得ることは困難である.そこで本論文では,各エージェントの選好の一部が順序付けられていない,部分的な選好下における多対一マッチング問題を考察する.本論文の扱うモデルにおいて,学生が学校にインタビューを行うことにより,各エージェントは自分が潜在的に持つ選好を明確にできる.しかしながら,インタビューにはコストが生じると仮定するのが一般的である.そこで,必要最小限のインタビューを用いて,各エージェントの潜在的な選好を解明しつつ,望ましい割当を求めることが望まれる.部分的選好下での一対一マッチング問題においては,学生最適性を満たす割当を出力するメカニズムが提案されている.しかしながら,このメカニズムは,すべての学校に対して共通な部分的選好を仮定している.そこで本論文では,既存の仮定を緩和した整合性を満たす部分選好下での多対一マッチング問題において,学生最適性を満たす割当を出力するメカニズムを提案する.
著者
松原 繁夫 横尾 真 Shigeo Matsubara Makoto Yokoo
雑誌
人工知能学会誌 = Journal of Japanese Society for Artificial Intelligence (ISSN:09128085)
巻号頁・発行日
vol.15, no.5, pp.912-921, 2000-09-01

Internet and agent technologies have facilitated world-wide trade, but we sometimes encounter risky situation in exchange processes involving goods and money, i. e., fraud. This problem is becoming more serious with the growing popularity of person-to-person trade. One of the reasons for such fraud is that obtaining a new identifier in netwoeks is cheap. This makes it difficult to exclude malicious agents from trade. One solution is the imposition of an entry fee. However, if an entry fee is expensive, it discourages newcomers from starting deals. To resolve the conflict between safety and convenience, we have developed two kinds of exchange mechanisms that guarantee against defection from a contract. One reduces the entry fee by integrating multiple deals and controlling goods and money flows. We also show an extension of this mechanism that can reduce the entry fee more while taking a longer time to complete the exchange process. The other reduces the entry fee by incorporating a third party agent into the exchange process. We examine the lower bound of the entry fee for each mechanism and provide a calculation method that is able to obtain this value in linear time.
著者
伊原 尚正 鶴田 俊佑 東藤 大樹 櫻井 祐子 横尾 真
出版者
人工知能学会
雑誌
人工知能学会全国大会論文集 (ISSN:13479881)
巻号頁・発行日
vol.29, 2015

本論文ではケーキ分割問題において,参加者が任意の一定区間以上の割当を望む場合を対象とする.我々は,まず,パレート効率性を満たす戦略的操作不可能なメカニズムを提案する.しかしながら,パレート効率的な割当決定問題はNP困難であるため,多項式時間で割当を決定することを保証する戦略的操作不可能なケーキ分割メカニズムの提案を行う.さらに,計算機実験により割当に関する評価を行う.
著者
山本 駿 岩崎 敦 横尾 真 趙 登吉
出版者
人工知能学会
雑誌
人工知能学会全国大会論文集 (ISSN:13479881)
巻号頁・発行日
vol.28, 2014

不完全私的観測付き繰り返しゲームでは,同じゲームが繰り返しプレイされ,プレイヤは相手の行動を直接観測できず,ノイズを含むシグナルを観測する.本論文では,我々のグループが開発した,均衡判定プログラムをベースに,進化的アルゴリズムを用いて均衡となる戦略を発見するプログラムを提案する.繰り返し囚人のジレンマゲーム等の代表的なゲームに関して,このプログラムによって発見されたいくつかの新しい均衡を示す.
著者
横尾 真 神取 道宏 田村 明久 船木 由喜彦 関口 格 坂井 豊貴 平山 勝敏 尾山 大輔 安田 洋祐 岡本 吉央 岩崎 敦 川崎 雄二郎 小野 廣隆 櫻井 祐子 東藤 大樹 上田 俊 伊藤 孝行 小島 武仁 小原 一郎
出版者
九州大学
雑誌
基盤研究(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.