# A Common Value Experimentation with Multiarmed Bandits

Authors: Xiujuan Gao; Hao Liang; Tong Wang
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

We study a value common experimentation with multiarmed bandits and give an application about the experimentation. The second derivative of value functions at cutoffs is investigated when an agent switches action with multiarmed bandits. If consumers have identical preference which is unknown and purchase products from only two sellers among multiple sellers, we obtain the necessary and sufficient conditions about the common experimentation. The Markov perfect equilibrium and the socially effective allocation inK-armed markets are discussed.


---

## Body

## 1. Introduction

A financial debate has arisen when we need to choose the best goods among multiple products. In Robbins [1], this problem is described as a decision maker facing N slot machines (called arms) and the maker has to choose one of them at each instantaneous time. Gittins and Jones [2] and Michael et al. [3] calculate the value of pulling an arm, i.e., Gittins index, in discrete time. Comparing the value to the Gittins index of all other arms, Michael et al. [3] present that the optimal strategy for an N-armed problem is an N-dimensional discounted Markov decision chain and the value pulling each arm itself is independent of the cutoff. Karatzas [4], Kaspi, and Mandelbaum [5] transform the problem into a standard optimal stopping problem. Bolton and Harris [6] and Bergemann and Välimäki [7] show that when there are K≥2 sellers who sell different products and N consumers whose preferences are identical (but unknown) in the market, the optimal strategies of consumers are to buy the products from the same seller; i.e., it is symmetric equilibria. Cohen and Solan [8] study two-armed bandit problems in the continuous time with the property ofLévy processes and obtain the Hamilton-Jacobi-Bellman (HJB) equation for the problem. They conclude that the optimal strategy is a cutoff strategy when the arms have two types. For other optimal strategies and control approaches, the reader is referred to [9–11] and the references therein.Jan and Xi [12] investigate that second derivatives of value functions are equal at the cutoff with value matching and smooth pasting (assume that the value function is V(x)∈C2(R+) and the cutoff is x∗∈R+. Value matching: V(x∗-)=V(x∗+) and smooth pasting: V′(x∗-)=V′(x∗+) which is discussed in [13, 14], where V(x-)≔limx→x-V(x) and V(x+)≔limx→x+V(x)), when there are two arms with different types, and conclude that the optimal strategy is an interval strategy in the market. In [12], an application is given about strategic pricing of two vendors in a competitive market. There are N≥2 consumers who have the same type either H or L. Two vendors produce two different kinds of goods for the two types, respectively. Jan and Xi [12] describe the socially efficient allocation and pricing strategies of two vendors in the market. Moreover, they use value matching, smooth pasting, and second derivatives of value functions to discuss the Markov perfect equilibrium and the socially efficient allocation.In this article, we investigate multiarmed bandits, while two-armed bandits are studied in [12]. We consider multiple sellers instead of two sellers. In general, there are multiple sellers to sell the same type of goods in the market, but the quality, utilities, and the prices of goods sold by each seller are different. Therefore, changing the number of arms from two to K≥2 is reasonable in the market. People believe that purchasing two products has the best effects to type H or L in the market. For example, the first seller is the highest utility to type H but is the lowest utility to type L. On the contrary, the second seller is the highest utility to type L but is the lowest utility to type H and other utilities are between about the two sellers to types H and L. Instinctively, we think that a rational consumer chooses goods only from the first two sellers but this is not perfect or this strategy needs some conditions. We discuss the necessary and sufficient conditions for this strategy.In order to obtain our conclusions under certain assumptions of the model for multiarmed bandits, using the methods used in [12], we calculate the optimal cutoff points by solving the corresponding ordinary differential equations. Then, we obtain the necessary and sufficient conditions for the strategy of which consumers purchase products from only two sellers among multiple sellers.The rest of the paper is as follows. In Section2, we introduce a multiarmed model under certain assumptions and show a conclusion about the model. In Section 3, we give an application for the model. In Section 3.1, we discuss optimal choice of consumers in the case of market equilibrium. Based on the optimal choice of consumers, we derive HJB equations for their utilities functions. Using solutions of the HJB equations, value matching, and smooth pasting, we get the cutoff point at Markov perfect equilibrium and the necessary and sufficient conditions about the common experimentation. In Section 3.2, we get the cutoff point at socially efficient allocation with the same way in Section 3.1. The relationship between the Markov perfect equilibrium and the socially efficient allocation in K-armed markets is discussed.


## 2. The Model

