We consider a task of scheduling with a common deadline on a single machine. Every player reports to a scheduler the length of his job and the scheduler needs to finish as many jobs as possible by the deadline. For this simple problem, there is a truthful mechanism that achieves maximum welfare in dominant strategies. The new aspect of our work is that in our setting players are uncertain about their own job lengths, and hence are incapable of providing truthful reports (in the strict sense of the word). For a probabilistic model for uncertainty our main results are as follows. 1) Even with relatively little uncertainty, no mechanism can guarantee a constant fraction of the maximum welfare. 2) To remedy this situation, we introduce a new measure of economic efficiency, based on a notion of a fair share of a player, and design mechanisms that are @math -fair. In addition to its intrinsic appeal, our notion of fairness implies good approximation of maximum welfare in several cases of interest. 3) In our mechanisms the machine is sometimes left idle even though there are jobs that want to use it. We show that this unfavorable aspect is unavoidable, unless one gives up other favorable aspects (e.g., give up @math -fairness). We also consider a qualitative approach to uncertainty as an alternative to the probabilistic quantitative model. In the qualitative approach we break away from solution concepts such as dominant strategies (they are no longer well defined), and instead suggest an axiomatic approach, which amounts to listing desirable properties for mechanisms. We provide a mechanism that satisfies these properties.
Cooperation in organisms, whether bacteria or primates, has been a difficulty for evolutionary theory since Darwin. On the assumption that interactions between pairs of individuals occur on a probabilistic basis, a model is developed based on the concept of an evolutionarily stable strategy in the context of the Prisoner's Dilemma game. Deductions from the model, and the results of a computer tournament show how cooperation based on reciprocity can get started in an asocial world, can thrive while interacting with a wide range of other strategies, and can resist invasion once fully established. Potential applications include specific aspects of territoriality, mating, and disease.  The concept of a perfect equilibrium point has been introduced in order to exclude the possibility that disequilibrium behavior is prescribed on unreached subgames. (Selten 1965 and 1973). Unfortunately this definition of perfectness does not remove all difficulties which may arise with respect to unreached parts of the game. It is necessary to reexamine the problem of defining a satisfactory non-cooperative equilibrium concept for games in extensive form. Therefore a new concept of a perfect equilibrium point will be introduced in this paper. In retrospect the earlier use of the word "perfect" was premature. Therefore a perfect equilibrium point in the old Sense will be called "subgame perfect". The new definition of perfectness has the property that a perfect equilibrium point is always subgame perfect but a subgame perfect equilibrium point may not be perfect. It will be shown that every finite extensive game with perfect recall has at least one perfect equilibrium point. Since subgame perfectness cannot be detected in the normal form, it is clear that for the purpose of the investigation of the problem of perfectness, the normal form is an inadequate representation of the extensive form. It will be convenient to introduce an "agent normal form" as a more adequate representation of games with perfect recall.