# Stanford RAIN (Research on Algorithms and Incentives in Networks) Seminar

The Internet is a complex network made of both machines and people, and hence, problems in this domain often require techniques from both algorithms and the social sciences. The RAIN (Research on Algorithms and Incentives in Networks) seminar, supported by SOAL, provides a gathering place for talks and social discussion in this area.

- Our talks this year are Wednesdays 12 PM PT in Y2E2 101!
- To receive updates on upcoming talks, please join our email list!

# Upcoming Talks

## → Abstract and Bio

TBD## → Abstract and Bio

TBD## → Abstract and Bio

TBD## → Abstract and Bio

TBD## → Abstract and Bio

Randomized experiments are widely used for investigating causal quantities in a variety of settings, from clinical trials and public policy evaluations to development economics and product development. A standard assumption in designing and analyzing such experiments is that of “no-interference”, which states that a participant’s outcome is only affected by their individual treatment and not by the treatments given to other participants in the experiment. Although standard, this assumption does not hold in many experimental settings, e.g. studies of the effect of vaccines where disease may spread between the participants or cash transfer programs where participants may affect local economies containing other participants. In this talk, I will present a new design-based experimental framework for formulating and investigating causal quantities under complex interference. The framework is expressive in the sense that it allows experimenters to define and investigate new causal estimands based on continuous or discrete treatment assignments under rich and complex interference structures. We present the Riesz Estimator, which is a unified approach to estimation based on insights from functional analysis. Finally, we derive necessary statistical tools (CLT, variance estimators) to construct asymptotically valid confidence intervals for the causal estimand. Joint work with Fredrik Sävje and Yitan Wang.**Bio:**Christopher Harshaw is a FODSI postdoctoral fellow hosted jointly between UC Berkeley and MIT. He obtained his PhD in Computer Science from Yale University, where he was advised by Daniel Spielman and Amin Karbasi. His research addresses theoretical aspects of causal inference and data science, particularly algorithmic and statistical problems arising in the design and analysis of randomized experiments.

## → Abstract and Bio

TBD## → Abstract and Bio

TBD# Previous Talks This Year

## → Abstract and Bio

Natural language processing (NLP) has had increasing success and produced extensive industrial applications. Despite being sufficient to enable these applications, current NLP systems often ignore the social part of language, e.g., who says it, in what context, for what goals, which severely limits the functionality of these applications and the growth of the field. Our research focuses on the social part of language, towards building more socially responsible language technologies. In this talk, I will take a closer look at social factors in language and share two recent works for promoting more civility and positivity in language use. The first one studies hate speech by introducing a benchmark corpus on implicit hate speech and computational models to detect and explain latent hatred in language. The second examines positive reframing by neutralizing a negative point of view and generating a more positive perspective without contradicting the original meaning.**Bio:**Diyi Yang is an assistant professor in the Computer Science Department at Stanford University. Her research interests are computational social science and natural language processing. Her research goal is to understand the social aspects of language and to build socially aware NLP systems to better support human-human and human-computer interaction. Her work has received multiple paper awards or nominations at ACL, ICWSM, EMNLP, SIGCHI, and CSCW. She is a recipient of Forbes 30 under 30 in Science (2020), IEEE “AI 10 to Watch” (2020), the Intel Rising Star Faculty Award (2021), Microsoft Research Faculty Fellowship (2021), and NSF CAREER Award (2022).

## → Abstract and Bio

Prediction systems face exogenous and endogenous distribution shift -- the world constantly changes, and the predictions the system makes change the environment in which it operates. For example, a music recommender observes exogeneous changes in the user distribution as different communities have increased access to high speed internet. If users under the age of 18 enjoy their recommendations, the proportion of the user base comprised of those under 18 may endogeneously increase. Most of the study of endogenous shifts has focused on the single decision-maker setting, where there is one learner that users either choose to use or not. In this talk, I'll describe several settings where user preferences may cause changes in distributions over the life of an ML system, and how these changes will affect the long-term performance of such systems. Joint work with Sarah Dean, Mihaela Curmei, Maryam Fazhel and Lillian Ratliff.**Bio:**Jamie Morgenstern is an assistant professor in the Paul G. Allen School of Computer Science & Engineering at the University of Washington. She was previously an assistant professor in the School of Computer Science at Georgia Tech. Prior to starting as faculty, she was fortunate to be hosted by Michael Kearns, Aaron Roth, and Rakesh Vohra as a Warren Center fellow at the University of Pennsylvania. She completed her PhD working with Avrim Blum at Carnegie Mellon University. She studies the social impact of machine learning and the impact of social behavior on ML's guarantees. How should machine learning be made robust to behavior of the people generating training or test data for it? How should ensure that the models we design do not exacerbate inequalities already present in society?

## → Abstract and Bio