Jin and Xi [12] consider one agent and a bandit with 2 arms. We study multiarmed bandits and consider the case where there is only one real-valued state x(t)∈Υ and Υ∈R is a connect set. The instantaneous flow payoff of each arm is fj(x) at state x, j=1,2,…,K. Let r>0 be the discount rate. For each arm j, there is a probability space {Ωj,Fj,Pj} endowed with filtration {Ftj,t≥0} and Tj(t) is the total measure of time to time t when arm j has been chosen. From [12], we know that the updating of x in arm j, when there are K arms in the market, satisfies(1)dxjt=μjxt-dTjt+σjxt-dWjTjt+∑i≠j∫R-0Jjxt-,xiNjdTjt,dxi,where Wj(t) is a standard Brownian motion, Wj(t) is independent of Wi(t) (i≠j), and Nj is a Poisson random measure that is independent of Wj. The state x is updated from arm i, i=1,2,…,K and dx(t)=∑i=1Kdxi(t). Let Jj(x(t-),xi) be the change of the state when there is a Poisson jump. Equation (1) shows that the state changes from xj to xi (i≠j). Thus, (1) does not contain the case that state xj jump from other states. Because state xj can jump to any other states and any other states can jump back to xj, (1) contains all jump processes that describe the changes of state.In multiarmed bandit problem, the stochastic process{xt} is constructed on the product space {Ω,F}≔{Ω1,F1}×{Ω2,F2}×⋯×{ΩK,FK} with filtration Ft=⋁i=1KFTi(t)i. If x=x0, the agent chooses an allocation rule mt={1,2,…,K} adapted to filtration {Ft}t≥0 to solve the following optimal control problem:(2)vx=supmt⁡E∫t=0∞e-rtfmtxtdt,(3)s.tdxt=μmtxtdt+σmtxtdWt+∑i≠mt∫R-0Jmtxt-,xiNmtdt,dxi.Assumption 1 (see [12]).
LetΥ be a connected set. Assume that fj(x), μj(x), σj(x), and Jj(x,xi) for i≠j are C2 functions of x∈Υ.Assumption 2 (see [12]).
Assume that the first derivatives offj(x), μj(x), σj(x), and Jj(x,·) with respect to x are bounded. Namely, there exists M>0 such that for any x∈Υ, fj′x≤M, μj′x≤M, σj′x≤M, and ∂Jjx,xi/∂x≤M for each i≠j. Using (2) and the dynamic programming principle (the detailed process is in [15]), for any h>0, we obtain(4)vx=supmt⁡E∫t=0he-rtfmtxtdt+e-rhvxh.
Using Ito’s lemma fore-rtv(xt) and property of Poisson random measure (the property of Poisson random measure is in [13]), we get (5)de-rtvxt=-re-rtvxtdt+e-rtv′xtdxtc+12e-rtv′′xtdx,xt=-re-rtvxtdt+e-rtv′xtdxtc+12e-rtσmt2xtv′′xtdt+∑i=1,i≠mtK-1∫R-0Jmtxt-,xiNmtdt,dxi2+2∑1≤p<q≤K-1∫R-0Jmtxt-,xpNmtdt,dxp×∫R-0Jmtxt-,xqNmtdt,dxq=-re-rtvxtdt+e-rtv′xtdxtc+12e-rtσmt2xtv′′xtdt+∑i=1,i≠mtK-1∫R-0vx+Jmtxt-,xmt-vxNmtdt,dxi,where dxtc=μmt(xt)dt+σmt(xt)dWt.
Then, we have(6)e-rhvxh=vx+∫t=0h-re-rtvxtdt+e-rtv′xtdxtc+∫t=0h12e-rtσmt2xtv′′xtdt+∑i=1,i≠mtK-1∫t=0hvx+Jmtxt-,xmt-vxNmtdt,dxi.Substituting (6) into (4), using the mean value theorem of integrals and sending h→0, we get the HJB equation(7)rvx=supmt⁡fmtx+μmtxv′x+12σmt2xv′′x+∑i=1,i≠mtK-1∫R-0vx+Jmtxt-,xi-vxνmtdxi,where νmt is the finite intensity measure of Nmt. From [13], we know that there exists a unique solution to (1).We assume that optimal strategy of consumers is an interval strategy (see [14]). Namely, there exists K-1 points (cutoffs) x1,x2,…,xk-1 to partition the space Υ into K-1 intervals, where x1≤x2≤⋯≤xk-1. When i,j=1,2,…,K-2 and i≠j, (xi,xi+1)∩(xj,xj+1)=ϕ, we assume that if x∈(xj-1,xj), the agent chooses arm j, where j=1,2,…,K and x0≔inf{x}, xK≔sup{x}. Thus, we have(8)rvx=fjx+μjxv′x+12σj2xv′′x+∑i=1,i≠jK-1∫R-0vx+Jjxt-,xi-vxνjdxi.Using the conclusions in [12, 14], we have the value matching(9)vxj-=vxj+and the smooth pasting(10)v′xj-=v′xj+.Now, in the light of the value matching and smooth pasting, we have the following conclusion.Theorem 3.
Ifσj(x)>0 for all x∈Υ, j=1,2,…,K, a necessary condition for optimal solution xj is that v′′(x) satisfies v′′(xj-)=v′′(xj+) for any possible cutoffs xj.Proof.
On the basis of assumptionx∈(xj-1,xj), an agent chooses arm j, j=1,2,…,K. It derives that(11)fjx+μjxv′x+12σj2xv′′x+∑i=1,i≠jK-1∫R-0vx+Jjxt-,xi-vxνjdxi≤rvx.For x→xj and x>xj, inequality (11) becomes(12)fjxj+μjxjv′xj++12σj2xjv′′xj++∑i=1,i≠jK-1∫R-0vxj+Jjxj,xi-vxj+νjdxi≤rvxj+.
Due to the value matching, we have(13)fjxj+μjxjv′xj++12σj2xjv′′xj++∑i=1,i≠jK-1∫R-0vxj+Jjxj,xi-vxj+νjdxi≤rvxj-and(14)rvxj-=fjxj+μjxjv′xj-+12σj2xjv′′xj-+∑i=1,i≠jK-1∫R-0vxj+Jjxj,xi-vxj-νjdxi.From the smooth pasting, we obtain v′′(xj+)≤v′′(xj-). In the same way, we get v′′(xj-)≤v′′(xj+). Thus, we have v′′(xj-)=v′′(xj+) for any j=1,2,…,K.Theorem3 gives a necessary condition under which second derivatives of value functions are equal at every cutoff when there are K arms in the market.WhenK=2, i.e., there are two arms in the market; the agent has two states x1 and x2 in the model. In this case, we only need to consider that an agent jumps between the two states, i.e., mt={1,2}. Thus, there is one cutoff, which is discussed in [12].


