The Shapley value for a fair division of group discounts for coordinating cooling loads
Autoři:
Sasan Maleki aff001; Talal Rahwan aff002; Siddhartha Ghosh aff003; Areej Malibari aff004; Daniyal Alghazzawi aff005; Alex Rogers aff006; Hamid Beigy aff001; Nicholas R. Jennings aff007
Působiště autorů:
Department of Computer Engineering, Sharif University of Technology, Tehran, Iran
aff001; Computer Science, New York University Abu Dhabi, Abu Dhabi, UAE
aff002; Electronics and Computer Science, University of Southampton, Southampton, United Kingdom
aff003; Computer Science Department, King Abdulaziz University, Jeddah, Saudi Arabia
aff004; Information Systems Department, King Abdulaziz University, Jeddah, Saudi Arabia
aff005; Department of Computer Science, Oxford University, Oxford, United Kingdom
aff006; Department of Computing, Imperial College London, Oxford, United Kingdom
aff007
Vyšlo v časopise:
PLoS ONE 15(1)
Kategorie:
Research Article
doi:
https://doi.org/10.1371/journal.pone.0227049
Souhrn
We consider a demand response program in which a block of apartments receive a discount from their electricity supplier if they ensure that their aggregate load from air conditioning does not exceed a predetermined threshold. The goal of the participants is to obtain the discount, while ensuring that their individual temperature preferences are also satisfied. As such, the apartments need to collectively optimise their use of air conditioning so as to satisfy these constraints and minimise their costs. Given an optimal cooling profile that secures the discount, the problem that the apartments face then is to divide the total discounted cost in a fair way. To achieve this, we take a coalitional game approach and propose the use of the Shapley value from cooperative game theory, which is the normative payoff division mechanism that offers a unique set of desirable fairness properties. However, applying the Shapley value in this setting presents a novel computational challenge. This is because its calculation requires, as input, the cost of every subset of apartments, which means solving an exponential number of collective optimisations, each of which is a computationally intensive problem. To address this, we propose solving the optimisation problem of each subset suboptimally, to allow for acceptable solutions that require less computation. We show that, due to the linearity property of the Shapley value, if suboptimal costs are used rather than optimal ones, the division of the discount will be fair in the following sense: each apartment is fairly “rewarded” for its contribution to the optimal cost and, at the same time, is fairly “penalised” for its contribution to the discrepancy between the suboptimal and the optimal costs. Importantly, this is achieved without requiring the optimal solutions.
Klíčová slova:
Algorithms – Conditioned response – Electricity – Game theory – Games – Memory – Optimization – Payment
Zdroje
1. US Department of Energy. Grid 2030: A National Vision For Electricity’s Second 100 Years. United States of America Department of Energy; 2008.
2. Ramchurn SD, Vytelingum P, Rogers A, Jennings NR. Putting the “smarts” into the Smart Grid: A Grand Challenge for Artificial Intelligence. Communications of the ACM. 2012;55(4):86–97. doi: 10.1145/2133806.2133825
3. Dutta G, Mitra K. A literature review on dynamic pricing of electricity. Journal of the Operational Research Society. 2017;68(10):1131–1145. doi: 10.1057/s41274-016-0149-4
4. Quillinan JD. Pricing for retail electricity. Journal of Revenue and Pricing Management. 2011;10(6):545–555. doi: 10.1057/rpm.2011.22
5. Simshauser P, Downer D. On the Inequity of Flat-rate Electricity Tariffs. The Energy Journal. 2016;0 (3). doi: 10.5547/01956574.37.3.psim
6. McNeil MA, Letschert VE. Future Air Conditioning Energy Consumption in Developing Countries and what can be done about it: The Potential of Efficiency in the Residential Sector. Lawrence Berkeley National Laboratory. 2008;.
7. Yuan-Yih Hsu, Chung-Ching Su. Dispatch of direct load control using dynamic programming. IEEE Transactions on Power Systems. 1991;6(3):1056–1061. doi: 10.1109/59.119246
8. Dong L, Falvey R, Luckraz S. Fair share and social efficiency: A mechanism in which peers decide on the payoff division. Games and Economic Behavior. 2019;115:209–224. doi: 10.1016/j.geb.2019.02.016
9. Battaglini M, Nunnari S, Palfrey TR. The Dynamic Free Rider Problem: A Laboratory Study. American Economic Journal: Microeconomics. 2016;8(4):268–308.
10. Chakraborty P, Baeyens E, Poolla K, Khargonekar PP, Varaiya P. Sharing Storage in a Smart Grid: A Coalitional Game Approach. IEEE Transactions on Smart Grid. 2019;10(4):4379–4390. doi: 10.1109/TSG.2018.2858206
11. Chakraborty P, Baeyens E, Khargonekar PP. Cost Causation Based Allocations of Costs for Market Integration of Renewable Energy. IEEE Transactions on Power Systems. 2018;33(1):70–83. doi: 10.1109/TPWRS.2017.2690404
12. Chakraborty P, Baeyens E, Khargonekar PP, Poolla K. A cooperative game for the realized profit of an aggregation of renewable energy producers. In: 2016 IEEE 55th Conference on Decision and Control (CDC); 2016. p. 5805–5812.
13. Zhou Q, Shahidehpour M, Sun T, Feng D, Yan M. Cooperative Game for Carbon Obligation Allocation Among Distribution System Operators to Incentivize the Proliferation of Renewable Energy. IEEE Transactions on Smart Grid. 2019;10(6):6355–6365. doi: 10.1109/TSG.2019.2903686
14. Aghajani S, Kalantar M. A cooperative game theoretic analysis of electric vehicles parking lot in smart grid. Energy. 2017;137:129–139. doi: 10.1016/j.energy.2017.07.006
15. Airiau S. Cooperative games and multiagent systems. The Knowledge Engineering Review. 2013;28(4):381–424. doi: 10.1017/S0269888913000106
16. Fang Q. In: Kao MY, editor. Complexity of Core. New York, NY: Springer New York; 2016. p. 372–375.
17. Greco G, Malizia E, Palopoli L, Scarcello F. On the complexity of core, kernel, and bargaining set. Artificial Intelligence. 2011;175(12):1877–1910. doi: 10.1016/j.artint.2011.06.002
18. Maschler M, Solan E, Zamir S. In: The bargaining set. Cambridge University Press; 2013. p. 782–800.
19. Shapley L. A value for n-person games. Contributions to the theory of games. 1953; p. 307–317.
20. Maleki S, Tran-Thanh L, Hines G, Rahwan T, Rogers A. Bounding the Estimation Error of Sampling-based Shapley Value Approximation. In: The Fifth Workshop on Cooperative Games in Multiagent Systems (CoopMAS); 2014.
21. Mann I, Shapley L. Values for large games IV: Evaluating the electoral college exactly. RAND Corporation; 1962. RM-3158-PR.
22. Owen G. Multilinear Extensions of Games. Management Science. 1972;18(5):64–79. doi: 10.1287/mnsc.18.5.64
23. Bachrach Y, Markakis E, Resnick E, Procaccia AD, Rosenschein JS, Saberi A. Approximating power indices: theoretical and empirical analysis. Autonomous Agents and Multi-Agent Systems. 2010;20(2):105–122. doi: 10.1007/s10458-009-9078-9
24. Shaheen F, Jennings NR. A Linear Approximation Method for the Shapley Value. Artificial Intelligence Journal. 2008;172(14):1673–1699. doi: 10.1016/j.artint.2008.05.003
25. Sandholm TW, Lesser VR. Coalitions Among Computationally Bounded Agents. Artificial Intelligence. 1997;94(1-2):99–137. doi: 10.1016/S0004-3702(97)00030-1
26. Thrall RM, Lucas WF. N-person games in partition function form. Naval Research Logistics Quarterly. 1963;10(1):281–298. doi: 10.1002/nav.3800100126
27. Y Guo GP R Li, Zeman A. A Simulator for Self-Adaptive Energy Demand Management. In: Proceedings of the 2nd IEEE International Conference on Self-Adaptive and Self-Organizing Systems; 2008. p. 64–73.
28. Rogers A, Maleki S, Ghosh S, Jennings NR. Adaptive Home Heating Control Through Gaussian Process Prediction and Mathematical Programming. In: The Second International Workshop on Agent Technologies for Energy Systems (ATES), The 10th International Conference on Autonomous Agents and Multiagent Systems; 2011.
29. Andersen K, Madsen H, Hansen L. Modelling the Heat Dynamics of a Building using Stochastic Differential Equations. Energy and Buildings. 2000;31(1):13–24. doi: 10.1016/S0378-7788(98)00069-3
30. Bacher P, Madsen H. Identifying Suitable Models for the Heat Dynamics of Buildings. Energy and Buildings. 2011;43(7):1511–1522. doi: 10.1016/j.enbuild.2011.02.005
31. Simon D. Optimal State Estimation: Kalman, H Infinity, and Nonlinear Approaches. New York, NY, USA: Wiley-Interscience; 2006.
32. Aswani A, Master N, Taneja J, Culler DE, Tomlin C. Reducing Transient and Steady State Electricity Consumption in HVAC Using Learning-Based Model-Predictive Control. Proceedings of the IEEE. 2012;100(1):240–253. doi: 10.1109/JPROC.2011.2161242
33. Alam M, Ramchurn S, Rogers A. Cooperative Energy Exchange for the Efficient Use of Energy and Resources in Remote Communities. In: Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS). AAMAS’13. International Foundation for Autonomous Agents and Multiagent Systems; 2013. p. 731–738.
34. Aziz H, Cahan C, Gretton C, Kilby P, Mattei N, Walsh T. A Study of Proxies for Shapley Allocations of Transport Costs. Journal of Artificial Intelligence Research. 2016;56(1):573–611. doi: 10.1613/jair.5021
Článek vyšel v časopise
PLOS One
2020 Číslo 1
- Proč se v Česku šíří několik „vymýcených“ infekcí najednou? Ptáme se odborníků
- ADHD jako evoluční výhoda? Výzkum se zaměřil na lovce a sběrače
- Není migréna jako migréna: Co pociťují ženy a co muži?
- Metamizol jako analgetikum první volby: kdy, pro koho, jak a proč?
- Není statin jako statin aneb praktický přehled rozdílů jednotlivých molekul
Nejčtenější v tomto čísle
- Severity of misophonia symptoms is associated with worse cognitive control when exposed to misophonia trigger sounds
- Chemical analysis of snus products from the United States and northern Europe
- Calcium dobesilate reduces VEGF signaling by interfering with heparan sulfate binding site and protects from vascular complications in diabetic mice
- Effect of Lactobacillus acidophilus D2/CSL (CECT 4529) supplementation in drinking water on chicken crop and caeca microbiome
Zvyšte si kvalifikaci online z pohodlí domova
Všechny kurzy