Página 1 dos resultados de 160 itens digitais encontrados em 0.006 segundos

A cooperative game theory analysis for transmission loss allocation

Lima, Delberis A.; Contreras, Javier; Padilha-Feltrin, Antonio
Fonte: Elsevier B.V. Sa Publicador: Elsevier B.V. Sa
Tipo: Artigo de Revista Científica Formato: 264-275
Português
Relevância na Pesquisa
48.162188%
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.

Characterizing the Shapley value in fixed-route traveling salesman problems with appointments

Yengin, D.
Fonte: Physica-Verlag GMBH & Co Publicador: Physica-Verlag GMBH & Co
Tipo: Artigo de Revista Científica
Publicado em //2012 Português
Relevância na Pesquisa
67.93632%
Starting from her home, a service provider visits several customers, following a predetermined route, and returns home after all customers are visited. The problem is to find a fair allocation of the total cost of this tour among the customers served. A transferable-utility cooperative game can be associated with this cost allocation problem. We introduce a new class of games, which we refer as the fixed-route traveling salesman games with appointments. We characterize the Shapley value in this class using a property which requires that sponsors do not benefit from mergers, or splitting into a set of sponsors.; Duygu Yengin

Energy Accounting and Optimization for Mobile Systems

Dong, Mian
Fonte: Universidade Rice Publicador: Universidade Rice
Português
Relevância na Pesquisa
48.20654%
Energy accounting determines how much a software process contributes to the total system energy consumption. It is the foundation for evaluating software and has been widely used by operating system based energy management. While various energy accounting policies have been tried, there is no known way to evaluate them directly simply because it is hard to track every hardware use by software in a heterogeneous multicore system like modern smartphones and tablets. This work provides the ground truth for energy accounting based on multi-player game theory and offers the first evaluation of existing energy accounting policies, revealing their important flaws. The proposed ground truth is based on Shapley value, a single value solution to multi-player games of which four axiomatic properties are natural and self-evident to energy accounting. This work further provides a utility optimization formulation of energy management and shows, surprisingly, that energy accounting does not matter for existing energy management solutions that control the energy use of a process by giving it an energy budget, or budget based energy management (BEM). This work shows an optimal energy management (OEM) framework can always outperform BEM. While OEM does not require any form of energy accounting...

The Shapley group value

Flores Díaz, Ramón Jesús; Molina, Elisenda; Tejada, Juan
Fonte: Universidade Carlos III de Madrid Publicador: Universidade Carlos III de Madrid
Tipo: Trabalho em Andamento
Publicado em 01/11/2013 Português
Relevância na Pesquisa
58.425703%
Following the original interpretation of the Shapley value (Shapley, 1953a) as a priori evaluation of the prospects of a player in a multi-person iteraction situation, we propose a group value, which we call the Shapley group value, as a priori evaluation of the prospects of a group of players in a coalitional game when acting as a unit. We study its properties and we give an axiomatic characterization. We motivate our proposal by means of some relevant applications of the Shapley group value, when it is used as an objective function by a decision maker who is trying to identify an optimal group of agents in a framework in which agents interact and the attained benefit can be modeled by means of a transferable utility game. As an illustrative example we analyze the problem of identifying the set of key agents in a terrorist network.; This research has been supported by I+D+i research project MTM2011-27892 from the Government of Spain

The value of shapley as a strategy for Resource Optimization on Power Line Communication (PLC); El Valor de Shapley como estrategia de optimizaci??n de recursos sobre Power Line Communication (PLC)

Vesga, Juan C.; Acu??a, Gerardo Granados; Sierra Carrillo, Javier E.
Fonte: Universidad EAFIT Publicador: Universidad EAFIT
Tipo: info:eu-repo/semantics/article; info:eu-repo/semantics/publishedVersion; article; Art??culo Formato: application/pdf; text/html
Português
Relevância na Pesquisa
48.523096%
This article proposes the use of cooperative game theory, supported by the use of bankruptcy game of the and the Shapley value, as a strategy to optimize the allocation of resources in each node, according to service demand, the number of stations and the conditions of the PLC channel. The paper proposes a scenario under saturated traffic conditions, in order to assess the degree of optimization that the value of Shapley can perform in front of traffic and channel conditions clearly established. It is concluded that the use of cooperative game theory, supported on the Shapley value, can be considered as an excellent alternative when making resource optimization processes in a PLC channel y with the possibility to be implemented in economic embedded systems, because it does not require complex operations for its estimation.; En este art??culo se propone el uso de la teor??a de juegos cooperativos, apoyados en el uso del juego de la bancarrota y el valor de Shapley, como estrategia para optimizar la asignaci??n de recursos en cada nodo, acorde con la demanda en el servicio, el n??mero de estaciones y las condiciones del canal PLC. El art??culo plantea un escenario bajo condiciones de tr??fico saturado, con el fin de evaluar el grado de optimizaci??n que el valor de Shapley puede realizar ante condiciones de tr??fico y de canal claramente establecidas. Se concluye que el uso de la teor??a juegos cooperativos...

