ترغب بنشر مسار تعليمي؟ اضغط هنا

The Naming Game on the complete graph

117   0   0.0 ( 0 )
 نشر من قبل Eric Foxall
 تاريخ النشر 2017
  مجال البحث
والبحث باللغة English
 تأليف Eric Foxall




اسأل ChatGPT حول البحث

We consider a model of language development, known as the naming game, in which agents invent, share and then select descriptive words for a single object, in such a way as to promote local consensus. When formulated on a finite and connected graph, a global consensus eventually emerges in which all agents use a common unique word. Previous numerical studies of the model on the complete graph with $n$ agents suggest that when no words initially exist, the time to consensus is of order $n^{1/2}$, assuming each agent speaks at a constant rate. We show rigorously that the time to consensus is at least $n^{1/2-o(1)}$, and that it is at most constant times $log n$ when only two words remain. In order to do so we develop sample path estimates for quasi-left continuous semimartingales with bounded jumps.



قيم البحث

اقرأ أيضاً

We examine a naming game with two agents trying to establish a common vocabulary for n objects. Such efforts lead to the emergence of language that allows for an efficient communication and exhibits some degree of homonymy and synonymy. Although homo nymy reduces the communication efficiency, it seems to be a dynamical trap that persists for a long, and perhaps indefinite, time. On the other hand, synonymy does not reduce the efficiency of communication, but appears to be only a transient feature of the language. Thus, in our model the role of synonymy decreases and in the long-time limit it becomes negligible. A similar rareness of synonymy is observed in present natural languages. The role of noise, that distorts the communicated words, is also examined. Although, in general, the noise reduces the communication efficiency, it also regroups the words so that they are more evenly distributed within the available verbal space.
In this paper, we study the role of degree mixing in the naming game. It is found that consensus can be accelerated on disassortative networks. We provide a qualitative explanation of this phenomenon based on clusters statistics. Compared with assort ative mixing, disassortative mixing can promote the merging of different clusters, thus resulting in a shorter convergence time. Other quantities, including the evolutions of the success rate, the number of total words and the number of different words, are also studied.
Red and blue particles are placed in equal proportion through-out either the complete or star graph and iteratively sampled to take simple random walk steps. Mutual annihilation occurs when particles with different colors meet. We compare the time it takes to extinguish every particle to the analogous time in the (simple to analyze) one-type setting. Additionally, we study the effect of asymmetric particle speeds.
Consider the complete graph on $n$ vertices. To each vertex assign an Ising spin that can take the values $-1$ or $+1$. Each spin $i in [n]={1,2,dots, n}$ interacts with a magnetic field $h in [0,infty)$, while each pair of spins $i,j in [n]$ interac t with each other at coupling strength $n^{-1} J(i)J(j)$, where $J=(J(i))_{i in [n]}$ are i.i.d. non-negative random variables drawn from a prescribed probability distribution $mathcal{P}$. Spins flip according to a Metropolis dynamics at inverse temperature $beta in (0,infty)$. We show that there are critical thresholds $beta_c$ and $h_c(beta)$ such that, in the limit as $ntoinfty$, the system exhibits metastable behaviour if and only if $beta in (beta_c, infty)$ and $h in [0,h_c(beta))$. Our main result are sharp asymptotics, up to a multiplicative error $1+o_n(1)$, of the average crossover time from any metastable state to the set of states with lower free energy. We use standard techniques of the potential-theoretic approach to metastability. The leading order term in the asymptotics does not depend on the realisation of $J$, while the correction terms do. The leading order of the correction term is $sqrt{n}$ times a centred Gaussian random variable with a complicated variance depending on $beta,h,mathcal{P}$ and on the metastable state. The critical thresholds $beta_c$ and $h_c(beta)$ depend on $mathcal{P}$, and so does the number of metastable states. We derive an explicit formula for $beta_c$ and identify some properties of $beta mapsto h_c(beta)$. Interestingly, the latter is not necessarily monotone, meaning that the metastable crossover may be re-entrant.
In recent times, the research field of language dynamics has focused on the investigation of language evolution, dividing the work in three evolutive steps, according to the level of complexity: lexicon, categories and grammar. The Naming Game is a s imple model capable of accounting for the emergence of a lexicon, intended as the set of words through which objects are named. We introduce a stochastic modification of the Naming Game model with the aim of characterizing the emergence of a new language as the result of the interaction of agents. We fix the initial phase by splitting the population in two sets speaking either language A or B. Whenever the result of the interaction of two individuals results in an agent able to speak both A and B, we introduce a finite probability that this state turns into a new idiom C, so to mimic a sort of hybridization process. We study the system in the space of parameters defining the interaction, and show that the proposed model displays a rich variety of behaviours, despite the simple mean field topology of interactions.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا