Search

Structured game representations have recently attracted interest as models for multi-agent artificial intelligence scenarios, with rational behavior most commonly characterized by Nash equilibria. This paper presents efficient, exact algorithms for computing Nash equilibria in structured game representations, including both graphical games and multi-agent influence diagrams (MAIDs). The algorithms are derived from a continuation method for normal-form and extensive-form games due to Govindan and Wilson; they follow a trajectory through a space of perturbed games and their equilibria, exploiting game structure through fast computation of the Jacobian of the payoff function. They are theoretically guaranteed to find at least one equilibrium of the game, and may find more. Our approach provides the first efficient algorithm for computing exact equilibria in graphical games with arbitrary topology, and the first algorithm to exploit fine-grained structural properties of MAIDs. Experimental results are presented demonstrating the effectiveness of the algorithms and comparing them to predecessors. The running time of the graphical game algorithm is similar to, and often better than, the running time of previous approximate algorithms. The algorithm for MAIDs can effectively solve games that are much larger than those solvable by previous methods.

This paper addresses the problem of planning under uncertainty in large Markov Decision Processes (MDPs). Factored MDPs represent a complex state space using state variables and the transition model using a dynamic Bayesian network. This representation often allows an exponential reduction in the representation size of structured MDPs, but the complexity of exact solution algorithms for such MDPs can grow exponentially in the representation size. In this paper, we present two approximate solution algorithms that exploit structure in factored MDPs. Both use an approximate value function represented as a linear combination of basis functions, where each basis function involves only a small subset of the domain variables. A key contribution of this paper is that it shows how the basic operations of both algorithms can be performed efficiently in closed form, by exploiting both additive and context-specific structure in a factored MDP. A central element of our algorithms is a novel linear program decomposition technique, analogous to variable elimination in Bayesian networks, which reduces an exponentially large LP to a provably equivalent, polynomial-sized one. One algorithm uses approximate linear programming, and the second approximate dynamic programming. Our dynamic programming algorithm is novel in that it uses an approximation based on max-norm, a technique that more directly minimizes the terms that appear in error bounds for approximate MDP algorithms. We provide experimental results on problems with over 10^40 states, demonstrating a promising indication of the scalability of our approach, and compare our algorithm to an existing state-of-the-art approach, showing, in some problems, exponential gains in computation time.

We review the principle and methodology of leakage radiation microscopy (LRM) applied to surface plasmon polaritons (SPPs). Therefore we first analyse in detail the electromagnetic theory of leaky SPP waves. We show that LRM is a versatile optical far-field method allowing direct quantitative imaging and analysis of SPP propagation on thin metal films. We illustrate the LRM potentiality by analyzing the propagation of SPP waves interacting with several two dimensional plasmonic devices realized and studied in the recent years., Comment: European Materials Research Society (E-MRS) Spring Meeting, Strasbourg, May 2007, Materials Science and Engineering B 149, 220 (2008)

Given a knowledge base KB containing first-order and statistical facts, we consider a principled method, called the random-worlds method, for computing a degree of belief that some formula Phi holds given KB. If we are reasoning about a world or system consisting of N individuals, then we can consider all possible worlds, or first-order models, with domain {1,...,N} that satisfy KB, and compute the fraction of them in which Phi is true. We define the degree of belief to be the asymptotic value of this fraction as N grows large. We show that when the vocabulary underlying Phi and KB uses constants and unary predicates only, we can naturally associate an entropy with each world. As N grows larger, there are many more worlds with higher entropy. Therefore, we can use a maximum-entropy computation to compute the degree of belief. This result is in a similar spirit to previous work in physics and artificial intelligence, but is far more general. Of equal interest to the result itself are the limitations on its scope. Most importantly, the restriction to unary predicates seems necessary. Although the random-worlds method makes sense in general, the connection to maximum entropy seems to disappear in the non-unary case. These observations suggest unexpected limitations to the applicability of maximum-entropy methods., Comment: See http://www.jair.org/ for any accompanying files

We report far infrared transmission measurements on single crystal samples derived from Bi$_{2}$Sr$_{2}$CaCu$_{2}$O$_{8}$. The impurity scattering rate of the samples was varied by electron-beam irradiation, 50MeV $^{16}$O$^{+6}$ ion irradiation, heat treatment in vacuum, and Y doping. Although substantial changes in the infrared spectra were produced, in no case was a feature observed that could be associated with the superconducting energy gap. These results all but rule out ``clean limit'' explanations for the absence of the spectroscopic gap in this material, and provide evidence that the superconductivity in Bi$_{2}$Sr$_{2}$CaCu$_{2}$O$_{8}$ is gapless., Comment: 4 pages and 3 postscript figures attached. REVTEX v3.0. Accepted for publication in Phys. Rev. Lett. IRDIRTY