Search

We adapt the method used by Jaynes to derive the equilibria of statistical physics to instead derive equilibria of bounded rational game theory. We analyze the dependence of these equilibria on the parameters of the underlying game, focusing on hysteresis effects. In particular, we show that by gradually imposing individual-specific tax rates on the players of the game, and then gradually removing those taxes, the players move from a poor equilibrium to one that is better for all of them.

We introduce a general framework for formalizing and analyzing the problem faced by a Decision Maker (DM) working under information-theoretic constraints on their observational ability. The random utility model and the "hedonic utility" model of Netzer and Robson (NR) are special cases of this framework. We begin by applying information theory to our framework to derive general results concerning the expected regret of DM under observational limitations. We then turn our attention to the effects of observational limitations on choice behavior (rather than their effects on the regret values induced by that behavior). We focus on the special case of NR. First we derive two postulates assumed by NR. We then provide a simple derivation of the result of NR that a particular hedonic utility function satisfies certain optimality principles. Next we extend NR to allow a countable, rather than uncountable, set of states of the world. In particular we show how to use dynamic programming to solve for the optimal preference order of DM in this extension. We also extend NR by considering the case where more than two options are presented to DM. In particular, we show that the results of NR change in such a case, implying that the number of options being presented is a crucial aspect of choice problems

Prescriptive Bayesian decision making has reached a high level of maturity and is well-supported algorithmically. However, experimental data shows that real decision makers choose such Bayes-optimal decisions surprisingly infrequently, often making decisions that are badly sub-optimal. So prevalent is such imperfect decision-making that it should be accepted as an inherent feature of real decision makers living within interacting societies. To date such societies have been investigated from an economic and gametheoretic perspective, and even to a degree from a physics perspective. However, little research has been done from the perspective of computer science and associated disciplines like machine learning, information theory and neuroscience. This book is a major contribution to such research. Some of the particular topics addressed include: How should we formalise rational decision making of a single imperfect decision maker? Does the answer change for a system of imperfect decision makers? Can we extend existing prescriptive theories for perfect decision makers to make them useful for imperfect ones? How can we exploit the relation of these problems to the control under varying and uncertain resources constraints as well as to the problem of the computational decision making? What can we learn from natural, engineered, and social systems to help us address these issues?

We show how to combine Bayes nets and game theory to predict the behavior of hybrid systems involving both humans and automated components. We call this novel framework “Semi Network-Form Games”, and illustrate it by predicting aircraft pilot behavior in potential near mid-air collisions. At present, at the beginning of such potential collisions, a collision avoidance system in the aircraft cockpit advises the pilots what to do to avoid the collision. However studies of mid-air encounters have found wide variability in pilot responses to avoidance system advisories. In particular, pilots rarely perfectly execute the recommended maneuvers, despite the fact that the collision avoidance system’s effectiveness relies on their doing so. Rather pilots decide their actions based on all information available to them (advisory, instrument readings, visual observations). We show how to build this aspect into a semi network-form game model of the encounter and then present computational simulations of the resultant model.

We examine the potential for a simple auction to allocate arrival slots during Ground Delay Programs (GDP’s) more efficiently than the currently used sys- tem. The analysis of these auctions uses Predictive Game Theory (PGT) Wolpert and Bono (2010a,b), a new approach that produces a probability distribution over strategies instead of an equilibrium set. We compare the simple auction with other allocation methods, including combinatorial auctions and theoretical benchmarks using data from a one-hour GDP at Chicago Midway. We find that the simple slot auction overcomes several practical shortcomings of other approaches, while offering economically significant efficiency gains with respect to current practices and the potential to lower airline costs. We also find that the second price version of the simple auction dominates the first price version in nearly every decision-relevant category. This is despite the fact that none of the conventional arguments for second price auctions, such as dominant strategy implementability, even apply to GDP slot auctions. Finally, the results indicate that combinatorial auctions, if made operationally practical, might be more efficient than our auction, even though the combinatorial auction does not implement the social optimum in dominant strategies.

We consider the problem of designing the the utility functions of the utility-maximizing agents in a multi-agent system so that they work synergistically to maximize a global utility. The particular problem domain we explore is the control of network routing by placing agents on all the routers in the network. Conventional approaches to this task have the agents all use the Ideal Shortest Path routing Algorithm (ISPA). We demonstrate that in many cases, due to the side-effects of one agent's actions on another agent's performance, having agents use ISPA's is suboptimal as far as global aggregate cost is concerned, even when they are only used to route infinitesimally small amounts of traffic. The utility functions of the individual agents are not ``aligned'' with the global utility, intuitively speaking. As a particular example of this we present an instance of Braess' paradox in which adding new links to a network whose agents all use the ISPA results in a decrease in overall throughput. We also demonstrate that load-balancing, in which the agents' decisions are collectively made to optimize the global cost incurred by all traffic currently being routed, is suboptimal as far as global cost averaged across time is concerned. This is also due to `side-effects', in this case of current routing decision on future traffic. The mathematics of Collective Intelligence (COIN) is concerned precisely with the issue of avoiding such deleterious side-effects in multi-agent systems, both over time and space. We present key concepts from that mathematics and use them to derive an algorithm whose ideal version should have better performance than that of having all agents use the ISPA, even in the infinitesimal limit. We present experiments verifying this, and also showing that a machine-learning-based version of this COIN algorithm in which costs are only imprecisely estimated via empirical means (a version potentially applicable in the real world) also outperforms the ISPA, despite having access to less information than does the ISPA. In particular, this COIN algorithm almost always avoids Braess' paradox.

