Learning Payoff Functions in Infinite Games

1 Introduction

Game-theoretic analysis typically begins with a complete description of strategic interactions, that is, the game. We consider the prior question of determining what the game actually is, given a database of game experience rather than any direct speci�cation. This is one possible target of learning applied to games [Shoham et al., 2003]. When agents have few available actions and outcomes are deterministic, the game can be identi�ed through systematic exploration. For instance, we can ask the agents to play each strategy pro�le in the entire joint strategy set and record the payoffs for each. If the joint action space is small enough, limited nondeterminism can be handled by sampling. Coordinating exploration of the joint set does pose dif�cult issues. Brafman and Tennenholtz, for example, address these carefully for the case of commoninterest stochastic games [Brafman and Tennenholtz, 2003], as well as the general problem of maintaining an equilibrium among learning algorithms [Brafman and Tennenholtz, 2004].

Further dif�culties are posed by intractably large (or in�- nite) strategy sets. We can make this problem tractable by reducing the number of pro�les that agents are allowed to play, but this comes at the cost of transforming the game of interest into a different game entirely. Instead, we seek to identify the full game (or at least a less restrictive game) from limited data, entailing some generalization from observed instances. Approximating payoff functions using supervised learning (regression) methods allows us to deal with continuous agent strategy sets, providing a payoff for an arbitrary strategy pro�le. In so doing, we adopt functional forms consistent with prior knowledge about the game, and also admit biases toward forms facilitating subsequent game analysis (e.g., equilibrium calculation).

In this paper, we present our �rst investigation of approximating payoff functions, employing regression to low-degree polynomials. We explore two example games, both with incomplete information and real-valued actions. First is the standard �rst-price sealed bid auction, with two players and symmetric value distributions. The solution to this game is well-known [Krishna, 2002], and its availability in analytical form proves useful for benchmarking our learning approach. Our second example is a �ve-player market-based scheduling game [Reeves et al., 2005], where time slots are allocated by simultaneous ascending auctions [Milgrom, 2000]. This game has no known solution, though previous work has identi�ed equilibria on discretized subsets of the strategy space.

2 Preliminaries

2.1 Notation

A generic normal form game is formally expressed as [I, {∆(Si)}, {ui(s)}], where I refers to the set of players and m = |I| is the number of players. Si is the set of strategies available to player i ∈ I, and the set ∆(Si) is the simplex of mixed strategies over Si. Finally, ui(s) : S1×· · ·×Sm →R is the payoff function of player i when all players jointly play s = (s1, . . . , sm), with each sj ∈ Sj. As is common, we assume von Neumann-Morgenstern utility, allowing an agent i's payoff for a particular mixed strategy pro�le to be ui(σ) = ∑s∈S [σ1(s1) · · · σm(sm)]ui(s), where σj : Sj → [0, 1] is a mixed strategy of player i, assigning a probability to each pure strategy sj ∈ Sj such that all probabilities over the agent's strategy set add to 1 (i.e., σj ∈ ∆(Sj)).

It will often be convenient to refer to the strategy (pure or mixed) of player i separately from that of the remaining players. To accommodate this, we use s-i to denote the joint strategy of all players other than player i.

2.2 Nash Equilibrium

In this paper, we are concerned with one-shot normal-form games, in which players make decisions simultaneously and accrue payoffs, upon which the game ends. This single-shot nature may seem to preclude learning from experience, but in fact repeated episodes are allowed, as long as actions cannot affect future opportunities, or condition future strategies. Game payoff data may also be obtained from observations of other agents playing the game, or from simulations of hypothetical runs of the game. In any of these cases, learning is relevant despite the fact that the game is to be played only once.

Faced with a one-shot game, an agent would ideally play its best strategy given those played by the other agents. A con�guration where all agents play strategies that are best responses to the others constitutes a Nash equilibrium.

De�nition 1 A strategy pro�le s = (s1, . . . , sm) constitutes a (pure-strategy) Nash equilibrium of game [I , {Si}, {ui(s)}] if for every i ∈ I, s′i ∈ Si, ui(si, s-i) ≥ ui(s′i , s-i).

A similar de�nition applies when mixed strategies are allowed.

De�nition 2 A strategy pro�le σ = (σ1, . . . , σm) constitutes a mixed-strategy Nash equilibrium of game [I, {∆(Si)}, {ui(s)}] if for every i ∈ I, σ′i ∈ ∆(Si), ui(σi , σ-i) ≥ ui(σ′i , σ-i).

