Página 28 dos resultados de 10730 itens digitais encontrados em 0.084 segundos

Higher-Order Decision Theory

Hedges, Jules; Oliva, Paulo; Sprits, Evguenia; Winschel, Viktor; Zahn, Philipp
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
463.0107%
Classical decision theory models behaviour in terms of utility maximisation where utilities represent rational preference relations over outcomes. However, empirical evidence and theoretical considerations suggest that we need to go beyond this framework. We propose to represent goals by higher-order functions or operators that take other functions as arguments where the max and argmax operators are special cases. Our higher-order functions take a context function as their argument where a context represents a process from actions to outcomes. By that we can define goals being dependent on the actions and the process in addition to outcomes only. This formulation generalises outcome based preferences to context-dependent goals. We show how to uniformly represent within our higher-order framework classical utility maximisation but also various other extensions that have been debated in economics.; Comment: arXiv admin note: text overlap with arXiv:1409.7411

A general theory of equilibrium behavior

Avramopoulos, Ioannis
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 04/04/2013 Português
Relevância na Pesquisa
463.0107%
Economists were content with the concept of the Nash equilibrium as game theory's solution concept until Daskalakis, Goldberg, and Papadimitriou showed that finding a Nash equilibrium is most likely a computationally hard problem, a result that set off a deep scientific crisis. Motivated, in part, by their result, in this paper, we propose a general theory of equilibrium behavior in vector fields (and, therefore, also noncooperative games). Our line of discourse is to show that these universal in nature mathematical objects are endowed with significant structure, which we probe to unearth atypical, previously unidentified, equilibrium behavior.

The nature of individual choice: a formalism for utility function based on set theory

Shabani, Redjan F.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 26/10/2010 Português
Relevância na Pesquisa
463.0107%
In the theory of social choice the research is focused around the projection of individual preference orders to the social preference order. Also, the justification of the preference order formalism begins with the concept of utility i.e. an alternative is preferred to another one if the utility over the first is higher then the utility over the second. In this paper is proposed an ideal model of measuring utilities by considering individuals and alternatives no more as atomic concepts but as being composed by other entities. Furthermore is proposed a formal definition of evaluation processes based on utilities.

Stability of Mixed-Strategy-Based Iterative Logit Quantal Response Dynamics in Game Theory

Zhuang, Qian; Di, Zegnru; Wu, Jinshan
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 14/10/2013 Português
Relevância na Pesquisa
463.0107%
Using the Logit quantal response form as the response function in each step, the original definition of static quantal response equilibrium (QRE) is extended into an iterative evolution process. QREs remain as the fixed points of the dynamic process. However, depending on whether such fixed points are the long-term solutions of the dynamic process, they can be classified into stable (SQREs) and unstable (USQREs) equilibriums. This extension resembles the extension from static Nash equilibriums (NEs) to evolutionary stable solutions in the framework of evolutionary game theory. The relation between SQREs and other solution concepts of games, including NEs and QREs, is discussed. Using experimental data from other published papers, we perform a preliminary comparison between SQREs, NEs, QREs and the observed behavioral outcomes of those experiments. For certain games, we determine that SQREs have better predictive power than QREs and NEs.

A Decidable Theory of Skiplists of Unbounded Size and Arbitrary Height

Sánchez, César; Sánchez, Alejandro
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 18/01/2013 Português
Relevância na Pesquisa
463.0107%
This paper presents a theory of skiplists of arbitrary height, and shows decidability of the satisfiability problem for quantifier-free formulas. A skiplist is an imperative software data structure that implements sets by maintaining several levels of ordered singly-linked lists in memory, where each level is a sublist of its lower levels. Skiplists are widely used in practice because they offer a performance comparable to balanced binary trees, and can be implemented more efficiently. To achieve this performance, most implementations dynamically increment the height (the number of levels). Skiplists are difficult to reason about because of the dynamic size (number of nodes) and the sharing between the different layers. Furthermore, reasoning about dynamic height adds the challenge of dealing with arbitrary many levels. The first contribution of this paper is the theory TSL that allows to express the heap memory layout of a skiplist of arbitrary height. The second contribution is a decision procedure for the satisfiability prob- lem of quantifier-free TSL formulas. The last contribution is to illustrate the formal verification of a practical skiplist implementation using this decision procedure.; Comment: 25 pages

