A game theoretic approach for feature clustering and its application to feature selection

In this paper, we develop a game theoretic approach for clustering features in a learning problem. Feature clustering can serve as an important preprocessing step in many problems such as feature selection, dimensionality reduction, etc. In this approach, we view features as rational players of a coalitional game where they form coalitions (or clusters) among themselves in order to maximize their individual payoffs. We show how Nash Stable Partition (NSP), a well known concept in the coalitional game theory, provides a natural way of clustering features. Through this approach, one can obtain some desirable properties of the clusters by choosing appropriate payoff functions. For a small number of features, the NSP based clustering can be found by solving an integer linear program (ILP). However, for large number of features, the ILP based approach does not scale well and hence we propose a hierarchical approach. Interestingly, a key result that we prove on the equivalence between a k-size NSP of a coalitional game and minimum k-cut of an appropriately constructed graph comes in handy for large scale problems. In this paper, we use feature selection problem (in a classification setting) as a running example to illustrate our approach. We conduct experiments to illustrate the efficacy of our approach.

Pattern clustering using cooperative game theory

In this paper, we approach the classical problem of clustering using solution concepts from cooperative game theory such as Nucleolus and Shapley value. We formulate the problem of clustering as a characteristic form game and develop a novel algorithm DRAC (Density-Restricted Agglomerative Clustering) for clustering. With extensive experimentation on standard data sets, we compare the performance of DRAC with that of well known algorithms. We show an interesting result that four prominent solution concepts, Nucleolus, Shapley value, Gately point and \tau-value coincide for the defined characteristic form game. This vindicates the choice of the characteristic function of the clustering game and also provides strong intuitive foundation for our approach.

Game theoretic, decentralized, local information based algorithm for community detection in social graphs

Motivated by the observation that communities in real world social networks form due to actions of rational individuals in networks, we propose a novel game theory inspired algorithm to determine communities in networks. The algorithm is decentralized and only uses local information at each node. We show the efficacy of the proposed algorithm through extensive experimentation on several real world social network data sets.

Sustaining cooperation on networks: an analytical study based on evolutionary game theory

We analytically study the role played by the network topology in sustaining cooperation in a society of myopic agents in an evolutionary setting. In our model, each agent plays the Prisoner's Dilemma (PD) game with its neighbors, as specified by a network. Cooperation is the incumbent strategy, whereas defectors are the mutants. Starting with a population of cooperators, some agents are switched to defection. The agents then play the PD game with their neighbors and compute their fitness. After this, an evolutionary rule, or imitation dynamic is used to update the agent strategy. A defector switches back to cooperation if it has a cooperator neighbor with higher fitness. The network is said to sustain cooperation if almost all defectors switch to cooperation. Earlier work on the sustenance of cooperation has largely consisted of simulation studies, and we seek to complement this body of work by providing analytical insight for the same. We find that in order to sustain cooperation, a network should satisfy some properties such as small average diameter, densification, and irregularity. Real-world networks have been empirically shown to exhibit these properties, and are thus candidates for the sustenance of cooperation. We also analyze some specific graphs to determine whether or not they sustain cooperation. In particular, we find that scale-free graphs belonging to a certain family sustain cooperation, whereas Erdos-Renyi random graphs do not. To the best of our knowledge, ours is the first analytical attempt to determine which networks sustain cooperation in a population of myopic agents in an evolutionary setting.

Game theoretic analysis of collusions in nonneutral networks

This paper studies the impact of exclusive contracts between a content provider (CP) and an internet service provider (ISP) in a nonneutral network. We consider a simple linear demand function for the CPs. We studywhen an exclusive contract is benefcial to the colluding pair and evaluate its impact on the noncolluding players at equilibrium. For the case of two CPs and one ISP we show that collusion may not always be benefcial. We derive an explicit condition in terms of the advertisement revenues of the CPs that tells when a collusion is proftable to the colluding entities.

Novel Biobjective Clustering (BiGC) Based on Cooperative Game Theory

We propose a new approach to clustering. Our idea is to map cluster formation to coalition formation in cooperative games, and to use the Shapley value of the patterns to identify clusters and cluster representatives. We show that the underlying game is convex and this leads to an efficient biobjective clustering algorithm that we call BiGC. The algorithm yields high-quality clustering with respect to average point-to-center distance (potential) as well as average intracluster point-to-point distance (scatter). We demonstrate the superiority of BiGC over state-of-the-art clustering algorithms (including the center based and the multiobjective techniques) through a detailed experimentation using standard cluster validity criteria on several benchmark data sets. We also show that BiGC satisfies key clustering properties such as order independence, scale invariance, and richness.

