Players are rational if they always choose best replies given their beliefs. They are good predictors if the difference between their beliefs and the distribution of the other's actual strategies goes to zero over time. Learning is deterministic if beliefs are fully determined by the initial conditions and the observed data. (Bayesian updating is a particular example). If players are rational' good predictors, and learn deterministically, there are many games for which neither beliefs nor actions converge to a Nash equilibrium. We introduce an alternative approach to learning called prospecting in which players are rational and good predictors, but beliefs have a small random component. In any finite game, and from any initial conditions, prospecting players learn to play arbitrarily close to Nash equilibrium with probability one.

It is shown here that market crashes and bubbles can arise without external shocks. Sudden changes in behavior may be the result of endogenous information processing. Except for the daily observation of the market, there is no new information, no communication and no coordination between the participants.

This Paper studies the following online replacement problem. There is a real function f(t), called the flow rate, defined over a finite time horizon [0,T]. It is known that m% f(t) % M for some reals 0 % m < M. At time 0 an online player starts to pay money at the rate of f(0). At each time 0 < t % T the player may changeover and continue paying money at the rate f(t). The complication is that each such changeover incures some fixed penalty. The player is called online as at each time t the player knows f only over the time interval [0,t]. The goal of the player is to minimize the total cost comprised of cumulative payment flow plus change over costs. This formulation of the replacement problem has various interesting applications among which are: equipment replacement, supplier replacement, the menu cost problem and mortgagere financing. With respect to the competitive ratio performance measure, this paper seeks to determine the best possible competitive ratio achievable by an online replacement policy. Our results include the following: a general lower bound on the performance of any deterministic policy, a policy that is optimal in several special cases and a simple policy that is approximately optimal.

In this note, a congestion game is a noncooperative normal-form game in which the players share a common set of strategies. The payoff a player receives for playing a particular strategy depends only on the total number of players playing that strategy and decreases with that number in a manner which is specific to the particular player. The corresponding sequential move game is the perfect-information extensive-form game in which players choose their plays sequentially rather than simultaneously, and each player knows the plays of the previous players. We show that the backward induction path of this game is a pure-strategy Nash equilibrium of the simultaneous move game. We also show that, by changing the order of movers in the sequential move game, every pure-strategy Nash equilibrium of the simultaneous move game that is not Pareto dominated by another equilibrium can be obtained.

An interview conducted on June 30, 1995, which is to appear in the Selten Festschrift: Understanding strategic Interaction, edited by Wulf Albers, Werner Guth, Peter Hammerstein, Benny Moldovanu, and Eric van Damme, with the help of Martin Strobel, to be published by Springer in 1996. The interview ranges over a wide variety of topics related to Game Theory, with special emphasis on empirical applications, both of the cooperative and of the noncooperative theories.

Newly emerged bees learn to forage more efficiently as they gain experience. We hypothesized that foraging efficiency would increase as bees gain experience during the day, but would decrease overnight, due to loss of memory. To test this hypothesis, we allowed naive bombus terretris bumblebees to forage on two clusters of artificial flowers of unequal profitabilities during three consecutive days. Nectar intake rate, percentage visitation to the more profitable cluster, probing time and time intervals between visits were computed as measures of the bees' foraging efficiency. Nectar intake rates increased significantly during the day, and decreased partially but significantly after a night. There was much variation between individual bees in nectar intake rates. The bees did not show a preference for one of the clusters at the onset of the experiment, and no consistent increase in visitation to the more profitable cluster was found during single observation days for all bees. Most individuals did not visit the higher-reward cluster exclusively by the end of the third day. However, visitation to the higher-reward cluster did increase significantly when the first day of observation was compared to the third day. Preference for the higher-reward cluster increased over the first night but decreased significantly over the second night. Probing time and inter-visit intervals decreased significantly during observation days, and increased significantly after a night. The results indicate that bees learn to approach and probe flowers faster, as they gain experience, during a foraging day, but that these skills are partially forgotten overnight. Patch preference is formed more slowly. Once formed, it is also weakened overnight. Such partial forgetting may aid the bee in reacting quickly to overnight changes in resource profitability by modifying flower choices and handling techniques.

