Search

We consider goodness-of-fit tests for the distribution of the composed error in Stochastic Frontier Models. The proposed test statistic utilizes the characteristic function of the composed error term, and is formulated as a weighted integral of properly standardized data. The new test statistic is shown to be consistent and computationally convenient. Simulation results are presented whereby resampling versions of the new tests are compared to classical goodness-of-fit methods., 15 pages, 6 tables

The problem of continual learning in the domain of reinforcement learning, often called non-stationary reinforcement learning, has been identified as an important challenge to the application of reinforcement learning. We prove a worst-case complexity result, which we believe captures this challenge: Modifying the probabilities or the reward of a single state-action pair in a reinforcement learning problem requires an amount of time almost as large as the number of states in order to keep the value function up to date, unless the strong exponential time hypothesis (SETH) is false; SETH is a widely accepted strengthening of the P $\neq$ NP conjecture. Recall that the number of states in current applications of reinforcement learning is typically astronomical. In contrast, we show that just $\textit{adding}$ a new state-action pair is considerably easier to implement.

Kakutani's Fixed Point theorem is a fundamental theorem in topology with numerous applications in game theory and economics. Computational formulations of Kakutani exist only in special cases and are too restrictive to be useful in reductions. In this paper, we provide a general computational formulation of Kakutani's Fixed Point Theorem and we prove that it is PPAD-complete. As an application of our theorem we are able to characterize the computational complexity of the following fundamental problems: (1) Concave Games. Introduced by the celebrated works of Debreu and Rosen in the 1950s and 60s, concave $n$-person games have found many important applications in Economics and Game Theory. We characterize the computational complexity of finding an equilibrium in such games. We show that a general formulation of this problem belongs to PPAD, and that finding an equilibrium is PPAD-hard even for a rather restricted games of this kind: strongly-concave utilities that can be expressed as multivariate polynomials of a constant degree with axis aligned box constraints. (2) Walrasian Equilibrium. Using Kakutani's fixed point Arrow and Debreu we resolve an open problem related to Walras's theorem on the existence of price equilibria in general economies. There are many results about the PPAD-hardness of Walrasian equilibria, but the inclusion in PPAD is only known for piecewise linear utilities. We show that the problem with general convex utilities is in PPAD. Along the way we provide a Lipschitz continuous version of Berge's maximum theorem that may be of independent interest.

Goodness-of-fit tests for the distribution of the composed error term in a Stochastic Frontier Model (SFM) are suggested. We focus on the case of a normal/gamma SFM and the heavy-tailed stable/gamma SFM. In the first case we use the moment generating function as tool while in the latter case the characteristic function of the error term and formulate our test statistics as weighted integrals of properly standardized data. The new tests are consistent, and for the normal/gamma SFM are shown to have an intrinsic relation to moment-based tests. The finite-sample behavior of a resampling version of the new test for the normal/gamma SFM is investigated by Monte Carlo simulations, while the corresponding test for the stable/gamma SFM is applied on several real-data sets.

Under what conditions do the behaviors of players, who play a game repeatedly, converge to a Nash equilibrium? If one assumes that the players' behavior is a discrete-time or continuous-time rule whereby the current mixed strategy profile is mapped to the next, this becomes a problem in the theory of dynamical systems. We apply this theory, and in particular the concepts of chain recurrence, attractors, and Conley index, to prove a general impossibility result: there exist games for which any dynamics is bound to have starting points that do not end up at a Nash equilibrium. We also prove a stronger result for $\epsilon$-approximate Nash equilibria: there are games such that no game dynamics can converge (in an appropriate sense) to $\epsilon$-Nash equilibria, and in fact the set of such games has positive measure. Further numerical results demonstrate that this holds for any $\epsilon$ between zero and $0.09$. Our results establish that, although the notions of Nash equilibria (and its computation-inspired approximations) are universally applicable in all games, they are also fundamentally incomplete as predictors of long term behavior, regardless of the choice of dynamics., Comment: 25 pages

The subject-verb-object (SVO) word order prevalent in English is shared by about $42\%$ of world languages. Another $45\%$ of all languages follow the SOV order, $9\%$ the VSO order, and fewer languages use the three remaining permutations. None of the many extant explanations of this phenomenon take into account the difficulty of implementing these permutations in the brain. We propose a plausible model of sentence generation inspired by the recently proposed Assembly Calculus framework of brain function. Our model results in a natural explanation of the uneven frequencies. Estimating the parameters of this model yields predictions of the relative difficulty of dis-inhibiting one brain area from another. Our model is based on the standard syntax tree, a simple binary tree with three leaves. Each leaf corresponds to one of the three parts of a basic sentence. The leaves can be activated through lock and unlock operations and the sequence of activation of the leaves implements a specific word order. More generally, we also formulate and algorithmically solve the problems of implementing a permutation of the leaves of any binary tree, and of selecting the permutation that is easiest to implement on a given binary tree.

