Search for: All records

A fundamental shortcoming of the concept of Nash equilibrium is its computational intractability: approximating Nash equilibria in normal-form games is PPAD-hard. In this paper, inspired by the ideas of smoothed analysis, we introduce a relaxed variant of Nash equilibrium called σ-smooth Nash equilibrium, for a {smoothness parameter} σ. In a σ-smooth Nash equilibrium, players only need to achieve utility at least as high as their best deviation to a σ-smooth strategy, which is a distribution that does not put too much mass (as parametrized by σ) on any fixed action. We distinguish two variants of σ-smooth Nash equilibria: strong σ-smooth Nash equilibria, in which players are required to play σ-smooth strategies under equilibrium play, and weak σ-smooth Nash equilibria, where there is no such requirement. We show that both weak and strong σ-smooth Nash equilibria have superior computational properties to Nash equilibria: when σ as well as an approximation parameter ϵ and the number of players are all constants, there is a {constant-time} randomized algorithm to find a weak ϵ-approximate σ-smooth Nash equilibrium in normal-form games. In the same parameter regime, there is a polynomial-time deterministic algorithm to find a strong ϵ-approximate σ-smooth Nash equilibrium in a normal-form game. These results stand in contrast to the optimal algorithm for computing ϵ-approximate Nash equilibria, which cannot run in faster than quasipolynomial-time, subject to complexity-theoretic assumptions. We complement our upper bounds by showing that when either σ or ϵ is an inverse polynomial, finding a weak ϵ-approximate σ-smooth Nash equilibria becomes computationally intractable. Our results are the first to propose a variant of Nash equilibrium which is computationally tractable, allows players to act independently, and which, as we discuss, is justified by an extensive line of work on individual choice behavior in the economics literature. 

We initiate the study of smoothed analysis for the sequential probability assignment problem with contexts. We study information-theoretically optimal minmax rates as well as a framework for algorithmic reduction involving the maximum likelihood estimator oracle. Our approach establishes a general-purpose reduction from minimax rates for sequential probability assignment for smoothed adversaries to minimax rates for transductive learning. This leads to optimal (logarithmic) fast rates for parametric classes and classes with finite VC dimension. On the algorithmic front, we develop an algorithm that efficiently taps into the MLE oracle, for general classes of functions. We show that under general conditions this algorithmic approach yields sublinear regret. 

Nearly, all dense suspensions undergo dramatic and abrupt thickening transitions in their flow behavior when sheared at high stresses. Such transitions occur when the dominant interactions between the suspended particles shift from hydrodynamic to frictional. Here, we interpret abrupt shear thickening as a precursor to a rigidity transition and give a complete theory of the viscosity in terms of a universal crossover scaling function from the frictionless jamming point to a rigidity transition associated with friction, anisotropy, and shear. Strikingly, we find experimentally that for two different systems—cornstarch in glycerol and silica spheres in glycerol—the viscosity can be collapsed onto a single universal curve over a wide range of stresses and volume fractions. The collapse reveals two separate scaling regimes due to a crossover between frictionless isotropic jamming and frictional shear jamming, with different critical exponents. The material-specific behavior due to the microscale particle interactions is incorporated into a scaling variable governing the proximity to shear jamming, that depends on both stress and volume fraction. This reformulation opens the door to importing the vast theoretical machinery developed to understand equilibrium critical phenomena to elucidate fundamental physical aspects of the shear thickening transition.

 

A thorough study is made of the dependences on salt concentration and polymer chain lengths of the low-frequency plateau of coacervates of poly (diallyl dimethyl ammonium chloride), PDADMAC, and poly (sodium 4-styrenesulfonate), PSS. The reliability and reproducibility of these measurements are carefully checked by determining the frequency-dependent stress limits of the rheometer through the use of reference fluids and by repeat experiments with coacervates. Long-time frequency sweeps show that coacervates with less salt are more repeatable than those with higher salt. A low-frequency plateau reliably appears only below a critical salt concentration, and the magnitude of the plateau depends strongly on salt concentration and chain lengths of both polycation and polyanion. It is only present for the molecular weight of the polycation, PDADMAC, higher than 100 kDa, but the magnitude of the plateau is more strongly influenced by the chain length of the polyanion, PSS. Possible causes of the low-frequency plateau are discussed. 

A full understanding of the sequence of processes exhibited by yield stress fluids under large amplitude oscillatory shearing is developed using multiple experimental and analytical approaches. A novel component rate Lissajous curve, where the rates at which strain is acquired unrecoverably and recoverably are plotted against each other, is introduced and its utility is demonstrated by application to the analytical responses of four simple viscoelastic models. Using the component rate space, yielding and unyielding are identified by changes in the way strain is acquired, from recoverably to unrecoverably and back again. The behaviors are investigated by comparing the experimental results with predictions from the elastic Bingham model that is constructed using the Oldroyd–Prager formalism and the recently proposed continuous model by Kamani, Donley, and Rogers in which yielding is enhanced by rapid acquisition of elastic strain. The physical interpretation gained from the transient large amplitude oscillatory shear (LAOS) data is compared to the results from the analytical sequence of physical processes framework and a novel time-resolved Pipkin space. The component rate figures, therefore, provide an independent test of the interpretations of the sequence of physical processes analysis that can also be applied to other LAOS analysis frameworks. Each of these methods, the component rates, the sequence of physical processes analysis, and the time-resolved Pipkin diagrams, unambigiously identifies the same material physics, showing that yield stress fluids go through a sequence of physical processes that includes elastic deformation, gradual yielding, plastic flow, and gradual unyielding.