## 3. Application

The application of Theorem3 is similar to that in [12]. The difference is that there are K≥2 sellers offering different products in the market. We index these sellers with j=1,2,…,K. We assume that all consumers have the same type i, either H or L. Let βjH and βjL be the utilities of consumers who buy good j with type H or L, respectively. We assume β1H>β2H>⋯>βKH and β1L<β2L<⋯<βKL, i.e., the more likely the consumers are to buy type H, the more tendency they choose the previous sellers. Therefore, we denote that x∈[0,1] is the common belief that the type is high and then the expected utility of controlling the seller j is fj(x)≔xβjH+(1-x)βjL. If we denote aj≔βjH-βjL and bj≔βjL, the utility is represented by(15)fjx=ajx+bj,where aj+bj<aj+1+bj+1 and bj>bj+1.At any time, all market participants observe all previous outcomes. Because of the influence caused by uncertain external factors, the flow utilityuji(t) has a noisy signal of the true value (the detailed introduction can be found in [12]). (16)dujit=ξjidt+σjdW~jt,where W~j(t) is independent of W~i(t)(i≠j).x is related to time and it is described as a learning process in [16], denoted by xt. Without loss of generality, we assume that there are nj consumers choosing seller j and ∑j=1Knj = N≥2. From the statements in [6, 7], we have that xt satisfies(17)dxt=∑j=1KnjΞjxdWjt,where Wj(t) is independent of Wi(t)(i≠j) and Ξj(x)≔x2(1-x)2aj/σj. We denote sj≔aj/σj.In the next subsection, the Markov perfect equilibrium and the socially efficient allocation inK-armed market are discussed.


### 3.1. Markov Perfect Equilibrium