We describe a parser of English effectuated by biologically plausible neurons and synapses, and implemented through the Assembly Calculus, a recently proposed computational framework for cognitive function. We demonstrate that this device is capable of correctly parsing reasonably nontrivial sentences. While our experiments entail rather simple sentences in English, our results suggest that the parser can be extended beyond what we have implemented, to several directions encompassing much of language. For example, we present a simple Russian version of the parser, and discuss how to handle recursion, embedding, and polysemy.

We introduce $��$-Rank, a principled evolutionary dynamics methodology for the evaluation and ranking of agents in large-scale multi-agent interactions, grounded in a novel dynamical game-theoretic solution concept called Markov-Conley chains (MCCs). The approach leverages continuous- and discrete-time evolutionary dynamical systems applied to empirical games, and scales tractably in the number of agents, the type of interactions, and the type of empirical games (symmetric and asymmetric). Current models are fundamentally limited in one or more of these dimensions and are not guaranteed to converge to the desired game-theoretic solution concept (typically the Nash equilibrium). $��$-Rank provides a ranking over the set of agents under evaluation and provides insights into their strengths, weaknesses, and long-term dynamics. This is a consequence of the links we establish to the MCC solution concept when the underlying evolutionary model's ranking-intensity parameter, $��$, is chosen to be large, which exactly forms the basis of $��$-Rank. In contrast to the Nash equilibrium, which is a static concept based on fixed points, MCCs are a dynamical solution concept based on the Markov chain formalism, Conley's Fundamental Theorem of Dynamical Systems, and the core ingredients of dynamical systems: fixed points, recurrent sets, periodic orbits, and limit cycles. $��$-Rank runs in polynomial time with respect to the total number of pure strategy profiles, whereas computing a Nash equilibrium for a general-sum game is known to be intractable. We introduce proofs that not only provide a unifying perspective of existing continuous- and discrete-time evolutionary evaluation models, but also reveal the formal underpinnings of the $��$-Rank methodology. We empirically validate the method in several domains including AlphaGo, AlphaZero, MuJoCo Soccer, and Poker.