Efficient Computation of the Shapley Value for Game-Theoretic Network Centrality

Michalak, Tomasz Pawel; Aadithya, Karthik V; Szczepanski, Piotr L.; Ravindran, Balaraman; Jennings, Nicholas R.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 03/02/2014 Português
Relevância na Pesquisa
48.315195%
The Shapley value---probably the most important normative payoff division scheme in coalitional games---has recently been advocated as a useful measure of centrality in networks. However, although this approach has a variety of real-world applications (including social and organisational networks, biological networks and communication networks), its computational properties have not been widely studied. To date, the only practicable approach to compute Shapley value-based centrality has been via Monte Carlo simulations which are computationally expensive and not guaranteed to give an exact answer. Against this background, this paper presents the first study of the computational aspects of the Shapley value for network centralities. Specifically, we develop exact analytical formulae for Shapley value-based centrality in both weighted and unweighted networks and develop efficient (polynomial time) and exact algorithms based on them. We empirically evaluate these algorithms on two real-life examples (an infrastructure network representing the topology of the Western States Power Grid and a collaboration network from the field of astrophysics) and demonstrate that they deliver significant speedups over the Monte Carlo approach. For instance...

Steady Marginality: A Uniform Approach to Shapley Value for Games with Externalities

Skibski, Oskar
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 11/05/2011 Português
Relevância na Pesquisa
48.102383%
The Shapley value is one of the most important solution concepts in cooperative game theory. In coalitional games without externalities, it allows to compute a unique payoff division that meets certain desirable fairness axioms. However, in many realistic applications where externalities are present, Shapley's axioms fail to indicate such a unique division. Consequently, there are many extensions of Shapley value to the environment with externalities proposed in the literature built upon additional axioms. Two important such extensions are "externality-free" value by Pham Do and Norde and value that "absorbed all externalities" by McQuillin. They are good reference points in a space of potential payoff divisions for coalitional games with externalities as they limit the space at two opposite extremes. In a recent, important publication, De Clippel and Serrano presented a marginality-based axiomatization of the value by Pham Do Norde. In this paper, we propose a dual approach to marginality which allows us to derive the value of McQuillin. Thus, we close the picture outlined by De Clippel and Serrano.

The Shapley Value of Phylogenetic Trees

Haake, Claus-Jochen; Kashiwada, Akemi; Su, Francis Edward
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
48.315195%
Every weighted tree corresponds naturally to a cooperative game that we call a "tree game"; it assigns to each subset of leaves the sum of the weights of the minimal subtree spanned by those leaves. In the context of phylogenetic trees, the leaves are species and this assignment captures the diversity present in the coalition of species considered. We consider the Shapley value of tree games and suggest a biological interpretation. We determine the linear transformation M that shows the dependence of the Shapley value on the edge weights of the tree, and we also compute a null space basis of M. Both depend on the "split counts" of the tree. Finally, we characterize the Shapley value on tree games by four axioms, a counterpart to Shapley's original theorem on the larger class of cooperative games.; Comment: References added, and a section (calculating the Shapley value of a tree game from its subtrees) was removed for length reasons (request of referee) and may appear in another paper. 16 pages; related work at http://www.math.hmc.edu/~su/papers.html. Journal of Mathematical Biology, to appear. The original article is available at http://www.springerlink.com

Bounding the Estimation Error of Sampling-based Shapley Value Approximation

