A Course on Cooperative Game Theory

Introduction

This is an innocuous looking question with a deep answer. We will not attempt to explore the question in its full generality (We refer the reader to Aho, Hopcroft and Ullman (1974) for a comprehensive discussion.). Instead, a high level view will be adopted. An intuitive answer is that an algorithm is a finite sequence of elementary operations with the objective of performing some (computational) task. Let us take this as an acceptable answer and consider several aspects of it in more detail.

Elementary operations: A natural question to ask is how elementary is ‘elementary’? The idea of Turing machines formalises an elementary operation as simply reading or writing a symbol and/or moving a tape head one cell to the left or writing on an infinite tape divided into cells where it is possible to write one symbol on any cell. It is possible to start from this simple notion and obtain algorithms for very complex tasks. In fact, it is a hypothesis that Turing machines capture the exact notion of algorithms. We, however, will not work with the Turing machine model. The reason is that the simplicity of the model makes it quite cumbersome to express higher level ideas. Instead, the elementary operations that we will consider will be at a higher level and include arithmetic and logical operations. This is also the usual practice in the study of algorithms. One works at a higher level knowing that, in theory, all algorithms can be reduced to the Turing machine model.

Finite sequence: The finiteness condition of an algorithm implies that it must always halt. Procedures which continue indefinitely will not be considered as algorithms. The notion of Turing machines can be extended to cover such procedures, but, we will not need to consider them here. A word about the sequence of operations in an algorithm will also be in order.