Back to search

University of Southampton

Addressing the computational issues of the Shapley value with applications in the smart grid

Abstract

dc:description.abstract

We consider the computational issues that arise in using the Shapley value in practical applications. Calculating the Shapley value involves computing the value of an exponential number of coalitions, which poses a significant computational challenge in two cases: (i) when the number of agents (players) is large (e.g., more than 20), and (ii) when the time complexity of the characteristic function is high. However, to date, researchers have aimed to address only the first case, although with limited success.<br/><br/>To address the first issue, we focus on approximating the Shapley value. In more detail, building upon the existing sampling-based approaches, we propose an improved error bound for approximating the Shapley value using simple random sampling (SRS), which can be used in any superadditive game. Moreover, we put forward the use of stratified sampling, which can lead to smaller standard errors. We propose two methods for minimising the standard error in supermodular games and a class of games that have a property that we call order-reflecting. We show that among others, newsvendor games, which have applications in the smart grid, exhibit this property. Furthermore, to evaluate our approach, we apply our stratified sampling methods to an instance of newsvendor games consisting of 100 agents using real data. We find that the standard error of stratified sampling in our experiments is on average 48% lower than that of SRS.<br/><br/>To address the second issue, we propose the characteristic function of the game be approximated. This way, calculating the Shapley value becomes straightforward. However, in order to maintain fairness, we argue that, in distributing the value of the grand coalition, agents' contribution to the complexity of the characteristic function must be taken into account. As such, we propose the bounded rational Shapley value, which, using the additivity axiom of the Shapley value, ensures that the share of each agent reflects its contribution to the difficulty of computing the coalition values. We demonstrate the usefulness of this approach in a demand response scenario where a number of apartments want to fairly divide the discount they receive for coordinating their cooling loads.<br/>

Degree

thesis:*
Name dc:type.qualificationname
Ph.D.
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of Southampton
Year dc:date.issued
2015

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Maleki, Sasan
Advisor dc:contributor.advisor
  • Rogers, Alex

Rights

Language dc:language
English, eng

Chain of custody

source
Harvested from
University of Southampton
Base URL
eprints.soton.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Maleki, Sasan. Addressing the computational issues of the Shapley value with applications in the smart grid. doctoral thesis, University of Southampton, 2015.