We consider the complexity of finding a Correlated Equilibrium in an n-player game in a model that allows the algorithm to make queries for players' utilities at pure strategy profiles. Many randomized regret-matching dynamics are known to yield an approximate correlated equilibrium quickly: in time that is polynomial in the number of players, n, the number of strategies of each player, m, and the approximation error, 1/?. Here we show that both randomization and approximation are necessary: no efficient deterministic algorithm can reach even an approximate equilibrium and no efficient randomized algorithm can reach an exact equilibrium.

We model constitutions by effectivity functions. We assume that the constitution is common knowledge among the members of the society. However, the preferences of the citizen are private information. We investigate whether there exist decision schemes (i. e., functions that map profiles of (dichotomous) preferences on the set of outcomes to lotteries on the set of social states), with the following properties: i) The distribution of power induced by the decision scheme is identical to the effectivity function under consideration; and ii) the (incomplete information) game associated with the decision scheme has a Bayesian Nash equilibrium in pure strategies. If the effectivity function is monotonic and superadditive, then we find a class of decision schemes with the foregoing properties. When applied to n-person games in strategic form, a decision scheme d is a mapping from profiles of (dichotomous) preferences on the set of pure strategy vectors to probability distributions over outcomes (or equivalently, over pure strategy vectors). We prove that for any feasible and individually rational payoff vector of a strategic game, there exists a decision scheme that yields that payoff vector as a (pure) Nash equilibrium payoff in the game induced by the strategic game and the decision scheme. This can be viewed as a kind of purification result.

We introduce asymptotic analysis of stochastic games with short-stage duration. The play of stage $k$, $k'geq 0$, of a stochastic game $'Gamma_'delta$ with stage duration $'delta$ is interpreted as the play in time $k'delta'leq t0$ as the stage duration $'delta$ goes to $0$, and study the asymptotic behavior of the value, optimal strategies, and equilibrium. The asymptotic analogs of the discounted, limiting-average, and uniform equilibrium payoffs are defined. Convergence implies the existence of an asymptotic discounted equilibrium payoff, strong convergence implies the existence of an asymptotic limiting-average equilibrium payoff, and exact convergence implies the existence of an asymptotic uniform equilibrium payoff.

Are good people motivated to behave in accordance the moral truth whatever it is? Michael Smith, who has named this motivation the de-dicto moral motivation, famously criticized it. According to Smith, good people are instead motivated directly by more concrete moral concerns, such as 'the well-being of their fellows, people getting what they deserve, justice, equality, and the like . Here I argue for the non-Smithian view that good people have (also) a de-dicto moral motivation. The argument runs roughly as follows: given that good people tend to behave appropriately, and that in some situations it is appropriate to reevaluate one s underived moral beliefs, good people tend to seriously reevaluate underived moral beliefs sometimes. Theories of motivation have to account for this fact (a point overlooked by Smith and his respondents). What motivates a good person to pay attention to evidence that is contrary to her underived moral beliefs? What does she aim for in reevaluating those beliefs? I argue that the view that good people are motivated to act morally de-dicto is in a better position to explain the relevant facts about good people s reevaluation of underived moral beliefs.

We construct a continuum of games on a countable set of players that does not possess a measurable equilibrium selection that satisfies a natural homogeneity property. The explicit nature of the construction yields counterexamples to the existence of equilibria in models with overlapping generations and in games with a continuum of players.

We present a discounted stochastic game with a continuum of states, finitely many players and actions, such that although all transitions are absolutely continuous w.r.t. a fixed measure, it possesses no stationary equilibria. This absolute continuity condition has been assumed in many equilibrium existence results, and the game presented here complements a recent example of ours of a game with no stationary equilibria but which possess deterministic transitions. We also show that if one allows for compact action spaces, even games with state-independent transitions need not possess stationary equilibria.

We present an example of a discounted stochastic game with a continuum of states, finitely many players and actions, and deterministic transitions, that possesses no measurable stationary equilibria, or even stationary approximate equilibria. The example is robust to perturbations of the payoffs, the transitions, and the discount factor, and hence gives a strong nonexistence result for stationary equilibria. The example is a game of perfect information, and hence it also does not possess stationary extensive-form correlated equilibrium. Markovian equilibria are also shown not to exist in appropriate perturbations of our example.

Simon (2003) presented an example of a 3-player Bayesian games with no Bayesian equilibria but it has been an open question whether or not there are games with no approximate Bayesian equilibria. We present an example of a Bayesian game with two players, two actions and a continuum of states that possesses no approximate Bayesian equilibria, thus resolving the question. As a side benefit we also have for the first time an an example of a 2-player Bayesian game with no Bayesian equilibria and an example of a strategic-form game with no approximate Nash equilibria. The construction makes use of techniques developed in an example by Y. Levy of a discounted stochastic game with no stationary equilibria.

Being a product of evolutionary pressures, it would not be surprising to find that what seems to be a limitation of the cognitive system is actually a fine-tuned compromise between a set of competing needs. This thesis is demonstrated using the case of the limited capacity of short-term memory, which is often regarded as the prime example of a cognitive limitation.

The acquaintance principle (AP) and the view it expresses have recently been tied to a debatesurrounding the possibility of aesthetic testimony, which, plainly put, deals with the questionwhether aesthetic knowledge can be acquired through testimony-typically aesthetic and non-aesthetic descriptions communicated from person to person. In this context a number of suggestions have been put forward opting for a restricted acceptance of AP. This paper is an attempt to restrict AP even more

