Various methods based on the Shapley value have enjoyed notable success in recent years within the field of Explainable AI (XAI), in particular as feature selection mechanisms and for providing feature attributions for explaining machine learning models. Nevertheless, recent studies have raised concerns regarding the use of the Shapley value in this framework. In this paper, we delve deeper into these limitations through the lens of the axiomatic analysis of the Shapley value and its implications in the realm of machine learning. Leveraging on specific examples of classification models, we compare the effects of axioms for the Shapley value with other axioms for ranking methods based on a coalitional framework, where features are the “players” and the worth of a coalition of features corresponds to their predictive capacity. As an alternative feature selection method we pay particular attention to the lex-cel, a social ranking solution introduced in the recent literature at the intersection between coalitional games and social choice theory. Our analysis suggests that axioms characterizing the lex-cel, under certain circumstances, are more suitable for ranking features in machine learning models, compared to axioms satisfied by the Shapley value. Furthermore, through experiments conducted on public datasets, we show that the lex-cel outperforms some commonly employed feature selection algorithms based on the Shapley value, in particular with respect to the capacity of selecting less redundant features. An approximated version of the lex-cel, showing a satisfactory compromise between scalability of the approach and selection performance, is also presented and discussed.

Several methods have been introduced in the literature to extend preferences over items from a population to preferences over the groups they may form - a problem known as the Order Lifting problem. The converse matter of deducing preferences over items from expressed preferences over the coalitions that may be formed within a population - a problem known as the Social Ranking Problem - has also been studied more recently. In this paper, we investigate the links between these two problems: after an examination of the general case, we consider the impact of missing information, by studying which social ranking methods allow for the most accurate recovery of initial preferences over items, depending on the amount of missing information about coalitions. Finally, we consider the specific case in which preferences are only expressed over coalitions of same size, and examine the accuracy of social ranking methods when faced with impartial information about preferences over k-sized coalitions.

Decision makers are commonly challenged with comparing, and ultimately ranking, elements with regards to the degree to which they satisfy multiple criteria and in terms of their own preferences. This calls for a new decision making framework, which we formally present here. Within such a framework, we present multi-criteria lex-cel: a new method for ranking single elements. Furthermore, we formally establish that our contributions generalise recent results in the social choice literature. We also illustrate our contributions through a case study that poses an ethical decision-making problem.

In a coalitional game, the coalitions are weakly ordered according to their worths in the game. When moreover a power index is given, the players are ranked according to the real numbers they are assigned by the power index. If any game inducing the same ordering of the coalitions generates the same ranking of the players then, by definition, the game is (ordinally) stable for the power index, which in turn is ordinally invariant for the game. If one is interested in ranking players of a game which is stable, re-computing the power indices when the coalitional worths slightly fluctuate or are uncertain becomes useless. Bivalued games are easy examples of games stable for any power index which is linear. Among general games, we characterize those that are stable for a given linear index. Note that the Shapley and Banzhaf scores, frequently used in AI, are particular semivalues, and all semivalues are linear indices. To check whether a game is stable for a specific semivalue, it suffices to inspect the ordering of the coalitions and to perform some direct computation based on the semivalue parameters.

Abstract Decision makers can often be confronted with the need to select a subset of objects from a set of candidate objects by just counting on preferences regarding the objects’ features. Here we formalise this problem as the dominant set selection problem. Solving this problem amounts to finding the preferences over all possible sets of objects. We accomplish so by: (i) grounding the preferences over features to preferences over the objects themselves; and (ii) lifting these preferences to preferences over all possible sets of objects. This is achieved by combining lex-cel –a method from the literature—with our novel anti-lex-cel method, which we formally (and thoroughly) study. Furthermore, we provide a binary integer program encoding to solve the problem. Finally, we illustrate our overall approach by applying it to the selection of value-aligned norm systems.

