Algorithmic game theory, mechanism design, and learning

We study Bayesian information design for managing the concentrations of strategic agents across a congestible hub and peripheral location(s). Agents’ payoffs are location-specific and depend on an uncertain parameter. The agents face a central planner who seeks to manage the concentration of agents at the hub. The design problem is to determine signaling that maximizes the planner’s expected utility (which may be parameter-dependent), with agents using this information to update beliefs about their expected payoff from moving to the hub. This problem arises in applications such as managing hybrid workers to control the spread of a contagious disease, and ensuring driver availability in ride-hailing systems affected by a surge.

We focus on two settings not yet addressed in the literature: (1) Planner prefers agent concentrations at the hub that can be expressed as a union of finitely many closed intervals for all parameter values; (2) Planner’s preference is a function of the parameter and the concentration of agents at the hub. For setting (1) we show that optimal design is a monotone partitional signaling for typical parameter distributions; that is, the planner maximizes her utility by disclosing a signal corresponding to the interval in which the true parameter belongs. This interval-based structure is, in general, not optimal for the setting (2). Here, we develop a linear programming approach that provides an approximately optimal design by computing a map from discretized subintervals of the parameter space to a distribution over a set of signals.

Finally, we extend these ideas to a dynamic setting where the planner sequentially provisions information over a memoryless time horizon. We show that the optimal design admits a simple time-independent strategy that is more effective at managing congestion at the hub in comparison to other information provision benchmarks.

This work is joint with Sohil Shah and Patrick Jaillet.

Bio: Saurabh Amin with the Department of Civil and Environmental Engineering (CEE) at Massachusetts Institute of Technology (MIT). He currently serves as Director of Henry L. Pierce Laboratory for Infrastructure Science and Engineering and CEE Undergraduate Officer. He is a member of the Laboratory of Information and Decision Systems (LIDS) and the Operations Research Center (ORC) at MIT.

We study the power of cooperation in a network of agents that exchange information with each other to learn faster. In the talk, we show the extent to which cooperation allows to prove performance bounds that are strictly better than the known bounds for noncooperating agents. Our results are formulated within the online learning setting and hold for variuos types of feedback models.

We study a network design problem (NDP) where the planner aims at selecting the optimal single-link intervention on a transportation network to minimize the travel time under Wardrop equilibrium flows. Our first result is that, if the delay functions are affine and the support of the equilibrium is not modified with interventions, the NDP may be formulated in terms of electrical quantities computed on a related resistor network. In particular, we show that the travel time variation corresponding to an intervention on a given link depends on the effective resistance between the endpoints of the link. We suggest an approach to approximate such an effective resistance by performing only local computation, and exploit it to design an efficient algorithm to solve the NDP. We discuss the optimality of this procedure in the limit of infinitely large networks, and provide a sufficient condition for its optimality. We then provide numerical simulations, showing that our algorithm achieves good performance even if the equilibrium support varies and the delay functions are nonlinear.

Suppose a gambler faces a finite sequence of independent nonnegative random rewards with known distribution. The random variables are realized one after the other, and at each point in time, the gambler can either keep the current value and stop the sequence or discard that value forever and continue with the next. The basic prophet inequality states that the gambler can obtain, in expectation, at least half of what a prophet, who knows the realizations beforehand, could. This elementary model leads to a vast array of deep mathematical and computational questions that the probability theory community has studied for half a century. More recently, due to notable connections to online combinatorial allocations and the optimization of online marketplaces, the topic has expanded much beyond the original ground and is an active research direction in computer science and operations research. In this talk I will first review some elementary variants of the prophet inequality problem, and then move on to connections with online combinatorial allocations.

Bio: Jose Correa is a full professor in the Department of Industrial Engineering and a PI at the Center for Mathematical Modeling, both at Universidad de Chile. Jose obtained a mathematical engineering degree from Universidad the Chile in 1999 and a Ph.D. in Operations Research from MIT in 2004. His research, focusing on 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 award, a Tucker prize finalist, and research awards from Amazon and Google. Jos´e has given keynote talks at several institutions and conferences and has been on the program committee of international computer science conferences. He also serves and has served on the editorial board of some of the leading journals in his field: Mathematical Programming B, Mathematics of Operations Research (as Game Theory Area Editor), and Operations Research.

