J. Ling: jeffl[email protected] K. Xiao: [email protected] D. Yang: [email protected] Online Algorithms Modeled After Mousehunt Jeffrey Ling, Kai Xiao, Dai Yang January 9, 2015 5 1 0 2 n Abstract a J In this paper we study a variety of novel online algorithm problems inspired by the game Mouse- 8 hunt. We consider a number of basic models that approximate the game, and we provide solutions to ] these models using Markov Decision Processes, deterministic online algorithms, and randomized online S algorithms. We analyze these solutions’ performance by deriving results on their competitive ratios. D . s c 1 Introduction [ 1 Mousehunt is a Facebook game developed in 2006 by HitGrab Inc. The goal of the game is to catch mice v 0 using a variety of traps. Each species of mice is worth a certain amount of points and gold. Although 2 collecting gold helps the player afford better traps, collecting points is the ultimate goal of the game. One 7 1 particularly focus-worthy aspect of the game is that Ronza, a nomadic merchant, visits for short periods of 0 time roughly once a year, and sells valuable exclusive traps during these unannounced visits. . 1 0 We introduce simple models of this game that involve optimizing the number of points gained over a 5 finite time interval. While the problem’s overall description will resemble the classic ski rental problem, the 1 : finer details will differ, and we will be able to show different lower bounds on the competitive ratio. We will v i approach these problems using both deterministic and randomized online strategies to try to achieve the X best possible competitive ratios. r a In this paper, we will use the convention that the competitive ratio r is always less than 1, i.e. if our algorithm earns value C , and the optimal offline algorithm earns value C , then C ≥r·C . A OPT A OPT WebeginbyproposingasimplemodelforMousehunt,wherewestartwithabasictrapthatcanselectively catch mice worth one point or one gold. Assuming that we don’t know when Ronza will arrive next, and that we have some estimate x of the benefit we gain from Ronza’s traps, we are able to prove that it is optimal to hunt for gold if and only if the ratio of the gold cost of the trap c to the timespan T satisfies c/T ≤1− √1 . That is, the potential amount of benefit we can gain is worth it iff the cost of the trap is not x √ too high. In this case, we obtain a competitive ratio of 1/ x. If we randomize our strategy, it turns out we can do better than 1/2-competitive on average. 1 J. Ling: jeffl[email protected] K. Xiao: [email protected] D. Yang: [email protected] 2 A Simple Model 2.1 Modeling Mousehunt InthegameMousehunt,playersattempttocatchdifferenttypesofmicewhichgiveplayersrewardsofpoints and gold when caught. The reward can therefore be represented as a vector (p,g) where p is the amount of points and g is the amount of gold. In the real game, players can use different trap setups to increase their catch rates against certain sets of mice, and the player can select which mice to target by changing their trap setup (by arming certain types of cheese or traveling to certain locations). Traps can be purchased for certainamountsofgoldfromtrapsmithsorfromRonza,whovisitsthemouse-huntinglandofGnawniaonce a year. 2.2 Initial Problem Suppose that there are three traps available, A , A , and B. Using trap A will allow the player to catch a 1 2 1 mouse worth 1 gold, and using trap A will allow the player to catch a mouse worth 1 point. Using trap B 2 will allow the player to catch a mouse worth x points for x>1. Traps A and A are available at the start 1 2 of the game while trap B can only be purchased from the wandering merchant Ronza. There are T time steps in total. Ronza appears for a single time step at some unknown time y, and sells trap B at cost c. Before each time step, and also at the end, the player makes a decision to lay down either trap A , trap A , 1 2 or B, and then immediately reaps the rewards of their choosing. This setup poses two different but related problems: one, to determine an optimal trap-choosing strategy to maximize the expected payoff given some distribution assumptions, and two, to find a strategy that maximizes the competitive ratio. 3 Markov Decision Process Analysis 3.1 Distribution and Optimality Fortherestofthissection,wewillassumethatRonza’sarrivaltimeisdistributeduniformlyamong1,2,...,T. Wecanperformsimilaranalyseswithdifferentdistributions,butitwillbemostcleartoanalyzetheuniform distribution case. We establish the following lemma concerning optimal online algorithms which solve this problem. Lemma 3.1. The online algorithm, if it is optimal, can be assumed to take on one of the following formats: • Only hunt for the mouse worth 1 point. • Hunt for the mouse worth 1 coin until c coins are gathered or until the merchant arrives. Purchase the trap B if possible when the merchant arrives, and only hunt for mice worth a maximum amount of points afterward. Proof. First, suppose that the online algorithm O at time t decides to earn points and at the next time 1 step t+1 decides to collect gold. Then, consider the alternative online algorithm O that collects gold at t 2 2 J. Ling: jeffl[email protected] K. Xiao: [email protected] D. Yang: [email protected] and earns points at t+1. Both of these choices are conditioned on Ronza having not arrived yet, as it is clear that the only right decision after Ronza arrives is to earn points. If Ronza appears after time t+1 or before time t, both algorithms perform equally well. If Ronza appears between times t and t+1, then the algorithm O will have performed worse. Thus, any deterministic optimal online algorithm will collect gold 1 at the beginning, if at all, and hence take on one of the two prescribed formats. 3.2 Markov Decision Process OneapproachforsolvingtheinitialproblemistoviewitasaMarkovDecisionProcess. Forafixedx,define f(c,T) to be the optimal decision when there are T time steps remaining and we require c more coins for Ronza’s trap; the lemma tells us that f(c,T) can only take on two forms: aim for points, or aim for c coins. Define g(c,T) to be expected payoff in points when pursuing this optimal decision. The base cases go as follows. When c = 0, we have f(c,T) as aim for points and g(c,T) = x+1(T +1), because Ronza comes 2 in the middle of the time steps on average. When c = 1, we have g(c,T) as max(x+1T,T +1): the latter 2 payoff is achieved by aiming for points, and the former payoff is achieved by aiming for a single coin. When T =1,c>1, we have f(c,T) as aim for points and g(c,T)=2. Then: Theorem3.2. Inthestate(c,T)whereT >1andc>0,f(c,T)andg(c,T)canbedeterminedbycomparing T +1 and T−1g(c−1,T −1)+1. If the latter is larger, then it is the expected payoff, and the optimal move T f(c,T) is to aim for c gold. Otherwise, if the former is larger, then it is the expected payoff, and the optimal move f(c,T) is to aim for points. Proof. By the lemma, we may reduce the optimal decision to two possibilities: aim for points, or aim for c coins. If we decide to aim for points, the payoff will be 1+g(c,T −1). However, it is not rational to aim for coins in future time steps if we do not aim for coins now. Hence, the payoff must evaluate to 1+g(c,T −1)=1+T. Otherwise, if we decide to aim for c coins, then our payoff will depend on whether or not Ronza arrives in the next time step. If Ronza arrives in the next time step, then we have no choice but to gain 1 point after all remaining time steps, accruing a total of T points. This occurs with probability 1. T If Ronza arrives after the next time step, then her arrival time will be uniformly distributed among the remaining T −1 time steps, just as in the state (c−1,T −1). This reduction allows us to conclude that the payoff is g(c−1,T −1), and occurs with probability T−1. T Thus, the expected payoff when aiming for c coins is T−1g(c−1,T −1)+ 1 ·T = T−1g(c−1,T −1)+1. T T T BetweenthispayoffandthepayoffofT+1fromgreedilyamassingpoints,whicheveroneislargerwilldictate both f(c,T) and g(c,T). Theorem 3.3. Let r = c. Then asymptotically, f(c,T) will dictate that it is optimal to catch mice to aim T for c gold iff r ≤1− √1 . x Proof. We will no longer keep track of unneeded additive constants as we are determining asymptotic be- havior. Suppose that Ronza’s arrival time is y. We already know from the lemma that the alternative to catching mice to aim for c gold is catching mice to aim for points. The latter yields a payoff of T (in fact, T +1). Now we will compute the payoff of the former in a non-recursive fashion. 3 J. Ling: jeffl[email protected] K. Xiao: [email protected] D. Yang: [email protected] • Case 1: Ronza comes after time c. This means that c ≤ y, and decisions made according to this algorithm will earn y −c+x(T −y) points: y−c points from mice worth 1 point each, and x(T−y) points from mice worth x points each. The average value of y here is c+T. 2 • Case 2: Ronza comes before time c. This means c>y, and the player can never afford trap B, so the algorithmwillsimplycatchmiceworth1pointforallremainingtimesteps,yieldingT−y points. The average value of y here is c. 2 Thismeansthatifwedecidetoaimforccoins,ourexpectedgaininpointsis T−c·(c+T−c+x(T−c+T))+ T 2 2 c(T − c). Equalizing the payoffs of the two decisions allows us to determine the asymptotic boundary: T 2 T −c c+T c+T c c T = ·( −c+x(T − ))+ (T − ) T 2 2 T 2 x+1 1=(1−r)·(1−r)( )+r·(1−r/2) 2 x x−1 0= r2−xr+ 2 2 0=xr2−2xr+x−1 Solving this quadratic and taking the root such that r < 1 yields r = 1− √1 . Therefore, the asymptotic x behavior of this Markov Decision Process can be summarized as: until Ronza makes an appearance, aim for c coins if the state (c,T) satisfies c ≤1− √1 , and aim for points otherwise. T x Below, we present a few values of g(c,T) when x = 2, that is to say, when trap B is twice as effective as trap A. Bolded entries represent states in which f(c,T) dictates that aiming for c coins is strictly better than aiming for points. Notice that the boundary between the two strategies being optimal closely follows the line c=(1− √1 )T, as shown in the theorem above. 2 (c,T) 1 2 3 4 5 6 7 8 9 10 0 3 4.5 6 7.5 9 10.5 12 13.5 15 16.5 1 2 3 4.5 6 7.5 9 10.5 12 13.5 15 2 2 3 4 5 6 7.3 8.7 10.2 11.7 13.2 3 2 3 4 5 6 7 8 9 10 11.5 4 2 3 4 5 6 7 8 9 10 11 5 2 3 4 5 6 7 8 9 10 11 It is not difficult to generalize this table for all x. Note that for a given (c,T), we can use dynamic programming to fill in this table and compute f(c,T) and g(c,T) in O(cT) time. However, for large values of c,T, we can bypass Markov Decision Processes altogether and use Theorem 3.3 to compute them in O(1) time. OuranalysessofarreliedonthedistributionofRonza’sarrivaltimebeinguniform. Ifthedistributionis not known, however, then Markov Decision Processes cannot be used to model the decision problem. Next, we will show a solution to the algorithm online problem against any adversary. 4 J. Ling: jeffl[email protected] K. Xiao: [email protected] D. Yang: [email protected] 4 Competitive Analysis Model In this section we analyze online algorithms to solve the initial problem without a known probability dis- tribution. We examine both an optimal deterministic online algorithm, and a randomized online algorithm that achieves the best possible asymptotic competitive ratio. 4.1 Competitive Ratio Analysis: Deterministic Iftheonlinealgorithmdecidedonlytoearnpoints,theworstcasescenarioisthattheoptimalofflinealgorithm was to earn c gold and buy trap B when Ronza arrived to earn x points per subsequent mouse. This means thatc≤y,andtheofflinealgorithmwouldgarnermax(y−c+x(T−y),T)points. Ifmax(y−c+x(T−y),T)= T, the competitive ratio is 1. We now analyze the case when max(y−c+x(T −y),T)=(y−c)+x(T −y), where the competitive ratio of the two algorithms is T . (y−c)+x(T−y) We can find an upper bound on the reciprocal of this fraction to find a lower bound on this ratio. Let r = c. Then the reciprocal of the ratio can be upper bounded as follows. T (cid:18) (cid:19) (y−c)+x(T −y) c 1−x =x− +y T T T c (cid:18)1−x(cid:19) (cid:16) c(cid:17) ≤x− +c =x 1− =x(1−r) T T T where we used the fact that (1−x) is negative and c≤y. The competitive ratio is thus lower bounded by 1 . x(1−r) If the online algorithm decided to collect gold to try to buy the trap, the worst case scenario is that Ronza appears before the algorithm has collected enough gold to purchase the trap. In this case, c>y, and the online algorithm would earn T −y points (it would earn gold until the merchant arrived at time y, after which it would earn points) and the offline optimal algorithm would earn T points. The competitive ratio here is T−y. Here we find that the ratio is T y c 1− >1− =1−r T T Thus, given knowledge of x,c,T, we can choose our strategy based on the larger of the values 1 and x(1−r) 1−r to achieve the best competitive ratio. Since these two expressions vary in opposite directions as r increases, the worst case occurs when the two expressions are equal, i.e. 1 1 =(1−r) ⇐⇒ 1−r = √ x(1−r) x Thus,sinceouranalysiswasworstcase,weobtainatightlowerboundof √1 onourcompetitiveratio. Thus x this deterministic algorithm is always √1 competitive for all values of r. x 4.2 Competitive Ratio Analysis: Randomized Here we describe and analyze a randomized online algorithm that achieves a worst case competitive ratio of 1/2 for all values of x, c, and T. 5 J. Ling: jeffl[email protected] K. Xiao: [email protected] D. Yang: [email protected] First, if x(T −c) < T, then it is always optimal just to go for points because going for the trap would result in y −c+x(T −y) ≤ x(T −c) < T points at the end. This information is available to the online algorithm so the online algorithm is exactly the same as the offline one in this case. Thus, we just have to analyze the case that x(T −c)≥T. As before, any optimal online algorithm will either only aim for points or it will collect gold until Ronza arrives or until it has collected c gold, after which it will collect points and buy Ronza’s trap if possible. The randomized algorithm is to choose to try to gather gold for Ronza’s trap with probability q and to choose to aim for points only with probability 1−q. We will determine q later based on x and r = c. T Call the gold gathering strategy S and the point gathering strategy S . Let S denote the randomly chosen g p strategy. Given our choice of q, the adversary’s goal is to choose Ronza’s arrival time y so that the competitive ratio is minimized. Our goal is to choose a q to maximize this minimal value. If y <c then the competitive ratio is  T−y if S =S T g 1 if S =S p If y ≥c then the competitive ratio is  1 if S =S g  T if S =S (y−c)+x(T−y) p Thus the overall competitive ratio, denoted by R(x,c,T), is  (cid:16) (cid:17)  q· T−y +(1−q) :y <c R(x,c,T)= T  q+(1−q) T :y ≥c (y−c)+x(T−y) Suppose q has been chosen already. If the adversary chooses y <c, then R(x,c,T) is minimized when y is maximized, or when y =c−1≈c. If y ≥c, then minimizing R(x,c,T) involves maximizing (y−c)+x(T −y)=xT −c+y(1−x) which occurs when y is minimized since x>1. Thus in this case the adversary will choose y =c. Thus we get that   q·(cid:0)T−c(cid:1)+(1−q)=1− cq :y <c R(x,c,T)= T T (cid:16) (cid:17)  q+(1−q) T = T + 1− T q :y ≥c x(T−c) x(T−c) x(T−c) Note that the coefficient of q is negative in the case y <c and the coefficient of q is positive in the case y ≥ c since x(T −c) ≥ T. As q increases, R(x,c,T) goes down in the case y < c and goes up in the case y ≥c. 6 J. Ling: jeffl[email protected] K. Xiao: [email protected] D. Yang: [email protected] The two possible expressions for R(x,c,T) thus change in opposite directions as q is varied. Thus, if we want to maximize the minimum of these two numbers, we have to set them equal. This gives (cid:18) (cid:19) T T c + 1− q =1− q x(T −c) x(T −c) T (cid:18) (cid:19) T c T ⇐⇒ q 1− + =1− x(T −c) T x(T −c) (cid:18)x(T −c)(T)−T2+cx(T −c)(cid:19) −T +x(T −c) ⇐⇒ q = x(T −c)(T) x(T −c) −T2+xT(T −c) ⇐⇒ q = x(T −c)(T)−T2+cx(T −c) xT2−T2−cxT q = xT2−T2−c2x This gives the optimal value of q given x, c, and T. If we let r = c, we can rewrite this as T x−1−rx q = x−1−r2x We can also rewrite the condition x(T −c)≥T as x(1−r)≥1 ⇐⇒ x−xr ≥1 x−1 ⇐⇒ ≥r x Plugging this value of q back into R(x,c,T), we get that the competitive ratio of this randomized algorithm is c xr−r−r2x (x−1)(1−r) R(x,c,T)=1− q =1−rq =1− = T x−1−r2x x−1−r2x To find a lower bound on the competitive ratio of R, we need to minimize R(x,c,T) over all values of x, c, and T. Since R only depends on the ratio r = c asymptotically, we can just consider R(x,r). T To minimize R, we compute the partial derivative ∂R −(x−1)(x−1−r2x)−(−2rx)(x−1)(1−r) = ∂r (x−1−r2x)2 (x−1)(−(x−1−r2x)+2rx−2r2x) = (x−1−r2x)2 (x−1)(−r2x+2rx−x+1) = (x−1−r2x)2 R is minimized when the partial derivative is 0, or at the endpoints. At the endpoint r = 0 we get R(x,r)=1, and at the endpoint r = x−1, we know x−1=rx, so x rx(1−r) R(x,r)= =1 rx−r2x When the partial derivative is 0, we have that (x−1)(1−x(1−r)2)=0 7 J. Ling: jeffl[email protected] K. Xiao: [email protected] D. Yang: [email protected] Since x>1, solving this gives 1 r =1− √ x This value of r is valid because we know that r =1− √1 <1− 1 = x−1. Plugging this value of r back into x x x R(x,r) we get that (cid:16) (cid:16) (cid:17)(cid:17) (x−1) 1− 1− √1x 1(cid:18) 1 (cid:19) R(x,r)= = √ +1 (cid:16) (cid:17)2 2 x x−1− 1− √1 x x We can find the minimum value of this over all x. If we let x range from 1 to ∞ we see that R(x,r)> 1 2 for all x. One way to intuitively derive the same competitive ratio is that the optimal offline algorithm clearly either goes for gold for Ronza’s trap or goes for points the entire time. Thus, a basic randomized algorithm would just flip a fair coin. If the coin landed heads, it would choose to go for gold, and if it landed tails, it would choose to go for points. 1 of the time the randomized algorithm will match the optimal offline 2 algorithm, so we are at least 1 competitive. 2 The result we showed was a proof that the algorithm was 1 competitive for all values of x, c, and T. 2 However, in reality, for most values of x, c, and T, the competitive ratio our randomized algorithm obtains is R(x,r), which, for most values of r, is much better than the ratio obtained by single randomized coin flip algorithm. As an example, consider the graphs shown in Figure 1 of R(x,r) for the cases x=4 and x=100 for the appropriate range of r ∈(cid:0)0,x−1(cid:1). x Figure 1: Left plot: x=4. Right plot: x=100. 4.3 Proof of Optimality of Randomized Algorithm We will conclude this section with a proof that for any randomized online algorithm, an asymptotic com- petitive ratio of 1 over all values of x, c, and T is optimal using Yao’s minimax principle. 2 Yao’sminimaxprinciplestatesthattheexpectedcostofarandomizedalgorithmontheworstcaseinput is no better than the worst case probability distribution of inputs for a deterministic algorithm that works best for that worst case distribution. Thus, we simply have to present a probability distribution such that no deterministic algorithm can perform very well for it. Itisnotdifficulttofindsuchadistribution. Giventheparametersx,c,andT,wecandefinetwopossible inputs(whicharejustvaluesofy,Ronza’sarrivaltime)andgivethemasinputstothedeterministicalgorithm 8 J. Ling: jeffl[email protected] K. Xiao: [email protected] D. Yang: [email protected] with probability 1 each. The first input is y =c and the second input is y =c−1. Then, the deterministic 2 algorithm can be analyzed as follows. • Case1: Thedeterministicalgorithmgatherscoinsforthefirstcsteps(assumingRonzadoesn’tappear). Then, for the input y =c, the deterministic algorithm will be 1-competitive. For the input y =c−1, at time t = c−1 the algorithm will realize that it can not buy the trap, and so it will then gather points afterwards. This gives us an overall competitive ratio of (cid:18) (cid:19) 1 T −c 1 1+ = (1+(1−r)) 2 T 2 • Case2: Thedeterministicalgorithmdoesanythingelse. Then,thismeansattimet=c,thealgorithm will have less than c gold. Then, for the input y = c, the algorithm will fail to buy the trap. For y = c−1, the algorithm will also fail to buy the trap, and at best it will be 1-competitive. The algorithmwillhaveearnedatmostcpointsinthefirstctimesteps. Theoptimalofflinealgorithmwill buy the trap for c gold in the case t=c. Thus the overall competitive ratio is (cid:18) (cid:19) (cid:18) (cid:19) (cid:18) (cid:19) 1 c+T −c 1 T 1 1 +1 ≤ +1 = 1+ 2 (y−c)+x(T −y) 2 x(T −c) 2 x(1−r) In that special case that r =1− √1 , we know that the competitive ratio of this deterministic algorithm x (cid:16) (cid:17) will be equal to 1 1+ √1 . Thus, as x approaches infinity, any optimal deterministic algorithm for this 2 x input will be at best 1 competitive, so 1 competitive is as good as any randomized algorithm can be for the 2 2 original problem. 5 Unknown Cost, Fixed Arrival Time In this section, we explore a variant of our initial problem. Now, suppose that Ronza’s arrival time y is known, but the cost c of buying trap B is unknown. 5.1 Online and Offline Algorithms First, we consider the offline algorithm. If c is known, then this reduces to our initial offline problem. Therefore, if c ≤ y, the optimal algorithm will get max(y−c+x(T −y),T) points, and if c > y, then the algorithm gets T points. Anydeterministiconlinealgorithmcanbecharacterizedbyanumberm≤y,whereitcollectsgoldform of the first y time steps, and hunts for points otherwise. It will buy Ronza’s trap at time y if it is affordable at time y. Now, there are two possible outcomes: • If the algorithm manages to collect c gold, i.e. m ≥ c, then it is always optimal to buy trap B if possible. Then the algorithm earns a total of y−m+x(T −y) points. • If m<c, then the algorithm earns T −m points. 9 J. Ling: jeffl[email protected] K. Xiao: [email protected] D. Yang: [email protected] Inordertofindacompetitiveratioforthisonlineproblem,weconsidertheproblemfromtheperspective of the adversary. For given choices of c and m, we have the following cases and known ratios for the online and offline algorithms: 1. If c>y, we have a ratio of T−m T 2. If m<c≤y, and y−c+x(T −y)<T, we have a ratio of T−m T 3. If m<c≤y, and y−c+x(T −y)≥T, we have a ratio T−m y−c+x(T−y) 4. If m≥c, and y−c+x(T −y)<T, we have a ratio of y−m+x(T−y) T 5. If m≥c, and y−c+x(T −y)≥T, we have a ratio of y−m+x(T−y) y−c+x(T−y) As the adversary, our job is to design c for fixed m in order to produce the smallest ratio. Note that since cases1and2producethesameratio, andtherealwaysexistsactosatisfycase1, weneednotconsidercase 2. Similarly, because y−m+x(T −y)≥T −m ⇐⇒ (x−1)(T −y)≥0 is true for any m, case 4 is redundant given case 1. Now notice that as the ratio in case 5 is an increasing function of c, its minimum is achieved at c = 0. Thus, if we compare the ratios in cases 1 and 5, we have T −m y−m+x(T −y) < ⇐⇒ Ty+xT2−xTy−my−xTm+mxy <Ty−Tm+xT2−xyT T y+x(T −y) Canceling terms and rearranging, we obtain 0<m(x−1)(T −y) which is always true. Thus, case 5 is redundant given case 1. It remains to compare the ratios of cases 1 and 3, and for an online algorithm’s choice of m, it is the adversary’s goal to choose c to obtain the smaller ratio. Note that the value of c that minimizes ratio 3 is c=m+1, assuming such a c satisfies the constraints, so we are left with two ratios to compare: T−m from T case 1, and T−m from case 3. y−m−1+x(T−y) In words, case 1 corresponds to when both offline and online algorithm cannot buy Ronza’s trap, and case 3 corresponds to when the offline can and does buy the trap while the online cannot, with conditions c≤(x−1)(T −y) and m<c≤y. 5.2 Worst Case Analysis Suppose the online algorithm chooses a value of m = min((cid:98)(x−1)(T −y)(cid:99),y). In this case, no integral value of c can satisfy the constraints c ≤ (x−1)(T −y) and m < c ≤ y in case 3, so the resulting ratio is T−(x−1)(T−y) or T−y, depending on whether or not (x−1)(T −y)≤y. T T In the other case, suppose the online algorithm chooses m < min((cid:98)(x − 1)(T − y)(cid:99),y). The worst competitive ratios that the adversary can return are T−m and T−m . The latter expression can be T y−m−1+x(T−y) 10