We study the repeated games with a bound on strategic entropy (Neyman and Okada (1996)) of player 1's strategy while player 2's strategy is unrestricted. The strategic entropy bound will be a function (N) of the number of repetitions N, and hence, so is the maximin value of N((N)) of the repeated game with such bound. Our interest is in the asymptotic behavior of N((N)) (as N ) under the condition the per stage entropy bound, (N)/N where 0. We characterize the asymptotics of N((N)) by a continuous function of . Specifically, it is shown that this function is the concavification of the maximin value of the stage game in which player 1's action is restricted to those with entropy at most . We also show that, for infinitely repeated games, if player 1's strategies are restricted to those with strategic entropy rate at most , then the maximin value () exists and it, too, equals the concavified function mentioned above evaluated at .

We analyze the set of equilibria of two-person repeated games with incomplete information on both sides. We show that each equilibrium generates a martingale with certain properties. Moreover, for games, satisfying a certain condition that we call "tightness", it is shown that the converse also holds: each such martingale generates an equilibrium.

Expert clinicians were given batteries of psychodiagnostic test results (Rorshach, TAT, Drow-A-Person, Bender-Gestalt, Wechsler) to analyze. For half, a battery came along with a suggestion that the person suffers from Borderline Personality disorder, and for half - that battery was accompanied by a suggestion that he suffers from Paranoid Personality disorder. In study 1, the suggestion was made indirectly, through a background story that preceded the test results. In study 2, the suggestion was made directly, by the instructions given. The experts saw in the tests what they hypothesized to be there. In particular, the target diagnoses were rated higher when they were hypothesized than when they were not.

Let X1, ... , Xn be n random variables, with cumulative distribution functions F1, ... , Fn. define %i := fi(XI) for all i, and let %(1) % ... % %(n) be the order statistics of the (%i)i. Let %1 % ... % %n be n numbers in the interval [0,1]. We show that the probability of the event R := %%(i) % %i for all 1 % i % n %) is at most mini %n%i/i%. Moreover, this bound is exact: for any given n marginal distributions (Fi)i, there exists a joint distribution with these marginals such that the probability of R is exactly mini %n%i/i%. This result is used in analyzing the significance level of multiple hypotheses testing. In particular, it implies that the R?ger tests dominate all tests with rejection regions of type R as above.

In their paper How Good is the Simplex Algorithm?, Klee and Minty exhibited a sequence of linear programs for which the number of pivot steps in the simplex algorithm grows exponentially with the dimensions of the program. We present a probabilistic model in which the expected numberof steps for a variant of the simplex method grows linearly with the dimensions. For programs with parallel pair of inequalities (lower and upper bounds), we present a model in which the expected number of steps from minimum to maximum is d. We also present related results concerning the expected complexity of multi-objective linear programming.