In experiments it is typically found that many joint utility outcomes arise in any given unstructured bargaining game. This suggests using a positive unstructured bargaining concept that maps a bargaining game to a probability distribution over outcomes rather than to a single outcome. We show how to "translate" Nash's bargaining axioms to apply to such distributional bargaining concepts. We then prove that a subset of those axioms forces the distribution over outcomes to be a power-law. Unlike Nash's original result, our result holds even if the feasible set is finite. When the feasible set is convex and comprehensive, the mode of the power law distribution is the Harsanyi bargaining solution, and if we require symmetry it is the Nash bargaining solution. However in general these modes of the joint utility distribution are not Bayes-optimal predictions for the joint uitlity, nor are the bargains corresponding to those outcomes the most likely bargains. We then show how an external regulator can use distributional solution concepts to optimally design an unstructured bargaining scenario. Throughout we demonstrate our analysis in computational experiments involving flight rerouting negotiations in the National Airspace System.

To identify psychosocial factors associated with the use of continuous glucose monitoring by adults with Type 1 diabetes.Twenty adult patients (aged 45 +/- 15 years, diabetes duration 25 +/- 19 years, 50% female) followed at our site in the multi-centre Juvenile Diabetes Research Foundation continuous glucose monitoring trial were divided into three groups: Glycated haemoglobin (HbA(1c)) Responders who demonstrated an improvement in glycaemic control with continuous glucose monitoring (baseline HbA(1c)or = 7.0%, HbA(1c) reduction greater than or equal to 0.5%), Hypoglycaemia Responders (baseline HbA(1c)7.0%) who demonstrated decreased time3.9 mmol/l while remaining within target HbA(1c), and HbA(1c) Non-Responders (baseline HbA(1c)or = 7.0%, HbA(1c) reduction less than 0.5%). Subjects participated in semi-structured interviews focusing on their psychosocial experiences with continuous glucose monitoring.Three major themes were identified that differentiated Responders (including both the HbA(1c) and Hypoglycaemia groups) from Non-Responders: (i) coping with frustrations-Responders used self-controlled rather than emotions-based coping when faced with continuous glucose monitoring frustrations; (ii) use of information-Responders used retrospective pattern analysis, not just minute-by-minute data analysis, in glycaemic management; (iii) 'significant other'/spousal involvement-Responders endorsed interest, encouragement and participation by their loved ones. Both Responders and Non-Responders expressed body image concerns when wearing continuous glucose monitoring devices.This qualitative study points to the importance of coping skills, retrospective review of data, and 'significant other' involvement in the effective use of continuous glucose monitoring. These findings will inform clinical initiatives to improve patient selection and training in the use of this new technology and have served as the basis for development of quantitative surveys to be used in clinical practice.

Under its conventional positive interpretation, game theory predicts that the mixed strategy pro?le of players in a noncooperative game will satisfy some setvalued solution concept. Relative probabilities of pro?les in that set are unspeci?ed, and all pro?les not satisfying it are implicitly assigned probability zero. However the axioms underlying Bayesian rationality say that we should reason about player behavior using a probability density over all mixed strategy pro?les, not using a subset of all such pro?les. Such a density over pro?les can be viewed as a solution concept that is distribution-valued rather than set-valued. A distribution-valued concept provides a best single prediction for any noncooperative game, i.e., a universal re?nement. In addition, regulators can use a distribution-valued solution concept to make Bayes optimal choices of a mechanism, as required by Savage's axioms. In particular, they can do this in strategic situations where conventional mechanism design cannot provide advice. We illustrate all of this on a Cournot duopoly game.

In experimental tests of human behavior in unstructured bargaining games, typically many joint utility outcomes are found to occur, not just one. This suggests we predict the outcome of such a game as a probability distribution. This is in contrast to what is conventionally done (e.g, in the Nash bargaining solution), which is predict a single outcome. We show how to translate Nash’s bargaining axioms to provide a distribution over outcomes rather than a single outcome. We then prove that a subset of those axioms forces the distribution over utility outcomes to be a power-law distribution. Unlike Nash’s original result, our result holds even if the feasible set is finite. When the feasible set is convex and comprehensive, the mode of the power law distribution is the Harsanyi bargaining solution, and if we require symmetry it is the Nash bargaining solution. However, in general these modes of the joint utility distribution are not the experimentalist’s Bayes-optimal predictions for the joint utility. Nor are the bargains corresponding to the modes of those joint utility distributions the modes of the distribution over bargains in general, since more than one bargain may result in the same joint utility. After introducing distributional bargaining solution concepts, we show how an external regulator can use them to optimally design an unstructured bargaining scenario. Throughout we demonstrate our analysis in computational experiments involving flight rerouting negotiations in the National Airspace System. We emphasize that while our results are formulated for unstructured bargaining, they can also be used to make predictions for noncooperative games where the modeler knows the utility functions of the players over possible outcomes of the game, but does not know the move spaces the players use to determine those outcomes.

