Decentralized Collective Learning for Self-managed Sharing Economies

Abstract

The Internet of Things equips citizens with a phenomenal new means for online participation in sharing economies. When agents self-determine options from which they choose, for instance, their resource consumption and production, while these choices have a collective systemwide impact, optimal decision-making turns into a combinatorial optimization problem known as NP-hard. In such challenging computational problems, centrally managed (deep) learning systems often require personal data with implications on privacy and citizens’ autonomy. This article envisions an alternative unsupervised and decentralized collective learning approach that preserves privacy, autonomy, and participation of multi-agent systems self-organized into a hierarchical tree structure. Remote interactions orchestrate a highly efficient process for decentralized collective learning. This disruptive concept is realized by I-EPOS, the Iterative Economic Planning and Optimized Selections, accompanied by a paradigmatic software artifact. Strikingly, I-EPOS outperforms related algorithms that involve non-local brute-force operations or exchange full information. This article contributes new experimental findings about the influence of network topology and planning on learning efficiency as well as findings on techno-socio-economic tradeoffs and global optimality. Experimental evaluation with real-world data from energy and bike sharing pilots demonstrates the grand potential of collective learning to design ethically and socially responsible participatory sharing economies.

References

1. Mohammad Alaggan, Sébastien Gambs, and Anne-Marie Kermarrec. 2011. Private Similarity Computation in Distributed Systems: From Cryptography to Differential Privacy. Springer, Berlin, 357--377.
2. Zeyuan Allen-Zhu and Elad Hazan. 2016. Variance reduction for faster non-convex optimization. In Proceedings of the International Conference on Machine Learning. 699--707.
3. Kevin Beyer, Jonathan Goldstein, Raghu Ramakrishnan, and Uri Shaft. 1999. When is “nearest neighbor” meaningful? In Proceedings of the International Conference on Database Theory. Springer, 217--235.
4. Stefan Bosse. 2017. Incremental distributed learning with javascript agents for earthquake and disaster monitoring. Int. J. Distrib. Syst. Technol. 8, 4 (2017), 34--53.
5. Arthur Earl Bryson and Yu-Chi Ho. 1969. Applied Optimal Control: Optimization, Estimation and Control. Xerox College Publishing.
6. Antonio Bucchiarone, Martina De Sanctis, and Annapaola Marconi. 2016. Decentralized dynamic adaptation for service-based collective adaptive systems. In Proceedings of the International Conference on Service-Oriented Computing. Springer, Berlin, 5--20.
7. Javier Cámara, David Garlan, Bradley Schmerl, and Ashutosh Pandey. 2015. Optimal planning for architecture-based self-adaptation via model checking of stochastic games. In Proceedings of the 30th Annual ACM Symposium on Applied Computing (SAC’15). ACM, New York, NY, 428--435.
8. Ernest J. J. H. H. Chang. 1982. Echo algorithms: Depth parallel operations on general graphs. IEEE Trans. Softw. Eng. 8, 4 (1982), 391.
9. Anton Chechetka and Katia Sycara. 2006. No-commitment branch and bound search for distributed constraint optimization. In Proceedings of the 5th International Joint Conference on Autonomous Agents and Multiagent Systems. ACM, 1427--1429.
10. Cyrille Médard de Chardon, Geoffrey Caruso, and Isabelle Thomas. 2016. Bike-share rebalancing strategies, patterns, and purpose. J. Transport Geogr. 55 (2016), 22--39.
11. Li Deng, Dong Yu, et al. 2014. Deep learning: Methods and applications. Found. Trends Sign. Process. 7, 3--4 (2014), 197--387.
12. Frederick Ducatelle, Gianni Di Caro, and Luca Maria Gambardella. 2005. Using ant agents to combine reactive and proactive strategies for routing in mobile ad-hoc networks. Int. J. Comput. Intell. Appl. 5, 2 (2005), 169--184.
13. Ivana Dusparic and Vinny Cahill. 2009. Distributed w-learning: Multi-policy optimization in self-organizing systems. In Proceedings of the 2009 3rd IEEE International Conference on Self-Adaptive and Self-Organizing Systems. IEEE, 20--29.
14. Judith Fröhling. 2017. Abstract Flexibility Description for Virtual Power Plant Scheduling. Ph.D. Dissertation. BIS der Universität Oldenburg.
15. Wojciech Galuba, Karl Aberer, Zoran Despotovic, and Wolfgang Kellerer. 2009. ProtoPeer: A P2P toolkit bridging the gap between simulation and live deployement. In Proceedings of the 2nd International Conference on Simulation Tools and Techniques. Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, 60.
16. Reza GhasemAghaei, Md Abdur Rahman, Wail Gueaieb, and Abdulmotaleb El Saddik. 2007. Ant colony-based reinforcement learning algorithm for routing in wireless sensor networks. In Proceedings of the 2007 IEEE Instrumentation 8 Measurement Technology Conference (IMTC’07). IEEE, 1--6.
17. Ian Goodfellow, Yoshua Bengio, and Aaron Courville. 2016. Deep Learning. MIT Press, Cambridge, MA.
18. Sara Hajian, Francesco Bonchi, and Carlos Castillo. 2016. Algorithmic bias: From discrimination discovery to fairness-aware data mining. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2125--2126.
19. Dirk Helbing, Bruno S. Frey, Gerd Gigerenzer, Ernst Hafen, Michael Hagner, Yvonne Hofstetter, Jeroen van den Hoven, Roberto V. Zicari, and Andrej Zwitter. 2017. Will democracy survive big data and artificial intelligence. Sci. Am. 25 (2017).
20. Dirk Helbing and Evangelos Pournaras. 2015. Society: Build digital democracy. Nature 527 (2015), 33--34.
21. Christian Hinrichs, Sebastian Lehnhoff, and Michael Sonnenschein. 2013. COHDA: A combinatorial optimization heuristic for distributed agents. In Proceedings of the International Conference on Agents and Artificial Intelligence. Springer, 23--39.
22. Christian Hinrichs, Sebastian Lehnhoff, and Michael Sonnenschein. 2014. A decentralized heuristic for multiple-choice combinatorial optimization problems. In Proceedings of the Annual Conference on Operations Research 2012. Springer, 297--302.
23. Honglin Hu, Jian Zhang, Xiaoying Zheng, Yang Yang, and Ping Wu. 2010. Self-configuration and self-optimization for LTE networks. IEEE Commun. Mag. 48, 2 (2010), 94--100.
24. Aravind Kailas, Valentina Cecchi, and Arindam Mukherjee. 2012. A survey of communications and networking technologies for energy management in buildings and home automation. J. Comput. Netw. Commun. 2012 (2012).
25. Hongseok Kim, Young-Jin Kim, Kai Yang, and Marina Thottan. 2011. Cloud-based demand response for smart grid: Architecture and distributed algorithms. In Proceedings of the 2011 IEEE International Conference on Smart Grid Communications (SmartGridComm’11). IEEE, 398--403.
26. Stefan Korff and Rainer Böhme. 2014. Too much choice: End-user privacy decisions in the context of choice proliferation. In Proceedings of the Symposium on Usable Privacy and Security (SOUPS’14). 69--87.
27. Marinos Koutsomichalis and Evangelos Pournaras. 2017. The sound of decentralization-sonifying computational intelligence in sharing economies. In Proceedings of the 23rd International Symposium on Electronic Art (ISEA’17).
28. Yung-Ming Li, Yong Tan, and Prabuddha De. 2013. Self-organized formation and evolution of peer-to-peer networks. INFORMS J. Comput. 25, 3 (2013), 502--516.
29. Ashutosh Pandey, Gabriel A. Moreno, Javier Cámara, and David Garlan. 2016. Hybrid planning for decision making in self-adaptive systems. In Proceedings of the 10th International Conference on Self-adaptive and Self-organizing Systems. IEEE.
30. Payal V. Parmar, Shraddha B. Padhar, Shafika N. Patel, Niyatee I. Bhatt, and Rutvij H. Jhaveri. 2014. Survey of various homomorphic encryption algorithms and schemes. Int. J. Comput. Appl. 91, 8 (2014).
31. Adrian Petcu and Boi Faltings. 2005. A Scalable Method for Multiagent Constraint Optimization. In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI'05). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 266--271.
32. Peter Pilgerstorfer and Evangelos Pournaras. 2017. Self-adaptive learning in decentralized combinatorial optimization: A design paradigm for sharing economies. In Proceedings of the 12th International Symposium on Software Engineering for Adaptive and Self-Managing Systems. IEEE Press, 54--64.
33. Evangelos Pournaras. 2013. Multi-level Reconfigurable Self-organization in Overlay Services. Ph.D. Dissertation. TU Delft, Delft University of Technology.
34. Evangelos Pournaras, Ben-Elias Brandt, Manish Thapa, Dinesh Acharya, Jose Espejo-Uribe, Mark Ballandies, and Dirk Helbing. 2017a. SFINA-simulation framework for intelligent network adaptations. Simul. Model. Pract. Theory 72 (2017), 34--50.
35. Evangelos Pournaras and Jose Espejo-Uribe. 2017. Self-repairable smart grids via online coordination of smart transformers. IEEE Trans. Industr. Inf. 13, 4 (2017), 1783--1793.
36. Evangelos Pournaras, Matteo Vasirani, Robert E. Kooij, and Karl Aberer. 2014a. Decentralized planning of energy demand for the management of robustness and discomfort. IEEE Trans. Industr. Inf. 10, 4 (2014), 2280--2289.
37. Evangelos Pournaras, Matteo Vasirani, Robert E. Kooij, and Karl Aberer. 2014b. Measuring and controlling unfairness in decentralized planning of energy demand. In Proceedings of the 2014 IEEE International Energy Conference (ENERGYCON’14). IEEE, 1255--1262.
38. Evangelos Pournaras, Srivatsan Yadhunathan, and Ada Diaconescu. 2018. Holarchic Structures for Decentralized Deep Learning-A Performance Analysis. arXiv preprint arXiv:1805.02686 (2018). http://arxiv.org/abs/1805.02686
39. Evangelos Pournaras, Mark Yao, and Dirk Helbing. 2017b. Self-regulating supply--demand systems. Fut. Gener. Comput. Syst. 76 (2017), 73--91.
40. Jakob Puchinger and Günther R. Raidl. 2005. Combining metaheuristics and exact algorithms in combinatorial optimization: A survey and classification. In Proceedings of the International Work-Conference on the Interplay Between Natural and Artificial Computation. Springer, 41--53.
41. R. Tyrrell Rockafellar, Stanislav Uryasev, et al. 2000. Optimization of conditional value-at-risk. J. Risk 2 (2000), 21--42.
42. Ognjen Scekic, Hong-Linh Truong, and Schahram Dustdar. 2013. Incentives and rewarding in social computing. Commun. ACM 56, 6 (2013), 72--82.
43. Thure Traber and Claudia Kemfert. 2011. Gone with the wind? - Electricity market prices and incentives to invest in thermal power plants under increasing wind energy supply. Energy Econ. 33, 2 (2011), 249--256.
44. William Yeoh, Ariel Felner, and Sven Koenig. 2008. BnB-ADOPT: An asynchronous branch-and-bound DCOP algorithm. In Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems, Vol. 2. International Foundation for Autonomous Agents and Multiagent Systems, 591--598.

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

• Computing methodologies

  • Artificial intelligence

    • Distributed artificial intelligence

      • Cooperation and coordination

      • Multi-agent systems

    • Planning and scheduling

      • Multi-agent planning

      • Planning for deterministic actions

  • Distributed computing methodologies

    • Distributed algorithms

• Networks

  • Network properties

    • Network manageability

    • Network structure

  • Network services

    • In-network processing

    • Network management

  • Network types

    • Cyber-physical networks

    • Overlay and other logical network structures

      • Peer-to-peer networks