In this study we devote particular attention to games that exhibit symmetry with respect to payoffs.

De�nition 3 A game [I, {∆(Si)}, {ui(s)}] is symmetric if ∀i, j ∈ I, (a) Si = Sj and (b) ui(si, s-i) = uj(sj, s-j) whenever si = sj and s-i = s-j

Symmetric games have relatively compact descriptions and may present associated computational advantages. Given a symmetric game, we may focus on the subclass of symmetric equilibria, which are arguably most natural [Kreps, 1990], and avoid the need to coordinate on roles. In fairly general settings, symmetric games do possess symmetric equilibria [Nash, 1951].

3 Payoff Function Approximation

3.1 ProblemDe�nition

We are given a set of data points (s, v), each describing an instance where agents played strategy pro�le s and realized value v = (v1, . . . , vm). For deterministic games of complete information, v is simply u. With incomplete information or stochastic outcomes, v is a random variable, more speci�cally an independent draw from a distribution function of s, with expected value u(s).

The payoff function approximation task is to select a function ˆu from a candidate set U minimizing some measure of deviation from the true payoff function u. Because the true function u is unknown, of course, we must base our selection on evidence provided by the given data points.

Our goal in approximating payoff functions is typically not predicting payoffs themselves, but rather in assessing strategic behavior. Therefore, for assessing our results, we measure approximation quality not directly in terms of a distance between ˆ u and u, but rather in terms of the strategies dictated by ˆ u evaluated with respect to u. For this we appeal to the notion of approximate Nash equilibrium.

De�nition 4 A strategy pro�le σ = (σ1, . . . , σm) constitutes an ϵ-Nash equilibrium of game [I, {∆(Si)}, {ui(s)}] if for every i ∈ I, σ′i ∈ ∆(Si), ui(σi, σ-i) + ϵ ≥ ui(σ′i , σ-i).

Since in general u will either be unknown or not amenable to this analysis, we developed a method for estimating ϵ from data. We will describe it in some detail below.

We propose using ϵ in the above de�nition as a measure of approximation error of ˆ u, and employ it in evaluating our learning methods. When u is known, we can compute ϵ in a straightforward manner. Let s∗i denote i's bestresponse correspondence, de�ned by s∗i (σ-i) = {x : x ∈ argmaxsi ui(si, σ-i)}. For clarity of exposition, we take s∗i (σ-i) to be single-valued. Let ˆσ be a solution (e.g., a Nash equilibrium) of game [I, {∆(Si)}, {ˆui(s)}]. Then ˆ σ is an ϵNash equilibrium of the true game [I, {∆(Si)}, {ui(s)}], for ϵ =maxi∈I [ui(s∗i (ˆσ-i), ˆ σ-i) - ui(ˆσi, ˆ σ-i)] .

For the remainder of this report, we focus on a special case of the general problem, where action sets are real-valued intervals, Si = [0, 1]. Moreover, we restrict attention to symmetric games and further limit the number of variables in payoff-function hypotheses by using some form of aggregation of other agents' actions. 1 The assumption of symmetry allows us to adopt the convention for the remainder of the paper that payoff u(si, s-i) is to the agent playing si.

3.2 Polynomial Regression

One class of models we consider are the nth-degree separable polynomials:

where φ(s-i) represents some aggregation of the strategies played by agents other than i. For two-player games, φ is simply the identity function. We refer to polynomials of the form (1) as separable, since they lack terms combining si and s-i. We also consider models with such terms, for example, the non-separable quadratic:

Note that (2) and (1) coincide in the case n = 2 and c = 0. In the experiments described below, we employ a simpler version of non-separable quadratic that takes b1 = b2 = 0.

One advantage of the quadratic form is that we can analytically solve for Nash equilibrium. Given a general nonseparable quadratic (2), the necessary �rst-order condition for an interior solution is si = -(a1 + cφ(s-i))/2a2. This reduces to si = -a1/2a2 in the separable case. For the non-separable case with additive aggregation, φsum(s-i) =

1 Although none of these restrictions are inherent in the approach, one must of course recognize the tradeoffs in complexity of the hypothesis space and generalization performance.

∑j̸=i sj, we can derive an explicit �rst-order condition for symmetric equilibrium: si = -a1/(2a2 + (m - 1)c).