Social influence is largely recognized as a key factor in opinion formation processes. Recently, the role of external forces in inducing opinion displacement and polarization in social networks has attracted significant attention.
This is in particular motivated by the necessity to understand and possibly prevent interference phenomena during political campaigns and elections. In this paper, we formulate and solve a targeted intervention problem for opinion displacement minimization on a social network. Specifically, we consider a min-max problem whereby a social planner (the defender) aims at selecting the optimal network intervention within her given budget constraint in order to minimize the opinion displacement in the system that an adversary (the attacker) is instead trying to maximize. Our results show that the optimal intervention of the defender has two regimes. For large enough budget, the optimal intervention of the social planner acts on all nodes proportionally to a new notion of network centrality. For lower budget values, such optimal intervention has a more delicate structure and is rather concentrated on a few target individuals.

I will illustrate the role of mixed strategies in some stochastic games of optimal stopping (Dynkin games). In particular, I will present a detailed solution to a nonzero-sum game of investment with uncertain competition. Two agents are interested in the same investment opportunity whose value depends on the dynamics of an underlying stochastic process. Neither of the two players reveals publicly their interest, so that they are both uncertain about the existence of a competitor. Each agent can choose a stopping time at which they enter the investment but only the first one to invest will obtain a positive payoff. The equilibrium is trivial if players only use pure strategies and their payoff is zero. In mixed strategies instead we obtain a much richer structure of the equilibrium.

Bio: Tiziano De Angelis is Associate Professor in Probability and Mathematical Statistics in the School of Management and Economics, Universit`a di Torino, and Affiliate of Collegio Carlo Alberto. He obtained his PhD in Mathematics for Economic-Financial Applications from La Sapienza, Universit`a di Roma, in 2012. Then he moved to the School of Mathematics of the University of Manchester, form 2012 to 2015, and to the School of Mathematics of the University of Leeds, from 2015 to 2020. His research interests span optimal stopping, singular stochastic control, free-boundary problems, stochastic games and mathematical finance.

We consider a society where voters’ preferences over candidates are one-dimensional, i.e., single-peaked. We would like to sample voters’ preferences to uniquely identify the underlying axis. We give bounds on the number of samples required, both for thecase where we can sample entire votes and for the case where we only have access topairwise comparisons, for two natural distributions of voters’ preferences. We also analyse a more general setting where voters’ preferences may be single-peaked with respect to one of two axes, and one or both of these axes are unknown.

Joint work with Sonja Kraiczy

Bio: Edith Elkind is a Professor of Computer Science at University of Oxford. She obtained her PhD from Princeton in 2005, and has worked in the UK, Israel, and Singapore before joining Oxford in 2013. She works in algorithmic game theory, with a focus on algorithms for collective decision making and coalition formation. Edith has published over 100 papers in leading AI conferences and journals, and has served as a program chair of WINE, AAMAS, ACM EC and COMSOC; she is currently serving as a program chair of IJCAI’23.

Up until recently, Algorithmic Game Theory has mainly focused on the design of mechanisms that incentivize agents to truthfully report their private preferences. However, algorithms and incentives interact in many additional ways; the design of contracts being a prime example. While mechanism design deals with hidden preferences, contract design deals with hidden actions, and studies how best to incentivize agents to take costly actions, when their actions are hidden from the principal. With the transition of classic applications of contracts into computational platforms, algorithm design for such applications becomes timely and relevant. In this talk, I will survey two papers on combinatorial contracts, which highlight different sources of complexity that arise in contract design. Based on joint work with Tomer Ezra, Paul Duetting and Thomas Kesselheim.

Bio: Michal Feldman is the Computation and Economics Professor of Computer Science in the Blavatnik School of Computer Science at Tel Aviv University and a visiting scholar at Microsoft Research Israel. Her research lies in the border of computer science, game theory and economics. She studies the design and analysis of algorithms, auctions, markets, contracts and networks, under different types of uncertainty, with an emphasis on efficiency, simplicity, robustness and fairness. She received her P.h.D. from the University of California at Berkeley in 2005. She held a visiting position at Harvard University and Microsoft Research New England (2011-13). She is an Associate Editor in Games and Economic Behavior, Mathematics of Operations Research, ACM Transactions on Economics and Computation, and Journal of Computer and System Sciences. She served as Vice Chair of ACM SIGecom, and PC chair of ACM EC 2015, and WINE 2021. She is an alumna of the Global Young Academy, and the Israeli Young Academy. She is the recipient of the Kadar award, two ERC grants of the European Research Council, Marie Curie IOF, Alon, ISF and Amazon Research Award. She was listed in Forbes’ list of the 50 most influential women in Israel (2016). For more information, see https://www.mfeldman.sites.tau.ac.il/

This talk will discuss how refinements of Nash equilibrium can be derived from models where players don’t know their opponents’ strategies and learn them from repeated observations.

