"The computational complexity of two classes of market mechanisms is compared. First the Walrasian interpretation in which prices are centrally computed by an auctioneer. Recent results on the computational complexity are reviewed. The non-polynomial complexity of these algorithms makes Walrasian general equilibrium an implausible conception. Second, a decentralised picture of market processes is described, involving concurrent exchange within transient coalitions of agents. These processes feature price dispersion, yield allocations that are not in the core, modify the distribution of wealth, are always stable, but path-dependent. Replacing the Walrasian framing of markets requires substantial revision of conventional wisdom concerning markets."

"Over the last couple of years, Cosma Shalizi and I have been working together on various things, including, inter alia, the relationship between complex systems, democracy and the Internet. These are big unwieldy topics, and trying to think about them systematically is hard. Even so, we’ve gotten to the point where we at least feel ready to start throwing stuff at a wider audience, to get feedback on what works and what doesn’t. Here’s a paper we’re working on, which argues that we should (for some purposes at least), think of markets, hierarchy and democracy in terms of their capacity to solve complex collective problems, makes the case that democracy will on average do the job a lot better than the other two ways, and then looks at different forms of collective information processing on the Internet as experiments that democracies can learn from."

This paper studies decision making by agents who value optimism, but are unsure of their environment. As in Brunnermeier and Parker (2005), an agent’s optimism is assumed to be tempered by the decision costs it imposes. As in Hansen and Sargent (2008), an agent’s uncertainty about his environment leads him to formulate ‘robust’ decision rules. It is shown that when combined, these two considerations can lead agents to adhere to the Rational Expectations Hypothesis. Rather than being the outcome of the sophisticated statistical calculations of an impassive expected utility maximizer, Rational Expectations can instead be viewed as a useful approximation in environments where agents struggle to strike a balance between doubt and hope.

"The problem of multiple hypothesis testing with observation control is considered in both fixed sample size and sequential settings. In the fixed sample size setting, for binary hypothesis testing, it is shown that the optimal exponent for the maximal error probability corresponds to the maximum Chernoff information over the choice of controls. It is also shown that a pure stationary open-loop control policy is asymptotically optimal within the larger class of all causal control policies. For multihypothesis testing in the fixed sample size setting, lower and upper bounds on the optimal error exponent are derived. It is also shown through an example with three hypotheses that the optimal causal control policy can be strictly better than the optimal open-loop control policy. In the sequential setting, a test based on earlier work by Chernoff for binary hypothesis testing, is shown to be first-order asymptotically optimal for multihypothesis testing for vanishing error probabilities. The role of past information and randomization in designing optimal control policies is discussed."

Multi-armed bandit problems are the most basic examples of sequential decision problems with an exploration-exploitation trade-off. This is the balance between staying with the option that gave highest payoffs in the past and exploring new options that might give higher payoffs in the future. Although the study of bandit problems dates back to the Thirties, exploration-exploitation trade-offs arise in several modern applications, such as ad placement, website optimization, and packet routing. Mathematically, a multi-armed bandit is defined by the payoff process associated with each option. In this survey, we focus on two extreme cases in which the analysis of regret is particularly simple and elegant: i.i.d. payoffs and adversarial payoffs. Besides the basic setting of finitely many actions, we also analyze some of the most important variants and extensions, such as the contextual bandit model.

"We servey [sic!] a series of investigations of optimal testing of multiple hypotheses conserning various multiobject models. These studies are a bright instance of application of methods and technics developed in Shannon information theory to solution of typical statistical problems."

Consider any investor who fears ruin facing any set of invest-
ments that satisfy no-arbitrage. Before investing, he can purchase informa-
tion about the state of nature in the form of an information structure. Given
his prior, information structure  is more informative than information struc-
ture  if whenever he rejects  at some price, he also rejects  at that price.
We show that this complete informativeness ordering is represented by the
decrease in entropy of his beliefs, regardless of his preferences, initial wealth
or investment problem. It is also shown that no prior-independent informa-
tiveness ordering based on similar premises exists.

This paper establishes information order in a number of special settings. We
discuss Lehmann’s condition, relate it to Blackwell’s and discuss its application in
statistical decision problems, certain Bayesian games and in principal agent problems. We distinguish between KR (Karlin Rubin) monotone preferences and single
crossing preferences and between Lehmann’s and Persico’s theorems. A generalisation of Lehmann’s condition is given that is applicable to situations where monotone
likelihood ratio does not apply. The principal agent problem is treated both via
the first-order approach and for the general finite action model. Points of contact
with Lehmann’s condition are identified in both cases.