While a pure-strategy equilibrium will necessarily exist for any separable polynomial model, it is only guaranteed to exist in the non-separable case when the learned quadratic is concave. In the experiments that follow, when the learned non-separable quadratic does not have a pure Nash equilibrium, we generate an arbitrary symmetric pure pro�le as the approximate Nash equilibrium.

Another dif�culty arises when a polynomial of a degree higher than three has more than one Nash equilibrium. In such a case we select an equilibrium arbitrarily.

3.3 Local Regression

In addition to polynomial models, we explored learning using two local regression methods: locally weighted average and locally weighted quadratic regression [Atkeson et al., 1997]. Unlike model-based methods such as polynomial regression, local methods do not attempt to infer model coef�cients from data. Instead, these methods weigh the training data points by distance from the query point and estimate the answer�in our case, the payoff at the strategy pro�le point�using some function of the weighted data set. We used a Gaussian weight function: w = e-d2 , where d is the distance of the training data point from the query point and w is the weight that is assigned to that training point.

In the case of locally weighted average, we simply take the weighted average of the payoffs of the training data points as our payoff at an arbitrary strategy pro�le. Locally weighted quadratic regression, on the other hand, �ts a quadratic regression to the weighted data set for each query point.

3.4 Support Vector Machine Regression

The third category of learning methods we used was Support Vector Machines (SVMs). For details regarding this learning method, we refer an interested reader to [Vapnik, 1995]. In our experiments, we used SVM light package [Joachims, 1999], which is an open-source implementation of SVM classi�cation and regression algorithms.

3.5 FindingMixed Strategy Equilibria

In the case of polynomial regression, we were able to �nd either analytic or simple and robust numeric methods for computing pure Nash equilibria. With local regression and SVM learning we are not so fortunate, as we do not have access to a closed-form description of the function we are learning. Furthermore, we are often interested in mixed strategy approximate equilibria, and our polynomial models and solution methods yield pure strategy equilibria.

When a particular learned model is not amenable to a closed-form solution, we can approximate the learned game with a �nite strategy grid and �nd a mixed-strategy equilibrium of the resulting �nite game using a general-purpose �nite-game solver. We employed replicator dynamics [Fudenberg and Levine, 1998], which searches for a symmetric mixed equilibrium using an iterative evolutionary algorithm. We treat the result after a �xed number of iterations as an approximate Nash equilibrium of the learned game.

3.6 Strategy Aggregation

As noted above, we consider payoff functions on twodimensional strategy pro�les in the form u(si, s-i) = f(si, φ(s-i)). As long as φ(s-i) is invariant under different permutations of the same strategies in s-i, the payoff function is symmetric. Since the actual payoff functions for our example games are also known to be symmetric, we constrain that φ(s-i) preserve the symmetry of the underlying game.

In our experiments, we compared three variants of φ(s-i). First and most compact is the simple sum, φsum(s-i). Second is the ordered pair (φsum, φss), where φss(s-i) = ∑j̸=i (sj)2 . The third variant, φidentity(s-i) = s-i, simply takes the strategies in their direct, unaggregated form. To enforce the symmetry requirement in this last case, we sort the strategies in s-i.

4 First-Price Sealed-Bid Auction

In the standard �rst-price sealed-bid (FPSB) auction game [Krishna, 2002], agents have private valuations for the good for sale, and simultaneously choose a bid price representing their offer to purchase the good. The bidder naming the highest price gets the good and pays the offered price. Other agents receive and pay nothing. In the classic setup �rst analyzed by Vickrey [1961], agents have identical valuation distributions, uniform on [0, 1], and these distributions are common knowledge. The unique (Bayesian) Nash equilibrium of this game is for agent i to bid m-1 m xi, where xi is i's valuation for the good.

Note that strategies in this game (and generally for games of incomplete information), bi : [0, 1] → [0, 1], are functions of the agent's private information. We consider a restricted case, where bid functions are constrained to the form bi(xi) = kixi, ki ∈ [0, 1]. This constraint transforms the action space to a real interval, corresponding to choice of parameter ki. We can easily see that the restricted strategy space includes the known equilibrium of the full game, with si = ki = m-1 m for all i, which is also an equilibrium of the restricted game in which agents are constrained to strategies of the given form.

We further focus on the special case m = 2, with corresponding equilibrium at s1 = s2 = 1/2. For the two-player FPSB, we can also derive a closed-form description of the actual expected payoff function:

