Judging Proofs and Evolving Programs: Expert Feedback for Reliable LLM Systems
Talk details
Large language models are increasingly capable of producing plausible solutions, but expert domains demand more than plausibility: they require reliable mechanisms for evaluation, correction, and improvement. This talk connects two recent projects that study this challenge from complementary angles. QEDBench examines the reliability of automated evaluation by measuring the alignment gap between LLM-as-a-judge protocols and human expert assessment for university-level mathematical proofs, using dual rubrics and extensive human evaluation. ParEVO moves from evaluation to synthesis, introducing an agentic evolutionary framework for generating high-performance parallel algorithms over irregular data structures such as sparse graphs. It combines curated instruction data, specialized models, and iterative feedback from performance tests to optimize generated programs. Together, these papers argue for a shift from static benchmark performance toward expert-grounded feedback loops: systems that can be rigorously judged, corrected using domain-specific signals, and improved in settings where correctness, reasoning, and efficiency are all non-negotiable.
Bio: Quanquan C. Liu is an Assistant Professor of Computer Science at Yale University. Her research spans algorithms for large-scale data, dynamic and parallel graph algorithms, high-performance computing, differential privacy, and resilient distributed computation. Recently, her work has also explored how large language models can be evaluated and improved in expert technical domains, including mathematical proof assessment through QEDBench and high-performance parallel code synthesis through ParEVO. She received her Ph.D., MEng, and B.S. from MIT.
Kevin Leyton-Brown
Algorithm Synthesis with Theoretical Guarantees
Talk details
Despite massive progress on LLM-driven code synthesis, identifying algorithms that achieve excellent empirical performance requires extensive, extremely expensive empirical testing. Algorithm configuration methods are automated ways of performing such testing: optimizing the performance of parameterized heuristic algorithms on given distributions of problem instances. Such methods can be seen as efficient procedures for extending classical machine learning to hypothesis spaces consisting of algorithm designs. This talk will begin by defining the problem and illustrating its promise via some recent practical success stories. However, all widely used algorithm configuration methods both achieve poor asymptotic runtime performance in the worst case and optimize what I will argue is the wrong objective function. I will begin by explaining why we should leverage decision theory to maximize expected utility instead of minimizing average runtime. Then I will present a new algorithm configuration approach called Continuous, Online Utilitarian Procrastination (COUP), which optimizes this objective while offering strong theoretical guarantees. I will conclude by showing that these guarantees come effectively for free, as COUP achieves state-of-the-art empirical performance.
Bio: Kevin Leyton-Brown is a professor of Computer Science and a Distinguished University Scholar at the University of British Columbia. He holds a Canada CIFAR AI Chair at the Alberta Machine Intelligence Institute and is an associate member of the Vancouver School of Economics. He received a PhD and an M.Sc. from Stanford University (2003; 2001) and a B.Sc. from McMaster University (1998). He studies artificial intelligence, mostly at the intersection of machine learning with either the design and operation of electronic markets or the design of heuristic algorithms.
Ashesh Rambachan
From Next-Token Prediction to Automata Induction
Talk details
Sequence data is ubiquitous in economics — job histories in labor economics, diagnosis and treatment sequences in health economics, strategic interactions in game theory. Generative sequence models can learn to predict these sequences well, but their complexity makes it hard to extract interpretable economic insights from their predictions. We develop a framework for inducting compact state representations (finite automata) that summarize estimated next-token probabilities. This provides a common language between black-box sequence models and the dynamic restrictions imposed by economic models. We illustrate the framework through applications to collusive behavior and cooperation in repeated games.
Bio: Ashesh Rambachan is a Silverman (1968) Family Career Development Assistant Professor of Economics at MIT. His research interests are primarily in econometrics with a focus on applications of machine learning in economics and causal inference.
Yiming Yang
What Makes Diffusion Models Work for Combinatorial Optimization?
Talk details
Recent advances in generative modeling — particularly diffusion models — have shown strong performance beyond traditional domains such as vision and language, extending to combinatorial optimization (CO). However, it remains unclear what fundamentally drives their success in these structured, discrete settings. In this talk, I present a unified perspective on what makes diffusion-based approaches effective for CO, centered on three interconnected aspects: training signal, credit assignment, and stable local updates. · First, I show that in CO, labeled optimal solutions are sparse and often weak as supervision, while unsupervised approaches that directly leverage objective values provide dense and informative training signals. · Second, I examine how global objectives are propagated to local updates. Standard diffusion relies on indirect, multi-step signal propagation, whereas methods such as combinatorial adjoint matching (CAM) directly inject endpoint objectives into each step. These represent two extremes — multi-step refinement and direct global supervision — and effective performance requires balancing the two, leading to a notion of problem-dependent effective depth. · Third, I show that even with proper objectives and credit assignments, diffusion models can fail without stable local updates. In discrete spaces, naive updates can be unstable; structure (e.g., feasibility-preserving operators) and regularization (e.g., controlling update magnitude) are essential for stable training and effective inference. Overall, the effectiveness of diffusion models in CO arises not from any single component, but from the combination of guided and stabilized local updates, suggesting a broader perspective for generative optimization beyond diffusion alone.
Bio: Yiming Yang is a Professor in the Language Technologies Institute and Machine Learning Department at Carnegie Mellon University. Her recent research focuses on generative machine learning, including diffusion and flow models, agentic large language models, and their applications to combinatorial optimization and scientific discovery. Her work explores a unifying perspective that views generative models as structured reasoning processes, connecting local operations with global objectives through geometric and dynamic views. She has made influential contributions across multiple phases of machine learning, from early work in text classification and information retrieval to widely cited advances in foundation models, including XLNet, Transformer architectures, and neural architecture search (e.g., DARTS). Her recent work further investigates scalable reasoning, alignment, and evaluation in large language models and agentic systems. She has published extensively in top venues such as NeurIPS, ICML, ICLR, ACL, EMNLP, AAAI, and SIGIR, and is a member of the ACM SIGIR Academy.
Grant Schoenebeck
Incentivized Alignment for Strategic Agents (Human and Otherwise)
Talk details
Advances in machine learning enable new forms of human-AI collaboration, but collaborative settings typically involve agents with divergent objectives and private information. This will become increasingly critical in the emerging world of agentic AI, where ML-powered agents act on behalf of individuals or institutions with conflicting goals. I use the term incentivized alignment to describe the approach of combining both machine learning and incentive design to achieve alignment of system outcomes despite misaligned agents. This talk presents two case studies of incentivized alignment showing how machine learning can make mechanism design scalable and practical, and how mechanism design can make machine learning strategically robust. First, I examine the use of LLMs as judges for rating subjective responses. While LLMs perform well on existing datasets, they are highly susceptible to manipulation. I propose adapting peer-prediction mechanisms to create strategically-robust scoring mechanisms that incentivize honest reporting. Beyond ensuring high-quality inputs to AI systems, these mechanisms can potentially eliminate reward hacking in ML training pipelines. Second, I consider collective decision-making where agents hold different objectives and private information. In particular, we examine the Community Notes mechanism in this context. The goal is then to design mechanisms that incentivize strategic agents to select outcomes that would be optimal under full information sharing, according to certain criteria. Both case studies demonstrate solutions for incentivized alignment in multi-agent systems employing the combination of incentive design and machine learning, a theme likely to be central to the future of collaborative AI.
Bio: Grant Schoenebeck is an associate professor at the University of Michigan in the School of Information. His work has recently focused on developing and analyzing systems for eliciting and aggregating information from a diverse group of agents with varying information, interests, and abilities by combining ideas from machine learning and economics (e.g. game theory, mechanism design, and information design). More generally, his recent work has been about incentives and (machine) learning in a variety of contexts. His research is supported by multiple NSF grants including a CAREER award and spans publications in top venues including NeurIPS, ICLR, EC, WINE, the Web Conference, STOC, and FOCS. His former PhD students and postdocs now hold tenure-track positions at the University of Illinois Urbana-Champaign, Peking University, George Mason University, and Shanghai Jiao Tong University. He recently served as Program Committee Co-chair for WINE, Theory Track Co-chair for EC, and Economics and Computation Track co-chair at the Web Conference. Grant received his PhD at UC Berkeley, studied theology at Oxford University, and received his BA in mathematics and computer science from Harvard.
Joseph Jay Williams
Using Adaptive Experimentation to Design Real-World AI Systems for Education & Health
Talk details
AI systems can look promising - helping certain people with mental health and some students with learning – yet fail others. I develop Adaptive A/B Experimentation methods that embed AI into everyday interfaces – to discover which actions work, for who, and when. This has generated AI systems that used text messages for mental health coaching, and created online homework systems that experimented with explanations like an expert teacher. Adaptive Experimentation enabled AI systems that: (1) generate candidate actions using improved LLM interfaces and co-design between LLMs, users, and scientists (e.g. action A, B, C…); and (2) use reinforcement learning algorithms to test, personalize, and deploy interventions in real time. We identified a 3-minute intervention that boosted student grades by as much as 4%. This work received 1st place in the $1M XPRIZE and a $3M NSF grant to provide practitioners and scientists access to Adaptive Experimentation tools. These tools enable cross-domain improvement in how AI systems change beliefs and behavior for the better.
Bio: Joseph Jay Williams is an Assistant Professor at the University of Toronto in Computer Science, with courtesy appointments supervising PhD students in Statistical Sciences, Psychology, and the Vector Institute for Artificial Intelligence. He also has courtesy appointments in Economics and Industrial Engineering. He directs the Adaptive Experimentation and Intelligent Interventions lab. His lab's work is represented in over 85 papers, 2 Best Paper Awards (1 at CHI), 4 Runner-up/Honorable Mention for Best Paper (CHI, EDM, LAS), and 1st place in a $1M XPRIZE competition for the future of experimentation technology in education. He's received over $2M in grant funding, enabling interventions impacting over 500,000 people. His PhD Students have spanned HCI (Human-Computer Interaction), Education, Health, Psychology, applied AI (Reinforcement Learning & LLMs), and Statistics. Joseph is originally from Trinidad and Tobago, was previously an Assistant Professor in Information Systems & Analytics at the National University of Singapore, Research Scientist at Harvard, postdoc at Stanford, and did his PhD at UC Berkeley.
Cathy Wu
Tackling the Long Tail of Transportation Optimization with Machine Learning
Talk details
Before changing a bus network, signal timing plan, or autonomy deployment, decision-makers must compare relevant counterfactuals. However, such counterfactual questions induce a long tail of difficult optimization problems for which traditional approaches are prohibitively costly—requiring years of solver development, lengthy solve times, or both. My research asks: How can AI lower the cost of solving transportation optimization problems? In principle, deep reinforcement learning (RL) can be used to solve arbitrary optimization problems. However, RL is far from mature; our work exposes fundamental limitations in current methods: brittleness to even small changes, like network structure or demand. In response, I take two broad approaches. First is to address non-robustness in deep RL: I will present a Bayesian approach that trains an ensemble of RL models to solve contextual control problems with up to 30x improved sample efficiency. Second is to understand how to use AI in conjunction with classical optimization techniques: I will show how AI can help identify and eliminate unproductive decisions within combinatorial optimization solvers, leading to 2-10x faster solve times. Finally, we inform transportation policy by tackling an open optimization problem: we produce the first prospective impact assessment of city-scale eco-driving, showing that optimizing vehicle speeds at intersections can significantly improve energy efficiency without sacrificing throughput or safety. Together, these approaches suggest a principled "middle road" between pure RL and pure classical optimization for scalable decision-making across transportation, logistics, and beyond.
Bio: Cathy Wu is the Class of 1954 Career Development Professor at MIT, holding appointments in LIDS, CEE, and IDSS. She holds a Ph.D. in EECS from UC Berkeley, and B.S. and M.Eng. in EECS from MIT, and completed a Postdoc at Microsoft Research. Her research group studies machine learning for optimization, with a focus on transportation. She is broadly interested in enabling faster, evidence-driven decisions for sociotechnical systems. Cathy is the recipient of the NSF CAREER (2023), the Ole Madsen Mentoring Award (2025), the IEEE ITS Best Dissertation Award (2019), and the CUTC Milton Pikarsky Memorial Award (2018). She serves on the Board of Governors for the IEEE ITSS, is an Associate Editor or Area Chair for ICML, NeurIPS, ICRA, Transportation Research Part C, and Operations Research, and served as Program Co-chair for RLC 2025. She is also the inaugural Chair and Co-founder of the REproducible Research In Transportation Engineering (RERITE) Working Group.
Juba Ziani
How Differential Privacy Shapes Incentives in Data Sharing
Talk details
Many data-driven decisions rely on combining data held by multiple independent actors who differ in their willingness to share sensitive information. While differential privacy is often regarded as a gold standard for privacy in statistical analysis and learning tasks, much less is understood about how privacy choices shape incentives to participate and contribute data when participation is voluntary.
This talk takes an economic and incentive-centric view of differential privacy in collaborative and federated data-sharing environments. I study settings in which participation is voluntary, and privacy protection affects agents' incentives, trading off learning benefits—which improve as more data are pooled—against privacy disutilities from sharing sensitive information. The talk analyzes both centralized designs, in which a platform commits to a (potentially personalized) privacy policy and agents decide whether to participate, and decentralized designs, in which agents jointly determine participation and form data-sharing coalitions through direct interactions.
This is based on two recent joint works. One with Rachel Cummings, Hadi Elzayn, Vasilis Gkatzelis, Manolis Pountourakis, and one with Raef Bassily, Kate Donahue, and student authors Diptangshu Sen and Annuo Zhao.
Bio: Juba Ziani is an Assistant Professor in the School of Industrial and Systems Engineering and an Adjunct Professor in the School of Computer Science at Georgia Tech. He is a recipient of the NSF CAREER Award. His research lies at the intersection of computer science, operations research, and economics. He uses tools from learning theory, game theory, and optimization to address technical and societal challenges arising from AI, machine learning, and data-driven decision-making.
Prior to joining Georgia Tech, Juba was a Ph.D. student in Computing and Mathematical Sciences at Caltech, advised by Katrina Ligett and Adam Wierman, and a postdoctoral fellow at the Warren Center for Data Science at the University of Pennsylvania, hosted by Sampath Kannan, Michael Kearns, and Aaron Roth.
Chara Podimata
Toward a Science of Auditing AI-Mediated Information Ecosystems
Talk details
AI-mediated systems, from social media recommendation algorithms to LLMs, now curate the information that billions of people worldwide consume at an unprecedented scale. Yet both operate as black boxes: their internal mechanisms are opaque, their biases poorly understood, and their accountability to ethical norms mostly unenforced. In this talk, I present two complementary studies that work toward a science of auditing such systems. In doing so, I will reveal a duality: LLMs can serve as both the methodological tool and the object of the auditing study.
In the first study, I introduce a counterfactual auditing framework that uses LLMs as behavioral engines for synthetic user accounts, enabling causal identification of how social media algorithms respond to user demographics, a form of identification that had previously been infeasible. Deployed on X during the 2024 U.S. presidential election, we find that the platform's recommendation algorithm substantially amplifies toxic, polarizing, and right-leaning content, with effects that are highly heterogeneous across user types and political leanings. In the second, I turn the same auditing lens on LLMs themselves, querying 12 models daily from July through November 2024 on a set of more than 12,000 election-related questions. I find that LLMs exhibit systematic biases in how they represent candidates and electoral issues, are sensitive to demographic steering, and hold implicit (and highly unstable) beliefs about election outcomes. These findings suggest that LLMs are political actors, whether or not they intend to be.
Taken together, I argue that auditing AI-mediated information systems requires new methodological frameworks, ones that are counterfactual, large-scale, and sensitive to heterogeneity across user populations. Building this science is one of the most pressing challenges at the intersection of AI and society.
Bio: Chara Podimata is the Class of 1942 Career Development Professor and Assistant Professor of Operations Research and Statistics at MIT's Sloan School of Management. Her research sits at the intersection of theoretical computer science, operations research, and AI, with a focus on AI auditing and incentive-aware AI. She received her PhD in Computer Science from Harvard University, where she was a member of the EconCS group, and completed a FODSI postdoctoral fellowship at UC Berkeley. Her work is supported by an Amazon Research Award, a Google Research Scholar Award, a MacArthur Foundation x-grant, and several internal MIT awards. In her "free" time, she trains for marathons and triathlons and adventures with her pup, Terra.
Vivek Farias
The Sign Estimator: Preference Modeling for LLM Alignment under Heterogeneity
Talk details
LLM alignment methods typically learn a single reward model (either implicitly or explicitly) from pairwise comparison data. This approach implicitly assumes homogeneous preferences across human labelers — an assumption that is violated in practice. As a result, the learned reward model is generally mis-specified: Prior work shows that it is inconsistent with the population-average utility, incurring large distortion, and that recovering the average utility is provably impossible in the worst case. In this work, we show that the average utility is recoverable under a relatively mild assumption. Our accompanying estimator, the Sign Estimator, simply replaces the standard cross-entropy loss function in reward learning pipelines with a notion of binary classification loss and yields a reward model that is ordinally consistent with the population-average utility. We further establish a finite-sample convergence rate of $O(n^{-1/3})$, which provides, to our knowledge, the first consistent estimator for heterogeneous preferences that does not suffer from the curse of dimensionality.
Bio: Vivek is interested in the development of new methodologies and applications for large scale dynamic optimization. He received his Ph.D. in Electrical Engineering from Stanford University in 2007 and is the Patrick J. McGovern (1959) Professor at MIT. Vivek is a recipient of an INFORMS MSOM Student Paper Prize (2006), an INFORMS JFIG paper prize (2009, 2011), the NSF CAREER award (2011), MIT Sloan’s Outstanding Teacher award (2013), the INFORMS Simulation Society Best Publication Award (2014), the INFORMS Pricing and Revenue Management Best Publication Award (2015), the INFORMS MSOM Best Publication award in Management Science (2016), the MSOM Young Scholar Prize (2020), the Wagner prize (2022), the Pierskalla award (2024), and is an Informs Fellow (2025). Vivek’s doctoral advisees have on various occasions won the Nicholson, MSOM, APS and RMP student paper prizes. Outside of academia, Vivek was co-founder/CTO at Celect (2014-19; acquired by Nike); was a corresponding author of the technology at Seer (2018-2020; IPO); and is co-founder/CTO at Cimulate (2023-26; acquired by Salesforce).
Meena Jagadeesan
Power and Limitations of Aggregation in Compound AI Systems
Talk details
When designing compound AI systems, a common approach is to query multiple copies of the same model and aggregate the responses to produce a synthesized output. Given the homogeneity of these models, this raises the question of whether aggregation unlocks access to a greater set of outputs than querying a single model. In this talk, we investigate the power and limitations of aggregation within a stylized principal-agent framework. This framework models how the system designer can partially steer each agent's output through its reward function specification, but still faces limitations due to prompt engineering ability and model capabilities. Our analysis uncovers three natural mechanisms -- feasibility expansion, support expansion, and binding set contraction -- through which aggregation expands the set of outputs that are elicitable by the system designer. We prove that any aggregation operation must implement one of these mechanisms in order to be elicitability-expanding, and that strengthened versions of these mechanisms provide necessary and sufficient conditions that fully characterize elicitability-expansion. Finally, we provide an empirical illustration of our findings for LLMs deployed in a toy reference-generation task. Altogether, our results take a step towards characterizing when compound AI systems can overcome limitations in model capabilities and in prompt engineering. Based on joint work with Nivasini Ananthakrishnan.
Bio: Meena Jagadeesan is an incoming Assistant Professor in the Computer and Information Science Department at the University of Pennsylvania, starting in Summer 2026. Her research aims to steer multi-agent interactions in machine learning ecosystems. She is currently a Stanford AI Lab postdoctoral fellow advised by Tatsu Hashimoto and Sanmi Koyejo. She received a PhD in Computer Science from UC Berkeley advised by Michael I. Jordan and Jacob Steinhardt.
Suresh Venkatasubramanian
Frames, Measurements, and Tools: A triple threat for AI governance
Talk details
2025 felt like the year that we started to throw caution to the winds when it came to AI deployment. AI policy priorities have shifted almost 180 degrees, global cooperation has been replaced by talk of American dominance, and the relentless march of LLMs into every nook and cranny of our lives continues apace. And 2026 seems like more of the same. One would not be faulted for thinking that we've abandoned virtually everything we've learnt about how to deploy AI systems -- in decision making or other critical settings -- responsibly. And yet, the lessons we've learnt from over a decade of thinking about responsible AI seem still relevant and still point us towards new and interesting research questions. These lessons can be roughly organized in an interacting triangle of Framing, Measuring, and Building. How we frame the problems we are concerned about, how we measure the degree to which these problems are real, and how we build tools to help us measure and mitigate, are the basis of success in AI governance thus far, and are the way we can start to tackle the next wave of challenges in this space. In this talk I'll present some recent work that can be classified into one or more of these dimensions, from better ways to think about regulating general purpose AI to proofs of concept for how to do end to end auditing of complex AI supply chains.
Bio: Suresh Venkatasubramanian directs the Center for Technological Responsibility, Reimagination, and Redesign (CNTR) with the Data Science Institute at Brown University, and is a Professor of Computer Science and Data Science. Suresh's background is as a computer scientist and his current research interests lie in algorithmic fairness, and more generally the impact of automated decision-making systems in society. Suresh recently finished a stint in the Biden-Harris administration, where he served as Assistant Director for Science and Justice in the White House Office of Science and Technology Policy. In that capacity, he helped co-author the Blueprint for an AI BIll of Rights. His research on algorithmic fairness has received press coverage across the globe, including NPR’s Science Friday, NBC, and CNN, as well as in other media outlets. He is a past member of the Computing Community Consortium Council of the CRA, spent 4 years (2017-2021) as a member of the board of the ACLU in Utah, and is a past member of New York City’s Failure to Appear Tool (FTA) Research Advisory Council, the Research Advisory Council for the First Judicial District of Pennsylvania and the Utah State Auditor's Commission on protecting privacy and preventing discrimination. He was named in 2023 by Fast Company to their AI20 list of thinkers shaping the world of generative AI, and currently sits on the boards of the Data and Society Institute, the Partnership on AI, and the Ada Lovelace Institute. He is the co-chair of ACM's AI And Algorithms Policy Committee.
Nico Christianson
End-to-end learning for uncertainty- and risk-aware decision-making
Talk details
Machine learning can significantly improve average performance for decision-making under uncertainty in a wide range of domains. However, ensuring robust, risk-aware decisions—a critical need in high-stakes settings—requires well-calibrated uncertainty estimates; yet in high-dimensional settings, there can be many valid uncertainty estimates, each with its own performance profile. That is, not all uncertainty is equally valuable for downstream decision-making. In this talk, I will discuss recent work developing an end-to-end learning framework to train machine learning models while enforcing uncertainty calibration and risk constraints through conformal prediction-based methods. Our proposed approach enables provable guarantees on calibration and risk control while providing consistent improvements over existing, two-stage baselines in applications spanning energy systems and medical image classification.
Bio: Nico Christianson is a Stanford Energy Postdoctoral Fellow and an incoming Assistant Professor of Computer Science at Johns Hopkins University (starting Fall 2026). His research lies broadly at the intersection of algorithms, machine learning, and optimization, with a specific emphasis on the development of new, theoretically-grounded algorithms and AI/ML methods for reliable decision-making under uncertainty. Much of his work is motivated by modern energy and sustainability challenges, with applications ranging from energy resource operation to sustainable computing systems. Nico received his PhD in computing and mathematical sciences from Caltech in 2025, where he was supported by an NSF Graduate Research Fellowship and a PIMCO Data Science Fellowship. His PhD dissertation won Caltech’s Ben P.C. Chou Doctoral Prize in Information Science and Technology and Demetriades-Tsafka-Kokkalis Prize in Renewable Energy. Before Caltech, Nico received an AB in applied mathematics from Harvard College.
Negin Golrezaei
Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
Talk details
We study the bidding problem in repeated uniform price multi-unit auctions from the perspective of a value-maximizing buyer. The buyer aims to maximize their cumulative value over T rounds while adhering to per-round return-on-investment (RoI) constraints in a strategic (or adversarial) environment. Using an m-uniform bidding format, the buyer submits m bid-quantity pairs (bi, qi) to demand qi units at bid bi, with m ≪ M in practice, where M denotes the buyer's maximum demand. We introduce the notion of safe bidding strategies as those that satisfy the RoI constraints irrespective of competing bids. Despite the stringent requirement, we show that these strategies satisfy a mild no-overbidding condition, depend only on the bidder's valuation curve, and the bidder can focus on a finite subset without loss of generality. Though the subset size is exponential in m, we design a polynomial-time learning algorithm that achieves sublinear regret, both in full-information and bandit settings, relative to the hindsight-optimal safe strategy. We assess the robustness of safe strategies against the hindsight-optimal strategy from a richer class. We define the richness ratio α ∈ (0, 1] as the minimum ratio of the value of the optimal safe strategy to that of the optimal strategy from richer class and construct hard instances showing the tightness of α. Our algorithm achieves α-approximate sublinear regret against these stronger benchmarks. Simulations on semi-synthetic auction data show that empirical richness ratios significantly outperform the theoretical worst-case bounds. The proposed safe strategies and learning algorithm extend naturally to more nuanced buyer and competitor models.
Bio: Negin Golrezaei is the Theresa Seley Associate Professor of Management Science and an Associate Professor of Operations Management at the MIT Sloan School of Management. Her research focuses on advancing digital marketplaces—such as e-commerce, online advertising, and emissions trading systems—through data-driven strategies and algorithmic innovations. She aims to create more resilient, equitable, and sustainable digital ecosystems. In addition to her academic role, Negin has served as a visiting scholar at Google Research and Meta, where she collaborated with research and product teams to design and test new mechanisms for online marketplaces. Before joining MIT, she was a postdoctoral fellow at Google Research in New York, working with the Market Algorithms team. She holds a BSc (2007) and MSc (2009) in Electrical Engineering from Sharif University of Technology, Iran, and a PhD (2017) in Operations Research from the University of Southern California.
Moshe Tennenholtz
Artificial Social Intelligence
Talk details
Artificial intelligence (AI) has been growing at an unprecedented pace. Many of us have experienced a “ChatGPT moment” — a realization that AI will profoundly transform our lives. While numerous challenges and calls for improvement remain, there is little doubt that AI agents will play a central role in shaping our future. We argue, however, that the prevailing perspective on AI agent design is insufficient for achieving desirable social welfare, not merely due to computational or regulatory constraints. While it is understood that AI agents should be orchestrated in order to be used by an organization, and that system-level outcomes depend not only on the design of individual agents, the far more intricate reality is that the combination of misaligned incentives and incompatible technological designs may lead to poor social outcomes. Our argument is not merely conceptual but constitutes a concrete call to action: to establish a systematic research agenda on Artificial Social Intelligence, tackling multi-agent alignment among incentive-wise and technology-wise diverse AI agents. We illustrate this vision through four complementary research directions: (i) understanding multi-agent alignment in information retrieval (search, RAG, attribution) ecosystems, (ii) analyzing model selection in language-based economics as a strategic choice, (iii) rethinking fairness and regulation through the lens of multi-agent ethics, and (iv) designing hybrid social laws for human-AI coexistence. Together, these directions outline a roadmap toward welfare-maximizing AI societies— an essential step toward socially aligned intelligence.
Bio: Moshe Tennenholtz is a professor with the Technion -- Israel Institute of Technology, where he joined on 1993, and holds the Sondheimer Technion Academic Chair. In 2008 Moshe founded the Microsoft Research activity in Israel, and served as its leader until 2014, with significant contributions and distinguished ROI. He was also the founder of the Technion-Microsoft research center, and served as his scientific director, and served as co-founder and chief scientist of several startups. In joint work with colleagues and students he introduced several contributions to the interplay between artificial intelligence to game theory / economics, such as the study of artificial social systems, co-learning, non-cooperative computing, distributed games, the axiomatic approach to ranking, reputation, recommendation and trust systems, competitive safety analysis, program equilibrium, mediated equilibrium, learning equilibrium, as well the first near-optimal algorithm for reinforcement learning in adversarial contexts.
Jon Kleinberg
Superhuman AI in a Complex Human Ecosystem: Chess as a Model Domain
Talk details
In domains where AI systems have achieved superhuman performance, there is an opportunity to study the similarities and contrasts between human and AI behaviors at the level of granular decisions, not just aggregate performance. This type of analysis can yield several potential sources of insight. First, by studying expert-level human decisions through the lens of systems that far surpass this performance, we can try to characterize the settings in which humans errors are most likely to occur. Second, we can try to design systems whose decisions match human ones as closely as possible. And finally, we can ask whether it is possible to adapt superhuman AI so that its decisions can be usefully interleaved with human decisions, making them compatible in a way that allows collaboration. We pursue these goals in a domain with a long history in AI: chess. For our purposes, chess provides a setting with many different levels of human expertise; like other domains where people acquire expertise and mastery, it is a context in which people train over many years, drawing on more than a century of scholarship in the area, and acquire levels of skill far beyond what most practitioners can ever hope to achieve. And yet if we construe the goal of chess to be the winning of chess games, then algorithms have long since surpassed human beings, and by an increasingly enormous margin, allowing us to study what happens when powerful algorithms are introduced into a domain like this.
We'll discuss a line of work that predicts human decisions in chess at a move-by-move level much more accurately than existing chess engines, and in a way that is tunable to fine-grained differences in human skill; then we'll talk about extensions that use this framework to create AI chess agents that are simultaneously superhuman but also more compatible with human decision-making. We'll use these results to reflect on what we can learn from chess as a setting that simultaneously exhibits both very high levels of human skill and AI that has progressed far into superhuman levels of ability. The talk is based on joint work with Ashton Anderson, Solon Barocas, Karim Hamade, Difan Jiao, Reid McIlroy-Young, Sendhil Mullainathan, Siddhartha Sen, Zhenwei Tang, Russell Wang, and Eric Xue.
Bio: Jon Kleinberg is the Tisch University Professor in the Departments of Computer Science and Information Science at Cornell University. His research focuses on the interaction of algorithms and networks, the roles they play in large-scale social and information systems, and their broader societal implications. He is a member of the National Academy of Sciences, the National Academy of Engineering, the American Academy of Arts and Sciences, and the American Philosophical Society, and he has served on advisory groups including the National AI Advisory Committee (NAIAC) and the National Research Council's Computer Science and Telecommunications Board (CSTB) and Committee on Science, Technology, and Law (CSTL). He has received MacArthur, Packard, Simons, Sloan, and Vannevar Bush research fellowships, as well as awards including the the Nevanlinna Prize, the World Laureates Association Prize, the ACM/AAAI Allen Newell Award, and the ACM Prize in Computing.
Sebastien Bubeck
Recent advances in LLMs for Mathematics
Talk details
I will review the progress of large language models for mathematics over the last 3 years, from barely solving high school level mathematics to solving some minor open problems in convex optimization, combinatorics and probability theory. The emphasis will be on trying to identify the shape of the current frontier capabilities, as it stands today, finding out both where it's helpful and where it's still falling short as a research assistant.
Bio: Sebastien Bubeck is currently a research lead at OpenAI. Previously he served as VP AI and Distinguished Scientist at Microsoft, spending 10 years in Microsoft Research, and before that he was an assistant professor at Princeton University. His work on machine learning, convex optimization and online algorithms won several best paper awards, and more recently his work on Large (and Small) Language Models, including their applications to science, were featured in mainstream media such as the New York Times and Wired.
Christian Borgs
Are travel bans effective in containing the spread of a disease?
Talk details
In this talk, I present a mathematical model for the spread of an epidemic from one community to another via travel. Here each community is modeled by a random network (for simplicity, we assume it is an Erdos-Renyi random graph), with the epidemic spread inside the community given by the SIR model on this graph. Travel is modeled by individuals moving from one community to the other at some rate eta_T, and returning home at another rate eta_H. We assume that the return rate is of the same order as the recovery rate of the epidemic, while eta_T is much smaller. Under this assumption, we rigorously prove that if an epidemic starts in the first community, and the second community enacts a travel ban at the moment the epidemic is large enough to be detectable, such a travel ban is ineffective in preventing a large outbreak in the second community. But contrast, other mitigation measure like masks or vaccinations (modeled by reducing the rate of infections in the second community) are effective.
Bio: Christian Borgs is professor in the Berkeley AI Research Group (BAIR) in the EECS department at Berkeley, and faculty director of the Bakar Institute of Digital Materials for the Planet. Borgs is a Fellow of the American Mathematical Society, and the American Association for the Advancement of Science. Borgs current research focuses on both AI for science and the science of networks, including mathematical foundations, particularly the theory of graph limits aka Graphons (which he co-invented about 15 years ago), graph processes, graph algorithms, and applications of graph theory from economics to systems biology and epidemics.
Adam Kalai
Why Language Models Hallucinate
Talk details
Large language models (LLMs) sometimes generate statements that are plausible but factually incorrect—a phenomenon commonly called "hallucination." We argue that these errors are not mysterious failures of architecture or reasoning, but rather predictable consequences of standard training and evaluation incentives. We show (i) that hallucinations can be viewed as classification errors: when pretrained models cannot reliably distinguish a false statement from a true one, they may produce the false option rather than saying I don't know; (ii) that optimization of benchmark performance encourages guessing rather than abstaining, since most evaluation metrics penalize expressing uncertainty; and (iii) that a possible mitigation path lies in revising existing benchmarks to reward calibrated abstention, thus realigning incentives in model development. Joint work with Santosh Vempala (Georgia Tech) and Ofir Nachum & Edwin Zhang (OpenAI).
Bio: Adam Tauman Kalai is a Research Scientist at OpenAI, specializing in AI Safety and Ethics. His research interests also include algorithms, AI theory, and game theory. Adam earned his BA from Harvard University and his PhD from Carnegie Mellon University, after which he served as an Assistant Professor at TTIC and Georgia Tech and a Senior Principal Researcher at Microsoft Research New England. He is also a member of Project CETI's science team.
Sarah Cen
Bridging the Gap Between Research and Policy in AI Safety and Accountability
Talk details
As AI becomes increasingly integrated into both the private and public sectors, challenges around AI safety and policy have arisen. There is a growing, compelling body of work around the legal and societal challenges that come with AI, but there is a gap in our rigorous understanding of these problems. In this talk, I dive deep into a few topics in AI safety and policy. We will discuss AI supply chains (the increasingly complex ecosystem of AI actors and components that contribute to AI products) and study how AI supply chains complicate machine learning objectives. We'll then shift our discussion to AI audits and evidentiary burdens in cases involving AI. Using Pareto frontiers as a tool for assessing performance-fairness tradeoffs, we will show how a closed-form expression for performance-fairness Pareto frontiers can help plaintiffs (or auditors) overcome evidentiary burdens or a lack of access in AI contexts. I'll conclude with a longitudinal study of LLMs during the 2024 US election season. If time permits, we may touch on formal notions of trustworthiness.
Bio: Sarah Cen is a postdoc at Stanford University and incoming Assistant Professor at Carnegie Mellon University's Departments of ECE & EPP. At Stanford, Sarah works with Prof. Percy Liang in Computer Science and Prof. Daniel Ho in the Stanford Law School. Her research is interdisciplinary and inspired by works in machine learning, economics, law, and policy. She has ongoing work on algorithmic auditing, AI supply chains, due process for AI determinations, risk under the EU AI Act, and formalizing trustworthy algorithms. Previously, Sarah received her BSE in Mechanical Engineering from Princeton University and Master's in Engineering Science (Robotics) from Oxford University, where she worked on autonomous vehicles.
Dylan Hadfield-Menell
Building aligned agents for open-universe tasks
Talk details
As agents move from the lab into real-world settings, designers have a limited ability to anticipate the agent's context and design explicit safeguards. In this talk, I will outline challenges that this raises from the perspective of designing flexible, robust, and aligned agent behaviors. The key to the approach is to design agents that can model and respond to appropriate uncertainty about a user's intended goal and the normative environment they are deployed into. I will begin with a survey of current alignment techniques and AI agents, then outline the theoretical motivation for this approach. Next, I will describe recent work from my lab that attempts to address this problem by 1) designing flexible goal inference mechanisms that can track the set of plausible user goals reliably from context; and 2) integrating these inference tools with efficient agent designs that leverage POMDP solvers in order to train agents that implement belief-constrained behaviors. I will conclude with a discussion of recent work that evaluates collaborative agents and discuss the implications for the design of aligned systems that augment and integrate with human users and intent.
Bio: Dylan Hadfield-Menell is an Associate Professor of EECS at MIT. His research develops methods to ensure that AI systems behavior aligns with the goals and values of their human users and society as a whole, a concept known as 'AI alignment'. His goal is to enable the safe, beneficial, and trustworthy deployment of AI in real-world settings.
Connor Lawless
Democratizing Optimization via Generative AI
Talk details
From healthcare delivery to resilient power grid management, optimization has the potential to improve decision-making for some of today's most pressing problems, but its use is often limited by the mathematical expertise required to model and solve complex problems. This talk will showcase the potential of generative AI to lower this barrier and democratize access to advanced optimization tools. Motivated by a collaboration with Microsoft Outlook, the first part of the talk will present a novel framework for interactive decision support for non-expert users that leverages large language models (LLM) to translate user requests into an underlying constraint programming model. We investigate this framework through the lens of meeting scheduling, and showcase its potential via a user study with a prototype system. In the second part of the talk, we demonstrate how LLMs can be used to automatically generate problem-specific optimization solver configurations, a challenging task for even expert optimization users. Our approach achieves up to 70% speed-ups over default solver settings with little-to-no additional compute. We will conclude by discussing broader opportunities for integrating natural language and optimization, moving toward a future where powerful decision-making tools are as accessible for managers at a local food bank as they are for applied scientists at Amazon.
Bio: Connor Lawless is a Postdoctoral Fellow at the Stanford Institute for Human- Centered Artificial Intelligence advised by Ellen Vitercik and Madeleine Udell. His research blends tools from optimization, machine learning, and human-computer interaction to make advanced analytics tools more accessible and trustworthy. He received his PhD in Operations Research from Cornell University where he was advised by Oktay Gunluk, and previously spent time at Microsoft Research, IBM Research, and the Royal Bank of Canada.
Alice Oh
LLM Evaluation for the Real World
Talk details
Traditional evaluation methods for large language models (LLMs)—often centered on accuracy in static multiple-choice or short-answer questions—fail to capture real-world complexities. As LLMs increasingly serve users in dynamic, multicultural contexts, we must redefine meaningful evaluation. This talk presents our recent research advancing LLM evaluation through culturally aware, socially grounded, and customizable benchmarks. We assess factual consistency across languages, everyday knowledge in underrepresented cultures, and cultural inclusivity. We highlight that biases become evident in generation tasks, reflecting actual LLM use. Central to our approach is BenchHub, a unified benchmark suite categorizing over 300,000 questions across diverse domains and cultures, enabling tailored evaluations. BenchHub underscores domain-specific variations and the critical role benchmark composition plays in LLM performance rankings. These insights demonstrate that accuracy alone is insufficient; comprehensive LLM evaluation must consider culture, context, and customization. This talk advocates a broader evaluation agenda, presenting foundational steps toward robust, inclusive assessments.
Bio: Alice Oh is a Professor in the School of Computing at KAIST. Her major research area is at the intersection of natural language processing (NLP) and computational social science, with a recent focus on multilingual and multicultural aspects of LLMs. She collaborates with scholars in humanities and social sciences such as political science, education, and history. She has served as Program Chair for ICLR 2021 and NeurIPS 2022, General Chair for ACM FAccT 2022 and NeurIPS 2023, and DEI Chair for COLM 2024. She is the current President of SIGDAT which oversees EMNLP.
Nika Haghtalab
Distortion of Learning and AI Alignment from Heterogenous Human Feedback
Talk details
After pre-training, large language models are aligned with human preferences based on crowdsourced pairwise comparisons. State-of-the-art alignment methods (such as PPO-based RLHF and DPO) are built on the assumption of aligning with a single preference model, despite being deployed in settings where users have diverse preferences. As a result, it is not even clear that these alignment methods produce models that satisfy users in any meaningful way. In this work, we ask a deceptively simple yet foundational question: Do state-of-the-art alignment methods actually produce models that satisfy users on average in the presence of heterogeneous preferences? Drawing on social choice theory, and modeling each user's comparisons via an individual Bradley–Terry (BT) model, we introduce the distortion of an alignment method: the worst-case ratio between the optimal achievable average utility and the average utility of the learned policy. This notion yields concrete insights into alignment with heterogeneous preferences. In particular, we establish an impossibility result for aligning to average user utility — counter to the conventional wisdom that ML methods, even if imperfect for every individual, at least perform well on average. Distortion also highlights sharp differences between alignment methods: we show that widely used approaches such as RLHF and DPO can have exponentially large — or even unbounded — distortion, whereas a constant minimax-optimal distortion is achievable via a method inspired by social choice theory, known as maximal lotteries, or Nash Learning from Human Feedback.
Bio: Nika Haghtalab is an Assistant Professor in the Department of Electrical Engineering and Computer Sciences at UC Berkeley. She works on a broad and versatile set of problems related to machine learning, algorithms, economics, and society. Her work contributes to an emerging mathematical foundation for learning and decision-making systems in the presence of economic and societal forces. Her work has been recognized by a Sloan fellowship (2024), Schmidt Sciences AI2050 award, NSF CAREER (2022), Google Research Scholar award (2023), NeurIPS and ICAPS best paper awards, EC exemplary track paper awards, and several other industry awards and fellowships.
Andrew Ilyas
Data Attribution, Selection, and Valuation at Scale with Metagradients
Talk details
Training data is now recognized as a key driver the performance of AI systems. Indeed, AI companies are signing multi-million dollar deals for training data acquisition, raising the question: how "should" this training data be priced? Understanding how to value training data requires us to understand the downstream impact of this data on model behavior---which is made challenging by the complex, uninterpretable nature of large-scale ML models.
In the first part of this talk, we present some recent work on tracing back model performance to training data---improving on a long line of prior work in machine learning, our method can optimally (in a natural sense) predict the impact of training data on model performance. In the second part of the talk, we propose a framework for studying data pricing theoretically, inspired by our experimental results in the first part of the talk. We conclude with some open questions and directions.
Bio: Andrew is an incoming Assistant Professor at CMU. Previously, he was a Stein Fellow at Stanford and a PhD student at MIT, where he was supported by an Open Philanthropy AI Fellowship. His interests are currently in understanding and predicting the effects of design choices on downstream machine learning systems.
2024-25
Nick Arnosti
Greedy Algorithms for Dynamic Matching
Talk details
We study a foundational model of dynamic matching market with abandonment. This model has been studied by Collina et al (2020) and Aouad and Saritac (2022), and many other papers have considered special cases. We compare the performance of greedy policies -- which identify a set of "acceptable" matches up front, and perform these matches as soon as possible -- to that of an omniscient benchmark which knows the full arrival and departure sequence.
Bio: Nick Arnosti is an Assistant Professor in the Department of Industrial and Systems Engineering (ISyE) at the University of Minnesota. He earned his Ph.D. in Operations Research from Stanford University in 2016, advised by Ramesh Johari and Paul Milgrom. Arnosti’s research centers on market-design questions for allocating social goods—such as public good and school seats—with a particular emphasis on the lotteries and waitlists used to distribute affordable-housing units.
Zoe Hitzing
Contextually Private Mechanisms
Talk details
We introduce a framework for comparing the privacy of different dynamic mechanisms. A mechanism designer employs a dynamic protocol to elicit agents’ private information. Protocols produce a set of contextual privacy violations—information learned about agents that may be superfluous given the context. A protocol is maximally contextually private if there is no protocol that produces a subset of the violations it produces, while still implementing the choice rule. We show that selecting a maximally contextually private protocol involves a deliberate decision about whose privacy is most important to protect, and these protocols delay questions to those they aim to protect. Taking the second-price auction rule as an instructive example, we derive two novel designs that are maximally contextually private: the ascending-join and overdescending-join protocols.
Bio: Zoë Hitzig is a Junior Fellow at the Harvard Society of Fellows (on leave) and a Research Scientist at OpenAI.
Nikhil Garg
Recommendations in high-stakes settings
Talk details
Recommendation systems are now used in high-stakes settings, including to help find jobs, schools, and partners. Building public-interest recommender systems in such settings brings both individual-level (enabling exploration, diversity, data quality) and societal (fairness, capacity constraints, algorithmic monoculture) challenges. In this talk, I'll discuss our theoretical, empirical, and deployment work in tackling these challenges, including ongoing work on (a) applicant behavior and recommendations for the NYC HS match, (b) a platform to help discharge patients to long-term-care facilities, and (c) feed-ranking algorithms on Bluesky for research-paper recommendations.
Bio: Nikhil Garg is an assistant professor of Operations Research and Information Engineering (ORIE) at Cornell Tech. His work has received several awards, including NSF CAREER, the INFORMS George Dantzig Dissertation Award, the ACM SIGecom Dissertation Award (Honorable Mention), Forbes 30 Under 30 for Science, and the NSF Graduate Research Fellowship. Previously, he received an MS and PhD from Stanford in 2020, where he was advised by Prof. Ashish Goel and Prof. Ramesh Johari.
Nicholas Christakis
Social Artificial Intelligence
Talk details
The impact of artificial intelligence (AI) transcends the simple case of human-machine interactions and extends to human-human interactions in the presence of AI. Here, I explore such “hybrid systems” of humans and machines. Our large-sample experiments show how the careful yet simple programming of AI agents can enhance the performance of human groups, making people within such groups better able to cooperate, coordinate, innovate, and communicate, ultimately contributing to their superior performance. On the other hand, both simple and complex forms of AI (such as large language models) can also do the opposite, harming groups of people and our society as a whole. Our experiments show how AI agents can affect social processes and human performance in settings as diverse as people working together online or coordinating their movement on roadways. Our work, in short, does not involve the development of super-smart AI to replace human cognition, but rather “dumb AI” to supplement human interaction. These findings reveal what the disruptive introduction of AI into our lives means for the future of human social behavior. And they suggest ways to design AI — as a type of “social catalyst” — so as to make sure it supports a utopian rather than dystopian future.
Bio: Nicholas A. Christakis, MD, PhD, MPH, is a social scientist and physician at Yale University who conducts research in the fields of network science, biosocial science, and computational social science. His current work focuses on how human biology and health affect, and are affected by, social interactions and social networks. Dr. Christakis directs the Human Nature Lab and is the Director of the Yale Institute for Network Science.
Evi Micha
Fair and Representative Citizens' Assemblies
Talk details
Sortition is based on the idea of choosing randomly selected representatives for decision-making. The main properties that make sortition particularly appealing are fairness and proportional representation. When a population lies on a representation metric, we formally define proportional representation using a notion called the core. Thus, we ask: Can we design a selection algorithm that satisfies fairness and the core simultaneously? We answer this question affirmatively and present an efficient selection algorithm, called Fair Greedy Capture, that is fair and provides a constant-factor approximation to the optimal core.
Bio: Evi Micha is an assistant professor in the Thomas Lord Department of Computer Science at the University of Southern California. She did her postdoc at Harvard University and obtained her Ph.D. from the University of Toronto. Her research interests lie at the intersection of computer science and economics and span areas such as algorithmic fairness and computational social choice. One of her recent papers was selected as exemplary in the applied-modeling track of the ACM Conference on Economics and Computation. Her research has been awarded the 2024 Best Dissertation Award from the Canadian AI Association and was runner-up for the 2024 IFAAMAS Victor Lesser Distinguished Dissertation Award.
Cora Kyler
Getting the Right Data: The Hidden Challenge of Dating Apps
Talk details
Bio: Cora co-founded soon.dating, a coding project with her best friend that got popular in San Francisco last year. Before soon, she was a PhD student at UC Berkeley studying mathematical logic and philosophy. While building soon, she became entrenched in the data problem along the way. The talk will explore why gathering meaningful data is the true challenge in building effective dating platforms. While the solution might seem obvious, she'll discuss why getting the right data is both more crucial and more difficult than it appears.
Jay Baxter
Community Notes: Under the Hood
Talk details
Community Notes empowers people on X to collaboratively add context to potentially misleading posts. Community Notes have been rated as more trustworthy (bipartisanly) than simple misinformation flags, and cause users to organically like and share noted posts significantly less often. This talk will explore the algorithm behind X's Community Notes, including bridging-based ranking (elevating consensus from people who often disagree via matrix factorization) and a reputation system. We will also touch on newer ideas that aren't yet in production, e.g., generating notes that are predicted to be rated helpful by raters with a diverse set of viewpoints.
Bio: Jay Baxter is a Sr. Staff Machine Learning Engineer at X and was the founding ML lead on Community Notes. He was previously a tech lead in Twitter Cortex Applied Research, focusing on user modeling and large-scale, real-time recommender systems. He holds an MEng and SB in EECS from MIT, where he built BayesDB, a probabilistic database.
Jon Kleinberg
Language Generation in the Limit
Talk details
Although current large language models are complex, the most basic specifications of the underlying language generation problem itself are simple to state: given a finite set of training samples from an unknown language, produce valid new strings from the language that don't already appear in the training data. Here we ask what we can conclude about language generation using only this specification, without further properties or distributional assumptions. In particular, we consider models in which an adversary enumerates the strings of an unknown target language that is known only to come from one of a possibly infinite list of candidates, and the goal is to generate new strings from this target language; we show that it is possible to give certain non-trivial guarantees for language generation in this setting. The resulting guarantees contrast dramatically with negative results due to Gold and Angluin in a well-studied model of language learning where the goal is to identify an unknown language from samples; the difference between these results suggests that identifying a language is a fundamentally different problem than generating from it. (This is joint work with Sendhil Mullainathan.)
Bio: Jon Kleinberg is the Tisch University Professor in the Departments of Computer Science and Information Science at Cornell University. His research focuses on the interaction of algorithms and networks, the roles they play in large-scale social and information systems, and their broader societal implications. He is a member of the National Academy of Sciences, the National Academy of Engineering, the American Academy of Arts and Sciences, and the American Philosophical Society, and he serves on the U.S. National AI Advisory Committee. He has received MacArthur, Packard, Simons, Sloan, and Vannevar Bush research fellowships, as well as awards including the Harvey Prize, the Lanchester Prize, the Nevanlinna Prize, the World Laureates Association Prize, and the ACM Prize in Computing.
Vinay Rao
Deployment Safeguards for AI Models
Talk details
Bio: Vinay Rao leads Anthropic's Trust and Safety team, which develops and enforces policies governing Claude's real-world applications. His team focuses on mitigating catastrophic risks as well as critical risks such as election interference, child safety, and misinformation. They also play a key role in securing Anthropic's models to comply with the company's Responsible Scaling Policy for safe and ethical AI development and deployment. With nearly two decades of experience in trust and safety, Vinay has built and managed leading Trust and Safety functions at major tech companies, including YouTube, Google, Airbnb, and Stripe.
Amy Greenwald
Solving Games Forwards and Backwards
Talk details
Computing equilibria in games is a problem of great interest in both economics and computer science. We present a min-max formulation of this problem, in which the minimizer seeks an equilibrium solution for the game, while the maximizer seeks to find fault with the proposed solutions. We call this the "forward" problem. In the "backwards" problem, we are instead given an equilibrium and a parameterized game, and we are interested in inferring a game from that equilibrium—that is, identifying the game parameters that induce the observed equilibrium. We consider the backwards problem under increasingly weaker assumptions, ranging from inverse multi-agent planning to inverse multi-agent learning and beyond, each with corresponding min-max formulations. While it can be difficult to ensure that the min-max formulation of a forward problem is convex-concave (and thus amenable to solutions such as gradient-descent ascent), we find it easier to ensure that the min-max formulation of a backward problem is convex-concave. We apply our backwards method to Spanish electricity-market time-series data and then push the inferred game forward to predict future market prices. (Joint work with Denizalp Goktas and Sadie Zhao.)
Bio: Amy Greenwald is a Professor of Computer Science at Brown University in Providence, Rhode Island. Her research focuses on game-theoretic and economic interactions among computational agents, with applications to automated bidding and negotiation in domains ranging from advertising auctions to supply chains. She is also active in promoting diversity in computer science, leading multiple K-12 initiatives in the Providence public schools.
Weijie Zhong
Rank-Guaranteed Auctions
Talk details
We propose a combinatorial ascending auction that is "approximately" optimal, requiring minimal rationality to achieve this level of optimality, and is robust to strategic and distributional uncertainties. Specifically, the auction is rank-guaranteed, meaning that for any menu M and any valuation profile, the ex-post revenue is guaranteed to be at least as high as the highest revenue achievable from feasible allocations, taking the (|M| + 1)th-highest valuation for each bundle as the price. Our analysis highlights a crucial aspect of combinatorial-auction design, namely, the design of menus. We provide simple and approximately optimal menus in various settings.
Bio: Weijie Zhong is an Assistant Professor of Economics at the Stanford Graduate School of Business. He specializes in microeconomic theory, focusing on how information influences individual behavior and market outcomes. His recent research delves into optimal ways to dynamically acquire information to aid decision-making.
Pengyu Qian
Incentivizing Resource Pooling
Talk details
Resource pooling improves system efficiency drastically in large stochastic systems, but its effective implementation in decentralized systems remains relatively underexplored. This paper studies how to incentivize resource pooling when agents are self-interested and their states are private information. Our primary motivation is applications in the design of decentralized computing markets, among others. We study a standard multi-server queueing model in which each server is associated with an M/M/1 queue and aims to minimize its time-average job holding and processing costs. We design a simple token-based mechanism where servers can earn tokens by offering help and spend tokens to request help from other servers, all in their self-interest. The mechanism induces a complex game among servers. We employ the fluid mean-field equilibrium (FMFE) concept to analyze the system, combining mean-field approximation with fluid relaxation. This framework enables us to derive a closed-form characterization of servers' FMFE strategies. We show that these FMFE strategies approximate well the servers' rational behavior. We leverage this framework to optimize the design of the mechanism and present our main results: As the number of servers increases, the proposed mechanism incentivizes complete resource pooling—namely, the system dynamics and performance under our mechanism match those under centralized control.
Bio: Pengyu Qian is an Assistant Professor in the Operations & Technology Management department at the Questrom School of Business, Boston University. His research studies the design and analysis of marketplaces in dynamic settings, using tools from probability, optimization, and game theory. He is interested in foundational models driven by challenges in the sharing economy and the allocation of public resources. His research emphasizes algorithms and mechanisms that not only have good theoretical guarantees but also are simple, robust, and practical for real-world systems. Pengyu is a recipient of the INFORMS JFIG Best Paper Prize. He earned his Ph.D. from Columbia Business School and his B.S. from Peking University.
Noam Brown
Learning to Reason with LLMs
Talk details
Large language models (LLMs) have demonstrated remarkable capabilities in generating coherent text and completing various natural-language tasks. Nevertheless, their ability to perform complex, general reasoning has remained limited. In this talk, I will describe OpenAI's new o1 model, an LLM trained via reinforcement learning to generate a hidden chain of thought before its response. We have found that the performance of o1 consistently improves with more reinforcement-learning compute and with more inference compute. o1 surpasses previous state-of-the-art models on a variety of benchmarks that require reasoning, including mathematics competitions, programming contests, and advanced science question sets. I will discuss the implications of scaling this paradigm even further.
Bio: Noam Brown is a research scientist at OpenAI investigating reasoning and multi-agent AI. He co-created Libratus and Pluribus, the first AIs to defeat top humans in two-player no-limit poker and multiplayer no-limit poker, respectively, and Cicero, the first AI to achieve human-level performance in the natural-language strategy game Diplomacy. He has received the Marvin Minsky Medal for Outstanding Achievements in AI, was named one of MIT Technology Review's 35 Innovators Under 35, and his work on Pluribus was named by *Science* as one of the top 10 scientific breakthroughs of 2019. Noam received his Ph.D. from Carnegie Mellon University.
Daniel Freund
The Dedicated Docket in U.S. Immigration Courts: An Analysis of Fairness and Efficiency Properties
Talk details
In this talk I will give an overview of my recent work at the intersection of humanitarian immigration and operations, with a particular focus on the dedicated docket program. The dedicated docket was introduced by the Biden Administration to reform the asylum system. It creates a separate queue for court proceedings in which judges are supposed to issue decisions for each case within a target time frame. Its goals are to improve speed, accuracy, and fairness. Though it meets its first goal, legal advocacy groups report that this comes at the expense of the last. Referring to it as a "denial of justice," they find that cases on the dedicated docket routinely fail to access legal representation and have a much lower asylum-grant rate. Against this backdrop, we study the operational implications of a dedicated-docket system. We develop a queueing model in which a policy-maker routes asylees to the regular or the dedicated docket and sets a delay target for the latter. Constrained by the target, the court allocates its capacity to minimize average delay, and immigration lawyers schedule their time between dockets to maximize the rate of successful asylum cases. Compared to a single docket, we show that the dedicated-docket system can Pareto-improve speed and accuracy. However, we also prove that the system satisfies two natural fairness rules only if it is dominated in speed and accuracy by the single docket. Our analysis can guide public discourse by informing both policymakers and legal advocacy groups of the necessary trade-offs involved in scheduling decisions in the asylum context. (Joint work with Wentao Weng.) A preprint of the paper is available at https://papers.ssrn.com/sol3/papers.cfm?abstract_id=4785713.
Bio: Daniel Freund is an Assistant Professor of Operations Management at the MIT Sloan School of Management. His research applies optimization, stochastic modeling, and revenue-management techniques to problems in transportation, online platforms, and humanitarian immigration, among others. His work has been recognized with the George B. Dantzig Dissertation Award (2018), the Daniel H. Wagner Prize (2018), and several INFORMS best-paper prizes. He frequently serves as an associate editor for *Operations Research* and *Transportation Science*, and on program committees for conferences such as EC, EAAMO, and TheWebConf.
2023-24
Elaine Shi
Decentralized Mechanism Design
Talk details
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.
Alex Teytelboym
Equilibrium Existence and Implementability
Talk details
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).
Emre Kiciman
Causal inference and LLMs: A new frontier
Talk details
The causal capabilities of large language models (LLMs) is a matter of significant debate, with critical implications for the use of LLMs in societally impactful domains such as medicine, science, law, and policy. We further our understanding of LLMs and their causal implications, considering the distinctions between different types of causal reasoning tasks, as well as the entangled threats of construct and measurement validity. LLM-based methods establish new state-of-the-art accuracies on multiple causal benchmarks. Algorithms based on GPT-3.5 and 4 outperform existing algorithms on a pairwise causal discovery task (97%, 13 points gain), counterfactual reasoning task (92%, 20 points gain), and actual causality (86% accuracy in determining necessary and sufficient causes in vignettes). At the same time, LLMs exhibit unpredictable failure modes and we provide some techniques to interpret their robustness.
Crucially, LLMs perform these causal tasks while relying on sources of knowledge and methods distinct from and complementary to non-LLM based approaches. Specifically, LLMs bring capabilities so far understood to be restricted to humans, such as using collected knowledge to generate causal graphs or identifying background causal context from natural language. We envision LLMs to be used alongside existing causal methods, as a proxy for human domain knowledge and to reduce human effort in setting up a causal analysis, one of the biggest impediments to the widespread adoption of causal methods. We also see existing causal methods as promising tools for LLMs to formalize, validate, and communicate their reasoning especially in high-stakes scenarios.
In capturing common sense and domain knowledge about causal mechanisms and supporting translation between natural language and formal methods, LLMs open new frontiers for advancing the research, practice, and adoption of causality.
Bio: Emre Kiciman is a Senior Principal Researcher at Microsoft Research, where his research interests span causal inference, machine learning, the security of AI systems, and AI’s implications for people and society. Emre is a co-founder of the DoWhy library for causal machine learning. For publications and talks, please visit https://kiciman.org.
Jason Hartline
Regulation of Algorithmic Collusion
Talk details
Consider sellers in a competitive market that use algorithms to adapt their prices from data that they collect. In such a context it is plausible that algorithms could arrive at prices that are higher than the competitive prices and this may benefit sellers at the expense of consumers (i.e., the buyers in the market). This paper gives a definition of algorithmic non-collusion for pricing algorithms. The definition allows a regulator to empirically audit algorithms by applying a statistical test to the data that they collect. Algorithms that are good, i.e., approximately optimize prices to market conditions, can be augmented to collect the data sufficient to pass the audit. Algorithms that have colluded on, e.g., higher-than-competitive prices cannot pass the audit. The definition allows for the possession of useful side information which, e.g., may be correlated with supply and demand and should affect the prices used by good algorithms. The paper provides an analysis of the statistical complexity of such an audit, i.e., how much data is sufficient for the test of non-collusion to be accurate. Joint work with Sheng Long and Chenhao Zhang.
Bio: Jason Hartline received his Ph.D. in 2003 from the University of Washington under the supervision of Anna Karlin. He was a postdoctoral fellow at Carnegie Mellon University under the supervision of Avrim Blum; and subsequently a researcher at Microsoft Research in Silicon Valley. He joined Northwestern University in 2008 where he is a professor of computer science. He was on sabbatical at Harvard University in the Economics Department during the 2014 calendar year and visiting Microsoft Research, New England for the Spring of 2015. He is the director of Northwestern’s Online Markets Lab, he was a founding codirector of the Institute for Data, Econometrics, Algorithms, and Learning from 2019-2022, and is a cofounder of virtual conference organizing platform Virtual Chair.
Robert Kleinberg
U-Calibration: Forecasting for an Unknown Agent
Talk details
We consider the problem of evaluating forecasts of binary events when predictions are consumed by rational agents who take an action in response to a prediction, but whose utility is unknown to the forecaster. We show that optimizing forecasts for a single scoring rule (e.g., the Brier score) cannot guarantee low regret for all possible agents. In contrast, forecasts that are well-calibrated guarantee that all agents incur sublinear regret. However, calibration is not a necessary criterion here; it is possible for miscalibrated forecasts to provide good regret guarantees for all possible agents. Moreover, calibrated forecasting procedures have provably worse convergence rates than forecasting procedures targeting a single scoring rule. Motivated by this, we present a new metric for evaluating forecasts that we call U-calibration, equal to the maximal regret of the sequence of forecasts when evaluated under any bounded scoring rule. We show that sublinear U-calibration error is a necessary and sufficient condition for all agents to achieve sublinear regret guarantees. We additionally demonstrate how to compute the U-calibration error efficiently and provide an online algorithm that achieves asymptotically optimal U-calibration error (on par with optimal rates for optimizing for a single scoring rule, and bypassing lower bounds for the traditionally calibrated learning procedures). Finally, we discuss generalizations to the multiclass prediction setting. This talk is joint work with Renato Paes Leme, Jon Schneider, and Yifeng Teng.
Bio: Bobby Kleinberg is a Professor of Computer Science at Cornell University and a part-time Faculty Researcher at Google. His research concerns algorithms and their applications to machine learning, economics, networking, and other areas. Prior to receiving his doctorate from MIT in 2005, Kleinberg spent three years at Akamai Technologies; he and his co-workers received the 2018 SIGCOMM Networking Systems Award for pioneering the first Internet content delivery network. He is a Fellow of the ACM and a recipient of the ACM SIGecom Mid-Career Award for advancing the understanding of on-line learning and decision problems and their application to mechanism design.
Bruno Ribeiro
Causal Lifting and Causal Identification in Link Prediction using Neural Networks
Talk details
In this talk, we consider a small piece of the larger puzzle of endowing state-of-the-art neural networks with the ability to perform causal reasoning. First, we will cover the rich literature on causal identification under peer effects, both under intrinsic factors and path-dependent graph evolution models. Then, I will introduce “Causal Lifting”, which generalizes the earlier causal identification methods for both nodes and edges under network effects, also unveiling a fundamental difference between estimating causal effects on nodes from effects on edges. Finally, we will explore how Causal Lifting aligns causal identification seamlessly with how we design state-of-the-art neural network models for relational reasoning tasks, which can then be integrated with chatbots such as ChatGPT.
Bio: Bruno Ribeiro is an Associate Professor in the Department of Computer Science at Purdue University, currently a Visiting Associate Professor at Stanford University. Prior to joining Purdue in 2015, he earned his Ph.D. from the University of Massachusetts Amherst and was a postdoctoral fellow at Carnegie Mellon University. Ribeiro is interested in the intersection between relational learning and causality in deep learning. Ribeiro received an NSF CAREER award in 2020, an Amazon Research Award in 2022, and multiple best paper awards.
Shuchi Chawla
Revisiting revenue maximization for many buyers: buy-many mechanisms and sequential posted pricing
Talk details
A recent line of research has established a novel desideratum for designing approximately-revenue-optimal multi-item mechanisms, namely the buy-many constraint. Under this constraint, prices for different allocations made by the mechanism must be subadditive implying that the price of a bundle cannot exceed the sum of prices of individual items it contains. This natural constraint has enabled several positive results in multi-item mechanism design bypassing well-established impossibility results. Our work addresses a main open question from this literature involving the design of buy-many mechanisms for multiple buyers. We show that a simple sequential item pricing mechanism with buyer-specific prices can achieve an O(log m) approximation to the revenue of any buy-many mechanism when all buyers have unit-demand preferences over m items. This is the best approximation possible as it directly matches the previous results for the single-buyer setting where no simple mechanism can obtain a better approximation. En route to proving this result we define and prove a multi-dimensional online contention resolution scheme (OCRS) for revenue. This is joint work with Rojin Rezvan (UT-Austin), Yifeng Teng (Google Research), and Christos Tzamos (UW-Madison).
Bio: Shuchi Chawla holds an Endowed Professorship in Computer Science at UT-Austin and is an Amazon Scholar. Shuchi is a theoretical computer scientist specializing in the areas of algorithm design and economics and computation. Prior to joining UT-Austin, she spent 15 years as a professor of CS at the University of Wisconsin-Madison. Shuchi is the recipient of an NSF Career award, a Sloan Foundation fellowship, and several awards for her research and teaching at UW-Madison. Shuchi recently served as the PC Chair of SODA'20 and EC'21, and currently serves on the editorial boards of the SIAM Journal of Computing, the ACM Transactions on Algorithms and the ACM Transactions on Economics and Computation.
Grant Schoenebeck
Mechanisms To Procure Information Without Verification
Talk details
In a wide variety of contexts including peer grading, peer review, and crowd-sourcing (e.g. evaluating LLM outputs) we would like to design mechanisms which reward agents for producing high quality responses. Unfortunately, computing rewards by comparing to ground truth or gold standard is often cumbersome, costly, or impossible. Instead we would like to compare agent reports. First, we will argue the importance of creating measurements of agent response quality that are both accurate and strategy-proof (agents do not benefit by intentionally falsely reporting). Second, we will illustrate that previous solutions only achieve one of these desiderata: naïve mechanisms fail to be strategy-proof, yet existing strategy-proof mechanisms are much less accurate than the naïve mechanisms in evaluating response quality. Third, we will show how to create mechanisms that are both strategy-proof and (reasonably) accurate. The key theoretical technique is a variational interpretation of mutual information, which permits machine learning to estimate mutual information using only a few samples (and likely has other applications in machine learning even beyond the strategic settings). Finally, time permitting, we will survey future directions for the field.
Bio: Grant Schoenebeck is an associate professor at the University of Michigan in the school of information. His work spans diverse areas in theoretical computer science but has recently focused on combining ideas from theoretical computer science, machine learning, and economics (e.g game theory, mechanism design, and information design) to develop and analyze systems for eliciting and aggregating information from of diverse group of agents with varying information, interests, and abilities. His research is supported by the NSF including an NSF CAREER award. Before coming to the University of Michigan in 2012, he was a Postdoctoral Research Fellow at Princeton. Grant received his PhD at UC Berkeley, studied theology at Oxford University, and received his BA in mathematics and computer science from Harvard.
Yuqing Kong
Eliciting Information Without Verification from Humans and Machines
Talk details
Many application domains rely on eliciting high-quality (subjective) information. This presentation will talk about how to elicit and aggregate information from both human and machine participants, especially when the information cannot be directly verified. The first part of the talk presents a mechanism, DMI-Mechanism, designed to incentivize truth-telling in the setting where participants are assigned multiple multi-choice questions (e.g. what’s the quality of the above content? High/Low). DMI-Mechanism ensures that truthful responses are more rewarding than any less informative strategy. The implementation of DMI-Mechanism is straightforward, requiring no verification or prior knowledge, and involves only two participants and four questions for binary-choice scenarios. When applied to machine learning, DMI-Mechanism results in a loss function that is invariant to label noise. The second part of the talk discusses the elicitation of information not just from humans but also from machines. Recognizing the limitations in time and resources that humans and machines have, the talk introduces a method to elicit and analyze the 'thinking hierarchy' of both entities. This approach not only facilitates the aggregation of information when the majority of agents are at less sophisticated 'thinking' levels but also provides a unique way to compare humans and machines. This talk is based a series of works including Kong (SODA 2020, ITCS 2022, JACM 2024), Xu, Cao, Kong, Wang (NeurIPS 2019), Kong, Li, Zhang, Huang, Wu (NeurIPS 2022), Huang, Mei, Kong (2024).
Bio: Yuqing Kong is currently an assistant professor at The Center of Frontier Computing Science (CFCS), Peking University. She obtained her Ph.D. degree from the Computer Science and Engineering Department at University of Michigan in 2018 and her bachelor degree in mathematics from University of Science and Technology of China in 2013. Her research interests lie in the intersection of theoretical computer science and the areas of economics: information elicitation, prediction markets, mechanism design, and the future applications of these areas to crowdsourcing and machine learning.
Panos Toulis
Experimental Designs for Structural Economic Models on Large Networks
Talk details
This talk presents an ongoing large field experiment in a country of South America that randomizes tax audit notices (treatment) to firms connected through a large network of VAT transactions. While the ultimate goal is to optimize tax audit policy, the short-term goal is to estimate causal effects of tax audit notices on firm behavior. Of particular interest is to understand spillovers, that is, the response of firms that are not treated but are connected to other firms that are treated. First, I will discuss why current popular approaches to experimenting on networks are limited by the reality of inter-firm networks, such as their size, high interconnectivity and heavy-tailed degree distributions. I will then describe an approach to experimentation that leverages subtle sub-structures in the network. This approach is specifically designed to allow the application of Fisherian-style permutation tests of causal effects. These testing procedures are computationally efficient and finite-sample valid, qualities that are important for testing in a robust way the parameters of structural economic models.
Bio: Panos Toulis studies causal inference in complex settings (e.g., networks) through resampling methods such as permutation tests. These methods are model-agnostic and thus have a degree of robustness not afforded by classical model-based statistlcal methods. He is also interested in the design of experiments on networks, and generally the interface between statistics and optimization. His research has been published in the Journal of the Royal Statistical Society, Annals of Statistics, Biometrika, Journal of the Americal Statistical Association, Journal of Econometrics, Statistics and Computing, and Games and Economic Behavior, as well as in major machine learning and economics conferences. For his research, Toulis has received the Arthur P. Dempster Award from Harvard University’s Department of Statistics, the LinkedIn Economic Graph Challenge award, and the 2012 Google United States/Canada PhD Fellowship in statistics. Toulis got his PhD in statistics from Harvard University, advised by Edo Airoldi, David Parkes, and Don Rubin. He also holds MS degrees in statistics and computer science from Harvard University, and a BS in electrical and computer engineering from Aristotle University in Thessaloniki, Greece. Outside of academia, he has prior corporate experience in software engineering at Google Inc. and at startup companies in Greece. He also enjoys science fiction, history, and politics.
Yash Kanoria
Simulation is All You Need
Talk details
Motivated by online matching markets and network revenue management (NRM) problems with many types (e.g., fulfillment optimization), we study dynamic spatial matching (DSM) in which supply and demand live in d dimensional space and need to be matched with each other dynamically. If demand and supply have the same spatial distribution, greedy matching suffices, and achieves average match distance of the same order as the distance to the nearest neighbor, *except* for the case of d=1 and both supply and demand arriving dynamically over time. If demand and supply have different spatial distributions, the matching constraint has bite and greedy matching fails. We introduce a unifying and practical algorithmic principle for NRM and DSM dubbed SOAR: Simulate, Optimize, Assign, Repeat, which repeatedly simulates the future to enable good matching decisions. Simulating one sample path at each stage already enables SOAR to produce near optimal regret for the majority of NRM models in the literature, and for DSM with non-atomic demand and supply distributions. For more challenging NRM and DSM models, SOAR with multiple simulated sample paths at each stage achieves near optimal regret.
Bio: Yash Kanoria is an Associate Professor of Business in the Decision, Risk and Operations division at Columbia Business School, specializing in the design and optimization of marketplaces, especially matching markets. He obtained a BTech from IIT Bombay and a PhD from Stanford in Electrical Engineering. He has received a National Science Foundation CAREER Award, a Sigecom Test of Time Award, and an Operations Research Best Paper award for optimizing Amazon's outbound supply chain.
David Shmoys
Algorithmic Tools for Redistricting: Fairness via Analytics
Talk details
The American winner-take-all congressional district system empowers politicians to engineer electoral outcomes by manipulating district boundaries. To date, computational solutions mostly focus on drawing unbiased maps by ignoring political and demographic input, and instead simply optimize for compactness and other related metrics. However, we maintain that this is a flawed approach because compactness and fairness are orthogonal qualities; to achieve a meaningful notion of fairness, one needs to model political and demographic considerations, using historical data. We will discuss a series of papers that explore and develop this perspective. In the first (joint with Wes Gurnee), we present a scalable approach to explicitly optimize for arbitrary piecewise-linear definitions of fairness; this employs a stochastic hierarchical decomposition approach to produce an exponential number of distinct district plans that can be optimized via a standard set partitioning integer programming formulation. This enables a large-scale ensemble study of congressional districts, providing insights into the range of possible expected outcomes and the implications of this range on potential definitions of fairness. Further work extending this (joint with Julia Allen & Wes Gurnee), shows that many additional real-world constraints can be easily adapted in this framework (such as minimal county splits as was recently required in Alabama legislation in response to the US Supreme Court decision Milligan v. Alabama). In another paper (joint with Nikhil Garg, Wes Gurnee, and David Rothschild), we study the design of multi-member districts (MMDs) in which each district elects multiple representatives, potentially through a non-winner-takes-all voting rule (as was proposed in H.R. 4000). We carry out large-scale analyses for the U.S. House of Representatives under MMDs with different social choice functions, under algorithmically generated maps optimized for either partisan benefit or proportionality. We find that with three-member districts using Single Transferable Vote, fairness-minded independent commissions can achieve proportional outcomes in every state (up to rounding), and this would significantly curtail the power of advantage-seeking partisans to gerrymander.
Bio: David Shmoys is the Laibe/Acheson Professor and Director for the Center for Data Science for Enterprise & Society at Cornell University. He obtained his Ph.D. in computer science from the University of California at Berkeley in 1984, and held postdoctoral positions at MSRI in Berkeley and Harvard University, and a faculty position at MIT before joining the Cornell faculty. He is a Fellow of the ACM, INFORMS, and of SIAM, was an NSF Presidential Young Investigator. He has been the advisor for 30 graduated Ph.D. students, and his former students are currently on the faculties of many leading universities and industrial research labs, including MIT, Waterloo, Brown, Maryland, Georgetown, and Google. Shmoys' research has focused on the design and analysis of efficient algorithms for discrete optimization problems, with applications including scheduling, inventory theory, computational biology, and most recently, comptuational sustainability. He has been working on data-driven models in a broad cross-section of areas, including COVID epidemiological modeling, congressional districting and IoT network design
Tim Roughgarden
The Computer in the Sky
Talk details
Turing-complete blockchain protocols approximate the idealized abstraction of a computer in the sky that is open access, runs in plain view, and, in effect, has no owner or operator. This technology can, among other things, enable stronger notions of ownership of digital possessions than we have ever had before. Building the computer in the sky is hard (and scientifically fascinating), and in this talk I'll highlight three threads in my recent research on this challenge: Possibility and impossibility results for permissionless consensus protocols (i.e., implementing an “ownerless” computer). Incentive-compatible transaction fee mechanism design (i.e., making an “open-access” computer sustainable and welfare-maximizing). A Black-Scholes-type formula for quantifying adverse selection in automated market makers (some of the most popular 'programs' running on the computer in the sky). The talk will emphasize the diversity of mathematical tools necessary for understanding blockchain protocols and their applications (e.g., distributed computing, game theory, mechanism design, and continuous-time stochastic processes) and the immediate practical impact that mathematical work on this topic has had (e.g., Ethereum's EIP-1559 and LVR for automated market makers).
Bio: Tim Roughgarden is a Professor in the Computer Science Department at Columbia University and the Founding Head of Research at a16z crypto. Prior to joining Columbia, he spent 15 years on the computer science faculty at Stanford, following a PhD at Cornell and a postdoc at UC Berkeley. His research interests include the many connections between computer science and economics, as well as the design, analysis, applications, and limitations of algorithms. For his research, he has been awarded the ACM Grace Murray Hopper Award, the Presidential Early Career Award for Scientists and Engineers (PECASE), the Kalai Prize in Computer Science and Game Theory, the Social Choice and Welfare Prize, the Mathematical Programming Society's Tucker Prize, the INFORMS Lanchester Prize, and the EATCS-SIGACT Gödel Prize. He was an invited speaker at the 2006 International Congress of Mathematicians and the Shapley Lecturer at the 2008 World Congress of the Game Theory Society. He is a Fellow of the Guggenheim Foundation, the ACM, the Game Theory Society, and the Society for the Advancement of Economic Theory. He has written or edited ten books and monographs, including Twenty Lectures on Algorithmic Game Theory (2016), Beyond the Worst-Case Analysis of Algorithms (2020), and the Algorithms Illuminated book series (2017-2020).
Kirthevasan Kandasamy
Mechanism Design for Collaborative Normal Mean Estimation
Talk details
Due to the popularity of machine learning, many organizations view data as an invaluable resource, likening it to the "new oil/gold". However, unlike other types of resources, data can be freely replicated and used by many. Hence, data produced by one organization, can, in principle, generate limitless value to many others. This will accelerate economic, social, and scientific breakthroughs and benefit society at large. However, strategic considerations such as free-riding, competition, and data monetization may prevent such open sharing of data between organizations. In this talk, I will focus on free-riding, and show that in naive mechanisms for data sharing, agents may attempt to benefit from the data that the others have collected without contributing any themselves. Free-riding can manifest in strategic behavior such as under-collecting data, or submitting fabricated datasets. I will present some of our recent work where we study these challenges in one of the most foundational statistical problems, normal mean estimation. Here, a set of strategic agents collect i.i.d samples from a normal distribution at a cost, and wish to estimate the mean of this distribution. To facilitate collaboration, we design mechanisms that incentivize agents to collect a sufficient amount of data and share it truthfully, so that they are all better off than working alone. Our approach prevents under-collection and data fabrication via two key techniques: first, when sharing the others’ data with an agent, the mechanism corrupts this dataset proportional to how much the data reported by the agent differs from the others; second, we design minimax optimal estimators for the corrupted dataset. Our mechanism, which is Nash incentive compatible and individually rational, achieves a social penalty (sum of all agents’ estimation errors and data collection costs) that is at most a factor 2 of the global minimum. When extending this work to high dimensional (non-Gaussian) distributions with bounded variance, where agents have heterogeneous data collection capabilities, our mechanisms retain these properties, but with slightly weaker results. This is joint work with Yiding Chen, Alex Clinton, and Jerry Zhu.
Bio: Kirthevasan Kandasamy is an assistant professor in the Department of Computer Sciences at the University of Wisconsin-Madison, working on topics in machine learning and game theory. He was a postdoctoral scholar at the University of California, Berkeley. He completed his PhD in Machine Learning at Carnegie Mellon University.
Sophie Yu
Constant Regret Primal-Dual Policy for Multi-Way Dynamic Matching
Talk details
We study a discrete-time dynamic multi-way matching model. There are finitely many agent types that arrive stochastically and wait to be matched. State-of-the-art dynamic matching policies in the literature require the knowledge of all system parameters to determine an optimal basis of the fluid relaxation, and focus on controlling the number of waiting agents using only matches within the optimal basis (Kerimov et al., 2021a,b; Gupta, 2021). In this paper, we propose a primal-dual policy that schedule matches for future arrivals based on an estimator for the dual solution. Our policy does not require the knowledge of the arrival rates and operates with greater flexibility as it does not restrict matches to only the match types within an optimal basis. We show that our policy is first to achieve constant regret at all times under unknown arrival rates, and when the arrival rates are known, it achieves the optimal scaling as the lower-bound described in Kerimov et al. (2021a,b). Furthermore, when the arrival rates are known, the primal-dual policy significantly outperforms alternative dynamic matching policies in several numerical simulations. Here is the paper link: https://papers.ssrn.com/sol3/papers.cfm?abstract_id=4357216
Bio: Sophie Yu a Postdoctoral Scholar under Prof. Itai Ashlagi and Prof. Amin Saberi, at Management Science and Engineering, Stanford University. She will join the Wharton School of Business as an assistant professor of Operations, Information and Decisions, starting in summer of 2024. She received her Ph.D. in Decision Sciences from the Fuqua School of Business at Duke University, under Prof. Jiaming Xu and Prof. Yehua Wei. Her research interests focus on data analysis, algorithm design, and performance evaluation in large-scale networks and stochastic systems.
Omar Besbes
A Journey Through Robust Auction Design
Talk details
Auctions are widely used in practice. While also extensively studied in the literature, most of the developments rely on significant assumptions regarding the knowledge of the players. In this work, we consider the setting in which the distribution of values is unknown. We study the design of optimal prior-independent auctions, exploring how the seller should incorporate partial information. We consider various forms of partial information, including distributional classes, correlation structures, support, and potentially market research data. We present general results that yield optimal or near-optimal robust auctions across a range of settings. These results also allow, e.g., to quantify the value of partial information or to uncover novel robust auction formats.
Bio: Omar Besbes is the Vikram S. Pandit Professor of Business at Columbia University, where he is a member of the Decision, Risk & Operations division in the Graduate School of Business. He is also a member of the Data Science Institute. His primary research interests are in the area of data-driven decision-making with a focus on applications in digital markets. His research has been recognized by multiple prizes including the 2019 Frederick W. Lanchester Prize, the 2017 M&SOM society Young Scholar Prize, the 2013 M&SOM best paper award and the 2012 INFORMS Revenue Management and Pricing Section prize. He serves on the editorial boards of Management Science and Operations Research. Omar is a graduate of Ecole Polytechnique (France) and received a M.Sc. in Aero/Astro from Stanford University and a Ph.D. from Columbia University. Before joining Columbia, he was on the faculty at the Wharton School, University of Pennsylvania.
Hongyao Ma
Iterative Network Pricing for Ridesharing Platforms
Talk details
Ridesharing platforms match riders and drivers, using dynamic pricing to balance supply and demand. The origin-based 'surge pricing', however, does not depend on the market condition of trip destinations, leading to inefficient trip flows in space and incentivizes drivers to strategize. In this work, we introduce the Iterative Network Pricing mechanism, addressing the main challenge in the practical implementation of optimal origin-destination (OD) based prices, that the model for rider-demand is hard to estimate. Assuming that the platform's surge algorithm clears the market for each origin in real-time, our mechanism updates the OD-based price adjustments week-over-week, using only information immediately observable during the same time window in the prior weeks. For stationary market conditions, we prove that our mechanism converges to an outcome that is approximately welfare-optimal. Using data made public by the City of Chicago, we illustrate (via simulation) the iterative updates under our mechanism for morning rush hours, demonstrating substantial welfare improvements despite significant fluctuations of market conditions from early 2019 through the end of 2020. Link to the paper: https://tinyurl.com/iterative-network-pricing
Bio: Hongyao Ma is an Assistant Professor in the Decision, Risk, and Operations division at Columbia Business School. Her research is situated at the interface of computer science, economics and operations, with a particular focus on market design. Hongyao completed her Ph.D. in Computer Science at Harvard University in 2019, and worked as a postdoctoral researcher at Uber and then Caltech during 2019-2020. She obtained her M.S. in 2014 at Harvard, and B.E. in 2012 at Xi'an Jiaotong University, both in Electrical Engineering. She received the ACM SIGecom Doctoral Dissertation Award in 2020, a Siebel Scholarship 2017-2018, and a Certificate of Distinction in Teaching at Harvard in 2014.
Will Ma
A Nonparametric Framework for Online Stochastic Matching with Correlated Arrivals
Talk details
The design of online algorithms for matching markets and revenue management settings is usually bound by the stochastic prior that the demand process is formed by a fixed-length sequence of queries with unknown types, each drawn independently. This assumption of serial independence implies that the demand of each type, i.e., the number of queries of a given type, has low variance and is approximately Poisson-distributed. This paper explores more general stochastic models for online edge-weighted matching that depart from the serial independence assumption. We propose two new models, Indep and Correl, that capture different forms of serial correlations by combining a nonparametric distribution for the demand with standard assumptions on the arrival patterns---adversarial or random order. The Indep model has arbitrary marginal distributions for the demands but assumes cross-sectional independence for the customer types, whereas the Correl model captures common shocks across customer types. We demonstrate that fluid relaxations, which rely solely on expected demand information, have arbitrarily bad performance guarantees. In contrast, we develop new algorithms that essentially achieve optimal constant-factor performance guarantees in each model. Our mathematical analysis includes tighter linear programming relaxations that leverage distribution knowledge, and a new lossless randomized rounding scheme in the case of Indep. In numerical simulations of the Indep model, we find that tighter relaxations are beneficial under high-variance demand and that our demand-aware rounding scheme can outperform stockout-aware rounding.
Bio: Will Ma is an Associate Professor of Decision, Risk, and Operations at Columbia Business School. His research centers around e-commerce, covering supply-side problems like inventory and fulfillment, as well as demand-side opportunities like personalized product assortments to facilitate matching supply to demand. He specializes in designing algorithms that make these decisions in real-time, from data, often prioritizing simplicity and robustness. Will also has miscellaneous experience as a professional poker player, video-game startup founder, and karaoke bar pianist.
Ben Golub
Robust Interventions in Markets
Talk details
A platform hosts many imperfectly competitive sellers that compete in prices. A policymaker has noisy information about the parameters (e.g., demand) in the market. We define a frequentist notion of robust interventions—ones achieving improvements in platform revenue or total surplus with high probability, uniformly over unknown market conditions. We characterize when it is and is not possible to robustly mitigate inefficiencies in differentiated oligopoly. A key tool is a set of spectral methods for studying price and welfare pass-throughs in a market with rich strategic spillovers, which permit the use of statistical results on matrix completion. Joint work with Andrea Galeotti, Sanjeev Goyal, Eduard Talamàs, and Omer Tamuz.
Bio: Ben Golub is a Professor of Economics and (by courtesy) Computer Science at Northwestern. His research focuses on the theory of social and economic networks, including the dynamics of learning and influence, targeting interventions for behavior change, and systemic risk and fragility in financial and production systems. He is interested in methods from probability theory, including random graphs and percolation, as well as the foundations and statistics of network centrality measures. He received the Calvó Armengol Prize International Prize in Economics and is a Fellow of the Econometric Society.
Brendan Lucier
Certification Design for a Competitive Market
Talk details
We consider a market for products with varying but hidden levels of quality. A third-party certifier can provide informative signals about the quality of products and can charge for this service. The certifier designs the set of offered certificates and their prices; sellers choose both the quality of the product they produce and a certification. The products are then sold in a competitive market. Under a single-crossing condition, we show that the levels of certification chosen by sellers are uniquely determined at equilibrium, and that the certifier's problem is equivalent to a screening problem with non-linear valuations. Certification objectives to maximize gains from trade, quantity traded, and certification revenue are in general incompatible. We prove that optimal menus for these and other objectives satisfy a monotonicity property, show how they can be interpreted as maximizing a modified virtual welfare, and provide a FPTAS for their computation. We discuss how to interpret our results and their policy implications in the motivating example of markets for carbon offsets and removal activities. This is joint work with Andreas Haupt and Nicole Immorlica.
Bio: Brendan Lucier is a Senior Principal Researcher at Microsoft Research in the economics and computation group. He is a graduate of the University of Waterloo and received his PhD in Computer Science from the University of Toronto. His research seeks to understand how the algorithms embedded in online platforms and other sociotechnical systems influence user behavior. He specializes in the impact of algorithmic choices and interfaces in market design, with an emphasis on simplicity and robustness. His research is motivated by applications such as digital advertising, matching markets, and markets for sustainability.
Paul Gölz
Generative Social Choice
Talk details
Traditionally, social choice theory has only been applicable to choices among a few predetermined alternatives but not to more complex decisions such as collectively selecting a textual statement. We introduce generative social choice, a framework that combines the mathematical rigor of social choice theory with the capability of large language models to generate text and extrapolate preferences. This framework divides the design of AI-augmented democratic processes into two components: first, proving that the process satisfies rigorous representation guarantees when given access to oracle queries; second, empirically validating that these queries can be approximately implemented using a large language model. We apply this framework to the problem of generating a slate of statements that is representative of opinions expressed as free-form text; specifically, we develop a democratic process with representation guarantees and use this process to represent the opinions of participants in a survey about chatbot personalization. We find that 93 out of 100 participants feel 'mostly' or 'perfectly' represented by the slate of five statements we extracted.
Bio: Paul Gölz is currently a postdoc at UC Berkeley and will start as an assistant professor at Cornell ORIE in Summer 2024. Before that, he was the Sloan Foundation supported postdoctoral fellow of the Algorithms, Fairness, and Equity program at the Simons Laufer Mathematical Sciences Institute (formerly: MSRI), a postdoctoral fellow at Harvard, and received his Ph.D. in computer science at Carnegie Mellon University. Paul studies democratic decision making and the fair allocation of resources, using tools from algorithms, optimization, and artificial intelligence. Algorithms developed in his work are now deployed to select citizens' assemblies around the world and to allocate refugees for a major US resettlement agency.
Nina Balcan
Online learning in Stackelberg Security Games
Talk details
In a Stackelberg Security Game, a defender commits to a randomized deployment of security resources, and an attacker best responds by attacking a target that maximizes their utility. While algorithms for computing an optimal strategy for the defender to commit to have been used in several real-world applications, deployed applications require knowledge about the utility function of the potential attacker. In this talk I will describe an online learning approach for addressing this problem. We consider algorithms that prescribe a randomized strategy for the defender at each step against an adversarially chosen sequence of attackers and obtain feedback on their choices. I will discuss online algorithms whose regret (when compared to the best fixed strategy in hindsight) is sublinear in the number of time steps. I will also consider an extension that handles auxiliary contextual information that is often readily available to each player (e.g. traffic patterns or weather conditions) and discuss what no regret guarantees are possible in this even more realistic scenario.
Bio: Maria Florina Balcan is the Cadence Design Systems Professor of Computer Science in the School of Computer Science at Carnegie Mellon University. Her main research interests are machine learning, artificial intelligence, theory of computing, and algorithmic game theory. She is a Simons Investigator, an ACM Fellow, a Sloan Fellow, a Microsoft Research New Faculty Fellow, and the recipient of the ACM Grace Murray Hopper Award, NSF CAREER award, and several best paper awards. She has co-chaired major conferences in the field: the Conference on Learning Theory (COLT) 2014, the International Conference on Machine Learning (ICML) 2016, and Neural Information Processing Systems (NeurIPS) 2020. She has also been the general chair for the International Conference on Machine Learning (ICML) 2021, a board member of the International Machine Learning Society, and a co-organizer for the Simons semester on Foundations of Machine Learning.
2022-2023
Benjamin Brooks
Robust Mechanisms for the Financing of Public Goods
Talk details
We propose a novel proportional cost-sharing mechanism for funding public goods with interdependent values: the agents simultaneously submit bids, which are nonnegative numbers; the expenditure on the public good is an increasing and concave function of the sum of the bids; and each agent is responsible for the fraction of the expenditure proportional to their bid. The proportional cost-sharing mechanism provides a non-trivial guarantee for social welfare, regardless of the structure of the agents’ information and the equilibrium that is played, as long as the social value for the public good is sufficiently large. Moreover, this guarantee is shown to be unimprovable in environments where the designer knows a lower bound on the social value. The guarantee converges to the entire efficient surplus when the social value grows large. When there are two agents, our model can be reinterpreted as one of bilateral trade, and the proportional cost-sharing is reinterpreted as proportional pricing.
Bio: Benjamin Brooks is an Associate Professor in the Department of Economics at the University of Chicago. He studies various aspects of economic theory, including games of incomplete information, auction theory and mechanism design, and repeated games.
Diyi Yang
More Civility and Positivity for Socially Responsible Language Understanding
Talk details
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).
Jamie Morgenstern
Shifts in Distributions and Preferences in Response to Learning
Talk details
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?
Shahar Dobzinski
On the Hardness of Dominant Strategy Mechanism Design
Talk details
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.
Nynke Niezink
Networks in 3D: Inference for Three-way Social Networks
Talk details
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.
Thodoris Lykouris
Decentralized multi-agent learning in queuing systems
Talk details
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.
Tina Eliassi-Rad
The Why, How, and When of Representations for Complex Systems, and their Implications for Machine Learning
Talk details
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.
Sigal Oren
Algorithmic Game Theory Meets Behavioral Economics
Talk details
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.
Dan Larremore
Quantifying hierarchy and dynamics in U.S. faculty hiring and retention
Talk details
Faculty hiring and retention determine the composition of the U.S. academic workforce and directly shape educational outcomes, career trajectories, the development and spread of ideas, and research priorities. But patterns in faculty hiring and retention are dynamic, reflecting societal and academic priorities, generational turnover, and long-term efforts to diversify the professoriate along gender, racial, and socioeconomic lines. In this talk, we'll analyze, at unprecedented scale and resolution, the academic employment and doctoral education of tenure-track faculty at all PhD-granting U.S. universities over the decade spanning 2011-2020. Focusing on the networks formed when departments hire each other's graduates as faculty, we'll explore the mechanisms shaping these networks as well as the processes of the academic ecosystem that are shaped by them.
Bio: Daniel Larremore is an assistant professor in the Department of Computer Science and the BioFrontiers Institute. His research develops statistical and inferential methods for analyzing large-scale network data, and uses those methods to solve applied problems in diverse domains, including public health and academic labor markets. In particular, his work focuses on generative models for networks, the ongoing evolution of the malaria parasite and the origins of social inequalities in academic hiring and careers. Prior to joining the CU Boulder faculty, he was an Omidyar Fellow at the Santa Fe Institute (2015-2017) and a post-doctoral fellow at the Harvard T.H. Chan School of Public Health (2012-2015). He obtained his PhD in applied mathematics from CU Boulder in 2012, and holds an undergraduate degree from Washington University in St. Louis.
Rad Niazadeh
When Matching Meets Batching: Optimal Multi-stage Algorithms and Applications
Talk details
In several applications of real-time matching of demand to supply in online marketplaces --- for example matching delivery requests to dispatching centers in Amazon or allocating video-ads to users in YouTube --- the platform allows for some latency (or there is an inherent allowance for latency) in order to batch the demand and improve the efficiency of the resulting matching. Motivated by these scenarios, I investigate the optimal trade-off between batching and inefficiency in the context of designing robust online allocations in this talk. In particular, I consider K-stage variants of the classic vertex weighted bipartite b-matching and AdWords problems in the adversarial setting, where online vertices arrive stage-wise and in K batches—in contrast to online arrival. Our main result for both problems is an optimal (1-(1-1/K)^K)-competitive competitive (fractional) matching algorithm, improving the classic (1 − 1/e) competitive ratio bound known for the online variants of these problems (Mehta et al., 2007; Aggarwal et al., 2011). Our main technique at high-level is developing algorithmic tools to vary the trade-off between “greedyness” and “hedging” of the matching algorithm across stages. We rely on a particular family of convex-programming based matchings that distribute the demand in a specifically balanced way among supply in different stages, while carefully modifying the balancedness of the resulting matching across stages. More precisely, we identify a sequence of polynomials with decreasing degrees to be used as strictly concave regularizers of the maximum weight matching linear program to form these convex programs. At each stage, our fractional multi-stage algorithm returns the corresponding regularized optimal solution as the matching of this stage (by solving the convex program). By providing structural decomposition of the underlying graph using the optimal solutions of these convex programs and recursively connecting the regularizers together, we develop a new multi-stage primal-dual framework to analyze the competitive ratio of this algorithm. We extend our results to integral allocations in the vertex weighted b-matching problem with large budgets, and in the AdWords problem with small bid over budget ratios. I will also briefly mention a recent extension of these results to the multi-stage configuration allocation problem and its applications to video-ads. The talk is based on a series of work with Yiding Feng and Amin Saberi: https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3689448 https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3613755
Bio: Rad Niazadeh is an Assistant Professor of Operations Management at The University of Chicago Booth School of Business. He is also part of the faculty at Toyota Technological Institute of Chicago (TTIC) by a courtesy appointment. Prior to joining Chicago Booth, he was a visiting researcher at Google Research NYC and a postdoctoral fellow at Stanford University, Computer Science Department. He finished his PhD in Computer Science (minored in Applied Mathematics) at Cornell University. Rad primarily studies the interplay between algorithms, incentives, and learning in real-time operations of online marketplaces and e-commerce platforms. His research aims to build theoretical methodologies and generic frameworks to design faster and economically efficient market algorithms, and also to help with addressing humanitarian needs (such as equity, fairness, and non-discrimination) in operations of governmental agencies and non-profit organizations. https://faculty.chicagobooth.edu/rad-niazadeh
Nika Haghtalab
Multi-objective learning: A unifying framework for robustness, fairness, and collaboration
Talk details
Social and real-world considerations such as robustness, fairness, social welfare, and multi-agent tradeoffs have given rise to multi-objective learning paradigms. In recent years, these paradigms have been studied by several disconnected communities and under different names, including collaborative learning, distributional robustness, group fairness, and fair federated learning. In this talk, I will highlight the importance of multi-objective learning paradigms in general, introduce technical tools for addressing them from a simple unifying perspective, and discuss how these problems relate to classical and modern consideration in data-driven processes.
Bio: Nika Haghtalab is an Assistant Professor in the Department of Electrical Engineering and Computer Sciences at UC Berkeley. She works broadly on the theoretical aspects of machine learning and algorithmic economics. Prof. Haghtalab's work builds theoretical foundations for ensuring both the performance of learning algorithms in presence of everyday economic forces and the integrity of social and economic forces that are born out of the use of machine learning systems. Previously, Prof. Haghtalab was an Assistant Professor in the CS department of Cornell University, in 2019-2020. She received her Ph.D. from the Computer Science Department of Carnegie Mellon University. She is a co-founder of Learning Theory Alliance (LeT-All). Among her honors are the CMU School of Computer Science Dissertation Award, SIGecom Dissertation Honorable Mention, and NeurIPS outstanding paper award.
Christopher Harshaw
A New Design-Based Framework for Randomized Experiments and the Riesz Estimator
Talk details
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.
Dhruv Madeka
Deep Reinforcement Learning for Real-World Inventory Management
Talk details
We present a Deep Reinforcement Learning approach to solving a periodic review inventory control system with stochastic vendor lead times, lost sales, correlated demand, and price matching. While this dynamic program has historically been considered intractable, we show that several policy learning approaches are competitive with or outperform classical baseline approaches. In order to train these algorithms, we develop novel techniques to convert historical data into a simulator and present a collection of results that motivate this approach. We also present a model-based reinforcement learning procedure (Direct Backprop) to solve the dynamic periodic review inventory control problem by constructing a differentiable simulator. Under a variety of metrics Direct Backprop outperforms model-free RL and newsvendor baselines, in both simulations and real-world deployments.
Bio: Dhruv is a Principal Machine Learning Scientist at Amazon. His current research focuses on applying Deep Reinforcement Learning to supply chain problems. Dhruv has also worked on developing generative and supervised deep learning models for probabilistic time series forecasting. In the past - Dhruv worked in the Quantitative Research team at Bloomberg LP, contributing to the open source Python and Jupyter community.
Kamesh Munagala
Limits of an Information Intermediary in Auction Design
Talk details
We study the classical Bayesian auction setting with a twist: Between the revenue maximizing seller and the buyers lies an intermediary that is better informed about the buyer values. The intermediary now segments the market by selectively releasing information to the seller, who still controls the auction. This process is called signaling and allows the seller to price discriminate. Though one would expect signaling to always help the seller, in the setting with one buyer, Bergemann, Brooks, and Morris [AER 2015] showed a remarkable result: Signaling can maximally help the buyer without really helping the seller. Specifically, there exists a signaling scheme where the seller's revenue does not increase but the item always sells, thereby maximizing the consumer (buyer) surplus. In this talk, we will explore whether such a result is possible in more general settings: First, when the type space of the buyer is “inter-dimensional” with a private budget or deadline in addition to a private value, and second, when there are multiple buyers in the auction. On the positive side, we show exact and approximation results via new signaling schemes, while on the negative side, we show impossibility results that capture the limits to which information intermediaries can help the buyers. Joint work with Reza Alijani, Sid Banerjee, Shao-Heng Ko, and Kangning Wang, and combines two papers that appeared in ACM EC 2022.
Bio: Kamesh Munagala is Professor of Computer Science at Duke University. He is broadly interested in algorithm design, particularly approximation and online algorithms, algorithmic fairness, and algorithmic game theory. He obtained his Ph.D. (2003) and M.S. (2002) from Stanford University, and B.Tech. (1998) from IIT Bombay. He is an ACM Distinguished Scientist (2019); a recipient of the NSF CAREER Award (2008) and the Alfred P. Sloan Fellowship (2009); and is a co-author on the best papers at the WINE 2018 and WWW 2009 conferences. He was a Visiting Research Professor at Twitter in 2012, served as the Director of Graduate Studies for Duke CS from 2012 to 2015, and currently serves as its Associate Chair.
Chara Podimata
The disparate effects of recommending to strategic users
Talk details
Recommendation systems are pervasive in the digital economy. An important assumption in many deployed systems is that user consumption reflects user preferences in a static sense: users consume the content they like with no other considerations in mind. However, as we document in a large-scale online survey, user behavior departs from this model in a crucial way: users choose content strategically, with the goal of influencing their future recommendations. We model the user behavior as a two-stage noisy signaling Stackelberg game between the recommendation system and users: in a finite-length first stage, the recommendation system implements a preliminary recommendation policy, to which users respond by strategically consuming content to change the breakdown of content types recommended to them in the future. Based on the user’s preferences as learned in this first stage, in the second stage, the platform commits to a recommendation policy by which it will recommend content to the users. We show that users’ strategic behavior can affect the user experience: at equilibrium in this game, differences in users’ preferences become accentuated as they strategically consume content further outside the mainstream. This effect is particularly strong among users from (statistical) minorities, who must specifically avoid signaling interest in mainstream content in order to ensure the algorithm will show them content related to their minoritized identities. This puts minority users at an unfair disadvantage, where they cannot access mainstream content without the algorithm suppressing the content types that only they (as the minority) enjoy. We next propose three interventions that improve the recommendation quality (both on average and for minority groups) that account for strategic consumption:(1) Adopting a recommendation system policy that uses preferences from a prior, (2) Communicating to users that universally liked (“mainstream”) content will not be used as the basis of recommendation, and (3) Serving content that is personalized-enough yet expected to be liked in the beginning. Finally, we describe a methodology to inform applied theory modeling in incentive-aware learning settings with survey results. Based on joint work with Andreas Haupt (MIT) and Dylan Hadfield-Menell (MIT).
Bio: Chara Podimata is currently a FODSI postdoctoral fellow at UC Berkeley and is joining MIT Sloan as an Assistant Professor of OR/Stat in Fall 2023. She received her PhD from Harvard, advised by Yiling Chen. She is interested in social aspects of computing and more specifically, the effects of humans adapting to machine learning algorithms used for consequential decision-making. During her PhD, she interned at MSR and Google, and her research was supported by a Microsoft Dissertation Grant and a Siebel Scholarship. Outside of research, she spends her time adventuring with her pup, Terra.
Dave Holtz
Reducing Interference Bias in Online Marketplace Experiments using Cluster Randomization: Evidence from a Pricing Meta-Experiment on Airbnb
Talk details
Online marketplace designers frequently run randomized experiments to measure the impact of proposed product changes. However, given that marketplaces are inherently connected, total average treatment effect (TATE) estimates obtained through individual-level randomized experiments may be biased due to violations of the stable unit treatment value assumption, a phenomenon we refer to as 'interference bias.' Cluster randomization, i.e., the practice of randomizing treatment assignment at the level of 'clusters' of similar individuals, is an established experiment design technique for countering interference bias in social networks, but it is unclear ex ante if it will be effective in marketplace settings. In this paper, we use a meta-experiment or 'experiment over experiments' conducted on Airbnb to both provide empirical evidence of interference bias in online market settings and assess the viability of cluster randomization as a tool for reducing interference bias in marketplace TATE estimates. Results from our meta-experiment indicate that at least 19.76% of the TATE estimate produced by an individual-randomized evaluation of the platform fee increase we study is attributable to interference bias and eliminated through the use of cluster randomization. We also find suggestive, non-statistically significant evidence that interference bias in seller-side experiments is more severe in demand-constrained markets, and that the efficacy of cluster randomization at reducing interference bias increases with cluster quality
Bio: David Holtz is an assistant professor in the Management of Organizations (MORS) and Entrepreneurship and Innovation groups at the Haas School of Business. He earned his PhD at the MIT Sloan School of Management, in the Information Technology (IT) group. He also holds an MA in Physics and Astronomy from Johns Hopkins University, and a BA in Physics from Princeton University. Holtz studies the design of online marketplaces and platforms using large-scale online field experiments and novel digital trace data. His research agenda focuses on online trust and reputation system design, the business and societal impacts of personalized recommendations, and the design and analysis of field experiments in online marketplaces. His work has appeared in a number of journals and conferences, including The Proceedings of the National Academy of Science and the ACM Conference on Economics and Computation, and has been covered by popular news outlets, such as MSNBC, The Washington Post, and the Boston Globe. Before returning to academia, Holtz spent time in the Bay Area working as a data scientist and product manager at a number of technology firms, including Airbnb (where he was one of the founding members of the company’s algorithmic pricing team) and TrialPay (acquired by Visa). In carrying out his research agenda, he continues to work closely with many leading firms in the tech sector, including Airbnb, Facebook, Spotify, Microsoft, and Etsy.
Yuri Faenza
Stable matchings in choice function models: algorithms, polyhedra, and an application to school choice
Talk details
In the classical marriage model by Gale and Shapley, agents from one side of the market have a strict ordering of the agents from the other side of the market and vice-versa. The goal is to find a matching that satisfies a fairness condition known as stability. However, strict orders cannot model many preference patterns that arise in problems such as diversification of school cohorts, formation of teams, etc. Hence, much attention has recently been reserved to matching problems where preferences of agents have a more complex behavior, which can be described via certain choice functions. In the first part of this talk, I will investigate algorithmic properties of these models, showing that the classical combinatorial approach based on the distributive lattice of stable matchings and the description of the convex hull of stable matchings as an LP are intimately related. This approach may turn out to be of interest for other problems as well. In the second part of the talk, I will show how certain choice functions can be used to model school admission criteria that take into account well-defined diversity and fairness concerns. I will show the practical relevance of those choice functions by applying them to data from specialized high schools admission in New York City. Based on joint work with Swati Gupta (GA Tech & MIT) and Xuan Zhang (Meta Research).
Bio: Yuri Faenza obtained his Ph.D. from the Sapienza University of Rome and is currently an associate professor in the IEOR department at Columbia University. He works in discrete optimization, operations research, matching theory, market design, and their applications. His research has been funded by the NSF (including an NSF Career award), the ONR, the Swiss NSF, and by a Meta Research Award. He is the chair of Mixed-Integer Programming Society of the MOS.
Kuang Xu
Non-Stationary Bandit Learning via Predictive Sampling
Talk details
Thompson sampling has proven effective across a wide range of stationary bandit environments. However, as we demonstrate in this paper, it can perform poorly when applied to non-stationary environments. We show that such failures are attributed to the fact that, when exploring, the algorithm does not differentiate actions based on how quickly the information acquired loses its usefulness due to non-stationarity. Building upon this insight, we propose predictive sampling, an algorithm that deprioritizes acquiring information that quickly loses usefulness. Theoretical guarantee on the performance of predictive sampling is established through a Bayesian regret bound. We provide versions of predictive sampling for which computations tractably scale to complex bandit environments of practical interest. Through numerical simulations, we demonstrate that predictive sampling outperforms Thompson sampling in all non-stationary environments examined. Joint work with Yueyang Liu and Benjamin Van Roy (MS&E, Stanford University).
Bio: Kuang Xu is an Associate Professor at the Stanford Graduate School of Business. His research focuses on principles for decision-making in a stochastic system, with applications to operations, experimentation and logistics. He has received a First Place in the INFORMS George E. Nicholson Student Paper Competition, a Best Paper Award as well as Outstanding Student Paper Award at ACM SIGMETRICS, and an ACM SIGMETRICS Rising Star Research Award. He currently serves as an Associate Editor for Operations Research and Management Science. Outside of academia, he has consulted as the chief data science advisor for Shipt and as a senior advisor for Uber.
2021-2022
Nihar Shah
Two F-words in Peer Review (Fraud and Feedback)
Talk details
In this talk, we present two major challenges in peer review, propose solutions with guarantees, and discuss important open problems. (1) Fraud: There have been several recent discoveries of fraud in peer review: A group of participants form a coalition, get assigned each other's papers by manipulating the system, and then accept each others' papers. We present an algorithm which mitigates such fraud by randomizing reviewer assignments, and does not rely on assumptions about the malicious behavior. The algorithm yields an optimal-quality assignment subject to the randomization constraints, and we will discuss experiments characterizing this tradeoff. (2) Feedback: Real-world systems rely on feedback about their performance for their continual improvement. A useful means of obtaining feedback about the peer-review process is to ask authors' opinions. However, author opinions are significantly biased by whether their paper was accepted. We formulate this problem and present algorithms to debias such feedback. Our work relies on the key observation that the direction of this bias is known: the program chairs know which authors' papers were accepted. An overview of research on peer review is available here http://bit.ly/PeerReviewOverview
Bio: Nihar B. Shah is an Assistant Professor in the Machine Learning and Computer Science departments at Carnegie Mellon University (CMU). His research interests span statistics, machine learning, information theory, and game theory, recently focusing on improving the peer-review process by designing computational methods, mathematical guarantees, experimental evaluations and deployments. He is a recipient of a Google Research Scholar Award 2021, an NSF CAREER Award 2020-25, the 2017 David J. Sakrison memorial prize from EECS Berkeley for a "truly outstanding and innovative PhD thesis", the Microsoft Research PhD Fellowship 2014-16, the Berkeley Fellowship 2011-13, the IEEE Data Storage Best Paper and Best Student Paper Awards for the years 2011/2012, and the SVC Aiya Medal 2010, and has supervised the Best Student Paper at AAMAS 2019.
Katrina Ligett
Gaming Helps! Learning from Strategic Interactions in Natural Dynamics
Talk details
Those who are being classified are sometimes aware of the classifiers that are being used on them, and may have incentive to change their behavior to try to improve the label they receive. The attitude towards such strategic behavior, both in practice and in theoretical treatment, has generally been quite negative, and this is one of the reasons that the internal workings of high-stakes classifiers are often shrouded in secrecy. However, intuitively, agents who strategically change their behavior in response to incentives set by classifiers may actually be doing everyone a favor: they are helping teach the classifier whether the variables that the classifier depends on are truly meaningful for the task at hand---that is, features that, when changed, affect the true label (as opposed to non-meaningful features that have no effect). Over time, this could push the system to develop better classifiers, and could push individuals to invest more in meaningful variables. We study this issue in an online regression setting. Joint work with Yahav Bechavod, Zhiwei Steven Wu, and Juba Ziani. Work appeared at AISTATS'21.
Bio: Katrina Ligett is an Associate Professor of Computer Science at the Hebrew University of Jerusalem, where she is also the Head of the Program on Internet & Society. Her research interests include data privacy, algorithmic fairness, machine learning theory, and algorithmic game theory. She received her PhD in computer science in 2009, from Carnegie Mellon University, and did a postdoc at Cornell University. Before joining the Hebrew University, Katrina was on the faculty in computer science and economics at Caltech.
Douglas Guilbeault
How communication networks promote cross-cultural similarities: The case of category formation
Talk details
Individuals vary widely in how they categorize novel phenomena. This individual variation has led canonical theories in cognitive and social science to suggest that communication in large social networks leads populations toward divergent category systems. Yet, anthropological data indicates that large, independent societies consistently arrive at similar categories across a range of topics. How is it possible for diverse populations, consisting of individuals with significant variation in how they view the world, to independently construct similar categories? Through a series of online experiments, I show how large communication networks within cultures can promote the formation of similar categories across cultures. I use the online “Grouping Game” to observe how people construct categories in both small and large populations when presented with the same novel images. I replicate this design for English-speaking subjects in the U.S. and Mandarin-speaking subjects in China. In both cultures, solitary individuals and small social groups produced highly divergent category systems. Yet, large social groups separately and consistently arrived at highly similar categories both within and across cultures. These findings are accurately predicted by a simple mathematical model of critical mass dynamics. Altogether, I show how large communication networks can filter lexical diversity among individuals to produce replicable society-level patterns, yielding unexpected implications for cultural evolution.
Bio: Douglas Guilbeault is an assistant professor in the management of organizations at the Berkeley Haas School of Business. His research focuses on how communication networks underlie the production and diffusion of cultural content, such as linguistic categories and social norms. His studies have been published in a number of top journals, including Nature Communications, The Proceedings of the National Academy of the Sciences, and Management Science. As well, he has received top research awards from the International Conference on Computational Social Science, the Cognitive Science Society, and Facebook. Douglas teaches People Analytics at Haas, and he has served as a People Analytics consultant for a variety of organizations.
Vijay Vazirani (Tues 3 pm, joint with CS Theory)
Online Bipartite Matching and Adwords
Talk details
Over the last three decades, the online bipartite matching (OBM) problem has emerged as a central problem in the area of Online Algorithms. Perhaps even more important is its role in the area of Matching-Based Market Design. The resurgence of this area, with the revolutions of the Internet and mobile computing, has opened up novel, path- breaking applications, and OBM has emerged as its paradigmatic algorithmic problem. In a 1990 joint paper with Richard Karp and Umesh Vazirani, we gave an optimal algorithm, called RANKING, for OBM, achieving a competitive ratio of (1 – 1/e); however, its analysis was difficult to comprehend. Over the years, several researchers simplified the analysis. We will start by presenting a “textbook quality” proof of RANKING. Its simplicity raises the possibility of extending RANKING all the way to a generalization of OBM called the adwords problem. This problem is both notoriously difficult and very significant, the latter because of its role in the AdWords marketplace of Google. We will show how far this endeavor has gone and what remains. We will also provide a broad overview of the area of Matching-Based Market Design and pinpoint the role of OBM. Based on: https://arxiv.org/pdf/2107.10777.pdf
Bio: Vijay Vazirani got his undergraduate degree from MIT in 1979 and his PhD from the University of California, Berkeley in 1983. He is currently a Distinguished Professor at the University of California, Irvine. Vazirani has made fundamental contributions to several areas of the theory of algorithms, including algorithmic matching theory, approximation algorithms and algorithmic game theory, as well as to complexity theory, in which he established, with Les Valiant, the hardness of unique solution instances of NP-complete problems. Over the last four years, he has been working on algorithms for matching markets. He is one of the founders of algorithmic game theory. In 2001 he published Approximation Algorithms, which is widely regarded as the definitive book on the topic. In 2007, he published the co-edited book Algorithmic Game Theory. Another co-edited book, Online and Matching-Based Market Design, will be published by Cambridge University Press in early 2022; see its flyer: https://www.ics.uci.edu/~vazirani/flyer.pdf
Omer Tamuz
Private Private Information
Talk details
In a private private information structure, agents’ signals contain no information about the signals of their peers. We study how informative such structures can be, and characterize those that are on the Pareto frontier, in the sense that it is impossible to give more information to any agent without violating privacy. In our main application, we show how to optimally disclose information about an unknown state under the constraint of not revealing anything about a correlated variable that contains sensitive information.
Bio: Omer Tamuz is a professor of economics and mathematics at Caltech.
Ron Berman
Naive analytics equilibrium
Talk details
We study interactions with uncertainty about demand sensitivity. In our solution concept (1) firms choose seemingly-optimal strategies given the level of sophistication of their data analytics, and (2) the levels of sophistication form best responses to one another. Under the ensuing equilibrium firms underestimate price elasticities and overestimate advertising effectiveness, as observed empirically. The misestimates cause firms to set prices too high and to over-advertise. In games with strategic complements (substitutes), profits Pareto dominate (are dominated by) those of the Nash equilibrium. Applying the model to team production games explains the prevalence of overconfidence among entrepreneurs and salespeople.
Bio: Ron Berman is an assistant professor of marketing at Wharton. He focuses his research on digital marketing and marketing analytics. Recently Ron has been investigating how firms assess and optimize marketing effectiveness through experiments, how curation algorithms may create filter-bubbles on social media, and how descriptive analytics affects online firm performance. His research has been published in top marketing journals such as Marketing Science and the Journal of Marketing Research and he is a member of the editorial boards of the Journal of Marketing Research and Quantitative Marketing and Economics. Ron disseminates his research by teaching Digital Marketing courses in undergrad, MBA and Executive Education programs, and is often invited by market leading firms including Google, Facebook, and Wayfair to share and discuss his research. Ron’s experience includes early-stage venture capital investing at Viola Ventures (formerly Carmel Ventures) and developing software for the Israeli Defense Forces (IDF). Ron is an active advisor and investor, involved with startups such as Desti (travel planning, acquired by Nokia), Zimperium (cyber security), Abakus (advertising attribution, acquired by SAP), Peerspace (P2P venue marketplace), Netlify (serverless website deployment), Stackbit (content management), cauzal.ai (conversion optimization) and Honeycomb Insurance (commercial real-estate insurance). Ron holds a PhD and MSc in Business Administration (Marketing) from the University of California, Berkeley, an MBA and MSc in Computer Science from Tel-Aviv University, and a BSc in Computer Science, Physics and Mathematics from the Hebrew University in Jerusalem.
Christina Yu
Simple yet Efficient Graph Agnostic Estimators for Network Causal Inference - from Linear to Low Degree Polynomial Models
Talk details
Randomized experiments are widely used to estimate causal effects of proposed "treatments" in domains spanning across physical sciences, social sciences, medicine, and technology industries. However, classical approaches to experimental design rely on critical independence assumptions that are violated when the outcome of an individual a may be affected by the treatment of another individual b, referred to as network interference. Under such network interference, naively using popular estimators and randomized experimental designs can result in significant bias and loss of efficiency. We consider heterogeneous linear and polynomial potential outcomes models for network interference, under which we propose simple estimators for the total treatment effect that output unbiased estimates with low variance under simple randomized designs. Our solution and statistical guarantees do not rely on restrictive network properties, allowing for highly connected graph structures. When the network is completely unknown, we provide a simple unbiased and efficient estimator under a staggered rollout randomized design, showing that the flexibility from experimentation implemented over time can remove any requirement of network knowledge. We believe our results are poised to impact current randomized experimentation strategies due to its simplicity and ease of implementation, wide applicability across different network structures, and its statistical guarantees under a flexible hierarchy of network interference models.
Bio: Christina Lee Yu is an Assistant Professor at Cornell University in the School of Operations Research and Information Engineering. Prior to Cornell, she was a postdoc at Microsoft Research New England. She received her PhD in 2017 and MS in 2013 in Electrical Engineering and Computer Science from Massachusetts Institute of Technology in the Laboratory for Information and Decision Systems. She received her BS in Computer Science from California Institute of Technology in 2011. She received honorable mention for the 2018 INFORMS Dantzig Dissertation Award. She is a recipient of the 2021 Intel Rising Stars Award and a JPMorgan Faculty Research Award. Her research interests include algorithm design and analysis, high dimensional statistics, inference over networks, sequential decision making under uncertainty, online learning, and network causal inference.
Constantinos Daskalakis
What does it take to be a good fisherman?
Talk details
A reasonable approach to figure this out is to collect training data comprising features of fishermen and their daily catch, and then learn a model mapping fishermen features to the size of their catch. Reasonable as this approach may sound, it will most likely result in a biased model. The reason for this bias is that the training data will miss all those individuals who were not good enough at fishing and decided to become hunters (or do something else) instead. Such self-selection bias is pervasive. From understanding what it takes to be a good college student or company employee to learning from expert demonstrations and understanding strategic behavior in markets, data available for learning statistical models are the results of strategic decisions that have already operated on and filtered out some of the relevant data. I will discuss recent progress on some classical econometric challenges revolving around estimating linear models under self-selection bias, and identification of non-parametric auction models, and present several open directions for future investigation. This talk is based on joint works with Yeshwanth Cherapanamjeri, Andrew Ilyas, Manolis Zampetakis.
Bio: Constantinos (aka "Costis" with an accent on "i") Daskalakis is a Professor of Electrical Engineering and Computer Science at MIT. He holds a Diploma in Electrical and Computer Engineering from the National Technical University of Athens, and a PhD in Electrical Engineering and Computer Science from UC Berkeley. He works on Computation Theory and its interface with Game Theory, Economics, Probability Theory, Machine Learning and Statistics. He has resolved long-standing open problems about the computational complexity of Nash equilibrium, and the mathematical structure and computational complexity of multi-item auctions. His current work focuses on high-dimensional statistics and learning from biased, dependent, or strategic data. He has been honored with the ACM Doctoral Dissertation Award, the Kalai Prize from the Game Theory Society, the Sloan Fellowship in Computer Science, the SIAM Outstanding Paper Prize, the Microsoft Research Faculty Fellowship, the Simons Investigator Award, the Rolf Nevanlinna Prize from the International Mathematical Union, the ACM Grace Murray Hopper Award, and the Bodossaki Foundation Distinguished Young Scientists Award.
Ravi Jagadeesan
Matching and Prices
Talk details
Indivisibilities and budget constraints are pervasive features of many matching markets. But when taken together, these features typically cause failures of gross substitutability—a standard condition on preferences imposed in most matching models. To accommodate budget constraints and other income effects, we analyze matching markets under a weaker condition: net substitutability. Although competitive equilibria do not generally exist in our setting, we show that stable outcomes always exist and are efficient. However, standard auctions and matching procedures, such as the Deferred Acceptance algorithm and the Cumulative Offer process, do not generally yield stable outcomes. We illustrate how the flexibility of prices is critical for our results. We also discuss how budget constraints and other income effects affect classic properties of stable outcomes. Joint work with Alex Teytelboym
Bio: Ravi Jagadeesan is a Postdoctoral Fellow at Stanford. Starting in July, he will be an Assistant Professor in the Department of Economics at Stanford. He completed his PhD in Business Economics at Harvard in Spring 2020. Before that, he graduated from Harvard with an A.B. in Mathematics and an A.M. in Statistics in Spring 2018.
Federico Echenique
Empirical Welfare Economics
Talk details
We provide an empirical analogue to the equality of marginal rates of substitution condition for Pareto optimality, and address related questions. Welfare economics relies on agents’ utility functions: we revisit classical questions in welfare economics, assuming access to agents’ past choices instead of their utility functions. Our main result considers whether there are convex preferences for which some candidate allocation is Pareto optimal. We show that this candidate allocation is possibly efficient if and only if it is efficient for the incomplete relation derived from the revealed preference relations and convexity. Similar ideas are used to address when the Kaldor criterion may be used to make welfare comparisons, what prices can be Walrasian equilibrium prices, and the possibility of a representative consumer when the income distribution is endogenous. Joint work with Chris Chambers
Bio: Federico Echenique is the Allen and Lenabelle Davis Professor of Economics at Caltech. Federico Echenique's research focuses on understanding economic models of agents and markets. He is interested in determining the testable implications of models and the relationship between different theoretical models and the data possibly used to testing them. He is also studying fairness and efficiency in discrete allocation problems, such as two-sided matching markets and one-sided object allocation. Echenique is active in research at the intersection of economics and computer science. Echenique is Licenciado en Economía from the Universidad de la República in Uruguay and holds a PhD in economics from UC Berkeley. Prior to joining the Caltech faculty, he was an assistant professor at the Universidad de la República from 2000 to 2002 and an assistant professor at the Universidad Torcuato Di Tella in Buenos Aires from 2001 to 2002. He served on the editorial boards for the American Economic Review, Econometrica, The Economic Journal, Economic Theory, and the Journal of Economic Theory, and he is currently a co-editor of Theoretical Economics. Echenique is also a fellow of the Econometric Society.
2020-2021
Betsy Ogburn
Social network dependence, the replication crisis, and (in)valid inference
Talk details
In the first part of this talk, we show that social network dependence can result in /spurious associations due to network dependence/, potentially contributing to replication crises across the health and social sciences. Researchers in these fields frequently sample subjects from one or a small number of communities, schools, hospitals, etc., and while many of the limitations of such convenience samples are well-known, the issue of statistical dependence due to social network ties has not previously been addressed. A paradigmatic example of this is the Framingham Heart Study (FHS). Using a statistic that we adapted to measure network dependence, we test for network dependence and for possible spurious associations in several of the thousands of influential papers published using FHS data. Results suggest that some of the many decades of research on coronary heart disease, other health outcomes, and peer influence using FHS data may suffer from spurious estimates of association and anticonservative uncertainty quantification due to unacknowledged network structure. But data with network dependence abounds, and in many settings researchers are explicitly interested in learning about social network dynamics. Therefore, there is high demand for methods for causal and statistical inference with social network data. The second part of the talk describes recent work on causal inference for observational data from a single social network, focusing on (1) new types of causal estimands that are of interest in social network settings, and (2) conditions under which central limit theorems hold and inference based on approximate normality is licensed.
Bio: Dr. Elizabeth (Betsy) Ogburn is currently an Associate Professor in the Department of Biostatistics at Johns Hopkins University. She is also the founder of the COVID-19 Collaboration Platform. She received her Ph.D. in Biostatistics from Harvard University, and her research interests include causal inference and epidemiological methods.
Carrie Wu (SOAL Seminar)
Developing Data Efficient Algorithms for AI
Talk details
Our increasingly ambitious goals in artificial intelligence motivate several key algorithmic challenges, such as: how do we design algorithms that make the best use of the data that is available, and how do we design algorithms that are empirically and theoretically effective on the kinds of data that we often see in practice, for example, data with temporal dependencies and data that follow distributions that are hard to describe. In this talk, I will give examples of algorithmic solutions that addresses some of these challenges. I will first present a theoretical analysis of rates of convergence for SGD with experience replay, which is a technique used in Reinforcement Learning to break temporal differences in data. I will then present an algorithm that solves Markov Decision Processes with nearly optimal sample and runtime guarantees. Lastly, I will present an algorithmic solution for estimating local density for an arbitrary dataset.
Ruta Mehta
Nash Social Welfare Approximation for Strategic Agents
Talk details
A central goal in the long literature on fair division is the design of mechanisms that implement fair outcomes, despite the participants' strategic behavior. We study this question by measuring the fairness of an allocation using the geometric mean of the agents' values, known as the Nash social welfare (NSW). This objective is maximized by widely known concepts such as the Nash bargaining solution, proportional fairness, and the competitive equilibrium with equal incomes; we focus on (approximately) implementing this objective and analyze the Trading Post mechanism. We consider allocating goods that are substitutes or complements and show that this mechanism achieves an approximation of 2 for concave utility functions, and becomes essentially optimal for complements, where it can reach (1+e) for any e > 0. Moreover, we show that the Nash equilibria of this mechanism are pure and provide individual fairness in the sense of proportionality. (Joint work with Simina Branzei and Vasilis Gkatzelis. To appear in Operations Research.)
Bio: Ruta Mehta is an assistant professor in CS at UIUC, working on algorithmic, complexity, strategic, fairness, and learning aspects of various game-theoretic and economic problems. Prior to this, she was a postdoctoral fellow at the Simons Institute, UC Berkeley (Aug'15 - Dec'15), and at Georgia Tech (Sept'12 - July'15). She did her Ph.D. from IIT-Bombay. Her Ph.D. thesis, titled 'Nash Equilibrium Computation in Various Games' won the ACM India Doctoral Dissertation Award, 2012. Other awards she received include Best Postdoctoral Fellow Award, 2014 at Georgia Tech, and the NSF CAREER Award, 2018.
Karl Rohe
Vintage Factor Analysis with Varimax Performs Statistical Inference
Talk details
Vintage Factor Analysis is nearly a century old and remains popular today with practitioners. A key step, the factor rotation, is historically controversial because it appears to be unidentifiable. This controversy goes back as far as Charles Spearman. The unidentifiability is still reported in all modern multivariate textbooks. This talk will overturn this controversy and provide a positive theory for PCA with a varimax rotation. Just as sparsity helps to find a solution in p>n regression, we show that sparsity resolves the rotational invariance of factor analysis. PCA + varimax is fast to compute and provides a unified spectral estimation strategy for Stochastic Blockmodels, topic models (LDA), and nonnegative matrix factorization. Moreover, the estimator is consistent for an even broader class of models and the old factor analysis diagnostics (which have been used for nearly a century) assess the identifiability. Paper: https://arxiv.org/abs/2004.05387
Bio: Karl Rohe is an Associate Professor of Statistics at the University of Wisconsin-Madison, with courtesy appointments in Journalism, Educational Psychology, and Electrical & Computer Engineering. He is an AE at JRSS-B and JASA. His PhD is from Berkeley in 2011, working with Bin Yu.
Christopher Musco (OR Seminar)
Optimal Stochastic Trace Estimation
Talk details
I will discuss algorithms for an important computational primitive in linear algebra: approximately computing the trace of an implicit matrix A that can only be accessed through matrix-vector multiplications. Trace approximation finds applications across machine learning and scientific computing, where it is used to compute matrix norms, spectral densities, log-determinants, triangle counts in graphs, and much more. In 1990, Hutchinson introduced an elegant randomized algorithm for the trace approximation problem that has become ubiquitous in practice. I will introduce a simple modified version of this algorithm that provides the same theoretical guarantees, but requires quadratically fewer matrix-vector multiplications, and performs far better in experiments. We pair this result with matching lower bounds based on reductions to communication complexity and hypothesis testing for spiked-covariance matrices. Our lower bounds fall into a broader research agenda of better understanding the computational complexity of basic linear algebra problems in the restricted 'matrix-vector query' model of computation, which generalizes common algorithmic frameworks like linear sketching and Krylov subspace methods. Joint work with Raphael A. Meyer, Cameron Musco, and David P. Woodruff. Paper: https://arxiv.org/abs/2010.09649
Katy Craig (OR Seminar)
Gradient Flows in the Wasserstein Metric: From Discrete to Continuum via Regularization
Talk details
Over the past ten years, optimal transport has become a fundamental tool in statistics and machine learning: the Wasserstein metric provides a new notion of distance for classifying distributions and a rich geometry for interpolating between them. In parallel, optimal transport has led to new theoretical results on the stability and long time behavior of partial differential equations through the theory of Wasserstein gradient flows. These two lines of research recently intersected in a series of works that characterized the dynamics of training neural networks with a single hidden layer as a Wasserstein gradient flow. In this talk, I will briefly introduce the mathematical theory of Wasserstein gradient flows and describe recent results on discrete to continuum limits. In particular, I will show how passing from the discrete to continuum limit by introducing an appropriate regularization can lead to faster rates of convergence, as well as novel, deterministic particle methods for diffusive processes.
Bio: Katy Craig is an assistant professor in the department of mathematics at the University of California, Santa Barbara. Prior to coming to UCSB, Katy received her Ph.D. from Rutgers University, held an NSF postdoc at UCLA, and held a UC President’s Postdoctoral Fellowship at UCSB.
Guillaume Basse (RAIN/OR Joint Seminar 8:30 AM PT)
Displacement Effects in a Hot Spot Policing Intervention in Medellin: Inference and Pitfalls
Talk details
In hot policing, resources are targeted at specific locations predicted to be at high risk of crime; so-called 'hot spots.' Rather than reduce overall crime, however, there is a concern that these interventions simply displace crime from the targeted locations to nearby non-hot spots. We address this question in the context of a large-scale randomized experiment in Medellin, Colombia, in which police were randomly assigned to increase patrols at a subset of possible hotspots. Estimating the displacement effects on control locations is difficult because the probability that a nearby hotspot is treated is a complex function of the underlying geography. While existing methods developed for this 'general interference' setting, especially Horvitz-Thompson (HT) estimators, have attractive theoretical properties, they can perform poorly in practice and mislead practitioners. In this talk, I explore the key pitfalls that practitioners should watch out for when conducting this type of analysis, and propose some ways to partially remedy them.
Bio: Guillaume Basse is an Assistant Professor in the MS&E and Statistics departments at Stanford. His research focuses broadly on Causal Inference and Design of Experiments in complex settings. He is particularly interested in complications arising when interventions spillover across space and / or time.
José Correa
The Value of Observability in Dynamic Pricing
Talk details
We consider a dynamic pricing problem where a firm sells one item to a single buyer in order to maximize expected revenues. The firm commits to a price function over an infinite horizon. The buyer arrives at some random time with a private value for the item. He is more impatient than the seller and strategizes the time of his purchase in order to maximize his expected utility, which implies either buying immediately or waiting to benefit from a lower price. We study how important is to observe the buyer arrival time in terms of the seller's expected revenue. When the seller can observe the arrival of the buyer, she can make the price function contingent on his arrival time. On the contrary, when the seller cannot observe the arrival, her price function is fixed at time zero for the whole horizon. The value of observability (VO) is defined as the worst case ratio between the expected revenue of the seller when she observes the buyer's arrival and that when she does not. Our main result establishes that in a very general setting about valuation and arrival time distributions, the value of observability is bounded by a small constant. To obtain this bound we fully characterize the observable arrival setting and use this solution to construct a random and periodic price function for the unobservable case. This is joint work with Dana Pizarro and Gustavo Vulcano
Bio: José Correa is a full professor in the Department of Industrial Engineering at Universidad de Chile. José obtained a mathematical engineering degree from Universidad the Chile in 1999 and a PhD in Operations Research from MIT in 2004. His research, focusing in algorithmic game theory and mechanism design, has received numerous awards including an ACM SIGecom best paper award, an INFORMS Transportation Science and Logistics best paper awards, a Tucker prize finalist, and research awards from Amazon and Google. José has given keynote talks at several institutions and conferences and has been in the program committee of international computer science conferences. He also serves and has served in the editorial board of some of the leading journals of his field: Mathematical Programming B, Mathematics of Operations Research (as Game Theory Area Editor), and Operations Research.
Jean Pouget-Abadie
Design and Analysis of Bipartite (Market) Experiments
Talk details
Bipartite experiments are randomized experiments where treatment is applied to one set of units, while outcomes are measured on a different set of units. The interactions between the treated units and the 'outcome' units can be captured by a bipartite graph. Bipartite experiments are a recent object of study in causal inference, whereby treatment is applied to one set of units and outcomes of interest are measured on a different set of units. These experiments are particularly useful in settings where strong interference effects occur between units of a bipartite graph. In market experiments for example, assigning treatment at the seller-level and measuring outcomes at the buyer-level (or vice-versa) may lead to causal models that better account for the interference that naturally occurs between buyers and sellers. In this talk, we will cover the motivation for and formal setting of bipartite experiments. Furthermore, we will explore possible design choices for such experiments, namely clustered randomized designs, as well as various unbiased inference methods.
Bio: Jean is a research scientist at Google NY, on the Algorithms and Optimization team, led by Vahab Mirrokni. Before Google, Jean was a PhD student in computer science at Harvard University, advised by Edoardo Airoldi and Salil Vadhan. Prior to that, he was an undergraduate at Ecole Polytechnique in Paris. His recent research interests focus on causal inference, particularly when interactions between units are present.
Annie Liang
Data and Incentives
Talk details
Markets for lending and insurance incentivize good behavior by forecasting risk on the basis of past outcomes. As "big data" expands the set of covariates used to predict risk, how will these incentives change? We show that "attribute" data which is informative about consumer quality tends to decrease effort, while "circumstance" data which predicts idiosyncratic shocks to outcomes tends to increase it. When covariates are independent, this effect is uniform across all consumers. Under more general forms of correlation, this effect continues to hold on average, but observation of a new covariate may lead to disparate impact---increasing effort for some consumer groups and decreasing it for others. A regulator can improve social welfare by restricting the use of either attribute or circumstance data, and by limiting the use of covariates with substantial disparate impact.
Bio: Annie Liang is an Assistant Professor of Economics and an Assistant Professor of Computer Science at Northwestern University. Her work focuses on economic theory and the application of machine learning techniques in the social sciences. She has studied the dynamics of strategic information acquisition, as well as the use of machine learning to evaluate and improve economic models.
Arun Chanrashaker
Identifying the latent space geometry of network models through analysis of curvature
Talk details
Statistically modeling networks, across numerous disciplines and contexts, is fundamentally challenging because of (often high-order) dependence between connections. A common approach assigns each person in the graph to a position on a low-dimensional manifold. Distance between individuals in this (latent) space is inversely proportional to the likelihood of forming a connection. The choice of the latent geometry (the manifold class, dimension, and curvature) has consequential impacts on the substantive conclusions of the model. More positive curvature in the manifold, for example, encourages more and tighter communities; negative curvature induces repulsion among nodes. Currently, however, the choice of the latent geometry is an a priori modeling assumption and there is limited guidance about how to make these choices in a data-driven way. In this work, we present a method to consistently estimate the manifold type, dimension, and curvature from an empirically relevant class of latent spaces: simply connected, complete Riemannian manifolds of constant curvature. Our core insight comes by representing the graph as a noisy distance matrix based on the ties between cliques. Leveraging results from statistical geometry, we develop hypothesis tests to determine whether the observed distances could plausibly be embedded isometrically in each of the candidate geometries. We explore the accuracy of our approach with simulations and then apply our approach to data-sets from economics and sociology as well as neuroscience. Paper: https://stanford.edu/~arungc/LCM.pdf
Bio: Arun Chandrasekhar is an Associate Professor of Economics at Stanford University. His work focuses on development economics. He studies the role that social networks play in developing countries. In particular, he is interested in how the economics of networks can help us understand information aggregation failures and breakdown of cooperation in the developing world.
Michael Leung
Network Cluster-Robust Inference
Talk details
Since network data commonly consists of observations on a single large network, researchers often partition the network into clusters in order to apply cluster-robust inference methods. All existing such methods require clusters to be asymptotically independent. We prove that for this requirement to hold, under certain conditions, it is necessary and sufficient for clusters to have low conductance, the ratio of edge boundary size to volume, which yields a measure of cluster quality. We show in simulations that, for important classes of networks lacking low-conductance clusters, cluster-robust methods can exhibit substantial size distortion, whereas for networks with such clusters, they outperform HAC estimators. To assess the existence of low-conductance clusters and construct them, we draw on results in spectral graph theory showing a close connection between conductance and the spectrum of the graph Laplacian. Based on these results, we propose to use the spectrum to compute the number of low-conductance clusters and spectral clustering to compute the clusters. We illustrate our results and proposed methods in simulations and empirical applications.
Bio: Michael Leung is an economist at USC whose work focuses on developing econometric methods for network data.
Paul Milgrom
Investment Incentives in Near-Optimal Mechanisms
Talk details
In many real-world resource allocation problems, optimization is computationally intractable, so any practical allocation mechanism must be based on an approximation algorithm. We study investment incentives in strategy-proof mechanisms that use such approximations. In sharp contrast with the Vickrey-Clark-Groves mechanism, for which individual returns on investments are aligned with social welfare, we find that some algorithms that approximate efficient allocation arbitrarily well can nevertheless create misaligned investment incentives that lead to arbitrarily bad overall outcomes. However, if a near-efficient algorithm "excludes bossy negative externalities," then its outcomes remain near-efficient even after accounting for investments. A weakening of this "XBONE" condition is necessary and sufficient for the result.
Bio: Paul Milgrom is the Shirley and Leonard Ely professor of Humanities and Sciences in the Department of Economics at Stanford University and professor, by courtesy, at both the Department of Management Science and Engineering and the Graduate School of Business. He is the world's leading auction designer, known for his work on auction theory and innovative resource allocation methods, particularly in radio spectrum. He is the co-recipient of the 2020 Nobel Prize in Economic Sciences, together with Robert Wilson, 'for improvements to auction theory and inventions of new auction formats.'
Shipra Agrawal
Dynamic Pricing and Learning under the Bass Model
Talk details
We consider a novel formulation of the dynamic pricing and demand learning problem, where the evolution of demand in response to posted prices is governed by a stochastic variant of the popular Bass model with parameters (α, β) that are linked to the so-called "innovation" and "imitation" effects. Unlike the more commonly used i.i.d. demand models, in this model the price posted not only affects the demand and the revenue in the current round but also the evolution of demand, and hence the fraction of market potential that can be captured, in future rounds. Finding a revenue-maximizing dynamic pricing policy in this model is non-trivial even when model parameters are known, and requires solving for the optimal non-stationary policy of a continuous-time, continuous-state MDP. In this paper, we consider the problem of dynamic pricing is used in conjunction with learning the model parameters, with the objective of optimizing the cumulative revenues over a given selling horizon. Our main contribution is an algorithm with a regret guarantee of O (m^2/3), where m is mnemonic for the (known) market size. Moreover, we show that no algorithm can incur smaller order of loss by deriving a matching lower bound. We observe that in this problem the market size m, and not the time horizon T, is the fundamental driver of the complexity; our lower bound in fact indicates that for any fixed α,β, most non-trivial instances of the problem have constant T and large m. This insight sets the problem setting considered here uniquely apart from the MAB type formulations typically considered in the learning to price literature.
Bio: Shipra Agrawal is Cyrus Derman Assistant Professor of the Department of Industrial Engineering and Operations Research. She is also affiliated with the Department of Computer Science and the Data Science Institute, at Columbia University. She received her Ph.D. from Stanford University in June 2011 under the guidance of Prof. Yinyu Ye and was a researcher at Microsoft Research India from 2011 to 2015. Her research spans several areas of optimization and machine learning, including online optimization under uncertainty, multi-armed bandits, online learning, and reinforcement learning. Shipra serves as an associate editor for Management Science, Mathematics of Operations Research, and INFORMS Journal on Optimization. Her research is supported by a Google Faculty Research Award, an Amazon research award, and an NSF CAREER Award.
Lihua Lei
Hierarchical Community Detection for Heterogeneous and Multi-scaled Networks
Talk details
Real-world networks are often hierarchical, heterogeneous, and multi-scaled, while the idealized stochastic block models that are extensively studied in the literature tend to be over-simplified. In a line of work, we propose several top-down recursive partitioning algorithms which start with the entire network and divide the nodes into two communities by certain spectral clustering methods repeatedly, until a stopping rule indicates no further community structures. For these algorithms, the number of communities does not need to be known a priori or estimated consistently. On a broad class of hierarchical network models, our algorithms are proved to achieve the exact recovery for sparse networks with expected node degrees logarithmic in the network size, and are computationally more efficient than non-hierarchical spectral clustering algorithms. More interestingly, we identify regimes where no algorithm can recover all communities simultaneously while our algorithm can still recover the mega-communities (unions of communities defined by the hierarchy) consistently without recovering the finest structure. Our theoretical results are based on the newly developed two-to-infinity eigenspace perturbation theory for binary random matrices with independent or dependent entries.
Bio: Lihua Lei is a postdoctoral researcher in Statistics at Stanford University, advised by Emmanuel Candès. Prior to joining Stanford, he obtained his Ph.D. in statistics at UC Berkeley, advised by Peter Bickel and Michael Jordan. His research areas include network analysis, causal inference, conformal inference, multiple hypothesis testing, and stochastic optimization.
Mukund Sundararajan
Using Attribution to Understand Deep Neural Networks
Talk details
Predicting cancer from XRays seemed great Until we discovered the true reason. The model, in its glory, did fixate On radiologist markings - treason!
We found the issue with attribution: By blaming pixels for the prediction (1,2,3,4,5,6). A complement'ry way to attribute, is to pay training data, a tribute (1).
If you are int'rested in FTC, counterfactual theory, SGD Or Shapley values and fine kernel tricks, Please come attend, unless you have conflicts
Should you build deep models down the road, Use attributions. Takes ten lines of code!
Bio: There once was an RS called MS, He studied models that are a mess, A director at Google. Accurate and frugal, Explanations are what he liked best.
Mark Braverman
Optimization-friendly generic mechanisms without money
Talk details
Our goal is to develop a generic framework for converting modern gradient-descent based optimization algorithms into mechanisms where inputs come from self-interested agents. We focus on aggregating preferences from n players in a context without money. Special cases of this setting include voting, allocation of items by lottery, and matching. Our key technical contribution is a new meta-algorithm we call APEX (Adaptive Pricing Equalizing Externalities). The framework is sufficiently general to be combined with any optimization algorithm that is based on local search. In the talk I'll outline the algorithm, and open problem/research directions that it raises, with a particular focus towards mechanism design + ML. If time permits, I will discuss a special case of applying the framework to the problem of one-sided allocation with lotteries. In this case, we obtain a strengthening of the 1979 result by Hylland and Zeckhauser on allocation via a competitive equilibrium from equal incomes (CEEI). The [HZ79] result posits that there is a (fractional) allocation and a set of item prices such that the allocation is a competitive equilibrium given prices. We further show that there is always a reweighing of the players' utility values such that running the standard unit-demand VCG with reweighed utilities leads to a HZ-equilibrium prices. Interestingly, not all HZ competitive equilibria come from VCG prices.
Bio: Mark Braverman is a professor of Computer Science at Princeton University. He works primarily on building new connections between theoretical computer science and other disciplines, including information theory, algorithmic mechanism design, dynamical systems, analysis, and geometry. He received a 2013 Packard Fellowship, and a 2019 NSF Alan T. Waterman award.
Elena Manresa (12-1 pm PT)
An Adversarial Approach to Structural Estimation
Talk details
We propose a new simulation-based estimation method, adversarial estimation, for structural models. The estimator is formulated as the solution to a minimax problem between a generator (which generates synthetic observations using the structural model) and a discriminator (which classifies if an observation is synthetic). The discriminator maximizes the accuracy of its classification while the generator minimizes it. We show that, with a sufficiently rich discriminator, the adversarial estimator attains parametric efficiency under correct specification and the parametric rate under misspecification. We advocate the use of a neural network as a discriminator that can exploit adaptivity properties and attain fast rates of convergence. We apply our method to the elderly’s saving decision model and show that including gender and health profiles in the discriminator uncovers the bequest motive as an important source of saving across the wealth distribution, not only for the rich.
2019-2020
Shane Henderson
Under the Hood of Bike Sharing
Suleyman Kerimov (first half)
Scrip Systems with Minimal Availability
Nikhil Garg (second half)
Driver Surge Pricing
Rupert Freeman
Truthful Aggregation of Budget Proposals
Aleksandra Korolova
Societal Concerns in Targeted Advertising
Ali Aouad (OR Seminar)
Click-Based MNL: Algorithmic Frameworks for Modeling Click Data in Assortment Optimization
Peng Shi
Optimal Priority-Based Allocation Mechanisms
Matt Weinberg
(a biased selection of) Recent Developments in Combinatorial Auctions
Sham Kakade (OR Seminar)
Representation, Modeling, and Optimization in Reinforcement Learning
Warren Powell (OR Seminar)
From Reinforcement Learning to Stochastic Optimization: A Universal Framework for Sequential Decision Analytics
Haris Aziz
Fair and Efficient Allocation of Indivisible Goods and Chores
Avi Mandelbaum (OR Seminar)
"Theompirical" Research of Service Systems
Edward McFowland III
Estimating Causal Peer Influence in Homophilous Social Networks by Inferring Latent Locations
Benjamin Plaut (first half)
Beyond the First Welfare Theorem: Counteracting Inequality in Markets
Faidra Monachou (second half)
Discrimination in Online Markets: Effects of Social Bias on Learning from Reviews and Policy Design
