Search

In this work we address the problem of critical source selection in social sensing. We propose an approach to the ranking of information streams, which is aware of the interdependence among streams (redundancy and synergies), of the cost of individual streams, and of the cost related to the integration of multiple streams. The method is based on the use of the Coalitional Game Theory concept of Power Index, and relies on the polynomial-time estimate of the stream sets characteristics. With respect to other works using a power index, the method takes into account that the problem has a non-trivial cost structure.

BackgroundComplex 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.ResultsWe 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.ConclusionsGame theoretic centrality can prioritize influential, disease-associated genes within biological networks, and assist in the decoding of polygenic associations to complex disorders like autism.

This paper investigates the cooperative data exchange (CDE) scheme using the instantly decodable network coding across energy-constrained devices over the wireless channels. In fact, enabling the CDE brings several challenges, such as how to extend the network lifetime and how to reduce the number of transmissions in order to satisfy the urgent delay requirements. The problem is modeled using the cooperative game theory in partition form. Unlike most existing studies, which are only delay-sensitive, we take into account both the completion time and the consumed energy. We propose a distributed merge-and-split algorithm to allow the wireless nodes to self-organize into the independent disjoint coalitions in a distributed manner. Indeed, the proposed algorithm guarantees reduced energy consumption and minimizes the delay in the resulting clustered network structure. Note that we have considered not only the transmission energy but also the computational energy consumption. Moreover, we focus on the mobility issue and we analyze how, in the proposed framework, the nodes can adapt to the dynamics of the network. Such an important result offers insights into how to design the scalable energy and delay aware CDE framework. The simulation results validate the proposed framework and show that, interestingly, the nodes reduce both the energy consumption and the completion time.

To improve the performance of Intensive Care Units (ICUs), the field of bio-statistics has developed scores which try to predict the likelihood of negative outcomes. These help evaluate the effectiveness of treatments and clinical practice, and also help to identify patients with unexpected outcomes. However, they have been shown by several studies to offer sub-optimal performance. Alternatively, Deep Learning offers state of the art capabilities in certain prediction tasks and research suggests deep neural networks are able to outperform traditional techniques. Nevertheless, a main impediment for the adoption of Deep Learning in healthcare is its reduced interpretability, for in this field it is crucial to gain insight into the why of predictions, to assure that models are actually learning relevant features instead of spurious correlations. To address this, we propose a deep multi-scale convolutional architecture trained on the Medical Information Mart for Intensive Care III (MIMIC-III) for mortality prediction, and the use of concepts from coalitional game theory to construct visual explanations aimed to show how important these inputs are deemed by the network. Results show our model attains a ROC AUC of 0.8735 ( ± 0.0025) which is competitive with the state of the art of Deep Learning mortality models trained on MIMIC-III data, while remaining interpretable. Supporting code can be found at https://github.com/williamcaicedo/ISeeU .

Despite mounting evidence for the strong role of genetics in the phenotypic manifestation of Autism Spectrum Disorder (ASD), the specific genes responsible for the variable forms of ASD remain undefined. ASD may be best explained by a combinatorial genetic model with varying epistatic interactions across many small effect mutations. Coalitional or cooperative game theory is a technique that studies the combined effects of groups of players, known as coalitions, seeking to identify players who tend to improve the performance--the relationship to a specific disease phenotype--of any coalition they join. This method has been previously shown to boost biologically informative signal in gene expression data but to-date has not been applied to the search for cooperative mutations among putative ASD genes. We describe our approach to highlight genes relevant to ASD using coalitional game theory on alteration data of 1,965 fully sequenced genomes from 756 multiplex families. Alterations were encoded into binary matrices for ASD (case) and unaffected (control) samples, indicating likely gene-disrupting, inherited mutations in altered genes. To determine individual gene contributions given an ASD phenotype, a "player" metric, referred to as the Shapley value, was calculated for each gene in the case and control cohorts. Sixty seven genes were found to have significantly elevated player scores and likely represent significant contributors to the genetic coordination underlying ASD. Using network and cross-study analysis, we found that these genes are involved in biological pathways known to be affected in the autism cases and that a subset directly interact with several genes known to have strong associations to autism. These findings suggest that coalitional game theory can be applied to large-scale genomic data to identify hidden yet influential players in complex polygenic disorders such as autism.

