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

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


Presentations
1. Takamasa Ihara, Shunsuke Tsuruta, Taiki Todo, Yuko Sakurai, Makoto Yokoo, Strategy-proof cake cutting mechanisms for all-or-nothing utility, 18th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2015, 2015.01, The cake cutting problem must fairly allocate a divisible good among agents who have varying preferences 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 functions over a resource. In this paper, we consider the allor-nothing utility function as a representative example of non-additive utility because it can widely cover agents’ preferences for real-world resources, such 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 a serial dictatorship mechanism, at the sacrifice of envy-freeness. To address computational feasibility, we propose an approximation 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 abandon 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..
2. Zhaohong Sun, Hideaki Hata, Taiki Todo, Makoto Yokoo, Exchange of indivisible objects with asymmetry, 24th International Joint Conference on Artificial Intelligence, IJCAI 2015, 2015.01, In this paper we study the exchange of indivisible objects where agents' possible preferences over the objects are strict and share a common structure among all of them, which represents a certain level of asymmetry among objects. A typical example of such an exchange model is a re-scheduling of tasks over several processors, since all task owners are naturally assumed to prefer that their tasks are assigned to fast processors rather than slow ones. We focus on designing exchange rules (a.k.a. mechanisms) that simultaneously satisfy strategyproofness, individual rationality, and Pareto efficiency. We first provide a general impossibility result for agents' preferences that are determined in an additive manner, and then show an existence of such an exchange rule for further restricted lexicographic preferences. We finally find that for the restricted case, a previously known equivalence between the single-valuedness of the strict core and the existence of such an exchange rule does not carry over..
3. Etsushi Fujita, Julien Lesca, Akihisa Sonoda, Taiki Todo, Makoto Yokoo, A complexity approach for core-selecting exchange with multiple indivisible goods under lexicographic preferences, 29th AAAI Conference on Artificial Intelligence, AAAI 2015 and the 27th Innovative Applications of Artificial Intelligence Conference, IAAI 2015, 2015.06, Core-selection is a crucial property of social choice functions, or rules, in social choice literature. It is also desirable to address the incentive of agents to cheat by misreporting their preferences. This paper investigates an exchange problem where each agent may have multiple indivisible goods, agents' preferences over sets of goods are assumed to be lexicographic, and side payments are not allowed. We propose an exchange rule called augmented top-trading-cycles (ATTC) procedure based on the original TTC procedure. We first show that the ATTC procedure is core-selecting. We then show that finding a beneficial misreport under the ATTC procedure is NP-hard. Under the ATTC procedure, we finally clarify the relationship between preference misreport and splitting, which is a different type of manipulation..
4. Hideaki Hata, Taiki Todo, Saya Onoue, Kenichi Matsumoto, Characteristics of sustainable OSS projects
A theoretical and empirical study, 8th International Workshop on Cooperative and Human Aspects of Software Engineering, CHASE 2015, 2015.07, How can we attract developers? What can we do to incentivize developers to write code? We started the study by introducing the population pyramid visualization to software development communities, called software population pyramids, and found a typical pattern in shapes. This pattern comes from the differences in attracting coding contributors and discussion contributors. To understand the causes of the differences, we then build game-theoretical models of the contribution situation. Based on these results, we again analyzed the projects empirically to support the outcome of the models, and found empirical evidence. The answers to the initial questions are clear. To incentivize developers to code, the projects should prepare documents, or the projects or third parties should hire developers, and these are what sustainable projects in Git Hub did in reality. In addition, making innovations to reduce the writing costs can also have an impact in attracting coding contributors..
5. Akihisa Sonoda, Taiki Todo, Makoto Yokoo, False-name-proof locations of two facilities
Economic and algorithmic approaches, 30th AAAI Conference on Artificial Intelligence, AAAI 2016, 2016, This paper considers a mechanism design problem for locating two identical facilities on an interval, in which an agent can pretend to be multiple agents. A mechanism selects a pair of locations on the interval according to the declared singlepeaked preferences of agents. An agent's utility is determined by the location of the better one (typically the closer to her ideal point). This model can represent various application domains. For example, assume a company is going to release two models of its product line and performs a questionnaire survey in an online forum to determine their detailed specs. Typically, a customer will buy only one model, but she can answer multiple times by logging onto the forum under several email accounts. We first characterize possible outcomes of mechanisms that satisfy false-name-proofness, as well as some mild conditions. By extending the result, we completely characterize the class of false-name-proof mechanisms when locating two facilities on a circle.We then clarify the approximation ratios of the false-name-proof mechanisms on a line metric for the social and maximum costs. 1 Introduction..
6. Mingyu Guo, Yuko Sakurai, Taiki Todo, Makoto Yokoo, Individually rational strategy-proof social choice with exogenous indifference sets, 19th International Conference on Princiles and Practice of Multi-Agent Systems, PRIMA 2016, 2016.01, We consider a social choice problem where individual rationality is required. The status quo belongs to the outcome space, and the selected alternative must be weakly better than the status quo for everybody. If the mechanism designer has no knowledge of the alternatives, we obtain a negative result: any individually rational (IR) and strategy-proof (SP) mechanism can choose at most one alternative (besides the status quo), regardless of the preferences. To overcome this negative result, we consider a domain where the alternatives have a known structure, i.e., an agent is indifferent between the status quo and a subset of the outcomes. This set is exogenously given and public information. This assumption is natural if the social choice involves the participation of agents. For example, consider a group of people organizing a trip where participation is voluntary. We can assume each agent is indifferent between the trip plans in which she does not participate and the status quo (i.e., no trip). In this setting, we obtain more positive results: we develop a class of mechanisms called Approve and Choose mechanisms, which are IR and SP, and can choose multiple alternatives as well as the status quo..
7. Tomohiro Ono, Taiki Todo, Makoto Yokoo, Rename and False-Name Manipulations in Discrete Facility Location with Optional Preferences, 20th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2017, 2017.01, We consider the problem of locating facilities on a discrete acyclic graph, where agents’ locations are publicly known and the agents are requested to report their demands, i.e., which facilities they want to access. In this paper, we study the effect of manipulations by agents that utilize vacant vertices. Such manipulations are called rename or false-name manipulations in game theory and mechanism design literature. For locating one facility on a path, we carefully compare our model with traditional ones and clarify their differences by pointing out that some existing results in the traditional model do not carry over to our model. For locating two facilities, we analyze the existing and new mechanisms from a perspective of approximation ratio and provide non-trivial lower bounds. Finally, we introduce a new mechanism design model where richer information is available to the mechanism designer and show that under the new model false-name-proofness does not always imply population monotonicity..
8. Julien Lesca, Taiki Todo, Service exchange problem, 27th International Joint Conference on Artificial Intelligence, IJCAI 2018, 2018.01, 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..
9. Yuho Wada, Tomohiro Ono, Taiki Todo, Makoto Yokoo, Facility location with variable and dynamic populations, 17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018, 2018.01, Facility location is a well-studied problem in social choice literature. where agents' preferences are restricted to be single-peaked. When the number of agents is treated as a variable (e.g., not observable a priori), a social choice function must be defined so that it can accept any possible number of preferences as input. Furthermore, there exist cases where multiple choices must be made continuously while agents dynamically arrive/leave. Under such variable and dynamic populations, a social choice function needs to give each agent an incentive to sincerely report her existence. In this paper we investigate facility location models with variable and dynamic populations. For a static, i.e., one-shot, variable population model, we provide a necessary and sufficient condition for a social choice function to satisfy participation, as well as truthfulness, anonymity, and Pareto efficiency. The condition is given as a further restriction on the well-known median voter schemes. For a dynamic model, we first propose an online social choice function, which is optimal for the total sum of the distances between the choices in the previous and current periods, among any Pareto efficient functions. We then define a generalized class of online social choice functions and compare their performances both theoretically and experimentally..
10. Ken C.K. Fong, Minming Li, Pinyan Lu, Taiki Todo, Makoto Yokoo, Facility location games with fractional preferences, 32nd AAAI Conference on Artificial Intelligence, AAAI 2018, 2018.01, In this paper, we propose a fractional preference model for the facility location game with two facilities that serve the similar purpose on a line where each agent has his location information as well as fractional preference to indicate how well they prefer the facilities. The preference for each facility is in the range of [0, L] such that the sum of the preference for all facilities is equal to 1. The utility is measured by subtracting the sum of the cost of both facilities from the total length L where the cost of facilities is defined as the multiplication of the fractional preference and the distance between the agent and the facilities. We first show that the lower bound for the objective of mini-1 mizing total cost is at least Ω(n3). Hence, we use the utility function to analyze the agents' satification. Our objective is to place two facilities on [0, L] to maximize the social utility or the minimum utility. For each objective function, we propose deterministic strategy-proof mechanisms. For the objective of maximizing the social utility, we present an optimal deterministic strategy-proof mechanism in the case where agents can only misreport their locations. In the case where agents can only misreport their preferences, we present a 2-approximation deterministic strategy-proof mechanism. Finally, we present a 4-approximation deterministic strategyproof mechanism and a randomized strategy-proof mechanism with an approximation ratio of 2 where agents can misreport both the preference and location information. Moreover, we also give a lower-bound of 1.06. For the objective of maximizing the minimum utility, we give a lower-bound of 1.5 and present a 2-approximation deterministic strategyproof mechanism where agents can misreport both the preference and location..
11. 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.
12. Taiki Todo, Fairness and False-Name-Proofness in Randomized Allocation of a Divisible Good, Dagstuhl Seminar 16232: Fair Division, 2016.06.
13. Taiki Todo, Establishing a Theory for Exchange of Multiple Indivisible Goods with Indifferences, Microsoft Research Japan-Korea Academic Day 2016, 2016.05.
14. Taiki Todo, Establishing a Theory for Exchange of Multiple Indivisible Goods with Indifferences, Microsoft Research Korea-Japan Academic Day 2015, 2015.05.
15. Zhaohong Sun, Taiki Todo, Makoto Yokoo, Exchange of Indivisible Objects with Asymmetry, Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-15), 2015.07.
16. 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.
17. 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.
18. 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.
19. Atsushi Iwasaki, Etsushi Fujita, Taiki Todo, Hidenao Iwane, Hirokazu Anai, Mingyu Guo, Makoto Yokoo, Parametric Mechanism Design via Quantifier Elimination, Fourteenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS-15), 2015.05.
20. 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.
21. Masaaki Oka, Taiki Todo, Yuko Sakurai, Makoto Yokoo, Predicting Own Action: Self-Fulfilling Prophecy Induced by Proper Scoring Rules, The Second AAAI Conference on Human Computation and Crowdsourcing (HCOMP-14), 2014.11.
22. 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 (ECAI 2014), 2014.08, [URL].
23. 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 (AAAI 2014), 2014.07.
24. , [URL].
25. 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 (AAMAS 2014), 2014.05.
26. 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 (AAMAS 2014), 2014.05.
27. Akihisa Sonoda, Etsushi Fujita, Taiki Todo, Makoto Yokoo, Trading Multiple Indivisible Goods with Indifferences: Beyond Sönmez's Result, The 16th International Workshop on Agent-Mediated Electronic Commerce (AMEC) and Trading Agents Design and Analysis (TADA), 2014.05.
28. Taiki Todo, A complexity approach for Pareto efficient exchange with multiple indivisible goods, Warsaw Workshop on Economic and Computational Aspects of Game Theory and Social Choice, 2014.03.
29. Taiki Todo, Strategy-proof exchange with multiple private endowments, The First International Workshop on Market Design Technologies for Sustainable Development, 2013.11.
30. Taiki Todo, Vincent Conitzer, False-name-proof Matching, The Twelfth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2013), 2013.05.
31. 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 (AAMAS 2013), 2013.05.
32. Taiki Todo, False-name-proofness in Online Mechanisms, Duke University Visiting Day, 2013.02.
33. Taiki Todo, False-name-proof Matching, Duke CS-ECON Seminar, 2013.02.
34. Taiki Todo, Takayuki Mouri, Atsushi Iwasaki, Makoto Yokoo, False-name-proofness in Online Mechanisms, The Eleventh International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2012), 2012.06.
35. Taiki Todo, Generalizing Envy-Freeness Toward Group of Agents, The 13th ACM Conference on Electronic Commerce (EC 2012), 2012.06.
36. Takayuki Mouri, Runcong Li, Taiki Todo, Atsushi Iwasaki, Makoto Yokoo, Envy-Freeness for Groups of Agents: Beyond Single-Minded Domain, Joint Workshop on Trading Agent Design and Analysis (TADA) and Agent-Mediated Electronic Commerce (AMEC), 2012.06.
37. Taiki Todo, False-name-proof Mechanism Design without Money, Duke CS-ECON Seminar, 2012.04.
38. 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 (IJCAI 2011), 2011.07.
39. Taiki Todo, Atsushi Iwasaki, Makoto Yokoo, False-name-proof Mechanism Design without Money, The Tenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011), 2011.05.
40. Taiki Todo, Atsushi Iwasaki, Makoto Yokoo, False-name-proofness in Facility Location Problem on the Real Line, The Sixth Workshop on Internet and Network Economics (WINE 2010), 2010.12.
41. Taiki Todo, Takayuki Mouri, Atsushi Iwasaki, Makoto Yokoo, False-name-proofness in Online Mechanisms, The First International Joint Agent Workshop & Symposium (iJAWS 2010), 2010.10.
42. Taiki Todo, False-name-proofness in Facility Location Problem on the Real Line, Hitotsubashi G-COE Workshop on Choice, Games, and Welfare, 2010.10.
43. Taiki Todo, Atsushi Iwasaki, Makoto Yokoo, Characterization of Revenue Monotonicity in Combinatorial Auctions, 2010 IEEE/WIC/ACM Conference on Intelligent Agent Technology (IAT 2010), 2010.09.
44. Atsushi Iwasaki, Vincent Conitzer, Mingyu Guo, Taiki Todo, Yoshifusa Omori, Yuko Sakurai, Makoto Yokoo, Worst-case efficiency ratio in false-name-proof combinatorial auction mechanisms, The Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010), 2010.05.
45. Taiki Todo, Atsushi Iwasaki, Makoto Yokoo, Characterization of Revenue Monotonicity in Combinatorial Auctions, Twelfth International Workshop on Agent-Mediated Electronic Commerce (AMEC 2010), 2010.05.
46. Taiki Todo, Characterization of False-name-proof Social Choice Mechanisms, AAMAS2010 Doctoral Mentoring Program, 2010.05.
47. Taiki Todo, False-name-proofness in Online Mechanisms, COST-ADT Doctoral School on Computational Social Choice, 2010.04.
48. Taiki Todo, Atsushi Iwasaki, Makoto Yokoo, Characterization of Strategy-proof, Revenue Monotone Combinatorial Auction Mechanisms and Connection with False-name-proofness, The Fifth Workshop on Internet and Network Economics (WINE 2009), 2009.12.
49. Taiki Todo, Characterizing false-name-proof allocation rules in combinatorial auctions, Hitotsubashi G-COE Con- ference on Choice, Games, and Welfare: Mechanism Design, 2009.09.
50. Taiki Todo, Atsushi Iwasaki, Makoto Yokoo, Yuko Sakurai, Characterizing false-name-proof allocation rules in combinatorial auctions, The Eighth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2009), 2009.05.