the journal version

"This paper studies the well-known counter example of Witsenhausen when the  initial  uncertainty is  small.  Using an asymptotic approach, it  is established that linear  strategies are  asymptotically optimal over a large class of nonlinear  strategies.  This  serves as a guideline for optimal solutions of non-classical problems with very noisy communication channels."

"We consider the celebrated Blackwell Approachability Theorem for two-player games with vector payoffs. We show that Blackwell's result is equivalent, via efficient reductions, to the existence of "no-regret" algorithms for Online Linear Optimization. Indeed, we show that any algorithm for one such problem can be efficiently converted into an algorithm for the other. We provide a useful application of this reduction: the first efficient algorithm for calibrated forecasting."

"A theory of choice under uncertainty is proposed which removes the completeness assumption from the Anscombe–Aumann formulation of Savage's theory and introduces an inertia assumption. The inertia assumption is that there is such a thing as the status quo and an alternative is accepted only if it is preferred to the status quo. This theory is one way of giving rigorous expression to Frank Knight's distinction between risk and uncertainty."

Hmm: "We propose a rigorous framework for Uncertainty Quantification (UQ) in which the UQ objectives and the assumptions/information set are brought to the forefront. This framework, which we call \emph{Optimal Uncertainty Quantification} (OUQ), is based on the observation that, given a set of assumptions and information about the problem, there exist optimal bounds on uncertainties: these are obtained as extreme values of well-defined optimization problems corresponding to extremizing probabilities of failure, or of deviations, subject to the constraints imposed by the scenarios compatible with the assumptions and information. In particular, this framework does not implicitly impose inappropriate assumptions, nor does it repudiate relevant information. ..."

Hot damn! "... in this paper we re-examine Freund's problem in case the experts have internal structure that enables them to learn. In this case the problem has two possible interpretations: should the experts learn from all data or only from the subsequence on which they are being tracked? The MPP algorithm solves the first case. Our contribution is to generalise MPP to address the second option. The results we obtain apply to any expert structure that can be formalised using (expert) hidden Markov models. Curiously enough, for our interpretation there are \emph{two} natural reference schemes: freezing and sleeping. For each scheme, we provide an efficient prediction strategy and prove the relevant loss bound."

"We recently proved that game theory and statistical physics are identical when cast in terms of information theory.

We call the associated formalism Probability Collectives (PC). PC opens many new lines of research, and provides new approaches to problems in distributed control and distributed optimization."

A quote from Blackwell himself: "Basically, I'm not interested in doing research and I never have been, I'm interested in understanding, which is quite a different thing. And often to understand something you have to work it out yourself because no one else has done it."

"This paper develops a generalized apprenticeship learning protocol for reinforcement-learning agents with access to a teacher who provides policy traces (transition and reward observations). We characterize sufficient conditions of the underlying models for efficient apprenticeship learning and link this criteria to two established learnability classes (KWIK and Mistake Bound). We then construct efficient apprenticeship-learning algorithms in a number of domains, including two types of relational MDPs. We instantiate our approach in a software agent and a robot agent that learn effectively from a human teacher."

Nice list of references on decentralized control and team decision problems.

Abstract: "Online learning is becoming increasingly popular for training on large datasets. However, the sequential nature of online learning requires a centralized learner to store data and update parameters. In this paper, we consider a fully decentralized setting, cooperative autonomous online learning, with a distributed data source. The learners perform learning with local parameters while periodically communicating with a small subset of neighbors to exchange information. We define the regret in terms of an implicit aggregated parameter of the learners for such a setting and prove regret bounds similar to the classical sequential online learning." Damn, looks like I've been scooped!

Daron Acemoglu, Munther A. Dahleh, Ilan Lobel, Asuman Ozdaglar; NBER Working Paper No. 14040

"...a website for research and coordination on Decentralized Techniques for Reasoning in Reduced Information Spaces (ONR 2009 Multi-disciplinary University Research Project)"

From the abstract: "We consider multi-armed bandit with distributed players, where each player independently samples one of N stochastic processes with unknown parameters and accrues reward in each slot without information exchange. Users choosing the same arm collide, and none or only one receives reward depending on the collision model. This problem can be formulated as a decentralized multi-armed bandit problem."

Ashutosh Nayyar, Demosthenis Teneketzis

M. H. DeGroot

Dinah Rosenberg, Eilon Solan, Nicolas Vieille

How can the social sciences, mathematics and computer science combine to affect national security policy?