Maleki, Sasan; Tran-Thanh, Long; Hines, Greg; Rahwan, Talal; Rogers, Alex
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
48.425703%
The Shapley value is arguably the most central normative solution concept in cooperative game theory. It specifies a unique way in which the reward from cooperation can be "fairly" divided among players. While it has a wide range of real world applications, its use is in many cases hampered by the hardness of its computation. A number of researchers have tackled this problem by (i) focusing on classes of games where the Shapley value can be computed efficiently, or (ii) proposing representation formalisms that facilitate such efficient computation, or (iii) approximating the Shapley value in certain classes of games. For the classical \textit{characteristic function} representation, the only attempt to approximate the Shapley value for the general class of games is due to Castro \textit{et al.} \cite{castro}. While this algorithm provides a bound on the approximation error, this bound is \textit{asymptotic}, meaning that it only holds when the number of samples increases to infinity. On the other hand, when a finite number of samples is drawn, an unquantifiable error is introduced, meaning that the bound no longer holds. With this in mind, we provide non-asymptotic bounds on the estimation error for two cases: where (i) the \textit{variance}...

The Shapley Value in Knapsack Budgeted Games

Bhagat, Smriti; Kim, Anthony; Muthukrishnan, S.; Weinsberg, Udi
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 18/09/2014 Português
Relevância na Pesquisa
48.46887%
We propose the study of computing the Shapley value for a new class of cooperative games that we call budgeted games, and investigate in particular knapsack budgeted games, a version modeled after the classical knapsack problem. In these games, the "value" of a set $S$ of agents is determined only by a critical subset $T\subseteq S$ of the agents and not the entirety of $S$ due to a budget constraint that limits how large $T$ can be. We show that the Shapley value can be computed in time faster than by the na\"ive exponential time algorithm when there are sufficiently many agents, and also provide an algorithm that approximates the Shapley value within an additive error. For a related budgeted game associated with a greedy heuristic, we show that the Shapley value can be computed in pseudo-polynomial time. Furthermore, we generalize our proof techniques and propose what we term algorithmic representation framework that captures a broad class of cooperative games with the property of efficient computation of the Shapley value. The main idea is that the problem of determining the efficient computation can be reduced to that of finding an alternative representation of the games and an associated algorithm for computing the underlying value function with small time and space complexities in the representation size.; Comment: A short version to appear in the 10th Conference on Web and Internet Economics (WINE 2014)

Comparing the rankings obtained from two biodiversity indices: the Fair Proportion Index and the Shapley Value

Wicke, Kristina; Fischer, Mareike
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 30/07/2015 Português
Relevância na Pesquisa
48.315195%
The Shapley Value and the Fair Proportion Index of phylogenetic trees have been frequently discussed as prioritization tools in conservation biology. Both indices rank species according to their contribution to total phylogenetic diversity, allowing for a simple conservation criterion. While both indices have their specific advantages and drawbacks, it has recently been shown that both values are closely related. However, as different authors use different definitions of the Shapley Value, the specific degree of relatedness depends on the specific version of the Shapley Value - it ranges from a high correlation index to equality of the indices. In this note, we first give an overview of the different indices. Then we turn our attention to the mere ranking order provided by either of the indices. We show that even though the chance of two rankings being exactly identical (when obtained from different versions of the Shapley Value) decreases with an increasing number of taxa, the distance between the two rankings converges to zero, i.e. the rankings are becoming more and more alike. Moreover, we introduce our software package FairShapley, which was implemented in Perl and with which all calculations have been performed.; Comment: 19 pages...

The Inverse Shapley Value Problem

De, Anindya; Diakonikolas, Ilias; Servedio, Rocco A.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 20/12/2012 Português
Relevância na Pesquisa
48.50502%
For $f$ a weighted voting scheme used by $n$ voters to choose between two candidates, the $n$ \emph{Shapley-Shubik Indices} (or {\em Shapley values}) of $f$ provide a measure of how much control each voter can exert over the overall outcome of the vote. Shapley-Shubik indices were introduced by Lloyd Shapley and Martin Shubik in 1954 \cite{SS54} and are widely studied in social choice theory as a measure of the "influence" of voters. The \emph{Inverse Shapley Value Problem} is the problem of designing a weighted voting scheme which (approximately) achieves a desired input vector of values for the Shapley-Shubik indices. Despite much interest in this problem no provably correct and efficient algorithm was known prior to our work. We give the first efficient algorithm with provable performance guarantees for the Inverse Shapley Value Problem. For any constant $\eps > 0$ our algorithm runs in fixed poly$(n)$ time (the degree of the polynomial is independent of $\eps$) and has the following performance guarantee: given as input a vector of desired Shapley values, if any "reasonable" weighted voting scheme (roughly, one in which the threshold is not too skewed) approximately matches the desired vector of values to within some small error...

