The existence of simple uncoupled no-regret learning dynamics that converge to correlated equilibria in normal-form games is a celebrated result in the theory of multi-agent systems. Specifically, it has been known for more than 20 years that when all players seek to minimize their internal regret in a repeated normal-form game, the empirical frequency of play converges to a normal-form correlated equilibrium. Extensive-form (that is, tree-form) games generalize normal-form games by modeling both sequential and simultaneous moves, as well as imperfect information. Because of the sequential nature and presence of private information in the game, correlation in extensive-form games possesses significantly different properties than in normal-form games, many of which are still open research directions. Extensive-form correlated equilibrium (EFCE) has been proposed as the natural extensive-form counterpart to the classical notion of correlated equilibrium in normal-form games. Compared to the latter, the constraints that define the set of EFCEs are significantly more complex, as the correlation device (a.k.a. mediator) must take into account the evolution of beliefs of each player as they make observations throughout the game. Due to that significant added complexity, the existence of uncoupled learning dynamics leading to an EFCE has remained a challenging open research question for a long time. In this article, we settle that question by giving the first uncoupled no-regret dynamics that converge to the set of EFCEs in n -player general-sum extensive-form games with perfect recall. We show that each iterate can be computed in time polynomial in the size of the game tree, and that, when all players play repeatedly according to our learning dynamics, the empirical frequency of play after T game repetitions is proven to be a \( O(1/\sqrt {T}) \) -approximate EFCE with high probability, and an EFCE almost surely in the limit.

The search problem of computing aStackelberg(orleader-follower)equilibrium(also referred to as anoptimal strategy to commit to) has been widely investigated in the scientific literature in, almost exclusively, the single-follower setting. Although theoptimisticandpessimisticversions of the problem, i.e., those where the single follower breaks any ties among multiple equilibria either in favour or against the leader, are solved with different methodologies, both cases allow for efficient, polynomial-time algorithms based on linear programming. The situation is different with multiple followers, where results are only sporadic and depend strictly on the nature of the followers’ game. In this paper, we investigate the setting of a normal-form game with a single leader and multiple followers who, after observing the leader’s commitment, play a Nash equilibrium. When both leader and followers are allowed to play mixed strategies, the corresponding search problem, both in the optimistic and pessimistic versions, is known to be inapproximable in polynomial time to within any multiplicative polynomial factor unless $$\textsf {P}=\textsf {NP}$$P=NP . Exact algorithms are known only for the optimistic case. We focus on the case where the followers play pure strategies—a restriction that applies to a number of real-world scenarios and which, in principle, makes the problem easier—under the assumption of pessimism (the optimistic version of the problem can be straightforwardly solved in polynomial time). After casting this search problem (with followers playing pure strategies) as apessimistic bilevel programming problem, we show that, with two followers, the problem is -hard and, with three or more followers, it cannot be approximated in polynomial time to within any multiplicative factor which is polynomial in the size of the normal-form game, nor, assuming utilities in [0, 1], to within any constant additive loss stricly smaller than 1 unless $$\textsf {P}=\textsf {NP}$$P=NP . This shows that, differently from what happens in the optimistic version, hardness and inapproximability in the pessimistic problem are not due to the adoption of mixed strategies. We then show that the problem admits, in the general case, a supremum but not a maximum, and we propose a single-level mathematical programming reformulation which asks for the maximization of a nonconcave quadratic function over an unbounded nonconvex feasible region defined by linear and quadratic constraints. Since, due to admitting a supremum but not a maximum, only a restricted version of this formulation can be solved to optimality with state-of-the-art methods, we propose an exactad hocalgorithm (which we also embed within a branch-and-bound scheme) capable of computing the supremum of the problem and, for cases where there is no leader’s strategy where such value is attained, also an $$\alpha $$α -approximate strategy where $$\alpha > 0$$α>0 is an arbitrary additive loss (at most as large as the supremum). We conclude the paper by evaluating the scalability of our algorithms via computational experiments on a well-established testbed of game instances.