In their seminal works, Arrow (1965) and Pratt (1964) defined two aspects of risk aversion: absolute risk aversion and relative risk aversion. Based on their definitions, we define two aspects of risk: absolute risk and relative risk. We consider situations in which, by making an investment, an agent exchanges a certain amount of wealth w by a random distributed level of wealth W. In such situations, we define absolute risk as the riskiness of a gamble that is distributed as W-w, and relative risk as the riskiness of a security that is distributed as W/w. We measure absolute risk by the Aumann and Serrano (2008) index of riskiness and relative risk by an equivalent index that we develop in this paper. The two concepts of risk do not necessarily agree on which one of two investments is riskier, and hence they capture two different aspects of risk.

We extend Aumann's theorem (Aumann, 1987) in deriving correlated equilibria as a consequence of common priors and common knowledge of rationality by explicitly allowing for non-rational behavior. We replace the assumption of common knowledge of rationality with a substantially weakernotion, p-belief of rationality, where agents believe the other agents are rational with probabilities p or more. We show that behavior in this case constitutes a constrained correlated equilibrium of a doubled game satisfying certain p-belief constraints and characterize the topological structure of the resulting set of p-rational outcomes. We establish continuity in the parameters p and show that, for p sufficiently close to one, the p-rational outcomes are close to the correlated equilibria and, with high probability, supported on strategies that survive the iterated elimination of strictly dominated strategies. Finally, we extend Aumann and Dreze's theorem (Aumann and Dreze, 2008) on rational expectations of interim types to the broader p-rational belief systems, and also discuss the case of non-common priors.

Myerson's classic result provides a full description of how a seller can maximize revenue when selling a single item. We address the question of revenue maximization in the simplest possible multi-item setting: two items and a single buyer who has independently distributed values for theitems, and an additive valuation. In general, the revenue achievable from selling two independent items may be strictly higher than the sum of the revenues obtainable by selling each of themseparately. In fact, the structure of optimal (i.e., revenue-maximizing) mechanisms for two itemseven in this simple setting is not understood.In this paper we obtain approximate revenue optimization results using two simple auctions: that of selling the items separately, and that of selling them as a single bundle. Our main results (which are of a "direct sum" variety, and apply to any distributions) are as follows. Selling theitems separately guarantees at least half the revenue of the optimal auction; for identicallydistributed items, this becomes at least 73% of the optimal revenue. For the case of k > 2 items, we show that selling separately guarantees at least a c/log^2 k fraction of the optimal revenue; for identically distributed items, the bundling auction yields at least a c/log k fraction of the optimal revenue.

A new and fast learning method is described in the context of teaching a program to play chess. A theory of the meaning of a position evaluation is developed, and is then confronted with a large collection of games played by masters or other programs. The program learns by fitting its evaluation to better predict the results of the games. The method has been employed by a top-rated program for the past 10 years, and has earned several world championships and successful matches against the world's best grandmasters for the program. The effectiveness of the method is demonstrated by showing its successful prediction of known playing strength of the programs.

We consider small-influence anonymous games with a large number of players $n$ where every player has two actions. For this class of games we present a best-reply dynamic with the following two properties. First, the dynamic reaches Nash approximate equilibria fast (in at most $cn log n$ steps for some constant $c>0$). Second, Nash approximate equilibria are played by the dynamic with a limit frequency of at least $1-e^-c'n$ for some constant $c'>0$.

We prove that every continuous value on a space of vector measure market games $Q$, containing the space of nonatomic measures $NA$, has the textitconic property, i.e., if a game $vin Q$ coincides with a nonatomic measure $nu$ on a conical diagonal neighborhood then $varphi(v)=nu$. We deduce that every continuous value on the linear space $mathcal M$, spanned by all vector measure market games, is determined by its values on $mathcalLM$ - the space of vector measure market games which are Lipschitz functions of the measures.

Every continuous-time stochastic game with finitely many states and actions has a uniform andlimiting-average equilibrium payoff.

We study non-zero-sum continuous-time stochastic games, also known as continuous-time Markov games, of fixed duration. We concentrate on Markovian strategies. We show by way of example that equilibria need not exist in Markovian strategies, but they always exist in Markovian public-signal correlated strategies. To do so, we develop criteria for a strategy profile to be an equilibrium via differential inclusions, both directly and also by modeling continuous-time stochastic as differential games and using the Hamilton-Jacobi-Bellman equations. We also give an interpretation of equilibria in mixed strategies in continuous-time, and show that approximate equilibria always exist.

We show that the no betting characterisation of the existence of common priors over finite type spaces extends only partially to improper priors in the countably infinite state space context: the existence of a common prior implies the absence of a bounded agreeable bet, and the absence of a common improper prior implies the existence of a bounded agreeable bet. However, a type space that lacks a common prior but has a common improper prior may or may not have a bounded agreeable bet. The iterated expectations characterisation of the existence of common priors extends almost as is, as a sufficient and necessary condition, from finite spaces to countable spaces, but fails to serve as a characterisation of common improper priors. As a side-benefit of the proofs here, we also obtain a constructive proof of the no betting characterisation in finite spaces.