Steps towards a theory and calculus of aliasing

Meyer, Bertrand
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
463.0107%
A theory, graphical notation, mathematical calculus and implementation for finding whether two given expressions can, at execution time, denote references attached to the same object. Intended as the basis for a comprehensive solution to the "frame problem" and as a complement to, or even a replacement for, separation logic, shape analysis, ownership types and dynamic frames.; Comment: Revision of original JOT paper. To appear in IJSI (International Journal of Software and Informatics) in 2011. The original title was: The theory and calculus of aliasing

On CSP and the Algebraic Theory of Effects

van Glabbeek, Rob; Plotkin, Gordon
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 30/07/2010 Português
Relevância na Pesquisa
463.0107%
We consider CSP from the point of view of the algebraic theory of effects, which classifies operations as effect constructors or effect deconstructors; it also provides a link with functional programming, being a refinement of Moggi's seminal monadic point of view. There is a natural algebraic theory of the constructors whose free algebra functor is Moggi's monad; we illustrate this by characterising free and initial algebras in terms of two versions of the stable failures model of CSP, one more general than the other. Deconstructors are dealt with as homomorphisms to (possibly non-free) algebras. One can view CSP's action and choice operators as constructors and the rest, such as concealment and concurrency, as deconstructors. Carrying this programme out results in taking deterministic external choice as constructor rather than general external choice. However, binary deconstructors, such as the CSP concurrency operator, provide unresolved difficulties. We conclude by presenting a combination of CSP with Moggi's computational {\lambda}-calculus, in which the operators, including concurrency, are polymorphic. While the paper mainly concerns CSP, it ought to be possible to carry over similar ideas to other process calculi.

Homotopy limits in type theory

Avigad, Jeremy; Kapulkin, Chris; Lumsdaine, Peter LeFanu
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
463.0107%
Working in homotopy type theory, we provide a systematic study of homotopy limits of diagrams over graphs, formalized in the Coq proof assistant. We discuss some of the challenges posed by this approach to formalizing homotopy-theoretic material. We also compare our constructions with the more classical approach to homotopy limits via fibration categories.; Comment: 33 pages; v3: theorem numbering changed since v2 to match journal version

Theory of Programs

Meyer, Bertrand
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
463.0107%
A general theory of programs, programming and programming languages built up from a few concepts of elementary set theory. Derives, as theorems, properties treated as axioms by classic approaches to programming. Covers sequential and concurrent computation.

The Euler-Poincare theory of Metamorphosis

Holm, Darryl D.; Trouve, Alain; Younes, Laurent
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 04/06/2008 Português
Relevância na Pesquisa
463.0107%
In the pattern matching approach to imaging science, the process of ``metamorphosis'' is template matching with dynamical templates. Here, we recast the metamorphosis equations of into the Euler-Poincare variational framework of and show that the metamorphosis equations contain the equations for a perfect complex fluid \cite{Ho2002}. This result connects the ideas underlying the process of metamorphosis in image matching to the physical concept of order parameter in the theory of complex fluids. After developing the general theory, we reinterpret various examples, including point set, image and density metamorphosis. We finally discuss the issue of matching measures with metamorphosis, for which we provide existence theorems for the initial and boundary value problems.

The Monty Hall Problem in the Game Theory Class

Gnedin, Alexander
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 01/07/2011 Português
Relevância na Pesquisa
463.0107%
The basic Monty Hall problem is explored to introduce into the fundamental concepts of the game theory and to give a complete Bayesian and a (noncooperative) game-theoretic analysis of the situation. Simple combinatorial arguments are used to exclude the holding action and to find minimax solutions.; Comment: 18 pages, 1 color figure