Bio: Drew Fudenberg is the Paul A. Samuelson Professor of Economics at MIT. He received an A.B. in applied mathematics from Harvard College in 1978, and a Ph.D. in economics from MIT in 1981. He is a Fellow of the Econometric Society and was its President in 2017. He is a member of both the National Academy of Sciences and the American Academy of Arts and Sciences, and has received fellowships from the Guggenheim Foundation and the Alfred P. Sloan Foundation. Fudenberg’s work on game theory ranges from foundational work on learning and equilibrium to the analysis of repeated games and reputation effects to the study of particular games, competition between firms, and other topics in theoretical industrial organization. More recently he has worked on topics in behavioral economics and decision theory such as self-control and stochastic choice.

In adversarial team games, a team of players sequentially faces a team of adversaries. These games are the simplest setting with multiple players where cooperation and competition coexist, and it is known that the information asymmetry among the team members makes equilibrium approximation computationally hard. Although much effort has been spent designing scalable algorithms, the problem of solving large game instances is open. This work shows that we can recover from this weakness by bridging the gap between sequential adversarial team games and 2-player games. In particular, we propose a new, suitable game representation that we call team public information, in which a team is represented as a single coordinator who only knows information common to the whole team and prescribes to each member an action for any possible private state. The resulting representation is highly explainable, being a 2-player tree in which the team’s strategies are behavioral with a direct interpretation and more expressive than the original extensive form when designing abstractions. Furthermore, we prove the payoff equivalence of our representation, and we provide techniques that, starting directly from the extensive form, generate dramatically more compact representations without information loss. Finally, we experimentally evaluate our techniques when applied to a standard testbed, comparing their performance with the current state of the art.

Bio: Nicola Gatti is an associate professor of Computer Science and Engineering in the Department of Electronics, Information, and Bioengineering at Politecnico di Milano. His main achievements come from algorithmic game theory, allocation problems and incentives, algorithmic social choice theory, multiagent learning, and online learning. He received several awards, including the 2011 AIxIA Marco Somalvico Award as the best Italian young researcher in AI, the best paper award in several conferences, including the prestigious NeurIPS 2020 and Cooperative AI 2021 funded by Google Deepmind. In 2021 he was elected as a EurAi Fellow (top <3% of the European AI scientists) and awarded at IJCAI 2022, and he is also AIAA Fellow since 2022. He is one of the ten spoke coordinators of the PNRR-PE project (FAIR) on AI.

We study a dynamic traffic assignment model, where agents base their instantaneous routing decisions on real-time delay predictions. We formulate a mathematically concise model and derive properties of the predictors that ensure a dynamic prediction equilibrium exists. We demonstrate the versatility of our framework by showing that it subsumes the well-known full information and instantaneous information models, in addition to admitting further realistic predictors as special cases. We complement our theoretical analysis by an experimental study, in which we systematically compare the induced average travel times of different predictors, including a machine-learning model trained on data gained from previously computed equilibrium flows, both on a synthetic and a real road network.

Bio: Tobias Harks is Professor for Mathematical Optimization at the University of Passau, Germany. He held previous positions at the University of Augsburg and Maastricht University. His research interests include discrete and continuous optimization, algorithmic game theory, bilevel optimzation and the theory of dynamic equilibrium flows.

We consider sender-receiver games, where the sender and the receiver are two distant nodes on a communication network. We show that if the network has two disjoint paths of communication between the sender and the receiver, then we can replicate not only all equilibrium outcomes of the direct communication game (i.e., when the sender and the receiver communicate directly with each other), but also of the mediated game (i.e., when the sender and the receiver communicate with the help of a mediator).

Joint with L. Renou and X. Venel

Bio: Marie Laclau is a CNRS researcher and associate professor at HEC. She earns a PhD from HEC in 2012, and then conducted post-doctoral research and taught at Yale University (Cowles Foundation) before joining Paris School of Economics then HEC. Her research interests are about game theory, and more particularly about the strategic use of information and communication, repeated games and networks.

We undertake a fundamental study of network equilibria modeled as solutions of fixed-point equations for monotone linear functions with saturation nonlinearities. The considered model extends one originally proposed to study systemic risk in networks of financial institutions interconnected by mutual obligations. It is one of the simplest continuous models accounting for shock propagation phenomena and cascading failure effects. This model also characterizes Nash equilibria of constrained quadratic network games with strategic complementarities. We first derive explicit expressions for network equilibria and prove necessary and sufficient conditions for their uniqueness, encompassing and generalizing results available in the literature. Then, we study jump discontinuities of the network equilibria when the exogenous flows cross certain regions of measure 0 representable as graphs of continuous functions. Finally, we discuss some implications of our results in the two main motivating applications. In financial networks, this bifurcation phenomenon is responsible for how small shocks in the assets of a few nodes can trigger major aggregate losses to the system and cause the default of several agents. In constrained quadratic network games, it induces a blow-up behavior of the sensitivity of Nash equilibria with respect to the individual benefits.

