Abstract How to form effective coalitions is an important issue in multi-agent systems. Coalition Structure Generation ( $${{\mathsf {CSG}}}$$ CSG ) is a fundamental problem whose formalization can encompass various applications related to multi-agent cooperation. $${{\mathsf {CSG}}}$$ CSG involves partitioning a set of agents into coalitions such that the social surplus (i.e., the sum of the values of all coalitions) is maximized. In traditional $${\mathsf {CSG}}$$ CSG , we are guaranteed that all coalitions will be successfully established, that is, the attendance rate of each agent for joining any coalition is assumed to be 1.0. Having the real world in mind, however, it is natural to consider the uncertainty of agents’ availabilities, e.g., an agent might be available only two or three days a week because of his/her own schedule. Probabilistic Coalition Structure Generation ( $${{\mathsf {PCSG}}}$$ PCSG ) is an extension of $${\mathsf {CSG}}$$ CSG where the attendance type of each agent is considered. The aim of this problem is to find the optimal coalition structure which maximizes the sum of the expected values of all coalitions. In $${\mathsf {PCSG}}$$ PCSG , since finding the optimal coalition structure easily becomes intractable, it is important to consider approximation algorithms, i.e., to consider a trade-off between the quality of the returned solution and tractability. In this paper, a formal framework for $${\mathsf {PCSG}}$$ PCSG is introduced. Approximation algorithms for $${\mathsf {PCSG}}$$ PCSG called Bounded Approximation Algorithm based on Attendance Types ( $${{\mathsf {BAAAT}}}$$ BAAAT ) and Involved $${\mathsf {BAAAT}}$$ BAAAT ( $${{\mathsf {IBAAAT}}}$$ IBAAAT ) are then presented. We prove a priori bounds on the quality of the solution returned by $${\mathsf {BAAAT}}$$ BAAAT and $${\mathsf {IBAAAT}}$$ IBAAAT with respect to the optimum and perform experimental evaluations on a number of benchmarks.

Distributed Constraint Optimization Problem (DCOP) has been studied as a fundamental component of multiagent systems. With DCOPs, various applications on multiagent systems are formalized as constraint optimization problems where variables and functions are distributed among agents. Leximin AMODCOP has been proposed as a class of Multiple Objective DCOPs, where multiple objectives for individual agents are optimized based on the leximin operator. This problem also relates to Asymmetric DCOPs based on its the criteria of fairness among agents. 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 approximate/inexact algorithms.

A Constraint Satisfaction Problem (CSP) is a fundamental problem that can formalize various applications related to Artificial Intelligence problems. A Weighted Constraint Satisfaction Problem (WCSP) is a CSP where constraints can be violated, and the aim of this problem is to find an assignment that minimizes the sum of weights of the violated constraints. Most researches have focused on developing algorithms for solv- ing static mono-objective problems. However, many real world satisfaction/optimization problems involve multiple criteria that should be considered separately and satisfied/optimized simultaneously. Additionally, they are often dynamic, i.e., the problem changes at runtime. In this paper, we introduce a Multi-Objective WCSP (MO-WCSP) and develop a novel MO-WCSP algorithm called Multi-Objective Branch and Bound (MO-BnB), which is based on a new solution criterion called (l, s)-Pareto solution. Furthermore, we first for- malize a Dynamic MO-WCSP (DMO-WCSP). As an initial step forward developing an algorithm for solving a DMO-WCSP, we focus on the change of weights of constraints and develop the first algorithm called Dynamic Multi-Objective Branch and Bound (DMO-BnB) for solving a DMO-WCSPs, which is based on MO-BnB. Finally, we provide the complexity of our algorithm and evaluate DMO-BnB with different problem settings.

We address the problem of multi-objective constraint optimization problems (MO-COPs). Solving a MO-COP traditionally consists in computing the set of all Pareto optimal solutions, which is an exponentially large set in the general case. So this causes two main problems: first is the time complexity concern, second is a lack of decisiveness. In this paper, we formalize the notion of a MO-COP operator which associates every MO-COP with a subset of Pareto optimal solutions satisfying some desirable additional properties. Then, we present two specific classes of MO-COP operators that give preference to some subsets of Pareto optimal solutions. These operators correspond to two classical doctrines in Decision Theory: utilitarianism and egalitarianism. They compute solutions much more efficiently than standard operators computing all Pareto optimal solutions. In practice, they return a very few number of solutions even for problems involving a high number of objectives.

We develop a mechanism for setting discriminated reward prices in order to group crowd workers according to their abilities. Generally, a worker has a certain level of confidence in the correctness of her answers, and asking about it is useful for estimating the probability of correctness. However, we need to overcome two main obstacles to utilize confidence for inferring correct answers. One is that a worker is not always well-calibrated. Since she is sometimes over/underconfident, her confidence does not always coincide with the probability of correctness. The other is that she does not always truthfully report her confidence. Thus, we design an indirect mechanism that enables a worker to declare her confidence by choosing a desirable reward plan from the set of plans that correspond to different confidence intervals. Our mechanism ensures that choosing a plan including true confidence maximizes the worker's expected utility. We also propose a method that composes a set of plans that can achieve requester-specified accuracy in estimating the correct answer using a small number of workers. We show our experimental results using Amazon Mechanical Turk.