Preference aggregation theory without acyclicity: The core without majority dissatisfaction

Kumabe, Masahiro; Mihara, H. Reiju
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 03/07/2011 Português
Relevância na Pesquisa
463.0107%
Acyclicity of individual preferences is a minimal assumption in social choice theory. We replace that assumption by the direct assumption that preferences have maximal elements on a fixed agenda. We show that the core of a simple game is nonempty for all profiles of such preferences if and only if the number of alternatives in the agenda is less than the Nakamura number of the game. The same is true if we replace the core by the core without majority dissatisfaction, obtained by deleting from the agenda all the alternatives that are non-maximal for all players in a winning coalition. Unlike the core, the core without majority dissatisfaction depends only on the players' sets of maximal elements and is included in the union of such sets. A result for an extended framework gives another sense in which the core without majority dissatisfaction behaves better than the core.; Comment: 27+3 pages

Theory and applications of lattice point methods for binomial ideals

Miller, Ezra
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 14/09/2010 Português
Relevância na Pesquisa
463.0107%
This survey of methods surrounding lattice point methods for binomial ideals begins with a leisurely treatment of the geometric combinatorics of binomial primary decomposition. It then proceeds to three independent applications whose motivations come from outside of commutative algebra: hypergeometric systems, combinatorial game theory, and chemical dynamics. The exposition is aimed at students and researchers in algebra; it includes many examples, open problems, and elementary introductions to the motivations and background from outside of algebra.; Comment: 57 pages, 31 figures; to appear in proceedings of 2009 Abel Symposium (Voss, Norway)

Multiplicative Updates in Coordination Games and the Theory of Evolution

Chastain, Erick; Livnat, Adi; Papadimitriou, Christos; Vazirani, Umesh
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 15/08/2012 Português
Relevância na Pesquisa
463.0107%
We study the population genetics of Evolution in the important special case of weak selection, in which all fitness values are assumed to be close to one another. We show that in this regime natural selection is tantamount to the multiplicative updates game dynamics in a coordination game between genes. Importantly, the utility maximized in this game, as well as the amount by which each allele is boosted, is precisely the allele's mixability, or average fitness, a quantity recently proposed in [1] as a novel concept that is crucial in understanding natural selection under sex, thus providing a rigorous demonstration of that insight. We also prove that the equilibria in two-person coordination games can have large supports, and thus genetic diversity does not suffer much at equilibrium. Establishing large supports involves answering through a novel technique the following question: what is the probability that for a random square matrix A both systems Ax = 1 and A^T y = 1 have positive solutions? Both the question and the technique may be of broader interest. [1] A. Livnat, C. Papadimitriou, J. Dushoff, and M.W. Feldman. A mixability theory for the role of sex in evolution. Proceedings of the National Academy of Sciences, 105(50):19803-19808...

Graph Theory Applications in Network Security

Webb, Jonathan; Docemmilli, Fernando; Bonin, Mikhail
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 15/11/2015 Português
Relevância na Pesquisa
463.0107%
Graph theory has become a very critical component in many applications in the computing field including networking and security. Unfortunately, it is also amongst the most complex topics to understand and apply. In this paper, we review some of the key applications of graph theory in network security. We first cover some algorithmic aspects, then present network coding and its relation to routing.

Why does Deep Learning work? - A perspective from Group Theory

Paul, Arnab; Venkatasubramanian, Suresh
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
463.0107%
Why does Deep Learning work? What representations does it capture? How do higher-order representations emerge? We study these questions from the perspective of group theory, thereby opening a new approach towards a theory of Deep learning. One factor behind the recent resurgence of the subject is a key algorithmic step called pre-training: first search for a good generative model for the input samples, and repeat the process one layer at a time. We show deeper implications of this simple principle, by establishing a connection with the interplay of orbits and stabilizers of group actions. Although the neural networks themselves may not form groups, we show the existence of {\em shadow} groups whose elements serve as close approximations. Over the shadow groups, the pre-training step, originally introduced as a mechanism to better initialize a network, becomes equivalent to a search for features with minimal orbits. Intuitively, these features are in a way the {\em simplest}. Which explains why a deep learning network learns simple features first. Next, we show how the same principle, when repeated in the deeper layers, can capture higher order representations, and why representation complexity increases as the layers get deeper.; Comment: 13 pages...

