Pure Strategy Nash Equilibria

 

This appendix revisits the existence of pure strategy Nash equilibria (PNE) in the prescribed model of shopbots and pricebots whenever . It has previously been established (see Sec. 3) that no PNE exist when prices are selected from a continuous strategy space. Here, we assume that prices are chosen from a strategy space that is discrete rather than continuous, and we derive the set of pure strategy Nash equilibria. This set is symmetric in the case of 2 sellers, but is often asymmetric in the case of S > 2 sellers.

Recall from Sec. 2 that the profits for seller s are determined as follows, assuming for all buyers b, and for all sellers s:

where

• is the Kronecker function,
• is the number of sellers charging a lower price than s, and
• is the number of sellers charging the same price as s, excluding s itself.

The equilibrium derivation that follows concerns the case of discrete strategy spaces, characterized by some parameter , which dictates the sellers' space of strategies as follows: . If we assume , then this strategy space contains prices of the form , where . For convenience, we further assume .

The derivation of the set of pure strategy Nash equilibria is based on the following observations, which dictate the structure of its elements: at equilibrium,

1. No seller charges price .
2. No seller charges price .
3. At least two sellers charge prices .
4. Those sellers who charge prices charge equal prices.

The first two observations follow from the fact that the profits obtained by charging the monopoly price v are strictly positive, whereas the profits obtained by charging either or are zero. At least two sellers charge since (i) if all sellers were to charge v, seller s would stand to gain by instead charging (assuming ) and (ii) if only one seller were to charge , then must equal , in which case the other sellers would stand to gain by charging (assuming ). Finally, if seller s' were to charge , while seller s were charging , then seller s' would prefer price v to price , implying that is not an equilibrium price. Therefore, PNE are structured such that sellers charge for , while the remaining S - n sellers charge the monopoly price v.

Given the prescribed structure, the existence of pure strategy Nash equilibria is ensured whenever the following conditions are satisfied: for all sellers s,

1. No low-priced seller charging prefers the monopoly price v: i.e., , where is computed assuming is charged by n low-priced sellers. Expanding this condition leads to the following:

    

   This condition implies that , since .
   

2. No seller charging v prefers to undercut the low-priced sellers charging and charge : i.e., , where are the profits obtained if seller s is the unique, lowest-priced seller. Expanding this condition yields:

    

   For i = 1 this condition reduces to , which is tautological; hence this constraint is only of interest when i > 1.
   

3. No low-priced seller charging prefers to undercut its cohorts by charging : i.e., , which incidentally is implied by Conds. 14 and 15. This yields a constraint on the value of i (or stated otherwise, n) for which PNE exist, namely:

    

   Like the previous condition, this constraint is only applicable when i > 1.

Together Conds. 14, 15, and 16 are mathematical statements of the conditions for the existence of pure strategy Nash equilibria of the prescribed structure.

We now construct a series of examples, assuming production cost is c = 0.5, buyers have constant valuations v = 1, and and . Initially, we consider the case in which S = 2. If i = 1, then PNE exist whenever ; if i = 2, then PNE exist iff ; however, if i > 2, then no PNE exist since Cond. 16 requires that , which is impossible for integer values of i > 2. The complete set of PNE for S = 2 is listed in Table A. Notice that PNE cease to exist when |P| > 9; for S = 3, PNE cease to exist when |P| > 12; in general, PNE cease to exist whenever where is the maximum integer value i satisfying Cond. 16, which can be rearranged to give an upper bound on i.

  
Table: The set of PNE for S = 2. DNE stands for does not exist, implying the non-existence of pure strategy Nash equilibria, although the existence of mixed strategy equilibria is established in Nash [28].

Now consider a larger number of sellers; for concreteness, say S = 100. We first let i = 1, which limits our concern to Cond. 14. It follows from this condition that when the number of sellers is large, PNE exist even for small values of so long as n is also small. In particular, if n = 2 then PNE exist for ; specifically, if , then an asymmetric solution arises in which sellers who charge price earn profits of roughly 0.00126, while sellers who charge price v earn 0.00125. At the other extreme, if n = 100, then symmetric PNE exist iff ; these equilibria extend the top 5 solutions listed in Table A for S = 2 to the case of 100 sellers. A full range of equilibria exist when i = 1 for the values of specified by Cond. 14 that arise for values of n ranging from 2 to 100.

Still assuming a large number of sellers, let i > 1. Restating Cond. 16 as a bound on n and taking the limit as , we find that . But since at equilibrium, it follows that at any PNE exactly 2 sellers charge price . Again rewriting Cond. 16, this time as a bound on i and then taking the limit as , we also find it necessary that . Thus, for sufficiently large numbers of sellers, PNE exist in which exactly 2 low-priced sellers charge price , but no PNE exist in which any sellers charge for i > 2.

It is nonetheless possible for equilibria to arise in which i > 2, however not for the assignments of and assumed throughout our examples. Consider instead and . Now for S = 2, an equilibrium arises in which n = 2, i = 5, and , namely . Using Cond. 16, we note that as , i is bounded above only by ; in other words, high equilibrium prices prevail. On the other hand, as , n is bounded above only by S, implying that more and more sellers prefer to charge low prices.