Letpj denote the price of goods of seller j. The price is related to x at instantaneous time t. So pj is a mapping [0,1]→R, j=1,2,…,K. We denote αi as the choice of ith consumer which is related not only to his common belief x, but also to the prices of the sellers’ goods, i.e., αi:[0,1]×R×R×⋯×R︸The number ofRisK→{1,2,…,K}. A symmetric Markov perfect equilibrium is {α,p1,p2,…,pK}.When the choice of the previousN-1 consumers is observed, the utility of the Nth consumer is maximized. Let U(x) denote the maximum utility of this consumer and nj′ denote the number of choosing the jth seller. We have ∑j=1Knj′=N-1. There exists d∈{1,2,…,K} subject to nd′=nd-1 and ni′=ni, i≠d. Then, we have (18)rUx=max⁡f1x-p1x+12∑i=1KniΞix+Ξ1x-ΞdxU′′x⋮fd-1x-pd-1x+12∑i=1KniΞix+Ξd-1x-ΞdxU′′xfdx-pdx+12∑i=1KniΞixU′′xfd+1x-pd+1x+12∑i=1KniΞix+Ξd+1x-ΞdxU′′x⋮fKx-pKx+12∑i=1KniΞix+ΞKx-ΞdxU′′x. Due to the price competition, the consumer chooses equal utility for other sellers. Thus, we get (19)f1x-p1x+12∑i=1KniΞix+Ξ1x-ΞdxU′′x=⋯=fd-1x-pd-1x+12∑i=1KniΞix+Ξd-1x-ΞdxU′′x=fdx-pdx+12∑i=1KniΞixU′′x=fd+1x-pd+1x+12∑i=1KniΞix+Ξd+1x-ΞdxU′′x=⋯=fKx-pKx+12∑i=1KniΞix+ΞKx-ΞdxU′′x. Therefore, we obtain(20)fix-pix+12ΞixU′′x=fjx-pjx+12ΞjxU′′x,where i,j=1,2,…,K and i≠j.Now, we discuss the pricing of goods of sellers. DenoteVj(x) as the jth seller’s utility. If there are nj consumers buying goods j when the price is pj, we have(21)Vjx=E∫0∞e-rtnjpjxtdt,where dxt=∑j=1Knjxt(1-xt)sjdWj(t).From (21), we derive that(22)rVjx=njpjx+12∑i=1KniΞixVj′′x.We getnj=0 or N because all consumers choose only one seller (see [6, 7]). When nj=0, the utility of seller j is presented in the form(23)rVjx=N2ΞdxVj′′x,where we assume that all consumers choose seller d, i.e., j∈{1,2,…,K}-{d} and nd=N.When only one consumer chooses sellerj, i.e., nj=1, the utility of seller j is (24)rVjx=pjx+12N-1Ξdx+ΞjxVj′′x.As a rational market participant, when no consumer buys goods, the seller adjusts the price so that the payoff in this case is equal to the payoff when only one consumer chooses this seller. We obtain the price of goods of sellerj in the form(25)pjx=12Ξdx-ΞjxVj′′x.From (20), we get the price of seller d in the form(26)pdx=fdx-fjx+12Ξdx-ΞjxU′′x+Vj′′x.We haveN-1 cutoffs xj, j=1,2,…,N-1, where 0<x1≤x2≤⋯≤xj-1<1. When common belief x∈(xi-1,xi), consumer chooses seller i, i=1,2,…,K ( x0≔0, xK≔1). If x=xi, the utilities of consumers are indifferent when they choose seller i or i+1 due to value matching. When x≠xi, we have the conclusionTheorem 4.
All consumers only choose the first seller or the last seller in the market if and only if cutoffsxj, j=1,2,…,N-1, are the same and equal to (rD0-(b1-bk))/((a1-aK)-rD1), where (27)D0≔γ1+12s12+γK-12sK2b1-bKrC1+CKC1·CK,D1≔sK2-s12b1-bKr+s12γ1-12+sK2γK+12a1-aKrC1+CKC1·CK,C1≔12N-1s12λ1-γ1+12sK2λ1+γK,CK≔12N-1sK2λK-γK+12s12λK+γ1,γj≔1+8rNsj2,λ1≔1+8rN-1s12+sK2andλK≔1+8rN-1sK2+s12.Proof.
Firstly, we prove the sufficiency. When all cutoffs are equivalent and equal to(rD0-(b1-bk))/((a1-aK)-rD0), all consumers only choose the first seller or the last seller in the market.
Lettingx∗≔x1=⋯=xK-1, we have x∗=x1=xK-1. When x∈(0,x1), all consumers choose the first seller. From (25) and (26), we have(28)pKx=12Ξ1x-ΞKxVK′′xand(29)p1x=f1x-fKx+12Ξ1x-ΞKxU′′x+VK′′x.Substituting (29) into (22) yields(30)rV1x=Nf1x-fKx+12Ξ1x-ΞKxVK′′x-U′′x+N2Ξ1V1′′xSubstituting (28) and (29) into (22) gives rise to(31)rUx=fKx-12Ξ1x-ΞKxVK′′x+U′′x+N2Ξ1U′′x.
From (23), (30), and (31), for x∈(0,x1), we have(32)V1x=Nf1x-fKxr+P3xγ1+1/21-x-γ1-1/2-NP2xλ1+1/21-x-λ1-1/2VKx=P1xγ1+1/21-x-γ1-1/2Ux=fKxr+P2xλ1+1/21-x-λ1-1/2-P1xγ1+1/21-x-γ1-1/2.
Similarly, forx∈(xK-1,1), it has(33)V1x=Q1x-γK-1/21-xγK+1/2VKx=NfKx-f1xr+Q3x-γK-1/21-xγK+1/2-NQ2x-λK-1/21-xλK+1/2Ux=f1xr+Q2xλ+1/21-x-λ-1/2-Q1xγK+1/21-x-γK-1/2,where γj≔1+8r/Nsj2, λ1≔1+8r/((N-1)s12+sK2), λK≔1+8r/((N-1)sK2+s12), and Pξ and Qξ are constants, ξ=1,2,3.
Using value matching, smooth pasting, the second derivative condition, andx∗=x1=xK-1, we have V1(x∗-)=VK(x∗+), V1′(x∗-)=VK′(x∗+), V1′′(x∗-)=VK′′(x∗+), and U(x∗-)=U(x∗+). Therefore, we obtain(34)f1x∗-fKx∗r=φx∗C1+φx∗CK, where (35)φx≔γ1+12s12+γK-12sK2b1-bKr+sK2-s12b1-bKr+s12γ1-12+sK2γK+12a1-aKrx,C1≔12N-1s12λ1-γ1+12sK2λ1+γKand (36)CK≔12N-1sK2λK-γK+12s12λK+γ1.
Define(37)D0≔γ1+12s12+γK-12sK2b1-bKrC1+CKC1·CKand (38)D1≔sK2-s12b1-bKr+s12γ1-12+sK2γK+12a1-aKrC1+CKC1·CK.Thus, we get(39)f1x∗-fKx∗r=Do+D1x∗and(40)x∗=rD0-b1-bka1-aK-rD0.
Whenx∗≔x1=⋯=xK-1, (xi,xi+1)=ϕ, i=1,2,…,K-2, all consumers only choose the first seller or the last seller in the market.
The sufficiency of Theorem4 is proved.
Now, we prove the necessity. That all consumers choose only the first seller or the last seller in the market means that these cutoffs are the same and equal to(rD0-b1-bk)/((a1-aK)-rD0), x≠x∗. We prove it by contradiction.
Assumingxi≠xi+1, we get xi<xi+1, i=1,2,…,K-2. So (xi,xi+1)∩{[0,x∗)∪(x∗,1]}≠ϕ, i.e., ∃x0≠x∗, x0∈(xi,xi+1). When the common belief is x0, the optimal choice is the (i+1)th and i+1≠1 and i+1≠K. This is contradiction to the proposition of which all consumers choose only the first seller or the last seller. So xi=xi+1, i=1,2,…,K-2. According to the proof of the sufficiency, we have x∗=x1=xK-1=(rD0-b1-bk)/((a1-aK)-rD0). The necessity of Theorem 4 is proved.Theorem4 shows the necessary and sufficient conditions for the consumers’ choice. We find that when the consumers only choose the first seller and the last seller, the multiarmed bandits problem would be attributed to the two-armed bandits. In other words, other sellers gradually disappear in the market because they have no sales. The multiarmed bandit problem is transformed into the two-armed bandits in the situation discussed in [12].


