著者

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

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (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メカニズムを通して説明する.次に,従来は考えられていなかった課題を解決するためのメカニズムをどのように設計するかを解説するために,架空名義入札を取り上げる.加えて,メカニズムデザイン理論のよく知られた実践例である,検索連動型広告オークションとマッチングメカニズムの主要な結果に関して述べる.

著者

黒田 彗莉 大熊 智子 高野 雅典 森田 千絵 櫻井 祐子 清田 陽司

出版者

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

雑誌

人工知能 (ISSN:21882266)

巻号頁・発行日

vol.37, no.5, pp.640-648, 2022-09-01 (Released:2022-09-01)

著者

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

出版者

日本ソフトウェア科学会

雑誌

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

巻号頁・発行日

vol.37, no.3, pp.323-328, 2022-05-01 (Released:2022-05-01)

著者

上田 晴康 加藤 恒昭 斎藤 博昭 櫻井 祐子 小林 一郎

雑誌

人工知能

巻号頁・発行日

vol.34, 2019-03-01

著者

櫻井 祐子

出版者

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

雑誌

人工知能 (ISSN:21882266)

巻号頁・発行日

vol.38, no.5, pp.750-756, 2023-09-01 (Released:2023-09-01)

著者

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

雑誌

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

巻号頁・発行日

2023-04-06

著者

デイヴィッド・ローベンハイマー スティーヴン・J.シンプソン著 櫻井祐子訳

出版者

サンマーク出版

巻号頁・発行日

2021

著者

伊原 尚正 東藤 大樹 櫻井 祐子 横尾 真

出版者

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

雑誌

人工知能学会論文誌 (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.

著者

ジェネビーブ・ボン・ペッツィンガー著 櫻井祐子訳

出版者

文藝春秋

巻号頁・発行日

2016

著者

伊原 尚正 鶴田 俊佑 東藤 大樹 櫻井 祐子 横尾 真

出版者

人工知能学会

雑誌

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

巻号頁・発行日

vol.29, 2015

---

本論文ではケーキ分割問題において,参加者が任意の一定区間以上の割当を望む場合を対象とする.我々は,まず,パレート効率性を満たす戦略的操作不可能なメカニズムを提案する.しかしながら,パレート効率的な割当決定問題はNP困難であるため,多項式時間で割当を決定することを保証する戦略的操作不可能なケーキ分割メカニズムの提案を行う.さらに,計算機実験により割当に関する評価を行う.

著者

櫻井 祐子 横尾 真 湊 真一

出版者

九州大学

雑誌

基盤研究(C)

巻号頁・発行日

2011-04-28

---

効率的な提携を形成すること(提携構造形成問題)は,人工知能やマルチエージェントシステムの研究領域において,重要な研究分野となっている.本研究課題では,多分岐ゼロサプレス型BDD~(MTZDD)を応用し,(1) あらゆる特性関数を記述可能,(2) 既存の表現法よりも指数的に簡略化可能な場合が存在,(3) コアに関する問題をMTZDDのノード数の多項式時間で求解可能,(4) 提携構造形成問題は混合整数計画法を用いることで,既存アルゴリズムよりも高速に解を求めることが求解可能といった性質を持つ簡略記述法の提案などを行った.これらの研究成果は,国際会議 PRIMA2011で優秀論文賞を受賞した.

著者

櫻井 祐子 横尾 真

出版者

人工知能学会

雑誌

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

巻号頁・発行日

vol.24, 2010

---

検索エンジンでキーワード検索を行うと,検索結果と共に関連する広告が表示される.広告の掲載順位は,広告主がキーワードに対して入札を行い,その入札結果に応じて決定される.このようなオークションは,検索連動型広告オークションと呼ばれる.本論文では,検索連動型広告オークションにおいて,広告主の表示方法に関する選好を考慮し,掲載数を最適化する検索連動型広告オークションメカニズムの提案を行う.

著者

西村 直史 大田 直樹 櫻井 祐子 岩崎 敦 横尾 真

出版者

人工知能学会

雑誌

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

巻号頁・発行日

vol.23, 2009

---

ある程度規模の大きい学会では,様々な制約条件や価値基準を満足する会議プログラムを手作業で作成することは困難であり,大きな労力が伴う.そのため著者らは,制約充足/最適化のテクニックを用いた会議プログラムの自動生成ツールを開発した.本論文では,開発したツールを用いて実際の2008年度人工知能学会全国大会のプログラムを作成した結果と,大会終了後に行なったツールの改良について報告する.