Does learning from empirical observations converge to a Nash equilibrium in a game-theoretic setting? If yes, at what rate? And, if not, what are the possible limiting behaviors that emerge otherwise? A series of well-known impossibility results preclude the possibility of a ”universally positive” answer to the first question - i.e., the existence a dynamical process which, based on player-specific information alone, converges to Nash equilibrium in all games. In view of this, we will instead examine the convergence properties of a class of widely used online learning algorithms which includes the exponential weights algorithm, its bandit/optimistic variants, and many others. In this general context, we establish a comprehensive equivalence between the stability of a Nash equilibrium and its support: a Nash equilibrium is stable and attracting if and only if it is strict (i.e., each equilibrium strategy has a unique best response). We will also discuss the robustness of this equivalence to different feedback models - from full information to bandit, payoff-based feedback - as well as the methods’ rate of convergence, and what other limiting behaviors may arise in the long run.

Bio: Panayotis Mertikopoulos is a principal researcher at the French National Center for Scientific Research (CNRS). After graduating valedictorian from the University of Athens in 2003, he received his MSc and MPhil degrees in mathematics in 2005 from Brown University, and his PhD degree from the University of Athens in 2010. He then spent one year as a post-doctoral fellow at École Polytechnique in Paris before joining CNRS in 2011. Since 2011, he has held visiting or part-time positions at UC Berkeley, EPFL and, more recently, Criteo AI Lab. His research interests span the interface of game theory, learning and optimization, with a special view towards their applications to machine learning, operations research, and network theory. He is especially interested in the long-run behavior of multi-agent learning and optimization algorithms and dynamics – whether they converge, at what speed, and/or what type of non-stationary, off-equilibrium behaviors may arise when they do not.In 2020, he was one of the two finalists for the m´edaille de bronze of the CNRS in computer science. His distinctions otherwise include several spotlights in the NeurIPS, ICML and ICLR), and the best paper award at the 2012 IEEE International Conference on Networks, Control and Optimization.

Congestion games are a prototypical class of games used to model resource allocation problems subject to congestion, with applications spanning transportation, telecommunications, scheduling, and many other disciplines. In this context, a significant bulk of the literature has focused on assessing to what extent equilibria (e.g., Nash equilibria) incur near optimal social cost. Motivated by fleet management in autonomous mobility, in this work we take an opposite view on congestion games, and ask the following question: how good of an approximation can we find to the minimum social cost problem? During the talk, I will present a comprehensive set of results providing tight hardness results and a polynomial time algorithm with optimal approximation. Interestingly, such algorithm is based on the utilization of carefully designed taxes, thus showing that self-interested decision makers can be incentivized to settle on an allocation with as good performance as that achievable with complete control. Finally, I will show that, although worst-case, the approximation factors obtained are near optimal (i.e., close to one) for many real-world instances of interest.

Joint work with: Martin Gairing (University of Liverpool)

Bio: Dario Paccagnan is an Assistant Professor at the Department of Computing, Imperial College London since the Fall 2020. Before that, he was a postdoctoral fellow with the Center for Control, Dynamical Systems and Computation, University of California, Santa Barbara. He obtained his PhD from the Automatic Control Laboratory, ETH Zurich, Switzerland, in 2018. He received a B.Sc. and M.Sc. in Aerospace Engineering from the University of Padova, Italy, in 2011 and 2014, and a M.Sc. in Mathematical Modelling and Computation from the Technical University of Denmark in 2014; all with Honors. Dario’s interests are at the interface of game theory and control theory, with a focus on the design of behavior-influencing mechanisms for socio-technical systems. Dario was a finalist for the 2019 EECI best PhD thesis award and was recognized with the SNSF Early Postdoc Mobility Fellowship, the SNSF Doc Mobility Fellowship, and the ETH medal for his doctoral work.

References: EC 2021 https://dl.acm.org/doi/10.1145/3465456.3467601, ArXiv https://arxiv.org/abs/2105.07480

Bayesian information design is a compelling framework for generating persuasive recommendations. Feasibility of a recommendation policy is often characterized by the “obedience constraint” according to which following recommendation is, in a posteriori expectation, no worse than any other action. The probabilistic recommendation policy has continuous support for non-atomic games. This makes it computationally challenging to handle the obedience constraint for optimal design, and further questions the practical validity of Bayesian computation in decisionmaking for non-atomic setting. We address these issues in the context of routing games. For polynomial link latency functions, we provide an exact finite-dimensional formulation of the obedience constraint. We also study a repeated setting, in which the likelihood of an agent following a recommendation in a stage is proportional to the population-wide average regret from previous stages, e.g., provided by a review aggregator platform. We present results from a human subject experiment on validity of this “learning model” and establish its convergence to Bayes correlated equilibrium under obedient recommendation policy.