Pricing and Power allocation in Femtocells using Stackelberg Game Theory

We consider a system with multiple Femtocells operating in a Macrocell. The transmissions in one Femtocell interfere with its neighboring Femtocells as well as with the Macrocell Base Station. We model Femtocells as selfish nodes and the Macrocell Base Station protects itself by pricing subchannels for each usage. We use Stackelberg game model to study this scenario and obtain equilibrium policies that satisfy certain quality of service.

Doubts and Equilibria

In real life strategic interactions, decision-makers are likely to entertain doubts about the degree of optimality of their play. To capture this feature of real choice-making, we present here a model based on the doubts felt by an agent about how well is playing a game. The doubts are coupled with (and mutually reinforced by) imperfect discrimination capacity, which we model here by means of similarity relations. We assume that each agent builds procedural preferences de ned on the space of expected payoffs-strategy frequencies attached to his current strategy. These preferences, together with an adaptive learning process lead to doubt-based selection dynamic systems. We introduce the concepts of Mixed Strategy Doubt Equilibria, Mixed Strategy Doubt-Full Equilibria and Mixed Strategy Doubtless Equilibria and show the theoretical and the empirical relevance of these concepts.

A Behavioral Foundation for Models of Evolutionary Drift

Binmore and Samuelson (1999) have shown that perturbations (drift) are crucial to study the stability properties of Nash equilibria. We contribute to this literature by providing a behavioural foundation for models of evolutionary drift. In particular, this article introduces a microeconomic model of drift based on the similarity theory developed by Tversky (1977), Kahneman and Tversky (1979) and Rubinstein (1988),(1998). An innovation with respect to those works is that we deal with similarity relations that are derived from the perception that each agent has about how well he is playing the game. In addition, the similarity relations are adapted to a dynamic setting. We obtain different models of drift depending on how we model the agent´s assessment of his behaviour in the game. The examples of the ultimatum game and the chain-store game are used to show the conditions for each model to stabilize elements in the component of Nash equilibria that are not subgame- perfect. It is also shown how some models approximate the laboratory data about those games while others match the data.

Implementing with veto players: a simple non cooperative game

The paper adapts a non cooperative game presented by Dagan, Serrano and Volij (1997) for bankruptcy problems to the context of TU veto balanced games. We investigate the relationship between the Nash outcomes of a noncooperative game and solution concepts of cooperative games such as the nucleolus, kernel and the egalitarian core.

A Model of Evolutionay Drift

Drift appears to be crucial to study the stability properties of Nash equilibria in a component specifying different out-of-equilibrium behaviour. We propose a new microeconomic model of drift to be added to the learning process by which agents find their way to equilibrium. A key feature of the model is the sensitivity of the noisy agent to the proportion of agents in his player population playing the same strategy as his current one. We show that, 1. Perturbed Payoff-Positive and PayoffMonotone selection dynamics are capable of stabilizing pure non strict Nash equilibria in either singleton or nonsingleton component of equilibria; 2. The model is relevant to understand the role of drift in the behaviour observed in the laboratory for the Ultimatum Game and for predicting outcomes that can be experimentally tested. Hence, the selection dynamics model perturbed with the proposed drift may be seen as well as a new learning tool to understand observed behaviour.

Competitive Pressure and Job Interview Lying: A Game Theoretical Analysis

We consider a job contest in which candidates go through interviews (cheap talk) and are subject to reference checks. We show how competitive pressure - increasing the ratio of "good" to "bad" type candi- dates - can lead to a vast increase in lying and in some cases make bad hires more likely. As the number of candidates increases, it becomes harder to in- duce truth-telling. The interview stage becomes redundant if the candidates, a priori, know each others' type or the result of their own reference check. Finally, we show that the employer can bene t from committing not to reject all the applicants.

Evolution of Cooperation in the Snowdrift Game with Incomplete Information and Heterogeneous Population

Differently from previous studies of tag-based cooperation, we assume that individuals fail to recognize their own tag. Due to such incomplete information, the action taken against the opponent cannot be based on similarity, although it is still motivated by the tag displayed by the opponent. We present stability conditions for the case when individuals play unconditional cooperation, unconditional defection or conditional cooperation. We then consider the removal of one or two strategies. Results show that conditional cooperators are the most resilient agents against extinction and that the removal of unconditional cooperators may lead to the extinction of unconditional defectors.