# Computing Nash equilibria in discrete auctions

I am trying to compute the (pure strategy) Nash equilibria of some discrete auctions.

More precisely, let us define the strategy of each player as a function mapping from every valuation that they might have to their bid (i.e. the 'bidding function'). Let us suppose that each player's valuation is drawn from some finite set and that their bid must belong to this same (finite) set. I am interested in finding the set of bidding functions, one for each player, such that each player's bidding function is optimal given the bidding functions of all the other players.

If it makes things easier, we can assume that valuations are symmetric (i.e. each player's valuation is generated by the same probability distribution) and that there are only two bidders. Ideally, however, we would proceed without these simplifications. I am interested in computing the equilibrium for the first price sealed bid and all pay auctions (in the latter, you pay your bid even if you lose; in the former, you don't.)

I have considered writing down the discrete auction game in normal form and finding the equilibria using software like Gambit. However, this would seem tricky since the strategy space is so large. For example, if a player chooses bids from $$\{1,...,10\}$$ and draws values from $$\{1,...,10\}$$, then already they have $$10^{10}$$ pure strategies.

Does anyone have any ideas about how to proceed here?

• The answer might depend on the parameters. How large is the finite set of possible valuations, in practice? Is it at most about 10? – D.W. Feb 18 '19 at 20:20
• No, usually more like 100 - 1000 (unfortunately!) However, we can reduce the dimensionality somewhat by ruling out strategies that require you to bid more than your valuation. – afreelunch Feb 20 '19 at 15:04
• OK. What determines whether a player's bidding function is optimal, given the other functions? I'm wondering how one would check that, and how "simple" a computation it is. (If it involves reasoning about all other possible choices for that player's bidding function, that sounds pretty complicated. But maybe there's some simpler characterization of when a proposed bidding function is optimal, when given all the other players' functions?) – D.W. Feb 20 '19 at 19:33
• Optimal = maximises expected payoff (i.e. assume risk neutrality) – afreelunch Feb 23 '19 at 16:00
• OK. How do we calculate expected payoff, given all the players bidding functions? Is it "highest bidder wins the item, and their payoff for that item is what they bid minus their valuation of the item"? And where is the randomness (why do you say expected payoff)? – D.W. Feb 23 '19 at 19:44

If there are only two players, you could use integer linear programming.

I'll introduce some zero-or-one integer variables to encode the (unknown) bidding functions (via a one-hot encoding). Let $$x_{v,b}=1$$ if player $$0$$'s bid is $$b$$ when their valuation is $$v$$, and $$0$$ otherwise; and $$y_{w,c}=1$$ if player $$1$$'s bid is $$c$$ when their valuation is $$w$$, and $$0$$ otherwise. In this way, if there are $$n$$ possible valuations, we obtain $$2n^2$$ zero-or-one integer variables. We will write down linear inequalities on these variables that characterize the optimality condition, then use an integer programming solver to find a solution that satisfies all of these inequalities.

Note that if player $$0$$'s valuation is $$v$$ and player $$1$$'s valuation is $$w$$, then player $$0$$'s payoff (in a first-price auction) is

$$\sum_{b>c} x_{v,b} y_{w,c} (v-b).$$

Therefore, if player $$0$$'s valuation is $$v$$, player $$0$$'s expected payoff is

$$\sum_w p_1(w) \sum_{b>c} x_{v,b} y_{w,c} (v-b),$$

where $$p_1(w)$$ represents the probability that player $$1$$ gets valuation $$w$$. Now, we need this to be at least what it would be if player $$0$$ used any other bid for valuation $$v$$, i.e., any other choice of $$x_{v,\cdot}$$'s. If there are $$n$$ possible valuations, there are only $$n$$ possible bids, so we obtain $$n$$ inequalities

$$\sum_w p_1(w) \sum_{b>c} x_{v,b} y_{w,c} (v-b) \ge \sum_w p_1(w) \sum_{b'>c} y_{w,c} (v-b'),$$

where we obtain one such inequality for each possible value of $$b'$$. (The sum on the left-hand-side is over $$w,b,c$$ that satisfy the condition $$b>c$$; the sum on the right-hand-side is over $$w,c$$ that satisfy the condition $$c.)

This is a quadratic inequality. We'll turn it into a linear inequality using the techniques of Express boolean logic operations in zero-one integer linear programming (ILP). In particular, introduce new zero-or-one variables $$t_{v,w,b,c}$$, with the intention that $$t_{v,w,b,c}=x_{v,b} y_{w,c}$$. This can be enforced using the linear inequalities $$t_{v,w,b,c} \ge x_{v,b} + y_{w,c} - 1$$, $$t_{v,w,b,c} \le x_{v,b}$$, $$t_{v,w,b,c} \le y_{w,c}$$, $$0 \le t_{v,w,b,c} \le 1$$. Now the optimality condition becomes

$$\sum_w p_1(w) \sum_{b>c} t_{v,w,b,c} (v-b) \ge \sum_w p_1(w) \sum{b'>c} y_{w,c} (v-b'),$$

for each $$v,b'$$. We obtain one such inequality for each $$v$$ and each $$b'$$. These $$n^2$$ inequalities ensure that player $$0$$'s strategy will be optimal (given player $$1$$'s strategy).

Then, add similar inequalities to require player $$1$$'s strategy to be optimal (given player $$0$$'s strategy).

Also add the $$n^2+n$$ constraints that $$0 \le x_{v,b} \le 1$$ and $$\sum_b x_{v,b}=1$$ to require the $$x$$'s to correspond to a bidding function, and similarly for the $$y$$'s.

Finally, take all of these inequalities and feed them to an off-the-shelf integer linear programming solver. If it finds a solution, then you have found a Nash equilibrium for your game. ILP is NP-hard, so there is no guarantee that it will terminate in a reasonable amount of time, but in my experience often the solvers can handle surprisingly large systems of inequalities.

The same approach can handle all-pay auctions as well as first-price auctions.

In practice, you might be able to speed up the solver by adding some extra constraints to help it identify a solution faster. In particular, I have a hunch that without loss of generality the optimal bidding function can be assumed to be monotonic: if we increase my valuation, my bid should never decrease. We can add extra inequalities to the system to characterize this additional assumption, and this might narrow the search space and thus help the ILP solver find a solution more rapidly.

One big limitation is that this seems limited to two players (or a very small number of players). If there are multiple players, the number of variables and inequalities will explode, and this might not be an effective approach.