文献一覧: 岡本吉央 (著者)

31 0 0 0 OA 『計算機科学者のためのゲーム理論入門』シリーズについて

著者: 横尾真岩崎敦櫻井祐子岡本吉央
出版者: 日本ソフトウェア科学会
雑誌: コンピュータソフトウェア (ISSN:02896540)
巻号頁・発行日: vol.29, no.2, pp.2_65-2_68, 2012-04-25 (Released:2012-06-25)

7 0 0 0 OA 『計算機科学者のためのゲーム理論入門』シリーズ第3回メカニズムデザイン(基礎編)

著者: 横尾真岩崎敦櫻井祐子岡本吉央
出版者: 日本ソフトウェア科学会
雑誌: コンピュータソフトウェア (ISSN:02896540)
巻号頁・発行日: vol.29, no.4, pp.4_15-4_31, 2012-10-25 (Released:2012-12-25)

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

7 0 0 0 OA 非協力ゲーム(基礎編)

著者: 横尾真岩崎敦櫻井祐子岡本吉央
出版者: 日本ソフトウェア科学会
雑誌: コンピュータソフトウェア (ISSN:02896540)
巻号頁・発行日: vol.29, no.2, pp.2_69-2_84, 2012-04-25 (Released:2012-06-25)

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

6 0 0 0 OA 『計算機科学者のためのゲーム理論入門』シリーズ第4回メカニズムデザイン(応用編)

著者: 横尾真岩崎敦櫻井祐子岡本吉央
出版者: 日本ソフトウェア科学会
雑誌: コンピュータソフトウェア (ISSN:02896540)
巻号頁・発行日: vol.30, no.1, pp.1_34-1_52, 2013-01-25 (Released:2013-03-25)

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

4 0 0 0 OA 「Cellチャレンジ2009」実施報告

著者: 中田尚吉見真聡片桐孝洋吉瀬謙二岡本吉央津邑公暁
雑誌: 研究報告計算機アーキテクチャ(ARC)
巻号頁・発行日: vol.2009-ARC-184, no.24, pp.1-6, 2009-07-28

先進的計算基盤システムシンポジウム SACSIS2009 併設企画として,マルチコアプログラミングコンテスト「Cell チャレンジ 2009」を開催した.文字列の編集距離を求める規定課題部門,および各チームが自由に課題を設定できる自由課題部門の 2 部門で行ったところ,のべ 77 チームの参加を集め,盛況に終えることができた.本稿では,Cell チャレンジ 2009 の実施報告を行う.

2020-01-19 17:22:23
4 + 5 Twitter

http://id.nii.ac.jp/1001/00062720/

4 0 0 0 OA 絵画的迷路の作り方 (理論計算機科学の深化と応用)

著者: 岡本吉央上原隆平
出版者: 京都大学数理解析研究所
雑誌: 数理解析研究所講究録 (ISSN:18802818)
巻号頁・発行日: vol.1649, pp.58-65, 2009-05

2012-06-14 03:27:56
4 + 10 Twitter

http://hdl.handle.net/2433/140755

3 0 0 0 OA 非協力ゲーム(発展編)

著者: 横尾真岩崎敦櫻井祐子岡本吉央
出版者: 日本ソフトウェア科学会
雑誌: コンピュータソフトウェア (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完全性について解説する.

2 0 0 0 OA 『計算機科学者のためのゲーム理論入門』シリーズ第5回協力ゲーム

著者: 横尾真岩崎敦櫻井祐子岡本吉央
出版者: 日本ソフトウェア科学会
雑誌: コンピュータソフトウェア (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に関する問題を効率的に解くことができるため,協力ゲームの簡潔な記述方法を概説する.

2023-02-24 19:16:43
2 + 2 Twitter

2 0 0 0 OA 持続可能な発展のための資源配分メカニズム設計理論の構築

著者: 横尾真神取道宏田村明久船木由喜彦関口格坂井豊貴平山勝敏尾山大輔安田洋祐岡本吉央岩崎敦川崎雄二郎小野廣隆櫻井祐子東藤大樹上田俊伊藤孝行小島武仁小原一郎
出版者: 九州大学
雑誌: 基盤研究(S)
巻号頁・発行日: 2012-05-31

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

2023-01-23 13:34:50
2 + 3 Twitter

https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-24220003/

2 0 0 0 Submodularity of some classes of the combinatorial optimization games〔和文〕

著者: 岡本吉央
出版者: 一般社団法人情報処理学会
雑誌: 情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)
巻号頁・発行日: vol.2002, no.70, pp.17-24, 2002-07-25

協力ゲーム理論において劣モジュラ性は非常に重要な性質であると認識されている.本論では,最小彩色ゲームと最小頂点被覆ゲームが劣モジュラ性を有する場合の特徴づけを示す.この特徴づけにより,与えられたグラフに対する最小彩色ゲーム/最小頂点被覆ゲームが劣モジュラであるかどうかを判定することが多項式時間で出来ることが分かる.それに関連して,ゲーム理論におけるシャプレイ値,および,付随するマトロイド構造についても述べる.Submodularity is considered as an important property in the field of cooperative game theory. In this report, we characterize submodular minimum coloring games and submodular minimum vertex cover games. These characterizations immediately show that it can be decided in polynomial time that the minimum coloring game or the minimum vertex cover game is submodular or not for a given graph. Related to these results, the Shapley values and the associated matroid structures are also investigated.