We study the communication complexity of dominant strategy implementations of combinatorial auctions. We start with two domains that are generally considered easy: multi-unit auctions with decreasing marginal values and combinatorial auctions with gross substitutes valuations. For both domains we have fast algorithms that find the welfare-maximizing allocation with communication complexity that is poly-logarithmic in the input size. This immediately implies that welfare maximization can be achieved in an ex-post equilibrium with no significant communication cost, by using VCG payments. In contrast, we show that in both domains the communication complexity of any dominant strategy implementation that achieves the optimal welfare is polynomial in the input size. We then study the approximation ratios achievable by dominant strategy mechanisms. For combinatorial auctions with general valuations, we show that no dominant-strategy mechanism achieves an approximation ratio of m^(1−eps), where m is the number of items. In contrast, a randomized dominant strategy mechanism that achieves an O(sqrt m) approximation. This proves the first gap between computationally efficient deterministic dominant strategy mechanisms and randomized ones. Joint work with Shiri Ron and Jan Vondrak.**Bio:**Shahar Dobzinski is a faculty member of Weizmann's applied math and computer science department. His general research area is algorithmic game theory, an area on the intersection of computer science, game theory, and economics. Specifically, he usually studies the theory of computer science aspects of problems in algorithmic mechanism design. He is also interested in other related areas of theoretical computer science, such as approximation algorithms.

## → Abstract and Bio

Most statistical methods for social network analysis are developed for social structures that consist of directed or undirected ties between two actors. Yet, in many social contexts, relations inherently involve three actors. For example, different people are known to perceive and cognitively represent the networks they are embedded in differently. Understanding differences in perceptions, and how perceptions drive behavior, requires an explicit model of network perception (sender-receiver-peceiver) data. Gossip networks too require a three-way network perspective. In this talk, I will introduce statistical models and inference for static and dynamic three-way network analysis based on incomplete observations.**Bio:**Nynke Niezink is an assistant professor in the Department of Statistics and Data Science at Carnegie Mellon University. Her research focuses on developing statistical methodology and software for the social sciences, with an emphasis on social network analysis. Much of her work is inspired by interdisciplinary collaborations. She received her PhD in Sociology, her MSc’s in Applied Mathematics and Social and Behavioral Sciences, and her BSc’s in Mathematics and Pedagogical and Educational Sciences from the University of Groningen. Her work has been supported by the NSF, NIH, and the Russell Sage and Richard King Mellon Foundation. She was granted a Provost Inclusive Teaching Fellowship for her project targeting diversity, equity, and inclusion in Statistics education at CMU.

## → Abstract and Bio

Learning in multi-agent systems often poses significant challenges due to interference between agents. In particular, unlike classical stochastic systems, the performance of an agent's action is not drawn i.i.d. from some distribution but is directly affected by the (unobserved) actions of the other agents. This is the reason why most collaborative multi-agent learning approaches aim to globally coordinate all agents' actions to evade this interference. In this talk, we focus on bipartite queuing networks, a common model for two-sided platforms, where N agents request service from K servers. Prior decentralized multi-agent learning approaches have the aforementioned 'global coordination' flavor and therefore suffer from significant shortcomings: they are restricted to symmetric systems, have performance that degrades exponentially in the number of servers, require communication through shared randomness and unique identifiers, and are computationally demanding. In contrast, we provide a simple learning algorithm that, when run decentrally by each agent, avoids the shortcomings of 'global coordination' and leads to efficient performance in general asymmetric bipartite queuing networks while also having additional robustness properties. Along the way, we provide the first UCB-based algorithm for the centralized case of the problem, which resolves an open question by Krishnasamy, Sen, Johari, and Shakkottai (NeurIPS'16 / OR'21). The paper on which this talk is based is joint work with Daniel Freund and Wentao Weng and can be found here: https://arxiv.org/abs/2206.03324. A preliminary version appeared at COLT'22 and Wentao was selected as a finalist in the Applied Probability Society student paper competition for this work.**Bio:**Thodoris Lykouris is an assistant professor at the MIT Sloan School of Management, affiliated with the Operations Management group and the Operations Research Center. His research focuses on data-driven sequential decision-making and spans across the areas of machine learning, dynamic optimization, and economics. Before joining MIT, he received his Ph.D. from Cornell University and spent two years at Microsoft Research NYC as a postdoctoral researcher. He is the recipient of a Google Ph.D. Fellowship and a Cornell University Fellowship and was selected as a finalist in the Dantzig Dissertation award as well as the George Nicholson and Applied Probability Society student paper competitions.

## → Abstract and Bio

