Shopbots and Pricebots

1 Introduction

Shopbots, agents that automatically search the Inter­ net for goods and/or services on behalf of consumers, herald a future in which autonomous agents become an essential component of nearly every facet of elec­ tronic commerce [Chavez and Maes, 1996; Kephart et al., 1998; Tsvetovatyy et al. , 1997]. In response to a consumer's expressed interest in a specified good or ser­ vice, a typical shopbot can query several dozen web sites, and then collate and sort the available informa­ tion for the user - all within seconds. For example, www. shopper. com claims to compare 1,000,000 prices on 100,000 computer-oriented products! In addition, www. acses. com compares the prices and expected de­ livery times of books offered for sale on-line, while www. j ango . com and we bmarket . j unglee . com offer ev­ erything from apparel to gourmet groceries. Shopbots can out-perform and out-inform even the most patient, determined consumers, for whom it would take hours to obtain far less coverage of available goods and services.

Shopbots deliver on one of the great promises of elec­ tronic commerce and the Internet: a radical reduc­ tion in the cost of obtaining and distributing informa­ tion. It is generally recognized that freer flow of information will profoundly affect market efficiency, as eco­ nomic friction will be reduced significantly [Lewis, 1997; DeLong and Froomkin, 1998] . Transportation costs, menu costs- the costs to firms of evaluating, updating, and advertising prices - and shopping costs - the costs to consumers of seeking out optimal price and quality - will all decrease, as a consequence of the digital nature of information as well as the presence of autonomous agents that find, process, collate, and disseminate that information at little cost. What are the implications of the widespread use of shopbots and related types of autonomous agents in electronic marketplaces, and how might species of computational agents evolve?

DeLong and Froomkin [1998] qualitatively investigate the ongoing emergence of shopbots; in particular, they note that short of violating anti-trust laws, firms will be hard pressed to prevent their competitors from spon­ soring shopbots, in which case those who do not do so will experience decreased sales. In this paper, we utilize quantitative techniques to address the aforementioned questions. We propose, analyze, and simulate a simple economic model designed to capture the present role of shopbots as agents of economic change, particularly with regard to consumer preferences, as they decrease the cost of obtaining information in markets known to exhibit price dispersion. Looking ahead several years into the fu­ ture, we project that shopbots will evolve into economic entities (i.e., utility maximizers) in their own right, in­ teracting with billions of other self-interested software agents. Moreover, we predict the emergence of pricebots - economically-motivated agents that set prices so as to maximize the profits of firms, just as shopbots seek prices that minimize costs for consumers. Accordingly, we study adaptive price-setting algorithms which price­ hots might utilize to combat the growing community of shopbots, in a full-fledged agent-based economy.

This paper is organized as follows. The next section, Section 2, presents our model, which is analyzed in Sec­ tion 3 from a game-theoretic point of view. Section 4 de­ scribes various adaptive price-setting algorithms and the results of their simulation under the prescribed model. A possible evolution of shopbots and price hots is discussed Section 5. Concluding remarks and ideas for future work appear in Section 6.

2 Model

We consider an economy in which there is a commodity that is offered for sale by S sellers and of interest to B buyers, with B » S . Each buyer b generates purchase orders at random times, with rate Pb, while each seller 8 resets its price p, at random times, with rate p, . The value of the good to buyer b is Vb; the cost of production for seller 8 is c, .

A buyer b's utility for a good is a function of price:

This states that a buyer purchases a good from a given seller if and only if the seller's price is less than the buyer's valuation of the good; if price equals valuation, we make the behavioral assumption that a transaction occurs. We do not assume that buyers are utility maxi­ mizers; instead we assume that they consider the prices offered by sellers using one of the following strategies:

1. Any Seller: buyer selects seller at random, and pur­ chases the good if the price charged by that seller is less than the buyer's valuation.
2. Bargain Hunter: buyer checks the offer price of all sellers, determines the seller with the lowest price, and purchases the good if that lowest price is less than the buyer's valuation. (This type of buyer cor­ responds to those who take advantage of shopbots.)

