九州大学-研究者情報 [東藤大樹 (准教授) システム情報科学研究院情報学部門]

Establishing a Theory for Exchange of Multiple Indivisible Goods with Indifferences
2015.04～2016.03, 代表者：Taiki Todo, Kyushu University, Kyushu University.

研究業績

主要原著論文

全てを見る→

1.	Koji Osoegawa, Taiki Todo, Makoto Yokoo, False-Name-Proof Facility Location on Wheel Graphs, Proceedings of PRIMA 2022, 10.1007/978-3-031-21203-1_9, 2022.11.
2.	Sung-Ho Cho, Taiki Todo, Makoto Yokoo, Two-Sided Matching over Social Networks, Proceedings of IJCAI 2022, 10.24963/ijcai.2022/27, 2022.07.
3.	Bo You, Ludwig Dierks, Taiki Todo, Minming Li, Makoto Yokoo, Strategy-Proof House Allocation with Existing Tenants over Social Networks, Proceedings of AAMAS 2022, 2022.05.
4.	Ilan Nehama, Taiki Todo, Makoto Yokoo, Manipulation-resistant false-name-proof facility location mechanisms for complex graphs, Autonomous Agents and Multi-Agent Systems, 10.1007/s10458-021-09535-5, 2022.01.
5.	Taiki Todo, Ryoji Wada, Kentaro Yahiro, Makoto Yokoo, Lazy Gale-Shapley for Many-to-One Matching with Partial Information, Proceedings of ADT 2021, 2021.09.
6.	Zhaohong Sun, Taiki Todo, Makoto Yokoo, New Algorithms for Japanese Residency Matching, Proceedings of IJCAI 2021, 2021.08.
7.	Takehiro Kawasaki, Ryoji Wada, Taiki Todo, Makoto Yokoo, Mechanism Design for Housing Markets over Social Networks, Proceedings of AAMAS 2021, 2021.05.
8.	Takehiro Kawasaki, Nathanael Barrot, Seiji Takanashi, Taiki Todo, and Makoto Yokoo, Strategy-Proof and Non-Wasteful Multi-Unit Auction via Social Network, The 34th AAAI Conference on Artificial Intelligence (AAAI-2020), 2020.02, Auctions via social network, pioneered by Li et al. (2017), have been attracting considerable attention in the literature of mechanism design for auctions. However, no known mechanism has satisfied strategy-proofness, non-deficit, non-wastefulness, and individual rationality for the multi-unit unit-demand auction, except for some naı̈ve ones. In this paper, we first propose a mechanism that satisfies all the above properties. We then make a comprehensive comparison with two naı̈ve mechanisms, showing that the proposed mechanism dominates them in social surplus, seller’s revenue, and incentive of buyers for truth-telling. We also analyze the characteristics of the social surplus and the revenue achieved by the proposed mechanism, including the constant approximability of the worst-case efficiency loss and the complexity of optimizing revenue from the seller’s perspective..
9.	Etsushi Fujita, Julien Lesca, Akihisa Sonoda, Taiki Todo, Makoto Yokoo, A complexity approach for core-selecting exchange under conditionally lexicographic preferences, Journal of Artificial Intelligence Research, 10.1613/jair.1.11254, 63, 515-555, 2018.11, [URL], Core-selection is a crucial property of rules in the literature of resource allocation. It is also desirable, from the perspective of mechanism design, to address the incentive of agents to cheat by misreporting their preferences. this paper investigates the exchange problem where (i) each agent is initially endowed with (possibly multiple) indivisible goods, (ii) agents' preferences are assumed to be conditionally lexicographic, and (iii) side payments are prohibited. We propose an exchange rule called augmented top-trading-cycles (ATTC), based on the original TTC procedure. We first show that ATTC is core-selecting and runs in polynomial time with respect to the number of goods. We then show that finding a beneficial misreport under ATTC is NP-hard. We finally clarify relationship of misreporting with splitting and hiding, two different types of manipulations, under ATTC..

主要総説, 論評, 解説, 書評, 報告書等