The availability of known solutions for this example facilitates analysis of our learning approach. Our results are summarized in Figure 1. For each of our methods (classes of functional forms), we measured average ϵ for varying training set sizes. For instance, to evaluate the performance of separable quadratic approximation with training size N, we independently draw N strategies, {s1 , . . . , sN }, uniformly on [0, 1]. The corresponding training set comprises O(N 2 ) points: ((si , sj ), u(si , sj )), for i, j ∈ {1, . . . ,N}, with u as given by (3). We �nd the best separable quadratic �t ˆu to these points, and �nd a Nash equilibrium corresponding to ˆu. We then calculate the least ϵ for which this strategy pro�le is an ϵ-Nash equilibriumwith respect to the actual payoff function u. We repeat this process 200 times, averaging the results over strategy draws, to obtain each value plotted in Figure 1.

As we can see, both second-degree polynomial forms we tried do quite well on this game. For N < 20, quadratic regression outperforms the model labeled �sample best�, in which the payoff function is approximated by the discrete training set directly. The derived equilibrium in this model is simply a Nash equilibrium over the discrete strategies in the training set. At �rst, the success of the quadratic model may be surprising, since the actual payoff function (3) is only piecewise differentiable and has a point of discontinuity. However, as we can see from Figure 2, it appears quite smooth and well approximated by a quadratic polynomial. The higher-degree polynomials apparently over�t the data, as indicated by their inferior learning performance displayed in this game.

The results of this game provide an optimistic view of how well regression might be expected to perform compared to discretization. This game is quite easy for learning since the underlying payoff function is well captured by our lowerdegree model. Moreover, our experimental setup eliminated the issue of noisy payoff observations, by employing the actual expected payoffs for selected strategies.

5 Market-Based Scheduling Game

The second game we investigate presents a signi�cantly more dif�cult learning challenge. It is a �ve-player symmetric game, with no analytic characterization, and no (theoretically) known solution. The game hinges on incomplete information, and training data is available only from a simulator that samples from the underlying distribution.

The game is based on a market-based scheduling scenario [Reeves et al., 2005], where agents bid in simultaneous auctions for time-indexed resources necessary to perform their given jobs. Agents have private information about their job lengths, and values for completing their jobs by various deadlines. Note that the full space of strategies is quite complex: it is dependent on multi-dimensional private information about preferences as well as price histories for all the time slots. As in the FPSB example, we transform this policy space to the real interval by constraining strategies to a parametrized form. In particular, we start from a simple myopic policy� straightforward bidding [Milgrom, 2000], and modify it by a scalar parameter (called �sunk awareness�, and denoted by k) that controls the agent's tendency to stick with slots that it is currently winning. Although the details and motivation for sunk awareness are inessential to the current study, we note that k ∈ [0, 1], and that the optimal setting of k involves tradeoffs, generally dependent on other agents' behavior.

To investigate learning for this game, we collected data for all strategy pro�les over the discrete set of values k ∈ {0, 0.05, . . . , 1}. Accounting for symmetry, this represents 53,130 distinct strategy pro�les. For evaluation purposes, we treat the sample averages for each discrete pro�le as the true expected payoffs on this grid.

The previous empirical study of this game by Reeves et al. [2005] estimated the payoff function over a discrete grid of pro�les assembled from the strategies {0.8, 0.85, 0.9, 0.95, 1}, computing an approximate Nash equilibrium using replicator dynamics. We therefore generated a training set based on the data for these strategies (300000 samples per pro�le), regressed to the quadratic forms, and calculated empirical ϵ values with respect to the entire data set by computing the maximum bene�t from deviation within the data: ϵemp = maxi∈I maxsi∈Si [ui(si, ˆ s-i) - ui(ˆ s)] , where Si is the strategy set of player i represented within the data set. Since the game is symmetric, the maximum over the players can be dropped, and all the agent strategy sets are identical.

From the results presented in Table 1, we see that the Nash equilibria for the learned functions are quite close to that produced by replicator dynamics, but with ϵ values quite a bit lower. (Since 0.876 is not a grid point, we determined its ϵ post hoc, by running further pro�le simulations with all agents playing 0.876, and where one agent deviates to any of the strategies in {0, 0.05, . . . , 1}.)