Consider a two-person repeated game (with complete information). Assume that one of the players - say player 1 - has the possibility to sow doubt, in the mind of his opponent, as to what his own (i.e., player 1's) payoffs are. This results in a two-person repeated game with incomplete information. It turns out that, by sowing this kind of doubt, a player can increase his minimal equilibrium payoff in the original game. We prove that this minimum is maximal when only one payoff matrix, which is equal to the negative payoff matrix of the opponent, is added. Thus, it is optimal for a player to make his opponent believe that, with some positive probability, he is playing a zero-sum game. We obtain two formulas for calculating this maximal minimum payoff. Finally, we look at the outcome when both players simultaneously sow doubt in this way.

We study repeated two-person zero-sum games in which one of the players has a restricted set of strategies. Restriction is imposed directly on the set of mixed strategies. To this end, we introduce a notion of entropy for mixed strategies as the means of bounding strategies available to a player. We derive a relation between the two types of strategies in terms of entropy. Using this relation together with certain properties of entropy, we show that if the number of repetitions grows faster than the entropy bound, then an unrestricted player can asymptotically hold a restricted player's payoff down to his maximin level in pure actions of the stage game. We consider implications of this result concerning the asymptotic behavior of the value finitely repeated games with finite automata and bounded recall.

We define ternary voting games (TVGs), a generalization of simple voting games (SVGs). In a play of an SVG each voter has just two options: voting `yes' or `no'. In a TVG a third option is added: abstention. Every SVG can be regarded as a (somewhat degenerate) TVG; but the converse is false. We define appropriate generalizations of the Shapley-Shubik and Banzhaf indices for TVGs. We define also the responsiveness (or degree of democratic participation) of a TVG and determine, for each n, the most responsive TVGs with n voters. We show that these maximally responsive TVGs are more responsive than the corresponding SVGs.

This paper presents a new family of optimal, 2-competitive, deterministic online list accessing algorithms. This family includes as members the well known MOVE-TO-FRONT (MTF) algorithm, and the recent, more "conservative" algorithm TIMESTAMP due to Albres.

In a tree enterprise, users reside at the nodes of the tree and their aim is to connect themselves, directly or indirectly, to the root of the tree. The construction costs of arcs of the tree are given by means of the arc-cost-function associated with the tree. Face to face with this tree enterprise, the bankruptcy venture is described in terms of the estate of the bankrupt concern and the claims of the various creditors. The objective of the paper is to provide conditions (on the claims and the surplus of the claims in the bankruptcy venture) which are sufficient and necessary for the bankruptcy venture to agree with some tree enterprise. It is established that the bankruptcy venture agrees with some tree enterprise if and only if the surplus of claims in the bankruptcy venture is at most the size of the second smallest claim (in the weak sense). For that purpose, both the tree enterprise as well as the bankruptcy venture are modelled as a cooperative game with transferable utility. Within the framework of cooperative game theory, the proof of the equivalence theorem concerning the tree enterprise game and the bankruptcy game, under the given circumstances, is based on graph theoretic tools in a tree structure.

Naive bumblebees were allowed to forage on 30 color-polymorphic artificial flowers, which were identical in morphology and reward schedule, but were marked by either a human-blue, human-green or a human-white landing surface. The probability of nectar rewards in the artificial flowers, and their spatial distribution, were manipulated experimentally. The bees' color choices in the different experimental treatments were compared. The proportions of visits to the three color morphs deviated significantly from the expected random choice (1/3-1/3-1/3) for more than 50% of the bees. Out of these bees, 38%, 32% and 30% formed a preference for human-blue, human-green and human-white, respectively. The frequency of non-random color choice, and the strength of the deviation from random choice, were highest when the different morphs were placed in separate clusters, lower when they were placed in adjacent clusters, and lowest when they were randomly intermingled. Non-random color choice was also more pronounced when the bees were rewarded according to a constant schedule, rather than probabilistically. A statistically significant preference for human-blue was found during the bees' first three visits. The bees' tendency for "runs" of consecutive visits to the same flower color can partially account for their non-random color choices. The specific color preferences of individuals could not be related to their early foraging experiences.

In Aumann (1976) - "Agreeing to Disagree" - it is shown that if there is a common prior then common knowledge of disagreement is impossible. This paper studies the converse proposition. The lack of a common prior is shown to yield common knowledge of disagreement in a variety of cases. However, an example demonstrates that this result cannot be generalized.

We look at a set % of states of the world which are defined as maximal consistent lists of formulae formed in a language which contains a knowledge operator ki for each agent i. The states of the world induce an information partition for each agent i such that all those % % % are included in the same information cell which contain the same range of knowledge for this agent (this range of knowledge we will call the agent's ken). We can then ask what it means that some agent i forgets which one of a variety of kens he has. This question can be answered easily if we use states of the world as primitives: then the answer is just to take a union over information cells. This does not make sense any more when states of the world are lists of formulae. We find a solution to this question for the case of one agent and show why the same solution cannot be used for the case of more than one agent. In an appendix, we apply results obtained before to analyze the j-operator (the knowing-whether operator). The larger context in which our question arose was to prove the Bachrach-Cave Agreement-Theorem in a model where states of the world are not primitives.

The environmental need to control the quality of the air is represented by a multi-players sequential game. One model is a two period game with n + 1 players, of which n are operators and one is an inspector. The game is analyzed via the solution concept of the strategies equilibrium (Nash equilibrium). The second model assumes that all operators are identical,i.e. the payoffs are the same to all operators. The equations that describe the Nash equilibrium, are solved analytically under this assumption, and enable us to compare games with a different number of operators (n). Numerical solutions are included. A discussion of the advantages and disadvantages of individual punishment vs. collective punishment appears in the last section. The model includes a parameter which varies from full individual punishment when the inspector raises an alarm (i.e. only the operators that acted illegally are fined), to full collective punishment (i.e. all operators are fined regardless their actions). Numerical results are added.