Hint, Extortion, and Guessing Games in the Best Choice Problem
- PDF / 121,449 Bytes
- 7 Pages / 594 x 792 pts Page_size
- 45 Downloads / 213 Views
HINT, EXTORTION, AND GUESSING GAMES IN THE BEST CHOICE PROBLEM S. I. Dotsenkoa† and A. V. Marynych a‡
UDC 519.83
Abstract. The best choice problem (also known as “the secretary problem”) is one of the classical in stochastic optimization. In this paper, we consider a modification of the classical secretary problem by adding the second player, who can either help the first player to find the best element by a hint or precludes him by imposing some restrictions on the search. Nash equilibrium has been found in the explicit form of mixed strategies for three different types of the game. The asymptotic behavior of diverse numerical quantities associated with the optimal strategies for both players, as the number of objects tends to infinity, has been studied. Keywords: best choice problem, Markov chain stopping, matrix game, Nash equilibrium, mixed strategy, threshold strategy. INTRODUCTION The following formulation of the best choice problem was considered in [1]. Let the best object should be randomly chosen among n objects. After getting acquainted with an object, it is necessary either to choose it or to reject. It is prohibited to return to an already considered object. The objects are arranged in a certain way according to the quality, i.e., qualities of any two objects are comparable with each other. Random acquaintance assumes that initially all the n ! permutations specifying the order of search of the objects are equiprobable. In what follows, by the best object we will call the object favorable for all n, and the maximum is the best object among k considered ones. It is obvious that during the search it is necessary to analyze the expediency of choosing some object only if it is maximum. It appears that the first object is maximum and the indices of the maximum objects form a k Markov chain with transition probabilities p( k , j ) = , j > k. Irrespective of whether the kth element was maximum or j( j -1) not, the probability of the event that among elements with indices k + 1, K , n the minimum index of the maximum element is k k , j > k, and with probability there is no maximum element in the sequence k + 1, K , n. j is equal to j( j -1) n It is proved that to choose the best object among n, one should adhere to the following strategy: first skip all elements with indices 1, K , k n - 1 and then choose the first maximum element whose index is no less than k n , where k n is defined from the double inequality 1 1 1 1 . (1) +K + £1< +K + kn n -1 k n -1 n -1 It turns out that tends to e -1 .
kn 1 ® as n ® ¥, and the probability of choosing the best object when using the described strategy n e
a
Taras Shevchenko National University of Kyiv, Kyiv, Ukraine, †[email protected]; ‡[email protected]. Translated from Kibernetika i Sistemnyi Analiz, No. 3, May–June, 2014, pp. 107–115. Original article submitted April 19, 2013. 1060-0396/14/5003-0419
©
2014 Springer Science+Business Media New York
419
HINT GAME Let the first player browse each element before the second player. The second player gets a un
Data Loading...
