skip to main content

Title: Perturbation theory for evolution of cooperation on networks

Network structure is a mechanism for promoting cooperation in social dilemma games. In the present study, we explore graph surgery, i.e., to slightly perturb the given network, towards a network that better fosters cooperation. To this end, we develop a perturbation theory to assess the change in the propensity of cooperation when we add or remove a single edge to/from the given network. Our perturbation theory is for a previously proposed random-walk-based theory that provides the threshold benefit-to-cost ratio,$$(b/c)^*$$(b/c), which is the value of the benefit-to-cost ratio in the donation game above which the cooperator is more likely to fixate than in a control case, for any finite networks. We find that$$(b/c)^*$$(b/c)decreases when we remove a single edge in a majority of cases and that our perturbation theory captures at a reasonable accuracy which edge removal makes$$(b/c)^*$$(b/c)small to facilitate cooperation. In contrast,$$(b/c)^*$$(b/c)tends to increase when we add an edge, and the perturbation theory is not good at predicting the edge addition that changes$$(b/c)^*$$(b/c)by a large amount. Our perturbation theory significantly reduces the computational complexity for calculating the outcome of graph surgery.

more » « less
Award ID(s):
Author(s) / Creator(s):
Publisher / Repository:
Springer Science + Business Media
Date Published:
Journal Name:
Journal of Mathematical Biology
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    We present the first unquenched lattice-QCD calculation of the form factors for the decay$$B\rightarrow D^*\ell \nu $$BDνat nonzero recoil. Our analysis includes 15 MILC ensembles with$$N_f=2+1$$Nf=2+1flavors of asqtad sea quarks, with a strange quark mass close to its physical mass. The lattice spacings range from$$a\approx 0.15$$a0.15fm down to 0.045 fm, while the ratio between the light- and the strange-quark masses ranges from 0.05 to 0.4. The valencebandcquarks are treated using the Wilson-clover action with the Fermilab interpretation, whereas the light sector employs asqtad staggered fermions. We extrapolate our results to the physical point in the continuum limit using rooted staggered heavy-light meson chiral perturbation theory. Then we apply a model-independent parametrization to extend the form factors to the full kinematic range. With this parametrization we perform a joint lattice-QCD/experiment fit using several experimental datasets to determine the CKM matrix element$$|V_{cb}|$$|Vcb|. We obtain$$\left| V_{cb}\right| = (38.40 \pm 0.68_{\text {th}} \pm 0.34_{\text {exp}} \pm 0.18_{\text {EM}})\times 10^{-3}$$Vcb=(38.40±0.68th±0.34exp±0.18EM)×10-3. The first error is theoretical, the second comes from experiment and the last one includes electromagnetic and electroweak uncertainties, with an overall$$\chi ^2\text {/dof} = 126/84$$χ2/dof=126/84, which illustrates the tensions between the experimental data sets, and between theory and experiment. This result is in agreement with previous exclusive determinations, but the tension with the inclusive determination remains. Finally, we integrate the differential decay rate obtained solely from lattice data to predict$$R(D^*) = 0.265 \pm 0.013$$R(D)=0.265±0.013, which confirms the current tension between theory and experiment.

    more » « less
  2. Abstract

    An Eulerian walk (or Eulerian trail) is a walk (resp. trail) that visits every edge of a graphGat least (resp. exactly) once. This notion was first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. But what if Euler had to take a bus? In a temporal graph$$\varvec{(G,\lambda )}$$(G,λ), with$$\varvec{\lambda : E(G)}\varvec{\rightarrow } \varvec{2}^{\varvec{[\tau ]}}$$λ:E(G)2[τ], an edge$$\varvec{e}\varvec{\in } \varvec{E(G)}$$eE(G)is available only at the times specified by$$\varvec{\lambda (e)}\varvec{\subseteq } \varvec{[\tau ]}$$λ(e)[τ], in the same way the connections of the public transportation network of a city or of sightseeing tours are available only at scheduled times. In this paper, we deal with temporal walks, local trails, and trails, respectively referring to edge traversal with no constraints, constrained to not repeating the same edge in a single timestamp, and constrained to never repeating the same edge throughout the entire traversal. We show that, if the edges are always available, then deciding whether$$\varvec{(G,\lambda )}$$(G,λ)has a temporal walk or trail is polynomial, while deciding whether it has a local trail is$$\varvec{\texttt {NP}}$$NP-complete even if$$\varvec{\tau = 2}$$τ=2. In contrast, in the general case, solving any of these problems is$$\varvec{\texttt {NP}}$$NP-complete, even under very strict hypotheses. We finally give$$\varvec{\texttt {XP}}$$XPalgorithms parametrized by$$\varvec{\tau }$$τfor walks, and by$$\varvec{\tau +tw(G)}$$τ+tw(G)for trails and local trails, where$$\varvec{tw(G)}$$tw(G)refers to the treewidth of$$\varvec{G}$$G.

    more » « less
  3. Abstract

    Measurements of the associated production of a W boson and a charm ($${\text {c}}$$c) quark in proton–proton collisions at a centre-of-mass energy of 8$$\,\text {TeV}$$TeVare reported. The analysis uses a data sample corresponding to a total integrated luminosity of 19.7$$\,\text {fb}^{-1}$$fb-1collected by the CMS detector at the LHC. The W bosons are identified through their leptonic decays to an electron or a muon, and a neutrino. Charm quark jets are selected using distinctive signatures of charm hadron decays. The product of the cross section and branching fraction$$\sigma (\text {p}\text {p}\rightarrow \text {W}+ {\text {c}}+ \text {X}) {\mathcal {B}}(\text {W}\rightarrow \ell \upnu )$$σ(ppW+c+X)B(Wν), where$$\ell = \text {e}$$=eor$$\upmu $$μ, and the cross section ratio$$\sigma (\text {p}\text {p}\rightarrow {{\text {W}}^{+} + \bar{{\text {c}}} + \text {X}}) / \sigma (\text {p}\text {p}\rightarrow {{\text {W}}^{-} + {\text {c}}+ \text {X}})$$σ(ppW++c¯+X)/σ(ppW-+c+X)are measured in a fiducial volume and differentially as functions of the pseudorapidity and of the transverse momentum of the lepton from the W boson decay. The results are compared with theoretical predictions. The impact of these measurements on the determination of the strange quark distribution is assessed.

    more » « less
  4. Abstract

    In a Merlin–Arthur proof system, the proof verifier (Arthur) accepts valid proofs (from Merlin) with probability 1, and rejects invalid proofs with probability arbitrarily close to 1. The running time of such a system is defined to be the length of Merlin’s proof plus the running time of Arthur. We provide new Merlin–Arthur proof systems for some key problems in fine-grained complexity. In several cases our proof systems have optimal running time. Our main results include:

    Certifying that a list ofnintegers has no 3-SUM solution can be done in Merlin–Arthur time$$\tilde{O}(n)$$O~(n). Previously, Carmosino et al. [ITCS 2016] showed that the problem has a nondeterministic algorithm running in$$\tilde{O}(n^{1.5})$$O~(n1.5)time (that is, there is a proof system with proofs of length$$\tilde{O}(n^{1.5})$$O~(n1.5)and a deterministic verifier running in$$\tilde{O}(n^{1.5})$$O~(n1.5)time).

    Counting the number ofk-cliques with total edge weight equal to zero in ann-node graph can be done in Merlin–Arthur time$${\tilde{O}}(n^{\lceil k/2\rceil })$$O~(nk/2)(where$$k\ge 3$$k3). For oddk, this bound can be further improved for sparse graphs: for example, counting the number of zero-weight triangles in anm-edge graph can be done in Merlin–Arthur time$${\tilde{O}}(m)$$O~(m). Previous Merlin–Arthur protocols by Williams [CCC’16] and Björklund and Kaski [PODC’16] could only countk-cliques in unweighted graphs, and had worse running times for smallk.

    Computing the All-Pairs Shortest Distances matrix for ann-node graph can be done in Merlin–Arthur time$$\tilde{O}(n^2)$$O~(n2). Note this is optimal, as the matrix can have$$\Omega (n^2)$$Ω(n2)nonzero entries in general. Previously, Carmosino et al. [ITCS 2016] showed that this problem has an$$\tilde{O}(n^{2.94})$$O~(n2.94)nondeterministic time algorithm.

    Certifying that ann-variablek-CNF is unsatisfiable can be done in Merlin–Arthur time$$2^{n/2 - n/O(k)}$$2n/2-n/O(k). We also observe an algebrization barrier for the previous$$2^{n/2}\cdot \textrm{poly}(n)$$2n/2·poly(n)-time Merlin–Arthur protocol of R. Williams [CCC’16] for$$\#$$#SAT: in particular, his protocol algebrizes, and we observe there is no algebrizing protocol fork-UNSAT running in$$2^{n/2}/n^{\omega (1)}$$2n/2/nω(1)time. Therefore we have to exploit non-algebrizing properties to obtain our new protocol.

    Certifying a Quantified Boolean Formula is true can be done in Merlin–Arthur time$$2^{4n/5}\cdot \textrm{poly}(n)$$24n/5·poly(n). Previously, the only nontrivial result known along these lines was an Arthur–Merlin–Arthur protocol (where Merlin’s proof depends on some of Arthur’s coins) running in$$2^{2n/3}\cdot \textrm{poly}(n)$$22n/3·poly(n)time.

    Due to the centrality of these problems in fine-grained complexity, our results have consequences for many other problems of interest. For example, our work implies that certifying there is no Subset Sum solution tonintegers can be done in Merlin–Arthur time$$2^{n/3}\cdot \textrm{poly}(n)$$2n/3·poly(n), improving on the previous best protocol by Nederlof [IPL 2017] which took$$2^{0.49991n}\cdot \textrm{poly}(n)$$20.49991n·poly(n)time.

    more » « less
  5. Abstract

    Let$$(h_I)$$(hI)denote the standard Haar system on [0, 1], indexed by$$I\in \mathcal {D}$$ID, the set of dyadic intervals and$$h_I\otimes h_J$$hIhJdenote the tensor product$$(s,t)\mapsto h_I(s) h_J(t)$$(s,t)hI(s)hJ(t),$$I,J\in \mathcal {D}$$I,JD. We consider a class of two-parameter function spaces which are completions of the linear span$$\mathcal {V}(\delta ^2)$$V(δ2)of$$h_I\otimes h_J$$hIhJ,$$I,J\in \mathcal {D}$$I,JD. This class contains all the spaces of the formX(Y), whereXandYare either the Lebesgue spaces$$L^p[0,1]$$Lp[0,1]or the Hardy spaces$$H^p[0,1]$$Hp[0,1],$$1\le p < \infty $$1p<. We say that$$D:X(Y)\rightarrow X(Y)$$D:X(Y)X(Y)is a Haar multiplier if$$D(h_I\otimes h_J) = d_{I,J} h_I\otimes h_J$$D(hIhJ)=dI,JhIhJ, where$$d_{I,J}\in \mathbb {R}$$dI,JR, and ask which more elementary operators factor throughD. A decisive role is played by theCapon projection$$\mathcal {C}:\mathcal {V}(\delta ^2)\rightarrow \mathcal {V}(\delta ^2)$$C:V(δ2)V(δ2)given by$$\mathcal {C} h_I\otimes h_J = h_I\otimes h_J$$ChIhJ=hIhJif$$|I|\le |J|$$|I||J|, and$$\mathcal {C} h_I\otimes h_J = 0$$ChIhJ=0if$$|I| > |J|$$|I|>|J|, as our main result highlights: Given any bounded Haar multiplier$$D:X(Y)\rightarrow X(Y)$$D:X(Y)X(Y), there exist$$\lambda ,\mu \in \mathbb {R}$$λ,μRsuch that$$\begin{aligned} \lambda \mathcal {C} + \mu ({{\,\textrm{Id}\,}}-\mathcal {C})\text { approximately 1-projectionally factors through }D, \end{aligned}$$λC+μ(Id-C)approximately 1-projectionally factors throughD,i.e., for all$$\eta > 0$$η>0, there exist bounded operatorsABso thatABis the identity operator$${{\,\textrm{Id}\,}}$$Id,$$\Vert A\Vert \cdot \Vert B\Vert = 1$$A·B=1and$$\Vert \lambda \mathcal {C} + \mu ({{\,\textrm{Id}\,}}-\mathcal {C}) - ADB\Vert < \eta $$λC+μ(Id-C)-ADB<η. Additionally, if$$\mathcal {C}$$Cis unbounded onX(Y), then$$\lambda = \mu $$λ=μand then$${{\,\textrm{Id}\,}}$$Ideither factors throughDor$${{\,\textrm{Id}\,}}-D$$Id-D.

    more » « less