On the Dialectics of Computational Economics: A Synthesis of Distributed System and Game Theory
·
Disclaimer: This article is part of the Industry 4.0 Open Educational Resources (OER) Publication Initiatives jointly supported by Duke Learning Innovation Center and DKU Center for Teaching and Learning under the Carrying the Innovation Forward program. This article belongs to the OER Series No. 2 Computational Economics Spring 2022 collection. The Spring 2022 collection is partly supported by the Social Science Divisional Chair’s Discretionary Fund to encourage faculty engagement in undergraduate research and enhance student-faculty scholarly interactions outside of the classroom. The division chair is Prof. Keping Wu, Associate Professor of Anthropology at Duke Kunshan University. The co-author Xinyu Tian was the Teaching and Research Assistant for Prof. Luyao Zhang in the course: COMPSCI/ECON 206 Computational Microeconomics at Duke Kunshan University in Spring 2022, when he completed the joint article. The co-authors are forever indebted to Prof. Vincent Conitzer, who presented “Computer Science Meets Economics” as a distinguished guest lecture for this course on Apr. 19, 2022.
In the German philosopher Hegel’s famous dialectics, he “takes us through the well-known dialectic, whereby “being” gives way before its opposite, “nothing”, and the two are united in “becoming” (Habib 2018).” In similar spirits, we reason how the opposites in computational and economic science, precisely distributed system and game theory, drive the advancement of each other and meet in the synthesis of the two.
Part I: Interpret Game Theory in Distributed Systems
Interpreting Game Theory in the distributed system is complex. As defined by Coulouris et al. (2012), a distributed system is one in which hardware or software components located in computer networks communicate and coordinate their actions by passing messages. Computer scientists focus on the operation of system processors and the maintenance of security; In contrast, game theorists suggest enhancing the system operation by considering human agents’ rationality and reaction to incentives: i.e. a game theoretical approach is helpful when modeling problems in distributed systems involving human agents (Abraham, Alvisi, and Halpern 2011).
Figure 1: The Yin and Yang in Distributed System and Game Theory
Tables 1 and 2 show the important milestones of intellectual advancements in distributed systems and game theory.
1992: For contributions to the development of distributed, personal computing environments and the technology for their implementation: workstations, networks, operating systems, programming systems, displays, security, and document publishing.
2008: For contributions to practical and theoretical foundations of programming language and system design, especially related to data abstraction, fault tolerance, and distributed computing.
2009: For the pioneering design and realization of the first modern personal computer -- the Alto at Xerox PARC -- and seminal inventions and contributions to local area networks (including the Ethernet), multiprocessor workstations, snooping cache coherence protocols, and tablet personal computers.
2013: For fundamental contributions to the theory and practice of distributed and concurrent systems, notably the invention of concepts such as causality and logical clocks, safety and liveness, replicated state machines, and sequential consistency.
1944: The publication of the book “Theory of Games and Economic Behavior” by mathematician John von Neumann and economist Oskar Morgenstern by Princeton University Press, the groundbreaking text that created the interdisciplinary research field of game theory.
John F. Nash
1951: John F. Nash Nobel Prize Laureate in 1994, introduced the distinction between cooperative games, in which binding agreements can be made, and non-cooperative games, where binding agreements are not feasible. Nash developed an equilibrium concept for non-cooperative games that later came to be called Nash Equilibrium.
1965: Reinhard Selten, Nobel Prize Laureate in 1994, was the first to refine the Nash Equilibrium concept for analyzing dynamic strategic interaction. He has also applied these refined concepts to analyses of competition with only a few sellers.
2005: Thomas C. Schelling, Nobel Prize Laureate 2005, Prize motivation: “for having enhanced our understanding of conflict and cooperation through game-theory analysis, prompted new developments in game theory and accelerated its use and application through social science.
2005: Robert J. Aumann, Nobel Prize Laureate in 2005, was the first to conduct a full-fledged formal analysis of so-called infinitely repeated games. His research identified exactly what outcomes can be upheld over time in long-run relations.
We now interpret game theory in distributed systems in the three facets: agent, environment, and solution concepts.
1.1. Agent
Agents in distributed systems, by convention, are assumed to be either honest or malicious. The honest is to follow the rules, and the malicious is to damage the system regardless of the cost and benefits. The analysis of the two types widely appears in the fault tolerance problems of cybersecurity to analyze the bound of the negative impact of malicious agents. The computer science literature often reasons the malicious processors as random facts caused by system operation and increasing software complexity (Castro and Liskov 2002). In contrast, economists model agents’ reaction to incentives, to be either rational, bounded rational, or behavioral, where malicious and honest are sublate into two types of behavioral agents (Linial 1994, Cooper 2007, Farhi and Gabaix 2020). The extended interpretation of agents paves the foundation for applying game theory to distributed systems. For instance, game theoretical research provides the boundaries of fault tolerance in multi-party communication and rational secret-sharing problems involving coalitions of rational and malicious players (Abraham et al. 2006, Halpern 2021).
1.2. Environment.
The game environment in distributed systems belongs to network games. As defined by Jackson and Zenou (2015), network games focus on players who are connected via a network structure. Following the convention in game theory, we can divide the network games into cooperative and non-cooperative games based on whether a binding agreement is feasible or not.
1.2.1. Cooperative games.
A game is cooperative if the players are able to form binding commitments externally enforced (Chatain 2018). However, non-cooperative games are more commonly used to solve cooperative issues in establishing distributed system security and privacy (Aiyer et al. 2005, Manshaei et al. 2013). For example, the folk theorem in non-cooperative games demonstrates how miners on Bitcoin are incentivized to cooperatively build the longest chain rather than do solo work and create forks (Biais et al. 2019).
Perfect Bayesian Equilibrium (PBE) is the most widely used solution concept for dynamic games of imperfect information. For example, Amoussou-Guenou et al. (2020) apply PBE to analyze the strategic interactions and outcomes in the voting games of blockchain consensus. In evaluating the strategic outcome based on solution concepts, economists often care about social welfare maximization or Pareto efficiency (Pradelski and Young 2012) beyond the security of distributed systems.
Part II: Design Incentives in Distributed Systems
Incentives are at the center of applying game theoretical analysis to distributed systems. Table 3 shows several representative examples of incentives in distributed systems. Future protocol design of distributed systems shall consider the set of rewards and punishments that incentivize agents to achieve desired outcomes of security, privacy, and (Pareto) efficiency.
“A.M. Turing Award Winner Research Subjects.” n.d. Amturing.acm.org. Accessed June 10, 2022. https://amturing.acm.org/bysubject.cfm.
Abraham, Ittai, Lorenzo Alvisi, and Joseph Y. Halpern. 2011. “Distributed Computing Meets Game Theory.” ACM SIGACT News 42 (2): 69–76. https://doi.org/10.1145/1998037.1998055.
Abraham, Ittai, Danny Dolev, Rica Gonen, and Joe Halpern. 2006. “Distributed Computing Meets Game Theory.” Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing - PODC ’06. https://doi.org/10.1145/1146381.1146393.
Abraham, Ittai, Danny Dolev, and Joseph Y. Halpern. 2019. “Distributed Protocols for Leader Election.” ACM Transactions on Economics and Computation 7 (1): 1–26. https://doi.org/10.1145/3303712.
Aiyer, Amitanand S., Lorenzo Alvisi, Allen Clement, Mike Dahlin, Jean-Philippe Martin, and Carl Porth. 2005. “BAR Fault Tolerance for Cooperative Services.” Proceedings of the Twentieth ACM Symposium on Operating Systems Principles - SOSP ’05. https://doi.org/10.1145/1095810.1095816.
Amoussou-Guenou, Yackolley, Bruno Biais, Maria Potop-Butucaru, and Sara Tucci-Piergiovanni. 2020. “Rational Behavior in Committee-Based Blockchains.” HAL Archives Ouvertes. June 1, 2020. https://hal.archives-ouvertes.fr/hal-02867095.
Biais, Bruno, Christophe Bisière, Matthieu Bouvard, and Catherine Casamatta. 2019. “The Blockchain Folk Theorem.” The Review of Financial Studies 32 (5): 1662–1715. https://doi.org/10.1093/rfs/hhy095.
Castro, Miguel, and Barbara Liskov. 2002. “Practical Byzantine Fault Tolerance and Proactive Recovery.” ACM Transactions on Computer Systems 20 (4): 398–461. https://doi.org/10.1145/571637.571640.
Chatain, Olivier. 2018. “Cooperative and Non-Cooperative Game Theory.” The Palgrave Encyclopedia of Strategic Management, 345–46. https://doi.org/10.1057/978-1-137-00772-8_468.
Cooper, David J. 2007. “An Introduction to the Symposium on Behavioral Game Theory.” Economic Theory 33 (1): 1–10. https://doi.org/10.1007/s00199-007-0220-0.
Coulouris, George F, Jean Dollimore, Tim Kindberg, and Gordon Blair. 2012. Distributed Systems: Concepts and Design. Boston: Addison-Wesley. https://repository.dinus.ac.id/docs/ajar/George-Coulouris-Distributed-Systems-Concepts-and-Design-5th-Edition.pdf.
Farhi, Emmanuel, and Xavier Gabaix. 2020. “Optimal Taxation with Behavioral Agents.” American Economic Review 110 (1): 298–336. https://doi.org/10.1257/aer.20151079.
Grosu, Daniel, and Anthony T. Chronopoulos. 2005. “Noncooperative Load Balancing in Distributed Systems.” Journal of Parallel and Distributed Computing 65 (9): 1022–34. https://doi.org/10.1016/j.jpdc.2005.05.001.
Halpern, Joseph. 2021. “Distributed Computing Meets Game Theory: Fault Tolerance and Implementation with Cheap Talk.” Simons Institute for the Theory of Computing. February 16, 2021. https://simons.berkeley.edu/talks/tbd-272.
Ishai Menache, and Asuman E Ozdaglar. 2011. Network Games: Theory, Models, and Dynamics. San Rafael, Calif.: Morgan & Claypool. https://www.morganclaypool.com/doi/pdf/10.2200/S00330ED1V01Y201101CNT009.
Jackson, Matthew O., and Yves Zenou. 2015. “Games on Networks.” Handbook of Game Theory with Economic Applications 4: 95–163. https://doi.org/10.1016/b978-0-444-53766-9.00003-3.
Jaggard, Aaron D., Neil Lutz, Michael Schapira, and Rebecca N. Wright. 2017. “Dynamics at the Boundary of Game Theory and Distributed Computing.” ACM Transactions on Economics and Computation 5 (3): 1–20. https://doi.org/10.1145/3107182.
Linial, Nathan. 1994. “Chapter 38 Game-Theoretic Aspects of Computing.” Handbook of Game Theory with Economic Applications 2: 1339–95. https://doi.org/10.1016/s1574-0005(05)80070-0.
Manshaei, Mohammad Hossein, Quanyan Zhu, Tansu Alpcan, Tamer Bacşar, and Jean-Pierre Hubaux. 2013. “Game Theory Meets Network Security and Privacy.” ACM Computing Surveys 45 (3): 1–39. https://doi.org/10.1145/2480741.2480742.
Neumann, J. v. 1928. “Zur Theorie Der Gesellschaftsspiele.” Mathematische Annalen 100 (1): 295–320. https://doi.org/10.1007/bf01448847.
Osborne, Martin J, and Ariel Rubinstein. 1994. A Course in Game Theory. Cambridge, Mass.: Mit Press.
Penmatsa, Satish, and Anthony T. Chronopoulos. 2011. “Game-Theoretic Static Load Balancing for Distributed Systems.” Journal of Parallel and Distributed Computing 71 (4): 537–55. https://doi.org/10.1016/j.jpdc.2010.11.016.
Pradelski, Bary S.R., and H. Peyton Young. 2012. “Learning Efficient Nash Equilibria in Distributed Systems.” Games and Economic Behavior 75 (2): 882–97. https://doi.org/10.1016/j.geb.2012.02.017.
Silberschatz, Abraham, Greg Gagne, and Peter B Galvin. 2004. Operating System Concepts with Java. Hoboken, N.J.: John Wiley & Sons.
“The Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel 1994.” 2019. NobelPrize.org. 2019. https://www.nobelprize.org/prizes/economic-sciences/1994/press-release/.
Yates, Robin D.S. 1994. “The Yin-Yang Texts from Yinqueshan: An Introduction and Partial Reconstruction, with Notes on Their Significance in Relation to Huang-Lao Daoism.” Early China 19: 75–144. https://doi.org/10.1017/s0362502800003564.
Appendix A. Glossary Table
Glossary
Definition
References
Distributed system
One in which hardware or software components located at networked computers communicate and coordinate their actions only by passing messages.
Xinyu Tian is a rising senior majoring in Data Science at Duke Kunshan University (DKU) and a full-admission scholarship recipient at DKU. Her area of interest includes theory and applications about cooperative AI, blockchain trust and consensus, game theory, and computer vision. Her paper about meta-learning algorithms has been published at the 2021 International Conference on Computer Engineering and Application (ICCEA) and she was supported by the Summer Research Scholarship (SRS) program at Duke Kunshan University in 2021 and 2022. She is now working on her Signature Work about cooperative AI mentored by Prof. Luyao Zhang. Besides her academic interest, she also hopes to support the communication between academia and industry. So she is serving as Chair of Communication at SciEcon CIC and contributing to the industry 4.0 Open Educational Resources (OER).
Creative Commons Attribution 4.0 International License (CC-BY 4.0)