### 3.2. Socially Efficient Allocation

We consider the optimal choice of planners when they face multiarmed bandit problem. Let the total social surplus function bew(x). We have(41)wx=supn1,n2,…,nKE∫0∞e-rt∑j=1Knjtfjxtdt(42)s.t.dxt=∑j=1Knjtxt1-xtsjdWjt.Assume thatΠj(x) is the total social surplus in a neighborhood of x if a planner choose seller j. From (41), we have(43)rΠjx=Nfjx+12ΞjxΠj′′x,where j=1,2,…,K.Solving the ordinary differential equation (43), we get(44)Π1x=Nf1xr+C11xγ1+1/21-x-γ1-1/2,Πjx=Nfjxr+Cj1xγj+1/21-x-γj-1/2+Cj2x-γj-1/21-xγj+1/2j=2,…,K-1,ΠKx=NfKxr+CK2x-γK-1/21-xγK+1/2,where Ci1 and Ci2, i=1,2,…,K, are constants.We denotex^1,x^2,…,x^K-1 subjecting to 0<x^1≤x^2≤⋯≤x^K-1<1 as the cutoffs of the choice for the planner. When x∈(x^i-1,x^i), the optimal choice is the ith seller, i=1,2,…,K and x^0=0, x^K=1. Due to value matching, smooth pasting, and the second derivative conditions, one has(45)Πjx^j-=Πj+1x^j+,Πj′x^j-=Πj+1′x^j+,Πj′′x^j-=Πj+1′′x^j+,where j=1,2,…,K-1.There are(3K-3) unknown parameters and (3K-3) equations in system (45) with [xβ1-x)1-β′≠xβ(1-x)1-β, for all β>1, i.e., the coefficient matrix of system (45) is nonsingular. Thus, system (45) has a unique solution.The planner chooses from the first seller or theK-th seller when x^1=x^2=⋯=x^K-1. Let x†≔x^1=x^2=⋯=x^K-1. System (45) becomes(46)Π1x†=ΠKx†,Π1′x†=ΠK′x†,Π1′′x†=ΠK′′x†.We obtain (47)x†=b1-bkγ1+1/2s12+γK-1/2sK2aK-a1s12γ1-1/2+sK2γK+1/2+b1-bKs12-sK2.The results in [12] introduce the necessary and sufficient condition under which the Markov perfect equilibrium with cautious strategies is socially efficient with two-armed bandits.Corollary 5.
WhenK≥2, N≥2, the consumers’ cutoffs are x∗, and the planner’s cutoffs are x†, the Markov perfect equilibrium with cautious strategies is socially efficient if and only if s1=sK. Moreover, x∗>x†(x∗<x†) when s1>sK(s1<sK).The proof of Corollary5 is similar to that of Theorem 2 in [12]. We omit its proof.Corollary5 shows that the necessary and sufficient conditions under which the Markov perfect equilibrium with cautious strategies is socially efficient when the cutoffs are multiarmed bandits. Jin and Xi [12] present the conditions in the case of two-armed market. Thus, Theorem 4 extends parts of results in [12].According to the condition in Corollary5, when (β1H-β1L)/σ1=(βKH-βKL)/σK, we obtain that the Markov perfect equilibrium with cautious strategies is socially efficient. If σ1=σk, we obtain β1H-βKH=β1L-βKL. In the light of our initial hypothesis, we have β1H=βKH and β1L=βKL; i.e., all sellers are identical in the market.


