Kyushu University Academic Staff Educational and Research Activities Database
Researcher information (To researchers) Need Help? How to update
Makoto Yokoo Last modified date:2023.06.26



Graduate School
Undergraduate School


E-Mail *Since the e-mail address is not displayed in Internet Explorer, please use another web browser:Google Chrome, safari.
Homepage
https://kyushu-u.pure.elsevier.com/en/persons/makoto-yokoo
 Reseacher Profiling Tool Kyushu University Pure
http://agent.inf.kyushu-u.ac.jp/~yokoo/
Phone
092-802-3585
Fax
092-802-3576
Academic Degree
Research on Distributed Constraint Satisfaction Problem
Country of degree conferring institution (Overseas)
No
Field of Specialization
Multi-agent Systems
Total Priod of education and research career in the foreign country
02years00months
Outline Activities
When there exist multiple agents in a shared environment, there usually exist constraints among possible actions of these agents. A distributed constraint satisfaction problem (distributed CSP) is a problem to find a consistent combination of actions that satisfies these inter-agent constraints. A distributed CSP is a fundamental problem for achieving the coordination among agents, and this problem can formalize various application problems in DAI, such as MultiAgent truth maintenance tasks and distributed resource allocation problems.

I have developed a basic algorithm called asynchronous backtracking that is guaranteed to be complete, i.e., when there exists a consistent solution, the agents can eventually find it, and if there exists no solution since the constraints are too tight, the agents can eventually find out the fact that there exists no solution. Furthermore, this basic algorithm can be extended to a more efficient asynchronous weak-commitment search algorithm by introducing dynamic ordering among agents. The notion of weak-commitment is also effective for solving normal, centralized constraint satisfaction problems.

Furthermore, I'm conducting researches on mechanism design in multi-agent systems (e.g., auctions), iterative improvement algorithms for solving distributed CSPs, algorithms for over-constrained distributed CSPs, Multi-agent Real-time search algorithms, methods for solving CSPs using reconfigurable hardware (field programmable gate arrays), and landscape analysis of CSPs.
Research
Research Interests
  • Research on constrained two-sided matching
    keyword : two-sided matching, strategyproofness, deferred acceptance mechanism
    2015.04.
  • Mechanism Design, Internet Auctions
    keyword : Multi-agent Systems, Economics, Game theory
    1998.08.
  • Distributed Constraint Reasoning
    keyword : Search, Constraint Satisfaction, Multi-agent systems
    1989.01.
Academic Activities
Books
1. 横尾 真, Combinatorial Auctions, 2006.04.
Papers
1. Kwei-guu Liu, Kentaro Yahiro, Makoto Yokoo, Strategyproof Mechanism for Two-Sided Matching with Resource Allocation, Artificial Intelligence, 316, 2023.02.
2. Takamasa Suzuki, Akihisa Tamura, Kentaro Yahiro, Makoto Yokoo, Yuzhe Zhang, Strategyproof Allocation Mechanisms with Endowments and M-convex Distributional Constraints, Artificial Intelligence, 315, 2023.01.
3. Zhaohong Sun, Daisuke Moriwaki, Yoshihiro Takenami, Yoji Tomita, Makoto Yokoo, Daycare Matching in Japan: Transfers and Siblings, Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI-2023), 2023.02.
Awards
  • This award is given to a paper that has published at least 10 years ago and has a significant influence to the research community of autonomous agents and multiagent systems. The award is give to the following papers:
    Makoto Yokoo, Edmund H. Durfee, Toru Ishida, and Kazuhiro Kuwabara,
    ``The Distributed Constraint Satisfaction Problem: Formalization and Algorithms'',
    IEEE Transactions on Knowledge and Data Engineering
    10:673-685, 1998,
    together with,
    Makoto Yokoo and Katsutoshi Hirayama,
    ``Distributed Breakout Algorithm for Solving Distributed Constraint Satisfaction Problems'',
    Second International Conference on Multiagent Systems (ICMAS-96), pp.401-408,
    1996.