Dagstuhl Seminar 22452
Computational Social Dynamics
( Nov 06 – Nov 11, 2022 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/22452
Organizers
- Martin Hoefer (Goethe-Universität - Frankfurt am Main, DE)
- Sigal Oren (Ben Gurion University - Beer Sheva, IL)
- Roger Wattenhofer (ETH Zürich, CH)
Contact
- Andreas Dolzmann (for scientific matters)
- Christina Schwarz (for administrative matters)
Impacts
- Solving Woeginger's Hiking Problem : Wonderful Partitions in Anonymous Hedonic Games - Constantinescu, Andrei; Lenzner, Pascal; Reiffenhäuser, Rebecca; Schmand, Daniel; Varricchio, Giovanna - Cornell University : arXiv.org, 2023. - 19 pp..
- Complexity of equilibria in binary public goods games on undirected graphs : article in EC '23: Proceedings of the 24th ACM Conference on Economics and Computation - Klimm, Max; Stahlberg, Maximilian J. - New York : ACM, 2023. - Pages 938–955.
- Algorithms for Claims Trading : article in 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024) - Hoefer, Martin; Ventre, Carmine; Wilhelmi, Lisa - Wadern : LZI, 2024. - 17 pp. - (Leibniz International Proceedings in Informatics ; 289 : article).
- Solving Woeginger's Hiking Problem : Wonderful Partitions in Anonymous Hedonic Games : article in 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) - Constantinescu, Andrei; Lenzner, Pascal; Reiffenhäuser, Rebecca; Schmand, Daniel; Varricchio, Giovanna - Wadern : LZI, 2024. - 18 pp - (Leibniz International Proceedings in Informatics ; 297 : article).
Schedule
Algorithmic techniques provide a powerful toolbox for understanding many phenomena arising in modern society. Often, these phenomena are related to dynamics (e.g., dynamic information spreading, or dynamics in social networks that result from agent interaction). A large part of the present social interaction on networks can be expressed using game-theoretic or microeconomic concepts, e.g., the dynamics of opinions in networks, pricing problems and viral marketing, network-based effects of opinions, group formation, cognitive bias, etc. These problems are rigorously analyzed in the area of algorithmic game theory, where researchers apply the algorithmic toolbox to analyze various social systems.
In this field, a number of applications have not received sufficient attention, which are recently becoming increasingly prominent. For example,
- issues of fairness and bias are central challenges in modern societies.
- behavioral economists are challenging standard assumptions that humans are maximizing expected utility. This change in perspective also poses new challenges for suitable models and algorithm design.
- an important trend in the modern economy are informational challenges, e.g., in problems involving recommendation, persuasion, delegation, or (smart) contract design.
The main aim of this seminar was to bring together a leading set of researchers to discuss these and other challenges, and to advance the state of the art in several new directions. The majority of participants were academics from computer science departments; some were from other disciplines such as economics, mathematics, or electrical engineering. All participants had strong interdisciplinary interests that typically span economics, game theory, and theoretical computer science.
The seminar started on Monday with an introductory session, in which participants introduced their name, affiliation, main research interest as well as a "crazy idea" or "provoking thought". This session was very well-received by the participants, and it initiated discussions directly from the start. The subsequent program included four invited talks/tutorials of roughly one hour each, on several issues chosen by the organizers.
- Monday Caragiannis talked about notions of fairness for resource allocation problems.
- Tuesday Feldman presented recent innovations in algorithms for contract design.
- Wednesday Plonsky discussed behavioral experiments and ideas to predict human behavior.
- Thursday Wattenhofer surveyed issues in e-government, blockchains, and finance.
The contributed talks were solicited from the participants and lasted around 20-25 minutes each. In many of these talks there were lively discussions. They continued in the times from lunch to afternoon coffee, which were free for research and individual collaborative meetings.
There was a substantial set of presenters who focused on aspects of fair division. Rathi discussed epistemic notions of envy-freenes and their efficient computation. Bernadé presented results on online algorithms for fair division and guaranteeing notions of envy-freeness and Pareto-efficiency. Zick showed existence and efficient computation for several fairness criteria for matroid-rank valuations. Varricchio discussed algorithmic aspects of randomization and entitlements in fairness notions. Reiffenhäuser presented results on the quality of equilibria in fair division when strategic misreporting of preferences is allowed.
Another focus was the analysis of dynamics and stability in networks. Ventre discussed the clearing problem in financial networks with credit default swaps and showed FIXP-completeness results. Wilhelmi presented a game-theoretic model for clearing and results on equilibrium computation. Schmand considered a game-theoretic model for opinion formation in networks and convergence of natural best-response dynamics. Lenzner surveyed recent work on network creation games as well as network games that model segregation aspects.
Further talks addressed a number of different areas. Witkowski studied incentive-compatible forecasting competitions. Lavi considered incentives when several of these contests are available to participants. Klimm surveyed work on impartial selection, e.g., when agents have to decide on a representative member among themselves. Leyton-Brown posed new directions and open problems in the understanding of behavior in mobile gaming. Babichenko discussed aggregation mechanisms for anonymous information. Markakis presented a novel algorithm to compute an equilibrium in 2-player zero-sum games. Melnyk explained issues arising from Byzantine behavior in social choice. Last, but not least, Christodoulou gave a proof of the 23-year old Nisan-Ronen conjecture that every truthful mechanism for unrelated machine scheduling can only guarantee a linear approximation ratio.
The seminar was a big success. We believe it will stimulate new and very fruitful collaborations. We got laudatory feedback from many participants which is also reflected in the survey conducted by Dagstuhl.
We thank Giovanna Varricchio for serving as collector of abstracts and open problems.
Creative Commons BY 4.0
Martin Hoefer, Sigal Oren, and Roger Wattenhofer
Algorithmic techniques provide a powerful toolbox for understanding many phenomena arising in modern society. Often, these phenomena are related to dynamics – information spreads through networks through processes that mimic the behavior of epidemic spreading. Social networks themselves are the result of the dynamic interaction of agents. A large part of the present social interaction on networks can be expressed using game-theoretic or microeconomic concepts, e.g., the dynamics of opinions in networks, pricing problems and viral marketing, network-based effects of opinions, group formation, cognitive bias, etc.
In algorithmic game theory, an area at the intersection of economics, artificial intelligence and algorithmic theory, the algorithmic toolbox is applied to analyze various social systems. While there has been substantial progress, many important directions have not received sufficient attention. To advance the state of the art in this area, this Dagstuhl Seminar brings together a group of expert researchers concerned with understanding social and behavioral phenomena from a computational perspective. Apart from computer scientists, the seminar shall include economists, social scientists, and psychologists to provide valuable interdisciplinary interactions on several timely topics, including, but not limited to
- Networks: The role of network structures in societies is far from being well-understood from a computational perspective. Prominent examples include financial networks and systemic risk and networked structures in persuasion and recommendation problems. We will tackle some of these challenges.
- Fairness: As algorithms take a larger role in our lives it is crucial to make sure that the decisions they make are fair and do not amplify previous biases. We will explore new methods for developing fair algorithms in different settings.
- Cognitive Biases: Most of the algorithmic research on economic systems assumes that agents are rational utility-maximizers. In contrast, behavioral economics posits that cognitive biases invalidate this assumption. We aim to identify ways to narrow this gap between algorithmic research and behavioral economics.
This Dagstuhl Seminar is open also for discussion of other directions in this area. More fundamentally, a goal is to help shaping a new community – at this point, there is no dedicated conference on "Computational Social Dynamics", i.e., on social and behavioral phenomena from a computational perspective. The seminar aims to bring together a group of key researchers to meet and – beyond scientific problems – discuss also the general state of the field, as well as initiate future efforts in this area.
Martin Hoefer, Sigal Oren, and Roger Wattenhofer
- Yakov Babichenko (Technion - Haifa, IL) [dblp]
- Gerdus Benade (Boston University, US)
- Ioannis Caragiannis (Aarhus University, DK) [dblp]
- Giorgos Christodoulou (Aristotle University of Thessaloniki, GR) [dblp]
- Andrei Constantinescu (ETH Zürich, CH)
- Michal Feldman (Tel Aviv University, IL) [dblp]
- Tobias Harks (Universität Passau, DE) [dblp]
- Martin Hoefer (Goethe-Universität - Frankfurt am Main, DE) [dblp]
- Max Klimm (TU Berlin, DE) [dblp]
- Ron Lavi (University of Bath, GB) [dblp]
- Pascal Lenzner (Hasso-Plattner-Institut, Universität Potsdam, DE)
- Kevin Leyton-Brown (University of British Columbia - Vancouver, CA) [dblp]
- Evangelos Markakis (Athens University of Economics and Business, GR) [dblp]
- Darya Melnyk (Aalto University, FI)
- Noam Nisan (The Hebrew University of Jerusalem, IL) [dblp]
- Sigal Oren (Ben Gurion University - Beer Sheva, IL) [dblp]
- Ori Plonsky (Technion - Haifa, IL)
- Maria Polukarov (King's College London, GB) [dblp]
- Nidhi Rathi (Aarhus University, DK) [dblp]
- Rebecca Reiffenhäuser (University of Amsterdam, NL) [dblp]
- Jörg Rothe (Heinrich-Heine-Universität Düsseldorf, DE) [dblp]
- Daniel Schmand (Universität Bremen, DE) [dblp]
- Giovanna Varricchio (Goethe-Universität - Frankfurt am Main, DE)
- Carmine Ventre (King's College London, GB)
- Roger Wattenhofer (ETH Zürich, CH) [dblp]
- Lisa Wilhelmi (Goethe-Universität - Frankfurt am Main, DE)
- Jens Witkowski (Frankfurt School of Finance & Management, DE) [dblp]
- Yair Zick (University of Massachusetts - Amherst, US) [dblp]
Classification
- Artificial Intelligence
- Computer Science and Game Theory
- Data Structures and Algorithms
Keywords
- Algorithmic Game Theory
- Fair Division
- Financial Networks
- Social Networks
- Behavioral Economics