## 3.1. Markov Perfect Equilibrium

Letpj denote the price of goods of seller j. The price is related to x at instantaneous time t. So pj is a mapping [0,1]→R, j=1,2,…,K. We denote αi as the choice of ith consumer which is related not only to his common belief x, but also to the prices of the sellers’ goods, i.e., αi:[0,1]×R×R×⋯×R︸The number ofRisK→{1,2,…,K}. A symmetric Markov perfect equilibrium is {α,p1,p2,…,pK}.When the choice of the previousN-1 consumers is observed, the utility of the Nth consumer is maximized. Let U(x) denote the maximum utility of this consumer and nj′ denote the number of choosing the jth seller. We have ∑j=1Knj′=N-1. There exists d∈{1,2,…,K} subject to nd′=nd-1 and ni′=ni, i≠d. Then, we have (18)rUx=max⁡f1x-p1x+12∑i=1KniΞix+Ξ1x-ΞdxU′′x⋮fd-1x-pd-1x+12∑i=1KniΞix+Ξd-1x-ΞdxU′′xfdx-pdx+12∑i=1KniΞixU′′xfd+1x-pd+1x+12∑i=1KniΞix+Ξd+1x-ΞdxU′′x⋮fKx-pKx+12∑i=1KniΞix+ΞKx-ΞdxU′′x. Due to the price competition, the consumer chooses equal utility for other sellers. Thus, we get (19)f1x-p1x+12∑i=1KniΞix+Ξ1x-ΞdxU′′x=⋯=fd-1x-pd-1x+12∑i=1KniΞix+Ξd-1x-ΞdxU′′x=fdx-pdx+12∑i=1KniΞixU′′x=fd+1x-pd+1x+12∑i=1KniΞix+Ξd+1x-ΞdxU′′x=⋯=fKx-pKx+12∑i=1KniΞix+ΞKx-ΞdxU′′x. Therefore, we obtain(20)fix-pix+12ΞixU′′x=fjx-pjx+12ΞjxU′′x,where i,j=1,2,…,K and i≠j.Now, we discuss the pricing of goods of sellers. DenoteVj(x) as the jth seller’s utility. If there are nj consumers buying goods j when the price is pj, we have(21)Vjx=E∫0∞e-rtnjpjxtdt,where dxt=∑j=1Knjxt(1-xt)sjdWj(t).From (21), we derive that(22)rVjx=njpjx+12∑i=1KniΞixVj′′x.We getnj=0 or N because all consumers choose only one seller (see [6, 7]). When nj=0, the utility of seller j is presented in the form(23)rVjx=N2ΞdxVj′′x,where we assume that all consumers choose seller d, i.e., j∈{1,2,…,K}-{d} and nd=N.When only one consumer chooses sellerj, i.e., nj=1, the utility of seller j is (24)rVjx=pjx+12N-1Ξdx+ΞjxVj′′x.As a rational market participant, when no consumer buys goods, the seller adjusts the price so that the payoff in this case is equal to the payoff when only one consumer chooses this seller. We obtain the price of goods of sellerj in the form(25)pjx=12Ξdx-ΞjxVj′′x.From (20), we get the price of seller d in the form(26)pdx=fdx-fjx+12Ξdx-ΞjxU′′x+Vj′′x.We haveN-1 cutoffs xj, j=1,2,…,N-1, where 0<x1≤x2≤⋯≤xj-1<1. When common belief x∈(xi-1,xi), consumer chooses seller i, i=1,2,…,K ( x0≔0, xK≔1). If x=xi, the utilities of consumers are indifferent when they choose seller i or i+1 due to value matching. When x≠xi, we have the conclusionTheorem 4.
All consumers only choose the first seller or the last seller in the market if and only if cutoffsxj, j=1,2,…,N-1, are the same and equal to (rD0-(b1-bk))/((a1-aK)-rD1), where (27)D0≔γ1+12s12+γK-12sK2b1-bKrC1+CKC1·CK,D1≔sK2-s12b1-bKr+s12γ1-12+sK2γK+12a1-aKrC1+CKC1·CK,C1≔12N-1s12λ1-γ1+12sK2λ1+γK,CK≔12N-1sK2λK-γK+12s12λK+γ1,γj≔1+8rNsj2,λ1≔1+8rN-1s12+sK2andλK≔1+8rN-1sK2+s12.Proof.
Firstly, we prove the sufficiency. When all cutoffs are equivalent and equal to(rD0-(b1-bk))/((a1-aK)-rD0), all consumers only choose the first seller or the last seller in the market.
Lettingx∗≔x1=⋯=xK-1, we have x∗=x1=xK-1. When x∈(0,x1), all consumers choose the first seller. From (25) and (26), we have(28)pKx=12Ξ1x-ΞKxVK′′xand(29)p1x=f1x-fKx+12Ξ1x-ΞKxU′′x+VK′′x.Substituting (29) into (22) yields(30)rV1x=Nf1x-fKx+12Ξ1x-ΞKxVK′′x-U′′x+N2Ξ1V1′′xSubstituting (28) and (29) into (22) gives rise to(31)rUx=fKx-12Ξ1x-ΞKxVK′′x+U′′x+N2Ξ1U′′x.
From (23), (30), and (31), for x∈(0,x1), we have(32)V1x=Nf1x-fKxr+P3xγ1+1/21-x-γ1-1/2-NP2xλ1+1/21-x-λ1-1/2VKx=P1xγ1+1/21-x-γ1-1/2Ux=fKxr+P2xλ1+1/21-x-λ1-1/2-P1xγ1+1/21-x-γ1-1/2.
Similarly, forx∈(xK-1,1), it has(33)V1x=Q1x-γK-1/21-xγK+1/2VKx=NfKx-f1xr+Q3x-γK-1/21-xγK+1/2-NQ2x-λK-1/21-xλK+1/2Ux=f1xr+Q2xλ+1/21-x-λ-1/2-Q1xγK+1/21-x-γK-1/2,where γj≔1+8r/Nsj2, λ1≔1+8r/((N-1)s12+sK2), λK≔1+8r/((N-1)sK2+s12), and Pξ and Qξ are constants, ξ=1,2,3.
Using value matching, smooth pasting, the second derivative condition, andx∗=x1=xK-1, we have V1(x∗-)=VK(x∗+), V1′(x∗-)=VK′(x∗+), V1′′(x∗-)=VK′′(x∗+), and U(x∗-)=U(x∗+). Therefore, we obtain(34)f1x∗-fKx∗r=φx∗C1+φx∗CK, where (35)φx≔γ1+12s12+γK-12sK2b1-bKr+sK2-s12b1-bKr+s12γ1-12+sK2γK+12a1-aKrx,C1≔12N-1s12λ1-γ1+12sK2λ1+γKand (36)CK≔12N-1sK2λK-γK+12s12λK+γ1.
Define(37)D0≔γ1+12s12+γK-12sK2b1-bKrC1+CKC1·CKand (38)D1≔sK2-s12b1-bKr+s12γ1-12+sK2γK+12a1-aKrC1+CKC1·CK.Thus, we get(39)f1x∗-fKx∗r=Do+D1x∗and(40)x∗=rD0-b1-bka1-aK-rD0.
Whenx∗≔x1=⋯=xK-1, (xi,xi+1)=ϕ, i=1,2,…,K-2, all consumers only choose the first seller or the last seller in the market.
The sufficiency of Theorem4 is proved.
Now, we prove the necessity. That all consumers choose only the first seller or the last seller in the market means that these cutoffs are the same and equal to(rD0-b1-bk)/((a1-aK)-rD0), x≠x∗. We prove it by contradiction.
Assumingxi≠xi+1, we get xi<xi+1, i=1,2,…,K-2. So (xi,xi+1)∩{[0,x∗)∪(x∗,1]}≠ϕ, i.e., ∃x0≠x∗, x0∈(xi,xi+1). When the common belief is x0, the optimal choice is the (i+1)th and i+1≠1 and i+1≠K. This is contradiction to the proposition of which all consumers choose only the first seller or the last seller. So xi=xi+1, i=1,2,…,K-2. According to the proof of the sufficiency, we have x∗=x1=xK-1=(rD0-b1-bk)/((a1-aK)-rD0). The necessity of Theorem 4 is proved.Theorem4 shows the necessary and sufficient conditions for the consumers’ choice. We find that when the consumers only choose the first seller and the last seller, the multiarmed bandits problem would be attributed to the two-armed bandits. In other words, other sellers gradually disappear in the market because they have no sales. The multiarmed bandit problem is transformed into the two-armed bandits in the situation discussed in [12].