The buyer population consists of a mixture of buyers employing one of these strategies, with a fraction WA using the Any Seller strategy and a fraction WB using the Bargain Hunter strategy; WA + WB = 1. Buyers employing these respective strategies are referred to as type A and type B buyers.

A seller 8's expected profit per unit time 1r, is a func­ tion of the price vector p:

where D, (P) is the rate of demand for the good produced by seller 8 . This rate of demand is the product of the overall buyer rate of demand p = L:b Pb, the likelihood of a given buyer selecting seller 8 as their potential seller, h, (P) , and the fraction of buyers whose valuations satisfy Vb ?: p, , denoted g(p,) :

Note that g(p,) = J,""' "Y(:z:)d:z:, where "Y(:z:) is the probp, ability density function describing the likelihood that a given buyer has valuation :z: . If Vb = v for all buyers b, then "Y(:z:) is the Dirac delta function a(v- :z:), and the integral yields a step function g(p,) = e(v- p,):

Without loss of generality, we define the time scale such that pB = 1. It follows that D,(P) = h,(P)g(p,), and 7r1 is seller 8's expected profit per unit sold systemwide.

The probability h, (P) that buyers select seller 8 as their potential seller depends on the distribution of the buyer population, namely ( WA, w B) . In particular,

where J,,A(P) and f,,s(P) are the probabilities that seller 8 is selected by buyers of type A and B, respectively. The probability that a buyer of type A select a seller 8 is in­ dependent of the ordering of sellers' prices; in particular, f, ,A (P) = 1/ S . Buyers of type B, however, select a seller 8 if and only if 8 is one of the lowest price sellers. Given that the buyers' strategies depend on the relative order­ ing of the sellers' prices, it is convenient to define the following functions :

• .X, (P) is the number of sellers charging a lower price than 8, and
• r, (P) is the number of sellers charging the same price as 8, excluding 8 itself.

Now buyers of type b select seller 8 iff 8 is s.t . .X,(P) = 0, in which case a buyer selects a particular such seller 8 with probability 1/(r,(P) + 1) . Therefore,

where Oi,j is the Kronecker delta function, equal to 1, whenever i = j, and 0, otherwise.

The preceding results can be assembled to express the profit function 1r, for seller 8 in terms of the distribution of strategies and valuations within the buyer population. In particular, assuming (as we do from here forward) that all buyers share the same valuation v, and all sellers share the same cost c, then

where

3 Analysis

In this section, we perform a game-theoretic analysis as­ suming sellers are profit maximizers. In particular, we first show that there is no pure strategy Nash equilib­ rium, and we then compute and describe the symmetric mixed strategy Nash equilibrium. Recall that B » S; in particular, the number of buyers is assumed to be very large, while the number of sellers is a great deal smaller . In accordance with this assumption, it is rea­ sonable to consider the strategic decision-making of the sellers alone, since their relatively small number suggests that the behavior of individual sellers indeed influences market dynamics, while the large number of buyers ren­ ders the effects of individual buyers' actions negligible. A Nash equilibrium is a vector of prices p· at which sellers maximize their individual profits and from which they have no incentive to deviate [Nash, 1951] . Through­ out this exposition, we adopt the notation p= (p,,p_,), which distinguishes the price offered by seller s from the prices offered by the remaining sellers.

Traditional economic models consider the case in which all buyers are bargain hunters: i.e., WB = 1. In this case, prices are driven down to marginal cost; in particular, p; = c, for all sellers s (see, for example, Ti­ role [1988]) . In contrast, consider the case in which all buyers are of type A, meaning that they randomly select a potential seller: i.e., W.A = 1. In this situation, tacit collusion arises, in which all sellers charge the monop­ olistic price, in the absence of explicit coordination; in particular, p; = v, for all sellers s. Of particular inter­ est in this study, however, is the dynamics of interaction among buyers of various types: i.e., 0 < W.A , WB < 1.