In a more comprehensive trial, we collected 2.2 million additional samples per pro�le, and ran our learning algorithms on 100 training sets, each uniformly randomly selected from the discrete grid {0, 0.05, . . . , 1}. Each training set included pro�les generated from between �ve and ten of the twentyone agent strategies on the grid. Since in this case the pro�le of interest does not typically appear in the complete data set, we developed a method for estimating ϵ for pure symmetric approximate equilibria in symmetric games based on a mixture of neighbor strategies that do appear in the test set. Let us designate the pure symmetric equilibrium strategy of the approximated game by ˆ s. We �rst determine the closest neighbors to ˆ s in the symmetric strategy set S represented within the data. Let these neighbors be denoted by s′ and s′′ . We de�ne a mixed strategy α over support {s′ , s′′} as the probability of playing s′ , computed based on the relative distance of ˆ s from its neighbors: α = 1 - |ˆ s - s′ |/|s′ - s′′ |. Note that symmetry allows a more compact representation of a payoff function if agents other than i have a choice of only two strategies. Thus, we de�ne U(si, j) as the payoff to a (symmetric) player for playing strategy si ∈ S when j other agents play strategy s′ . If m- 1 agents each independently choose whether to play s′ with probability α, then the probability that exactly j will choose s′ is given by

We can thus approximate ϵ of the mixed strategy α by

Using this method of estimating ϵ on the complete data set, we compared results from polynomial regression to the method which simply selects from the training set the pure strategy pro�le with the smallest value of ϵ. We refer to this method as �sample best�, differentiating between the case where we only consider symmetric pure pro�les (labeled �sample best (symmetric)�) and all pure pro�les (labeled �sample best (all)�). 2

2 It is interesting to observe in Figures 3 and 4 that when we restrict the search for a best pure strategy pro�le to symmetric pro�les, we on average do better in terms of ϵ then when this restriction is not imposed.

From Figure 3 we see that regression to a separable quadratic produces a considerably better approximate equilibrium when the size of the training set is relatively small. Figure 4 shows that the non-separable quadratic performs similarly. The results appear relatively insensitive to the degree of aggregation applied to the representation of other agents' strategies.

The polynomial regression methods we employed yield pure-strategy Nash equilibria. We further evaluated four methods that generally produce mixed-strategy equilibria: two local regression learning methods, SVM with a Gaussian radial basis kernel, and direct estimation using the training data. As discussed above, we computed mixed strategy equilibria by applying replicator dynamics to discrete approximations of the learned payoff functions. 3 Since we ensure that the support of any mixed strategy equilibrium produced by these methods is in the complete data set, we can compute ϵ of the equilibria directly.

3 In the case of direct estimation from training data, the data itself

As we can see in Figure 5, locally weighted average method appears to work better than the other three for most data sets that include between �ve and ten strategies. Additionally, locally weighted regression performs better than replicator dynamics on four of the six data set sizes we considered, and SVM consistently beats replicator dynamics for all six data set sizes. 4

It is somewhat surprising to see how irregular our results appear for the local regression methods. We cannot explain this irregularity, although of course there is no reason for us to expect otherwise: even though increasing the size of the training data set may improve the quality of �t, improvement in quality of equilibrium approximation does not necessarily follow.

6 Conclusion

While there has been much work in game theory attempting to solve particular games de�ned by some payoff functions, little attention has been given to approximating such functions from data. This work addresses the question of payoff function approximation by introducing regression learning techniques and applying them to representative games of interest. Our results in both the FPSB and market-based scheduling games suggest that when data is sparse, such methods

was used as input to the replicator dynamics algorithm. For the other three methods we used a �xed ten-strategy grid as the discretized approximation of the learned game.

4 Note that we do not compare these results to those for the polynomial regression methods. Given noise in the data set, mixedstrategy pro�les with larger supports may exhibit lower ϵ simply due to the smoothing effect of the mixtures.

can provide better approximations of the underlying game� at least in terms of ϵ-Nash equilibria�than discrete approximations using the same data set.

Regression or other generalization methods offer the potential to extend game-theoretic analysis to strategy spaces (even in�nite sets) beyond directly available experience. By selecting target functions that support tractable equilibrium calculations, we render such analysis analytically convenient. By adopting functional forms that capture known structure of the payoff function (e.g., symmetry), we facilitate learnability. This study provides initial evidence that we can sometimes �nd models serving all these criteria.

In future work we expect to apply some of the methods developed here to other challenging domains.