著者

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

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (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:21882266)

巻号頁・発行日

vol.23, no.3, pp.357-361, 2008-05-01 (Released:2020-09-29)

著者

横尾 真 Makoto Yokoo 九州大学大学院システム情報科学研究院 Faculty of Information Science and Electrical Engineering Kyushu University

出版者

人工知能学会

雑誌

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

巻号頁・発行日

vol.23, no.3, pp.357-361, 2008-05-01

著者

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

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (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.17, no.2, pp.109-117, 2000-03-15

被引用文献数

10

著者

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

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (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.

著者

和田 凌司 八尋 健太郎 山口 知晃 東藤 大樹 横尾 真

出版者

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

雑誌

人工知能学会全国大会論文集 第33回全国大会(2019)

巻号頁・発行日

pp.4L2J1305, 2019 (Released:2019-06-01)

---

マッチング問題に関する既存研究の多くは,学生や学校の持つ選好が厳密に順序付けられている問題を前提としている.しかしながら,学生や学校が数多く存在する現実的な仮定の下で,互いの正確な情報を得ることは困難である.そこで本論文では,各エージェントの選好の一部が順序付けられていない,部分的な選好下における多対一マッチング問題を考察する.本論文の扱うモデルにおいて,学生が学校にインタビューを行うことにより,各エージェントは自分が潜在的に持つ選好を明確にできる.しかしながら,インタビューにはコストが生じると仮定するのが一般的である.そこで,必要最小限のインタビューを用いて,各エージェントの潜在的な選好を解明しつつ,望ましい割当を求めることが望まれる.部分的選好下での一対一マッチング問題においては,学生最適性を満たす割当を出力するメカニズムが提案されている.しかしながら,このメカニズムは,すべての学校に対して共通な部分的選好を仮定している.そこで本論文では,既存の仮定を緩和した整合性を満たす部分選好下での多対一マッチング問題において,学生最適性を満たす割当を出力するメカニズムを提案する.

著者

末原 剛志 竹内 孝 鹿島 久嗣 小山 聡 櫻井 祐子 横尾 真

雑誌

2023年度 人工知能学会全国大会(第37回)

巻号頁・発行日

2023-04-06

著者

横尾 真

出版者

日本ソフトウェア科学会

雑誌

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

巻号頁・発行日

vol.25, no.3, pp.3_60-3_65, 2008-07-25 (Released:2008-09-30)

著者

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

出版者

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

雑誌

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

巻号頁・発行日

vol.2011, pp.1F24, 2011

---

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

著者

横尾 真 山名 善之 岩岡 竜夫

出版者

日本建築学会

雑誌

日本建築学会計画系論文集 (ISSN:13404210)

巻号頁・発行日

vol.80, no.712, pp.1463-1471, 2015

---

&nbsp;This study aims to clarify architects' thoughts of &ldquo;A&Eacute;RO-CLUB ROLAND-GARROS &Agrave; BUC&rdquo;, which is the relationship between features and building components. It is about the features such as floor planning, concept of space, structure type, facility planning and also about the building components such as the assembly system as well as the list of all parts. The composition of this study includes the analysis of the features of this building and the analysis of the technological aspect of the building components. Finally, we discuss what kind of relationship the two has.

著者

横尾 真 山名 善之 岩岡 竜夫

出版者

日本建築学会

雑誌

日本建築学会技術報告集 (ISSN:13419463)

巻号頁・発行日

vol.21, no.48, pp.853-858, 2015

---

This study aims to clarify the design feature of Maison du Peuple de Clichy, which is located in the northwest of Paris and was designed by French architects in the late 1930&rsquo;s. As repair works have been carried out in recent years, it became possible for us to analyze this building. We are specifically focusing on the composition of each floor plan, the structure frame and two technical features. One is the prefabricated curtain wall panel which was the first in the world. The other is the system of moveable elements which can be used either as a market, a conference room or a cinema.

著者

横尾 真 山名 善之 岩岡 竜夫

出版者

日本建築学会

雑誌

日本建築学会計画系論文集 (ISSN:13404210)

巻号頁・発行日

no.739, pp.2421-2429, 2017-09

---

&nbsp;&ldquo;Maison d&eacute;montable en ancier B. L. P. S.&rdquo; was designed by French architects Eugene Beaudouin, Marcel Lods, Jean Prouv&eacute;, and Forges de Strasbourg as a constructor in 1936. An external form is 3.3m&times;3.3m, this small house is used for 2 persons. It consists a living room with 2 beds and a dining table, a kitchen space, a toilet and shower space and also could assemble and be demountable at anywhere. The begginig of this small house was made a prototype at Ateliers Jean Prouv&eacute; that was presented at the sixth exposition de l'habitation in the salon des arts m&eacute;nagers in January 1939. All parts not only the entire house but also furniture were made of the thin steel sheets, there was not the foundation by Reinforced concrete. When Lods demonstrated at the exposition, in fact he could assemble for 2.5 hours and be demountable for 45 minutes. In the same year, someone stolen this small house before begining World War II, and it can never be seen anywhere.<br>&nbsp;As a background and purpose of this study, it aims to clarify architects' thoughts of &ldquo;Maison d&eacute;montable en ancier B. L. P. S. &ldquo;, which focuses on the relationship between features and building components. It is about the features such as floor planning, concept of space, structure type, facility planning, and also about the building components such as the assembly system as well as the list of all parts. Finally, we discuss what kind of relationship the two has.<br>&nbsp;The previously-mentioned 3 French architects collaborated mainly in 3 projects, this small house is one of them, and its second project. Prouv&eacute; has explained through an interview in the book that was written by Peter Sulzer in 2000, it is &ldquo;B. L. P. S. entirely made at my place&hellip; an enormous number of innovations&hellip; like the system of assembling the panels...&rdquo;. Besides Franz Graf has explained that this small house, it's design, has been a great help in designing the fa&ccedil;ade of the Medische Faculteit in Rotterdam (today: Erasmus MC) by Prouv&eacute;, built in 1968. This means that Prouv&eacute; used the similar details in different project 30 years past, it could also say to find an importance innovation in this small house.<br>&nbsp;As a result, we found that important design through to clarify features and building components of &ldquo;Maison d&eacute;montable en ancier B. L. P. S.&rdquo;. It is consisted by 5 building components which are the roof panel, the floor panel, the wall panel, the facility unit, the funiture unit, and they are a set for 2 components. Each of them has a meanings, such as it plays a role as Instruction how to assemble or where sets a position for the next assembled parts. Detail of the joints which connects between building components, has same detail, it can say that a set of building components are able to use turning upside down and is possible to make entire building what it is designed 2 building components by same one without the floor panels and the facility unit.

著者

横尾 真

出版者

東京理科大学

巻号頁・発行日

2016

---

2015

著者

横尾 真 山名 善之 岩岡 竜夫

出版者

日本建築学会

雑誌

日本建築学会計画系論文集 (ISSN:13404210)

巻号頁・発行日

vol.80, no.712, pp.1463-1471, 2015 (Released:2015-07-11)

参考文献数

15

---

This study aims to clarify architects' thoughts of “AÉRO-CLUB ROLAND-GARROS À BUC”, which is the relationship between features and building components. It is about the features such as floor planning, concept of space, structure type, facility planning and also about the building components such as the assembly system as well as the list of all parts. The composition of this study includes the analysis of the features of this building and the analysis of the technological aspect of the building components. Finally, we discuss what kind of relationship the two has.