Randomized algorithms A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performan ...

are algorithms that employ a degree of randomness as part of their logic. These algorithms can be used to give good average-case results (complexity-wise) to problems which are hard to solve deterministically, or display poor

worst-case In computer science, best, worst, and average cases of a given algorithm express what the resource usage is ''at least'', ''at most'' and ''on average'', respectively. Usually the resource being considered is running time, i.e. time complexity, b ...

complexity. An algorithmic game theoretic approach can help explain why in the average case randomized algorithms may work better than deterministic algorithms.

Formalizing the game

Consider a

zero-sum game Zero-sum game is a mathematical representation in game theory and economic theory of a situation which involves two sides, where the result is an advantage for one side and an equivalent loss for the other. In other words, player one's gain is e ...

between player A, whose

strategies Strategy (from Greek στρατηγία ''stratēgia'', "art of troop leader; office of general, command, generalship") is a general plan to achieve one or more long-term or overall goals under conditions of uncertainty. In the sense of the "art ...

are deterministic algorithms, and player B, whose strategies are inputs for A's algorithms. The cost of a strategy profile is the running time of A's chosen algorithm on B's chosen input. Therefore, player A tries to minimize the cost, and player B tries to maximize it. In the world of pure strategies, for every algorithm that A chooses, B may choose the most costly input – this is the worst-case scenario, and can be found using standard

complexity analysis In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms—the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that re ...

. But in the real world, inputs are normally not selected by an ‘evil opponent’ – rather, they come from some distribution over inputs. Since this is the case, if we allow the algorithms to also be drawn from some distribution, we may look at the game as one that allows

mixed strategies In game theory, a player's strategy is any of the options which they choose in a setting where the outcome depends ''not only'' on their own actions ''but'' on the actions of others. The discipline mainly concerns the action of a player in a game ...

. That is, each player chooses a distribution over its strategies.

Analysis

Incorporating mixed strategies into the game allows us to use von Neumann's

minimax Minimax (sometimes MinMax, MM or saddle point) is a decision rule used in artificial intelligence, decision theory, game theory, statistics, and philosophy for ''mini''mizing the possible loss for a worst case (''max''imum loss) scenario. When de ...

theorem: :

\min_R \max_D T(A,D) = \max_D \min_A T(A,D) \,

where ''R'' is a distribution over the algorithms, ''D'' is a distribution over inputs, ''A'' is a single deterministic algorithm, and ''T''(''A'', ''D'') is the average running time of algorithm a on input ''D''. More specifically: :

T(A,D) = \,\underset{\operatorname{E (A,X) \,

If we limit the set of algorithms to a specific family (for instance, all deterministic choices for pivots in the

quick sort Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. Overall, it is slightly faster than ...

algorithm), choosing an algorithm A from R is equivalent to running a randomized algorithm (for instance, running quick sort and randomly choosing the pivots at each step). This gives us an insight on Yao's principle, which states that the expected cost of any

randomized algorithm A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performan ...

for solving a given problem, on the worst-case input for that algorithm, can be no better than the expected cost, for a worst-case random

probability distribution In probability theory and statistics, a probability distribution is the mathematical function that gives the probabilities of occurrence of different possible outcomes for an experiment. It is a mathematical description of a random phenomenon i ...

on the inputs, of the

deterministic algorithm In computer science, a deterministic algorithm is an algorithm that, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states. Deterministic algorithms are by far ...

that performs best against that distribution. Non-cooperative games Randomized algorithms