Kyushu University Academic Staff Educational and Research Activities Database
List of Papers
Makoto Yokoo Last modified date:2019.06.21

Professor / Intelligence Science / Department of Informatics / Faculty of Information Science and Electrical Engineering


Papers
1. Oskar Skibski, Talal Rahwan, Tomasz P. Michalak, Makoto Yokoo, Attachment centrality: Measure for connectivity in networks, Artificial Intelligence, 10.1016/j.artint.2019.03.002, 274, 151-179, 2019.09.
2. Xiaojuan Liao, Miyuki KoshimuraKazuki NomotoSuguru UedaYuko SakuraiMakoto Yokoo, Improved WPM encoding for coalition structure generation under MC-nets, Constraints, 24, 1, 25-55, 2019.01.
3. 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, Res.63, 515-555, 2018.11.
4. Suguru Ueda, Atsushi Iwasaki, Vincent Conitzer, Naoki Ohta, Yuko Sakurai, Makoto Yokoo, Coalition structure generation in cooperative games with compact representations, Autonomous Agents and Multi-Agent Systems, 10.1007/s10458-018-9386-z, 32, 4, 503-533, 2018.04.
5. Fuhito Kojima, Akihisa Tamura, Makoto Yokoo , Designing matching mechanisms under constraints: An approach from discrete convex analysis, Journal of Economic Theory, 10.1016/j.jet.2018.05.004, 178, 803-833, 2018.05, We consider two-sided matching problems where agents on one side of the market (hospitals) are required to satisfy certain distributional constraints. We show that when the preferences and constraints of the hospitals can be represented by an M♮-concave function, (i) the generalized Deferred Acceptance (DA) mechanism is strategyproof for doctors, (ii) it produces the doctor-optimal stable matching, and (iii) its time complexity is proportional to the square of the number of possible contracts. Furthermore, we provide sufficient conditions under which the generalized DA mechanism satisfies these desirable properties. These conditions are applicable to various existing works and enable new applications as well, thereby providing a recipe for developing desirable mechanisms in practice..
6. Toshihiro Matsui, Hiroshi Matsuo, Marius Silaghi, Katsutoshi Hirayama, Makoto Yokoo, Leximin Asymmetric Multiple Objective Distributed Constraint Optimization Problem, Computational Intelligence, 10.1111/coin.12106, 34, 1, 49-84, 2018.02.
7. Toshihiro Matsui, Marius Silaghi, Tenda Okimoto, Katsutoshi Hirayama, Makoto Yokoo, Hiroshi Matsuo, Leximin Multiple Objective DCOPs on Factor Graphs for Preferences of Agents, Fundamenta Informaticae, 10.3233/FI-2018-1642, 158 , No.1-3, , 63-91, 2018.02.
8. 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.02.
9. Makoto Yokoo, Naoto Hamada, Chia-Ling Hsu, Ryoji Kurata, Takamasa Suzuki, Suguru Ueda, Strategy-proof School Choice Mechanisms with Minimum Quotas and Initial Endowments, Artificial Intelligence Journal, 10.1016/j.artint.2017.04.006, 246, 47-71, 2017.08, We consider a school choice program where minimum quotas are imposed for each school, i.e., a school must be assigned at least a certain number of students to operate. We require that the obtained matching must respect the initial endowments, i.e., each student must be assigned to a school that is at least as good as her initial endowment school. Although minimum quotas are relevant in school choice programs and strategy-proofness is important to many policymakers, few existing mechanisms simultaneously achieve both. One difficulty is that no strategy-proof mechanism exists that is both efficient and fair under the presence of minimum quotas. Furthermore, existing mechanisms require that all students consider all schools acceptable to obtain a feasible matching that respects minimum quotas. This assumption is unrealistic in a school choice program.