The theme of the 2021 Nobel Prize in Physics was the study of complex systems. At the most basic level, complex systems consist of units and their interactions. In this talk, I will describe each step of a data analysis pipeline suitable for the study of complex systems: from the system dependencies that can manifest themselves in different flavors (temporal, subset, and spatial) to the common mathematical representations (such as graphs, simplicial complexes, and hypergraphs), their underlying assumptions, and the dependencies they encode. I will discuss the mathematical relationships between representations and explain how information can be lost (or imputed) when we convert data from one representation to another. I will use examples to highlight the importance of dependencies and careful choice of representations and algorithms when studying complex systems. The main message of the talk is that there is no perfect way to analyze a complex system, and that modeling decisions made when examining a data set from one system are not necessarily transferable to another system, or even to another data set from the same system. Yet, I see many studies apply certain pipelines for seemingly no other reason than because they are common in a particular field. Instead, I recommend evaluating and studying each new complex system and dataset individually and questioning each assumption and modeling decision. This talk is based on the following paper: Leo Torres, Ann Sizemore Blevins, Danielle S. Bassett, Tina Eliassi-Rad: The Why, How, and When of Representations for Complex Systems. SIAM Review 63(3): 435-485 (2021), https://doi.org/10.1137/20M1355896. Time permitting, I will describe work on measuring the distance between two graphs by relying on the theory of the length spectrum function from algebraic topology and its relationship to the non-backtracking cycles of a graph. This work is joint with Leo Torres and Pablo Suarez-Serrato, and was published in the Journal of Applied Network Science in June 2019 (http://eliassi.org/papers/appliednetsci19_nbd.pdf).**Bio:**Tina Eliassi-Rad is a professor of computer science at Northeastern University. She is also a core faculty member at Northeastern's Network Science Institute and the Institute for Experiential AI. In addition, she is an external faculty member at the Santa Fe Institute and the Vermont Complex Systems Center. Prior to joining Northeastern, Tina was an Associate Professor of Computer Science at Rutgers University; and before that she was a member of technical staff and principal investigator at Lawrence Livermore National Laboratory. Tina earned her Ph.D. in Computer Sciences (with a minor in Mathematical Statistics) at the University of Wisconsin-Madison. Her research is at the intersection of data mining, machine learning, and network science. She has over 100 peer-reviewed publications (including a few best paper and best paper runner-up awards); and has given over 250 invited talks and 14 tutorials. Tina's work has been applied to personalized search on the World-Wide Web, statistical indices of large-scale scientific simulation data, fraud detection, mobile ad targeting, cyber situational awareness, drug discovery, democracy and online discourse, and ethics in machine learning. Her algorithms have been incorporated into systems used by governments and industry (e.g., IBM System G Graph Analytics), as well as open-source software (e.g., Stanford Network Analysis Project). In 2017, Tina served as the program co-chair for the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (a.k.a. KDD, which is the premier conference on data mining) and as the program co-chair for the International Conference on Network Science (a.k.a. NetSci, which is the premier conference on network science). In 2020, she served as the program co-chair for the International Conference on Computational Social Science (a.k.a. IC2S2, which is the premier conference on computational social science). Tina received an Outstanding Mentor Award from the U.S. Department of Energy's Office of Science in 2010, became an ISI Foundation Fellow in 2019, was named one of the 100 Brilliant Women in AI Ethics in 2021, and received Northeastern University's Excellence in Research and Creative Activity Award in 2022.

## → Abstract and Bio

A recent line of work brings together Algorithmic Game Theory and Behavioral Economics. One approach taken in this line of work is to enrich well-studied settings in Algorithmic Game Theory by considering players that exhibit cognitive biases. In this talk, we will discuss two papers demonstrating this approach in two very different settings. The first paper extends the analysis of classic optimal stopping problems by considering agents that have loss aversion relative to a changing reference point and analyzes their behavior. The second paper relies on the literature on lying in behavioral economics and psychology to tackle one of the foundations of Algorithmic Mechanism Design: truthfulness. Based on joint works with Shahar Dobzinski, Bobby Kleinberg and Jon Kleinberg**Bio:**Sigal Oren is an associate professor at the Computer Science department of Ben-Gurion University. She is currently on Sabbatical at Stanford as a Koret fellow. Sigal's research area is algorithmic game theory. She is currently interested in combining behavioral economics and algorithmic game theory.

Previous talks can be found here.

# About The Seminar

**Seminar Organizers:** Itai Ashlagi, Grace Guan.

**Faculty Involved:** Itai Ashlagi, Ashish Goel, Ramesh Johari, Amin Saberi, Aaron Sidford, Johan Ugander, Irene Lo.

**Note for Speakers:** The talk is 55 minutes including questions (as we often start a couple of minutes late). If you are giving a talk at RAIN, please plan a 45-50 minute talk since the audience usually ask a lot of questions. Also, the audience is fairly knowledgeable, so speakers should not feel obligated to provide basic game-theoretic, algorithmic, societal, industrial, probabilistic, or statistical background.

Website template from the Stanford MLSys Seminar Series.