著者

岩崎 敦 東藤 大樹 Atsushi Iwasaki Taiki Todo

雑誌

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

巻号頁・発行日

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

著者

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

出版者

九州大学

雑誌

基盤研究(S)

巻号頁・発行日

2012-05-31

---

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

著者

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

出版者

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

雑誌

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

巻号頁・発行日

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

---

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

著者

岩崎 敦 東藤 大樹

出版者

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

雑誌

人工知能 (ISSN:21882266)

巻号頁・発行日

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

著者

岡田 和夏 和田 勇歩 東藤 大樹 横尾 真

出版者

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

雑誌

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

巻号頁・発行日

pp.2E1J103, 2019 (Released:2019-06-01)

---

我々は,充足可能性問題を解くソフトウェアであるSATソルバーを用いた計算機科学的アプローチで,多次元離散空間上の単一施設配置問題の解析を試みる.エージェントの選好は,自身の所在地から施設の配置位置までの距離が小さい程,効用が高いとする単峰的選好と,自身の所在地から施設の配置位置までの距離が大きい程,効用が高いと考える単溝的選好の2種類とする.本論文では,まず,グラフとエージェントの選好から,自動でCNF形式のSATインスタンスを生成するアルゴリズムの提案を行い,パレート効率性および架空名義操作不可能性に関する施設配置問題のSAT符号化を行った.次に,PicoSATを用いて実際に多次元離散空間上の施設配置問題を解き,パレート効率性および架空名義操作不可能性を同時に満たすメカニズムの存在性が,理論的結果と一致することを確認した.最後に,SATソルバーによって,サイズ2×3の格子空間において単溝的選好の場合,パレート効率性,架空名義操作不可能性,および全射性を同時に満たすメカニズムが存在しないことを示した.

著者

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

出版者

日本ソフトウェア科学会

雑誌

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

巻号頁・発行日

vol.29, 2015

---

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

著者

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

出版者

人工知能学会

雑誌

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

巻号頁・発行日

vol.25, 2011

---

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