全てを見る→

主要学会発表等

全てを見る→

1.	東藤大樹, マルチエージェントシステムとゲーム理論，そしてこれから, JSAI-22 企画セッション『マルチエージェントとは何か？』, 2022.06.
2.	Taiki Todo, Housing Markets over Social Networks, Dagstuhl Seminar 21241: Coalition Formation Games, 2021.06.
3.	Taiki Todo, Social Choice with Variable Populations, The 23rd International Conference on Principles and Practice of Multi-Agent Systems (PRIMA-2020), 2020.11, Social choice theory is one of the well-studied mathematical foundations of decision making for multi-agent systems. In the literature of social choice theory, the number of agents in the system is usually assumed to be a constant, and different social choice functions can be applied to different populations. When the number of agents is treated as a variable, e.g., not observable a priori, however, a social choice function must be carefully designed so that it can accept any possible population as input. Indeed, for the open, anonymous, and dynamic environments, the number of agents is not likely observable for the decision maker. In this talk, I will review some traditional models of social choice, introduce possible extensions of them for variable populations, and discuss the relation with mechanism design..
4.	Taiki Todo, Market Design with Uncertainty, the 29th International Joint Conference on Artificial Intelligence and the 17th Pacific Rim International Conference on Artificial Intelligence (IJCAI-PRICAI-2020), 2021.01, My research is summarized as mechanism design with uncertainty. Traditional mechanism design focuses on static environments where all the (possibly probabilistic) information about the agents are observable by the mechanism designer. In practice, however, it is possible that the set of participating agents and/or some of their actions are not observable a priori. We therefore focused on various kinds of uncertainty in mechanism design and developed/analyzed several market mechanisms that incentivise agents to behave in a sincere way..
5.	東藤大樹, 投票ルール設計のためのアルゴリズム的ゲーム理論, 情報科学技術フォーラム2020（FIT2020）, 2020.09, ミクロ経済学における投票とは、複数の候補者の集合から、投票者の投票をもとに唯一の当選者を選ぶ、社会選択の伝統的な数理モデルの１つである。近年では、本セッションのテーマでもある計算論的社会選択理論や、アルゴリズム的ゲーム理論 (algorithmic game theory) と呼ばれる、情報学と経済学との境界領域の発展に伴い、一般的な投票ルールの設計のほか、より制限された施設配置と呼ばれるモデルのための投票ルール（施設配置ルール）の設計が注目を集めている。本講演の目的は、投票と施設配置に関して、基礎的な知識を提供するとともに、特に情報学分野における最新の研究動向を紹介することである。まず、ギバード・サタースウェイトの定理や中位投票者ルールといった、経済学分野において得られてきた有名な研究成果を説明する。その後、施設配置ルールのアルゴリズム的ゲーム理論に基づく分析や、計算機を用いた投票ルールの自動設計に関する最新の研究動向を、講演者の研究成果と最近の興味を交えつつ紹介する。.
6.	東藤大樹, 交換のマーケットデザイン, 群体数理技術検討会, 2018.11.
7.	東藤大樹, マーケットデザインとゲーム理論, 創発システムシンポジウム2018, 2018.09, [URL].
8.	Etsushi Fujita, Julien Lesca, Akihisa Sonoda, Taiki Todo, Makoto Yokoo, A Complexity Approach for Core-Selecting Exchange with Multiple Indivisible Goods under Lexicographic Preferences, Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI-15), 2015.01.

学会活動

所属学会名

Association for Computing Machinery (ACM)

Association for the Advancement of Artificial Intelligence (AAAI)

日本ソフトウェア科学会

人工知能学会

情報処理学会

学協会役員等への就任

2023.04～2025.05, 人工知能学会, 代議員.

2021.04～2023.03, 日本ソフトウェア科学会, 代表会員.

2019.04～2021.03, マルチエージェントと協調計算研究会, リエゾン企画委員.

2017.04～2019.03, マルチエージェントと協調計算研究会, 運営委員.

学会大会・会議・シンポジウム等における役割

