Learning Optimal Discriminant Functions through a Cooperative Game of Automata

The problem of learning correct decision rules to minimize the probability of misclassification is a long-standing problem of supervised learning in pattern recognition. The problem of learning such optimal discriminant functions is considered for the class of problems where the statistical properties of the pattern classes are completely unknown. The problem is posed as a game with common payoff played by a team of mutually cooperating learning automata. This essentially results in a probabilistic search through the space of classifiers. The approach is inherently capable of learning discriminant functions that are nonlinear in their parameters also. A learning algorithm is presented for the team and convergence is established. It is proved that the team can obtain the optimal classifier to an arbitrary approximation. Simulation results with a few examples are presented where the team learns the optimal classifier.

A cooperative game of a pair of learning automata

A cooperative game played in a sequential manner by a pair of learning automata is investigated in this paper. The automata operate in an unknown random environment which gives a common pay-off to the automata. Necessary and sufficient conditions on the functions in the reinforcement scheme are given for absolute monotonicity which enables the expected pay-off to be monotonically increasing in any arbitrary environment. As each participating automaton operates with no information regarding the other partner, the results of the paper are relevant to decentralized control.

Cooperative game play with avatars and agents: Differences in brain activity and the experience of play

The current study sought to identify the impact of whether teammates in a cooperative videogame were controlled by other humans (avatars) or by the game (agents). The impact on player experience was explored through both subjective questionnaire measures and brain wave activity measurement (electroencephalography). Play with human teammates was associated with a greater sense of relatedness, but less competence and flow than play with other computer-controlled teammates. In terms of brain activity, play with human teammates was associated with greater activity in the alpha, theta and beta power bands than play with computer-controlled teammates. Overall, the results suggest that play with human teammates involves greater cognitive activity in terms of 'mentalising' than play with computer-controlled teammates. Additionally, the associations between subjective measures of player experience and brain activity are described. Limitations of the current study are identified and key directions for future research are discussed.

A cooperative game theoretic approach to prototype selection

In this paper we consider the task of prototype selection whose primary goal is to reduce the storage and computational requirements of the Nearest Neighbor classifier while achieving better classification accuracies. We propose a solution to the prototype selection problem using techniques from cooperative game theory and show its efficacy experimentally.

A non-cooperative game-theoretic approach to channel assignment in multi-channel multi-radio wireless networks

Channel assignment in multi-channel multi-radio wireless networks poses a significant challenge due to scarcity of number of channels available in the wireless spectrum. Further, additional care has to be taken to consider the interference characteristics of the nodes in the network especially when nodes are in different collision domains. This work views the problem of channel assignment in multi-channel multi-radio networks with multiple collision domains as a non-cooperative game where the objective of the players is to maximize their individual utility by minimizing its interference. Necessary and sufficient conditions are derived for the channel assignment to be a Nash Equilibrium (NE) and efficiency of the NE is analyzed by deriving the lower bound of the price of anarchy of this game. A new fairness measure in multiple collision domain context is proposed and necessary and sufficient conditions for NE outcomes to be fair are derived. The equilibrium conditions are then applied to solve the channel assignment problem by proposing three algorithms, based on perfect/imperfect information, which rely on explicit communication between the players for arriving at an NE. A no-regret learning algorithm known as Freund and Schapire Informed algorithm, which has an additional advantage of low overhead in terms of information exchange, is proposed and its convergence to the stabilizing outcomes is studied. New performance metrics are proposed and extensive simulations are done using Matlab to obtain a thorough understanding of the performance of these algorithms on various topologies with respect to these metrics. It was observed that the algorithms proposed were able to achieve good convergence to NE resulting in efficient channel assignment strategies.

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.

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.

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.

Blue Marlin, Makaira nigricans, Movements in the Western North Atlantic Ocean: Results of a Cooperative Game Fish Tagging Program, 1954-88

Blue marlin, Makaira nigricans, tag and recapture data are summarized for 1954-1988. During this period, 8,447 fish have been tagged and only 30 (0.35 percent) have been returned. Results of the tagging program indicate that blue marlin not only travel considerable distances (7,OOO km from the U. S. Virgin Islands to the Ivory Coast of West Africa), but have remained at large for up to 8 years. Seasonal movements, however, are difficult to determine accurately.

Transmission cost allocation using cooperative game theory: a comparative study