Model Theory of Ultrafinitism I: Fuzzy Initial Segments of Arithmetics

Mannucci, Mirco A.; Cherubin, Rose M.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 20/11/2006 Português
Relevância na Pesquisa
463.0107%
This article is the first of an intended series of works on the model theory of Ultrafinitism. It is roughly divided into two parts. The first one addresses some of the issues related to ultrafinitistic programs, as well as some of the core ideas proposed thus far. The second part of the paper presents a model of ultrafinitistic arithmetics based on the notion of fuzzy initial segments of the standard natural numbers series. We also introduce a proof theory and a semantics for ultrafinitism through which feasibly consistent theories can be treated on the same footing as their classically consistent counterparts. We conclude with a brief sketch of a foundational program, that aims at reproducing the transfinite within the finite realm.; Comment: 31 pages, Tennenbaum Memorial invited talk

Ioco Theory for Probabilistic Automata

Gerhold, Marcus; Stoelinga, Mariëlle
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 09/04/2015 Português
Relevância na Pesquisa
463.0107%
Model-based testing (MBT) is a well-known technology, which allows for automatic test case generation, execution and evaluation. To test non-functional properties, a number of test MBT frameworks have been developed to test systems with real-time, continuous behaviour, symbolic data and quantitative system aspects. Notably, a lot of these frameworks are based on Tretmans' classical input/output conformance (ioco) framework. However, a model-based test theory handling probabilistic behaviour does not exist yet. Probability plays a role in many different systems: unreliable communication channels, randomized algorithms and communication protocols, service level agreements pinning down up-time percentages, etc. Therefore, a probabilistic test theory is of great practical importance. We present the ingredients for a probabilistic variant of ioco and define the {\pi}oco relation, show that it conservatively extends ioco and define the concepts of test case, execution and evaluation.; Comment: In Proceedings MBT 2015, arXiv:1504.01928

Categories of relations as models of quantum theory

Heunen, Chris; Tull, Sean
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
463.0107%
Categories of relations over a regular category form a family of models of quantum theory. Using regular logic, many properties of relations over sets lift to these models, including the correspondence between Frobenius structures and internal groupoids. Over compact Hausdorff spaces, this lifting gives continuous symmetric encryption. Over a regular Mal'cev category, this correspondence gives a characterization of categories of completely positive maps, enabling the formulation of quantum features. These models are closer to Hilbert spaces than relations over sets in several respects: Heisenberg uncertainty, impossibility of broadcasting, and behavedness of rank one morphisms.; Comment: In Proceedings QPL 2015, arXiv:1511.01181

Elements of Game Theory - Part I: Foundations, acts and mechanisms

Georgiou, Harris V.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 16/06/2015 Português
Relevância na Pesquisa
463.0107%
In this paper, a gentle introduction to Game Theory is presented in the form of basic concepts and examples. Minimax and Nash's theorem are introduced as the formal definitions for optimal strategies and equilibria in zero-sum and nonzero-sum games. Several elements of cooperative gaming, coalitions, voting ensembles, voting power and collective efficiency are described in brief. Analytical (matrix) and extended (tree-graph) forms of game representation is illustrated as the basic tools for identifying optimal strategies and "solutions" in games of any kind. Next, a typology of four standard nonzero-sum games is investigated, analyzing the Nash equilibria and the optimal strategies in each case. Signaling, stance and third-party intermediates are described as very important properties when analyzing strategic moves, while credibility and reputation is described as crucial factors when signaling promises or threats. Utility is introduced as a generalization of typical cost/gain functions and it is used to explain the incentives of irrational players under the scope of "rational irrationality". Finally, a brief reference is presented for several other more advanced concepts of gaming, including emergence of cooperation, evolutionary stable strategies...