| 1. |
Hiromichi Goko, Ayumi Igarashi, Yasushi Kawase, Kazuhisa Makino, Hanna Sumita, Akihisa Tamura, Yu Yokoi, Makoto Yokoo,, A fair and truthful mechanism with limited subsidy, Games and Economic Behavior, https://doi.org/10.1016/j.geb.2023.12.006., 144, 40-70, 2024.03. |
| 2. |
Zhaohong Sun and
Naoyuki Yamada and
Yoshihiro Takenami and
Daisuke Moriwaki and
Makoto Yokoo, Stable Matchings in Practice: A Constraint Programming Approach, Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI), https://doi.org/10.1609/aaai.v38i20.30244, 2024.02. |
| 3. |
Yasushi Kawase and
Kazuhisa Makino and
Hanna Sumita and
Akihisa Tamura and
Makoto Yokoo, Towards Optimal Subsidy Bounds for Envy-Freeable Allocations, Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI), https://doi.org/10.1609/aaai.v38i9.28842, 2024.02. |
| 4. |
Garima Shakya and Makoto Yokoo, Balancing Fairness and Efficiency in 3D Repeated Matching in Ridesharing, ECAI 2023 - 26th European Conference on Artificial Intelligence, https://doi.org/10.3233/FAIA230507, 2023.10. |
| 5. |
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. |
| 6. |
Kwei-guu Liu, Kentaro Yahiro, Makoto Yokoo, Strategyproof Mechanism for Two-Sided Matching with Resource Allocation, Artificial Intelligence, 316, 2023.02. |
| 7. |
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. |
| 8. |
Oskar Skibski, Takamasa Suzuki, Tomasz Grabowski, Yuko Sakurai, Tomasz P. Michalak, Makoto Yokoo, Measuring power in coalitional games with friends, enemies and allies, Artificial Intelligence, 313, 2022.10. |
| 9. |
Sung-Ho Cho, Taiki Todo, Makoto Yokoo, Two-Sided Matching over Social Networks, The 31st International Joint Conference on Artificial Intelligence and the 25th European Conference on Artificial Intelligence (IJCAI-ECAI 2022), 186-193, 2022.07. |
| 10. |
Khoi D. Hoang, Ferdinando Fioretto, Ping Hou, William Yeoh, Makoto Yokoo, Roie Zivan, Proactive Dynamic Distributed Constraint Optimization Problems., Journal of Artificial Intelligence Research, 10.1613/jair.1.13499, 74, 179-225, 2022.05. |
| 11. |
Bo You, Ludwig Dierks, Taiki Todo, Minming Li, Makoto Yokoo, Strategy-Proof House Allocation with Existing Tenants over Social Networks., 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2022), 1446-1454, 2022.05. |
| 12. |
Miyuki Koshimura, Emi Watanabe, Yuko Sakurai, Makoto Yokoo, Concise integer linear programming formulation for clique partitioning problems., Constraints, 10.1007/s10601-022-09326-z, 27, 99-115, 2022.04. |
| 13. |
Haris Aziz, Péter Biró, Makoto Yokoo, Matching Market Design with Constraints, Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI 2022), https://doi.org/10.1609/aaai.v36i11.21495, 36, 11, 12308-12316, 2022.02. |
| 14. |
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, 36, 12, 2022.01. |
| 15. |
Taiki Todo, Ryoji Wada, Kentaro Yahiro, Makoto Yokoo, Lazy Gale-Shapley for Many-to-One Matching with Partial Information., Algorithmic Decision Theory - 7th International Conference (ADT 2021), 390-405, 2021.11. |
| 16. |
Zhaohong Sun, Taiki Todo, Makoto Yokoo, New Algorithms for Japanese Residency Matching, Thirtieth International Joint Conference on Artificial Intelligence (IJCAI 2021), 412-418, 2021.08. |
| 17. |
Takehiro Kawasaki, Ryoji Wada, Taiki Todo, Makoto Yokoo, Mechanism Design for Housing Markets over Social Networks, 20th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS-2021), 692-700, 2021.05. |
| 18. |
Taiki Todo, Nodoka Okada, Makoto Yokoo, False-Name-Proof Facility Location on Discrete Structures, 24th European Conference on Artificial Intelligence (ECAI-2020), 10.3233/FAIA200097, 227-234, 2020.08. |
| 19. |
Taiki Todo, Makoto Yokoo, Split Manipulations in Cost Sharing of Minimum Cost Spanning Tree, 24th European Conference on Artificial Intelligence (ECAI-2020), 10.3233/FAIA200096, 219-226, 2020.08. |
| 20. |
Khoi Hoang, William Yeoh, Makoto Yokoo, Zinovi Rabinovich, New Algorithms for Continuous Distributed Constraint Optimization Problems, 19th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS-2020), 502-510, 2020.05. |
| 21. |
Kentaro Yahiro, Makoto Yokoo, Game Theoretic Analysis for Two-Sided Matching with Resource Allocation, 19th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS-2020), 1548-1556, 2020.05. |
| 22. |
Oskar Skibski, Takamasa Suzuki, Tomasz Grabowski, Tomasz Michalak, Makoto Yokoo, Signed Graph Games: Coalitional Games with Friends, Enemies and Allies, 19th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS-2020), 1287-1295, 2020.05. |
| 23. |
Atsushi Iwasaki, Tadashi Sekiguchi, Shun Yamamoto, Makoto Yokoo, Repeated Multimarket Contact with Private Monitoring: A Belief-Free Approach, Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI-2020), 10.1609/aaai.v34i02.5576, 34, 2, 2038-2045, 2020.04. |
| 24. |
Kentaro Yahiro, Yuzhe Zhang, Nathanael Barrot, Makoto Yokoo , Strategyproof and fair matching mechanism for ratio constraints, Autonomous Agents and Multi-Agent Systems, 10.1007/s10458-020-09448-9, 23, 2020.02. |
| 25. |
Takehiro Kawasaki, Seiji Takanashi, Nathanael Barrot, Taiki Todo, Makoto Yokoo, Strategy-Proof and Non-Wasteful Multi-Unit Auction via Social Network, Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI-2020), 10.1609/aaai.v34i02.5579, 2062-2069, 2020.02, Auctions via a 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 a multi-unit unit-demand auction. In this paper, we first propose a mechanism that satisfies all of the above properties. We then make a comprehensive comparison with two naive mechanisms, showing that the proposed mechanism dominates them in social surplus, seller's revenue, and incentive for truth-telling by buyers. 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.. |
| 26. |
Atsushi Iwasaki, Tadashi Sekiguchi, Shun Yamamoto, Makoto Yokoo, Repeated Multimarket Contact with Private Monitoring: A Belief-Free Approach, Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI-2020), 10.1609/aaai.v34i02.5576, 2038-2045, 2020.02. |
| 27. |
Nodoka Okada, Taiki Todo, Makoto Yokoo, SAT-Based Automated Mechanism Design for False-Name-Proof Facility Location, 22nd International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2019, 10.1007/978-3-030-33792-6_20, 321-337, 2019.10, In the literature of mechanism design, market mechanisms have been developed by professionals based on their experience. The concept of automated mechanism design (AMD), initiated by Sandholm (2002), is a ground-breaking computer-aided framework to develop market mechanisms. In this paper, we apply a very recent AMD approach based on Boolean Satisfiability (SAT) to the mechanism design of false-name-proof facility location. We first provide a general theoretical characteristic of false-name-proof mechanisms, which enables a quite compact representation of target mechanisms. Our approach successfully reproduces several known results in the literature on false-name-proof facility locations over discrete structures. Furthermore, some unknown mechanisms are discovered for locating a public good on a 2-by-2 grid, and an impossibility result is revealed for locating a public bad, with an additional mild assumption, on a 2-by-3 grid. Finally, we demonstrate the extendability of our approach, by providing a new false-name-proof mechanism for a slightly modified problem of locating a public good.. |
| 28. |
Emi Watanabe, Miyuki Koshimura, Yuko Sakurai, Makoto Yokoo, Solving Coalition Structure Generation Problems over Weighted Graph, 22nd International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2019, 10.1007/978-3-030-33792-6_21, 338-353, 2019.10, Coalition Structure Generation (CSG), which is a leading research issue in the domain of coalitional games, divides agents into exhaustive and disjoint coalitions to optimize social welfare. This paper studies CSG problems over weighted undirected graphs in which the weight on an edge between any two connecting agents represents how well they work together in a coalition. The weight can have either a positive or a negative value. We examine two types of problems. One is a CSG without any restrictions on the number of coalitions, and another is a CSG with k coalitions where k is determined in advance. We present two methods to solve these problems: ILP formulation and MaxSAT encoding.. |
| 29. |
Applying Criterion of Leveling of Costs to Dynamic Programming for Shortest Path Finding Problems. |
| 30. |
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. |
| 31. |
Bin Li, Dong Hao, Dengji Zhao, Makoto Yokoo, Diffusion and auction on graphs, 28th International Joint Conference on Artificial Intelligence, IJCAI 2019, 435-441, 2019.08, Auction is the common paradigm for resource allocation which is a fundamental problem in human society. Existing research indicates that the two primary objectives, the seller's revenue and the allocation efficiency, are generally conflicting in auction design. For the first time, we expand the domain of the classic auction to a social graph and formally identify a new class of auction mechanisms on graphs. All mechanisms in this class are incentive-compatible and also promote all buyers to diffuse the auction information to others, whereby both the seller's revenue and the allocation efficiency are significantly improved comparing with the Vickrey auction. It is found that the recently proposed information diffusion mechanism is an extreme case with the lowest revenue in this new class. Our work could potentially inspire a new perspective for the efficient and optimal auction design and could be applied into the prevalent online social and economic networks.. |
| 32. |
Ayumi Igarashi, Kazunori Ota, Yuko Sakurai, Makoto Yokoo, Robustness against agent failure in hedonic games, Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAI 2019, 10.24963/ijcai.2019/52, 364-370, 2019.08, We study how stability can be maintained even after any set of at most k players leave their groups, in the context of hedonic games. While stability properties ensure an outcome to be robust against players' deviations, it has not been considered how an unexpected change caused by a sudden deletion of players affects stable outcomes. In this paper, we propose a novel criterion that reshapes stability form robustness aspect. We observe that some stability properties can be no longer preserved even when a single agent is removed. However, we obtain positive results by focusing on symmetric friend-oriented hedonic games. We prove that we can efficiently decide the existence of robust outcomes with respect to Nash stability under deletion of any number of players or contractual individual stability under deletion of a single player. We also prove that symmetric additively separable games always admit an individual stable outcome that is robust with respect to individual rationality.. |
| 33. |
Nathanaël Barrot, Makoto Yokoo, Stable and envy-free partitions in hedonic games, 28th International Joint Conference on Artificial Intelligence, IJCAI 2019, 10.24963/ijcai.2019/10, 67-73, 2019.08, In this paper, we study coalition formation in hedonic games through the fairness criterion of envy-freeness. Since the grand coalition is always envy-free, we focus on the conjunction of envy-freeness with stability notions. We first show that, in symmetric and additively separable hedonic games, an individually stable and justified envy-free partition may not exist and deciding its existence is NP-complete. Then, we prove that the top responsiveness property guarantees the existence of a Pareto optimal, individually stable, and envy-free partition, but it is not sufficient for the conjunction of core stability and envy-freeness. Finally, under bottom responsiveness, we show that deciding the existence of an individually stable and envy-free partition is NP-complete, but a Pareto optimal and justified envy-free partition always exists.. |
| 34. |
Anisse Ismaili, Naoto Hamada, Yuzhe Zhang, Takamasa Suzuki, Makoto Yokoo, Weighted Matching Markets with Budget Constraints, Journal of Artificial Intelligence Research, 65, 393-421, 2019.07. |
| 35. |
Taiki Todo, Atsushi Iwasaki, Makoto Yokoo, Competitive Auctions and Envy-Freeness for Group of Agents, 25th International Computing and Combinatorics Conference (COCOON-2019), 10.1007/978-3-030-26176-4_45, 541-553, 2019.07, In mechanism design, fairness is one of the central criteria for analyzing mechanisms. Recently, a new fairness concept called envy-freeness of a group toward a group (GtG-EFness) has received attention, which requires that no group of agents envies any other group. In this paper, we consider GtG-EFness in more general combinatorial auctions, including several subclasses of the multi-unit auction domain (unit-demand, diminishing marginal values, and all-or-nothing), and reveal the tight bound of the competitive ratios. In particular, we prove that the tight bound of the competitive ratio is 1/k (where k is the number of items) for the general combinatorial auction domain. We also clarify the relationship with Walrasian equilibria and conclude that no group envies any other group in any Walrasian equilibrium.. |
| 36. |
Ilan Nehama, Taiki Todo, Makoto Yokoo, Manipulation-resistant facility location mechanisms for ZV-line graphs, 18th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2019, 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.. |
| 37. |
Atena M. Tabakhi, William Yeoh, Makoto Yokoo, Parameterized heuristics for incomplete weighted CSPs with elicitation costs, 18th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2019, 476-484, 2019.05, Weighted Constraint Satisfaction Problems (WCSPs) are an elegant paradigm for modeling combinatorial optimization problems. A key assumption in this model is that all constraints are specified or known a priori, which does not hold in some applications where constraints may encode preferences of human users. Incomplete WCSPs (IWCSPs) extend WCSPs by allowing some constraints to be partially specified, and they can be elicited from human users during the execution of IWCSP algorithms. Unfortunately, existing approaches assume that the elicitation of preferences does not incur any additional cost. This assumption is unrealistic as human users are likely bothered by repeated elicitations and will refuse to provide an unbounded number of preferences. Therefore, we propose the IWCSP with Elicitation Cost (IWCSP+EC) model, which extends IWCSPs to include elicitation costs, as well as three parameterized heuristics that allow users to trade off solution quality for fewer elicited preferences and faster computation times. They provide theoretical quality guarantees for problems where elicitations are free. Our model and heuristics thus extend the state of the art in constraint reasoning to better model and solve agent-based applications with user preferences.. |
| 38. |
Julien Savaux, Julien Vion, Sylvain Piechowiak, Ren{'e, Mandiau, Toshihiro Matsui, Katsutoshi Hirayama, Makoto Yokoo, Shakre Elmane, Marius Silaghi, Privacy stochastic games in distributed constraint reasoning, Annals of Mathematics and Artificial Intelligence, 10.1007/s10472-019-09628-8, 88, 7, 691-715, 2019.04. |
| 39. |
Coalition Structure Generation for Partition Function Games Utilizing Partition Decision Trees
This paper studies coalition structure generation (CSG) problems for partition function games (PFGs) which are coalitional games with externalities. In PFGs, each value of a coalition depends on how the other agents are partitioned. In this paper, we consider CSG problems when there exist both positive and negative values for coalitions. We apply a compact representation method called Partition Decision Trees
(PDTs) to represent PFGs and propose two different methods to solve CSG problems: a depth-first branch-and-bound algorithm and MaxSAT encoding.. |
| 40. |
Xiaojuan Liao, Miyuki Koshimura, Kazuki Nomoto, Suguru Ueda, Yuko Sakurai, Makoto Yokoo, Improved WPM encoding for coalition structure generation under MC-nets, Constraints, 10.1007/s10601-018-9295-4, 24, 1, 25-55, 2019.01, The Coalition Structure Generation (CSG) problem plays an important role in the domain of coalition games. Its goal is to create coalitions of agents so that the global welfare is maximized. To date, Weighted Partial MaxSAT (WPM) encoding has shown high efficiency in solving the CSG problem, which encodes a set of constraints into Boolean propositional logic and employs an off-the-shelf WPM solver to find out the optimal solution. However, in existing WPM encodings, a number of redundant encodings are asserted. This results in additional calculations and correspondingly incurs performance penalty. Against this background, this paper presents an Improved Rule Relation-based WPM (I-RWPM) encoding for the CSG problem, which is expressed by a set of weighted rules in a concise representation scheme called Marginal Contribution net (MC-net). In order to effectively reduce the constraints imposed on encodings, we first identify a subset of rules in an MC-net, referred as a set of freelance rules. We prove that solving the problem made up of all freelance rules can be achieved with a straightforward means without any extra encodings. Thus the set of rules requiring to be encoded is downsized. Next, we improve the encoding of transitive relations among rules. To be specific, compared with the existing rule relation-based encoding that generates transitive relations universally among all rules, I-RWPM only considers the transitivity among rules with particular relationship. In this way, the number of constraints to be encoded can be further decreased. Experiments suggest that I-RWPM significantly outperforms other WPM encodings for solving the same set of problem instances.. |
| 41. |
Julien Savaux, Julien Vion, Sylvain Piechowiak, René Mandiau, Toshihiro Matsui, Katsutoshi Hirayama, Makoto Yokoo, Shakre Elmane, Marius Silaghi, Privacy stochastic games in distributed constraint reasoning, Annals of Mathematics and Artificial Intelligence, 10.1007/s10472-019-09628-8, 2019.01, In this work, we approach the issue of privacy in distributed constraint reasoning by studying how agents compromise solution quality for preserving privacy, using utility and game theory. We propose a utilitarian definition of privacy in the context of distributed constraint reasoning, detail its different implications, and present a model and solvers, as well as their properties. We then show how important steps in a distributed constraint optimization with privacy requirements can be modeled as a planning problem, and more specifically as a stochastic game. We present experiments validating the interest of our approach, according to several criteria.. |
| 42. |
Nathanael Barrot, Kazunori Ota, Yuko Sakurai, Makoto Yokoo, Unknown Agents in Friends Oriented Hedonic Games: Stability and Complexity
Stability and Complexity, Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-2019), 1756-1763, 2019.01. |
| 43. |
Xiaojuan Liao, Miyuki Koshimura, Kazuki Nomoto, Suguru Ueda, Yuko Sakurai, Makoto Yokoo, Improved WPM encoding for coalition structure generation under MC-nets, Constraints, 10.1007/s10601-018-9295-4, 24, 1, 25-55, 2019.01. |
| 44. |
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. |
| 45. |
Kota Shigedomi, Tadashi Sekiguchi, Atsushi Iwasaki, Makoto Yokoo, Repeated triangular trade
Sustaining circular cooperation with observation errors, 21st International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2018, 10.1007/978-3-030-03098-8_15, 242-257, 2018.10, We introduce a new fundamental problem called triangular trade, which is a natural extension of the well-studied prisoner’s dilemma for three (or more) players where a player cannot directly punish a seemingly defecting player. More specifically, this problem deals with a situation where the power/influence of players is one-way, players would be better off if they maintain circular cooperation, but each player has an incentive to defect. We analyze whether players can sustain such circular cooperation when they repeatedly play this game and each player observes the actions of another player with some observation errors (imperfect private monitoring). We confirm that no simple strategy can constitute an equilibrium within any reasonable parameter settings when there are only two actions: “Cooperate” and “Defect.” Thus, we introduce two additional actions: “Whistle” and “Punish,” which can be considered as a slight modification of “Cooperate.” Then, players can achieve sustainable cooperation using a simple strategy called Remote Punishment strategy (RP), which constitutes an equilibrium for a wide range of parameters. Furthermore, we show the payoff obtained by a variant of RP is optimal within a very general class of strategies that covers virtually all meaningful strategies.. |
| 46. |
Anisse Ismaili, Tomoaki Yamaguchi, Makoto Yokoo, Student-project-resource allocation
Complexity of the symmetric case, 21st International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2018, 10.1007/978-3-030-03098-8_14, 226-241, 2018.10, In this paper, we consider a student-project-resource allocation problem, in which students and indivisible resources are allocated to every project. The allocated resources determine endogenously the student capacity of a project. Traditionally, this problem is divided in two: (I) resources are allocated to projects based on expected demands (resource allocation problem), and (II) students are matched with projects based on the capacity determined in the previous problem (many-to-one matching problem). Although both problems are well-understood, unless the expectations used in the first problem are correct, we obtain a suboptimal outcome. Thus, it is desirable to solve this problem as a whole, without dividing it. We start by introducing a compact representation that takes advantage of the symmetry of preferences. Then, we show that computing a nonwasteful matching is FPNP -complete. Besides, a fair matching can be found in polynomial-time. Finally, deciding whether a stable (i.e. nonwasteful and fair) matching exists is NPNP -complete.. |
| 47. |
Takamasa Suzuki, Akihisa Tamura, Makoto Yokoo, Efficient allocation mechanism with endowments and distributional constraints, 17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018, 50-67, 2018.07, We consider an allocation problem of multiple types objects to agents, where each type of an object has multiple copies (e.g., mult iple seats of a school), each agent is endowed with an object, and some distributional constraints are imposed on the allocation (e.g., minimum/maximum quotas). We develop a mechanism that is based on the Top Trading Cycles mechanism, which Is strategy-proof, feasible (always satisfies distributional constraints). Pareto efficient, and individually rational, assuming the distributional constraints are represented as an M-convex set. The class of distributional cons traints we consider contains many situations raised from realistic matching problems, including individual minimum/maximum quot as, regional maximum quotas, type-specific quotas, and distance constraints. To the best of our knowledge, we are the first to develop a mechanism with these desirable properties.. |
| 48. |
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, 336-344, 2018.07, 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.. |
| 49. |
Yuzhe Zhang, Kentaro Yahiro, Nathanaël Barrot, Makoto Yokoo, Strategyproof and fair matching mechanism for union of symmetric m-convex constraints, 27th International Joint Conference on Artificial Intelligence, IJCAI 2018, 590-596, 2018.07, In this paper, we identify a new class of distributional constraints defined as a union of symmetric M-convex sets, which can represent a variety of real-life constraints in two-sided matching settings. Since M-convexity is not closed under union, a union of symmetric M-convex sets does not belong to this well-behaved class of constraints in general. Thus, developing a fair and strategyproof mechanism that can handle this class is challenging. We present a novel mechanism called Quota Reduction Deferred Acceptance (QRDA), which repeatedly applies the standard DA mechanism by sequentially reducing artificially introduced maximum quotas. We show that QRDA is fair and strategyproof when handling a union of symmetric M-convex sets. Furthermore, in comparison to a baseline mechanism called Artificial Cap Deferred Acceptance (ACDA), QRDA always obtains a weakly better matching for students and, experimentally, performs better in terms of nonwastefulness.. |
| 50. |
Kentaro Yahiro, Yuzhe Zhang, Nathanael Barrot, Makoto Yokoo, Strategyproof and fair matching mechanism for ratio constraints., 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2018), 59-67, 2018.07. |
| 51. |
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, 176, 803-833, 2018.07, 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.. |
| 52. |
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.. |
| 53. |
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. |
| 54. |
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. |
| 55. |
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. |
| 56. |
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. |
| 57. |
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, 1039-1046, 2018.02, 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.. |
| 58. |
Chi Kit Ken Fong, Minming Li, Pinyan Lu, Taiki Todo, Makoto Yokoo, Facility Location Games with Fractional Preferences, Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-2018), 1039-1046, 2018.02. |
| 59. |
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, The Distributed Constraint Optimization Problem (DCOP) lies at the foundations of multiagent cooperation. With DCOPs, the optimization in distributed resource allocation problems is formalized using constraint optimization problems. The solvers for the problem are designed based on decentralized cooperative algorithms that are performed by multiple agents. In a conventional DCOP, a single objective is considered. The Multiple Objective Distributed Constraint Optimization Problem (MODCOP) is an extension of the DCOP framework, where agents cooperatively have to optimize simultaneously multiple objective functions. In the conventional MODCOPs, a few objectives are globally defined and agents cooperate to find the Pareto optimal solution. However, such models do not capture the interests of each agent. On the other hand, in several practical problems, the share of each agent is important. Such shares are modeled as preference values of agents. This class of problems can be defined using the MODCOP on the preferences of agents. In particular, we define optimization problems based on leximin ordering and Asymmetric DCOPs (Leximin AMODCOPs). The leximin defines an ordering among vectors of objective values. In addition, Asymmetric DCOPs capture the preferences of agents. Because the optimization based on the leximin ordering improves the equality among the satisfied preferences of the agents, this class of problems is important. We propose several solution methods for Leximin AMODCOPs generalizing traditional operators into the operators on sorted objective vectors and leximin. The solution methods applied to the Leximin AMODCOPs are based on pseudo trees. Also, the investigated search methods employ the concept of boundaries of the sorted vectors.. |
| 60. |
Toshihiro Matsui, Marius Silaghi, Katsutoshi Hirayama, Makoto Yokoo, Hiroshi Matsuo, Study of route optimization considering bottlenecks and fairness among partial paths, 10th International Conference on Agents and Artificial Intelligence, ICAART 2018
, 37-47, 2018.01, Route optimization is an important problem for single agents and multi-agent systems. In route optimization tasks, the considered challenges generally belong to the family of shortest path problems. Such problems are solved using optimization algorithms, such as the A∗algorithm, which is based on tree search and dynamic programming. In several practical cases, cost values should be as evenly minimized for individual parts of paths as possible. These situations are also considered as multi-objective problems for partial paths. Since dynamic programming approaches are employed for the shortest path problems, different types of criteria which can be decomposed with dynamic programming might be applied to the conventional solution methods. For this class of problems, we employ a leximax-based criterion, which considers the bottlenecks and unfairness among the cost values of partial paths. This criterion is based on a similar criterion called leximin for multiobjective maximization problems. It is also generalized for objective vectors which have variable lengths. We address an extension of the conventional A∗search algorithm and investigate an issue concerning on-line search algorithms. The influence of the proposed approach is experimentally evaluated.. |
| 61. |
Julien Savaux, Julien Vion, Sylvain Piechowiak, Rene Mandiau, Toshihiro Matsui, Katsutoshi Hirayama, Makoto Yokoo, Shakre Elmane, Marius Silaghi, Stochastic Game Modelling for Distributed Constraint Reasoning with Privacy, International Symposium on Artificial Intelligence and Mathematics (ISAIM-2018), 2018.01. |
| 62. |
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), 163-179, 2017.10, 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.. |
| 63. |
Aolong Zha, Kazuki Nomoto, Suguru Ueda, Miyuki Koshimura, Yuko Sakurai, Makoto Yokoo, Coalition Structure Generation for Partition Function Games by Utilizing a Concise Graphical Representation, 20th International Conference on Principles and Practice of Multi-Agent Systems (PRIMA-2017), 143-159, 2017.10, Much of the Distributed Constraint Satisfaction Problem (DisCSP) solving research has addressed cooperating agents, and privacy was frequently mentioned as a significant motivation of the decentralization. While privacy may have a role for cooperating agents, it is easier understood in the context of self-interested utility-based agents, and this is the situation considered here. With utility-based agents, the DisCSP framework can be extended to model privacy and satisfaction under the concept of utility. We introduce Utilitarian Distributed Constraint Satisfaction Problems (UDisCSP), an extension of the DisCSP that exploits the rewards for finding a solution and the costs for losing privacy as guidance for the utility-based agents. A parallel can be drawn between Partially Observable Markov Decision Processes (POMDPs) and the problems solved by individual agents for UDisCSPs. Common DisCSP solvers are extended to take into account the utility function. In these extensions we assume that the planning problem is further restricting the set of communication actions to only the ones available in the corresponding solver protocols. The solvers obtained propose the action to be performed in each situation, defining thereby the policy of the agents.. |
| 64. |
Aolong Zha, Kazuki Nomoto, Suguru Ueda, Miyuki Koshimura, Yuko Sakurai, Makoto Yokoo, Coalition Structure Generation for Partition Function Games Utilizing a Concise Graphical Representation, Proceedings of PRIMA 2017, 10.1007/978-3-319-69131-2_9, 143-159, 2017.10. |
| 65. |
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.. |
| 66. |
Kazunori Ohta, Nathanael Barrot, Anisse Ismaili, Yuko Sakurai, Makoto Yokoo, Core Stability in Hedonic Games among Friends and Enemies: Impact of Neutrals, 26th International Joint Conference on Artificial Intelligence (IJCAI-2017), 359-365, 2017.08, We investigate hedonic games under enemies aversion and friends appreciation, where every agent considers other agents as either a friend or an enemy. We extend these simple preferences by allowing each agent to also consider other agents to be neutral. Neutrals have no impact on her preference, as in a graphical hedonic game. Surprisingly, we discover that neutral agents do not simplify matters, but cause complexity. We prove that the core can be empty under enemies aversion and the strict core can be empty under friends appreciation. Furthermore, we show that under both preferences, deciding whether the strict core is nonempty, is NPNP-complete. This complexity extends to the core under enemies aversion. We also show that under friends appreciation, we can always find a core stable coalition structure in polynomial time.. |
| 67. |
Naoto Hamada, Chia-Ling Hsu, Ryoji Kurata, Takamasa Suzuki, Suguru Ueda, Makoto Yokoo, Strategy-proof school choice mechanisms with minimum quotas and initial endowments, ARTIFICIAL INTELLIGENCE, 10.1016/j.artint.2017.04.006, 249, 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. (C) 2017 The Authors. Published by Elsevier B.V.. |
| 68. |
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.. |
| 69. |
Julien Lesca, Patrice Perny, Makoto Yokoo, Coalition structure generation and cs-core
Results on the tractability frontier for games represented by MC-nets, 16th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2017, 308-316, 2017.05, The coalition structure generation (CSG) problem consists in partitioning a group of agents into coalitions to maximize the sum of their values. We consider here the rase of coalitional games whose characteristic function is compactly represented by a set of weighted conjunctive formulae (an MC-net). In this context the CSG problem is known to be computationally hard in general. In this paper, we first study some key parameters of MC- nets that complicate solving make the CSG problem. Then we consider a specific class of MC-nets, called bipolar MC- nets, and prove that the CSG problem is polynomial for this class. Finally, we show that the CS-core of a game represented by a bipolar MC-net is never empty, and that an imputation belonging to the CS-core can be computed in polynomial time.. |
| 70. |
Khoi D. Hoang, Ping Hou, Ferdinando Fioretto, William Yeoh, Roie Zivan, Makoto Yokoo, Infinite-horizon proactive dynamic DCOPs, 16th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2017, 212-220, 2017.05, The Distributed Constraint Optimization Problem (DCOP) formulation is a powerful tool for modeling multi-Agent coordination problems. Researchers have recently extended this model to Proactive Dynamic DCOPs (PD-DCOPs) to capture the inherent dynamism present in many coordination problems. The PD-DCOP formulation is a finite-horizon model that assumes a finite horizon is known a priori. It ignores changes to the problem after the horizon and is thus not guaranteed to find optimal solutions for infinite-horizon problems, which often occur in the real world. Therefore, we (i) propose the Infinite-Horizon PD-DCOP (IPD- DCOP) model, which extends PD-DCOPs to handle infinite horizons', (ii) exploit the convergence properties of Markov chains to determine the optimal solution to the problem after it has converged; (Hi) propose three distributed greedy algorithms to solve IPD-DCOPs; (iv) provide theoretical quality guarantees on the new model; and (v) empirically evaluate both proactive and reactive algorithms to determine the tradeoffs between the two classes. The final contribution is important as, thus far. researchers have exclusively evaluated the two classes of algorithms in isolation. As a result, it is difficult to identify the characteristics of problems that they excel in. Our results arc the first in this important direction.. |
| 71. |
Nathanael Barrot, Jérôme Lang, Makoto Yokoo, Manipulation of hamming-based approval voting for multiple referenda and committee elections, 16th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2017, 1, 597-605, 2017.05, Several methods exist for electing committees of representatives and conducting multiple referenda based on approval voting. Recently, a family of rules for approval-based voting using ordered weighted averaging was proposed in [1], ranging from a simple candidate-wise majority (minisum) to egalitarian rule (minimax). Even though the first rule is strategyproof and the second is not, due to its egalitarian nature, only a partial study on manipulation has been conducted for inbetween rules. This paper investigates the maiiipulability of fair rules within this family. We first prove that all rules parameterized by fair (non-increasing) weight vectors are manipulable, except minisum, if we consider them either resolute with a tie-breaking mechanism or irresolute with classic extension principles. Then, we conduct an empirical study of the proportion of elections that are manipulable, showing that it increases based on the rule's fairness.. |
| 72. |
Naoto Hamada, Anisse Ismaili, Takamasa Suzuki, Makoto Yokoo, Weighted matching markets with budget constraints, 16th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2017, 317-325, 2017.05, We investigate markets with a set of students on one side and a set of colleges on the other. A student and college can be linked by a weighted contract that defines the student's wage, while a college's budget for hiring students is limited. Stability is a crucial requirement for matching mechanisms to be applied in the real world. A standard stability requirement is coalitional stability, i.e., no pair of a college and group of students has incentive to deviate. We find that a coalitionally stable matching is not guaranteed to exist, verifying the coalitional stability for a given matching is coXP- complete, and the problem to find whether a coalitionally stable matching exists in a given market, is NPNP-complete (that is Ef-complete). Given these computational hardness results, we pursue a weaker stability requirement called pairwise stability, i.e., no pair of a college and single student has incentive to deviate. We then design a strategy-proof mechanism that works in polynomial-Time for computing a pairwise stable matching in typed markets in which students are partitioned into types that induce their possible wages.. |
| 73. |
Julien Savaux, Julien Vion, Sylvain Piechowiak, Rene Mandiau, Toshihiro Matsui, Katsutoshi Hirayama, Makoto Yokoo, Shakre Elmane, Marius Silaghi, Utilitarian Approach to Privacy in Distributed Constraint Optimization Problems, Thirtieth International Florida Artificial Intelligence Research Society Conference (FLAIRS-2017), 454-459, 2017.05, Privacy has been a major motivation for distributed problem optimization. However, even though several methods have been proposed to evaluate it, none of them is widely used. The Distributed Constraint Optimization Problem (DCOP) is a fundamental model used to approach various families of distributed problems. Here we approach the problem by letting both the optimized costs found in DCOPs and the privacy requirements guide the agents' exploration of the search space. We introduce Utilitarian Distributed Constraint Optimization Problem (UDCOP) where the costs and the privacy requirements are used as parameters to a heuristic modifying the search process. Common stochastic algorithms for decentralized constraint optimization problems are evaluated here according to how well they preserve privacy.. |
| 74. |
Masahiro Goto, Fuhito Kojima, Ryoji Kurata, Akihisa Tamura, Makoto Yokoo, Designing Matching Mechanisms under General Distributional Constraints, AMERICAN ECONOMIC JOURNAL-MICROECONOMICS, 10.1257/mic.20160124, 9, 2, 226-262, 2017.05, To handle various applications, we study matching under constraints. The only requirement on the constraints is heredity; given a feasible matching, any matching with fewer students at each school is also feasible. Heredity subsumes existing constraints such as regional maximum quotas and diversity constraints. With constraints, there may not exist a matching that satisfies fairness and nonwastefulness (i. e., stability). We demonstrate our new mechanism, the Adaptive Deferred Acceptance mechanism (ADA), satisfies strategy-proofness for students, nonwastefulness, and a weaker fairness property. We also offer a technique to apply ADA even if heredity is violated (e.g., minimum quotas).. |
| 75. |
Fuuki Shigenaka, Tadashi Sekiguchi, Atsushi Iwasaki, Makoto Yokoo, Achieving Sustainable Cooperation in Generalized Prisoner's Dilemma with Observation Errors, Thirty-First AAAI Conference on Artificial Intelligence (AAAI-2017), 677-683, 2017.02. |
| 76. |
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. |
| 77. |
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. |
| 78. |
Oskar Skibski, Makoto Yokoo, 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. |
| 79. |
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, 10.1007/978-3-319-44832-9_11, 181-196, 2016.10, 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.. |
| 80. |
Julien Savaux, Julien Vion, Sylvain Piechowiak, Rene Mandiau, Toshihiro Matsui, Katsutoshi Hirayama, Makoto Yokoo, Shakre Elmane, Marius Silaghi, DisCSPs with Privacy Recast as Planning Problems for Self-Interested Agents, 2016 IEEE/WIC/ACM International Conference on Web Intelligence (WI-2016), 359-366, 2016.10, Much of the Distributed Constraint Satisfaction Problem (DisCSP) solving research has addressed cooperating agents, and privacy was frequently mentioned as a significant motivation of the decentralization. While privacy may have a role for cooperating agents, it is easier understood in the context of self-interested utility-based agents, and this is the situation considered here. With utility-based agents, the DisCSP framework can be extended to model privacy and satisfaction under the concept of utility. We introduce Utilitarian Distributed Constraint Satisfaction Problems (UDisCSP), an extension of the DisCSP that exploits the rewards for finding a solution and the costs for losing privacy as guidance for the utility-based agents. A parallel can be drawn between Partially Observable Markov Decision Processes (POMDPs) and the problems solved by individual agents for UDisCSPs. Common DisCSP solvers are extended to take into account the utility function. In these extensions we assume that the planning problem is further restricting the set of communication actions to only the ones available in the corresponding solver protocols. The solvers obtained propose the action to be performed in each situation, defining thereby the policy of the agents.. |
| 81. |
Masahiro Goto, Atsushi Iwasaki, Yujiro Kawasaki, Ryoji Kurata, Yosuke Yasuda, Makoto Yokoo, Strategyproof matching with regional minimum and maximum quotas, Artificial Intelligence, 10.1016/j.artint.2016.02.002, 235, 40-57, 2016.06, This paper considers matching problems with individual/regional minimum/maximum quotas. Although such quotas are relevant in many real-world settings, there is a lack of strategyproof mechanisms that take such quotas into account. We first show that without any restrictions on the regional structure, checking the existence of a feasible matching that satisfies all quotas is NP-complete. Then, assuming that regions have a hierarchical structure (i.e., a tree), we show that checking the existence of a feasible matching can be done in time linear in the number of regions. We develop two strategyproof matching mechanisms based on the Deferred Acceptance mechanism (DA), which we call Priority List based Deferred Acceptance with Regional minimum and maximum Quotas (PLDA-RQ) and Round-robin Selection Deferred Acceptance with Regional minimum and maximum Quotas (RSDA-RQ). When regional quotas are imposed, a stable matching may no longer exist since fairness and nonwastefulness, which compose stability, are incompatible. We show that both mechanisms are fair. As a result, they are inevitably wasteful. We show that the two mechanisms satisfy different versions of nonwastefulness respectively; each is weaker than the original nonwastefulness. Moreover, we compare our mechanisms with an artificial cap mechanism via simulation experiments, which illustrate that they have a clear advantage in terms of nonwastefulness and student welfare.. |
| 82. |
Masahiro Goto, Atsushi Iwasaki, Yujiro Kawasaki, Ryoji Kurata, Yosuke Yasuda, Makoto Yokoo, Strategyproof matching with regional minimum and maximum quotas, ARTIFICIAL INTELLIGENCE, 10.1016/j.artint.2016.02.002, 235, 40-57, 2016.06, This paper considers matching problems with individual/regional minimum/maximum quotas. Although such quotas are relevant in many real-world settings, there is a lack of strategyproof mechanisms that take such quotas into account. We first show that without any restrictions on the regional structure, checking the existence of a feasible matching that satisfies all quotas is NP-complete. Then, assuming that regions have a hierarchical structure (i.e., a tree), we show that checking the existence of a feasible matching can be done in time linear in the number of regions. We develop two strategyproof matching mechanisms based on the Deferred Acceptance mechanism (DA), which we call Priority List based Deferred Acceptance with Regional minimum and maximum Quotas (PLDA-RQ) and Round-robin Selection Deferred Acceptance with Regional minimum and maximum Quotas (RSDA-RQ). When regional quotas are imposed, a stable matching may no longer exist since fairness and nonwastefulness, which compose stability, are incompatible. We show that both mechanisms are fair. As a result, they are inevitably wasteful. We show that the two mechanisms satisfy different versions of nonwastefulness respectively; each is weaker than the original nonwastefulness. Moreover, we compare our mechanisms with an artificial cap mechanism via simulation experiments, which illustrate that they have a clear advantage in terms of nonwastefulness and student welfare. (C) 2016 The Authors. Published by Elsevier B.V.. |
| 83. |
Oskar Skibski, Talal Rahwan, Tomasz P. Michalak, Makoto Yokoo, Attachment centrality
An axiomatic approach to connectivity in networks, 15th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2016, 168-176, 2016.05, Centrality indices aim to quantify the importance of nodes or edges in a network. A number of new centrality indices have recently been proposed to try and capture the role of nodes in connecting the network. While these indices seem to deliver new insights, to date not enough is known about their theoretical properties. To address this issue, we propose an axiomatic approach. Specifically, we prove that there exists a unique centrality index satisfying some intuitive properties related to network connectivity. This new index, which we call Attachment Centrality, is equivalent to the Myerson value of a particular graph-restricted coalitional game. Building upon our theoretical analysis, we show that our Attachment Centrality has certain computational properties that are more attractive than the Myerson value for an arbitrary game.. |
| 84. |
Oskar Skibski, Szymon Matejczyk, Tomasz P. Michalak, Michael Wooldridge, Makoto Yokoo, K-coalitional cooperative games, 15th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2016, 177-185, 2016.05, In most previous models of coalition structure generation, it is assumed that agents may partition themselves into any coalition structure. In practice, however, there may be physical and organizational constraints that limit the number of co-existing coalitions. In this paper, we introduce k-coalitional games: a type of partition function game especially designed to model such situations. We propose an extension of the Shapley value for these games, and study its axiomatic and computational properties. In particular, we show that, under some conditions, it can be computed in polynomial time given two existing representations of coalitional games with externalities. Finally, we use k-coalitional games to analyse the relative importance of geographical locations in the game of Diplomacy.. |
| 85. |
Yuto Tominaga, Taiki Todov, Makoto Yokoo, Manipulations in two-agent sequential allocation with random sequences, 15th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2016, 141-149, 2016.05, Sequential allocation is one of the most fundamental models for allocating indivisible items to agents in a decentralized manner, in which agents sequentially pick their favorite items among the remainder based on a pre-defined priority ordering of agents (a sequence). In recent years, algorithmic issues about agents' manipulations have also been investigated, such as the computational complexity of verifying whether a given bundle of items is achievable and maximizing one's utility under a given additive utility function. In this paper we consider a slightly modified model, where the selection process is divided into rounds, each agent obtains exactly one item in each round, and the sequence per round is determined uniformly at random. It is natural to expect that finding a profitable manipulation is difficult even for the case of two agents, since a manipulator must consider exponentially many possible sequences with respect to the number of rounds due to randomization. To our surprise, however, an optimal manipulation can be computed without any exploration for exponentially decaying utilities. Furthermore, for general additive utilities, although some exploration is required, it can still be done in polynomial time with respect to the number of rounds.. |
| 86. |
Ryoji Kurata, Naoto Hamada, Chia Ling Hsu, Takamasa Suzuki, Suguru Ueda, Makoto Yokoo, Pareto efficient strategy-proof school choice mechanism with minimum quotas and initial endowments, 15th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2016, 59-67, 2016.05, This paper develops a strategy-proof and Pareto efficient mechanism for a school choice program called Top Trading Cycles among Representatives with Supplementary Seats (TTCR-SS). We consider a setting where minimum quotas are imposed for each school, i.e., a school is required to be assigned at least a certain number of students to operate, and the obtained matching must respect 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 achieve both of them simultaneously. Furthermore, existing mechanisms require that all students consider all schools acceptable to obtain a feasible matching that respects minimum quotas and cannot guarantee Pareto efficiency. TTCR-SS is based on Top Trading Cycles (TTC) mechanism, while it is significantly extended to handle the supplementary seats of schools while respecting minimum quotas. Our simulation results show TTCR-SS is significantly better than an existing TTC-based mechanism in terms of students' welfare.. |
| 87. |
Khoi D. Hoang, Ferdinando Fioretto, Ping Hou, Makoto Yokoo, William Yeoh, Roie Zivan, Proactive dynamic distributed constraint optimization, 15th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2016, 597-605, 2016.05, Current approaches that model dynamism in DCOPs solve a sequence of static problems, reacting to changes in the environment as the agents observe them. Such approaches thus ignore possible predictions on future changes. To overcome this limitation, we introduce Proactive Dynamic DCOPs (PD-DCOPs), a novel formalism to model dynamic DCOPs in the presence of exogenous uncertainty. In contrast to reactive approaches, PD-DCOPs are able to explicitly model the possible changes to the problem, and take such information into account proactively, when solving the dynamically changing problem. The additional expressivity of this formalism allows it to model a wider variety of distributed optimization problems. Our work presents both theoretical and practical contributions that advance current dynamic DCOP models: (i) we introduce the PD-DCOP model, which explicitly captures dynamic changes of the DCOP over time; (ii) we discuss the complexity of this new class of DCOPs; and (iii) we develop both exact and approximation algorithms with quality guarantees to solve PD-DCOPs proactively.. |
| 88. |
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, 615-621, 2016.02, 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.. |
| 89. |
Marius Silaghi, Song Qui, Toshihiro Matsui, Makoto Yokoo, Katsutoshi Hirayama, Bayesian network-based extension for PGP - Estimating petition support, 29th International Florida Artificial Intelligence Research Society Conference, FLAIRS 2016
, 98-103, 2016.01, Consider the problem of estimating the expected number of distinct eligible voters among the authors of a set of electronic signatures gathered for a petition (or citizen initiative) that has to pass legally required thresholds. We formalize this problem and propose an extension to the Pretty Good Privacy Web Of Trust, a mechanism for reciprocally certifying identities between peers. The extension (a) enables agents to certify additional relevant statements about others, and (b) gives agents opportunities for negative authentication statements (e.g., on ineligibility of an identity). A Bayesian Network model enables inferences on the data provided by the proposed PGP extension. Simulations and an agent-based platform are used to validate the concepts.. |
| 90. |
Daniel Fragiadakis, Atsushi Iwasaki, Peter Troyan, Suguru Ueda, Makoto Yokoo, Strategyproof matching with minimum quotas, ACM Transactions on Economics and Computation, 10.1145/2841226, 4, 1, 2015.12, We study matching markets in which institutions may have minimum and maximum quotas. Minimum quotas are important in many settings, such as hospital residency matching, military cadet matching, and school choice, but current mechanisms are unable to accommodate them, leading to the use of ad hoc solutions. We introduce two new classes of strategyproof mechanisms that allow for minimum quotas as an explicit input and show that our mechanisms improve welfare relative to existing approaches. Because minimum quotas cause a theoretical incompatibility between standard fairness and nonwastefulness properties, we introduce new second-best axioms and show that they are satisfied by our mechanisms. Last, we use simulations to quantify (1) the magnitude of the potential efficiency gains from our mechanisms and (2) how far the resulting assignments are from the first-best definitions of fairness and nonwastefulness. Combining both the theoretical and simulation results, we argue that our mechanisms will improve the performance of matching markets with minimum quota constraints in practice.. |
| 91. |
Atsushi Iwasaki, Tadashi Sekiguchi, Shun Yamamoto, Makoto Yokoo, How is cooperation/collusion sustained in repeated multimarket contact with observation errors?, AAAI Fall Symposium on Sequential Decision Making for Intelligent Agents, 46-53, 2015.11. |
| 92. |
Yuko Sakurai, Masato Shinoda, Satoshi Oyama, Makoto Yokoo, Flexible reward plans for crowdsourced tasks, 18th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2015, 10.1007/978-3-319-25524-8_25, 400-415, 2015.10, We develop flexible reward plans to elicit truthful predictive probability distribution over a set of uncertain events from workers. In general, strictly proper scoring rules for categorical events only reward a worker for an event that actually occurred. However, different incorrect predictions vary in quality, and the principal would like to assign different rewards to them, according to her subjective similarity among events; e.g. a prediction of overcast is closer to sunny than rainy. We propose concrete methods so that the principal can assign rewards for incorrect predictions according to her similarity between events. We focus on two representative examples of strictly proper scoring rules: spherical and quadratic, where a worker’s expected utility is represented as the inner product of her truthful predictive probability and her declared probability. In this paper, we generalize the inner product by introducing a reward matrix that defines a reward for each prediction outcome pair. We first show that if the reward matrix is symmetric and positive definite, both the spherical and quadratic proper scoring rules guarantee the maximization of a worker’s expected utility when she truthfully declares her prediction. We next compare our rules with the original spherical/quadratic proper scoring rules in terms of the variance of rewards obtained by workers. Finally, we show our experimental results using Amazon Mechanical Turk.. |
| 93. |
Toshihiro Matsui, Marius Silaghi, Tenda Okimoto, Katsutoshi Hirayama, Makoto Yokoo, Hiroshi Matsuo, Leximin asymmetric multiple objective DCOP on factor graph, 18th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2015, 10.1007/978-3-319-25524-8_9, 134-151, 2015.10, Leximin AMODCOP has been proposed as a class of Multiple Objective Distributed Constraint Optimization Problems, where multiple objectives for individual agents are optimized based on the leximin operator. This problem also relates to Asymmetric DCOPs with the criteria of fairness among agents, which is an important requirement in practical resource allocation tasks. Previous studies explore only Leximin AMODCOPs on constraint graphs limited to functions with unary or binary scopes.We address the Leximin AMODCOPs on factor graphs that directly represent n-ary functions. A dynamic programming method on factor graphs is investigated as an exact solution method. In addition, for relatively dense problems, we also investigate several inexact algorithms.. |
| 94. |
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, 10.1007/978-3-319-25524-8_8, 118-133, 2015.10, 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.. |
| 95. |
Toshihiro Matsui, Marius Silaghi, Tenda Okimoto, Katsutoshi, Hirayama, Makoto Yokoo, Hiroshi Matsuo, Leximin Asymmetric Multiple Objective DCOP on Factor Graph, 18th International Conference on Principles and Practice of Multi-Agent Systems (PRIMA-2015), 134-151, 2015.10. |
| 96. |
Toshihiro Matsui, Marius Silaghi, Tenda Okimoto, Katsutoshi Hirayama, Makoto Yokoo, Hiroshi Matsuo, Leximin Asymmetric Multiple Objective DCOP on Factor Graph, Proceedings of the 18th International Conference on Principles and Practice of Multi-Agent Systems (PRIMA-2015), 10.1007/978-3-319-25524-8_9, 134-151, 2015.10. |
| 97. |
Oskar Skibski, Tomasz P. Michalak, Yuko Sakurai, Makoto Yokoo, A pseudo-polynomial algorithm for computing power indices in graph-restricted weighted voting games, 24th International Joint Conference on Artificial Intelligence, IJCAI 2015, 631-637, 2015.07, Weighted voting games allow for studying the distribution of power between agents in situations of collective decision making. While the conventional version of these games assumes that any agent is always ready to cooperate with all others, recently, more involved models have been proposed, where cooperation is subject to restrictions. Following Myerson [1977], such restrictions are typically represented by a graph that expresses available communication links among agents. In this paper, we study the time complexity of computing two well-known power indices - the Shapley-Shubik index and the Banzhaf index - in the graph-restricted weighted voting games. We show that both are #P-complete and propose a dedicated dynamic-programming algorithm that runs in pseudo-polynomial time for graphs with the bounded treewidth.. |
| 98. |
Zhaohong Sun, Hideaki Hata, Taiki Todo, Makoto Yokoo, Exchange of indivisible objects with asymmetry, 24th International Joint Conference on Artificial Intelligence, IJCAI 2015, 97-103, 2015.07, 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.. |
| 99. |
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, 2, 907-913, 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.. |
| 100. |
Oskar Skibski, Tomasz P. Michalak, Yuko Sakurai, Michael Wooldridge, Makoto Yokoo, A graphical representation for games in partition function form, 29th AAAI Conference on Artificial Intelligence, AAAI 2015 and the 27th Innovative Applications of Artificial Intelligence Conference, IAAI 2015
, 1036-1042, 2015.06, We propose a novel representation for coalitional games with externalities, called Partition Decision Trees. This representation is based on rooted directed trees, where non-leaf nodes are labelled with agents' names, leaf nodes are labelled with payoff vectors, and edges indicate membership of agents in coalitions. We show that this representation is fully expressive, and for certain classes of games significantly more concise than an extensive representation. Most importantly, Partition Decision Trees are the first formalism in the literature under which most of the direct extensions of the Shapley value to games with externalities can be computed in polynomial time.. |
| 101. |
Ryoji Kurata, Masahiro Goto, Atsushi Iwasaki, Makoto Yokoo, Controlled school choice with soft bounds and overlapping types, 29th AAAI Conference on Artificial Intelligence, AAAI 2015 and the 27th Innovative Applications of Artificial Intelligence Conference, IAAI 2015
, 951-957, 2015.06, School choice programs are implemented to give students/parents an opportunity to choose the public school the students attend. Controlled school choice programs need to provide choices for students/parents while maintaining distributional constraints on the balance on the composition of students, typically in terms of socioeconomic status. Previous works show that setting soft-bounds, which flexibly change the priorities of students based on their types, is more appropriate than setting hard-bounds, which strictly limit the number of accepted students for each type. We consider a case where soft-bounds are imposed and one student can belong to multiple types, e.g., "financially-distressed" and "minority" types. We first show that when we apply a model that is a straightforward extension of an existing model for disjoint types, there is a chance that no stable matching exists. Thus, we propose an alternative model and an alternative stability definition, where a school has reserved seats for each type. We show that a stable matching is guaranteed to exist in this model, and develop a mechanism called Deferred Acceptance for Overlapping Types (DA-OT). The DA-OT mechanism is strategy-proof and obtains the student-optimal matching within all stable matchings. Computer simulation results illustrate that the DA-OT outperforms an artificial cap mechanism, where the number of seats for each type is fixed.. |
| 102. |
Masahiro Goto, Fuhito Kojima, Ryoji Kurata, Akihisa Tamura, Makoto Yokoo, Designing matching mechanisms under general distributional constraints (extended abstract), EC 2015 - Proceedings of the 2015 ACM Conference on Economics and Computation, 10.1145/2764468.2764501, 259-260, 2015.06. |
| 103. |
Atsushi Iwasaki, Suguru Ueda, Naoyuki Hashimoto, Makoto Yokoo, Finding core for coalition structure utilizing dual solution, Artificial Intelligence, 10.1016/j.artint.2015.01.001, 222, 49-66, 2015.05, When forming the grand coalition is not possible or optimal, agents need to create a coalition structure. The idea of the core can be extended to such a case. In this paper, we propose an innovative exact algorithm called CoreD to check core-non-emptiness for coalition structures. A more straightforward exact algorithm based on existing techniques, which we call CoreP, first obtains the value of optimal coalition structure by solving an integer programming problem. Then, it checks whether that value can be divided without making a blocking (dissatisfied) coalition. In contrast, CoreD first finds a minimal value of the optimal coalition structure so that there exists no blocking coalition. Next, it checks whether the optimal value equals the minimal value We empirically show that when the core is empty, CoreD is by far superior to CoreP. Also, to find a second-best payoff vector when the core is empty, we propose a new solution concept called the weak ε-core+, which can utilize the approximate value of the optimal coalition structure. Based on the idea of CoreD, we further develop an algorithm for checking the non-emptiness of the weak ε-core+.. |
| 104. |
Masahiro Goto, Ryoji Kurata, Naoto Hamada, Atsushi Iwasaki, Makoto Yokoo, Improving fairness in nonwasteful matching with hierarchical regional minimum quotas, 14th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015, 1887-1888, 2015.05, This paper considers matching problems with hierarchical regional minimum quotas. Although such quotas are relevant in many real-world settings, it is known that nonwastefulness and fairness (which compose stability) are incompatible when minimum quotas are imposed. We develop a new strategy-proof nonwasteful mechanism called Adaptive Deferred Acceptance with Regional minimum Quotas (ADARQ), which is fairer than an existing nonwasteful mechanism called Multi-Stage DA with Regional minimum Quotas (MSDA-RQ).. |
| 105. |
Shunsuke Tsuruta, Masaaki Oka, Taiki Todo, Yuko Sakurai, Makoto Yokoo, Fairness and false-name manipulations in randomized cake cutting, 14th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015
, 2, 909-917, 2015.05, Cake cutting has been recognized as a fundamental model in fair division, and several envy-free cake cutting algorithms have been proposed. Recent works from the computer science field proposed novel mechanisms for cake cutting, whose approaches are based on the theory of mechanism design; these mechanisms are strategy-proof, i.e., no agent has any incentive to misrepresent her utility function, as well as envy-free. We consider a different type of manipulations; each agent might create fake identities to cheat the mechanism. Such manipulations have been called Sybils or falsename manipulations, and designing robust mechanisms against them, i.e., false-name-proof, is a challenging problem in mechanism design literature. We first show that no randomized false-name-proof cake cutting mechanism simultaneously satisfies ex-post envy-freeness and Pareto efficiency. We then propose a new randomized mechanism that is optimal in terms of worst-case loss among those that satisfy false-name-proofness, ex-post envy-freeness, and a new weaker efficiency property. However, it reduces the amount of allocations for an agent exponentially with respect to the number of agents. To overcome this negative result, we provide another new cake cutting mechanism that satisfies a weaker notion of false-name-proofness, as well as ex-post envy-freeness and Pareto efficiency.. |
| 106. |
Mingyu Guo, Hong Shen, Taiki Todo, Yuko Sakurai, Makoto Yokoo, Social decision with minimal efficiency loss
An automated mechanism design approach, 14th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015
, 1, 347-355, 2015.05, We study the problem where a group of agents need to choose from a finite set of social outcomes. We assume every agent's valuation for every outcome is bounded and the bounds are public information. For our model, no mechanism simultaneously satisfies strategy-proofness, individual rationality, non-deficit, and efficiency. In light of this, we aim to design mechanisms that are strategy-proof, individually rational, non-deficit, and minimize the worst-case efficiency loss. We propose a family of mechanisms called the shifted Groves mechanisms, which are generalizations of the Groves mechanisms. We first show that if there exist mechanisms that are strategy-proof, individually rational, and non-deficit, then there exist shifted Groves mechanisms with these properties. Our main result is an Automated Mechanism Design (AMD) approach for identifying the (unique) optimal shifted Groves mechanism, which minimizes the worst-case efficiency loss among all shifted Groves mechanisms. Finally, we prove that the optimal shifted Groves mechanism is globally optimal among all deterministic mechanisms that are strategy-proof, individually rational, and non-deficit.. |
| 107. |
Atsushi Iwasaki, Etsushi Fujita, Taiki Todo, Hidenao Iwane, Hirokazu Anai, Mingyu Guo, Makoto Yokoo, Parametric mechanism design via quantifier elimination, Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS2015), 1885-1886, 2015.05. |
| 108. |
Atsushi Iwasaki, Tadashi Sekiguchi, Shun Yamamoto, Makoto Yokoo, Can local caution restore global tacit collusion?: Repeated multimarket contact with observation, AAAI Spring Symposium on Applied Computational Game Theory, ...-..., 2015.03. |
| 109. |
Atsushi Iwasaki, Tadashi Sekiguchi, Shun Yamamoto, Makoto Yokoo, How is cooperation/collusion sustained in repeated multimarket contact with observation errors?, AAAI 2015 Fall Symposium
, 46-53, 2015.01, This paper analyzes repeated multimarket contact with observation errors where two players operate in multiple markets simultaneously. Multimarket contact has received much attention from the literature of economics, management, and information systems. Despite vast empirical studies that examine whether multimarket contact fosters cooperation/collusion, little is theo-retically known as to how players behave in an equilibrium when each player receives a noisy observation of other firms' actions. This paper tackles an essentially realistic situation where the players do not share common information; each player may observe a different signal (private monitoring). Thus, players have difficulty in having a common understanding about which market their opponent should be punished in and when punishment should be started and ended. We first theoretically show that an extension of 1-period mutual punishment (IMP) for an arbitrary number of markets can be an equilibrium. Second, by applying a verification method, we identify a simple equilibrium strategy called "locally cautioning (LC)" that restores collusion after observation error or deviation. We then numerically reveal that LC significantly outperforms IMP and achieves the highest degree of collusion.. |
| 110. |
Katsutoshi Hirayama, Kenta Hanada, Suguru Ueda, Makoto Yokoo, Atsushi Iwasaki, Computing a payoff division in the least core for MC-nets coalitional games, 17th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2014, 319-332, 2014.12, MC-nets is a concise representation of the characteristic functions that exploits a set of rules to compute payoffs. Given aMC-nets instance, the problem of computing a payoff division in the least core, which is a generalization of the core-non-emptiness problem that is known to be coNP-complete, is definitely a hard computational problem. In fact, to the best of our knowledge, no algorithm can actually compute such a payoff division for MC-nets instances with dozens of agents. We propose a new algorithm for this problem, that exploits the constraint generation technique to solve the linear programming problem that potentially has a huge number of constraints. Our experimental results are striking since, using 8 GB memory, our proposed algorithm can successfully compute a payoff division in the least core for the instances with up to 100 agents, but the naive algorithm fails due to a lack of memory for instances with 30 or more agents.. |
| 111. |
Toshihiro Matsui, Marius Silaghi, Katsutoshi Hirayama, Makoto Yokoo, Hiroshi Matsuo, Leximin multiple objective optimization for preferences of agents, 17th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2014, 423-438, 2014.12, We address a variation of Multiple Objective Distributed Constraint Optimization Problems (MODCOPs). In the conventional MODCOPs, a few objectives are globally defined and agents cooperate to find the Pareto optimal solution. On the other hand, in several practical problems, the share of each agent is important. Such shares are represented as preference values of agents. This class of problems is defined as theMODCOP on the preferences of agents. Particularly, we focus on the optimization problems based on the leximin ordering (Leximin AMODCOPs), which improves the equality among agents. The solution methods based on pseudo trees are applied to the Leximin AMODCOPs.. |
| 112. |
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-2014), 184-191, 2014.11. |
| 113. |
Dengji Zhao, Siqi Luo, Taiki Todo, Makoto Yokoo, False-name-proof combinatorial auction design via single-minded decomposition, 21st European Conference on Artificial Intelligence, ECAI 2014, 10.3233/978-1-61499-419-0-945, 945-950, 2014.08, This paper proposes a new approach to building false-name-proof (FNP) combinatorial auctions from those that are FNP only with single-minded bidders, each of whom requires only one particular bundle. Under this approach, a general bidder is decomposed into a set of single-minded bidders, and after the decomposition the price and the allocation are determined by the FNP auctions for single-minded bidders. We first show that the auctions we get with the single-minded decomposition are FNP if those for single-minded bidders satisfy a condition called PIA. We then show that another condition, weaker than PIA, is necessary for the decomposition to build FNP auctions. To close the gap between the two conditions, we have found another sufficient condition weaker than PIA for the decomposition to produce strategy-proof mechanisms. Furthermore, we demonstrate that once we have PIA, the mechanisms created by the decomposition actually satisfy a stronger version of false-name-proofness, called false-name-proofness with withdrawal.. |
| 114. |
Taiki Todo, Haixin Sun, Makoto Yokoo, Strategyproof exchange with multiple private endowments, 28th AAAI Conference on Artificial Intelligence, AAAI 2014, 26th Innovative Applications of Artificial Intelligence Conference, IAAI 2014 and the 5th Symposium on Educational Advances in Artificial Intelligence, EAAI 2014, 805-811, 2014.07, We study a mechanism design problem for exchange economies where each agent is initially endowed with a set of indivisible goods and side payments arc not allowed. We assume each agent can withhold some endowments. as well as misreport her preference. Under this assumption, strategyproofness requires that for each agent, reporting her true preference with revealing all her endowments is a dominant strategy, and thus implies individual rationality. Our objective in this paper is to analyze the effect of such private ownership in exchange economies with multiple endowments. As fundamental results, we first show that the revelation principle holds under a natural assumption and that strategyproofness and Pareto efficiency are incompatible even under the lexicographic preference domain. We then propose a class of exchange rules, each of which has a corresponding directed graph to prescribe possible trades, and provide necessary and sufficient conditions on the graph structure so that they satisfy strategyproofness.. |
| 115. |
Akihisa Sonoda, Etsushi Fujita, Taiki Todo, Makoto Yokoo, Two case studies for trading multiple indivisible goods with indifferences, 28th AAAI Conference on Artificial Intelligence, AAAI 2014, 26th Innovative Applications of Artificial Intelligence Conference, IAAI 2014 and the 5th Symposium on Educational Advances in Artificial Intelligence, EAAI 2014, 791-797, 2014.07, Individual rationality, Pareto efficiency, and strategy-proofness are crucial properties of decision making functions, or mechanisms, in social choice literatures. In this paper we investigate mechanisms for exchange models where each agent is initially endowed with a set of goods and may have indifferences on distinct bundles of goods, and monetary transfers are not allowed. Sönmez (1999) showed that in such models, those three properties are not compatible in general. The impossibility, however, only holds under an assumption on preference domains. The main purpose of this paper is to discuss the compatibility of those three properties when the assumption does not hold. We first establish a preference domain called top-only preferences, which violates the assumption, and develop a class of exchange mechanisms that satisfy all those properties. Each mechanism in the class utilizes one instance of the mechanisms introduced by Saban and Sethuraman (2013). We also find a class of preference domains called m-chotomous preferences, where the assumption fails and these properties are incompatible.. |
| 116. |
Julien Lesca, Taiki Todo, Makoto Yokoo, Coexistence of utilitarian efficiency and false-name-proofness in social choice, 13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014, 1201-1208, 2014.05, The class of Groves mechanisms has been attracting much attention in mechanism design literature due to two attractive characteristics: utilitarian efficiency (also called social welfare maximization) and dominant strategy incentive compatibility. However, when strategic agents can create multiple fake identities and reveal more than one preference under them, a refined characteristic called false-name-proofness is required. Utilitarian efficiency and false-name-proofness are incompatible in combinatorial auctions, if we also have individual rationality as a desired condition. However, although individual rationality is strongly desirable, if participation is mandatory due to social norms or reputations, a mechanism without individual rationality can be sustained. In this paper we investigate the relationship between utilitarian efficiency and false-name-proofness in a social choice environment with monetary transfers. We show that in our modelization no mechanism simultaneously satisfies utilitarian efficiency, false-name-proofness, and individual rationality. Considering this fact, we ignore individual rationality and design various mechanisms that simultaneously satisfy the other two properties. We also compare our different mechanisms in terms of the distance to individual rationality. Finally we illustrate our mechanisms on a facility location problem.. |
| 117. |
Dengji Zhao, Dongmo Zhang, Enrico H. Gerding, Yuko Sakurai, Makoto Yokoo, Incentives in ridesharing with deficit control, 13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014, 1021-1028, 2014.05, This paper proposes a novel market-based system for ridesharing, where commuters are matched based on their declared travel constraints, the number of available seats (which could be zero), and their costs. Based on this information, the system then designates commuters to be either drivers or riders, finds appropriate matches, and calculates rewards for drivers and payments for riders. We show that, for this system, the well-known Vickrey-Clarke-Groves (VCG) mechanism is incentive compatible (IC), individually rational (IR) and efficient (i.e., minimizing cost), but results in a very high deficit, thus requiring large subsidies. We therefore investigate alternative mechanisms. We first consider mechanisms with fixed prices and show that no such mechanism can be both efficient and IC. Thus, we propose an inefficient IC mechanism but which has deficit control. We then consider a VCG mechanism with two-sided reserve prices. We show that this mechanism is IC and IR for a certain range of reserve prices, and we analyse the deficit bounds and how these can be controlled. We furthermore show that the deficit can be controlled even further by limiting the (costly) detours taken by the drivers when computing the allocations, thereby trading off efficiency and deficit.. |
| 118. |
Shunsuke Tsuruta, Masaaki Oka, Taiki Todo, Yujiro Kawasaki, Mingyu Guo, Yuko Sakurai, Makoto Yokoo, Optimal false-name-proof single-item redistribution mechanisms, 13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014, 221-228, 2014.05, Although the celebrated Vickrey auction is strategy-proof and guaranteed to achieve an efficient allocation in a single-object auction, if there exists no outside party (i.e., a seller or an auctioneer) with the right to collect the payment, the collected payment will be wasted. Redistribution mechanisms try to redistribute the payment to participating agents as much as possible without violating strategy-proofness. However, when a losing agent can obtain part of the payment, she may have an incentive to participate under multiple identities and receive a greater share of the redistribution. Our goal is to develop false-name-proof redistribution mechanisms that are robust against such manipulations. First, we prove that no mechanism simultaneously satisfies false-name-proofness and allocative efficiency, except for the Vickrey auction. Next, we propose a class of false-name-proof redistribution mechanisms, which are characterized by several parameters. We show that each mechanism in the class is not dominated by any other false-name-proof mechanism in terms of social welfare. Precisely, by choosing these parameters appropriately, all instances of this class are guaranteed to achieve at least the same amount of social welfare obtained by any false-name-proof mechanism. Furthermore, we formalize an optimization problem that determines appropriate parameter values based on prior information about participating agents.. |
| 119. |
Masahiro Goto, Naoyuki Hashimoto, Atshushi Iwasaki, Yujiro Kawasaki, Suguru Ueda, Yosuke Yasuda, Makoto Yokoo, Strategy-proof matching with regional minimum quotas, 13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014, 1225-1232, 2014.05, This paper considers the matching problem with regional quotas, in particular, regional minimum quotas. Although such quotas are relevant in many real-world settings, there is a lack of strategy-proof mechanisms that consider regional minimum quotas. We first show that without any restrictions on the region structure, finding a feasible matching that satisfies all quotas is NP-complete. Then, assuming that regions have a hierarchical structure (in this case, a tree), and maximum quotas are imposed only on individual schools, we show that checking the existence of a feasible matching can be done in a linear time in the number of regions. Furthermore, we develop strategy-proof matching mechanisms based on the Deferred Acceptance mechanism (DA), which we call Multi-Stage DA with Regional minimum Quotas (MSDA-RQ) and Round-robin Selection DA with Regional minimum Quotas (RSDA-RQ). When minimum quotas are imposed, fairness and nonwastefulness are incompatible. We prove that RSDA-RQ is fair but wasteful, while MSDA-RQ is nonwasteful but not fair. Moreover, we compare our mechanisms with artificial cap mechanisms whose individual maximum quotas are adjusted beforehand so that all regional quotas can be automatically satisfied. Our simulation reveals that our mechanisms substantially outperform artificial cap mechanisms in terms of student welfare. Furthermore, it illustrates the trade-off between our mechanisms.. |
| 120. |
S. Qin, Marius C. Silaghi, T. Matsui, M. Yokoo, K. Hirayama, Addressing false identity attacks in action-based P2P social networks with an open census, 2013 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology Workshops, WI-IATW 2013
, 10.1109/WI-IAT.2013.149, 50-57, 2013.12, P2P social networks defined by user actions (e.g., P2P discussion forums) are expected to be ideal environments for Sybil and false identity attacks (just as in the case of the similar web based systems: YouTube, etc.). In particular, these attacks are a significant impediment for meaningful electronic petition drives since they render impossible the verification of the eligibility of participants. While many electronic social networks strive for guaranteeing the privacy (e.g., by anonymization) of their users, existing systems for petition drives, like DirectDemocracyP2P.net, encourage users to disclose their real identities and are meaningless when users do not follow this request. We describe a framework and investigate techniques for running decentralized peer-to-peer census processes that enable observers to independently verify the identity of participants in a social network.. |
| 121. |
Toshihiro Matsui, Marius Silaghi, Katsutoshi Hirayama, Makoto Yokoo, Hiroshi Matsuo, Embedding preference ordering for symmetric DCOP solvers on spanning trees, 16th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2013
, 10.1007/978-3-642-44927-7_14, 197-212, 2013.12, The Max-Sum algorithm is a solution method for the Distributed Constraint Optimization Problem (DCOP) which is a fundamental problem in multiagent cooperation. Particularly, we focus on the case of Max-Sum on a spanning tree, where the algorithm is an exact solution method. In this case, all agents simultaneously compute globally optimal objective values as erootf nodes of the tree that represents the problem. On the other hand, a tiebreak is generally necessary in order to determine a unique optimal solution among the agents. While top-down post-processing is a well-known solution, one can prefer to design the solver as a bottom-up computation that is simply integrated to pre-processing. To address this issue, we investigate a technique that employs a preference ordering based on spanning trees for the optimization algorithms. With this technique, top-down processing to choose a unique optimal solution can be embedded into bottom-up optimization via small weight values for the preference ordering. We also evaluate an integrated algorithm that maintains both tree structures and quasi-optimal solutions using the bottom-up approaches.. |
| 122. |
Yuko Sakurai, Tenda Okimoto, Masaaki Oka, Makoto Yokoo, Strategy-proof mechanisms for the k-winner selection problem, 16th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2013
, 10.1007/978-3-642-44927-7_20, 292-307, 2013.12, The goal of this paper is to develop a strategy-proof (SP) mechanism for the k-winner selection problem, which finds a set of (at most) k winners among participants. Here, we assume the winners can have positive/negative externalities with each other; the gross utility of a winner not only depends on whether she wins, but also on the other winners. If the types of agents, i.e., the gross utilities of agents, are known, we can obtain a Pareto efficient (PE) allocation that maximizes the sum of the gross utilities of winners in polynomial time, assuming k is a constant. On the other hand, when the types of agents are private information, we need a mechanism that can elicit the true types of agents; it must satisfy SP. We first show that there exists no SP mechanism that is PE, individual rational (IR), and non-deficit (ND) in a general setting where we put no restrictions on possible agent types. Thus, we need to give up at least one of these desirable properties. Next, we examine how a family of Vickrey-Clarke-Groves (VCG) based mechanisms works for this problem. We consider two alternative VCG-based mechanisms in this setting, both of which are SP and PE. We show that one alternative, called VCG-ND, is ND but not IR, and the other alternative, called VCG-IR, is IR but not ND. Also, we show special cases where VCG-ND satisfies IR, or VCG-IR satisfies ND. Moreover, we propose mechanisms called VCG-ND+ and VCG-IR+, which can be applied to a general setting, where a mechanism designer has partial knowledge about the possible interactions among agents. Both VCG-ND+ and VCG-IR+ are SP, IR, and ND, but they are not PE. Finally, we present a concise graphical representation scheme of agant types.. |
| 123. |
Yuko Sakurai, Tenda Okimoto, Masaaki Oka, Makoto Yokoo, Strategy-proof mechanisms for the k-winner selection problem, In proceedings of the 13th International Conference on Principles and Practice of Multi-Agent Systems (PRIMA-2013), 10.1007/978-3-642-44927-7_20, 292-307, 2013.12. |
| 124. |
エージェント間に外部性が存在する場合の戦略的操作不可能な割当 てメカニズムの提案. |
| 125. |
A Hybrid Algorithm for Distributed Constraint Optimization (in Japanese). |
| 126. |
Complete/Incomplete Algorithms for MO-DCOPs (in Japanese). |
| 127. |
Atsushi Iwasaki, Suguru Ueda, Makoto Yokoo, Finding the core for coalition structure utilizing dual solution, 2013 12th IEEE/WIC/ACM International Conference on Intelligent Agent Technology, IAT 2013
, 10.1109/WI-IAT.2013.99, 2, 114-121, 2013.11, When forming the grand coalition is not possible/optimal, agents need to create a coalition structure. The idea of the core can be extended to such a case. In this paper, we propose an innovative algorithm called CoreD to check core-non-emptiness for coalition structures. A more straightforward algorithm based on existing techniques, which we call CoreP, first obtains the value of optimal coalition structure by solving an integer programming problem. Then, it checks whether that value can be divided without making a blocking (dissatisfied) coalition. In contrast, CoreD first finds a minimal amount value of optimal coalition structure so that there exists no blocking coalition. Then, it checks whether the optimal value can be equal to the minimal value. We empirically show that when the core is empty, CoreD is by far superior to CoreP. Also, to find a second-best payoff vector when the core is empty, we propose a new solution concept called the weak ε-core+, which can utilize the approximate value of the optimal coalition structure. Based on the idea of CoreD, we further develop an algorithm for checking the non-emptiness of the weak ε-core+.. |
| 128. |
Yuko Sakurai, Tenda Okimoto, Masaaki Oka, Masato Shinoda, Makoto Yokoo, Ability Grouping of Crowd Workers via Reward Discrimination, The First AAAI Conference on Human Computation and Crowdsourcing (HCOMP-2013), 147-155, 2013.11. |
| 129. |
Yuko Sakurai, Tenda Okimoto, Masaaki Oka, Masato Shinoda, Makoto Yokoo, Ability grouping of crowd workers via reward discrimination, The AAAI Conference on Human Computation and Crowdsourcing (HCOMP 2013), 10.1609/hcomp.v1i1.13083, 147-155, 2013.11. |
| 130. |
Toshihiro Matsui, Marius Silaghi, Katsutoshi Hirayama, Makoto Yokoo, Hiroshi Matsuo, Embedding Preference Ordering for Single-phase Self-stabilizing DCOP Solvers, 16th International Conference on Principles and Practice of Multi-Agent Systems(PRIMA 2013), 2013.11. |
| 131. |
Atsushi Iwasaki, Etsushi Fujita, Taiki Todo, Miao Yao, Makoto Yokoo, VCG-Equivalent in Expectation Mechanism: General Framework for Constructing Iterative Combinatorial Auction Mechanisms, The twelfth International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2013), 699-706, 2013.05. |
| 132. |
Pseudo-Tree Based Hybrid Algorithm for Distributed Constraint Optimization. |
| 133. |
Marius C. Silaghi, Khalid Alhamed, Osamah Dhannoon, Song Qin, Rahul Vishen, Ryan Knowles, Ihsan Hussien, Yi Yang, Toshihiro Matsui, Makoto Yokoo, Katsutoshi Hirayama, DirectDemocracyP2P - Decentralized deliberative petition drives - Decentralized d, 13th IEEE International Conference on Peer-to-Peer Computing, IEEE P2P 2013
, 10.1109/P2P.2013.6688733, 2013.01, DirectDemocracyP2P5 is an open source platform developed in JAVA and offering peer-to-peer and mobile ad hoc wireless communication capabilities. The platform offers an API supporting plugins, beside its main application: deliberative petition drives (aka citizens' initiatives with integrated argumentation) [1]. An authentication-by-reputation technique based on digital signatures and peer review [2], [3] is integrated into the platform via this main application. Each peer manages independently its database of items of interest. The items of interest are encapsulated as self-contained pieces of information and uniquely identifiable using a system of global identifiers (GIDs). Each GID consists of a combination of public keys with creation dates, or digest values. Communication is based on a combination of push and pull mechanisms. [1]. |
| 134. |
Toshihiro Matsui, Marius C. Silaghi, Katsutoshi Hirayama, Makoto Yokoo, Hiroshi Matsuo, Distributed search methods for Quantified Distributed Constraint Optimization Problem, Transactions of the Japanese Society for Artificial Intelligence, 10.1527/tjsai.28.43, 28, 1, 43-56, 2013.01, Distributed Constraint Optimization problems (DCOPs) have been studied as a fundamental model of multiagent cooperation. In traditional DCOPs, all agents cooperate to optimize the sum of their cost functions. However, in practical systems some agents may desire to select the value of their variables without cooperation. In special cases, such agents may take the values with the worst impact on the quality of the result reachable by the optimization process. Similar classes of problems have been studied as Quantified (Distributed) Constraint Problems, where the variables of the CSP have existential/universal quantifiers. All constraints should be satisfied independently of the value taken by universal variables. In this paper, a Quantified Distributed Constraint Optimization problem (QDCOP) that extends the framework of DCOPs is presented. We apply existential/universal quantifiers to distinct uncooperative variables. A universally quantified variable is left unassigned by the optimization as the result has to hold when it takes any value from its domain, while an existentially quantified variable takes exactly one of its values for each context. We consider that the QDCOP applies the concept of game tree search to DCOP. If the original problem is a minimization problem, agents that own universally quantified variables may intend to maximize the cost value in the worst case. Other agents normally intend to optimize the minimizing problems. Therefore, only the bounds, especially the upper bounds, of the optimal value are guaranteed. The purpose of the new class of problems is to compute such bounds, as well as to compute sub-optimal solutions. For the QDCOP, we propose solution methods that are based on min-max/alpha-beta and ADOPT algorithms.. |
| 135. |
Makoto Yokoo, Atsushi Iwasaki, Yuko Sakurai, Yoshio Okamoto, Game Theory for Computer Scientists - Cooperative Games, Computer Software, 10.11309/jssst.30.2_33, 30, 2, 33-51, 2013.01, This tutorial introduces a cooperative game theory which is one of main parts in game theory. A cooperative game theory consists of two major research topics. The first topic involves how to divide the value of the coalition among agents. We explain the desirable ways of dividing the rewards among cooperative agents, called solution concepts. The traditional cooperative game theory provides a number of solution concepts, such as the core, the Shapley value, and the nucleolus. We introduce some algorithms for dividing the obtained rewards among agents and show their computational complexities. The second topic involves partitioning a set of agents into coalitions so that the sum of the rewards of all coalitions is maximized. This is called Coalition Structure Generation problem (CSG). We explain efficient constraint optimization algorithms for solving the CSG problem. Furthermore, we introduce concise representation schemes for a characteristic function, since it is likely that we can solve solution concepts/CSG problem more efficiently by utilizing concise representation methods for a game.. |
| 136. |
Makoto Yokoo, Atsushi Iwasaki, Yuko Sakurai, Yoshio Okamoto, Game Theory for Computer Scientist-Mechanism Design (Advanced)., Computer Software, 10.11309/jssst.30.1_34, 30, 1, 34-52, 2013.01, This tutorial focuses on designing a mechanism that achieves a socially desirable outcome or a goal of the designer that arises from some practical demands, as several advanced topics on mechanism design theory. We first briefly explains the theory of combinatorial auctions via the most well-known Vickrey-Clarke-Groves mechanism. Second, as an example that designs a new mechanism for a practical demand, we introduce false-name bids and illustrate how we improve a trivial robust mechanism against false-name bids. Furthermore, we explore models and several theoretical results on mechanisms of a keyword auction and a two-sided matching as other well-known topics of mechanism design theory.. |
| 137. |
Tenda Okimoto, Yongjoon Joe, Atsushi Iwasaki, Makoto Yokoo, Interactive algorithm for multi-objective constraint optimization, Transactions of the Japanese Society for Artificial Intelligence, 10.1527/tjsai.28.57, 28, 1, 57-66, 2013.01, Many real world problems involve multiple criteria that should be considered separately and optimized simultaneously. A Multi-Objective Constraint Optimization Problem (MO-COP) is the extension of a mono-objective Constraint Optimization Problem (COP). In aMO-COP, it is required to provide the most preferred solution for a user among many optimal solutions. In this paper, we develop a novel Interactive Algorithm for MO-COP (MO-IA). The characteristics of this algorithm are as follows: (i) it can guarantee to find a Pareto solution, (ii) it narrows a region, in which Pareto front may exist, gradually, (iii) it is based on a pseudo-tree, which is a widely used graph structure in COP algorithms, and (iv) the complexity of this algorithm is determined by the induced width of problem instances. In the evaluations, we use an existing model for representing a utility function, and show empirically the effectiveness of our algorithm. Furthermore, we propose an extension of MO-IA, which finds several Pareto solutions so that we can provide a narrower region, in which Pareto front may exist, i.e., our extended algorithm can provide the more detailed information for Pareto front.. |
| 138. |
Interactive Algorithm for Multi-objective Constraint Optimization. |
| 139. |
Distributed Search Methods for Quantified Distributed Constraint Optimization Problem. |
| 140. |
Tenda Okimoto, Atsushi Iwasaki, Makoto Yokoo, Effect of DisCSP variable-ordering heuristics in scale-free networks, 13th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2010
, 10.1007/978-3-642-25920-3_12, 166-180, 2012.12, A Distributed Constraint Satisfaction Problem (DisCSP) is a constraint satisfaction problem in which variables and constraints are distributed among multiple agents. Various algorithms for solving DisC-SPs have been developed, which are intended for general purposes, i.e., they can be applied to any network structure. However, if a network has some particular structure, e.g., the network structure is scale-free, we can expect that some specialized algorithms or heuristics, which are tuned for the network structure, can outperform general purpose algorithms/heuristics. In this paper, as an initial step toward developing specialized algorithms for particular network structures, we examine variable-ordering heuristics in scale-free networks. We use the classic asynchronous backtracking algorithm as a baseline algorithm and examine the effect of variable-ordering heuristics. First, we show that the choice of variable-ordering heuristics is more influential in scale-free networks than in random networks. Furthermore, we develop a novel variable-ordering heuristic that is specialized to scale-free networks. Experimental results illustrate that our new variable-ordering heuristic is more effective than a standard degree-based variable-ordering heuristic. Our proposed heuristic reduces the required cycles by 30% at the critical point.. |
| 141. |
Yuko Sakurai, Makoto Yokoo, Generalized partition mechanism
Framework for combining multiple strategy-proof mechanisms, 2012 IEEE/WIC/ACM International Conference on Intelligent Agent Technology, IAT 2012
, 10.1109/WI-IAT.2012.256, 502-509, 2012.12, This paper presents a framework for combining multiple strategy-proof resource allocation mechanisms, in which participants are divided into several groups (partitions) and each mechanism is applied to one partition. The idea of dividing participants into several groups is introduced to achieve budget balance in a redistribution mechanism, i.e., the payment (money) collected in one partition is distributed in another partition. Furthermore, this idea has been used to adjust parameters of a mechanism (e.g., the reservation price in an auction) based on the information of participants in one partition in order to improve the mechanism's efficiency or revenue. This paper presents a unified framework called a generalized partition mechanism, in which information, money, and unsold goods can be transferred among partitions. This framework is very general and thus can be applied to various settings, including cases where a redistribution mechanism must adjust parameters to obtain a better social surplus. We provide a sufficient condition on the flow of information, money, and goods among partitions so that the generalized partition mechanism is strategy-proof, assuming that each mechanism applied to the partition is strategy-proof. We can use this sufficient condition as a guideline for combining multiple mechanisms. To show the applicability of this guideline, we develop new redistribution mechanisms based on this guideline, in which the utility of a participant can be non-quasi-linear.. |
| 142. |
Tenda Okimoto, Yongjoon Joe, Atsushi Iwasaki, Toshihiro Matsui, Katsutoshi Hirayama, Makoto Yokoo, Interactive algorithm for multi-objective constraint optimization, 18th International Conference on Principles and Practice of Constraint Programming, CP 2012
, 10.1007/978-3-642-33558-7_41, 561-576, 2012.11, Many real world problems involve multiple criteria that should be considered separately and optimized simultaneously. A Multi-Objective Constraint Optimization Problem (MO-COP) is the extension of a mono-objective Constraint Optimization Problem (COP). In a MO-COP, it is required to provide the most preferred solution for a user among many optimal solutions. In this paper, we develop a novel Interactive Algorithm for MO-COP (MO-IA). The characteristics of this algorithm are as follows: (i) it can guarantee to find a Pareto solution, (ii) it narrows a region, in which Pareto front may exist, gradually, (iii) it is based on a pseudo-tree, which is a widely used graph structure in COP algorithms, and (iv) the complexity of this algorithm is determined by the induced width of problem instances. In the evaluations, we use an existing model for representing a utility function, and show empirically the effectiveness of our algorithm. Furthermore, we propose an extension of MO-IA, which can provide the more detailed information for Pareto front.. |
| 143. |
Dong Hao, Xiaojuan Liao, Avishek Adhikari, Kouichi Sakurai, Makoto Yokoo, A repeated game approach for analyzing the collusion on selective forwarding in multihop wireless networks, Computer Communications, 10.1016/j.comcom.2012.07.006, 35, 17, 2125-2137, 2012.10, In multihop wireless networks (MWNs), the selective forwarding attack is a special case of denial of service attack. In this attack, the malicious wireless nodes only forward a subset of the received packets, but drop the others. This attack becomes more severe if multiple attackers exist and collude together to disrupt the normal functioning of the secure protocols. By colluding, each attacker can even only drop a little packets, but the overall loss of the path will be high. However, most prior researches on selective forwarding attacks assume the attackers do not collude with each other. Furthermore, the previous works also lack of comprehensive security analysis. In this paper, by utilizing the game theoretic approach, we analyze the collusion in selective forwarding attacks. We first put forward a sub-route oriented punish and reward scheme, and propose an multi-attacker repeated colluding game. Then by static and dynamic analysis of this colluding attack game, we find the sub-game equilibriums which indicate the attackers' optimal attack strategies. Based on the analysis result, we establish a security policies for multihop wireless networks, to threaten and detect the malicious insider nodes which collude with each other to launch the selective forwarding attacks.. |
| 144. |
Dong Hao, Xiaojuan Liao, Avishek Adhikari, Kouichi Sakurai, Makoto Yokoo, A repeated game approach for analyzing the collusion on selective forwarding in multihop wireless networks, Computer Communications, 10.1016/j.comcom.2012.07.006, 35, 17, 2125-2137, 2012.10, In multihop wireless networks (MWNs), the selective forwarding attack is a special case of denial of service attack. In this attack, the malicious wireless nodes only forward a subset of the received packets, but drop the others. This attack becomes more severe if multiple attackers exist and collude together to disrupt the normal functioning of the secure protocols. By colluding, each attacker can even only drop a little packets, but the overall loss of the path will be high. However, most prior researches on selective forwarding attacks assume the attackers do not collude with each other. Furthermore, the previous works also lack of comprehensive security analysis. In this paper, by utilizing the game theoretic approach, we analyze the collusion in selective forwarding attacks. We first put forward a sub-route oriented punish and reward scheme, and propose an multi-attacker repeated colluding game. Then by static and dynamic analysis of this colluding attack game, we find the sub-game equilibriums which indicate the attackers' optimal attack strategies. Based on the analysis result, we establish a security policies for multihop wireless networks, to threaten and detect the malicious insider nodes which collude with each other to launch the selective forwarding attacks.. |
| 145. |
BnB-ADOPT-p：分散制約最適化問題におけるハイブリッド型の解法の提案. |
| 146. |
Tenda Okimoto, Yongjoon Joe, Atsushi Iwasaki, Toshihiro Matsui, Katsutoshi Hirayama, Makoto Yokoo, Interactive Algorithm for Multi-objective Constraint Optimization, In Proceedings of the 18th International Conference on Principles and Practice of Constraint Programming (CP-2012), 10.1007/978-3-642-33558-7_41, 561-576, 2012.10. |
| 147. |
クラウドソーシングにおける品質コントロールの一考察. |
| 148. |
William Yeoh, Makoto Yokoo, Distributed problem solving, AI Magazine, 33, 3, 53-65, 2012.09, Broadly, distributed problem solving is a subfield within multiagent systems, where the focus is to enable multiple agents to work together to solve a problem. These agents are often assumed to be cooperative, that is, they are part of a team or they are self-interested but incentives or disincentives have been applied such that the individual agent rewards are aligned with the team reward. We illustrate the motivations for distributed problem solving with an example. Imagine a decentralized channel-allocation problem in a wireless local area network (WLAN), where each access point (agent) in the WLAN needs to allocate itself a channel to broadcast such that no two access points with overlapping broadcast regions (neighboring agents) are allocated the same channel to avoid interference. Figure 1 shows example mobile WLAN access points, where each access point is a Create robot fitted with a wireless CenGen radio card. Figure 2a shows an illustration of such a problem with three access points in a WLAN, where each oval ring represents the broadcast region of an access point.. |
| 149. |
Toshihiro Matsui, Marius Silaghi, Katsutoshi Hirayama, Makoto Yokoo, Hiroshi Matsuo, Distributed search method with bounded cost vectors on multiple objective DCOPs, 15th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2012
, 10.1007/978-3-642-32729-2_10, 7455 LNAI, 137-152, 2012.09, We generalize a pseudo-tree based solver to employ boundaries of multi-objective DCOPs. Multi-objective problems have been addressed in the research area of DCOPs recently. For the case of multiple objectives, the objective values are defined as the result of separate evaluation schemes. Applying multi-objectives to pseudo-tree based search is also important to generalize several traditional solvers. Here, we introduce boundaries for the vector of objective values in a solver based on pseudo-trees. Both the bottom-up computation of the partial dynamic-programming and the top-down computation of the tree-search employ the bounded vectors of the objective values. Several operations including aggregation, decomposition and comparison of objective values are extended for the bounded vectors.. |
| 150. |
多目的制約最適化問題：ユーザとの対話型解法の提案. |
| 151. |
Tenda Okimoto, Atsushi Iwasaki, Makoto Yokoo, Effect of DisCSP variable-ordering heuristics in scale-free networks, Multiagent and Grid Systems, 10.3233/MGS-2012-0189, 8, 2, 127-141, 2012.05, A Distributed Constraint Satisfaction Problem (DisCSP) is a constraint satisfaction problem in which variables and constraints are distributed among multiple agents. Various algorithms for solving DisCSPs have been developed, which are intended for general purposes, i.e., they can be applied to any network structure. However, if a network has some particular structure, e.g., the network structure is scale-free, we can expect that some specialized algorithms/heuristics, which are tuned for the network structure, can outperform general purpose algorithms/heuristics. In this paper, as an initial step toward developing specialized algorithms for particular network structures, we examine variable-ordering heuristics in scale-free networks. We use the classic asynchronous backtracking algorithm (ABT) as a baseline algorithm and examine the effect of variable-ordering heuristics. First, we show that the choice of variable-ordering heuristics is more influential in scale-free networks than in random networks. Furthermore, we develop a novel variable-ordering heuristic that is specialized to scale-free networks. In the evaluations, we show that our new variable-ordering heuristic is more effective than a standard degree-based variable-ordering heuristic. Our proposed heuristic reduces the required cycles by 30% at the critical point where the required cycles are maximum.. |
| 152. |
Tenda Okimoto, Atsushi Iwasaki, Makoto Yokoo, Effect of DisCSP Variable-Ordering Heuristics in Scale-free Networks, Multiagent and Grid Systems - An International Journal 8, 10.3233/MGS-2012-0189, 8, 2, 127-141, 2012.05. |
| 153. |
Introduction of Game Theory for Computer Scientists. |
| 154. |
Suguru Ueda, Makoto Kitaki, Atsushi Iwasaki, Makoto Yokoo, Concise characteristic function representations in coalitional games based on agent types, 22nd International Joint Conference on Artificial Intelligence, IJCAI 2011
, 10.5591/978-1-57735-516-8/IJCAI11-074, 393-399, 2011.12, Forming effective coalitions is a major research challenge in AI and multi-agent systems (MAS). Thus, coalitional games, including Coalition Structure Generation (CSG), have been attracting considerable attention from the AI research community. Traditionally, the input of a coalitional game is a black-box function called a characteristic function. A range of previous studies have found that many problems in coalitional games tend to be computationally intractable when the input is a black-box function. Recently, several concise representation schemes for a characteristic function have been proposed. Although these schemes are effective for reducing the representation size, most problems remain computationally intractable. In this paper, we develop a new concise representation scheme based on the idea of agent types. Intuitively, a type represents a set of agents, which are recognized as having the same contribution. This representation can be exponentially more concise than existing concise representation schemes. Furthermore, this idea can be used in conjunction with existing schemes to further reduce the representation size. Moreover, we show that most of the problems in coalitional games, including CSG, can be solved in polynomial time in the number of agents, assuming the number of possible types is fixed.. |
| 155. |
Taiki Todo, Runcong Li, Xuemei Hu, Takayuki Mouri, Atsushi Iwasaki, Makoto Yokoo, Generalizing envy-freeness toward group of agents, 22nd International Joint Conference on Artificial Intelligence, IJCAI 2011
, 10.5591/978-1-57735-516-8/IJCAI11-073, 386-392, 2011.12, Envy-freeness is a well-known fairness concept for analyzing mechanisms. Its traditional definition requires that no individual envies another individual. However, an individual (or a group of agents) may envy another group, even if she (or they) does not envy another individual. In mechanisms with monetary transfer, such as combinatorial auctions, considering such fairness requirements, which are refinements of traditional envy-freeness, is meaningful and brings up a new interesting research direction in mechanism design. In this paper, we introduce two new concepts of fairness called envy-freeness of an individual toward a group, and envy-freeness of a group toward a group . They are natural extensions of traditional envy-freeness. We discuss combinatorial auction mechanisms that satisfy these concepts. First, we characterize such mechanisms by focusing on their allocation rules. Then we clarify the connections between these concepts and three other properties: the core, strategy-proofness, and false-name-proofness.. |
| 156. |
Baba Satomi, Yongjoon Joe, Atsushi Iwasaki, Makoto Yokoo, Real-time solving of quantified CSPs based on Monte-Carlo game tree search, 22nd International Joint Conference on Artificial Intelligence, IJCAI 2011
, 10.5591/978-1-57735-516-8/IJCAI11-116, 655-661, 2011.12, We develop a real-time algorithm based on a Monte-Carlo game tree search for solving a quantified constraint satisfaction problem (QCSP), which is a CSP where some variables are universally quantified. A universally quantified variable represents a choice of nature or an adversary. The goal of a QCSP is to make a robust plan against an adversary. However, obtaining a complete plan off-line is intractable when the size of the problem becomes large. Thus, we need to develop a real-time algorithm that sequentially selects a promising value at each deadline. Such a problem has been considered in the field of game tree search. In a standard game tree search algorithm, developing a good static evaluation function is crucial. However, developing a good static evaluation function for a QCSP is very difficult since it must estimate the possibility that a partially assigned QCSP is solvable. Thus, we apply a Monte-Carlo game tree search technique called UCT. However, the simple application of the UCT algorithm does not work since the player and the adversary are asymmetric, i.e., finding a game sequence where the player wins is very rare. We overcome this difficulty by introducing constraint propagation techniques. We experimentally compare the winning probability of our UCT-based algorithm and the state-of-the-art alpha-beta search algorithm. Our results show that our algorithm outperforms the state-of-the-art algorithm in large-scale problems.. |
| 157. |
擬似木に基づく分散制約最適化問題の精度保証付き非厳密解法の提案. |
| 158. |
Yuko Sakurai, Suguru Ueda, Atsushi Iwasaki, Shin Ichi Minato, Makoto Yokoo, A compact representation scheme of coalitional games based on multi-terminal zero-suppressed binary decision diagrams, 14th International Conference on Principles and Practice of Multi-Agent Systems (PRIMA 2011), 10.1007/978-3-642-25044-6_4, 4-18, 2011.11, Coalitional games, including Coalition Structure Generation (CSG), have been attracting considerable attention from the AI research community. Traditionally, the input of a coalitional game is a black-box function called a characteristic function. Previous studies have found that many problems in coalitional games tend to be computationally intractable in this black-box function representation. Recently, several concise representation schemes for a characteristic function have been proposed. Among them, a synergy coalition group (SCG) has several good characteristics, but its representation size tends to be large compared to other representation schemes. We propose a new concise representation scheme for a characteristic function based on a Zero-suppressed Binary Decision Diagram (ZDD) and a SCG. We show our scheme (i) is fully expressive, (ii) can be exponentially more concise than the SCG representation, (iii) can solve core-related problems in polynomial time in the number of nodes, and (iv) can solve a CSG problem reasonably well by utilizing a MIP formulation. A Binary Decision Diagram (BDD) has been used as unified infrastructure for representing/manipulating discrete structures in such various domains in AI as data mining and knowledge discovery. Adapting this common infrastructure brings up the opportunity of utilizing abundant BDD resources and cross-fertilization with these fields.. |
| 159. |
分散制約充足問題：特定の制約網に特化した変数順序付けヒューリスティックの提案. |
| 160. |
Tenda Okimoto, Yongjoon Joe, Atsushi Iwasaki, Makoto Yokoo, Boi Faltings, Pseudo-tree-based incomplete algorithm for distributed constraint optimization with quality bounds, 17th International Conference on Principles and Practice of Constraint Programming, CP 2011
, 10.1007/978-3-642-23786-7_50, 660-674, 2011.09, A Distributed Constraint Optimization Problem (DCOP) is a fundamental problem that can formalize various applications related to multi-agent cooperation. Since it is NP-hard, considering faster incomplete algorithms is necessary for large-scale applications. Most incomplete algorithms generally do not provide any guarantees on the quality of solutions. Some notable exceptions are DALO, the bounded max-sum algorithm, and ADPOP. In this paper, we develop a new solution criterion called p-optimality and an incomplete algorithm for obtaining a p-optimal solution. The characteristics of this algorithm are as follows: (i) it can provide the upper bounds of the absolute/relative errors of the solution, which can be obtained a priori/a posteriori, respectively, (ii) it is based on a pseudo-tree, which is a widely used graph structure in complete DCOP algorithms, (iii) it is a one-shot type algorithm, which runs in polynomial-time in the number of agents n assuming p is fixed, and (iv) it has adjustable parameter p, so that agents can trade-off better solution quality against computational overhead. The evaluation results illustrate that this algorithm can obtain better quality solutions and bounds compared to existing bounded incomplete algorithms, while the run time of this algorithm is shorter.. |
| 161. |
Toshihiro Matsui, Marius Silaghi, Katsutoshi Hirayama, Makoto Yokoo, Boi Faltings, Hiroshi Matsuo, Reducing the search space of resource constrained DCOPs, 17th International Conference on Principles and Practice of Constraint Programming, CP 2011
, 10.1007/978-3-642-23786-7_44, 576-590, 2011.09, Distributed constraint optimization problems (DCOPs) have been studied as a basic framework of multi-agent cooperation. The Resource Constrained DCOP (RCDCOP) is a special DCOP framework that contains n-ary hard constraints for shared resources. In RCDCOPs, for a value of a variable, a certain amount of the resource is consumed. Upper limits on the total use of resources are defined by n-ary resource constraints. To solve RCDCOPs, exact algorithms based on pseudo-trees employ virtual variables whose values represent use of the resources. Although, virtual variables allow for solving the problems without increasing the depth of the pseudo-tree, they exponentially increase the size of search spaces. Here, we reduce the search space of RCDCOPs solved by a dynamic programming method. Several boundaries of resource use are exploitable to reduce the size of the tables. To employ the boundaries, additional pre-processing and further filtering are applied. As a result, infeasible solutions are removed from the tables. Moreover, multiple elements of the tables are aggregated into fewer elements. By these modifications, redundancy of the search space is removed. One of our techniques reduces the size of the messages by an order of magnitude.. |
| 162. |
Venkatesh Ramamoorthy, Marius C. Silaghi, Toshihiro Matsui, Katsutoshi Hirayama, Makoto Yokoo, The design of cryptographic S-boxes using CSPs, 17th International Conference on Principles and Practice of Constraint Programming, CP 2011
, 10.1007/978-3-642-23786-7_7, 54-68, 2011.09, We use the Constraint Satisfaction Problem (CSP) framework to model and solve the problem of designing substitution functions for substitution- permutation (SP) networks as proposed by Shannon for the architecture of ciphers. Many ciphers are designed using the SP pattern, and differ mainly by two parametrized functions: substitution and permutation. The most difficult of the two is the substitution function, which has to be nonlinear (a requirement that was difficult to define and quantify). Over time, researchers such as Nyberg, Pieprzyk and Matsui have proposed various metrics of nonlinearity that make the function robust to modern attacks. Before us, people have attempted various ways to design functions that respect these metrics. In the past people hand-picked substitution tables (S-boxes) by trying various values. Recently they use difficult to analyze constructs (such as Bent functions, spectral inversion, inverses in Galois fields) whose outputs are tested for nonlinearity. While efficient, such techniques are neither exhaustive (optimal), nor did they manage to generate better substitutions than the ones hand-picked in the past. We show that Matsui's nonlinearity requirement can be naturally modelled using CSPs. Based on a combination of existing CSP techniques and some new filtering operators that we designed specially for the new types of constraints, we manage to obtain better S-boxes than any previously published ones. The simplicity of the CSP framework and availability of general CSP solvers like ours, makes it easy for more people to design their own ciphers with easy to understand security parameters. Here we report on this new application of CSPs.. |
| 163. |
Tenda Okimoto, Yongjoon Joe, Atsushi Iwasaki, Makoto Yokoo, Boi Faltings, Pseudo-tree-based Incomplete Algorithm for Distributed Constraint Optimization with Quality Bounds, In Proceedings of the 17th International Conference on Principles and Practice of Constraint Programming (CP-2011), 10.1007/978-3-642-23786-7_50, 660-674, 2011.09. |
| 164. |
•Toshihiro Matsui, Marius Silaghi, Katsutoshi Hirayama, Makoto Yokoo, Boi Faltings, Hiroshi Matsuo, Reducing the Search Space of Resource Constrained DCOPs, 17th International Conference on Principles and Practice of Constraint Programming (CP-2011), 10.1007/978-3-642-23786-7_44, 576-590, 2011.09. |
| 165. |
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, 10.1142/S0219525911003104, 14, 3, 471-528, 2011.06, A significant body of work exists on effectively allowing multiple agents to coordinate to achieve a shared goal. In particular, a growing body of work in the Distributed Constraint Optimization (DCOP) framework enables such coordination with different amounts of teamwork. Such algorithms can implicitly or explicitly trade-off improved solution quality with increased communication and computation requirements. However, the DCOP framework is limited to planning problems; DCOP agents must have complete and accurate knowledge about the reward function at plan time. We extend the DCOP framework, defining the Distributed Coordination of Exploration and Exploitation (DCEE) problem class to address real-world problems, such as ad-hoc wireless network optimization, via multiple novel algorithms. DCEE algorithms differ from DCOP algorithms in that they (1) are limited to a finite number of actions in a single trial, (2) attempt to maximize the on-line, rather than final, reward, (3) are unable to exhaustively explore all possible actions, and (4) may have knowledge about the distribution of rewards in the environment, but not the rewards themselves. Thus, a DCEE problem is not a type of planning problem, as DCEE algorithms must carefully balance and coordinate multiple agents' exploration and exploitation. Two classes of algorithms are introduced: static estimation algorithms perform simple calculations that allow agents to either stay or explore, and balanced exploration algorithms use knowledge about the distribution of the rewards and the time remaining in an experiment to decide whether to stay, explore, or (in some algorithms) backtrack to a previous location. These two classes of DCEE algorithms are compared in simulation and on physical robots in a complex mobile ad-hoc wireless network setting. Contrary to our expectations, we found that increasing teamwork in DCEE algorithms may lower team performance. In contrast, agents running DCOP algorithms improve their reward as teamwork increases. We term this previously unknown phenomenon the team uncertainty penalty, analyze it in both simulation and on robots, and present techniques to ameliorate the penalty.. |
| 166. |
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, 10.1142/S0219525911003104, 14, 3, 471-528, 2011.06, A significant body of work exists on effectively allowing multiple agents to coordinate to achieve a shared goal. In particular, a growing body of work in the Distributed Constraint Optimization (DCOP) framework enables such coordination with different amounts of teamwork. Such algorithms can implicitly or explicitly trade-off improved solution quality with increased communication and computation requirements. However, the DCOP framework is limited to planning problems
DCOP agents must have complete and accurate knowledge about the reward function at plan time. We extend the DCOP framework, defining the Distributed Coordination of Exploration and Exploitation (DCEE) problem class to address real-world problems, such as ad-hoc wireless network optimization, via multiple novel algorithms. DCEE algorithms differ from DCOP algorithms in that they (1) are limited to a finite number of actions in a single trial, (2) attempt to maximize the on-line, rather than final, reward, (3) are unable to exhaustively explore all possible actions, and (4) may have knowledge about the distribution of rewards in the environment, but not the rewards themselves. Thus, a DCEE problem is not a type of planning problem, as DCEE algorithms must carefully balance and coordinate multiple agents' exploration and exploitation. Two classes of algorithms are introduced: static estimation algorithms perform simple calculations that allow agents to either stay or explore, and balanced exploration algorithms use knowledge about the distribution of the rewards and the time remaining in an experiment to decide whether to stay, explore, or (in some algorithms) backtrack to a previous location. These two classes of DCEE algorithms are compared in simulation and on physical robots in a complex mobile ad-hoc wireless network setting. Contrary to our expectations, we found that increasing teamwork in DCEE algorithms may lower team performance. In contrast, agents running DCOP algorithms improve their reward as teamwork increases. We term this previously unknown phenomenon the team uncertainty penalty, analyze it in both simulation and on robots, and present techniques to ameliorate the penalty. © 2011 World Scientific Publishing Company.. |
| 167. |
Ohta Naoki, Conitzer Vincent, Ichimura Ryo, Sakurai Yuko, Iwasaki Atsushi, Yokoo Makoto, Coalition structure generation utilizing compact characteristic function representations, Transactions of the Japanese Society for Artificial Intelligence, 10.1527/tjsai.26.451, 26, 3, 451-460, 2011.05, This paper presents a new way of formalizing the Coalition Structure Generation problem (CSG), so that we can apply constraint optimization techniques to it. Forming effective coalitions is a major research challenge in AI and multi-agent systems. CSG involves partitioning a set of agents into coalitions so that social surplus is maximized. Traditionally, the input of the CSG problem is a black-box function called a characteristic function, which takes a coalition as an input and returns the value of the coalition. As a result, applying constraint optimization techniques to this problem has been infeasible. However, characteristic functions that appear in practice often can be represented concisely by a set of rules, rather than a single black-box function. Then, we can solve the CSG problem more efficiently by applying constraint optimization techniques to the compact representation directly. We present new formalizations of the CSG problem by utilizing recently developed compact representation schemes for characteristic functions. We first characterize the complexity of the CSG under these representation schemes. In this context, the complexity is driven more by the number of rules rather than by the number of agents. Furthermore, as an initial step towards developing efficient constraint optimization algorithms for solving the CSG problem, we develop mixed integer programming formulations and show that an off-the-shelf optimization package can perform reasonably well, i.e., it can solve instances with a few hundred agents, while the state-of-the-art algorithm (which does not make use of compact representations) can solve instances with up to 27 agents.. |
| 168. |
Tenda Okimoto, Yongjoon Joe, Atsushi Iwasaki, Makoto Yokoo, Pseudo-tree-based Incomplete Algorithm for Distributed Constraint Optimization with Quality Bounds, The 4th International Workshop on Optimisation in Multi-agent Systems (OPTMAS 2011) (held in conjunction with AAMAS 2011), 52-67, 2011.05. |
| 169. |
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. |
| 170. |
Tenda Okimoto, Atsushi Iwasaki, Makoto Yokoo, Effect of DisCSP Variable-Ordering Heuristics in Scale-free Networks, In proceedings of the 13th International Conference on Principles and Practice of Multi-Agent Systems (PRIMA-2010), 10.1007/978-3-642-25920-3_12, 168-180, 2010.11. |
| 171. |
Toshihiro MATSUI, Marius C. Silaghi, Katsutoshi HIRAYAMA, Makoto YOKOO, Hiroshi MATSUO, Satomi BABA, A Quantified Distributed Constraint Optimization Problems, Proc. 9th Int'l. Conf. on Autonomous Agents and Multiagent Systems (AAMAS2010), 1023-1030, 2010.05. |
| 172. |
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. |
| 173. |
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. |
| 174. |
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. |
| 175. |
Applying Soft Arc Consistency to Distributed Constraint Optimization Problems. |
| 176. |
Marius C. Silaghi, Makoto Yokoo, ADOPT-ing: Unifying asynchronous distributed optimization with asynchronous backtracking, Autonomous Agents and Multi-Agent Systems, 10.1007/s10458-008-9069-2, 19, 2, 89-123, 2009.10, This article presents an asynchronous algorithm for solving distributed constraint optimization problems (DCOPs). The proposed technique unifies asynchronous backtracking (ABT) and asynchronous distributed optimization (ADOPT) where valued nogoods enable more flexible reasoning and more opportunities for communication, leading to an important speed-up. While feedback can be sent in ADOPT by COST messages only to one predefined predecessor, our extension allows for sending such information to any relevant agent. The concept of valued nogood is an extension by Dago and Verfaille of the concept of classic nogood that associates the list of conflicting assignments with a cost and, optionally, with a set of references to culprit constraints. DCOPs have been shown to have very elegant distributed solutions, such as ADOPT, distributed asynchronous overlay (DisAO), or DPOP. These algorithms are typically tuned to minimize the longest causal chain of messages as a measure of how the algorithms will scale for systems with remote agents (with large latency in communication). ADOPT has the property of maintaining the initial distribution of the problem. To be efficient, ADOPT needs a preprocessing step consisting of computing a Depth-First Search (DFS) tree on the constraint graph. Valued nogoods allow for automatically detecting and exploiting the best DFS tree compatible with the current ordering. To exploit such DFS trees it is now sufficient to ensure that they exist. Also, the inference rules available for valued nogoods help to exploit schemes of communication where more feedback is sent to higher priority agents. Together they result in an order of magnitude improvement. © 2008 Springer Science+Business Media, LLC.. |
| 177. |
A Resource Constrained Distributed Constraint Optimization Method using Resource Constraint Free Psudo-tree. |
| 178. |
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. |
| 179. |
Toshihiro Matsui, Marius Silaghi, Katsutoshi Hirayama, Makoto Yokoo, Hiroshi Matsuo, Directed Soft Arc Consistency in Pseudo-trees, Proc. 8th Intl. Conf. on Autonomous Agents and Multiagent Systems (AAMAS2009), 1, 1, 120-125, 2009.03. |
| 180. |
Marius C. Silaghi, Makoto Yokoo, ADOPT-ing: unifying asynchronous distributed optimization
with asynchronous backtracking, Journal of Autonomous Agents and Multi-Agent Systems, 2008.11. |
| 181. |
Toshihiro Matsui, Marius Silaghi, Katsutoshi Hirayama, Makoto Yokoo, Hiroshi Matsuo, Resource constrained distributed constraint optimization with virtual variables, Twenty-Third AAAI Conference on Artificial Intelligence (AAAI-08), 1, 1, 120-125, 2008.07. |
| 182. |
Toshihiro Matsui, Marius Silaghi, Katsutoshi Hirayama, Makoto Yokoo, Hiroshi Matsuo, Resource constrained distributed constraint optimization using resource constraint free pseudo-tree, The Seventh International Conference on Autonomous Agents and Multi-agent Systems (AAMAS2008), 1, 1, 1405-1408, 2008.05. |
| 183. |
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. |
| 184. |
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. |
| 185. |
Hiromitsu Hattori, Makoto Yokoo, Yuko Sakurai, Toramatsu Shintani, Determining bidding strategies in sequential auctions: Quasi-linear utility and budget constraints, Systems and Computers in Japan, 10.1002/scj.10465, 38, 8, 72-83, 2007.07, A great deal of research is actively being conducted concerning Internet auctions. A method has previously been proposed for obtaining the optimal bidding strategy by using dynamic programming in a sequential auction, which is one form of auction. However, the conventional method assumes that the utility of an agent who is bidding takes a general additive form, and the remaining endowment of money during bidding has to be represented in each of the various states that are taken into consideration in the dynamic programming procedure. As a result, when the initial endowment of money m is large, the number of states that have to be taken into consideration becomes extremely large. In this paper, by assuming that the utility of an agent takes a quasi-linear form, which is a type of additive form, the authors show that the optimal strategy using dynamic programming is obtained since the number of states is reduced to 1/m times the number obtained when the utility takes a general additive form. However, when the agent utility is assumed to take a quasi-linear form, it is impossible to represent budget constraints. Therefore, in this paper, the authors propose a method of quickly obtaining a quasi-optimal strategy when budget constraints exist by modifying the strategy that is obtained when quasi-linear utility is assumed and show the effectiveness of the proposed method through experimental evaluations. © 2007 Wiley Periodicals, Inc.. |
| 186. |
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. |
| 187. |
Kenji Terada, Makoto Yokoo, False-name-proof multi-unit auction protocol utilizing greedy allocation based on approximate evaluation values, Systems and Computers in Japan, 10.1002/scj.10664, 37, 13, 89-98, 2006.11, This paper presents a new false-name-proof multiunit auction protocol called the Greedy ALlocation (GAL) protocol. Internet auctions have become an integral part of Electronic Commerce and a promising field for applying agent and Artificial Intelligence technologies. Although the Internet provides an excellent infrastructure for executing auctions, the possibility of a new type of cheating called false-name bids has been pointed out. A false-name bid is a bid submitted under a fictitious name. A protocol called the Iterative Reducing (IR) protocol has been developed for multi-unit auctions and has proven to be false-name-proof, that is, using false-name bids is useless. For Internet auction protocols, being false-name-proof is important since identifying each participant on the Internet is virtually impossible. One shortcoming of the IR protocol is that it requires the auctioneer to carefully predetermine the reservation price for one unit. Our newly developed GAL protocol is easier to use than the IR, since the auctioneer does not need to set the reservation price nor any other parameters. The evaluation results show that the GAL protocol can obtain a social surplus that is very close to Pareto efficient. Furthermore, the obtained social surplus and seller's revenue are much better than those of the IR protocol even if the reservation price is set optimally. © 2006 Wiley Periodicals, Inc.. |
| 188. |
Takayuki It, Makoto Yokoo, Shigeo Matsubara, Atsushi Iwasaki, Implementing A Strategyproof Greedy-Allocation Combinatorial Auction and Extending to Ascending Auction, Systems and Computers in Japan(John Wiley & Sons, Inc.), 10.1002/scj.20748, 38, 9, 44-51, 2006.01. |
| 189. |
Takayuki Ito, Makoto Yokoo, Shigeo Matsubara, A combinatorial auction among experts and amateurs: The case of single-skilled experts, Systems and Computers in Japan, 10.1002/scj.20390, 36, 12, 11-21, 2005.11, Auctions have recently commanded a great deal of attention in the field of multiagent systems. Correctly judging the quality of auctioned goods is often difficult for amateurs, in particular, on the Internet auctions. We have formalized such a situation so that Nature selects the quality of the auctioned good. Experts can observe Nature's selection (i.e., the quality of the good) correctly, while amateurs, including the auctioneer, cannot. In other words, the information on Nature's selection is asymmetric between experts and amateurs. In this situation, it is difficult to attain an efficient allocation, since experts have a clear advantage over amateurs, and they would not reveal their valuable information without some reward. We have succeeded in developing a single-unit auction protocol in which truth-telling is a dominant strategy for each expert. In this paper, we focus on a combinatorial auction protocol under asymmetric information on Nature's selection. Experts may have an interest in, and expert knowledge on, Nature's selection for several goods, that is, experts are versatile. However, the case of versatile experts is very complicated. Thus, as a first step, we assume experts to have an interest in, and expert knowledge on, a single good. That is, experts are single-skilled. Under these assumptions, we develop an auction protocol in which the dominant strategy for experts is truth-telling. Also, for amateurs, truth-telling is the best response when experts tell the truth. By making experts to elicit their information on the quality of the goods, the protocol can achieve a socially desirable, (i.e., Pareto efficient) allocation, if certain assumptions are satisfied. © 2005 Wiley Periodicals, Inc.. |
| 190. |
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. |
| 191. |
Makoto Yokoo, Yuko Sakurai, Shigeo Matsubara, A double auction protocol robust to false-name bids, Electronics and Communications in Japan, Part II: Electronics (English translation of Denshi Tsushin Gakkai Ronbunshi), 10.1002/ecjb.20180, 88, 5, 50-59, 2005.05, The auction is a fast-developing, important area of electronic commerce in which software agent techniques are expected to find promising applications. By the use of the Internet, large-scale auctions can be realized at low cost. On the other hand, there arises the problem of illegal conduct of a new type, utilizing the name-concealment properties of the network. This paper proposes a new double auction protocol guaranteeing robustness to false-name bids, which constitute one type of such illegal conduct. The double auction is an auction in which multiple buyers/sellers exist and engage in bidding. It is widely used in dealing with foreign currency, credit, stocks, and other goods. For cases in which there is no false-name bid, the double auction protocol (PMD protocol) has been proposed, which is motivation-compatible in the dominant strategy. Considering the possible case in which the seller pretends to be a buyer and bids under another name, it is possible in the PMD protocol for the bidder to increase his benefit by a false-name bid. Thus, motivation compatibility is not guaranteed. This paper proposes the threshold price double auction protocol (TPD), which is motivation-compatible in the dominant strategy even if false-name bids are possible. The TPD protocol has the feature that the number of deals and the prices of deals are controlled by using the threshold price of the good. It is shown by simulation experiments that the TPD protocol realizes a social surplus which is very close to the Pareto-efficient assignment by appropriately setting the threshold price. © 2005 Wiley Periodicals, Inc.. |
| 192. |
Makoto Yokoo, Yuko Sakurai, Shigeo Matsubara, Robust double auction protocol against false-name bids, Decision Support Systems, 10.1016/j.dss.2003.10.009, 39, 2, 241-252, 2005.04, In this paper, we develop a new double auction protocol called the Threshold Price Double auction (TPD) protocol, which is dominant-strategy incentive compatible even if participants can submit several bids under fictitious names (false-name bids). In Internet auctions, false-name bids are very difficult to detect since identifying each participant on the Internet is virtually impossible. The characteristics of the TPD protocol are that the number of trades and prices of exchange are controlled by the threshold price. Simulation results show that this protocol can achieve a social surplus that is very close to being Pareto efficient. © 2003 Elsevier B.V. All rights reserved.. |
| 193. |
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. |
| 194. |
Atsushi Iwasaki, Makoto Yokoo, Kenji Terada, A robust open ascending-price multi-unit auction protocol against false-name bids, Decision Support Systems, 10.1016/j.dss.2004.08.005, 39, 1, 23-39, 2005.03, This paper develops a new ascending-price multi-unit auction protocol that has the following characteristics: (i) it has an open format, and (ii) sincere bidding is an equilibrium strategy even if the marginal values of each agent can increase and agents can submit false-name bids. False-name bids are bids submitted under fictitious names such as multiple e-mail addresses, which can be done easily on the Internet. This is the first protocol that has both of these characteristics. Our simulation results indicate that the developed protocol obtains a social surplus close to Pareto efficient. © 2004 Elsevier B.V. All rights reserved.. |
| 195. |
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. |
| 196. |
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. |
| 197. |
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. |
| 198. |
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. |
| 199. |
Pragnesh Jay Modi, Wei-Min Shen, Milind Tambe, Makoto Yokoo, Adopt: Asynchronous distributed constraint optimization with quality guarantees, Artificial Intelligence, 10.1016/j.artint.2004.09.003, 161, 1-2, 149-180, 2005.01, The Distributed Constraint Optimization Problem (DCOP) is a promising approach for modeling distributed reasoning tasks that arise in multiagent systems. Unfortunately, existing methods for DCOP are not able to provide theoretical guarantees on global solution quality while allowing agents to operate asynchronously. We show how this failure can be remedied by allowing agents to make local decisions based on conservative cost estimates rather than relying on global certainty as previous approaches have done. This novel approach results in a polynomial-space algorithm for DCOP named Adopt that is guaranteed to find the globally optimal solution while allowing agents to execute asynchronously and in parallel. Detailed experimental results show that on benchmark problems Adopt obtains speedups of several orders of magnitude over other approaches. Adopt can also perform bounded-error approximation - it has the ability to quickly find approximate solutions and, unlike heuristic search methods, still maintain a theoretical guarantee on solution quality. © 2004 Elsevier B.V. All rights reserved.. |
| 200. |
Katsutoshi Hirayama, Makoto Yokoo, The distributed breakout algorithms, Artificial Intelligence, 10.1016/j.artint.2004.08.004, 161, 1-2, 89-115, 2005.01, We present a new series of distributed constraint satisfaction algorithms, the distributed breakout algorithms, which is inspired by local search algorithms for solving the constraint satisfaction problem (CSP). The basic idea of these algorithms is for agents to repeatedly improve their tentative and flawed sets of assignments for variables simultaneously while communicating such tentative sets with each other until finding a solution to an instance of the distributed constraint satisfaction problem (DisCSP). We introduce four implementations of the distributed breakout algorithms: SINGLE-DB, MULTI-DB, MULTI-DB+, and MULTI-DB++. SiNGLE-DB is a distributed breakout algorithm for solving the DisCSP, where each agent has a single local variable and its related constraints. MULTI-DB, on the other hand, is another distributed breakout algorithm for solving the distributed SAT (DisSAT) problem, where each agent has multiple local variables and their related clauses. MULTI-DB+ and MULTI-DB++ are stochastic variations of MULTI-DB. In MULTI-DB+, we introduce a technique called random break into MULTI-DB
in MULTI-DB++, we introduce a technique called random walk into MULTI-DB+. We conducted experiments to compare these algorithms with the asynchronous type of distributed constraint satisfaction algorithm. Through these experiments, we found that SINGLE-DB, MULTI-DB, and MULTI-DB+ scale up better than the asynchronous type of distributed constraint satisfaction algorithms, but they sometimes show very poor performance. On the other hand, we also found that MULTI-DB++, which uses random walk, provides a clear performance improvement. © 2004 Elsevier B.V. All rights reserved.. |
| 201. |
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. |
| 202. |
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. |
| 203. |
William E. Walsh, Makoto Yokoo, Katsutoshi Hirayama, Michael P. Wellman, On market-inspired approaches to propositional satisfiability, Artificial Intelligence, 10.1016/S0004-3702(02)00386-7, 144, 1-2, 125-156, 2003.03, We describe three market-inspired approaches to propositional satisfiability. The first is based on a formulation of satisfiability as production on a supply chain, where producers of particular variable assignments must acquire licenses to fail to satisfy particular clauses. Experiments show that although this general supply-chain protocol can converge to market allocations corresponding to satisfiable truth assignments, it is impractically slow. We find that a simplified market structure and a variation on the pricing method can improve performance significantly. We compare the performance of the three market-based protocols with distributed breakout algorithm and GSAT on benchmark 3-SAT problems. We identify a tradeoff between performance and economic realism in the market protocols, and a tradeoff between performance and the degree of decentralization between the market protocols and distributed breakout. We also conduct informal and experimental analyses to gain insight into the operation of price-guided search. © 2002 Elsevier Science B.V. All rights reserved.. |
| 204. |
Takayuki Suyama, Makoto Yokoo, Hiroshi Sawada, Akira Nagoya, Solving satisfiability problems by using reconfigurable hardware, Electronics and Communications in Japan, Part II: Electronics (English translation of Denshi Tsushin Gakkai Ronbunshi), 10.1002/ecjb.10134, 86, 3, 35-46, 2003.03, In this paper, we will propose a new solution method for SAT (Satisfiability Problems) using FPGA (Field-Programmable Gate Arrays) and logic synthesis system. This method is distinctive in that a logic circuit specialized to solve each problem instance is configured on FPGA. This approach has become possible due to the progress in reconfigurable computing technology in recent years and opens a new possibility in design principle of algorithms: SAT is a kind of constraint satisfaction problem and is a general framework which can represent many application problems. In this paper, we will propose various algorithms which are suitable for implementation on hardware. Among these algorithms, the one which has the highest performance has a performance equal to the Davis-Putman algorithm which introduced the heuristic with dynamic ordering of variables. From the evaluation results using simulation, we show that by the method proposed herein, the solution of a 3-SAT problem instance with 400 variables generated in a very hard random can be obtained in 1.6 minutes when the circuit is operated at a machine cycle of 10 MHz. Moreover, a very hard problem instance with 128 variables and 256 clauses was packaged on FPGAs and its operation was confirmed.. |
| 205. |
"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). |
| 206. |
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. |
| 207. |
"An Average-case Budget-Non-Negative Double Auction Protocol'', Yuko Sakurai and Makoto Yokoo, Journal of Japanese Society for Artificial Intelligence. |
| 208. |
"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). |
| 209. |
Shigeo Matsubara, Makoto Yokoo, Believing others: Pros and cons, Artificial Intelligence, 10.1016/S0004-3702(02)00289-8, 142, 2, 179-203, 2002.12, In open environments there is no central control over agent behaviors. On the contrary, agents in such systems can be assumed to be primarily driven by self interests. Under the assumption that agents remain in the system for significant time periods, or that the agent composition changes only slowly, we have previously presented a prescriptive strategy for promoting and sustaining cooperation among self-interested agents. The adaptive, probabilistic policy we have prescribed promotes reciprocative cooperation that improves both individual and group performance in the long run. In the short run, however, selfish agents could still exploit reciprocative agents. In this paper, we evaluate the hypothesis that the exploitative tendencies of selfish agents can be effectively curbed if reciprocative agents share their "opinions" of other agents. Since the true nature of agents is not known a priori and is learned from experience, believing others can also pose its own hazards. We provide a learned trust-based evaluation function that is shown to resist both individual and concerted deception on the part of selfish agents in a package delivery domain. © 2002 Elsevier Science B.V. All rights reserved.. |
| 210. |
Shigeo Matsubara, Makoto Yokoo, Hideyuki Nakashima, Milind Tambe, Defection-free exchange mechanisms based on an entry fee imposition, Artificial Intelligence, 10.1016/S0004-3702(02)00276-X, 142, 2, 265-286, 2002.12, We propose a safe exchange mechanism involving indivisible goods and divisible goods. A typical situation is an exchange involving goods and money in a person-to-person trade in an Internet auction. Although the Internet and agent technologies have facilitated world-wide trade, we sometimes encounter risky situations, such as fraud, in the process of exchanges involving goods and money. This problem is becoming more serious with the growing popularity of person-to-person trade. One of the reasons why fraud is becoming widespread is that obtaining a new identifier in a network is cheap. This makes it almost impossible to exclude malicious agents from trade. One solution is to impose an entry fee. However, if the entry fee is too high, it will discourage newcomers from starting deals. To resolve the conflict between safety and convenience, we developed three exchange mechanisms that can guarantee against defection from a contract. Two of them reduce the entry fee by integrating multiple deals and controlling the flow of goods and money. The other reduces the entry fee by incorporating a third-party agent into the exchange process. We examine the lower bound of the entry fee for both of these mechanisms and describe a calculation method by which this value can be obtained in linear time. Our results show that the described mechanism can effectively reduce the lower bound of the entry fee. © 2002 Elsevier Science B.V. All rights reserved.. |
| 211. |
Shigeo Matsubara, Makoto Yokoo, Defection-Free Exchange Mechanisms based on an Entry Fee Imposition, Artificial Intelligence Journal, Vol. 142, pp. 265-286, 2002.01. |
| 212. |
"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. |
| 213. |
"Robust Combinatorial Auction Protocol against False-name Bids'', Makoto Yokoo, Yuko Sakurai, and Shigeo Matsubara, Transactions of Information Society of Japan. |
| 214. |
"Robust Multi-unit Auction Protocol against False-name Bids'', Makoto Yokoo, Yuko Sakurai, and Shigeo Matsubara, Journal of Japanese Society for Artificial Intelligence. |
| 215. |
Makoto Yokoo, Yuko Sakurai, Shigeo Matsubara, Robust combinatorial auction protocol against false-name bids, Artificial Intelligence, 10.1016/S0004-3702(01)00077-7, 130, 2, 167-181, 2001.08, This paper presents a new combinatorial auction protocol that is robust against false-name bids. Internet auctions have become an integral part of Electronic Commerce (EC) and a promising field for applying agent and Artificial Intelligence technologies. Although the Internet provides an excellent infrastructure for combinatorial auctions, we must consider the possibility of a new type of cheating, i.e., an agent tries to profit from submitting several bids under fictitious names (false-name bids). If there exists no false-name bid, the Generalized Vickrey Auction protocol (GVA) satisfies individual rationality, Pareto efficiency, and incentive compatibility. On the other hand, when false-name bids are possible, it is theoretically impossible for a combinatorial auction protocol to simultaneously satisfy these three properties. Our newly developed Leveled Division Set (LDS) protocol, which is a modification of the GVA, utilizes reservation prices of auctioned goods for making decisions on whether to sell goods in a bundle or separately. The LDS protocol satisfies individual rationality and incentive compatibility even if agents can submit false-name bids, although it is not guaranteed to achieve a Pareto efficient social surplus. Simulation results show that the LDS protocol can achieve a better social surplus than that for a protocol that always sells goods in one bundle. © 2001 Elsevier Science B.V. All rights reserved.. |
| 216. |
Takayuki Suyama, Makoto Yokoo, Hiroshi Sawada, Akira Nagoya, Solving satisfiability problems using reconfigurable computing, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 10.1109/92.920826, 9, 1, 109-116, 2001.02, This paper reports on an innovative approach for solving satisfiability problems for propositional formulas in conjunctive normal form (SAT) by creating a logic circuit that is specialized to solve each problem instance on field programmable gate arrays (FPGAs). This approach has become feasible due to recent advances in reconfigurable computing and has opened up an exciting new research field in algorithm design. SAT is an important subclass of constraint satisfaction problems, which can formalize a wide range of application problems. We have developed a series of algorithms that are suitable for logic circuit implementation, including an algorithm whose performance is equivalent to the Davis-Putnam procedure with powerful dynamic variable ordering. Simulation results show that this method can solve a hard random 3-SAT problem with 400 variables within 1.6 min at a clock rate of 10 MHz. Faster speeds can be obtained by increasing the clock rate. Furthermore, we have actually implemented a 128-variable 256-clause problem instance on FPGAs.. |
| 217. |
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. |
| 218. |
"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. |
| 219. |
"An Efficient Approximate Algorithm for Winner Determination in Combinatorial Auctions'', Yuko Sakurai, Makoto Yokoo, and Kouji Kamei, Journal of Japanese Society for Artificial Intelligence. |
| 220. |
"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. |
| 221. |
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. |
| 222. |
The Effect of False-name Declarations in Mechanism Design : Towards Collective Decision Making on the Internet.. |
| 223. |
"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). |
| 224. |
"Defection-Free Exchange Mecahnisms for Information Good'', Shigeo Matsubara and Makoto Yokoo, Journal of Japanese Society for Artificial Intelligence. |
| 225. |
"Frequency Assignment for Cellular Mobile Systems Using Constraint Satisfaction Techniques'', Makoto Yokoo and Katsutoshi Hirayama, Transactions of Information Society of Japan. |
| 226. |
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. |
| 227. |
"Distributed Constraint Satisfaction Algorithms for Complex Local Problems'', Mkoto Yokoo and Katsutoshi Hirayama, Journal of Japanese Society for Artificial Intelligence. |
| 228. |
A Limitation of the Generalized Vickrey Auction in Electonic Commerce : Robustness against Falsename Bids. |
| 229. |
"The Effect of Nogood Learning in Distributed Constraint Satisfaction'', Katsutoshi Hirayama and Makoto Yokoo, Journal of Japanese Society for Artificial Intelligence. |
| 230. |
"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). |
| 231. |
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. |
| 232. |
"Multi-State Commitment Search'', Yasuhiko Kitamura, Makoto Yokoo, Tomohisa Miyaji, and Shoji Tatsumi, Journal of Japanese Society for Artificial Intelligence. |
| 233. |
"Distributed Partial Constraint Satisfaction Problem'', Katsutoshi Hirayama and Makoto Yokoo, Journal of Japanese Society for Artificial Intelligence. |
| 234. |
"Analyzing Landscapes of CPSs'', Makoto Yokoo, Computer Software (Journal of Japanese Society for Software Science and Technology). |
| 235. |
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. |
| 236. |
"Distributed Breakout Algorithm for Solving Distributed Constraint Satisfaction Problems'', Makoto Yokoo and Katsutoshi Hirayama, Transactions of Information Society of Japan. |