2020.09.08～2020.09.10, 日本ソフトウェア科学会第37回大会, 運営副委員長.

2020.07.11～2020.07.17, IJCAI-PRICAI-20, Program Committee.

2020.06.09～2020.06.12, 2020年度人工知能学会全国大会（第34回）, 学生企画委員.

2020.06.08～2020.06.12, ECAI-20, Program Committee.

2020.05.09～2020.05.13, AAMAS-20, Senior Program Committee.

2020.02.07～2020.02.12, AAAI-20, Senior Program Committee.

2019.05.13～2019.05.17, AAMAS-19, Senior Program Committee.

2018.10.29～2018.11.02, PRIMA 2018: The 21st International Conference on Principles and Practice of Multi-Agent Systems, Finance Chair.

2018.09.13～2019.09.15, 合同エージェントワークショップ＆シンポジウム2018 (JAWS 2018), プログラム委員長.

2017.09.19～2017.09.21, 日本ソフトウェア科学会第34回大会, デモ・ポスター委員長.

2017.09.15～2017.09.17, 合同エージェントワークショップ＆シンポジウム2017 (JAWS 2017), オーガナイズドセッションチェア.

2017.05.08～2017.05.12, The Sixteenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2017), Program Committee.

2017.02.04～2017.02.09, The Thirty-First AAAI Conference on Artificial Intelligence (AAAI 2017), Program Committee.

2016.05.09～2016.05.13, The Fifteenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2016), Program Committee.

2016.02.12～2016.02.17, The Thirtieth AAAI Conference on Artificial Intelligence (AAAI 2016) , Program Committee.

2015.09.30～2015.10.02, 合同エージェントワークショップ＆シンポジウム2015 (JAWS 2015) , Senior Program Committee.

2015.07.26～2015.07.26, IJCAI-15 Workshop on Innovative Application of Game Theory and Market Design, Co-Organizer.

2015.07.25～2015.07.31, The Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015), Program Committee.

2015.05.04～2015.05.08, The Fourteenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2015), Program Committee.

2015.01.25～2015.01.29, The Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI 2015), Program Committee.

2014.10.27～2014.10.29, 合同エージェントワークショップ＆シンポジウム2014 (JAWS 2014), Senior Program Committee.

2014.08.17～2014.08.18, The Second International Workshop on Market Design Technologies for Sustainable Development, Co-Organizer.

2014.08.17～2014.08.18, The Second International Workshop on Market Design Technologies for Sustainable Development, 司会（Moderator）.

2014.06.08～2014.06.12, The 15th ACM Conference on Economics and Computation (EC 2014), Program Committee.

2014.05.05～2014.05.09, The 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2014), Program Committee.

2013.11.26～2013.11.28, The First International Workshop on Market Design Technologies for Sustainable Development, Co-Organizer.

2013.11.26～2013.11.28, The First International Workshop on Market Design Technologies for Sustainable Development, 司会（Moderator）.

2013.09.17～2013.09.20, 合同エージェントワークショップ＆シンポジウム2013 (JAWS 2013), Program Committee.

2013.05.06～2013.05.10, The 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2013), Program Committee.

2012.10.24～2012.10.26, 合同エージェントワークショップ＆シンポジウム2012 (JAWS 2012), Program Committee.

学会誌・雑誌・著書の編集への参加状況

2018.04～2019.11, 情報処理学会論文誌「エージェント理論・技術とその応用」特集, 国内, 副編集委員長.

学術論文等の審査

年度	外国語雑誌査読論文数	日本語雑誌査読論文数	国際会議録査読論文数	国内会議録査読論文数	合計
2018年度	3	2	13		18
2017年度	2	2	16	2	22
2014年度	2	1	25	3	31
2013年度	1	1	16	3	21
2012年度	1	1	13	2	17

その他の研究活動

海外渡航状況, 海外での教育研究歴

LAMSADE, Paris Dauphine University, France, 2017.01～2017.01.

City University of Hong Kong, Hong Kong , 2016.09～2017.02.

The University of Adelaide, Australia, 2015.10～2015.12.