We consider the environment where a student considers her initial endowment school acceptable and the initial endowments satisfy all the minimum quotas. We develop two strategy-proof mechanisms. One mechanism, which we call the Top Trading Cycles among Representatives with Supplementary Seats (TTCR-SS), is based on the Top Trading Cycles (TTC) mechanism and is significantly extended to handle the supplementary seats of schools while respecting minimum quotas. TTCR-SS is Pareto efficient. The other mechanism, which we call Priority List-based Deferred Acceptance with Minimum Quotas (PLDA-MQ), is based on the Deferred Acceptance (DA) mechanism. PLDA-MQ is fair, satisfies a concept called Priority List-based (PL-) stability, and obtains the student-optimal matching within all PL-stable matchings. Our simulation results show that our new mechanisms are significantly better than simple extensions of the existing mechanisms..
10. Makoto Yokoo, Masahiro Goto, Fuhito Kojima, Ryoji Kurata, Akihisa Tamura, Designing Matching Mechanisms under General Distributional Constraints, American Economic Journal, 10.1257/mic.20160124, 9, 2, 226-262, 2017.05, To handle diverse types of practical applications, this paper develops a theory of two-sided matching under distributional constraints. The only requirement we impose on the constraints is heredity, a condition that if a matching is feasible, then any matching that assigns weakly fewer students at each school is also feasible. This condition is more general than those studied in existing research such as regional maximum quotas and diversity constraints in school choice. When distributional constraints are imposed, there does not necessarily exist a stable matching, i.e., a matching that satisfies fairness and nonwastefulness. We propose a new mechanism called the Adaptive Deferred Acceptance mechanism (ADA), which satisfies strategyproofness for students, nonwastefulness, and a weaker fairness property. We also offer a technique to apply the ADA even if the constraints do not satisfy the heredity condition (e.g., minimum quotas). We demonstrate the applicability of our analysis in actual application domains..
11. Makoto Yokoo, Ryoji Kurata, Naoto Hamada, Atsushi Iwasaki, Controlled School Choice with Soft Bounds and Overlapping Types, Journal of Artificial Intelligence Research, 10.1613/jair.5297, 58, 153-184, 2017.01.
12. Makoto Yokoo, Oskar Skibski, An Algorithm for the Myerson Value in Probabilistic Graphs with an Application to Weighted Voting, IEEE Intelligent Systems, 10.1109/MIS.2017.3, 32, 1, 32-39, 2017.01.
13. Makoto Yokoo, Masahiro Goto, Atsushi Iwasaki, Yujiro Kawasaki, Ryoji Kurata, Yosuke Yasuda, Strategyproof matching with regional minimum and maximum quotas, Artificial Intelligence, 10.1016/1j.artint.2016.02.002, 235, 40-57, 2016.06.
14. Makoto Yokoo, Atsushi Iwasaki, Suguru Ueda, Naoyuki Hashimoto, Finding core for coalition structureutilizing dual solution, Artificial Intelligence, 222, 49-66, 2015.05.
15. Dong Hao, Xiaojuan Liao, Avishek Adhikari, 櫻井 幸一, 横尾 真, A repeated game approach for analyzing the collusion on selective forwarding in multihop wireless networks, Computer Communications, 35, 17, 2125-2137, 2012.10.
16. Matthew E. Taylor, Manish Jain, Prateek Tandon, Makoto Yokoo, Milind Tambe, Distributed on-Line Multi-Agent Optimization under Uncertainty: Balancing Exploration and Exploitation, Advances in Complex Systems, 14, 3, 471-528, 2011.03.
17. Yuko Sakurai, Atsushi Iwasaki, and Makoto Yokoo, Keyword Auction Protocol for Dynamically Adjusting the Number of Advertisements, Web Intelligence and Agent Systems (WIAS),, 8, 3, 331-341, 2010.04.
18. Emma Bowring, Milind Tambe, Makoto Yokoo, Balancing local resources and global goals in multiply-constrained DCOP, Journal of Multiagent and Grid Systems (MAGS), 6, 4, 353-393, 2010.04.
19. Makoto Tasaki, Yuichi Yabu, Yuki Iwanari, Makoto Yokoo, Janusz Marecki, Pradeep Varakantham, Milind Tambe, Introducing Communication in Dis-POMDPs with Locality of Interaction, Web Intelligence and Agent Systems (WIAS), 8, 3, 303-311, 2010.03.
20. Kiam Tian Seow, Chuan Ma, and Makoto Yokoo, Coordination Planning:Applying Control Synthesis Methods for a Class of Distributed Agents, IEEE Transactions on Control Systems Technology, Volume 17, Issue 2, pp.405--415, 2009.03.
21. Marius C. Silaghi, Makoto Yokoo, ADOPT-ing: unifying asynchronous distributed optimization
with asynchronous backtracking, Journal of Autonomous Agents and Multi-Agent Systems, 2008.11.
22. Takayuki Ito, Makoto Yokoo, Shigeo Matsubara, and Atsushi Iwasaki, Implementing a strategyproof greedy-allocation combinatorial auction and extending to ascending auction, Systems and Computers in Japan, vol.38, No.9, pp.44--51, 2007.08.
23. Hiromitsu Hattori, Makoto Yokoo, Yuko Sakurai, and Toramatsu Shintani, Determining bidding strategies in sequential auctions: Quasi-linear utility and budget constraints, Systems and Computers in Japan, Vol.38, No.8, pp.72--83, 2007.07.
24. Kenji Terada and Makoto Yokoo, False-name-proof multi-unit auction protocol utilizing greedy allocation based on approximate evaluation values, Systems and Computers in Japan, vol.37, No.13, pp.89--98, 2006.11.
25. Takayuki Suyama, Makoto Yokoo, Strategy/False-name Proof Protocols for Combinatorial Multi-Attribute
Procurement Auction, Autonomous Agents and Multi-Agent Systems, 10.1007/s10458-005-0983-2, 11, 1, 7-21, Vol.11, Issue 1, pp.7-21, 2005.07.
26. Atsushi Iwasaki, Makoto Yokoo, Kenji Terada, A Roubust Open Ascending-price Multi-unit Auction Protocol against
False-name Bids, Decision Support Systems, Vol.39, pp.23-39, 2005.03.
27. Makoto Yokoo, Koutarou Suzuki, Generalized Vickrey Auction and Suppression of Active Adversary Using
Incentive-Compatible Implementation, Transactions of the Institute of Electronics, Information and Communication Engineers(IEICE), 10.1093/ietfec/E88-A.1.255, E88A, 1, 255-261, Vol.E88-A, No.1, pp.255-261, 2005.01.
28. Pragnesh Jay Modi, Wei-Min Shen, Milind Tambe, Makoto Yokoo, Asynchronous Distributed Constraint Optimization with Quality
Guarantees, Artificial Intelligence Journal, Vol.161, No.1-2, pp.149-180, 2005.01.
29. Makoto Yokoo, Koutarou Suzuki, Katsutoshi Hirayama, Secure Distributed Constraint Satisfaction: Reaching Agreement
without Revealing Private Information, Artificial Intelligence Journal, 10.1016/j.artint.2004.10.007, 161, 1-2, 229-245, Vol.161, pp.229-245, 2005.01.
30. Katsutoshi Hirayama, Makoto Yokoo, The Distributed Breakout Algorithms, Artificial Intelligence Journal}, 10.1016/j.artint.2004.08.004, 161, 1-2, 89-115, Vol.161, No.1-2, pp.89-115, 2005.01.
31. Katsutoshi Hirayama, Makoto Yokoo, Katia Sycara, An Easy-Hard-Easy Cost Profile in Distributed Constraint Satisfaction, IPSJ Journal, Vol. 45, No.9, pp.2217-2225, 2004.09.
32. Makoto Yokoo, Yuko Sakurai, Shigeo Matsubara, The Effect of False-name Bids in Combinatorial Auctions: New Fraud in Internet Auctions, Games and Economic Behavior, Vol. 46, pp. 174-188, 2004.01.
33. "Bundle Design in Robust Combinatorial Auction Protocol against False-name Bids'', Makoto Yokoo, Yuko Sakurai, and Shigeo Matsubara, Computer Software (Journal of Japanese Society for Software Science and Technology).
34. William E. Walsh, Makoto Yokoo, Katsutoshi Hirayama, Michael P. Wellman, On Market-Inspired Approaches to Propositional Satisfiability, Artificial Intelligence Journal, Vol. 144, pp. 125-156, 2003.01.
35. "An Average-case Budget-Non-Negative Double Auction Protocol'', Yuko Sakurai and Makoto Yokoo, Journal of Japanese Society for Artificial Intelligence.
36. "Designing an Auction Protocol under Asymmetric Information on Nature's Selection'', Takayuki Ito, Makoto Yokoo, , and Shigeo Matsubara, Computer Software (Journal of Japanese Society for Software Science and Technology).
37. Shigeo Matsubara, Makoto Yokoo, Defection-Free Exchange Mechanisms based on an Entry Fee Imposition, Artificial Intelligence Journal, Vol. 142, pp. 265-286, 2002.01.
38. "A Dynamic Programming Model for Determining Bidding Strategies in Sequential Auctions: Quasi-linear Utility and Budget Constraints'', Hiromitsu Hattori, Makoto Yokoo, Yuko Sakurai, and Toramatsu Shintani, Transactions of the Institute of Electronics, Information and Communication Engineers.
39. "Robust Combinatorial Auction Protocol against False-name Bids'', Makoto Yokoo, Yuko Sakurai, and Shigeo Matsubara, Transactions of Information Society of Japan.
40. "Robust Multi-unit Auction Protocol against False-name Bids'', Makoto Yokoo, Yuko Sakurai, and Shigeo Matsubara, Journal of Japanese Society for Artificial Intelligence.
41. Makoto Yokoo, Yuko Sakurai, Shigeo Matsubara, Robust Combinatorial Auction Protocol against False-name Bids, Artificial Intelligence Journal, Vol. 130, No. 2, pp. 167-181, 2001.01.
42. "Robust Double Auction Protocol against False-name Bids'', Makoto Yokoo, Yuko Sakurai, and Shigeo Matsubara, Transactions of the Institute of Electronics, Information and Communication Engineers.
43. "An Efficient Approximate Algorithm for Winner Determination in Combinatorial Auctions'', Yuko Sakurai, Makoto Yokoo, and Kouji Kamei, Journal of Japanese Society for Artificial Intelligence.
44. "Solving Satisfiability Problems using Reconfigurable Computing'', Takayuki Suyama, Makoto Yokoo, Hiroshi Sawada, and Akira Nagoya, Transactions of the Institute of Electronics, Information and Communication Engineers.
45. Takayuki Suyama, Makoto Yokoo, Hiroshi Sawada, Akira Nagoya, Solving Satisfiability Problems using Reconfigurable Computing, IEEE Transactions on VLSI, Vol. 9, No. 1, pp. 109-116, 2001.01.
46. "The Effect of False-name Declarations in Mechanism Design: Towards Collective Decision Making on the Internet'', Makoto Yokoo, Yuko Sakurai, and Shigeo Matsubara, Computer Software (Journal of Japanese Society for Software Science and Technology).
47. "Defection-Free Exchange Mecahnisms for Information Good'', Shigeo Matsubara and Makoto Yokoo, Journal of Japanese Society for Artificial Intelligence.
48. "Frequency Assignment for Cellular Mobile Systems Using Constraint Satisfaction Techniques'', Makoto Yokoo and Katsutoshi Hirayama, Transactions of Information Society of Japan.
49. Makoto Yokoo, Katsutoshi Hirayama, Algorithms for Distributed Constraint Satisfaction: A Review, Autonomous Agents and Multi-Agent Systems, Vol. 3, No. 2, pp. 189-212, 2000.01.
50. "Distributed Constraint Satisfaction Algorithms for Complex Local Problems'', Mkoto Yokoo and Katsutoshi Hirayama, Journal of Japanese Society for Artificial Intelligence.
51. "The Effect of Nogood Learning in Distributed Constraint Satisfaction'', Katsutoshi Hirayama and Makoto Yokoo, Journal of Japanese Society for Artificial Intelligence.
52. "A Limitation of the Generalized Vickrey Auction in Electronic Commerce: Robustness against False-name Bids'', Yuko Sakurai, Makoto Yokoo, and Shigeo Matsubara, Computer Software (Journal of Japanese Society for Software Science and Technology).
53. Fumio Hattori, Takeshi Ohguro, Makoto Yokoo, Shigeo Matsubara, Sen Yoshida, Socialware: Multiagent Systems for Supporting Network Communities, Communications of the ACM, Vol. 42, No. 3, pp. 55-61, 1999.03.
54. "Multi-State Commitment Search'', Yasuhiko Kitamura, Makoto Yokoo, Tomohisa Miyaji, and Shoji Tatsumi, Journal of Japanese Society for Artificial Intelligence.
55. "Distributed Partial Constraint Satisfaction Problem'', Katsutoshi Hirayama and Makoto Yokoo, Journal of Japanese Society for Artificial Intelligence.
56. "Analyzing Landscapes of CPSs'', Makoto Yokoo, Computer Software (Journal of Japanese Society for Software Science and Technology).
57. Makoto Yokoo, Edmund H. Durfee, Toru Ishida, Kazuhiro Kuwabara, The Distributed Constraint Satisfaction Problem: Formalization and Algorithms, IEEE Transactions on Knowledge and Data Engineering, Vol. 10, No. 5, pp. 673-685, 1998.01.
58. "Distributed Breakout Algorithm for Solving Distributed Constraint Satisfaction Problems'', Makoto Yokoo and Katsutoshi Hirayama, Transactions of Information Society of Japan.