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 for the Autumn 2023 quarter are on Mondays 4 PM PT in Y2E2 299! (Except for the first talk on 9/29, which is at 2pm in Y2E2 101)
- To receive updates on upcoming talks, please join our email list!
Upcoming Talks
→ 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.
→ 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).
→ 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.
→ Abstract and Bio
TBABio: TBA
→ Abstract and Bio
TBABio: TBA
→ Abstract and Bio
TBABio: TBA
→ Abstract and Bio
TBABio: TBA
→ Abstract and Bio
TBABio: 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.