Under its conventional positive interpretation, game theory makes predictions about the mixed strategy profile of the players in a noncooperative game by specifying a "solution set" of such profiles, e.g., the set of Nash equilibria of that game. Profiles outside of that set are implicitly assigned probability zero, and relative probabilities of profiles in that set are not provided. In contrast, Bayesian analysis does not make predictions about the state of a system by specifying a set of possible states of that system. Rather it provides a probability density over all those states, conditioned on all relevant information we have concerning the system. So when the "state of a system" is the strategy profile of the players of a game, and our information comprises the game specification, a Bayesian analysis would result in a posterior density over the set of all profiles, conditioned on the game specification. Evidently the very form of a prediction provided by a Bayesian analysis is different from the form provided by solution sets. In this paper, we show how to construct a Bayesian posterior density over profiles and discuss its practical advantages over solution sets. As an example, by combining this posterior density with a loss function of the scientist making the prediction, standard decision theory fixes the unique Bayes-optimal prediction of the profile conditioned on the game specification. So it provides a universal refinement. As another example, Bayesian regulators of the players involved in a game would use such a posterior density to make Bayes-optimal choices of a mechanism to control player behavior (and thereby fully adhere to Savage's axioms). In particular, a regulator can do this in situations where conventional mechanism design cannot provide advice. We illustrate all of this numerically with Cournot duopoly games.

We adapt the method used by Jaynes to derive the equilibria of statistical physics to instead derive equilibria of bounded rational game theory. We analyze the dependence of these equilibria on the parameters of the underlying game, focusing on hysteresis effects. In particular, we show that by gradually imposing individual-specific tax rates on the players of the game, and then gradually removing those taxes, the players move from a poor equilibrium to one that is better for all of them., Comment: 5 pages, 4 figures

Recent work in several fields has established that humans can adopt binding “behavioral” preferences and convincingly signal those preferences to other humans, either via their behavior or via their body language / tone of voice. In this paper, we model the strategic implications of this ability. Our thesis is that through a person's lifetime they (perhaps subconsciously) learn what such signaled, binding behavioral preferences result in the highest value of their actual preferences, given the resultant behavior of other players. We argue that this “persona” model may explain why many interpersonal preferences have the particular form they do. As an illustration, we use the persona model to explain cooperation in non-repeated versions of the Prisoner's Dilemma (PD). We also provide quantitative predictions to distinguish this explanation of cooperation from simply assuming people have actual preferences biased towards cooperation. In particular, we show that the persona model predicts a “crowding out” phenomenon in the PD, in which introducing incentives to cooperate causes players to stop cooperating instead. We also use the persona model to predict a tradeoff between the robustness of cooperation in the PD and the benefit of that cooperation.

A memory is a physical system for transferring information from one moment in time to another, where that information concerns something external to the system itself. This paper argues on information-theoretic and statistical mechanical grounds that useful memories must be of one of two types, exemplified by memory in abstract computer programs and by memory in photographs. Photograph-type memories work by exploiting a collapse of state space flow to an attractor state. (This attractor state is the “initialized” state of the memory.) The central assumption of the theory of reversible computation tells us that inany such collapsing, regardless of whether the collapsing proceeds from the past to the future or vice versa, the collapsing must increase the entropy of the system. In concert with the second law, this establishes the logical necessity of the empirical observation that photograph-type memories are temporally asymmetric (they can tell us about the past but not about the future). Under the assumption that human memory is a photograph-type memory, this result also explains why we humans can remember only our past and not our future. In contrast to photograph-type memories, computer-type memories do not require any initialization, and therefore are not directly affected by the second law. As a result, computer memories can be of the future as easily as of the past, even if the program running on the computer is logically irreversible. This is entirely in accord with the well-known temporal reversibility of the process of computation. This paper ends by arguing that the asymmetry of the psychological arrow of time is a direct consequence of the asymmetry of human memory. With the rest of this paper, this explains, explicitly and rigorously, why the psychological and thermodynamic arrows of time are correlated with one another.

It is known that a player in a noncooperative game can benefit by publicly re- stricting their possible moves before start of play. We show that, more generally, a player may benefit by publicly committing to pay an external party an amount that is contingent on the game's outcome. We explore what happens when external parties (who we call game miners) discover this fact and seek to profit from it by entering an outcome-contingent contract with the players. We analyze various bargaining games between miners and players for determining such an outcome- contingent contract. We establish restrictions on the strategic settings in which a game miner can profit, and bounds on the game miner's profit given various structured bargaining games. These bargaining games include playing the players against one another, as well as allowing the players to pay the miner(s) for exclu- sivity and first-mover advantage. We also establish that when all players can enter contracts with miners, to guarantee the existence of equilibria it is necessary to assume that players can randomize over the contracts they make.

Airbreathing hypersonic systems offer distinct performance advantages over rocket-based systems for space access vehicles. Realization of this potential performance gain will require optimum integration of many different technology areas, including vehicle dynamics and controls. Typically detailed dynamic analysis and controls design are performed after a vehicle has completed the conceptual design phase. However, due to the complex interactions in an airbreathing hypersonic vehicle, delaying application of detailed dynamics analysis and controls design could result in suboptimal vehicle designs. The Guidance, Navigation, and Controls discipline of NASA's Fundamental Aeronautics Program Hypersonics area is applying dynamic analysis and controls design early in the vehicle conceptual design. This activity includes development of controls focused dynamic models, creation of an integrated design environment for dynamics analysis and controls design, and early evaluation of vehicle controllability aspects. This effort will provide valuable insight into the vehicle multidisciplinary design and optimization phase.

In many cultures a major factor affecting a person's happiness is the difference between their income and that of their neighbors, independent of their own income. This effect is strongest when the income difference is negative (richer neighbor). In addition, across their lifetime, a person's happiness tends to follow a U shape, with a minimum in the 40's. Previous models have separately explained some of these three phenomena. Some of these models have assumed the person has cognitive limitations, e.g., their happiness has a finite number of possible values, or they cannot accurately assess their happiness. Here I present a model which explains all three of the phenomena, and does not assume any cognitive limitations. In this model moderately greater income of your neighbor is statistical data that, if carefully analyzed, would recommend that you explore for a new income-generating strategy. This explains unhappiness that your neighbor has moderately greater income, as an emotional prod that induces you to explore, exactly as a detailed statistical analysis of the income difference would recommend. This model also explains why unhappiness is not stimulated by a positive income difference: that type of difference does not imply you should explore. In addition, the model explains the U shape of happiness across lifetime as due to the fact that the longer one lives, the more searching over income-generating strategies one has done, and therefore the less relevant new statistical data is. The model also makes numerous predictions that can be tested in future experiments and social surveys.

OBJECTIVE To examine the persistence of the original treatment effects 10 years after the Diabetes Control and Complications Trial (DCCT) in the follow-up Epidemiology of Diabetes Interventions and Complications (EDIC) study. In the DCCT, intensive therapy aimed at near-normal glycemia reduced the risk of microvascular complications of type 1 diabetes mellitus compared with conventional therapy. METHODS Retinopathy was evaluated by fundus photography in 1211 subjects at EDIC year 10. Further 3-step progression on the Early Treatment Diabetic Retinopathy Study scale from DCCT closeout was the primary outcome. RESULTS After 10 years of EDIC follow-up, there was no significant difference in mean glycated hemoglobin levels (8.07% vs 7.98%) between the original treatment groups. Nevertheless, compared with the former conventional treatment group, the former intensive group had significantly lower incidences from DCCT close of further retinopathy progression and proliferative retinopathy or worse (hazard reductions, 53%-56%; P < .001). The risk (hazard) reductions at 10 years of EDIC were attenuated compared with the 70% to 71% over the first 4 years of EDIC (P < .001). The persistent beneficial effects of former intensive therapy were largely explained by the difference in glycated hemoglobin levels during DCCT. CONCLUSION The persistent difference in diabetic retinopathy between former intensive and conventional therapy ("metabolic memory") continues for at least 10 years but may be waning. TRIAL REGISTRATION (clinicaltrials.gov) Identifiers: NCT00360815 and NCT00360893.

Conventionally, game theory predicts that the mixed strategy profile of players in a noncooperative game will satisfy some equilibrium concept. Relative probabil- ities of the strategy profiles satisfying the concept are unspecified, and all strategies not satisfying it are implicitly assigned probability zero. As an alternative, we re- cast the prediction problem of game theory as statistically estimating the strategy profile, from "data" that consists of the game specification. This replaces the focus of game theory, on specifying a set of "equilibrium" mixed strategies, with a new focus, on specifying a probability density over all mixed strategies. We explore a Bayesian version of such a Predictive Game Theory (PGT). We show that for some games the peaks of the posterior over strategy profiles approximate quantal response equilibria. We also show how PGT provides a best single prediction for any noncooperative game, i.e., a universal refinement. We also show how regula- tors can use PGT to make optimal decisions in situations where conventional game theory cannot provide advice.

We introduce a framework that explains non-rationality in non-repeated games. In our framework a player i adopts a binding "persona" - a temporary utility function --- that they honestly signal before play. By adopting a "non-rational" persona, i may cause changes in their opponents' behavior that increases $i$'s true utility. We use this framework to explain experimental data in the Traveler's Dilemma and to show how cooperation can arise in the Prisoner's Dilemma (PD). We then predict a crowding out phenomenon in the PD. We also predict a tradeoff between the robustness and the benefit of cooperation in the PD.

A long-running difficulty with conventional game theory has been how to modify it to accommodate the bounded rationality of all red-world players. A recurring issue in statistical physics is how best to approximate joint probability distributions with decoupled (and therefore far more tractable) distributions. This paper shows that the same information theoretic mathematical structure, known as Product Distribution (PD) theory, addresses both issues. In this, PD theory not only provides a principle formulation of bounded rationality and a set of new types of mean field theory in statistical physics; it also shows that those topics are fundamentally one and the same.

A significant body of research under the rubric of blackbox optimization addresses the problem of optimization in a design space where the designs are evaluated by a computer simulation. For many such simulations, conventional local optimization methods prove inadequate, owing to the presence of local minima, local non-smoothness, and so on. A more effective approach would learn the global characteristics of the design space, and sample from disparate regions as it progresses. Several probabilistic approaches to this problem are based on the following idea: during the course of any search process, our partial knowledge of the design space grows as we evaluate a growing number of designs, and this knowledge can be elegantly expressed in terms of probability distributions. This is usually done using surrogate models, or data fits. We would like to use this partial knowledge to lead us to promising new designs, and this involves searching the data fit for points where the uncertainty of the fit, in conjunction with the fit itself, indicates a good chance of finding a improved design. This is the basis for the well-known Efficient Global Optimization (EGO) algorithm. This task can be regarded as an auxiliary optimization problem, but one that has some undesirable characteristics, including large flat regions and multiple local optima. Previous solution approaches have included branch and bound (the EGO algorithm), and local optimization with multi-start. In this paper, we present a new approach, itself based on probability distributions. Probability Collectives (PC) is an optimization framework in which a given optimization problem is transformed to one over probability distributions. This transformation often enables us to overcome problems such as local non-smoothness and multiple local optima. One particular PC approach is closely related to function smoothing and filtering. Our formulation is a type of Monte Carlo Optimization, often encountered in machine learning algorithms. We briefly introduce this approach, and apply it to the auxiliary optimization problem described above. Finally, we compare this technique with other algorithms, including a heuristic sampling algorithm, and a genetic algorithm.

In this paper, we review an optimization technique called Probability Collectives (PC), and compare its approach with that of quadratic Response Surface Methods (RSM), on some standard continuous test functions for unconstrained minimization, both in the presence and absence of uncertainty in the function evaluations. Probability Collectives (PC) is an optimization framework where optimization is performed over probability distributions over the variables of interest, rather than the variables themselves. In order to find a solution to the original optimization problem, we sample the final solution of the transformed problem, which is a probability distribution. In other words, PC is a transform technique with the special property that the inverse transform is performed stochastically. This transformation yields algorithms that are relatively insensitive to structural properties of the underlying objective function, like continuity, convexity, and dierentiability; optimization under uncertainty becomes natural and straightforward; finally, the distributions yield sensitivity information about the original problem. Some PC algorithms bear a strong resemblance to RSM, and in this paper, we investigate these similarities, and compare performances of these techniques on some simple test functions.

Probability Collectives (PC) provides the information-theoretic extension of conventional full-rationality game theory to bounded rational games. Here an explicit solution to the equations giving the bounded rationality equilibrium of a game is presented. Then PC is used to investigate games in which the players use bounded rational best-response strategies. Next it is shown that in the continuumtime limit, bounded rational best response games result in a variant of the replicator dynamics of evolutionary game theory. It is then shown that for team (shared-payoff) games, this variant of replicator dynamics is identical to Newton-Raphson iterative optimization of the shared utility function.

First page of article Keywords: supervised learning; Bayesian learning; computational learning theory; ‘no free lunch’ theorems

Recent developments in actuator technology have resulted in small, simple devices capable of afiecting the ∞ow fleld over ∞ight vehicles su‐ciently to generate control forces. One of the devices which has been under investigation is the Miniature-Trailing Edge Efiector (MiTE), which consists of a small, 1-5% chord, moveable surface mounted at the wing trailing edge. The high bandwidth and good control authority make the device an ideal candidate for control of both the rigid body and ∞exible modes of a ∞ight vehicle. Unfortunately traditional control techniques do not address the non-linear nature of the device or the competing performance goals arising from large numbers of distributed devices. Novel approaches to control design are therefore required. To demonstrate the potential of this type of ∞ight control architecture and to explore suitable control synthesis techniques, a remotely piloted ∞ight vehicle has been developed. This paper details the ∞ight vehicle including a distributed ∞ight control system based upon MiTEs. The latter system includes distributed sensing, logic, and actuation. This paper also describes an applicable novel control synthesis technique based upon the theory of collectives. The theory and its application to the design of distributed ∞ight control systems is presented. Results of ∞ight tests with conventional control surfaces and with a MiTE based control system are provided.

Aerospace systems continue to grow in complexity while demanding optimal performance. This requires the systems to be both designed and controlled optimally. Aerospace systems are also typically comprised of many interacting components, some of which may have competing requirements. The optimization approaches used for aerospace systems usually require centralized coordination and synchronous updates. In addition, while the approaches treat the large numbers of variables, they may not take advantage of the fact that the coupling may only be between a relatively small number of the variables. Distributed optimization algorithms, such as the approach based upon collectives presented in this paper, attempt to exploit this aspect. A collective is deflned as a multi-agent system where each agent is self-interested and capable of learning. Furthermore, a collective has a specifled system objective which rates the performance of the joint actions of the agents. Although collectives have been used for a number of distributed optimization problems in computer science, recent developments based upon Probability Collectives (PC) theory enhance their applicability to discrete, continuous, mixed, and constrained optimization problems. This paper will present the theoretical underpinnings of the approach for these various problem domains. Several example problems are used to illustrate the technique and to provide insight into its behavior. The examples include discrete, constrained, and continuous problems. In particular a constrained discrete structural optimization and a continuous trajectory optimization illustrate the breadth of the collectives approach.

We consider the problem of designing a set of computational agents so that as they all pursue their self-interests a global function G of the collective system is optimized. Three factors govern the quality of such design. The first relates to conventional exploration-exploitation search algorithms for finding the maxima of such a global function, e.g., simulated annealing. Game-theoretic algorithms instead are related to the second of those factors, and the third is related to techniques from the field of machine learning. Here we demonstrate how to exploit all three factors by modifying the search algorithm's exploration stage so that rather than by random sampling, each coordinate of the underlying search space is controlled by an associated machine-learning-based ``player'' engaged in a non-cooperative game. Experiments demonstrate that this modification improves SA by up to an order of magnitude for bin-packing and for a model of an economic process run over an underlying network. These experiments also reveal novel small worlds phenomena.

Product distribution theory is a new collective intelligence-based framework for analyzing and controlling distributed systems. Its usefulness in distributed stochastic optimization is illustrated here through an airline fleet assignment problem. This problem involves the allocation of aircraft to a set of flights legs in order to meet passenger demand, while satisfying a variety of linear and non-linear constraints. Over the course of the day, the routing of each aircraft is determined in order to minimize the number of required flights for a given fleet. The associated flow continuity and aircraft count constraints have led researchers to focus on obtaining quasi-optimal solutions, especially at larger scales. In this paper, the authors propose the application of this new stochastic optimization algorithm to a non-linear objective cold start fleet assignment problem. Results show that the optimizer can successfully solve such highly-constrained problems (130 variables, 184 constraints).

Due to the increasing sophistication and miniaturization of computational components, complex, distributed systems of interacting agents are becoming ubiquitous. Such systems, where each agent aims to optimize its own performance, but there is a well-defined set of system-level performance criteria, are called collectives. The fundamental problem in analyzing and designing such systems is in determining how the combined actions of a large number of agents lead to “coordinated” behavior on the global scale. Examples of artificial systems that exhibit such behavior include packet routing across a data network, control of an array of communication satellites, coordination of multiple rovers, and dynamic job scheduling across a distributed computer grid. Examples of natural systems include ecosystems, economies, and the organelles within a living cell.

A survey of collectives.- Theory of collective intelligence.- On learnable mechanism design.- Asynchronous learning in decentralized environments.- Competition between adaptive agents.- Managing catastrophic changes in a collective.- Effects of inter-agent communications on the collective.- Man and superman--human limitations, innovation, and emergence in resource competition.- Design principles for the distributed control of modular self-reconfigurable robots.- Two paradigms for the design of artificial collectives.- Efficiency and equity in collective systems of interacting heterogeneous agents.- Selection in coevolutionary algorithms and the inverse problem.- Dynamics of large autonomous computational systems.- Index.

We consider the problem of designing (perhaps massively distributed) collectives of computational processes to maximize a provided "world utility" function. We consider this problem when the behavior of each process in the collective can be cast as striving to maximize its own payoff utility function. For such cases the central design issue is how to initialize/update those payoff utility functions of the individual processes so as to induce behavior of the entire collective having good values of the world utility. Traditional "team game" approaches to this problem simply assign to each process the world utility as its payoff utility function. In previous work we used the "Collective Intelligence" (COIN) framework to derive a better choice of payoff utility functions, one that results in world utility performance up to orders of magnitude superior to that ensuing from the use of the team game utility. In this paper, we extend these results using a novel mathematical framework. Under that new framework we review the derivation of the general class of payoff utility functions that both (i) are easy for the individual processes to try to maximize, and (ii) have the property that if good values of them are achieved, then we are assured a high value of world utility. These are the "Aristocrat Utility" and a new variant of the "Wonderful Life Utility" that was introduced in the previous COIN work. We demonstrate experimentally that using these new utility functions can result in significantly improved performance over that of previously investigated COIN payoff utilities, over and above those previous utilities' superiority to the conventional team game utility. These results also illustrate the substantial superiority of these payoff functions to perhaps the most natural version of the economics technique of "endogenizing externalities."

This paper reviews the supervised learning versions of the no-free-lunch theorems in a simplified form. It also discusses the significance of those theorems, and their relation to other aspects of supervised learning.

In this paper strong limits on the accuracy of real-world physical computation are established. To derive these results a non-Turing machine formulation of physical computation is used. First it is proven that there cannot be a physical computer C to which one can pose any and all computational tasks concerning the physical universe. Next it is proven that no physical computer C can correctly carry out every computational task in the subset of such tasks that could potentially be posed to C. This means in particular that there cannot be a physical computer that can be assured of correctly "processing information faster than the universe does." Because this result holds independent of how or if the computer is physically coupled to the rest of the universe, it also means that there cannot exist an infallible, general-purpose observation apparatus, nor an infallible, general-purpose control apparatus. These results do not rely on systems that are infinite, and/or nonclassical, and/or obey chaotic dynamics. They also hold even if one could use an infinitely fast, infinitely dense computer, with computational powers greater than that of a Turing machine (TM). After deriving these results analogs of the TM Halting theorem are derived for the novel kind of computer considered in this paper, as are results concerning the (im)possibility of certain kinds of error-correcting codes. In addition, an analog of algorithmic information complexity, "prediction complexity," is elaborated. A task-independent bound is derived on how much the prediction complexity of a computational task can differ for two different reference universal physical computers used to solve that task. This is analogous to the "encoding" bound governing how much the algorithm information complexity of a TM calculation can differ for two reference universal TMs. It is proven that either the Hamiltonian of our universe proscribes a certain type of computation, or prediction complexity is unique (unlike algorithmic information complexity). Finally, the implications of this analysis for the issue of whether the universe "is" a computer are briefly discussed.

We consider the design of multi-agent systems so as to optimize an overall world utility function when (1) those systems lack centralized communication and control, and (2) each agents runs a distinct Reinforcement Learning (RL) algorithm. A crucial issue in such design problems is to initialize/update each agent's private utility function, so as to induce best possible world utility. Traditional 'team game' solutions to this problem sidestep this issue and simply assign to each agent the world utility as its private utility function. In previous work we used the 'Collective Intelligence' framework to derive a better choice of private utility functions, one that results in world utility performance up to orders of magnitude superior to that ensuing from use of the team game utility. In this paper we extend these results. We derive the general class of private utility functions that both are easy for the individual agents to learn and that, if learned well, result in high world utility. We demonstrate experimentally that using these new utility functions can result in significantly improved performance over that of our previously proposed utility, over and above that previous utility's superiority to the conventional team game utility.

Adaptivity, both of the individual agents and of the interaction structure among the agents, seems indispensable for scaling up multi-agent systems (MAS s) in noisy environments. One important consideration in designing adaptive agents is choosing their action spaces to be as amenable as possible to machine learning techniques, especially to reinforcement learning (RL) techniques. One important way to have the interaction structure connecting agents itself be adaptive is to have the intentions and/or actions of the agents be in the input spaces of the other agents, much as in Stackelberg games. We consider both kinds of adaptivity in the design of a MAS to control network packet routing. We demonstrate on the OPNET event-driven network simulator the perhaps surprising fact that simply changing the action space of the agents to be better suited to RL can result in very large improvements in their potential performance: at their best settings, our learning-amenable router agents achieve throughputs up to three and one half times better than that of the standard Bellman-Ford routing algorithm, even when the Bellman-Ford protocol traffic is maintained. We then demonstrate that much of that potential improvement can be realized by having the agents learn their settings when the agent interaction structure is itself adaptive.

The evolution of human immunodeficiency virus type 1 (HIV-1) quasispecies at the envelope gene was studied from the time of infection in 11 men who experienced different rates of CD4+ cell count decline and 6 men with unknown dates of infection by using DNA heteroduplex mobility assays. Quasispecies were genetically homogeneous near the time of seroconversion. Subsequently, slower proviral genetic diversification and higher plasma viremia correlated with rapid CD4+ cell count decline. Except for the fastest progressors to AIDS, highly diverse quasispecies developed in all subjects within 3 to 4 years. High quasispecies diversity was then maintained for years until again becoming more homogeneous in a subset of late-stage AIDS patients. Individuals who maintained high CD4+ cell counts showed continuous genetic turnover of their complex proviral quasispecies, while more closely related sets of variants were found in longitudinal samples of severely immunocompromised patients. The limited number of variants that grew out in short-term PBMC cocultures were rare in the uncultured proviral quasispecies of healthy, long-term infected individuals but more common in vivo in patients with low CD4+ cell counts. The slower evolution of HIV-1 observed during rapid progression to AIDS and in advanced patients may reflect ineffective host-mediated selection pressures on replicating quasispecies.

Past cross-sectional studies have suggested that young adults with insulin-dependent (Type 1) diabetes mellitus (IDDM) may experience problems in their close peer relationships. For 10 years, we have followed an onset cohort of children and adolescents with IDDM (n = 57) and an age-matched group who were originally recruited after an acute illness, accident, or injury (n = 54). Now aged 19-26 years, these two groups were compared in terms of their friendship patterns, dating and love experiences, and sense of loneliness. All subjects in both groups had at least one friend. However, the IDDM group reported fewer friendships overall. The difference was accounted for by the number of less intimate friends. The two groups had similar frequencies of current romantic partners (IDDM = 63%; comparison group = 64%). While dating attitude and dating assertiveness did not differ between groups, some differences were found in terms of experiences of a primary love relationship. IDDM patients experienced less trust and sense of intimate friendship in these love relationships. No differences in loneliness were found. The preponderance of our findings indicate that the two groups had similar patterns and experiences of close peer relationships. Thus, the study does not suggest that IDDM leads to serious problems in forming social relationships for these patients during the transition to young adulthood. On the other hand, the IDDM patients' lower level of trust and intimacy within love relationships are consistent with other findings from this study suggesting specific areas of lowered self-worth that appear in social relationships.

This paper proves that for no prior probability distribution does the bootstrap (BS) distribution equal the predictive distribution, for all Bernoulli trials of some fixed size. It then proves that for no prior will the BS give the same first two moments as the predictive distribution for all size trials. It ends with an investigation of whether the BS can get the variance correct.

The “evidence” procedure for setting hyperparameters is essentially the same as the techniques of ML-II and generalized maximum likelihood. Unlike those older techniques however, the evidence procedure has been justified (and used) as an approximation to the hierarchical Bayesian calculation. We use several examples to explore the validity of this justification. Then we derive upper and (often large) lower bounds on the difference between the evidence procedure’s answer and the hierarchical Bayesian answer, for many different quantities. We prescribe a simple, easy to compute, test that can check the validity of the approximation after the fact. We also touch on subjects like the close relationship between the evidence procedure and maximum likelihood, and the self-consistency of deriving priors by “first-principles” arguments that don’t set the values of hyperparameters.

This paper is an attempt to reconcile Bayesian and non-Bayesian approaches to statistical inference, by casting both in terms of a broader formalism. In particular, this paper is an attempt to show that when one extends conventional Bayesian analysis to distinguish the truth from one’s guess for the truth, one gains a broader perspective which allows the inclusion of non-Bayesian formalisms. This perspective shows how it is possible for non-Bayesian techniques to perform well, despite their handicaps. It also highlights some difficulties with the “degree of belief” interpretation of probability.

This paper presents two Bayesian alternatives to the chi-squared test for determining whether a pair of categorical data sets were generated from the same underlying distribution. It then discusses such alternatives for the Kolmogorov- Smirnov test, which is often used when the data sets consist of real numbers.

The V3 loop of the human immunodeficiency virus type 1 (HIV-1) envelope protein is a highly variable region that is both functionally and immunologically important. Using available amino acid sequences from the V3 region, we have used an information theoretic quantity called mutual information, a measure of covariation, to quantify dependence between mutations in the loop. Certain pairs of sites, including non-contiguous sites along the sequence, do not have independent mutations but display considerable, statistically significant, covarying mutations as measured by mutual information. For the pairs of sites with the highest mutual information, specific amino acids were identified that were highly predictive of amino acids in the linked site. The observed interdependence between variable sites may have implications for structural or functional relationships; separate experimental evidence indicates functional linkage between some of the pairs of sites with high mutual information. Further specific mutational studies of the V3 loop's role in determining viral phenotype are suggested by our analyses. Also, the implications of our results may be important to consider for V3 peptide vaccine design. The methods used here are generally applicable to the study of variable proteins.

First, the correct entropic prior is computed by marginalization of alpha. This is followed by a discussion of improvements to the “evidence” approximation. Surprisingly, it appears that the approximations used to restore the famous “Susie” image may have questionable aspects.

This paper discusses the problem of extending the domain of learning sets and introduces HERBIE, a program which achieves this through graphical procedures rather than via neural networks. It is argued that for theoretical reasons HERBIE is well-suited to serving as a benchmark for measuring generalization efficacy, and therefore to serving as a means of testing claims of emergent distributed intelligence in neural nets. The successful results of tests of HERBIE as a pattern recognizer are presented, and HERBIE's behavior is favorably compared to neural nets for several real generalization problems. Finally, applications of HERBIE independent of its serving as a generalization benchmark, particularly in the area of cognitive science, are discussed.

The Douglas OGO-F Low Energy Solar Cosmic Ray Experiment measures the differential energy spectrum of protons (5 MeV to 80 MeV) and alphas (18 MeV to 160 MeV) using two double-diffused, totally depleted silicon diodes. The pulse amplitude discrimination syster, the data multiplexing scheme and the in-flight calibrator are discussed.

n/a