Designing Algorithms for Cooperation

--- tags: Algorithm Analysis --- # Designing Algorithms for Cooperation (from a lecture in my Algorithm Analysis course, March 28, 2024) --- *Thought is a social endeavour.* (Sloman & Fernbach) *The human mind evolved to be embedded in a community.* (Sloman & Fernbach) *Reasons are primarily for social consumption.* (Mercier & Sperber) *Language lays down tracks on which thoughts can travel.* (Daniel Dennett) *Your conscious understanding of your mind is an interpretation or narration that flows effortlessly from non-conscious processes*. (LeDoux) --- ## Introduction The traditional view of algorithm design: Algorithms satisfying their specification ... testing ... verification ... [Typically](https://www.cs.princeton.edu/~wayne/kleinberg-tardos/), algorithm design is taught by examples. This works well as long as we (humans) can say clearly by example what we want ... say, we want a compiler, a spreadsheet, a large language model, etc But: - How should we design algorithms that will interact with people in an open and unpredictable[^unpredictable] way? - How can we design algorithms that support people to cooperate? I am thinking of social media, blogging, content moderation, deliberating, trading, etc. **Example (Decentralized Social Media):** A substantial software engineering effort is going into building decentralized, censorship resistant alternatives to Twitter and other social media. But while these are promising efforts, no alternative has been successful so far. Why? - The rest of these notes can be understood as my attempt to search for an answer. I strongly suspect that there are other reasons in addition to the obvious ones (lack of funding, "lazy" consumers). - One should carefully study proposed solutions. For now I list only some known software that has been attempting this (there is much more out there): - [Fediverse](https://en.wikipedia.org/wiki/Fediverse). "To put it simply, it’s as if there were a thousand Twitters, a thousand Facebooks, a thousand YouTubes, but they could all talk to each other and you would not need an account on each one." [FAQs](https://pleroma.social/blog/2021/01/13/the-big-pleroma-and-fediverse-faq/) - [Mastodon](https://joinmastodon.org/), [How It Works](https://www.youtube.com/watch?v=IPSbNdBmWKE&t=1s), - [Decode](http://decodeproject.eu/), [video](https://www.youtube.com/watch?v=_-ooCbgIiyo). In cooperation with the cities of Amsterdam and Barcelona. - [Solid](https://solidproject.org/). Created by Tim Berners-Lee. "Solid is a proposed set of conventions and tools for building decentralized social applications based on Linked Data principles." - [Nostr](https://nostr.com/) ... ["awesome" links](https://github.com/aljazceru/awesome-nostr) ... [Wikipedia](https://en.wikipedia.org/wiki/Nostr) - [Bluesky](https://en.wikipedia.org/wiki/Bluesky_(social_network)), [Farcaster](https://tkxcapital.medium.com/the-current-state-of-social-protocols-farcaster-phaver-tkx-weekly-9cec4c21c388), ... - Btw, one idea to make decentralized social media work could be to intentionally keep things local and small and even topic specific, say a Chapman University social media ... maybe a decentralized [Fizz](https://fizzsocial.app/) or a bespoke network to connect students and researcher who want to discuss interesting things (maybe more like decentralized slack then a decentralized twitter). - Wikipedia ... - Stackoverflow ... **Other Examples:** There have been proposals to decentralize any of Dropbox, AirBnB, Uber, ... All of this works in principle. But, afaik, none of the decentralized alternatives has taken off. Why? **Example (People's Primary):** An interesting experiment in decentralizing primaries is taking place in the UK right now. This example also shows again that while software can help, the most difficult design questions are not inside traditional software engineering. For more see [Montbiot's article](https://www.monbiot.com/2024/04/03/small-revolution/),[`politicalprimary.org`](https://www.politicalprimary.org/). ## Designing Algorithms for Cooperation Previously in this course, I talked about networks as a unifying paradigm for data structures (graphs), social media (networks of friends), brains (networks of neurons), artificial neural networks, biological systems (bee hives, ant nests), ecological systems (rain forests), etc In this lecture, I want to widen the perspective. I want to think about algorithms that do not only navigate digital networks. I want to focus on **algorithms that interact with networks of people**. To properly design such algorithms, we need to understand people and networks of people. A key aspect will be to pay attention to what algorithms should not do. Specifially, I am interested in designing algorithms that help people **to solve collective action problems**. Collective action problems include some of the big problems of our times such as climate change and biodiversity loss. But they also show up on a much smaller scale in everyday life: **Example (Chore Wheel):** Daniel Kronovet will speek on Monday, April 1, in our Seminar Series on his work on the [Chore Wheel](https://github.com/zaratanDotWorld/choreWheel?tab=readme-ov-file). Here are some links: - [Design document](https://docs.google.com/document/d/e/2PACX-1vRjC4BDc7nNF6gFRvDQrgod4zC_O--xzX-EwG1H2MCMV7YjvskIzxXfcC695cryegrqR6GHZAC_Y1q7/pub) - [Slides](https://docs.google.com/presentation/d/1PcS42tksxbKC1MZDEbaWkzOAkOH88mPbcCnf0RR5CM0/edit#slide=id.p) - [Paper](https://uploads-ssl.webflow.com/61840fafb9a4c433c1470856/639b50ee30b729cb016806c1_BudgetingBoxes.pdf) - [How to install the software](https://docs.chorewheel.zaratan.world/en/latest/index.html) (Since the seminar, I incorporated some ideas and links of Daniel into these notes.) Note how the question of **how to reason about the behavior that emerges from algorithms interacting with people** adds a level of abstraction on top of the traditional level of software reliability, testing and verification. In fact, software engineering now becomes part of a whole range of disciplines usually neglected in computer science, including biology, economics and political science. (I hasten to add that this is not a new insight, similar ideas used to be much discussed under headings such as [cybernetics](https://en.wikipedia.org/wiki/Cybernetics) or [systems thinking](https://en.wikipedia.org/wiki/Systems_thinking).[^1989]) [^1989]: I would be interested in understanding better whether the decline of interest in approaches such as cybernetics and systems thinking is related to the "[end of history](https://en.wikipedia.org/wiki/The_End_of_History_and_the_Last_Man)" following the fall of the Berlin Wall. ## The Study of Cooperation in the Sciences (examples) In order to approach the topic of how to design algorithms for cooperation, for the rest of the lecture, I want to look at neighbouring disciplines such as biological evolution, primatology, anthropology, evolutionary psychology, economics, game theory, cultural evolution. For example: 1. How did cooperation evolve in the natural world? How does evolutionary biology explain the transition from molecules to cells, from cells to eukaryotes, from eukaryotes to multi-cellular organisms? 2. How does evolutionary psychology explain the evolution of reciprocal altruism, of parental investment, etc? 3. What is the role of emotions and consciousness in this? Should we try to equip AI with a [theory of mind](https://en.wikipedia.org/wiki/Theory_of_mind)? 4. How do economics, game theory and cultural evolution explain the emergence of institutions such as social norms, money, nation states, etc? ### Biological Evolution Starting with some remarks on the evolution from molecules to cells (reproduction, metabolism), from cells to eukaryotes, from eukaryotes to colonies, from colonies to multicelluar organisms, etc. Joseph LeDoux, [The Deep History of Ourselves: The Four-Billion-Year Story of How We Got Conscious Brains](https://dokumen.pub/the-deep-history-of-ourselves-the-four-billion-year-story-of-how-we-got-conscious-brains-0735223831-978-0735223837.html) has a sketch of the full history, from the biological beginnings to human psychology. ### Primatology Frans de Waal is known for his work on Chimpanzees and Bonobos. In this Ted Talk one can see a scene that is both surprising in how human Chimpanzee cooperation can be. Michael Tomasello, see his book [Becoming Human](https://www.jstor.org/stable/j.ctv24tr9w1), studied how human cooperation is different from the cooperation of other primates. A glimpse of his work on gesturing in children is illustrated in [this presentation](https://www.youtube.com/watch?v=46IrwGZpDQ4#t=22m50). While pointing to help seems obvious to human babes "chimps are terrible at this". Interestingly, it is not obvious what exactly the abilities are that humans have but great apes dont. [Does the chimpanzee have a theory of mind?](https://www.cambridge.org/core/journals/behavioral-and-brain-sciences/article/does-the-chimpanzee-have-a-theory-of-mind/1E96B02CD9850016B7C93BC6D2FEF1D0) is a classic paper (credited with introducing the techical term "theory of mind"). See also Call and Tomasello, [Does the chimpanzee have a theory of mind? 30 years later](https://www.eva.mpg.de/documents/Elsevier/Call_Does_TrendsCogSci_2008_1554401.pdf). Btw, it could be interesting to think about whether the distinction that Call and Tomasello make between **perception-goal pychology and belief-desire psychology** could be relevant for the design of decentralized social media. ### Anthropology Richard Wrangham in *[The Goodness Paradox: The Strange Relationship Between Virtue and Violence in Human Evolution](https://dokumen.pub/qdownload/the-goodness-paradox-the-strange-relationship-between-virtue-and-violence-in-human-evolution-2018028837-9781101870907-9781101870914.html)* (see also this [Review](https://www.researchgate.net/publication/335929824_The_Goodness_Paradox_How_evolution_made_us_more_and_less_violent_by_Richard_Wrangham)) asks the question why humans are both more more social and cooperative as well as more violent (eg in war) than animals. His answer, in a nutshell, is that self-domestication selected against reactive and for proactive aggression. ### Cognitive Science Hugo Mercier and Dan Sperber: The Enigma of Reason (2019). As [Kahneman](https://en.wikipedia.org/wiki/Daniel_Kahneman) and colleagues have shown, humans are not very good at reasoning. So what did reason evolve for? ### Philosophy Kim Sterelny. The Evolved Apprentice (2012). Humans were genetically modern 200,000 years ago but culturally modern only 50,000 years ago. What happened in between? From an answer to this question emerges a sophisticated account of the mechanisms underlying human cooperation and the accumulation of cognitive capital. ### Evolutionary Psychology How did altruism evolve? Group selection was the popular and "obvious" answer for a long time after Darwin, but what worried Hamilton was the individual free-riders: what was to stop them getting the benefits of others' selflessness without paying the costs and thereby proliferating until the altruists became extinct? In language introduced later: How can altruism be an [evolutionary stable strategy](https://en.wikipedia.org/wiki/Evolutionarily_stable_strategy)? See links below under economics. ### Psychology - Daniel Kahneman [Thinking, fast and slow](https://en.wikipedia.org/wiki/Thinking,_Fast_and_Slow), 2011. How good are humans at using reason to answer questions? How does [framing](https://en.wikipedia.org/wiki/Framing_effect_(psychology)) affect decisions? The famous [Linda example](https://en.wikipedia.org/wiki/Conjunction_fallacy). ### Economics The intersection of evolutionary psychology and economics has been a very fruitful area of research for a long time. Here is a very rough timeline. - von Neumann, Morgenstern, [Theory of Games and Economic Behavior](https://en.wikipedia.org/wiki/Theory_of_Games_and_Economic_Behavior), 1944. - Hamilton: [The Genetical Evolution of Social Behaviour](https://en.wikipedia.org/wiki/The_Genetical_Evolution_of_Social_Behaviour), 1964. Andrew Berry's review of Hamilton's collected wors [‘Narrow Roads of Gene Land’ by W.D. Hamilton](https://projects.iq.harvard.edu/files/andrew-berry/files/andrew_berry_reviews_narrow_roads_of_g.by_w.d._hamilton_lrb_6_february_2003.pdf) summarizes the influence of Hamilton's work and adds some biographical information. - Maynard Smith and Price: [The Logic of Animal Conflict](https://www.nature.com/articles/246015a0), 1973 formalized the concept of an evolutionary stable strategy. Maynard Smith's 1982b book [Evolution and the Theory of Games](https://en.wikipedia.org/wiki/Evolution_and_the_Theory_of_Games) has been very influential. - Axelrod, Hamilton, [The Evolution of Cooperation](https://websites.umich.edu/~axe/research/Axelrod%20and%20Hamilton%20EC%201981.pdf), 1981. I always highly recommend Axelrod's 1984 book [The Evolution of Cooperation](https://en.wikipedia.org/wiki/The_Evolution_of_Cooperation) - [Elinor Ostrom](https://en.wikipedia.org/wiki/Elinor_Ostrom): - [Governing the Commons: The Evolution of Institutions for Collective Action](https://archive.org/details/governingcommons0000ostr/page/n5/mode/2up), 1990. - Ostrom, Elinor; Walker, James (2003). Trust and reciprocity: interdisciplinary lessons from experimental research. - Ostrom, Elinor; Hess, Charlotte (2007). Understanding knowledge as a commons: from theory to practice. - Ostrom, Elinor; Chang, Christina; Pennington, Mark; Tarko, Vlad (2012). The Future of the Commons Beyond Market Failure and Government Regulation. - If you want a glimpse at how these ideas have been playing out more recently you can look at the inclusive fitness debate, eg - Nowak, M., Tarnita, C. & Wilson, E. [The evolution of eusociality](https://doi.org/10.1038/nature09205). Nature 466, (2010). - Abbot et al. [Inclusive fitness theory and eusociality](https://doi.org/10.1038/nature09831). Nature 471, (2011). - Birch: [The inclusive fitness controversy: finding a way forward](https://royalsocietypublishing.org/doi/epdf/10.1098/rsos.170335) ### Cultural Evolution - Joseph Henrich. [The WEIRDest People in the World](https://en.wikipedia.org/wiki/The_WEIRDest_People_in_the_World), (2020). How did human cognition and psychology co-evolve with culture? How is European civilisation peculiar? What role did the Church play in European cultural evolution? Btw, this is a great book also because it is full of interesting observations, eg why [Descarte's dualism](https://en.wikipedia.org/wiki/Mind%E2%80%93body_dualism), even if scientifically untenable, is so intuitively convincing. Or his remarks on the importance of the [Magdeburg Law](https://magdeburg-law.com/historic-city/). [The 2010 article](https://www2.psych.ubc.ca/~henrich/pdfs/WeirdPeople.pdf) of the same title. - Ara Norenzayan. Big Gods: How Religion Transformed Cooperation and Conflict. (2015). ### Social Learning Social learning is a broad field that encompasses how individuals learn from one another within a social context. It includes imitation, instruction, collaborative learning, and the cultural transmission of knowledge and behaviors. Scholars from all of the fields mentioned above contributed to the theory of social learning. I still have to do a more detailed literature review ... --- ## Designing Algorithms for Cooperation (some readings) - [Metagov](https://metagov.org/) has regular [seminars](https://researchseminars.org/seminar/Metagov). Some of the following references may seem very far removed from software engineering. In this lecture we didnt have time to tie this back to Algorithm Design and I will have to leave this to the future. I intend to curate a list here of papers that I think are directly relevant ... - DeScioli, Peter and Kurzban, Robert, [A Solution to the Mysteries of Morality](https://papers.ssrn.com/sol3/papers.cfm?abstract_id=2714109 ) (January 11, 2016). - Kurzban, Robert and DeScioli, Peter, [Adaptationist Punishment in Humans](https://ssrn.com/abstract=1368784) (March 26, 2009). Links I picked up from Daniel Kronovet: - [Behavior, Purpose and Teleology](https://www.jstor.org/stable/184878) by Arturo Rosenblueth, Norbert Wiener, Julian Bigelow in Philosophy of Science, Vol. 10, No. 1 (Jan., 1943) - Stafford Beer [Designing Freedom](https://monoskop.org/images/e/e3/Beer_Stafford_Designing_Freedom.pdf) - 99% Invisible Podcast on [Project Cybercyn](https://99percentinvisible.org/episode/project-cybersyn/) ## Further Reading on Technology and Society I copied this over from another set of notes and we didnt talk about this at all in the lecture ... but if anything on the list piques your interest I am happy to talk more ... **Computer Science:** - [**SWO**] Dean Allemang, Jim Hendler, Fabien Gandon: *Semantic Web for the Working Ontologist: Effective Modeling for Linked Data, RDFS and OWL*, 2020. --- The main technical reference for these slides. - Roy Fielding, [*Architectural Styles and the Design of Network-based Software Architectures*](https://www.ics.uci.edu/~fielding/pubs/dissertation/fielding_dissertation.pdf), 2000. Introduces [Representational State Transfer (REST)](https://en.wikipedia.org/wiki/Representational_state_transfer). - Tim Berners-Lee. [Design Issues](https://www.w3.org/DesignIssues/). --- Architectural and philosophical issues underpinning the design of the WWW. - [*Vitalik Buterin's website*](https://vitalik.ca/). --- A blog exploring the possibilities of decentralization mainly (but not only) from a blockchain perspective. - Jaron Lanier. *Who Owns the Future*. 2013.--- Thoughts on the history, presence and future of the internet. **Business and Economics:** - Parker, Van Alstyne, Choudary. *Platform Revolution*. 2016. --- How do platforms create value? - Kathryn Judge. *Direct: The Rise of the Middleman Economy and the Power of Going to the Source* (2022). --- How can technology support "going to the source"? - Rebecca Giblin, Cory Doctorow. *Chokepoint Capitalism*. 2022. Does copyright help content creators or publishing monopolies? - Tristan Harris from the [Center of Human Technology](https://www.humanetech.com/) explains the business model of [the Attention Econonomy](https://www.humanetech.com/news/principles-for-humane-technology). **Psychology:** - Jon Haidt. *[After Babel](https://jonathanhaidt.substack.com/p/why-some-researchers-think-im-wrong)*. --- A blog that argues that social media is causing a mental health crisis among teenagers. - Anna Lembke. *Dopamine Nation*. 2021. --- On the biology and psychology of addiction. **Media:** - Martin Gurri. *The Revolt of The Public and the Crisis of Authority in the New Millennium* (2014/2018). --- How will networks and hierarchies shape the struggle between authorities and the public? **Politics:** - Balaji Srinavasan. *[The Network State](https://balajis.com/the-network-state-2/)*. (2022). Can we decentralize politics? - Shoshana Zuboff: *The Age of Surveillance Capitalism* (2019). --- Does the information age tend towards authoritarianism? **Algorithms and AI:** - Brian Christian. *The Alignment Problem: Machine Learning and Human Values*. (2020). - Virginia Eubanks. *Automating Inequality: How High-Tech Tools Profile, Police, and Punish the Poor.* (2018) --- What happens when people are targeted by algorithmic decision-making tools? ## Acknowledgements I have been discussing decentralized social media over the years in particular with Henry Story, Andrea Bracciali and Jeff Turner. I am also grateful to my friends at the ESI, the Business School, the philosophy department and the Humanomics program of Chapman for providing an economics and philosophy perspective. Special thanks to Daniel Kronovet for a wonderful visit to Chapman that deepened my knowledge about this topic. [^unpredictable]: An unusual example of the unpredictable consequences of social software is the [Arab Spring](https://en.wikipedia.org/wiki/Arab_Spring). (A fascinating book that chronicles how Egyptians brought down a long-reigning dictator with the help of Facebook is [Revolution 2.0 : the power of the people is greater than the people in power : a memoir](https://archive.org/details/revolution20powe0000ghon/page/n5/mode/2up) by [Wael Ghonim](https://en.wikipedia.org/wiki/Wael_Ghonim). Martin Gurri (cited above) puts this into the wider context of global politics, technology and the future of democracy. In light of the considerable changes in technology since 2011, the series of events described by Wael Ghonim would likely play out differently in the present day but the wider questions that Gurri brings up are still very timely.)