Kyushu University Academic Staff Educational and Research Activities Database
List of Papers
Taiki Todo Last modified date:2022.05.08

Associate Professor / Intelligent Systems / Department of Informatics / Faculty of Information Science and Electrical Engineering


Papers
1. Ilan Nehama, Taiki Todo, Makoto Yokoo, Manipulation-resistant false-name-proof facility location mechanisms for complex graphs, 2022.01.
2. 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.
3. Zhaohong Sun, Taiki Todo, Toby Walsh, Fair Pairwise Exchange among Groups, Proceedings of IJCAI 2021, 2021.08.
4. Zhaohong Sun, Taiki Todo, Makoto Yokoo, New Algorithms for Japanese Residency Matching, Proceedings of IJCAI 2021, 2021.08.
5. Takehiro Kawasaki, Ryoji Wada, Taiki Todo, Makoto Yokoo, Mechanism Design for Housing Markets over Social Networks, Proceedings of AAMAS 2021, 2021.05.
6. Taiki Todo, Mechanism Design with Uncertainty, Proceedings of IJCAI-2020, https://doi.org/10.24963/ijcai.2020/730 , 2020.07.
7. Taiki Todo and Makoto Yokoo, Split Manipulations in Cost Sharing of Minimum Cost Spanning Tree, The 24th European Conference on Artificial Intelligence (ECAI-20), 2020.06.
8. Taiki Todo, Nodoka Okada, and Makoto Yokoo, False-Name-Proof Facility Location on Discrete Structures, The 24th European Conference on Artificial Intelligence (ECAI-20), 2020.06.
9. 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..
10. Nodoka Okada, Taiki Todo, Makoto Yokoo, SAT-based automated mechanism design for false-name-proof facility location, Proceedings of the 22nd International Conference on Principles and Practice of Multi-Agent Systems (PRIMA 2019), 321-337, 2019.10.
11. Taiki Todo, Atsushi Iwasaki, Makoto Yokoo, Competitive auctions and envy-freeness for group of agents, Proceedings of the 25th International Computing and Combinatorics Conference (COCOON 2019), 541-553, 2019.07.
12. Ilan Nehama, Taiki Todo, Makoto Yokoo, Manipulations-resistant facility location mechanisms for ZV-line graphs, the 18th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS-19), 1452-1460, 2019.05, In many real-life scenarios, a group of agents needs to agree on a common action, e.g., on a location for a public facility, while there is some consistency between their preferences, e.g., all preferences are derived from a common metric space. The facility location problem models such scenarios and it is a well-studied problem in social choice. We study mechanisms for facility location on unweighted undirected graphs, which are resistant to manipulations (strategy-proof, abstention-proof, and false-name-proof) by both individuals and coalitions and are efficient (Pareto optimal). We define a family of graphs, ZV-line graphs, and show a general facility location mechanism for these graphs which satisfies all these desired properties. Our result unifies the few works in the literature of false-name-proof facility location on discrete graphs including the preliminary (unpublished) works we are aware of..
13. 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, 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..
14. Julien Lesca, Taiki Todo, Service Exchange Problem, the 27th International Joint Conference on Artificial Intelligence and the 23rd European Conference on Artificial Intelligence (IJCAI-ECAI-18), 354-360, 2018.07, In this paper, we study the service exchange problem where each agent is willing to provide her service in order to receive in exchange the service of someone else. We assume that agent’s preference depends both on the service that she receives and the person who receives her service. This framework is an extension of the housing market problem to preferences including a degree of externalities. We investigate the complexity of computing an individually rational and Pareto efficient allocation of services to agents for ordinal preferences, and the complexity of computing an allocation which maximizes either the utility sum or the utility of the least served agent for cardinal preferences..
15. Yuho Wada, Tomohiro Ono, Taiki Todo, Makoto Yokoo, Facility Location with Variable and Dynamic Populations, the 17th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS-18), 336-344, 2018.07.
16. Chi Kit Ken Fong, Minming Li, Pinyan Lu, Taiki Todo, Makoto Yokoo, Facility Location Games With Fractional Preferences, The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18), 1039-1046, 2018.02.
17. Takamasa Ihara, Shunsuke Tsuruta, Taiki Todo, Yuko Sakurai, Makoto Yokoo, Strategy-proof Cake Cutting Mechanisms for All-or-nothing Utility, Fundamenta Informaticae, 10.3233/FI-2018-1641, 158, 1-3, 41-61, 2018.01, 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 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 and Pareto efficiency when each agent has all-or-nothing utility. We next propose two strategy-proof mechanisms that satisfy Pareto efficiency, which are based on the serial dictatorship mechanism, at the sacrifice of envy-freeness. 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 Pareto efficient allocation is NP-hard. As another approach that abandons Pareto efficiency, we develop an envy-free mechanism and show that one of our serial dictatorship based mechanisms satisfies proportionality in expectation, which is a weaker definition of proportionality. Finally, we evaluate the efficiency obtained by our proposed mechanisms by computational experiments..
18. Tomohiro Ono, Taiki Todo, Makoto Yokoo, Rename and False-Name Manipulations in Discrete Facility Location with Optional Preferences, The 20th International Conference on Principles and Practice of Multi-Agent Systems (PRIMA-2017), 163-179, 2017.10.
19. Takamasa Ihara, Taiki Todo, Yuko Sakurai, Makoto Yokoo, Cake cutting for all-or-nothing utility, Transactions of the Japanese Society for Artificial Intelligence, 10.1527/tjsai.AG16-E, 32, 5, AG16-E_1-AG16-E_9, 2017.01, 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..
20. Mingyu Guo, Yuko Sakurai, Taiki Todo, Makoto Yokoo, Individually rational strategy-proof social choice with exogenous indifference sets, Nineteenth International Conference on Principles and Practice of Multi-Agent Systems (PRIMA-16), 2016.08.
21. Yuto Tominaga, Taiki Todo, Makoto Yokoo, Manipulations in Two-Agent Sequential Allocation with Random Sequences, Fifteenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS-16), 2016.05.
22. Akihisa Sonoda, Taiki Todo, Makoto Yokoo, False-name-proof locations of two facilities: Economic and algorithmic approaches, Thirtieth AAAI Conference on Artificial Intelligence (AAAI-16), 2016.02.
23. Takamasa Ihara, Shunsuke Tsuruta, Taiki Todo, Yuko Sakurai, Makoto Yokoo, Strategy-proof Cake Cutting for All-or-nothing Utility, Eighteenth Conference on Principles and Practice of Multi-agent Systems (PRIMA-15), 2015.10.
24. Zhaohong Sun, Taiki Todo, Makoto Yokoo, Exchange of Indivisible Objects with Asymmetry, Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-15), 2015.07.
25. Atsushi Iwasaki, Etsushi Fujita, Taiki Todo, Hidenao Iwane, Hirokazu Anai, Mingyu Guo, Makoto Yokoo, Parametric Mechanism Design via Quantifier Elimination (Extended Abstract), Fourteenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS-15), 2015.05.
26. Mingyu Guo, Hong Shen, Taiki Todo, Yuko Sakurai, Makoto Yokoo, Social Decision with Minimal Efficiency Loss: An Automated Mechanism Design Approach, Fourteenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS-15), 2015.05.
27. Shunsuke Tsuruta, Masaaki Oka, Taiki Todo, Yuko Sakurai, Makoto Yokoo, Fairness and False-Name Manipulations in Randomized Cake Cutting, Fourteenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS-15), 2015.05.
28. Hideaki Hata, Taiki Todo, Saya Onoue, Ken-ichi Matsumoto, Characteristics of Sustainable OSS Projects: A Theoretical and Empirical Study, Eighth International Workshop on Cooperative and Human Aspects of Software Engineering (CHASE-15), 2015.05.
29. 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.
30. Masaaki Oka, Taiki Todo, Yuko Sakurai, Makoto Yokoo, Predicting Own Action: Self-Fulfilling Prophecy induced by Proper Scoring Rules, Second AAAI Conference on Human Computation (HCOMP-14), 2014.11.
31. Dengji Zhao, Siqi Luo, Taiki Todo, Makoto Yokoo, False-name-proof Combinatorial Auction Design via Single-minded Decomposition, The Twenty-First European Conference on Artificial Intelligence, 2014.08, [URL].
32. Etsushi Fujita, Taiki Todo, Makoto Yokoo, Atsushi Iwasaki, VCG-equivalent in expectation mechanism, Computer Software, 31, 3, 156-167, 2014.08, In this paper, we develop a new class of iterative mechanisms called a VCG-equivalent in expectation mechanism. To guarantee that sincere strategies are an ex post equilibrium, it inevitably asks an irrelevant query, in which a participant has no incentive to answer the query sincerely. Such an irrelevant query causes unnecessary leakage of private information and a different incentive issue. In a VCG-equivalent in expectation mechanism, the mechanism achieves the same allocation as VCG, but the transfers are the same as VCG only in expectation. We show that in a VCG-equivalent in expectation mechanism, sincere strategies constitute a sequential equilibrium. Also, we develop a general procedure for constructing a VCG-equivalent in expectation mechanism that does not ask any irrelevant query. To demonstrate the applicability of this idea in a practical application, we develop a VCG-equivalent in expectation mechanism that can be applied to the Japanese 4G spectrum auction..
33. Taiki Todo, Haixin Sun, Makoto Yokoo, Strategyproof exchange with multiple private endowments, The Twenty-Eighth AAAI Conference on Artificial Intelligence, 2014.07.
34. Akihisa Sonoda, Etsushi Fujita, Taiki Todo, Makoto Yokoo, Two Case Studies for Trading Multiple Indivisible Goods with Indifferences, The Twenty-Eighth AAAI Conference on Artificial Intelligence, 2014.07.
35. Shunsuke Tsuruta, Masaaki Oka, Taiki Todo, Yujiro Kawasaki, Mingyu Guo, Yuko Sakurai, Makoto Yokoo, Optimal False-name-proof Single-item Redistribution Mechanisms, The Thirteenth International Conference on Autonomous Agents and Multiagent Systems, 2014.05.
36. Julien Lesca, Taiki Todo, Makoto Yokoo, Coexistence of Utilitarian Efficiency and False-name-proofness in Social Choice, The Thirteenth International Conference on Autonomous Agents and Multiagent Systems, 2014.05.
37. Atsushi Iwasaki, Etsushi Fujita, Taiki Todo, Miao Yao, Makoto Yokoo, VCG-equivalent Mechanism in Expectation: General Framework for Constructing Iterative Combinatorial Auction Mechanisms, The Twelfth International Conference on Autonomous Agents and Multiagent Systems, 699-706, 2013.05.
38. Taiki Todo, Vincent Conitzer, False-name-proof Matching, The Twelfth International Conference on Autonomous Agents and Multiagent Systems, 311-318, 2013.05.
39. Taiki Todo, Takayuki Mouri, Atsushi Iwasaki, Makoto Yokoo, False-name-proofness in Online Mechanisms, The Eleventh International Conference on Automous Agents and Multiagent Systems, 753-762, 2012.06.
40. Taiki Todo, Runcong Li, Xuemei Hu, Takayuki Mouri, Atsushi Iwasaki, Makoto Yokoo, Generalizing Envy-Freeness Toward Group of Agents, The Twenty-second International Joint Conference on Artificial Intelligence, 386-392, 2011.07.
41. Taiki Todo, Atsushi Iwasaki, Makoto Yokoo, False-name-proof Mechanism Design without Money, The Tenth International Conference on Autonomous Agents and Multiagent Systems, 651-658, 2011.05.
42. Taiki Todo, Atsushi Iwasaki, Makoto Yokoo, Characterization of revenue monotonicity in combinatorial auctions., The 2010 IEEE/WIC/ACM International Conference on Intelligent Agent Technology, 383-390, 2010.09.
43. Atsushi Iwasaki, Vincent Conitzer, Yoshifusa Omori, Yuko Sakurai, Taiki Todo, Mingyu Guo, Makoto Yokoo, Worst-case efficiency ratio in false-name-proof combinatorial auction mechanisms, The Ninth International Conference on Autonomous Agents and Multiagent Systems, 633-640, 2010.05.
44. Taiki Todo, Atsushi Iwasaki, Makoto Yokoo, Yuko Sakurai, Characterizing False-name-proof Allocation Rules in Combinatorial Auctions, The Eighth International Joint Conference on Autonomous Agents and Multiagent Systems, 265-272, 2009.05.
45. Takamasa Ihara, Shunsuke Tsuruta, Taiki Todo, Yuko Sakurai, Makoto Yokoo, Strategy-proof Cake Cutting Mechanisms for All-or-Nothing Utility, Fundamenta Informaticae.