In this paper we address the distributed cross-chain swap problem in the blockchain context where multiple agents exchange assets across multiple blockchain systems (e.g. trading Bitcoins for Litecoins or Ethers). We present a mathematical framework allowing to characterize blockchain swap protocols as the combination of a publishing and a commitment phase, where contracts are respectively published and then committed. We characterize the equilibria of existing cross-chain swap protocols (i.e., blockchain swap protocols exchanging assets among different blockchains). More precisely, we prove that following a swap protocol characterized by concurrent publishing of exchange contracts and snap (immediate) assets transfers is a Nash equilibrium. Furthermore, we prove that for protocols with a sequential publishing and commitment of the assets transfers, following the prescribed protocol is a sub-game perfect equilibrium.

We investigate the issue of manipulability for social ranking rules, where the goal is to rank individuals given the ranking of coalitions formed by them and each individual prefers to reach the highest positions in the social ranking. This problem lies at the intersection of computational social choice and the algorithmic theory of power indices. Different social ranking rules have been recently proposed and studied from an axiomatic point of view. In this paper, we focus on rules representing three classical approaches in social choice theory: the marginal contribution approach, the lexicographic approach and the (ceteris paribus) majority one. We first consider some particular members of these families analysing their resistance to a malicious behaviour of individuals. Then, we analyze the computational complexity of manipulation, and complete our theoretical results with simulations in order to analyse the manipulation frequencies and to assess the effects of manipulations.

The 5G infrastructure brings a key novelty in networked systems design that is a new resource provisioning entity, the so-called "network slice". A network slice is meant to serve end-to-end services as a composition of different network and system resources as the radio, the link and a variety of computing resources (CPU, RAM, storage), generally each managed by a distinct decision-maker (platform, provider, orchestrator or controller). Naturally, centralized slice orchestration approaches have been proposed, where a multi-domain orchestrator allocates the resources, using a multi-resource allocation rule. Nonetheless, while simplifying the algorithmic approach, centralization can come at the expense of scalability and performance. In this paper, we propose new ways to decentralize the slice resource allocation problem, using cascade or parallel resource allocations. We provide an exhaustive analysis of the advantages and disadvantages of the different approaches together with a numerical analysis in a realistic environment.

BACKGROUND: Complex human health conditions with etiological heterogeneity like Autism Spectrum Disorder (ASD) often pose a challenge for traditional genome-wide association study approaches in defining a clear genotype to phenotype model. Coalitional game theory (CGT) is an exciting method that can consider the combinatorial effect of groups of variants working in concert to produce a phenotype. CGT has been applied to associate likely-gene-disrupting variants encoded from whole genome sequence data to ASD; however, this previous approach cannot take into account for prior biological knowledge. Here we extend CGT to incorporate a priori knowledge from biological networks through a game theoretic centrality measure based on Shapley value to rank genes by their relevance-the individual gene's synergistic influence in a gene-to-gene interaction network. Game theoretic centrality extends the notion of Shapley value to the evaluation of a gene's contribution to the overall connectivity of its corresponding node in a biological network. RESULTS: We implemented and applied game theoretic centrality to rank genes on whole genomes from 756 multiplex autism families. Top ranking genes with the highest game theoretic centrality in both the weighted and unweighted approaches were enriched for pathways previously associated with autism, including pathways of the immune system. Four of the selected genes HLA-A, HLA-B, HLA-G, and HLA-DRB1-have also been implicated in ASD and further support the link between ASD and the human leukocyte antigen complex. CONCLUSIONS: Game theoretic centrality can prioritize influential, disease-associated genes within biological networks, and assist in the decoding of polygenic associations to complex disorders like autism.

