1,721,463 research outputs found
Stable strategies of direct and indirect reciprocity across all social dilemmas
No full textSocial dilemmas are collective-action problems where individual interests are at odds with group interests. Such dilemmas occur frequently at all scales of human interactions. When dealing with collective-action problems, people often act reciprocally. They adjust their behavior to match the previous behavior of the recipient. The literature distinguishes two kinds of reciprocity. According to direct reciprocity, individuals react to their immediate experiences with the recipient. They are more likely to cooperate if the recipient previously cooperated with them. According to indirect reciprocity, individuals react to the recipient's general behavior, irrespectively of whether or not they benefited directly. In practice, the two kinds of reciprocity are often intertwined; people typically base their decisions on both direct experiences and indirect observations. Yet only recently have researchers begun to explore how the two kinds of reciprocity interact. So far, this research only addresses a single type of social dilemma, the donation game, where the effects of individual behaviors are independent. Instead, here we allow for all pairwise social dilemmas. By applying novel techniques to generalize the theory of zero-determinant strategies, we establish an important proof of principle: In all social dilemmas, socially optimal outcomes can be sustained as an equilibrium, using either direct or indirect reciprocity, or arbitrary mixtures thereof. These results neither require games to be repeated infinitely often, nor that individual opinions are synchronized. In this way, we considerably generalize the scope of models of reciprocity, and we build further bridges between the literatures on direct and indirect reciprocity.
Čas fixace v Moranově procesu při silné selekci
No full textMoranův proces je model, který se používá v evoluční dynamice ke studiu přírozeného výběru. V tomto procesu máme populaci jedinců, která se vyvíjí v krocích. V jednom kroku je vybrán náhodný jedinec s pravděpodobností úměrnou své zdatnosti (fitness), a ten se rozšíří do svého náhodně vybraného souseda. Klasickým předmětem studia je uvažovat jedince s dědičnou mutací a zkoumat osud této mutace v čase. Tato práce se zabývá upravenou verzí Moranova procesu, která odpovídá silné selekci, tak jako je tomu například v dynamice invazivních druhů. V tomto procesu se rozmno- žují pouze mutantní jedinci, kteří nakonec ovládnou celou populaci. Klíčovou veličinou, kterou studujeme, je tzv. čas fixace, tedy očekáváná doba než se všichni jedinci stanou mutanty. V práci ukazujeme těsné horní a dolní odhady na čas fixace pro obecnou strukturu po- pulace a zlepšujeme je pro některé třídy. Kromě toho dokazujeme přesné doby fixace pro některé konkrétní struktury populace.Moran process is a model used in evolutionary dynamics to study natural selection. In this process, a population of individuals evolves in steps. In one step a random individual is selected with probability proportional to its fitness and spreads to its randomly selected neighbor. The classical course of study is to consider an individual with a hereditary mutation and examine the fate of this mutation in time. This thesis investigates a modified version of the Moran process that corresponds to the strong selection, as in the dynamics of invasive species. In this process, only the mutant individuals spread and eventually conquer the whole population. The key quantity that we study is the so-called fixation time, which is the expected time until all individuals become mutants. We give tight upper and lower bounds for fixation time on a general population structure and refine them for some classes. Additionally, we compute the precise fixation times on some specific population structures.Computer Science Institute of Charles UniversityInformatický ústav Univerzity KarlovyMatematicko-fyzikální fakultaFaculty of Mathematics and Physic
Výpočetní problémy vztahující se ke grafovým strukturám v evoluci
No full textV této práci se zabýváme stochastickou hrou, která ilustruje koncept trestu a ukazuje, jak může trest navýšit kooperaci. Nejprve představíme základy teorie her, Markovových řetězců a stochastických her. Poté vysvětlíme, jak lze použít evoluci k výpočtu očekávaného množství kooperace ve hře. Na konci práce ukážeme výsledky simulací a numerických výpočtů, které potvrzují, že trest může mít pozitivní vliv na množství kooperace. Powered by TCPDF (www.tcpdf.org)In this work we study certain stochastic game that illustrates the concept of punishment and that shows how punishment can improve cooperation. First we introduce the basics of game theory, Markov chains and stochastic games. Then we explain how evolutionary dynamics can be used to evaluate the expected amount of cooperation in a game. Finally we run simulations and do some numerical computations that show how punishment can improve cooperation. Powered by TCPDF (www.tcpdf.org)Department of Applied MathematicsKatedra aplikované matematikyMatematicko-fyzikální fakultaFaculty of Mathematics and Physic
Computational Problems Related to Graph Structures in Evolution
No full textIn this work we study certain stochastic game that illustrates the concept of punishment and that shows how punishment can improve cooperation. First we introduce the basics of game theory, Markov chains and stochastic games. Then we explain how evolutionary dynamics can be used to evaluate the expected amount of cooperation in a game. Finally we run simulations and do some numerical computations that show how punishment can improve cooperation. Powered by TCPDF (www.tcpdf.org
Fixation time in Moran process under strong selection
No full textMoran process is a model used in evolutionary dynamics to study natural selection. In this process, a population of individuals evolves in steps. In one step a random individual is selected with probability proportional to its fitness and spreads to its randomly selected neighbor. The classical course of study is to consider an individual with a hereditary mutation and examine the fate of this mutation in time. This thesis investigates a modified version of the Moran process that corresponds to the strong selection, as in the dynamics of invasive species. In this process, only the mutant individuals spread and eventually conquer the whole population. The key quantity that we study is the so-called fixation time, which is the expected time until all individuals become mutants. We give tight upper and lower bounds for fixation time on a general population structure and refine them for some classes. Additionally, we compute the precise fixation times on some specific population structures
On the Recognition of Four-Directional Orthogonal Ray Graphs
Full text linkOrthogonal ray graphs are the intersection graphs of horizontal and vertical rays (i.e. half-lines) in the plane. If the rays can have any possible orientation (left/right/up/down) then the graph is a 4-directional orthogonal ray graph (4-DORG). Otherwise, if all rays are only pointing into the positive x and y directions, the intersection graph is a 2-DORG. Similarly, for 3-DORGs, the horizontal rays can have any direction but the vertical ones can only have the positive direction. The recognition problem of 2-DORGs, which are a nice subclass of bipartite comparability graphs, is known to be polynomial, while the recognition problems for 3-DORGs and 4-DORGs are open. Recently it has been shown that the recognition of unit grid intersection graphs, a superclass of 4-DORGs, is NP-complete. In this paper we prove that the recognition problem of 4-DORGs is polynomial, given a partition {L,R,U,D} of the vertices of G (which corresponds to the four possible ray directions). For the proof, given the graph G, we first construct two cliques G 1,G 2 with both directed and undirected edges. Then we successively augment these two graphs, constructing eventually a graph TeX with both directed and undirected edges, such that G has a 4-DORG representation if and only if TeX has a transitive orientation respecting its directed edges. As a crucial tool for our analysis we introduce the notion of an S-orientation of a graph, which extends the notion of a transitive orientation. We expect that our proof ideas will be useful also in other situations. Using an independent approach we show that, given a permutation π of the vertices of U (π is the order of y-coordinates of ray endpoints for U), while the partition {L,R} of V ∖ U is not given, we can still efficiently check whether G has a 3-DORG representation
Strong Completeness for Markovian Logics
Full text linkIn this paper we present Hilbert-style axiomatizations for three logics for reasoning about continuous-space Markov processes (MPs): (i) a logic for MPs defined for probability distributions on measurable state spaces, (ii) a logic for MPs defined for sub-probability distributions and (iii) a logic defined for arbitrary distributions. These logics are not compact so one needs infinitary rules in order to obtain strong completeness results.We propose a new infinitary rule that replaces the so-called Countable Additivity Rule (CAR) currently used in the literature to address the problem of proving strong completeness for these and similar logics. Unlike the CAR, our rule has a countable set of instances; consequently it allows us to apply the Rasiowa-Sikorski lemma for establishing strong completeness. Our proof method is novel and it can be used for other logics as well.<br/
Revisiting Space in Proof Complexity: Treewidth and Pathwidth
No full textSo-called ordered variants of the classical notions of pathwidth and treewidth are introduced and proposed as proof theoretically meaningful complexity measures for the directed acyclic graphs underlying proofs. The ordered pathwidth of a proof is shown to be roughly the same as its formula space. Length-space lower bounds for R(k)-refutations are generalized to arbitrary infinity axioms and strengthened in that the space measure is relaxed to ordered treewidth
- …
