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.

Upcoming Talks

Sept. 29, 2023
Elaine Shi
Decentralized Mechanism Design
→ Abstract and Bio In transaction fee mechanism design, users bid to get their transactions confirmed in the block. Classical auctions completely fail in such a decentralized environment where even the auctioneer (i.e., miners) can be a strategic player. Further, the miners can collude with a subset of the users, e.g., facilitated by real-world platforms like Flashbots. A line of works have attempted to devise a 'dream' transaction fee mechanism but all have failed. In this talk, I will first show that this is not a coincidence --- in fact, there is a fundamental mathematical barrier towards achieving a 'dream' transaction fee mechanism. Then, I will explain how to overcome impossibilities with the help of cryptography, leading to practical mechanisms that achieve good social welfare and revenue.

Bio: Elaine Shi is an Associate Professor at Carnegie Mellon University. Prior to joining CMU, she taught at Cornell and the University of Maryland. Her research interests include cryptography, security, algorithms, mechanism design, and foundations of blockchains. She has won numerous awards such as the Sloan Fellowship, the Packard Fellowship, the ONR YIP award, the NSA Best Science of Cybersecurity Paper award, Cylab Distinguished Alumni Award, and various other best paper awards. Her work on Oblivious RAM and privacy-preserving algorithms have been deployed at a large scale by companies like Signal, Google, and JP Morgan.
Oct. 2, 2023
Alex Teytelboym
Equilibrium Existence and Implementability
→ Abstract and Bio We explore equilibria in markets with money and in pseudomarkets when there are indivisible goods. We show that under a regularity condition, competitive equilibria exist in a transferable utility economy if and only if all random equilibria in a pseudomarket are implementable as a lottery over allocations. Our paper bridges two core models of competitive market designs for indivisible resources and generates new implementability and maximal domain results for pseudomarkets. One consequence is that random equilibria in pseudomarkets are implementable even in the presence of complementarities which feature in existing pseudomarkets, such as course assignment. We provide further equivalence results in the presence of ex-post individual (e.g., technological) constraints, ex-ante individual (e.g., budget) constraints, priorities (e.g., school choice), and ex-post aggregate (e.g., diversity) constraints.

Bio: Alex Teytelboym is a Professor of Economics at the Department of Economics, University of Oxford, a Tutorial Fellow at St. Catherine’s College, and a Senior Research Fellow at the Institute for New Economic Thinking at the Oxford Martin School. He directs the Oxford University Business Economics Programme. His research interests lie mainly in market design and the economics of networks. He is also interested in environmental economics and is part of the Leverhulme Centre for Nature Recovery. He often advises companies, governments and NGOs on auction and market design. He is also co-founder of Refugees.AI, an organisation that is developing new technology for refugee resettlement (originally funded by Skoll Centre for Social Entrepreneurship).
Oct. 9, 2023
Vijay Vazirani
LP-Duality and the Cores of Games Test
→ Abstract and Bio Even though LP-duality has played a central role in the study of the core, right from its early days to the present time, basic gaps still remain. I will summarise three papers which address these gaps:

Paper 1 defines new matching-based games, with important applications, and characterizes their cores. It also gives efficient algorithms for computing core imputations with enhanced fairness properties: min-max fair, max-min fair and equitable core imputations.

Paper 2 extends the scope of the notion of core beyond profit --- equivalently cost or utility --- sharing. The game in this paper is not a cooperative game, it is a game against nature.

Paper 3 rectifies the fact that the general graph matching game has an empty core by giving the notion of 2/3-approximate core.

Bio: Vijay Vazirani is a distinguished professor at the University of California, Irvine. A description of his research appears in the citation of his 2022 INFORMS John von Neumann Theory Prize. His co-edited book, Online and Matching-Based Market Design, appeared in July 2023.
Oct. 23, 2023
Emre Kiciman
TBA
→ Abstract and Bio TBA

Bio: TBA
Oct. 30, 2023
Jason Hartline
TBA
→ Abstract and Bio TBA

Bio: TBA
Nov. 6, 2023
Robert Kleinberg
TBA
→ Abstract and Bio TBA

Bio: TBA
Nov. 13, 2023
Bruno Ribeiro
TBA
→ Abstract and Bio TBA

Bio: TBA
Dec. 4, 2023
Shuchi Chawla
TBA
→ Abstract and Bio TBA

Bio: TBA

Previous Talks This Year

Previous talks can be found here.

About The Seminar

Seminar Organizers: Itai Ashlagi, Mohak Goyal, Tristan Pollner.

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

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.