00000cab a22000003a 4500 UP-99796217608823550 Buklod 20231007234830.0 m |o d | ta 090508s xx d | ||r ||||| || DENGII eng Deng, Xiaotie The Cost of Derandomization Computability or Competitiveness. pp. 786-802 Recently, much work has been done in game theory towards understanding the bounded rationality of players in infinite games. This requires the strategies of realistic players to be restricted to have bounded resources of reasoning. In this paper, we discuss infinite two-person games, focusing on the case where our player follows a computable strategy and the adversary may use any strategy, which formulates the notion of computer against extremely formidable nature. In this context, we say that an infinite game of semicomputably determinate if either the adversary has a winning strategy or our player has a computable winning strategy. We show that, whereas all open games are semicomputably determinate, there is a semicomputably inderterminate closed game. Since we want to prove an indeterminacy result for a closed games and since the adversary's strategy set is uncountable and our player's strategy set is countable, our proof for the indeterminacy result requires a new diagonalization technique, which might be useful in other similar cases. Our study of semicomputable games was inspired by online computing problems. In this direction, we discuss several possible applications to derandomization in online computing, with the restriction that the strategies of our player should be computable. We also study the power of randomization for the classical case where our player is allowed to play according to unrestricted strategies. An indeterminate game is obtained for which both players have a simple randomized winninig strategy agaist all of the deterministic strategies of the opponent. Online algorithm. Computability. Game theory. Derandomization. SIAM journal on computing. 26, 3 (1997). FO UPD DENG-II Article