Equilibrium problems in Bayesian auction games can be described as systems of differential equations. Depending on the model assumptions, these equations might be such that we do not have a rigorous mathematical solution theory. The lack of analytical or numerical techniques with guaranteed convergence for the equilibrium problem has plagued the field and limited equilibrium analysis to rather simple auction models such as single-object auctions. Recent advances in equilibrium learning led to algorithms that find equilibrium under a wide variety of model assumptions. Monotonicity and the Minty condition are the known sufficient conditions for learning algorithms to converge to an equilibrium in games. Not much is known about convergence of learning algorithms beyond these conditions. We analyze first- and second-price auctions where simple learning algorithms consistently converge to an equilibrium. The analysis is challenging, because these properties need to be shown in infinite dimensions. Interestingly, we show that neither monotonicity nor pseudo- or quasi-monotonicity holds for the respective variational inequalities (VIs). The second-price auction's equilibrium is a Minty-type solution, but the first-price auction is not. However, the analysis via infinite-dimensional VIs allows us to get ex-post guarantees for gradient-based algorithms. We show that the Bayes--Nash equilibrium is the unique solution to the VI within the class of uniformly increasing bid functions, which ensures that gradient-based algorithms attain the equilibrium in case of convergence, as also observed in numerical experiments.

We consider the problem of quantifying the amount of influence one agent can exert on another in the setting of multi-agent reinforcement learning (MARL). As a step towards a unified approach to express agents’ interdependencies, we introduce the total and state influence measurement functions. Both of these are valid for all common MARL systems, such as the discounted reward setting. Additionally, we propose novel quantities, called the total impact measurement (TIM) and state impact measurement (SIM), that characterize one agent’s influence on another by the maximum impact it can have on the other agents’ expected returns and represent instances of impact measurement functions in the average reward setting. Furthermore, we provide approximation algorithms for TIM and SIM with simultaneously learning approximations of agents’ expected returns, error bounds, stability analyses under changes of the policies, and convergence guarantees. The approximation algorithm relies only on observing other agents’ actions and is, other than that, fully decentralized. Through empirical studies, we validate our approach’s effectiveness in identifying intricate influence structures in complex interactions. Our work appears to be the first study of determining influence structures in the multi-agent average reward setting with convergence guarantees.

Game theory relies heavily on the availability of cardinal utility functions, but in fields such as matching markets, only ordinal preferences are typically elicited. The literature focuses on mechanisms with simple dominant strategies, but many real-world applications lack dominant strategies, making the intensity of preferences between outcomes important for determining strategies. Even though precise information about cardinal utilities is not available, some data about the likelihood of utility functions is often accessible. We propose to use Bayesian games to formalize uncertainty about the decision-makers' utilities by viewing them as a collection of normal-form games. Instead of searching for the Bayes-Nash equilibrium, we study how uncertainty in utilities is reflected in uncertainty of strategic play. To do this, we introduce a novel solution concept called α-Rank-collections, which extends α-Rank to Bayesian games. This allows us to analyze strategic play in, for example, non-strategyproof matching markets, for which appropriate solution concepts are currently lacking. α-Rank-collections characterize the expected probability of encountering a certain strategy profile under replicator dynamics in the long run, rather than predicting a specific equilibrium strategy profile. We experimentally evaluate α-Rank-collections using instances of the Boston mechanism, finding that our solution concept provides more nuanced predictions compared to Bayes-Nash equilibria. Additionally, we prove that α-Rank-collections are invariant to positive affine transformations, a standard property for a solution concept, and are efficient to approximate. By extending the α-Rank framework to account for Bayesian games, we provide a robust tool for analyzing strategic interactions in environments where uncertainty in preferences plays a critical role. This method offers a significant improvement in understanding and predicting strategic behaviors in various applications beyond matching markets, highlighting the versatility and efficiency of α-Rank-collections. Our approach opens new avenues for exploring complex strategic scenarios and provides a comprehensive framework for future research in game theory and economic computation. The full version of the paper can be found here https://arxiv.org/abs/2211.10317.

Understanding and analyzing markets is crucial, yet analytical equilibrium solutions remain largely infeasible. Recent breakthroughs in equilibrium computation rely on zeroth-order policy gradient estimation. These approaches commonly suffer from high variance and are computationally expensive. The use of fully differentiable simulators would enable more efficient gradient estimation. However, the discrete allocation of goods in economic simulations is a non-differentiable operation. This renders the first-order Monte Carlo gradient estimator inapplicable and the learning feedback systematically misleading. We propose a novel smoothing technique that creates a surrogate market game, in which first-order methods can be applied. We provide theoretical bounds on the resulting bias which justifies solving the smoothed game instead. These bounds also allow choosing the smoothing strength a priori such that the resulting estimate has low variance. Furthermore, we validate our approach via numerous empirical experiments. Our method theoretically and empirically outperforms zeroth-order methods in approximation quality and computational efficiency.