In this paper we propose a novel coalitional game theory based optimization method for minimizing the cost of the electricity consumed from the power grid by a community of smart households. A smart household may own both a renewable energy source and an energy storage system (ESS), or only an ESS. We propose an optimization model in which all the members of the community jointly share their renewable resources and storage systems. We show that the proposed coalitional optimization method reduces the consumption costs both at community level and at the individual level when compared to the case in which the households would individually optimize their costs. The monetary revenues gained by the coalition are divided among the members of the coalition according to the Shapley value. Simulation examples show that the proposed coalitional optimization method may reduce the electricity costs for the community by roughly 18%.

International audience; We consider a scenario where an Internet Service Provider (ISP) serves users that choose digital content among M Content Providers (CP). In the status quo, these users pay both access fees to the ISP and content fees to each chosen CP; however, neither the ISP nor the CPs share their profit. We revisit this model by introducing a different business model where the ISP and the CP may have motivation to collaborate in the framework of caching. The key idea is that the ISP deploys a cache for a CP provided that they share both the deployment cost and the additional profit that arises due to caching. Under the prism of coalitional games, our contributions include the application of the Shap-ley value for a fair splitting of the profit, the stability analysis of the coalition and the derivation of closed-form formulas for the optimal caching policy. Our model captures not only the case of non-overlapping contents among the CPs, but also the more challenging case of overlapping contents; for the latter case, a non-cooperative game among the CPs is introduced and analyzed to capture the negative externality on the demand of a particular CP when caches for other CPs are deployed.

Studies on autism spectrum disorder (ASD) have amassed substantial evidence for the role of genetics in the disease's phenotypic manifestation. A large number of coding and non-coding variants with low penetrance likely act in a combinatorial manner to explain the variable forms of ASD. However, many of these combined interactions, both additive and epistatic, remain undefined. Coalitional game theory (CGT) is an approach that seeks to identify players (individual genetic variants or genes) who tend to improve the performance-association to a disease phenotype of interest-of any coalition (subset of co-occurring genetic variants) they join. This method has been previously applied to boost biologically informative signal from gene expression data and exome sequencing data but remains to be explored in the context of cooperativity among non-coding genomic regions. We describe our extension of previous work, highlighting non-coding chromosomal regions relevant to ASD using CGT on alteration data of 4595 fully sequenced genomes from 756 multiplex families. Genomes were encoded into binary matrices for three types of non-coding regions previously implicated in ASD and separated into ASD (case) and unaffected (control) samples. A player metric, the Shapley value, enabled determination of individual variant contributions in both sets of cohorts. A total of 30 non-coding positions were found to have significantly elevated player scores and likely represent significant contributors to the genetic coordination underlying ASD. Cross-study analyses revealed that a subset of mutated non-coding regions (all of which are in human accelerated regions (HARs)) and related genes are involved in biological pathways or behavioral outcomes known to be affected in autism, suggesting the importance of single nucleotide polymorphisms (SNPs) within HARs in ASD. These findings support the use of CGT in identifying hidden yet influential non-coding players from large-scale genomic data, to better understand the precise underpinnings of complex neurodevelopmental disorders such as autism.

The main goal of this dissertation is to manage resource allocation in network engineering problems and to introduce efficient cooperative algorithms to obtain high performance, ensuring fairness and stability. Specifically, this dissertation introduces new approaches for resource allocation in Orthogonal Frequency Division Multiple Access (OFDMA) wireless networks and in smart power grids by casting the problems to the coalitional game framework and by providing a constructive iterative algorithm based on dynamic learning theory.

This paper studies the strategic behavior of a large number of game designers and studies the scalability, stability and robustness of their allocations in a large number of homogeneous coalitional games with transferable utilities (TU). For each TU game, the characteristic function is a continuous-time stochastic process. In each game, a game designer allocates revenues based on the extra reward that a coalition has received up to the current time and the extra reward that the same coalition has received in the other games. The approach is based on the theory of mean-field games with heterogeneous groups in a multi-population regime.