Bio: Ketan Savla is an associate professor and the John and Dorothy Shea Early Career Chair in Civil Engineering at the University of Southern California. His current research interest is in distributed optimal and robust control, dynamical networks, state-dependent queuing systems, and mechanism design, with applications in civil infrastructure systems. His recognitions include NSF CAREER, George S. Axelby Outstanding Paper Award, and the Donald P. Eckman Award. He serve(d) as an associate editor of the IEEE Transactions on Control of Network Systems, IEEE Control Systems Letters, and IEEE Transactions on Intelligent Transportation Systems. He is also a co-founder and the chief science officer of Xtelligent, Inc.

We consider finite two-player normal form games with random payoffs. Player A’s payoffs are i.i.d. from a uniform distribution. Given p in [0, 1], for any action profile, player B’s payoff coincides with player A’s payoff with probability p and is i.i.d. from the same uniform distribution with probability 1-p. This model interpolates the model of i.i.d. random payoff used in most of the literature and the model of random potential games. First we study the number of pure Nash equilibria in the above class of games. Then we show that, for any positive p, asymptotically in the number of available actions, best response dynamics reaches a pure Nash equilibrium with high probability.

Bio: Marco Scarsini is a Professor in the Department of Economics and Finance at LUISS, Rome, Italy. He obtained his Laurea in Economics and Social Sciences at Universita Bocconi and his HDR in Applied ‘ Mathematics and Applications of Mathematics at Universite Paris Dauphine. He had previous appointments in various universities. He has written over one hundred papers and serves on the editorial board of several scientific journals. His main research areas are applied probability and game theory, with a particular focus on congestion games and social learning.

Over the last two decades we have developed good understanding how to quantify the impact of strategic user behavior on outcomes in many games (including traffic routing and online auctions) and showed that the resulting bounds extend to repeated games assuming players use a form of no-regret learning to adapt to the environment. Unfortunately, these results do not apply when outcomes in one round effect the game in the future, as is the case in many applications. In this talk, we study this phenomenon in the context of a game modeling queuing systems: routers compete for servers, where packets that do not get served need to be resent, resulting in a system where the number of packets at each round depends on the success of the routers in the previous rounds. In joint work with Jason Gaitonde, we analyze the resulting highly dependent random process. We find that if the capacity of the servers is high enough to allow a centralized and knowledgeable scheduler to get all packets served even with double the packet arrival rate, then despite selfish behavior of the queues, the expected number of packets in the queues will remain bounded throughout time, assuming older packets have priority. Further, if queues are more patient in evaluating their outcomes , maximizing their long-run success rate, stability can be ensured with just 1.58 times extra capacity, strictly better than what is possible assuming the no-regret property.

Bio: Éva Tardos is a Jacob Gould Schurman Professor of Computer Science, currently chair of the Department of Computer Science for a second term after being chair 2006-2010. She was Interim Dean for Computing and Information Sciences 2012-2013 and more recently was Associate Dean for Diversity & Inclusion at Cornell University. She received her BA and PhD from Eötvös University in Budapest. She joined the faculty at Cornell in 1989. Tardos’s research interest is algorithms and interface of algorithms and incentives. She is most known for her work on quantifying the efficiency of selfish routing. She has been elected to the National Academy of Engineering, the National Academy of Sciences, the American Philosophical Society, the American Academy of Arts and Sciences, and to the Hungarian Academy of Sciences. She is the recipient of a number of fellowships and awards including the Packard Fellowship, the Gödel Prize, Dantzig Prize, Fulkerson Prize, ETACS prize, and the IEEE von Neumann Medal. She co-wrote the widely used textbook Algorithms Design. She has been editor-in-Chief of the Journal of the ACM and of the SIAM Journal of Computing, and editor of several other journals, and was program committee member and chair for several conferences in her area.

We model a system made of n asymmetric firms participating in a market in which each firm chooses as its strategy a supply function relating its quantity to its price.
Such strategy (Supply function equilibrium) is a generalization of models where firms can either set a fixed quantity (Cournot model) or set a fixed price (Bertrand model).
Our goal is to study the pay-as-bid auction in this setting. Under the assumption of K-Lipschitz supply functions, we were capable of determining existence and characterization of Nash equilibria of the game.