We begin our analysis with the following observation: at equilibrium, at most one sellers charges p; < v . Sup­ pose that two distinct sellers s' -::f s set their equilibrium prices to be p;, = p; < v, while all other sellers set their equilibrium prices at the buyers' valuation v . In this case, 1r,(p; - £,p~,) = [(1/S)w.A + WB](p;- f- c) > [(1/S)w.A + (1/2)wB](P; -c) = 1r,(p; ,p~ 1 ), for small values of£, whenever WB > 0, which implies that p; is not an equilibrium price for seller s . Now suppose that two distinct sellers s' -::f s set their equilibrium prices to be p;, < p; < v, while all other sellers set their equilibrium prices at v. In this case, seller s prefers price v top;, since 1r,(v,p~,) = [(1/S)w.A](v- c) > [(1/ S)w.A](p;- c) = 11"1 (p;, p~, ), which implies that p; is not an equilibrium price for seller s . Therefore, at most one seller charges p; < v.

On the other hand, at equilibrium, at least one seller s charges p; < v. Given that all sellers other than s set their equilibrium prices at v, seller s maximizes its profits by charging price v-£, since 1r,( v -t",p~,) = [(1/ S)w.A + wB](v- f- c)> [(1/S)(w.A + WB)](v- c)= 1r,(v,p~,), for small values of£, whenever WB > 0. Thus vis not an equilibrium price for seller 8 . It follows from these two observations that at equilibrium, exactly one seller 8 sets its price below the buyers' valuation v, while all other sellers 8 1 -::/= 8 set their equilibrium prices p;, 2: v. Note, however, that 1f,·(v,p~ 1 ,) = [(1/S)w.A](v- c) > 0 = 1f,·(v',p:_,,), for all v' > v, if W.A > 0, implying that all other sellers 8 1 maximize their profits by charging price v . Thus, the unique form of pure strategy equilibrium which arises in this setting requires that a single seller 8 set its price p; < v while all other sellers 8 1 -::f 8 set their prices p;, = v. The price vector (p;, p~,), with p~, = (v, ... ,v), however, is not a Nash equilibrium. While v is in fact an optimal response to p;, since the profits of sellers' -::/= s are maximized at v given that there exists low-priced seller 8 1 p; is not an optimal response to v. On the contrary, 1r,(p;, v, ... , v) < 1r,(p; +£, v, ... , v) . In particular, the low-priced sellers has incentive to de­ viate. It follows that there is no pure strategy Nash equilibrium in the proposed model of shopbots.

There does, however, exist a symmetric mixed strategy Nash equilibrium. Let f(p) denote the density function according to which sellers set their prices, and let F(p/ be the corresponding cumulative distribution function. The event that seller 8 is the low-priced seller occurs with probability [1- F(p)] 5 - 1 . Substituting this into Eq. 5, we obtain the demand expected by seller 8:

The precise value of F(p) is determined by noting that at equilibrium expected profits are equal for all sell­ ers, and moreover the expected profit level is given by the guaranteed minimum achieved at price v, namely (1/S)w.A(v- c) . Now, by setting 1r,(p) = h,(p)(p- c) equal to this value and solving for F(p), we obtain:

Notice that F(p) = 0 for p = p* defined as follows :

and F(p) = 1 for p = v. Thus, Eq. 10 is valid only in the range p* ::; p ::; v. 2

The functions F(p) and f(p) are plotted in Figure 1. When WB exceeds a critical threshold w~rit = 52~5 2 _ 2 (equal to 0.1071 for S = 5), f(p) is bimodal. In this regime, as either WB or S increases, the probability den­ sity concentrates either just below v, where sellers expect high margins but low volume, or just above p*, where they expect low margins but high volume; moreover, the latter solution becomes increasingly probable. Since p* itself decreases under these conditions (see Eq. 11), it follows that both the average price paid by buyers and the average profit earned by sellers decrease. These re­ lationships have a simple interpretation: buyers' use of shopbots catalyzes competition among sellers, and more­ over, smaller fractions of shopbot users induce competi­ tion among larger numbers of sellers.

4 Simulations

When sufficiently widespread adoption of shopbots by buyers forces sellers to become more competitive, it seems likely that sellers will respond by creating price­ bats that automatically set prices so as to maximize profitability. It is unrealistic, however, to expect that pricebots will simply compute the mixed strategy Nash equilibrium and distribute their prices accordingly. The real business world is fraught with uncertainties that un­ dermine the validity of traditional game-theoretic anal­ yses: sellers lack perfect knowledge of buyer demands, and have an incomplete understanding of competitors' strategies. In order to be profitable, pricebots will need to continually adapt to changing market conditions.

1 As the equilibrium is symmetric, we abbreviate p = p, and we suppress dependence on p.

2 A similar derivation of the mixed strategy equilibrium appears in Varian [1980].

In this section, we discuss simulations of two adaptive pricing strategies, and we compare the resulting price and profit dynamics with the game-theoretic equilib­ rium. Recently, empirical studies of sophisticated learn­ ing algorithms have revealed that learning tends to con­ verge to pure strategy Nash equilibria in games for which such equilibria exist [Greenwald et al., 1998]. As there does not exist a pure strategy Nash equilibrium in the shopbot model, it is of particular interest to study the outcome of adaptive pricing schemes.

4.1 Pricing Strategies

We consider three pricing strategies, each of which makes very different demands on the required level of informa­ tional and computational power of agents:

• GT The game-theoretic strategy is designed to repro­ duce the mixed strategy game-theoretic equilibrium computed in the previous section, provided that it is employed by all seller agents. It makes use of full information about the buyer population, and assumes that its competitors also use the GT strat­ egy. It therefore generates a price chosen randomly from the probability density function derived in the previous section.
• MY The myopically optimal, or myoptimal, 3 pricing strategy [Kephart et al., 1998] uses information about all the buyer characteristics that factor into the buyer demand function, as well as the competi­ tors' prices, but makes no attempt to account for competitors' pricing strategies. Instead, it is based on the assumption of static expectations: even if one seller is contemplating a price change under myop­ timal pricing, this seller does not assume that this will elicit a response from its competitors; instead it assumes that competitors' prices will remain fixed.

The myoptimal seller uses all of the available infor­ mation and the assumption of static expectations to perform an exhaustive search for the price p* that maximizes its expected profit 1r. In our simulations, we compute 1r according to Eqs. 7 and 8. The op­ timal price p* is guaranteed to be either the valu­ ation v or € below some competitor's price, where € is the price quantum, or the smallest amount by which one seller may undercut another, set to 0.002 in these simulations. This limits the search for p* to S possible values.

• DF The derivative-following strategy is far less informa­ tionally intensive than either the myoptimal pricing strategy or the game-theoretic strategy. In particu­ lar, this strategy can be used in the absence of any knowledge or assumptions about one's competitors or the buyer demand function . A derivative follower simply experiments with incremental increases (or decreases) in its price, continuing to move its price in the same direction until the observed profitability

3 In the game-theoretic literature, this adaptive strategy is known as Coumot best-reply dynamics [Cournot, 1838] .

level falls, at which point the direction of movement is reversed. The price increment o is chosen ran­ domly from a specified probability distribution; in the simulations described here the distribution was uniform between 0.01 and 0.02.

4.2 Price and Profit Dynamics

We have simulated an economy with 1000 buyers and 5 sellers employing various mixtures of pricing strategies. In each of the simulations depicted below, each buyer's valuation of the good v = 1, and each seller's production cost c = 0.5. The mixture of buyer types is set at WB = 0.75, i.e., 75% are bargain hunters.

The simulation is asynchronous: at each time step, a buyer or seller is randomly selected to carry out an action (e.g., buying an item or resetting a price). The chance that a given agent is selected for action is determined by its rate; the rate Pb at which a given buyer b attempts to purchase the good is set to 0.001, while the rate p1 at which a given seller reconsiders its price is 0.00002. Each simulation was iterated for 100 million time steps.

GT Pricing Strategy

Simulations verify that , if agents are GT strategists, the cumulative distribution of prices closely resembles the derived F(p) (to within statistical error), and moreover, the time-averaged profit for each seller is 7r = 0.0255 ± 0.0003, which is nearly the theoretical value of 0.0250.

MY Pricing Strategy

Fig. 2(a) illustrates the cyclical price wars that typically occur when all 5 sellers use the myoptimal pricing strat­ egy. Regardless of the initial value of the price vector, a pattern quickly emerges in which prices are positioned near the monopolistic price v = 1, followed by a long episode during which the sellers successively undercut one another by €. During this latter phase, no two prices differ by more than (S- 1)€, and the prices fall linearly with time. Eventually, when the lowest-priced seller is within € above the value p* = 0.53125, the next seller finds it unprofitable to undercut, and instead resets its price to v = 1. The other sellers follow suit, until all but the lowest-priced seller are charging v = 1. At this point, the lowest-priced seller finds that it can maintain its market share but increase its profit dramatically - from p*- .5 = 0.03125 to 0.5-€- by raising its price to 1 - €. No sooner than the lowest-priced seller raises its price does the next seller who resets its price undercut, thereby igniting the next cycle of the price war.

Fig. 3(a) shows the sellers' profits averaged during the intervals between successive resetting of prices. The up­ per curve represents a linear decrease in the average profit attained by the lowest-priced seller as price de­ creases, whichever seller that happens to be. The lower curve represents the average profit attained by sellers that are not currently the lowest-priced; near the end of the cycle they suffer from both low market share and low margin. The expected average profit can be computed by averaging the ~ofit given by Eqs. 7 and 8 over one price-war cycle: 1r, Y = (1/S)[(1/2)(v + p")- c], which yields 7r~Y = 0.053125 in this instance. The simulation results match this closely: the average profit per time step is 0.0515, which is just over twice the average profit obtained via the game-theoretic pricing strategy.

Since prices fluctuate over time, it is of interest to compute the probability distribution of prices. Fig. 4( a) depicts the cumulative distribution function for myopti­ mal pricing. This measured cumulative density function has exactly the same endpoints p· = 0.53125 and v = 1 as those of the mixed strategy equilibrium, but the linear shape between those endpoints (which reflects the linear price war) is quite different from what is displayed in Fig. 1(a).

DF Pricing Strategy

Fig. 2(b) shows the price dynamics that result when 5 derivative followers are pitted against one another. Re­ call that derivative followers do not base their pricing de­ cisions on any information that pertains to other agents in the system - neither sellers' price-setting tenden­ cies nor buyers' preferences. Nonetheless, their behavior tends towards what is in effect a collusive state in which all sellers charge nearly the monopolistic price. This is tacit collusion as defined, for example, in Tirole [1988], so-called because the agents do not communicate at all and there is consequently nothing illegal about their col­ lusive behavior. Note that DF sellers accumulate greater profits than myoptimal or game-theoretic sellers. Ac­ cording to Fig. 3(b), sellers that are currently lowest­ priced can expect an average profit of 0.30 to 0.35, while the others can expect roughly the game-theoretic profit of 0.025. Averaging over the last 90 million time steps (to eliminate transient effects), we find that the aver­ age profit per seller is 0.0841. This is near the absolute collusive limit of (1/S)(v- c) = 0.10, which would be obtained if all sellers were to fix their prices at 1.

How do derivative followers manage to collude? Like myoptimal sellers, DF sellers are capable of engaging in price wars; such dynamics are visible in Fig. 2(b). How· ever, these price wars tend to involve only two sellers, and the positive feedback that drives them depends crit­ ically on both the sequence of price increments and the timing of the asynchronous moves by the sellers. Down­ ward trends are therefore very easily disrupted. For ex­ ample, if A's price is currently above B's, but A reduces its price by an amount insufficient to undercut B, then A's profits decrease, so that A raises its price in sub­ sequent time steps. Soon after A breaks the downward cycle, B discovers that it can improve profits by increas­ ing its price, and does so. Simulations clearly show that upward trends in price are much faster and more certain than downward trends. The tendency of a society of DF sellers to reach and maintain high prices is reflected in the cumulative distribution function, shown in Fig. 4(b).

It is also of interest to study the interplay among GT, MY, and DF sellers. Typically, we find that, when a myoptimal seller is introduced into a population of DF or GT sellers, it substantially outplays them, and their profits decline significantly.

"'*'·

Figure 4: Cumulative distribution functions for a) 5 MY sellers and b) 5 DF sellers, derived from prices observed between times 10 million and 100 million.