How good is the Shapley value-based approach to the influence maximization problem?

Adamczewski, Kamil; Matejczyk, Szymon; Michalak, Tomasz P.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 27/09/2014 Português
Relevância na Pesquisa
48.162188%
The Shapley value has been recently advocated as a method to choose the seed nodes for the process of information diffusion. Intuitively, since the Shapley value evaluates the average marginal contribution of a player to the coalitional game, it can be used in the network context to evaluate the marginal contribution of a node in the process of information diffusion given various groups of already 'infected' nodes. Although the above direction of research seems promising, the current liter- ature is missing a throughout assessment of its performance. The aim of this work is to provide such an assessment of the existing Shapley value-based approaches to information diffusion.; Comment: 21st European Conference on Artificial Intelligence

Implementation of the Ordinal Shapley Value for a three-agent economy

Pérez-Castrillo, David; Wettstein, David
Fonte: Conselho Superior de Investigações Científicas Publicador: Conselho Superior de Investigações Científicas
Tipo: Documento de trabajo
Português
Relevância na Pesquisa
67.93632%
We propose a simple mechanism that implements the Ordinal Shapley Value (Pérez-Castrillo and Wettstein [2005]) for economies with three or less agents.; We gratefully acknowledge financial support from project BEC 2003-01133, the Generalitat de Catalunya (2001 SGR-00162 and Barcelona Economics, CREA), and the Israeli Science Foundation.

An Ordinal Shapley Value for Economic Environments [Revised Version]

Pérez-Castrillo, David; Wettstein, David
Fonte: Elsevier Publicador: Elsevier
Tipo: Documento de trabajo
Português
Relevância na Pesquisa
68.347227%
Revised Version of the Paper UFAE and IAE Working Papers nr. 560.03. Published in the Journal of Economic Theory, Vol. 127, Issue 1, March 2006, Pages 296-308.; We propose a new solution concept to address the problem of sharing a surplus among the agents generating it. The problem is formulated in the preferences-endowments space. The solution is defined recursively, incorporating notions of consistency and fairness and relying on properties satisfied by the Shapley value for Transferable Utility (TU) games. We show a solution exists, and call it the Ordinal Shapley value (OSV). We characterize the OSV using the notion of coalitional dividends, and furthermore show it is monotone and anonymous. Finally, similarly to the weighted Shapely value for TU games, we construct a weighted OSV as well.

Bidding For The Surplus: A Non-Cooperative Approach To The Shapley Value

Pérez-Castrillo, David; Wettstein, David
Fonte: Conselho Superior de Investigações Científicas Publicador: Conselho Superior de Investigações Científicas
Tipo: Documento de trabajo
Português
Relevância na Pesquisa
68.20538%
We propose a simple mechanism to determine how the surplus generated by cooperation is to be shared in zero-monotonic environments with transferable utility. The mechanism consists of a bidding stage followed by a proposal stage. We show that the subgame perfect equilibrium outcomes of this mechanism coincide with the vector of the Shapley value payoffs. We extend our results to implement the weighted Shapley values. Finally, we generalize our mechanism to handle arbitrary transferable utility environments. The modified mechanism generates an efficient coalition structure, and implements the Shapley values of the super-additive cover of the environment.; Pérez-Castrillo acknowledges financial support from the DGES PB 97-0181 and SGR 96-75. Part of this research was conducted while Wettstein was visiting the Universitat Autònoma de Barcelona, with a grant from the Generalitat de Catalunya, and both authors were visiting the University of Copenhagen, whose financial support is acknowledged.

An Ordinal Shapley Value for Economic Environments

Pérez-Castrillo, David; Wettstein, David
Fonte: Conselho Superior de Investigações Científicas Publicador: Conselho Superior de Investigações Científicas
Tipo: Documento de trabajo
Português
Relevância na Pesquisa
68.315195%
We propose a new solution concept to address the problem of sharing a surplus among the agents generating it. The sharing problem is formulated in the preferences-endowments space. The solution is defined in a recursive manner incorporating notions of consistency and fairness and relying on properties satisfied by the Shapley value for Transferable Utility (TU) games. We show a solution exists, and refer to it as an Ordinal Shapley value (OSV). The OSV associates with each problem an allocation as well as a matrix of concessions "measuring" the gains each agent foregoes in favor of the other agents. We analyze the structure of the concessions, and show they are unique and symmetric. Next we characterize the OSV using the notion of coalitional dividends, and furthermore show it is monotone in an agent's initial endowments and satisfies anonymity. Finally, similarly to the weighted Shapley value for TU games, we construct a weighted OSV as well.; Pérez-Castrillo gratefully acknowledges financial support from projects BEC 2000-0172 and 2001 SGR-00162. Part of this research was conducted while Wettstein was visiting the Universitat Autònoma de Barcelona, with a grant from the Generalitat de Catalunya.; Peer reviewed