Wireless communications are important in our highly connected world. The amount of data being transferred in cellular networks is steadily growing, and consequently more capacity is needed. This thesis considers the problem of downlink capacity improvement from the perspective of multicell coordination. By employing multiple antennas at the transmitters and receivers of a multicell network, the inherent spatial selectivity of the users can be exploited in order to increase the capacity through linear precoding and receive filtering. For the coordination between cells, distributed algorithms are often sought due to their low implementation complexity and robustness. In this context, the thesis considers two problem domains: base station clustering and coordinated precoding. Base station clustering corresponds to grouping the cell base stations into disjoint clusters in order to reduce the coordination overhead. This is needed in intermediate-sized to large networks, where the overhead otherwise would be overwhelmingly high. Two solution methods for the clustering problem are proposed: an optimal centralized method, as well as a heuristic distributed method. The optimal method applies to a family of throughput models and exploits the structure of the model to find bounds that can be used to focus the search for the optimal clustering into promising territories. The distributed method instead uses notions from coalitional game theory, where the base stations are modelled as rational and intelligent players in a game. By letting the players make individual deviations that benefit them in the game, i.e.\@ switching clusters, a distributed coalition formation algorithm is obtained. Coordinated precoding is the act of finding the linear precoders and receive filters that maximize the network performance, given a base station clustering. Four specific challenges are studied in this problem domain. First, coordinated precoding under intercluster interference is considered. The channels of the intercluster links are not explicitly estimated due to overhead reasons, and these links thus lead to intercluster interference. By exploiting the known statistics of the intercluster channels, a robust and distributed coordinated precoding algorithm is developed. Second, coordinated precoding under imperfect channel state information is considered. Relying on the channel reciprocity under time-division duplex operation, a distributed estimation framework is proposed. Given the estimated channels, a robust and distributed coordinated precoding algorithm is then derived. Third, coordinated precoding under imperfect radio hardware is considered. By modelling the radio frequency distortion noises, a distributed coordinated precoding method that accounts for the imperfections is proposed. Fourth, joint coordinated precoding and discrete rate selection is considered. By bounding and linearizing an originally intractable optimization problem, a heuristic algorithm is derived which selects the transmit rate from a finite set and simultaneously forms the linear precoders and receive filters. Trådlös kommunikation är ett viktigt verktyg i dagens ständigt uppkopplade värld. Datamängden som överförs i mobilnätverk ökar stadigt och därmed behovet av mer kapacitet. För att öka kapaciteten i nedlänken så utvecklar denna avhandling nya metoder för koordinering av multicellnätverk. Med flerantenniga sändare och mottagare så kan den spatiala selektiviteten hos mottagarna utnyttjas för att separera dem, vilket ger en ökad kapacitet. För denna koordinering är distribuerade algoritmer ofta att föredra eftersom de är robusta och har låg implementeringskomplexitet. I detta sammanhang undersöker denna avhandling två problemområden: basstationsgruppering och samordnad förkodning. Basstationsgruppering innebär att basstationerna delas in i disjunkta grupper, vilket minskar overheadkostnaden för samordningen. Detta är framför allt nödvändigt i medelstora till stora nätverk, eftersom overheadkostnaden för koordineringen av dessa annars skulle bli för stor. Två lösningar för basstationsgruppering presenteras: dels en optimal och centraliserad metod samt dels en heuristisk och distribuerad metod. Den optimala och centraliserade metoden kan hantera en familj av modeller för den totala datatakten och utnyttjar strukturen i modellen för att fokusera sökandet efter den optimala grupperingen mot lovande områden. Den heuristiska och distribuerade metoden bygger på spelteori för koalitioner och modellerar basstationerna som rationella och intelligenta spelare i ett spel. En distribuerad algoritm för koalitionsformering härleds genom att låta spelarna göra individuella förflyttningar, dvs. byta grupp, när det gynnar dem under spelets regler. Vid samordnad förkodning använder de flerantenniga sändarna och mottagarna linjära förkodare och mottagningsfilter för att maximera nätverkets prestanda. Inom detta problemområde undersöks fyra olika specifika problem. Först undersöks problemet när det finns störningar mellan basstationsgrupperna. För att hålla nere mängden overhead så skattas inte kanalerna mellan grupperna, vilket ger upphov till störningar hos mottagarna. Genom att utnyttja den kända statistiska informationen för dessa okända kanaler kan en robust och distribuerade samordningsmetod för förkodningen utvecklas. Därnäst undersöks problemet då kanalkännedomen är bristfällig i allmänhet. Reciprociteten som uppstår vid tidsdelningsduplexning utnyttjas och flera distribuerade skattningsmetoder härleds. Givet den skattade kanalkännedomen föreslås en robust metod för samordnad förkodning. Därnäst undersöks problemet med samordnad förkodning då radiohårdvaran är bristfällig. En modell för det distortionsbrus som skapas av den bristfälliga hårdvaran används för att föreslå en robust distribuerad metod för samordnad förkodning för detta scenario. Slutligen undersöks valet av diskret datatakt med simultan samordnad förkodning. En heuristisk algoritm utvecklas som löser ett begränsat optimeringsproblem. Algoritmen väljer sänddatatakten från en ändlig mängd och bestämmer simultant de linjära förkodarna och mottagningsfiltrena. QC 20160407

