The Colloquium on Digital Transformation is a series of weekly online talks featuring top scientists from academia and industry on how artificial intelligence, machine learning, and big data can lead to scientific breakthroughs with large-scale societal benefit.
Register for the fall Zoom webinar series here.
See videos of all C3.ai DTI talks at YouTube.com/C3DigitalTransformationInstitute.
February 10, 2022, 1 pm PT/3 pm CT
A Fresh Look at Design: A Rigorous Framework for Integrating Model-Based and Data-Based Systems Engineering
John S. Baras, Distinguished University Professor, Institute for Systems Research, University of Maryland
Advances in Information Technology have enabled the design of complex engineered systems, with large numbers of heterogeneous components capable of multiple complex functions leading to ubiquitous cyber-physical systems (CPS). At the same time, these advances have increased these systems’ capabilities and increased their complexity to such an extent that systematic design towards predictable performance is extremely challenging. We first describe a rigorous framework we are developing for model-based systems engineering (MBSE) that addresses these challenges, incorporating manufacturing and operation and lifecycle considerations. We describe three fundamental components for MBSE within our framework: (a) An integrated systems modeling hub built around SysML; (b) Linking this modeling hub with tradeoff analysis tools for design space exploration; (c) Representation and management of requirements. We then describe more recent work aiming to integrate Data-Based design (ML and AI methods and algorithms) with our MBSE framework. We briefly describe applications of the emerging framework to several important current technological problems: power grids, automotive, aerospace, energy-efficient buildings, sensor and communication networks, smart manufacturing, robotics and UAVs, healthcare, and cybersecurity. We close with research challenges and future promising research directions.
John S. Baras, a Distinguished University Professor, holds the Lockheed Martin Chair in Systems Engineering, a Joint Appointment with the Institute for Systems Research (ISR) and the ECE Department at the University of Maryland College Park. He received his Ph.D. degree in Applied Mathematics in 1973 from Harvard University, and has been with UMD since then. From 1985 to 1991, he became Founding Director of the ISR. Since 1992, he has directed the Maryland Center for Hybrid Networks, which he co-founded. He is a Fellow of IEEE (Life), SIAM, AAAS, NAI, IFAC, AMS, AIAA, Member of the National Academy of Inventors (NAI), and a Foreign Member of the Royal Swedish Academy of Engineering Sciences.
Major honors and awards include the 1980 George Axelby Award from the IEEE Control Systems Society, the 2006 Leonard Abraham Prize from the IEEE Communications Society, the 2017 IEEE Simon Ramo Medal, the 2017 AACC Richard E. Bellman Control Heritage Award, and the 2018 AIAA Aerospace Communications Award. In 2016, he was inducted into the University of Maryland A. J. Clark School of Engineering Innovation Hall of Fame. In June 2018, he was awarded a Doctorate Honoris Causa by his alma mater, the National Technical University of Athens, Greece. His research interests include systems, control, optimization, autonomy, machine learning, artificial intelligence, and communication.
Watch the recording on YouTube
February 17, 2022, 1 pm PT/3 pm CT
On Dynamics-Informed Blending of Machine Learning and Game Theory
Michael I. Jordan, Pehong Chen Distinguished Professor, University of California, Berkeley
Much of the recent focus in machine learning has been on the pattern-recognition side of the field. I will focus instead on the decision-making side, where many fundamental challenges remain. Some are statistical in nature, including the challenges associated with multiple decision-making, and some are algorithmic — including the challenge of coordinated decision-making on distributed platforms, and others are economic, involving learning systems that must cope with scarcity, competition, and incentives. I will present recent progress on each of these fronts, focusing on the economics front.
Michael I. Jordan is the Pehong Chen Distinguished Professor at the University of California, Berkeley. His research interests include machine learning, optimization, control theory, and computational biology. Professor Jordan is a member of the National Academy of Sciences, the National Academy of Engineering, and the American Academy of Arts and Sciences. He is a Foreign Member of the Royal Society. He was a Plenary Lecturer at the International Congress of Mathematicians in 2018. He has received the Ulf Grenander Prize from the American Mathematical Society, the IEEE John von Neumann Medal, the IJCAI Research Excellence Award, the David Rumelhart Prize, and the ACM/AAAI Allen Newell Award.
February 24, 2022, 1 pm PT/3 pm CT
Algorithmic Tools for U.S. Congressional Districting: Fairness via Analytics
David Shmoys, Laibe/Acheson Professor, Cornell University
The American winner-take-all congressional district system empowers politicians to engineer electoral outcomes by manipulating district boundaries. Computational solutions have mostly focused on drawing “unbiased” maps by simply optimizing for compactness and related metrics. We maintain that this approach is flawed; to achieve a meaningful notion of fairness, one must model political and demographic considerations, using historical data. We discuss two papers that develop this perspective. In the first (with Wes Gurnee), we show how to explicitly optimize for arbitrary piecewise-linear definitions of fairness, presenting a comprehensive 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. In the second (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 currently proposed in H.R. 4000). We present large-scale analyses for Congress 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, while significantly curtailing the power of advantage-seeking partisans.
David Shmoys is the Laibe/Acheson Professor and Director of the Center for Data Science for Enterprise & Society at Cornell University. He obtained his PhD in Computer Science from the University of California, Berkeley in 1984, and held postdoctoral positions at MSRI in Berkeley and Harvard University, and a faculty position at MIT before joining the Cornell University faculty. His research has focused on the design and analysis of efficient algorithms for discrete optimization problems, with applications including scheduling, inventory theory, computational biology, computational sustainability, and most recently, data-driven decision-making in the sharing economy.
March 3, 2022, 1 pm PT/3 pm CT
Optimal and Differentially Private Data Acquisition from Strategic Users
Asuman Ozdaglar, MathWorks Professor of Electrical Engineering and Computer Science; Department Head, EECS, MIT
The data of billions of people around the world are used every day for improving search algorithms, recommendations on online platforms, personalized advertising, and the design of new drugs, services and products. With rapid advances in machine learning (ML) algorithms and further growth in data collection, these practices will become only more widespread in the years to come. A common concern with many of these data-intensive applications centers on privacy — as a user’s data is harnessed, more and more information about her behavior and preferences are uncovered and potentially utilized by platforms and advertisers. A popular solution to the tension between privacy costs and benefits of data is to use methods such as differential privacy in order to limit the extent to which an individual’s data is uncovered and exploited. Although these methods are already used by many of the tech companies, a key practical question remains: how do we decide how much privacy heterogeneous, strategic users will obtain?
This talk is an attempt to answer this key question and study the impact of data market architecture on the design of mechanisms for purchasing data from privacy sensitive strategic users. We consider a platform interested in estimating an underlying parameter using data collected from users. We formulate this question as a Bayesian-optimal mechanism design problem, in which an individual can share her (verifiable) data in exchange for a monetary reward or services, but at the same time has a (private) heterogeneous privacy sensitivity that represents her cost per unit privacy loss. We consider two popular differential privacy settings for providing privacy guarantees for the users: central and local. In both cases, we establish minimax lower bounds for the estimation error and derive (near) optimal estimators for given heterogeneous privacy loss levels for users. Building on this characterization, we pose the mechanism design problem as the optimal selection of an estimator and payments that will elicit truthful reporting of privacy sensitivities of users under a regularity condition on the distribution of privacy sensitivities. Our mechanism in the central setting can be implemented in log-linear time in the number of users, and, in the local setting, it admits a Polynomial Time Approximation Scheme (PTAS).
Joint work with Alireza Fallah, Ali Makhdoumi, and Azarakhsh Malekian.
Asu Ozdaglar received the B.S. degree in electrical engineering from the Middle East Technical University, Ankara, Turkey, in 1996, and the S.M. and the Ph.D. degrees in electrical engineering and computer science from the Massachusetts Institute of Technology, Cambridge, in 1998 and 2003, respectively. She is the Mathworks Professor of Electrical Engineering and Computer Science (EECS) at the Massachusetts Institute of Technology (MIT). She is also the department head of EECS and deputy dean of academics of the Schwarzman College of Computing at MIT. Her research expertise includes optimization theory and algorithms, game theory, machine learning and network analysis with applications in social, economic and financial networks.
Her recent research focuses on designing incentives and algorithms for data-driven online systems with many diverse human-machine participants. Professor Ozdaglar is the recipient of a Microsoft fellowship, the MIT Graduate Student Council Teaching award, the NSF Career award, the 2008 Donald P. Eckman award of the American Automatic Control Council, the 2014 Spira teaching award, and Keithley, Distinguished School of Engineering and Mathworks professorships. She is an IEEE fellow and was selected as an invited speaker at the International Congress of Mathematicians. She served on the Board of Governors of the Control System Society in 2010 and was an associate editor for IEEE Transactions on Automatic Control. She was the inaugural area co-editor for the area entitled “Games, Information and Networks” in the journal Operations Research. She is the co-author of the book entitled “Convex Analysis and Optimization” (Athena Scientific, 2003).
Watch the recording on YouTube
March 10, 2022, 1 pm PT/3 pm CT
How Does the Brain Beget the Mind?
Christos Papadimitriou, Donovan Family Professor of Computer Science, Columbia University
It is beyond doubt that cognition and intelligence are the result of neural activity — but how? How do molecules, neurons and synapses give rise to reasoning, language, plans, stories, art, math? Despite dazzling progress in experimental neuroscience, as well as in cognitive science, we do not seem to be making progress in the overarching question. The reason is that these two communities are separated by a huge gap — not just in scale, but also in experimental methodology, tradition, and mindset. As Richard Axel recently put it in an interview to Neuron: “We don’t have a logic for the transformation of neural activity into thought…” What kind of formal system would qualify as this “logic”? I will introduce the Assembly Calculus, a computational system whose basic data structure is the assembly: assemblies are large populations of neurons representing concepts, words, ideas, episodes, etc. The Assembly Calculus is biologically plausible in the following two orthogonal senses: Its primitives are properties of assemblies observed in experiments, or useful for explaining other experiments, and can be provably (through both mathematical proof and simulations in biologically realistic platforms) “compiled down” to the activity of neurons and synapses. Furthermore, the Assembly Calculus can be shown both mathematically and experimentally to simulate simple high-level cognitive functions, such as parsing simple sentences, as well as planning. We believe that this formalism is well positioned to help in bridging the gap between the brain and the mind.
Christos Harilaos Papadimitriou is the Donovan Family Professor of Computer Science at Columbia University. Before joining Columbia in 2017, he was a professor at UC Berkeley for the previous 22 years, and before that he taught at Harvard, MIT, NTU Athens, Stanford, and UCSD. He has written five textbooks and many articles on algorithms and complexity, and their applications to optimization, databases, control, AI, robotics, economics and game theory, the Internet, evolution, and the brain. He holds a PhD from Princeton (1976), and eight honorary doctorates, including from ETH, University of Athens, EPFL, and Univ. de Paris Dauphine.
He is a member of the National Academy of Sciences of the U.S., the American Academy of Arts and Sciences, and the National Academy of Engineering, and he has received the Knuth prize, the Go”del prize, the von Neumann medal, as well as the 2018 Harvey Prize by Technion. In 2015, the president of the Hellenic republic named him commander of the order of the Phoenix. He has also written three novels: “Turing,” “Logicomix,” and his latest, “Independence.”
Watch the recording on YouTube
March 17, 2022, 1 pm PT/3 pm CT
Communicating with Anecdotes
Nicole Immorlica, Senior Principal Researcher, Microsoft Research
We study a communication game between a sender and receiver where the sender has access to a set of informative signals about a state of the world. The sender chooses one of her signals and communicates it to the receiver. We call this an “anecdote”. The receiver takes an action, yielding a utility for both players. Sender and receiver both care about the state of the world but are also influenced by a personal preference so that their ideal actions differ. We characterize perfect Bayesian equilibria when the sender cannot commit to a particular communication scheme. In this setting the sender faces “persuasion temptation”: she is tempted to select a more biased anecdote to influence the receiver’s action. Anecdotes are still informative to the receiver but persuasion comes at the cost of precision. This gives rise to “informational homophily” where the receiver prefers to listen to like-minded senders because they provide higher-precision signals. We show that for fat-tailed anecdote distributions the receiver might even prefer to talk to poorly informed senders with aligned preferences rather than a knowledgeable expert whose preferences may differ from her own because the expert’s knowledge also gives her likely access to highly biased anecdotes. We also show that under commitment differences in personal preferences no longer affect communication and the sender will generally report the most representative anecdote closest to the posterior mean for common distributions.
Nicole’s research lies broadly within the field of economics and computation. Using tools and modeling concepts from both theoretical computer science and economics, Nicole hopes to explain, predict, and shape behavioral patterns in various online and offline systems, markets, and games. Her areas of specialty include social networks and mechanism design. Nicole received her Ph.D. from MIT in Cambridge, MA in 2005 and then completed three years of postdocs at both Microsoft Research in Redmond, WA and CWI in Amsterdam, Netherlands before accepting a job as an assistant professor at Northwestern University in Chicago, IL in 2008. She joined Microsoft Research in 2012 and is currently based out of Boston, MA.
March 31, 2022, 1 pm PT/3 pm CT
Inducement of Desired Behavior via Soft Policies
Tamer Basar, Swanlund Endowed Chair Emeritus and CAS Professor Emeritus of ECE, University of Illinois Urbana-Champaign
Terms like inducement, incentivization, persuasion, and to some extent enticement, are used in our daily lives to describe situations where one individual (decision maker, or entity) acts in a way to influence the decision-making process of another individual or individuals, where the outcome could benefit all involved or only the one who has initiated the process. Such influence could be exerted in two different ways (though variations do exist): via a direct input by the influencer into the utility or reward (or loss) of the receiving party, or by controlling (and possibly manipulating) the information flow to the latter, in an attempt to shape beliefs at the receiving end (as in propagation of disinformation). Both scenarios (and those that fall in between) could be analyzed within a dynamic Stackelberg game-theoretic framework, with a precise notion of equilibrium, which I will address in this talk. My focus will naturally be on soft inducement (incentivization, persuasion) policies, rather than hard enforcement (such as threat) ones, which are not that interesting. I will discuss some explicit models that lead to appealing such policies. I will also talk about the impact of various factors, such as population size and uncertainty in modeling, on the resulting equilibria, and identify several challenges that lie ahead.
Tamer Başar is with the University of Illinois Urbana-Champaign (UIUC), currently as Swanlund Endowed Chair Emeritus, CAS Professor Emeritus of ECE, and Research Professor at CSL and ITI. He has served at UIUC as Director of the Center for Advanced Study (CAS), Interim Dean of Engineering, and Interim Director of the Beckman Institute. His research interests include stochastic teams, games, and networks; robust control; multi-agent systems and learning; data-driven distributed optimization; spread of (dis)information and epidemics; security and trust; energy systems; and cyber-physical systems. He is a member of the National Academy of Engineering, fellow of several societies, and recipient of several major awards, most recently the Wilbur Cross Medal from Yale. He also holds honorary titles from various universities in both Europe and Asia.
April 7, 2022, 1 pm PT/3 pm CT
Online Optimization and Control Using Black-Box Predictions
Adam Wierman, Professor of Computing and Mathematical Sciences, California Institute of Technology
Making use of modern black-box AI tools is potentially transformational for online optimization and control. However, such machine-learned algorithms typically do not have formal guarantees on worst-case performance, stability, or safety. So, while their performance may improve upon traditional approaches in “typical” cases, they may perform arbitrarily worse in scenarios where the training examples are not representative due to, e.g., distribution shift or unrepresentative training data. This represents a significant drawback when considering the use of AI tools for energy systems and autonomous cities, which are safety-critical. A challenging open question is thus: Is it possible to provide guarantees that allow black-box AI tools to be used in safety-critical applications? In this talk, I will introduce recent work that aims to develop algorithms that make use of black-box AI tools to provide good performance in the typical case while integrating “untrusted advice” from these algorithms into traditional algorithms to ensure formal worst-case guarantees. Specifically, we will discuss the use of black-box untrusted advice in the context of online convex body-chasing, online non-convex optimization, and linear quadratic control, identifying both novel algorithms and fundamental limits in each case.
Adam Wierman is a Professor in the Department of Computing and Mathematical Sciences (CMS) at the California Institute of Technology. He is the director of the Information Science and Technology initiative and served as Executive Officer (a.k.a. Department Chair) of CMS from 2015-2020. Additionally, he serves on Advisory Boards of the Linde Institute of Economic and Management Sciences and the “Sunlight to Everything” thrust in the Resnick Institute for Sustainability. He received his PhD, MSc and BSc in Computer Science from Carnegie Mellon University in 2007, 2004, and 2001, respectively, and has been a faculty member at Caltech since 2007.
April 14, 2022, 1 pm PT/3 pm CT
On Convergence and Stability of Coupled Belief – Strategy Learning Dynamics in Continuous Games
Manxi Wu, Postdoctoral Researcher, UC Berkeley, Department of Electrical Engineering and Computer Science, Simons Institute
We study a dynamic setting in which a public information platform updates a belief estimate of a continuous game parameter based on available data of strategies and payoffs. Players adjust their strategies by accounting for the repeatedly updated belief. The long-term behavior of the resulting stochastic learning dynamics is based on endogenous and non-i.i.d. data that is generated by players’ strategic decisions. We develop new tools to tackle the dynamic interplay between parameter learning and strategy learning in continuous games. We present results on the convergence and stability of such learning dynamics and develop conditions for convergence to complete information equilibrium. Furthermore, we apply this learning model to analyze the impact of information platforms on the strategic behavior of travelers in urban transportation systems. We show that our results can be used to design adaptive tolling mechanisms with travelers learning their routing decisions in traffic networks.
Manxi Wu is a research fellow at the University of California, Berkeley, in the learning and games program at the Simons Institute and at the Department of Electrical Engineering and Computer Science. In summer 2022, she will start as an assistant professor in Cornell’s School of Operations Research and Information Engineering. Her fields of interest are game theory, machine learning, engineering systems, and the theory of economic incentives. Her research analyzes strategic interactions between technologies and human users under the physical constraints and uncertainty of socio-technical systems. She also designs information and incentive mechanisms to improve system efficiency and resiliency. Manxi received her Ph.D. in social and engineering systems at MIT.
She also holds an M.S. in Transportation at MIT and B.S. in applied mathematics from Peking University. She is a recipient of the Hammer Fellowship, UTC Milton Pikarsky Memorial Award, Siebel Scholarship, EECS Rising Star, and Simons fellowship.
Watch the recording on YouTube
April 21, 2022, 1 pm PT/3 pm CT
AI for Social Impact: Results From Deployments for Public Health and Conservation
Milind Tambe, Professor, Harvard University and Google Research
With the maturing of AI and multi-agent systems research, we have a tremendous opportunity to direct these advances towards addressing complex societal problems. I will focus on domains of public health and conservation and address one key cross-cutting challenge: how to effectively deploy our limited intervention resources in these problem domains. I will present results from work around the globe using AI for challenges such as HIV prevention, maternal and child care interventions, and as well as wildlife conservation. Achieving social impact in these domains often requires methodological advances. To that end, I will highlight key research advances in multi-agent reasoning and learning, in particular in restless multi-armed bandits, influence maximization in social networks, computational game theory, and decision-focused learning. In pushing this research agenda, our ultimate goal is to facilitate local communities and non-profits to directly benefit from advances in AI tools and techniques.
Milind Tambe is the Gordon McKay Professor of Computer Science and Director of the Center for Research in Computation and Society at Harvard University; he also directs “AI for Social Good” at Google Research India. He is recipient of the IJCAI John McCarthy Award, AAMAS ACM Autonomous Agents Research Award, AAAI Robert S. Engelmore Memorial Lecture Award, and he is a fellow of AAAI and ACM. He has also received the INFORMS Wagner prize, Rist Prize from Military Operations Research Society, and the Columbus Fellowship Foundation Homeland Security Award, along with commendations from the U.S .Coast Guard, Federal Air Marshals Service, and Los Angeles airport police.
April 28, 2022, 1 pm PT/3 pm CT
Allocating Goods, Bads, and Mixed: Fairness and Efficiency through Competitiveness
Ruta Mehta, Assistant Professor, University of Illinois at Urbana-Champaign
Fair division is the problem of allocating a set of items among agents in a fair and efficient manner. This age-old problem, mentioned even in the Bible, arises naturally in a wide range of real-life settings, for example, school seat assignments, partnership dissolution, sharing of satellites, and dividing costs for climate resilience. Division based on competitive equilibrium (CE) has emerged as one of the best mechanisms for this problem. The existence and computability of CE have been extensively studied when all items are disposable goods, while the problem is less explored when some of them are nondisposable chores (bads). In this talk, I will discuss recent algorithmic advances on the computation of CE when each item may be a good, a chore, or both (mixed).
I will first consider the case of additive valuations, where when all items are goods, the CE set is well-known to be captured by convex programming formulations and thereby forms a convex set. In sharp contrast, with chores, the CE set may be nonconvex and disconnected. I will discuss how to handle this non-convexity through a novel exterior-point method to find an approximate CE in polynomial time (FPTAS). This method seems general enough to work with any mathematical formulation that optimizes a coordinate-wise monotone function over linear constraints. Finally, I will discuss extensions to general utility functions, and recent developments on the exchange setting (barter system).
Based on joint works with Shant Boodaghians, Bhaskar Ray Chaudhury, Jugal Garg, and Peter McGlaughlin.
Ruta Mehta is an Assistant Professor of Computer Science at the University of Illinois at Urbana-Champaign. Prior to joining UIUC, she was a postdoctoral fellow at Simons Institute, UC Berkeley, and at College of Computing, Georgia Tech. She did her Ph.D. from the Indian Institute of Technology Bombay, India. Her research interests lie in theoretical computer science and its interface with economics, games theory, fair division, and learning. Her honors include the NSF CAREER Award, the Simons-Berkeley Research Fellowship, and the Best Postdoctoral Award (given by CoC@GT). Her Ph.D. thesis won the ACM India Doctoral Dissertation Award and the IIT-Bombay Excellence in Ph.D. Thesis Award.
May 5, 2022, 1 pm PT/3 pm CT
Auditing and Designing for Equity in Resident Crowdsourcing
Nikhil Garg, Assistant Professor, Cornell Tech
Modern city governance relies heavily on crowdsourcing (or “coproduction”) to identify problems such as downed trees and power-lines. A major concern in these systems is that residents do not report problems at the same rates, leading to an inefficient and inequitable allocation of government resources. However, measuring such under-reporting is a difficult statistical task, as, almost by definition, we do not observe incidents that are not reported. Thus, distinguishing between low reporting rates and low ground-truth incident rates is challenging. First, joint with Zhi Liu, we develop a method to identify (heterogeneous) reporting rates, without using external (proxy) ground truth data. Our insight is that rates on duplicate reports about the same incident can be leveraged, to turn the question into a standard Poisson rate estimation task—even though the full incident reporting interval is also unobserved. We apply our method to over 100,000 resident reports made to the New York City Department of Parks and Recreation, finding that there are substantial spatial and socio-economic disparities in reporting rates, even after controlling for incident characteristics. Second, I’ll overview our work in redesigning inspection decisions to improve system efficiency and equity.
Nikhil Garg is an Assistant Professor of Operations Research and Information Engineering at Cornell Tech as part of the Jacobs Technion-Cornell Institute. His research interest is the application of algorithms, data science, and mechanism design to the study of democracy, markets, and societal systems at large. He received his PhD from Stanford University, and has spent considerable time in industry — most recently, he was the Principal Data Scientist at PredictWise, which provides election analytics for political campaigns. Nikhil received the INFORMS George Dantzig dissertation Award and an honorable mention for the ACM SIGecom dissertation award.
May 12, 2022, 1 pm PT/3 pm CT
Decentralized, Communication- and Coordination-free Learning in Structured Matching Markets
Chinmay Maheshwari, Graduate Student Researcher, Electrical Engineering and Computer Sciences, University of California, Berkeley
We study the problem of online learning in competitive settings in the context of two-sided matching markets. In particular, one side of the market, the agents, must learn about their preferences over the other side, the firms, through repeated interaction while competing with other agents for successful matches with preferred firms. We propose a class of decentralized, communication- and coordination-free algorithms that agents can use to reach their stable match in structured matching markets. In contrast to prior works, the proposed algorithms make decisions based solely on an agent’s own history of play and require no foreknowledge of the firms’ preferences. Our algorithms are constructed by splitting up the statistical problem of learning one’s preferences, via noisy observations, from the problem of competing for firms. We present two specific algorithms — one based on Upper Confidence Bounds and other based on Thompson sampling — both of which, under realistic structural assumptions on the underlying preferences of the agents and firms, incur a regret which grows at most logarithmically in the time horizon. Our results show that, in the case of matching markets, competition need not drastically affect the performance of online learning algorithms.
Chinmay Maheshwari is pursuing his doctoral studies at the University of California, Berkeley, with Professor Shankar Sastry. Maheshwari received his Bachelor of Technology (B.Tech) and Master of Technology (M.Tech) degrees from the Indian Institute of Technology, Bombay. His research focuses on using tools from game theory, control theory, online learning, and optimization for the design of robust and efficient societal-scale systems comprised of strategic and adversarial entities.