5 Evolution of Shopbots and Pricebots

In additional simulations, we investigated a situation in which all five sellers use identical pricing strategies, but one of the sellers resets its price more quickly than the others. We observed that the faster price-setter earns substantially more profit than the others because, for example, in the case of myoptimal agents, it undercuts far more often than it itself is undercut . In the absence of any throttling mechanism, it is advantageous for sellers to re-price their goods as quickly as possible, but this could potentially lead to an arms race in which sellers do so with ever-increasing frequency. In such a world, a human price setter would undoubtedly be too slow and costly, and would be replaced with a pricebot {likely one based on a more sophisticated algorithm than any ex­ plored in Section 4!). Almost certainly, this strategy would make use of information about the buyer popula­ tion, which could be purchased from other agents. Even more likely, however, the strategy would require knowl­ edge of competitors' prices. How would the pricebot obtain this information? From a shopbot, of course!

With each seller seeking to re-price its products faster than its competitors, shopbots would quickly be­ come overloaded with requests. A pricebot representing amazon . com might submit a million or more queries (one per book title) to a shopbot every hour- or maybe even every minute! Since shopbots must query individual sell­ ers for prices, they would in turn pass this load back to amazon. com's competitors: e.g., barnesandnoble. com, king books. com. The rate of pricing requests made by sellers could easily dwarf the rate at which similar re­ quests would be made by human buyers, eliminating the potential of shopbots to ameliorate market frictions .

