## 1 Introduction
An (oblivious) adversary knows \(\mathcal{A}\)'s algorithm completely but does not know the result of the coin flip and hence cannot determine which point (\(a\) or \(c\)) has the server missing in the next step. The adversary would make the next request on \(a\) but this time \(a\) has a server with probability \(1/2\) and \(\mathcal{A}\) can reduce its cost. Without giving details, it is not hard to show that this algorithm \(\mathcal{A}\) - with the randomized action for a request to \(b\) and a greedy action one for others - has a competitive ratio of 1.5. Indeed, one would imagine that it might be quite straightforward to design randomized algorithms which perform significantly better than deterministic ones for the \(2\)-server problem. As mentioned above this has not been the case. Only few special cases have yielded success. [PERSON], [PERSON], and [PERSON] gave a randomized algorithm for the 2-server problem on the line, whose competitive ratio is slightly better than 2 (\(\frac{155}{78}\approx 1.987\)) [11]. One other result by [PERSON] et. al. [12] uses a novel technique, the knowledge state method, to derive a \(\frac{19}{12}\) competitive randomized algorithm for the special case of Cross Polytope Spaces. Using similar techniques a new result for paging (the \(k\)-server problem in uniform spaces) was recently obtained. [PERSON] et al. [13] gave an \(H_{k}\)-competitive randomized algorithm which requires only \(O(k)\) memory for \(k\)-paging. (Though the techniques in the current paper are inspired by this work, the knowledge state method is not used here.) [PERSON] and [PERSON] showed that if specific three positions are given, then an optimal randomized algorithm for the 2-server problem over those three points can be derived in principle by using linear programming [14]. However, they do not give actual values of its competitive ratio and to this date the problem is still open even for the 2-server 3-points case. Finally, we mention other somewhat related work in the realm of online computation: see the work of [PERSON] et al. [15] for ski-rental problems, [PERSON] et al. [16] for list access problems, and [PERSON] et al. [17] for paging. **Our Contribution**. In this paper, we prove that the randomized competitive ratio of the 2-server 3-point problem in a general metric space is at most 1.5897 and also we conjecture that it is at most \(e/(e-1)\approx 1.5819\). Thus we give an upper bound that matches the lower bound within a small \(\varepsilon\). The underlying idea is to find a finite set \(S\) of triangles (i.e. three points) such that if the competitive ratio for each triangle in \(S\) is at most \(c\), then the competitive ratio for all triangles in any metric space is at most \(c\cdot\delta(S)\) where \(\delta(S)\geq 1\) is a value determined by \(S\). To bound the competitive ratio for each triangle in \(S\), we apply linear programming. As we consider larger sets, the value of \(\delta(S)\) becomes smaller and approaches 1. Thus the upper bound of the general competitive ratio also approaches the maximum competitive ratio of triangles in \(S\) and we can obtain arbitrarily close upper bounds by increasing the size of the computation. Our result in this paper strongly depends on computer simulations similar to earlier work based on knowledge states. Indeed, there are several successful examples of such an approach, which usually consists of two stages; (i) reducing infinitely many cases of a mathematical proof to finitely many cases (where this number is still too large for a \"standard proof\") and (ii) using computer programs to analyze the finitely many cases. See the work in [18; 19; 20; 21; 22] for design and analysis of such algorithms. In particular, for online competitive analysis, [PERSON] proved the currently best upper bound, 1.5889, for online bin-packing [23]. Also with this approach, [PERSON] et al. [24] obtained an optimal competitive ratio for the online knapsack problem with resource augmentation by buffer bins.