The Consensus-Based Bundle Algorithm (CBBA) is a leading approach for decentralized task allocation, offering conflict-free task assignments within a bounded number of iterations and a 50% optimality guarantee for utility functions with Diminishing Marginal Gains (DMG). However, we identify three limitations: (1) the Time-Discounted Reward utility function proposed with CBBA is not always DMG, (2) the optimality guarantee may not hold even with DMG functions, and (3) the algorithm can be inefficient as it incurs unnecessary idle iterations after convergence. To address these issues, we propose three key contributions. For limitation (1), we introduce the Repeated Path Times utility function, which is DMG in all cases and aligns with Min-Sum and Makespan objectives. Regarding point (2), we develop Global CBBA (GCBBA), a variant algorithm that leverages global consensus to restore the 50% optimality guarantee under DMG and ensures bounded convergence for any bundle-monotonic objective. Finally, to address limitation (3), we design a decentralized early convergence detection method to improve efficiency. Experimental results show that GCBBA significantly accelerates convergence on large-scale problems compared to the baseline CBBA.

Tracking systems are critical for air traffic control, as they provide aircraft trajectories to air controllers in real time. Therefore, the performance of these tracking systems must be carefully monitored to maintain traffic safety. Thales has thus developed a decision-making algorithm to precisely assess the quality of service (QoS) of tracking systems, by the aggregation of thirty metrics through a multi-criteria decision model. In particular, this QoS model provides a unique numeric value to quantify the tracking performance. The goal of this article is to show how to leverage sensitivity analysis to detect the specific metrics involved in a degradation of the QoS. The identification of the relevant metrics is a critical information for technical supervisors, who can then narrow their investigations to find the problem root causes, and ultimately restore an efficient tracking. Sensitivity analysis provides various methods to apportion the variability of a model output across the input variables, and thus identify the inputs with a strong impact on the QoS output. In particular, Shapley values have recently gain considerable momentum in the sensitivity analysis and machine learning communities as a powerful method to quantify the influence of input variables in correlated settings. Hence, we focus on a real dataset collected by Thales operational systems to show the efficiency of Shapley values. More precisely, we artificially introduce a random noise into the aircraft positions measured by the radars over a short time period, and show that Shapley values successfully identify the relevant metrics involved in the QoS degradation. Overall, this simulated analysis establishes a first level of demonstration of the approach efficiency to provide precise and useful information to the technical supervisor for the root cause identification of tracking problems.

This paper aims to transform a trained classifier into an abstaining classifier, such that the latter is provably protected from out-of-distribution and adversarial samples. The proposed Sample-efficient Probabilistic Detection using Extreme Value Theory (SPADE) approach relies on a Generalized Extreme Value (GEV) model of the training distribution in the latent space of the classifier. Under mild assumptions, this GEV model allows for formally characterizing out-of-distribution and adversarial samples and rejecting them. Empirical validation of the approach is conducted on various neural architectures (ResNet, VGG, and Vision Transformer) and considers medium and large-sized datasets (CIFAR-10, CIFAR-100, and ImageNet). The results show the stability and frugality of the GEV model and demonstrate SPADE’s efficiency compared to the state-of-the-art methods.

Interpretability is a desirable property for machine learning and decision models, particularly in the context of safety-critical applications. Another most desirable property of the sought model is to be unique or {\em identifiable} in the considered class of models: the fact that the same functional dependency can be represented by a number of syntactically different models adversely affects the model interpretability, and prevents the expert from easily checking their validity. This paper focuses on the Choquet integral (CI) models and their hierarchical extensions (HCI). HCIs aim to support expert decision making, by gradually aggregating preferences based on criteria; they are widely used in multi-criteria decision aiding {and are receiving interest from the} Machine Learning {community}, as they preserve the high readability of CIs while efficiently scaling up w.r.t. the number of criteria. The main contribution is to establish the identifiability property of HCI under mild conditions: two HCIs implementing the same aggregation function on the criteria space necessarily have the same hierarchical structure and aggregation parameters. The identifiability property holds even when the marginal utility functions are learned from the data. This makes the class of HCI models a most appropriate choice in domains where the model interpretability and reliability are of primary concern.

Multi-Criteria Decision Making (MCDM) aims at modelling expert preferences and assisting decision makers in identifying options best accommodating expert criteria. An instance of MCDM model, the Choquet integral is widely used in real-world applications, due to its ability to capture interactions between criteria while retaining interpretability. Aimed at a better scalability and modularity, hierarchical Choquet integrals involve intermediate aggregations of the interacting criteria, at the cost of a more complex elicitation. The paper presents a machine learning-based approach for the automatic identification of hierarchical MCDM models, composed of 2-additive Choquet integral aggregators and of marginal utility functions on the raw features from data reflecting expert preferences. The proposed NEUR-HCI framework relies on a specific neural architecture, enforcing by design the Choquet model constraints and supporting its end-to-end training. The empirical validation of NEUR-HCI on real-world and artificial benchmarks demonstrates the merits of the approach compared to state-of-art baselines.