An ordinal shapley value for economic environments (Revised version)

Pérez Castrillo, David; Wettstein, David
Fonte: Universidade Autônoma de Barcelona Publicador: Universidade Autônoma de Barcelona
Tipo: Trabalho em Andamento Formato: application/pdf
Publicado em //2006 Português
Relevância na Pesquisa
48.001787%
We propose a new solution concept to address the problem of sharing a surplus among the agents generating it. The problem is formulated in the preferences-endowments space. The solution is defined recursively, incorporating notions of consistency and fairness and relying on properties satisfied by the Shapley value for Transferable Utility (TU) games. We show a solution exists, and call it the Ordinal Shapley value (OSV). We characterize the OSV using the notion of coalitional dividends, and furthermore show it is monotone and anonymous. Finally, similarly to the weighted Shapely value for TU games, we construct a weighted OSV as well.

An ordinal shapley value for economic environments

Pérez Castrillo, David; Wettstein, David
Fonte: Universidade Autônoma de Barcelona Publicador: Universidade Autônoma de Barcelona
Tipo: Trabalho em Andamento Formato: application/pdf
Publicado em //2006 Português
Relevância na Pesquisa
48.162188%
We propose a new solution concept to address the problem of sharing a surplus among the agents generating it. The sharing problem is formulated in the preferences-endowments space. The solution is defined in a recursive manner incorporating notions of consistency and fairness and relying on properties satisfied by the Shapley value for Transferable Utility (TU) games. We show a solution exists, and refer to it as an Ordinal Shapley value (OSV). The OSV associates with each problem an allocation as well as a matrix of concessions ``measuring'' the gains each agent foregoes in favor of the other agents. We analyze the structure of the concessions, and show they are unique and symmetric. Next we characterize the OSV using the notion of coalitional dividends, and furthermore show it is monotone in an agent's initial endowments and satisfies anonymity. Finally, similarly to the weighted Shapley value for TU games, we construct a weighted OSV as well.

Proposta metodológica de cobrança pelo uso dos recursos hídricos usando o valor de Shapley: uma aplicação à bacia do rio Paraíba do Sul

Leite, Gil Bracarense; Vieira, Wilson da Cruz
Fonte: Universidade de São Paulo. Faculdade de Economia, Administração e Contabilidade Publicador: Universidade de São Paulo. Faculdade de Economia, Administração e Contabilidade
Tipo: info:eu-repo/semantics/article; info:eu-repo/semantics/publishedVersion; Formato: application/pdf
Publicado em 01/09/2010 Português
Relevância na Pesquisa
58.098994%
This study aimed to propose a methodology for charging for the use of water resources based on the allocation of costs - among sectors that demand water - of projects related to improvements in a river basin. This methodology consists of a rule of allocation known as Shapley value, belonging to the theory of cooperative games, and to show its applicability, we performed a case study in a sub-basin of the Paraíba do Sul river basin. As criteria for allocation of costs, we used the volumes of water withdrawn and consumed, and the amount of effluent discharged into the river. In applying the methodology, we considered three different scenarios: "clean" basin, polluted basin, and an intermediate situation, closer to real situation now found in the sub-basin analyzed. The obtained results showed high dependence of the cost allocation criteria (weights assigned to the volumes of water withdrawn and consumed, and the quantity of effluent discharged), and, in the case of intermediate scenario considered, the values found indicate that the urban users should pay the greatest part of the costs when compared to the fees currently in use, since these users are among those that greatly discharge effluents, being the deterioration of water quality the most relevant problem in this basin.; Este trabalho teve como objetivo propor uma metodologia de cobrança pelo uso de recursos hídricos baseada na alocação de custos - entre os setores demandantes de água - de projetos relacionados com melhorias em uma bacia hidrográfica. Essa metodologia consiste em regra de alocação conhecida como valor de Shapley...