A typical solution to an excess demand for shopbot services would be for shopbots to charge pricebots for price information. Today, shopbots tend to make a liv­ ing by selling advertising space on their Web pages. This appears to be an adequate business model so long as re­ quests are made by humans. Agents, however, are un­ welcome customers because they are are not influenced by advertisements; as a result, agents are either barely tolerated or excluded intentionally. By charging for the information services they provide, shopbots would be economically-motivated agents, creating the proper in­ centives to deter excess demand, and welcoming busi­ ness from other agents. Once shopbots begin to charge for pricing information, it would seem natural for sell­ ers - the actual owners of the desired information - to themselves charge the shopbots for their information. The sellers could use another form of price bot to dynam­ ically price this information. This scenario illustrates how the need for agents to dynamically price their ser­ vices could quickly percolate through an entire economy of software agents. The alternative is "meltdown" due to overload which could occur as agents become more prevalent on the Internet. Rules of etiquette followed voluntarily today by web crawlers and related programs could be trampled in the rush for competitive advantage.

6 Conclusion

Game-theoretic analysis of a model of a simple com­ modity market established a quantitative relationship between the degree of shop bot usage among buyers and the degree of price competition among sellers. This moti­ vated a comparative study of various price bot algorithms that sellers might employ in an effort to gain an edge in a market in which shopbots have increased the level of competition. Pricebots were shown to be capable of in­ ducing price wars, yet even so they may earn profits that are well above game-theoretic equilibrium levels. Future work will explore the dynamics of markets in which more sophisticated shopbots base their search on product at­ tributes as well as price, and in which pricebots use more sophisticated learning algorithms such as Q-learning.