Among the novelties introduced by 5G networks, the formalization of the `network slice' as a resource allocation unit is an important one. In legacy networks, resources such as link bandwidth, spectrum, computing capacity are allocated independently of each other. In 5G environments, a network slice is meant to directly serve end-to-end services, or verticals: behind a network slice demand, a tenant expresses the need to access a precise service type, under a fully qualified set of computing and network requirements. The resource allocation decision encompasses, therefore, a combination of different resources. In this paper, we address the problem of fairly sharing multiple resources between slices, in the critical situation in which the network does not have enough resources to fully satisfy slice demands. We model the problem as a multi-resource allocation problem, proposing a versatile optimization framework based on the Ordered Weighted Average (OWA) operator, that takes into account different fairness approaches. We show how, adapting the OWA utility function, our framework can generalize classical single-resource allocation methods, existing multi-resource allocation solutions at the state of the art, and implement novel multi-resource allocation solutions. We compare analytically and by extensive simulations the different methods in terms of fairness and system efficiency.

We introduce a new method to rank single elements given an order over their sets. For this purpose, we extend the game theoretic notion of marginal contribution and of Banzhaf index to our ordinal framework. Furthermore, we characterize the resulting ordinal Banzhaf solution by means of a set of properties inspired from those used to axiomatically characterize another solution from the literature: the ceteris paribus majority. Finally, we show that the computational procedure for these two social ranking solutions boils down to a weighted combination of comparisons over the same subsets of elements.

We study the problem of finding a social ranking over individuals given a ranking over coalitions formed by them. We investigate the use of a ceteris paribus majority principle as a social ranking solution inspired from the classical axioms of social choice theory. Faced with a Condorcet-like paradox, we analyze the consequences of restricting the domain according to an adapted version of single-peakedness. We conclude with a discussion on different interpretations of incompleteness of the ranking over coalitions and its exploitation for defining new social rankings, providing a new rule as an example.

In networking and computing, resource allocation is typically addressed using classical resource allocation protocols as the proportional rule, the max-min fair allocation, or solutions inspired by cooperative game theory. In this paper, we argue that, under awareness about the available resource and other users demands, a cooperative setting has to be considered in order to revisit and adapt the concept of fairness. Such a complete information sharing setting is expected to happen in 5G environments, where resource sharing among tenants (slices) need to be made acceptable by users and applications, which therefore need to be better informed about the system status via ad-hoc (northbound) interfaces than in legacy environments. We identify in the individual satisfaction rates the key aspect of the challenge of defining a new notion of fairness in systems with complete information sharing, consequently, a more appropriate resource allocation algorithm. We generalize the concept of user satisfaction considering the set of admissible solutions for bankruptcy games and we adapt to it the fairness indices. Accordingly, we propose a new allocation rule we call mood value: for each user, it equalizes our novel game-theoretic definition of user satisfaction with respect to a distribution of the resource. We test the mood value and a new fairness index through extensive simulations about the cellular frequency scheduling use-case, showing how they better support the fairness analysis. We complete the paper with further analysis on the behavior of the mood value in the presence of multiple competing providers and with cheating users.

In this work we address the issue of uncertainty in abstract argumentation. We propose a way to compute the relative relevance of arguments by merging the classical argumentation framework proposed in [5] into a game theoretic coalitional setting, where the worth of a collection of arguments can be seen as the combination of the information concerning the defeat relation and the preferences over arguments of a “user”. Via a property-driven approach, we show that the Shapley value [17] for coalitional games defined over an argumentation framework, can be applied to resume all the information about the worth of sets of arguments into an attribution of relevance for the single arguments. We also prove that, for a large family of (coalitional) argumentation frameworks, the Shapley value can be easily computed.

In the present Internet, inter-domain routing is based on BGP-4 [1] which selects a single path per destination prefix, thereby preventing carriers and end-users to use the vast inherent path diversity [2]. Addition of multi-path capabilities to the Internet have long been advocated for both robustness and traffic engineering purposes. Some works [3], [4] propose inter-domain multipath architectures. In this paper we consider a new service where carriers offer additional routes to their customers (w.r.t. to BGP default route) as an added-value service. These alternate routes can be used by customers to help them to meet their traffic engineering objectives (better delays etc.) or just for robustness purposes (disjoint alternate routes). Announcing additional paths can lead to scalability issues [5], so one carrier will propagate only the paths that are most interesting for neighboring domains. We propose an auction-like framework adapted to this specific service, allowing one carrier to select the most interesting paths and determine the prices at which these routes can be sold. We consider the case where routes are sold as infinitely duplicable goods (assuming small demands with regards to route capacities). We design a winner determination mechanism, based on the maximization of the seller's revenue, that enforces fair allocation of goods and is loser collusion proof. We also propose a payment mechanism that is proven to be truthful when each bidder submits one (potentially combinatorial) bid.

The energy consumption of network devices, and, as a consequence, of communication networks, is generally independent from their level of utilization, which results in a waste of energy when the network is lightly loaded. Ideally the consumption of a network should be proportional to the amount of traffic it conveys. The most straightforward way to enforce such a proportionality between the network energy consumption and its utilization level, is to dynamically adapt the status of network devices to the load, forcing a subset of them to enter a sleep state during the low activity periods. We present in this paper an algorithm to dynamically put links into a sleep state, based on a cooperative-game approach, named “L-Game”. Our approach decides which links can be switched off based on a measure of the criticality of each link expressed as its Shapley value. This measure combines topological aspects and traffic conditions. Simulation results on real network scenarios show that our solution achieves a better trade off between energy saving and Traffic Engineering than other legacy approaches.

MOTIVATION: The interpretation of gene interaction in biological networks generates the need for a meaningful ranking of network elements. Classical centrality analysis ranks network elements according to their importance but may fail to reflect the power of each gene in interaction with the others. RESULTS: We introduce a new approach using coalitional games to evaluate the centrality of genes in networks keeping into account genes' interactions. The Shapley value for coalitional games is used to express the power of each gene in interaction with the others and to stress the centrality of certain hub genes in the regulation of biological pathways of interest. The main improvement of this contribution, with respect to previous applications of game theory to gene expression analysis, consists in a finer resolution of the gene interaction investigated in the model, which is based on pairwise relationships of genes in the network. In addition, the new approach allows for the integration of a priori knowledge about genes playing a key function on a certain biological process. An approximation method for practical computation on large biological networks, together with a comparison with other centrality measures, is also presented.

BACKGROUND: In gene expression analysis, statistical tests for differential gene expression provide lists of candidate genes having, individually, a sufficiently low p-value. However, the interpretation of each single p-value within complex systems involving several interacting genes is problematic. In parallel, in the last sixty years, game theory has been applied to political and social problems to assess the power of interacting agents in forcing a decision and, more recently, to represent the relevance of genes in response to certain conditions. RESULTS: In this paper we introduce a Bootstrap procedure to test the null hypothesis that each gene has the same relevance between two conditions, where the relevance is represented by the Shapley value of a particular coalitional game defined on a microarray data-set. This method, which is called Comparative Analysis of Shapley value (shortly, CASh), is applied to data concerning the gene expression in children differentially exposed to air pollution. The results provided by CASh are compared with the results from a parametric statistical test for testing differential gene expression. Both lists of genes provided by CASh and t-test are informative enough to discriminate exposed subjects on the basis of their gene expression profiles. While many genes are selected in common by CASh and the parametric test, it turns out that the biological interpretation of the differences between these two selections is more interesting, suggesting a different interpretation of the main biological pathways in gene expression regulation for exposed individuals. A simulation study suggests that CASh offers more power than t-test for the detection of differential gene expression variability. CONCLUSION: CASh is successfully applied to gene expression analysis of a data-set where the joint expression behavior of genes may be critical to characterize the expression response to air pollution. We demonstrate a synergistic effect between coalitional games and statistics that resulted in a selection of genes with a potential impact in the regulation of complex pathways.

This paper focuses on the role that social norms play in the selection of equilibrium points seen as social conventions under unforeseen contingencies — that is, their role in the emergence of regularities of behavior which are self-enforcing and effectively adhered to by bounded rational agents due to their self-policing incentives. Differently stated, given a set of game situations imperfectly described, we want to understand how general and abstract norms provide at least the starting point for a norm-based equilibrium selection reasoning procedure which in the end will be able to determine which equilibrium point, belonging to perfectly described games, will be played as the unique solution of each imperfectly described game. In order to solve such a problem we introduce a selection process based on the reformulation of default logic in terms of possibility theory.

We describe the main lines of a teacher preparation model aiming to help teachers experience the opportunities and difficulties of using ICT (information and communication technology) as a means for encouraging students to learn from and with peers. Based on our experience with in-service and pre-service teachers, we firstly discuss the levels of competence to be achieved by trainee teachers, putting them in relation with the training objectives. Then we introduce our model, and discuss the results of an experiment on the practical applicability of our ideas. With our work we intend to contribute to define innovations to be introduced in ICT training to support teachers in understanding how, and under what conditions, technology can support the emerging pedagogical practices that emphasise learner-controlled learning.