## 3.2. Socially Efficient Allocation

We consider the optimal choice of planners when they face multiarmed bandit problem. Let the total social surplus function bew(x). We have(41)wx=supn1,n2,…,nKE∫0∞e-rt∑j=1Knjtfjxtdt(42)s.t.dxt=∑j=1Knjtxt1-xtsjdWjt.Assume thatΠj(x) is the total social surplus in a neighborhood of x if a planner choose seller j. From (41), we have(43)rΠjx=Nfjx+12ΞjxΠj′′x,where j=1,2,…,K.Solving the ordinary differential equation (43), we get(44)Π1x=Nf1xr+C11xγ1+1/21-x-γ1-1/2,Πjx=Nfjxr+Cj1xγj+1/21-x-γj-1/2+Cj2x-γj-1/21-xγj+1/2j=2,…,K-1,ΠKx=NfKxr+CK2x-γK-1/21-xγK+1/2,where Ci1 and Ci2, i=1,2,…,K, are constants.We denotex^1,x^2,…,x^K-1 subjecting to 0<x^1≤x^2≤⋯≤x^K-1<1 as the cutoffs of the choice for the planner. When x∈(x^i-1,x^i), the optimal choice is the ith seller, i=1,2,…,K and x^0=0, x^K=1. Due to value matching, smooth pasting, and the second derivative conditions, one has(45)Πjx^j-=Πj+1x^j+,Πj′x^j-=Πj+1′x^j+,Πj′′x^j-=Πj+1′′x^j+,where j=1,2,…,K-1.There are(3K-3) unknown parameters and (3K-3) equations in system (45) with [xβ1-x)1-β′≠xβ(1-x)1-β, for all β>1, i.e., the coefficient matrix of system (45) is nonsingular. Thus, system (45) has a unique solution.The planner chooses from the first seller or theK-th seller when x^1=x^2=⋯=x^K-1. Let x†≔x^1=x^2=⋯=x^K-1. System (45) becomes(46)Π1x†=ΠKx†,Π1′x†=ΠK′x†,Π1′′x†=ΠK′′x†.We obtain (47)x†=b1-bkγ1+1/2s12+γK-1/2sK2aK-a1s12γ1-1/2+sK2γK+1/2+b1-bKs12-sK2.The results in [12] introduce the necessary and sufficient condition under which the Markov perfect equilibrium with cautious strategies is socially efficient with two-armed bandits.Corollary 5.
WhenK≥2, N≥2, the consumers’ cutoffs are x∗, and the planner’s cutoffs are x†, the Markov perfect equilibrium with cautious strategies is socially efficient if and only if s1=sK. Moreover, x∗>x†(x∗<x†) when s1>sK(s1<sK).The proof of Corollary5 is similar to that of Theorem 2 in [12]. We omit its proof.Corollary5 shows that the necessary and sufficient conditions under which the Markov perfect equilibrium with cautious strategies is socially efficient when the cutoffs are multiarmed bandits. Jin and Xi [12] present the conditions in the case of two-armed market. Thus, Theorem 4 extends parts of results in [12].According to the condition in Corollary5, when (β1H-β1L)/σ1=(βKH-βKL)/σK, we obtain that the Markov perfect equilibrium with cautious strategies is socially efficient. If σ1=σk, we obtain β1H-βKH=β1L-βKL. In the light of our initial hypothesis, we have β1H=βKH and β1L=βKL; i.e., all sellers are identical in the market.


## 4. Conclusion

We study a common value experimentation with multiarmed bandits and present its application. This extends two-armed bandits in [12] to multiarmed bandits. We derive the HJB equation with multiarmed bandits. In the application, we get the necessary and sufficient conditions for the choices of consumers from two sellers. The necessary and sufficient conditions guarantee that the Markov perfect equilibrium with cautious strategies is socially efficient. In future, we need to solve all the cutoffs in system (45) when these cutoffs are different and give general solutions about these cutoffs.



---

*Source: 4791590-2018-07-30.xml*