Purpose: we prepared a questionnaire to evaluate Incompatible parts and also risk management in University of Science and Technology E-Learning Center and studying the Incompatible parts impacts on utility of organization. Design/methodology/approach: By using coalitional game theory we present a new model to recognize the degrees of incompatibility among independent divisions of an organization with dependent security assets. Based on positive and negative interdependencies in the parts, the model provides how the organization can decrease the security risks through non-cooperation rather than cooperation. we implement the proposed model of this paper by analyzing the data which have been provided by questionnaires from different three managers’ ideas of Iran University of Science and Technology E-Learning Center located in Iran University of Science and Technology, Tehran, Iran. Findings: In general, by collecting data and analyzing them, the survey showed that Incompatible parts of organizations have negative impacts on utility of organization risk management process. Furthermore, it adds values to other organizations and provides the best practices in planning, developing, implementing and monitoring risk management in organizations Research limitations/implications: Since Information security and also Risk Management are still areas which need to improve in some Iranian universities, we couldn’t consider them in our analysis. On the other hand, due to questionnaire limitation, the study’s sample size is 1. This size may be considered large for our statistical analysis. Originality/value: The main contribution of this paper is to propose a model for noncooperation among a number of divisions in an organization and using risk management factors.

The Shapley value is a key solution concept for coalitional games in general and voting games in particular. Its main advantage is that it provides a unique and fair solution, but its main drawback is the complexity of computing it (e.g., for voting games this complexity is #p-complete). However, given the importance of the Shapley value and voting games, a number of approximation methods have been developed to overcome this complexity. Among these, Owen's multi-linear extension method is the most time efficient, being linear in the number of players. Now, in addition to speed, the other key criterion for an approximation algorithm is its approximation error. On this dimension, the multi-linear extension method is less impressive. Against this background, this paper presents a new approximation algorithm, based on randomization, for computing the Shapley value of voting games. This method has time complexity linear in the number of players, but has an approximation error that is, on average, lower than Owen's. In addition to this comparative study, we empirically evaluate the error for our method and show how the different parameters of the voting game affect it. Specifically, we show the following effects. First, as the number of players in a voting game increases, the average percentage error decreases. Second, as the quota increases, the average percentage error decreases. Third, the error is different for players with different weights; players with weight closer to the mean weight have a lower error than those with weight further away. We then extend our approximation to the more general k-majority voting games and show that, for n players, the method has time complexity O(k2n) and the upper bound on its approximation error is O(k2/n).

We propose a novel tracking method that uses a network of independent particle filter trackers whose interactions are modeled using coalitional game theory. Our tracking method is general, it maintains pixel level accuracy, and can negotiate surface deformations and occlusions. We tested our method on a substantial video set featuring non-trivial motion from over 40 objects in both the infrared and visual spectra. The coalitional tracker demonstrated fault tolerant behavior that exceeds by far the performance of single particle filter trackers. Our method represents a shift from the typical tracking paradigms and may find application in demanding imaging problems across the electromagnetic spectrum.

Games and Learning; International audience; The liberalization of wireless spectrum markets has been envisioned as a method for improving mobile communication services and accommodating the increasing traffic volumes of wireless users. It has been assumed that competition among operators will foster optimal utilization of wireless spectrum and ensure the provision of cost-efficient wireless services to users. However, spectrum markets often function inefficiently due to collusion of the operators. Although it is illegal and detrimental to users, such phenomena are often observed in real life as, for example, in the form of implicit price fixing. This results in a de-facto monopoly in the spectrum market to the detriment of the users. In this paper, we consider a general wireless spectrum market where a set of operators sell bandwidth to a large population of users. We use an evolutionary game model to capture the user dynamics in the presence of limited market information and analyze the interaction of the operators using coalitional game theory. We define a partition formation game in order to rigorously study the conditions that render the grand coalition (emergence of monopoly) stable under various stability notions. The results obtained provide a foundation for effective measures against operator collusion by altering the underlying motivations rather than fighting against the symptoms through law enforcement.