The concept of leader-follower (or Stackelberg) equilibrium plays a central role in a number of real-world applications bordering on mathematical optimization and game theory. While the single-follower case has been investigated since the inception of bilevel programming with the seminal work of von Stackelberg, results for the case with multiple followers are only sporadic and not many computationally affordable methods are available. In this work, we consider Stackelberg games with two or more followers who play a (pure or mixed) Nash equilibrium once the leader has committed to a (pure or mixed) strategy, focusing on normal-form and polymatrix games. As customary in bilevel programming, we address the two extreme cases where, if the leader’s commitment originates more Nash equilibria in the followers’ game, one which either maximizes (optimistic case) or minimizes (pessimistic case) the leader’s utility is selected. First, we show that, in both cases and when assuming mixed strategies, the optimization problem associated with the search problem of finding a Stackelberg equilibrium is \(\mathcal {NP}\)-hard and not in Poly-\(\mathcal {APX}\) unless \(\mathcal {P} = \mathcal {NP}\). We then consider different situations based on whether the leader or the followers can play mixed strategies or are restricted to pure strategies only, proposing exact nonconvex mathematical programming formulations for the optimistic case for normal-form and polymatrix games. For the pessimistic problem, which cannot be tackled with a (single-level) mathematical programming formulation, we propose a heuristic black-box algorithm. All the methods and formulations that we propose are thoroughly evaluated computationally.

We study hidden-action principal-agent problems with multiple agents. These are problems in which a principal commits to an outcome-dependent payment scheme (called contract) in order to incentivize some agents to take costly, unobservable actions that lead to favorable outcomes. Previous works study models where the principal observes a single outcome determined by the actions of all the agents. This considerably limits the contracting power of the principal, since payments can only depend on the joint result achieved by the agents. In this paper, we consider a model in which each agent determines their own individual outcome as an effect of their action only, the principal observes all the individual outcomes separately, and they perceive a reward that jointly depends on all these outcomes. This considerably enhances the principal's contracting capabilities, by allowing them to pay each agent on the basis of their individual result. We analyze the computational complexity of finding principal-optimal contracts, revolving around two properties of principal's rewards, namely IR-supermodularity and DR-submodularity. The former captures settings with increasing returns, where the rewards grow faster as the agents' effort increases, while the latter models the case of diminishing returns, in which rewards grow slower instead. These naturally model diseconomies and economies of scale. We first address basic instances in which the principal knows everything about the agents, and, then, more general Bayesian instances where each agent has their own private type determining their features, such as action costs and how actions stochastically determine individual outcomes. As a preliminary result, we show that finding an optimal contract in a non-Bayesian instance can be reduced in polynomial time to a maximization problem over a matroid having a particular structure. This is needed to prove our main positive results in the rest of the paper. We start by analyzing non-Bayesian instances, where we first prove that the problem of computing a principal-optimal contract is inapproximable with either IR-supermodular or DR-submodular rewards. Nevertheless, we show that in the former case the problem becomes polynomial-time solvable under some mild regularity assumptions, while in the latter case it admits a polynomial-time (1 − 1/e)-approximation algorithm. In conclusion, we extend our positive results to Bayesian instances. First, we show that the principal's optimization problem can be approximately solved by means of a linear formulation. This is non-trivial since in general the problem may not admit a maximum, but only a supremum. Then, by working on such a linear formulation, we provide algorithms based on the ellipsoid method that (almost) match the guarantees obtained for non-Bayesian instances.

Equilibrium refinements are important in extensive-form (i.e., tree-form) games, where they amend weaknesses of the Nash equilibrium concept by requiring sequential rationality and other beneficial properties. One of the most attractive refinement concepts is quasi-perfect equilibrium. While quasiperfection has been studied in extensive-form games, it is poorly understood in Stackelberg settings—that is, settings where a leader can commit to a strategy—which are important for modeling, for example, security games. In this paper, we introduce the axiomatic definition of quasi-perfect Stackelberg equilibrium. We develop a broad class of game perturbation schemes that lead to them in the limit. Our class of perturbation schemes strictly generalizes prior perturbation schemes introduced for the computation of (non-Stackelberg) quasi-perfect equilibria. Based on our perturbation schemes, we develop a branch-and-bound algorithm for computing a quasi-perfect Stackelberg equilibrium. It leverages a perturbed variant of the linear program for computing a Stackelberg extensive-form correlated equilibrium. Experiments show that our algorithm can be used to find an approximate quasi-perfect Stackelberg equilibrium in games with thousands of nodes.