The Shapley value for a fair division of group discounts for coordinating cooling loads

English version

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
prolekare.web.journal.doi_sk: 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 – Optimization – Memory – Games – Electricity – Conditioned response – Payment – Game theory

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

The Shapley value for a fair division of group discounts for coordinating cooling loads

Souhrn

Klíčová slova:

Zdroje

PLOS One

Aktuální možnosti diagnostiky a léčby litiáz