Price of anarchy quantifies the degradation of social welfare in games due to the lack of a centralized authority that can enforce the optimal outcome. At its antipodes, mechanism design studies how to ameliorate these effects by incentivizing socially desirable behavior and implementing the optimal state as equilibrium. In practice, the responsiveness to such measures depends on the wealth of each individual. This leads to a natural, but largely unexplored, question. Does optimal mechanism design entrench, or maybe even exacerbate, social inequality? We study this question in nonatomic congestion games, arguably one of the most thoroughly studied settings from the perspectives of price of anarchy as well as mechanism design. We introduce a new model that incorporates the wealth distribution of the population and captures the income elasticity of travel time. This allows us to argue about the equality of wealth distribution both before and after employing a mechanism. We start our analysis by establishing a broad qualitative result, showing that tolls always increase inequality in symmetric congestion games under any reasonable metric of inequality, e.g., the Gini index. Next, we introduce the iniquity index, a novel measure for quantifying the magnitude of these forces towards a more unbalanced wealth distribution and show it has good normative properties (robustness to scaling of income, no-regret learning). We analyze iniquity both in theoretical settings (Pigou's network under various wealth distributions) as well as experimental ones (based on a large scale field experiment in Singapore). Finally, we provide an algorithm for computing optimal tolls for any point of the trade-off of relative importance of efficiency and equality. We conclude with a discussion of our findings in the context of theories of justice as developed in contemporary social sciences., Comment: 32 pages, 16 figures

Humans possess the capability to reason at an abstract level and to structure information into abstract categories, but the underlying neural processes have remained unknown. Experimental evidence has recently emerged for the organization of an important aspect of abstract reasoning: for assigning words to semantic roles in a sentence, such as agent (or subject) and patient (or object). Using minimal assumptions, we show how such a binding of words to semantic roles emerges in a generic spiking neural network through Hebbian plasticity. The resulting model is consistent with the experimental data and enables new computational functionalities such as structured information retrieval, copying data, and comparisons. It thus provides a basis for the implementation of more demanding cognitive computations by networks of spiking neurons., Comment: 23 pages, 5 figures

It was recently shown \cite{STV} that satisfiability is polynomially solvable when the incidence graph is an interval bipartite graph (an interval graph turned into a bipartite graph by omitting all edges within each partite set). Here we relax this condition in several directions: First, we show that it holds for $k$-interval bigraphs, bipartite graphs which can be converted to interval bipartite graphs by adding to each node of one side at most $k$ edges; the same result holds for the counting and the weighted maximization version of satisfiability. Second, given two linear orders, one for the variables and one for the clauses, we show how to find, in polynomial time, the smallest $k$ such that there is a $k$-interval bigraph compatible with these two orders. On the negative side we prove that, barring complexity collapses, no such extensions are possible for CSPs more general than satisfiability. We also show NP-hardness of recognizing 1-interval bigraphs.

Grid cells, discovered more than a decade ago [5], are neurons in the brain of mammals that fire when the animal is located near certain specific points in its familiar terrain. Intriguingly, these points form, for a single cell, a two-dimensional triangular grid, not unlike our Figure 3. Grid cells are widely believed to be involved in path integration, that is, the maintenance of a location state through the summation of small displacements. We provide theoretical evidence for this assertion by showing that cells with grid-like tuning curves are indeed well adapted for the path integration task. In particular we prove that, in one dimension under Gaussian noise, the sensitivity of measuring small displacements is maximized by a population of neurons whose tuning curves are near-sinusoids -- that is to say, with peaks forming a one-dimensional grid. We also show that effective computation of the displacement is possible through a second population of cells whose sinusoid tuning curves are in phase difference from the first. In two dimensions, under additional assumptions it can be shown that measurement sensitivity is optimized by the product of two sinusoids, again yielding a grid-like pattern. We discuss the connection of our results to the triangular grid pattern observed in animals.

Reduced Axin expression has been associated with an aggressive behavior in lung and esophageal squamous cell carcinomas. Its role in breast cancer has not been defined. The aim of our study was to investigate the expression pattern of Axin protein in invasive breast carcinomas, in relation to the behavior and prognosis of the disease. Immunohistochemistry was performed for the detection of Axin expression in 232 breast cancer tissues. Univariate and multivariate statistical analyses were used to assess the relation of Axin expression with classic clinicopathological parameters, patients' survival and various biologic markers Human Epidermal Factor-2 (HER-2), Ki-67, topoIIα, glycogen synthase kinase-3β (GSK-3β)]. Preserved cytoplasmic Axin expression was positively correlated to lymph node invasion, HER-2 and GSK-3β and inversely to Ki-67 and topoIIα. Nuclear Axin was positively associated with tumor size. Stromal Axin showed a parallel association with lymph node status and HER-2. In the subgroup of lobular breast carcinomas, preserved Axin was found to exert an unfavorable impact on patients' overall survival. Our findings indicate, for the first time, that in invasive breast cancer preserved Axin expression is associated with a more aggressive phenotype and that in the discrete subtype of lobular breast carcinomas Axin negatively influences patients' overall survival.

When agents with independent priors bid for a single item, Myerson's optimal auction maximizes expected revenue, whereas Vickrey's second-price auction optimizes social welfare. We address the natural question of trade-offs between the two criteria, that is, auctions that optimize, say, revenue under the constraint that the welfare is above a given level. If one allows for randomized mechanisms, it is easy to see that there are polynomial-time mechanisms that achieve any point in the trade-off (the Pareto curve) between revenue and welfare. We investigate whether one can achieve the same guarantees using deterministic mechanisms. We provide a negative answer to this question by showing that this is a (weakly) NP-hard problem. On the positive side, we provide polynomial-time deterministic mechanisms that approximate with arbitrary precision any point of the trade-off between these two fundamental objectives for the case of two bidders, even when the valuations are correlated arbitrarily. The major problem left open by our work is whether there is such an algorithm for three or more bidders with independent valuation distributions.

We develop a new technique of proving lower bounds for the randomized communication complexity of boolean functions in the multiparty 'number on the forehead' model. Our method is based on the notion of voting polynomial degree of functions and extends the degree-discrepancy lemma in the recent work of Sherstov (2007). Using this we prove that depth three circuits consisting of a MAJORITY gate at the output, gates computing arbitrary symmetric function at the second layer and arbitrary gates of bounded fan-in at the base layer i.e. circuits of type MAJ o SYMM o ANYO(1) cannot simulate the circuit class AC0 in sub-exponential size. Further, even if the fan-in of the bottom ANY gates are increased to o(log log n), such circuits cannot simulate AC0 in quasi-polynomial size. This is in contrast to the classical result of Yao and Beigel-Tarui that shows that such circuits, having only MAJORITY gales, can simulate the class ACC0 in quasi-polynomial size when the bottom fan-in is increased to poly-logarithmic size. In the second part, we simplify the arguments in the breakthrough work of Bourgain (2005) for obtaining exponentially small upper bounds on the correlation between the boolean function MODq and functions represented bv polynomials of small degree over Zm, when m,q ges 2 are co-prime integers. Our calculation also shows similarity with techniques used to estimate discrepancy of functions in the multiparty communication setting. This results in a slight improvement of the estimates of Bourgain et al. (2005). It is known that such estimates imply that circuits of type MAJ o MODm o ANDisin log n cannot compute the MODq function in sub-exponential size. It remains a major open question to determine if such circuits can simulate ACC0 in polynomial size when the bottom fan-in is increased to poly-logarithmic size.

We consider a modified notion of planarity, in which two nations of a map are considered adjacent when they share any point of their boundaries (not necessarily an edge, as planarity requires). Such adjacencies define a map graph. We give an NP characterization for such graphs, and a cubic time recognition algorithm for a restricted version: given a graph, decide whether it is realized by adjacencies in a map without holes, in which at most four nations meet at any point., 46 pages, LaTeX with 41 PS figures; see http://www.mathcs.emory.edu/~mic/mapgraphs/ for hi-res figures

ISBN:978-3-95404-125-1