We introduce a way of reasoning about preferences represented as pairwise comparative statements, based on a very simple yet appealing principle: cancelling out common values across statements. We formalize and streamline this procedure with argument schemes. As a result, any conclusion drawn by means of this approach comes along with a justification. It turns out that the statements which can be inferred through this process form a proper preference relation. More precisely, it corresponds to a necessary preference relation under the assumption of additive utilities. We show the inference task can be performed in polynomial time in this setting, but that finding a minimal length explanation is NP-complete.

It is often the case in the applications of Multi-Criteria Decision Making that the values of alternatives are unknown on some attributes. An interesting situation arises when the attributes having missing values are actually not relevant and shall thus be removed from the model. Given a model that has been elicited on the complete set of attributes, we are looking thus for a way -- called restriction operator -- to automatically remove the missing attributes from this model. Axiomatic characterizations are proposed for three classes of models. For general quantitative models, the restriction operator is characterized by linearity, recursivity and decomposition on variables. The second class is the set of monotone quantitative models satisfying normalization conditions. The linearity axiom is changed to fit with these conditions. Adding recursivity and symmetry, the restriction operator takes the form of a normalized average. For the last class of models -- namely the Choquet integral, we obtain a simpler expression. Finally, a very intuitive interpretation is provided.

We consider decision situations in which a set of points of view (voters, criteria) are to sort a set of candidates to ordered categories (Good/Bad). Candidates are judged good, when approved by a sufficient set of points of view; this corresponds to NonCompensatory Sorting. To be accountable, such approval sorting should provide guarantees about the decision process and decisions concerning specific candidates. We formalize accountability using a feasibility problem expressed as a boolean satisfiability formulation. We illustrate different forms of accountability when a committee decides with approval sorting and study the information that should be disclosed by the committee.

The capability to explain the result of aggregation models to decision makers is key to reinforcing user trust. In practice, Multi-Criteria Decision Aiding models are often organized in a hierarchical way, based on a tree of criteria. We present an explanation approach usable with any hierarchical multi-criteria model, based on an influence index of each attribute on the decision. A set of desirable axioms are defined. We show that there is a unique index fulfilling these axioms. This new index is an extension of the Shapley value on trees. An efficient rewriting of this index, drastically reducing the computation time, is obtained. Finally, the use of the new index is illustrated on an example.

We address the problem of multicriteria ordinalsorting through the lens of accountability, i.e. theability of a human decision-maker to own a recommendationmade by the system. We put forward anumber of model features that would favor the capabilityto support the recommendation with a convincingexplanation. To account for that, we designa recommender system implementing and formalizingsuch features. This system outputs explanationsdefined under the form of specific argumentschemes tailored to represent the specific rules ofthe model. At the end, we discuss possible andpromising argumentative perspectives.

In systems engineering, practitioners shall explore numerous architectural alternatives until choosing the most adequate variant. The decision-making process is most of the time a manual, time-consuming, and error-prone activity. The exploration and justification of architectural solutions is ad-hoc and mainly consists in a series of tries and errors on the modeling assets. In this paper, we report on an industrial case study in which we apply variability modeling techniques to automate the assessment and comparison of several candidate architectures (variants). We first describe how we can use a model-based approach such as the Common Variability Language (CVL) to specify the architectural variability. We show that the selection of an architectural variant is a multi-criteria decision problem in which there are numerous interactions (veto, favor, complementary) between criteria.

Recently, Dung's argumentation has been extended in order to consider the strength of the defeat relation, i.e., to quantify the degree to which an argument defeats another one. We construct an argumentation framework with varied-strength defeats from a preference-based argumentation framework with an intensity degree in the preference relation. We also consider the case when the preference over the arguments is constructed from a valued logic.

Grabisch and Labreuche have recently proposed an extension of the Choquet integral adapted to situations where the values to be aggregated lie on a bipolar scale. The resulting continuous piecewise linear aggregation function has the ability to represent decisional behaviors that depend on the ldquopositiverdquo or ldquonegativerdquo satisfaction of some of the criteria. Its main drawback is that it holds a huge number of parameters that makes its determination problematic in practice. From the observation that the decision maker usually adopts a bipolar reasoning only with respect to a (small) subset of criteria, we investigate Choquet-like aggregation models that are fully bipolar only with respect to certain criteria and whose number of parameters is much lower than that of the bipolar Choquet integral. The use of the proposed concepts is illustrated in an example.

The intepretation of aggregation functions in multicriteria decision making is often based on indices such as importance indices that measure the importance of one criterion. For instance, for the Choquet integral, the importance index is the so-called Shapley value. The use of an index must always be limited to the specific context it has been designed for. Here, we are interested in determining on which criteria acts should be improved if we want their global evaluation to increase as much as possible. The Shapley value is not suited for describing this. So, we introduce a new index of importance which represents the mean worth for acts to reach higher scores in a set of criteria. This index is defined for general aggregation functions with the help of several axioms. This importance index is then applied to the Choquet integral. In particular, we computer the worth to reach higher levels in one attribute, and in a couple of attributes. Interestingly, this leads to quantities that are closely related to the Shapley and interaction indices.