The University of Adelaide, Australia, 2015.03～2015.04.

Duke University, UnitedStatesofAmerica, 2012.04～2013.02.

外国人研究者等の受入れ状況

2021.05～2021.06, 1ヶ月以上, 九州大学, China, 日本学術振興会.

受賞

情報処理学会シニア会員, 一般社団法人情報処理学会, 2020.09.

JAWS2019 優秀論文賞, 第18回合同エージェントワークショップ＆シンポジウム2019 運営委員会, 2019.09.

JAWS2019 最優秀論文賞, 第18回合同エージェントワークショップ＆シンポジウム2019 運営委員会, 2019.09.

船井ベストペーパー賞, 情報科学技術フォーラム (FIT) 2014, 2014.09.

2011年度九州大学大学院システム情報科学府優秀学生表彰, 九州大学大学院システム情報科学府, 2012.03.

2011年度論文賞, 情報処理学会, 2012.03.

船井ベストペーパー賞, 情報科学技術フォーラム(FIT)2011, 2011.09.

ヤングリサーチャー賞, 情報科学技術フォーラム(FIT)2010, 2011.09.

Best Paper Award, iJAWS2010, 2010.10.

情報科学技術フォーラム論文賞, 情報科学技術フォーラム(FIT)2010, 2010.09.

IAT2010 Best Paper Award Nomination, 2010 IEEE/EIC/ACM International Conference on Intelligent Agent Technologies, 2010.09.

テレコムシステム技術学生賞, 電気通信普及財団, 2010.02.

学生研究奨励賞, IEEE福岡支部, 2010.01.

第23回人工知能学会全国大会優秀賞, 人工知能学会, 2009.09.

AAMAS2009 Pragnesh jay Modi Best Student Paper Award Nomination, International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2009.05.

研究資金

科学研究費補助金の採択状況(文部科学省、日本学術振興会)

2020年度～2023年度, 基盤研究(A), 代表, マルチエージェント最適化の数理基盤.

2017年度～2019年度, 基盤研究(A), 分担, マーケットデザインの実践的理論の構築.

2017年度～2020年度, 若手研究(A), 代表, 一般化交換問題のためのゲーム理論的／アルゴリズム論的解法の提案.

2012年度～2016年度, 基盤研究(S), 分担, 持続可能な発展のための資源配分メカニズム設計理論の構築.

2010年度～2012年度, 特別研究員奨励費, 代表, 動的で不確実な環境下での合意形成メカニズムの設計技術の確立.

2014年度～2016年度, 挑戦的萌芽研究, 分担, 限量子消去法を用いたパラメトリックメカニズム設計技術の確立.

2014年度～2015年度, 若手研究(B), 代表, インセンティブを考慮したアルゴリズム設計の基礎理論.

日本学術振興会への採択状況(科学研究費補助金以外)

2014年度～2016年度, 頭脳循環を加速する戦略的国際研究ネットワーク推進プログラム, 分担, ソフトウェアエコシステムの理論構築と実践を加速する分野横断国際ネットワークの構築.

競争的資金(受託研究を含む)の採択状況

2016年度～2017年度, 大川情報通信基金 2016年度研究助成, 代表, 最適性を保証する制約付き両方向マッチングのメカニズム設計.

2015年度～2015年度, Microsoft Research CORE11, 代表, Establishing a Theory for Exchange of Multiple Indivisible Goods with Indifferences.

寄附金の受入状況

2016年度, 公益財団法人大川情報通信基金, 最適性を保証する制約付き両方向マッチングのメカニズム設計.

2014年度, 日本マイクロソフト, Establishing Theory for Exchange of Multiple Indivisible Goods with Indifferences.

九大関連コンテンツ

pure2017年10月2日から、「九州大学研究者情報」を補完するデータベースとして、Elsevier社の「Pure」による研究業績の公開を開始しました。

QIR　九州大学学術情報リポジトリシステム情報科学研究院

システム情報科学研究院


	※ 研究者情報全体を検索する場合は右端の「すべて」を選択して下さい。