In this paper is presented a Game Theory based methodology to allocate transmission costs, considering cooperation and competition between producers. As original contribution, it finds the degree of participation on the additional costs according to the demand behavior. A comparative study was carried out between the obtained results using Nucleolus balance and Shapley Value, with other techniques such as Averages Allocation method and the Generalized Generation Distribution Factors method (GGDF). As example, a six nodes network was used for the simulations. The results demonstrate the ability to find adequate solutions on open access environment to the networks.

Reactive Control for Transmission Overload Relief Based on Sensitivity Analysis and Cooperative Game Theory

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

A cooperative game theory analysis for transmission loss allocation

This paper presents an analysis and discussion, based on cooperative game theory, for the allocation of the cost of losses to generators and demands in transmission systems. We construct a cooperative game theory model in which the players are represented by equivalent bilateral exchanges and we search for a unique loss allocation solution, the Core. Other solution concepts, such as the Shapley Value, the Bilateral Shapley Value and the Kernel are also explored. Our main objective is to illustrate why is not possible to find an optimal solution for allocating the cost of losses to the users of a network. Results and relevant conclusions are presented for a 4-bus system and a 14-bus system. (c) 2007 Elsevier B.V. All rights reserved.

Cooperation in supply chains: A cooperative game theoretic analysis = Együttműködés ellátási láncokban: Egy kooperatív játékelméleti elemzés

A cikkben a kooperatív játékelmélet fogalmait alkalmazzuk egy ellátási lánc esetében. Az ostorcsapás-hatás elemeit egy beszállító-termelő ellátási láncban ragadjuk meg egy Arrow-Karlin típusú modellben lineáris készletezési és konvex termelési költség mellett. Feltételezzük, hogy mindkét vállalat minimalizálja a fontosabb költségeit. Két működési rendszert hasonlítunk össze: egy hierarchikus döntéshozatali rendszert, amikor először a termelő, majd a beszállító optimalizálja helyzetét, majd egy centralizált (kooperatív) modellt, amikor a vállalatok az együttes költségüket minimalizálják. A kérdés úgy merül fel, hogy a csökkentett ostorcsapás-hatás esetén hogyan osszák meg a részvevők ebben a transzferálható hasznosságú kooperatív játékban. = In this paper we apply cooperative game theory concepts to analyze supply chains. The bullwhip effect in a two-stage supply chain (supplier-manufacturer) in the framework of the Arrow-Karlin model with linear-convex cost functions is considered. It is assumed that both firms minimize their relevant costs, and two cases are examined: the supplier and the manufacturer minimize their relevant costs in a decentralized and in a centralized (cooperative) way. The question of how to share the savings of the decreased bullwhip effect in the centralized (cooperative) model is answered by transferable utility cooperative game theory tools.

Cooperation in an HMMS-type supply chain: A management application of cooperative game theory = Kooperáció egy HMMS-típusú ellátási láncban: A kooperatív játékelmélet egy menedzsment alkalmazása

We apply cooperative game theory concepts to analyze a Holt-Modigliani-Muth-Simon (HMMS) supply chain. The bullwhip effect in a two-stage supply chain (supplier-manufacturer) in the framework of the HMMS-model with quadratic cost functions is considered. It is assumed that both firms minimize their relevant costs, and two cases are examined: the supplier and the manufacturer minimize their relevant costs in a decentralized and in a centralized (cooperative) way. The question of how to share the savings of the decreased bullwhip effect in the centralized (cooperative) model is answered by the weighted Shapley value, by a transferable utility cooperative game theory tool, where the weights are for the exogenously given “bargaining powers” of the participants of the supply chain. = A cikkben a kooperatív játékelmélet fogalmait alkalmazzuk egy Holt-Mogigliani-Muth-Simon-típusú ellátási lánc esetében. Az ostorcsapás-hatás elemeit egy beszállító-termelő ellátási láncban ragadjuk meg egy kvadratikus készletezési és termelési költség mellett. Feltételezzük, hogy mindkét vállalat minimalizálja a releváns költségeit. Két működési rendszert hasonlítunk össze: egy hierarchikus döntéshozatali rendszert, amikor először a termelő, majd a beszállító optimalizálja helyzetét, majd egy centralizált (kooperatív) modellt, amikor a vállalatok az együttes költségüket minimalizálják. A kérdés úgy merül fel, hogy a csökkentett ostorcsapás-hatás esetén hogyan osszák meg a részvevők ebben a transzferálható hasznosságú kooperatív játékban a költség megtakarítást, exogén módon adott tárgyalási pozíció mellett.