Stabilizing network bargaining games by blocking players

Cooperative matching games (Shapley and Shubik) and Network bargaining games (Kleinberg and Tardos) are games described by an undirected graph, where the vertices represent players. An important role in such games is played by stable graphs, that are graphs whose set of inessential vertices (those that are exposed by at least one maximum matching) are pairwise non adjacent. In fact, stable graphs characterize instances of such games that admit the existence of stable outcomes. In this paper, we focus on stabilizing instances of the above games by blocking as few players as possible. Formally, given a graph G we want to find a minimum cardinality set of vertices such that its removal from G yields a stable graph. We give a combinatorial polynomial-time algorithm for this problem, and develop approximation algorithms for some NP-hard weighted variants, where each vertex has an associated non-negative weight. Our approximation algorithms are LP-based, and we show that our analysis are almost tight by giving suitable lower bounds on the integrality gap of the used LP relaxations.     

Stability and the immediate acceptance rule when school priorities are weak

In a model of school choice, we allow school priorities to be weak and study the preference revelation game induced by the immediate acceptance (IA) rule (also known as the Boston rule), or the IA game. When school priorities can be weak and matches probabilistic, three stability notions—ex post stability, ex ante stability, and strong ex ante stability—and two ordinal equilibrium notions—sd equilibrium and strong sd equilibrium—become available (“sd” stands for stochastic dominance). We show that for no combination of stability and equilibrium notions does the set of stable matches coincide with the set of equilibrium matches of the IA game. This stands in contrast with the existing result that the two sets are equal when priorities are strict. We also show that in the presence of weak priorities, the transition from the IA rule to the deferred acceptance rule may, in fact, harm some students.     

A game-theoretic analysis of information security investment for multiple firms in a network

The application of Internet of Things promotes the cooperation among firms, and it also introduces some information security issues. Due to the vulnerability of the communication network, firms need to invest in information security technologies to protect their confidential information. In this paper, considering the multiple-step propagation of a security breach in a fully connected network, an information security investment game among n firms is investigated. We make meticulous theoretic and experimental analyses on both the Nash equilibrium solution and the optimal solution. The results show that a larger network size (n) or a larger one-step propagation probability (q) has a negative effect on the Nash equilibrium investment. The optimal investment does not necessarily increase in n or q, and its variation trend depends on the concrete conditions. A compensation mechanism is proposed to encourage firms to coordinate their strategies and invest a higher amount equal to the optimal investment when they make decisions individually. At last, our model is extended by considering another direct breach probability function and another network structure, respectively. We find that a higher connection density of the network will result in a greater expected cost for each firm.     

Building Graphs Whose Independence Polynomials Have Only Real Roots

A stable set in a graph G is a set of pairwise non-adjacent vertices, and the stability number α(G) is the maximum size of a stable set in G. The independence polynomial of G is

$I(G; x) = s_{0}+s_{1}x+s_{2}x^{2}+\cdots+s_{\alpha}x^{\alpha},\alpha=\alpha(G),$

where s _k equals the number of stable sets of cardinality k in G (Gutman and Harary [11]).

Unlike the matching polynomial, the independence polynomial of a graph can have non-real roots. It is known that the polynomial I(G; x) has only real roots whenever (a) α(G) = 2 (Brown et al. [4]), (b) G is claw-free (Chudnowsky and Symour [6]). Brown et al. [3] proved that given a well-covered graph G, one can define a well-covered graph H such that G is a subgraph of H, α(G) = α(H), and I(H; x) has all its roots simple and real.In this paper, we show that starting from a graph G whose I(G; x) has only real roots, one can build an infinite family of graphs, some being well-covered, whose independence polynomials have only real roots (and, sometimes, are also palindromic).     

Popular edges and dominant matchings

Given a bipartite graph \(G = (A \cup B,E)\) with strict preference lists and given an edge \(e^* \in E\), we ask if there exists a popular matching in G that contains \(e^*\). We call this the popular edge problem. A matching M is popular if there is no matching \(M'\) such that the vertices that prefer \(M'\) to M outnumber those that prefer M to \(M'\). It is known that every stable matching is popular; however G may have no stable matching with the edge \(e^*\). In this paper we identify another natural subclass of popular matchings called “dominant matchings” and show that if there is a popular matching that contains the edge \(e^*\), then there is either a stable matching that contains \(e^*\) or a dominant matching that contains \(e^*\). This allows us to design a linear time algorithm for identifying the set of popular edges. When preference lists are complete, we show an \(O(n^3)\) algorithm to find a popular matching containing a given set of edges or report that none exists, where \(n = |A| + |B|\).     

Vectorial Ekeland variational principle for systems of equilibrium problems and its applications

For a family of vector-valued bifunctions,we introduce the notion of sequentially lower monotonity,which is strictly weaker than the lower semi-continuity of the second variables of the bifunctions.Then,we give a general version of vectorial Ekeland variational principle(briefly,denoted by EVP) for a system of equilibrium problems,where the sequentially lower monotone objective bifunction family is defined on products of sequentially lower complete spaces(concerning sequentially lower complete spaces,see Zhu et al(2013)),and taking values in a quasi-ordered locally convex space.Besides,the perturbation consists of a subset of the ordering cone and a family {p_i}_(i∈I) of negative functions satisfying for each i∈I,p_i(x_i,y_i) = 0 if and only if x_i=y_i.From the general version,we can deduce several particular equilibrium versions of EVP,which can be applied to show the existence of solutions for countable systems of equilibrium problems.In particular,we obtain a general existence result of solutions for countable systems of equilibrium problems in the setting of sequentially lower complete spaces.By weakening the compactness of domains and the lower semi-continuity of objective bifunctions,we extend and improve some known existence results of solutions for countable system of equilibrium problems in the setting of complete metric spaces(or Fréchet spaces).When the domains are non-compact,by using the theory of angelic spaces(see Floret(1980)),we generalize some existence results on solutions for countable systems of equilibrium problems by extending the framework from reflexive Banach spaces to the strong duals of weakly compactly generated spaces.     

Critical Independent Sets and König–Egerváry Graphs

A set S of vertices is independent or stable in a graph G, and we write S ∈ Ind (G), if no two vertices from S are adjacent, and α(G) is the cardinality of an independent set of maximum size, while core(G) denotes the intersection of all maximum independent sets. G is called a König–Egerváry graph if its order equals α(G) + μ(G), where μ(G) denotes the size of a maximum matching. The number def (G) = | V(G) | ?2μ(G) is the deficiency of G. The number \({d(G)=\max\{\left\vert S\right\vert -\left\vert N(S)\right\vert :S\in\mathrm{Ind}(G)\}}\) is the critical difference of G. An independent set A is critical if \({\left\vert A\right\vert -\left\vert N(A)\right\vert =d(G)}\) , where N(S) is the neighborhood of S, and α _c (G) denotes the maximum size of a critical independent set. Larson (Eur J Comb 32:294–300, 2011) demonstrated that G is a König–Egerváry graph if and only if there exists a maximum independent set that is also critical, i.e., α _c (G) = α(G). In this paper we prove that: (i) \({d(G)=\left \vert \mathrm{core}(G) \right \vert -\left \vert N (\mathrm{core}(G))\right\vert =\alpha(G)-\mu(G)=def \left(G\right)}\) holds for every König–Egerváry graph G; (ii) G is König–Egerváry graph if and only if each maximum independent set of G is critical.     

Dimension scales of bicompacta

We introduce the notion of a (stable) dimension scale d-sc(X) of a space X, where d is a dimension invariant. A bicompactum X is called dimensionally unified if dim F = dim_G F for every closed F ? X and for an arbitrary abelian group G. We prove that there exist dimensionally unified bicompacta with every given stable scale dim-sc.     

Dimension and Matchings in Comparability and Incomparability Graphs

We develop some new inequalities for the dimension of a finite poset. These inequalities are then used to bound dimension in terms of the maximum size of matchings. We prove that if the dimension of P is d and d=3, then there is a matching of size d in the comparability graph of P. There is no analogue of this result for cover graphs, as we show that there is a poset P of dimension d for which the maximum matching in the cover graph of P has size \(O(\log d)\). On the other hand, there is a dual result in which the role of chains and antichains is reversed, as we show that there is also a matching of size d in the incomparability graph of P. The proof of the result for comparability graphs has elements in common with Perles’ proof of Dilworth’s theorem. Either result has the following theorem of Hiraguchi as an immediate corollary: \(\dim (P)\le |P|/2\) when |P|=4.     

The Generalized <Emphasis Type="Italic">M/G/k</Emphasis> Blocking System with Heterogeneous Servers

This paper studies the equilibrium behaviour of the generalized M/G/k blocking system with heterogeneous servers. Such a service system has k servers, each with a (possibly) different service time distribution, whose customers arrive in accordance with a Poisson process. They are served, unless all the servers are occupied. In this case they leave and they do not return later (i.e. they are ‘blocked’). Whenever there are n (n = 0, 1, 2,..., k) servers occupied, each arriving customer balks with probability 1 - f _{n +1}(f _{k +1} = 0) and each server works at a rate g _n . Among other things, a generalization of the Erlang B-formula is given and also it is shown that the equilibrium departure process from the system is Poisson.     

Equilibria of a nonautonomous Lotka-Volterra model with shelter for the prey

For the nonautonomous Lotka-Volterra model

$\dot x = \alpha (t)(x - M^{ - 1} x^2 - K^{ - 1} (x - \phi (x,y))y),\dot y = \beta (t)y(L^{ - 1} (x - \phi (x,y)) - 1),$

where some part φ(x, y) of the prey population is out of reach of the predator, we obtain sufficient conditions for the existence of a positive asymptotically stable equilibrium in the domain of admissible values of the variables x and y. We consider the cases in which φ(x, y) = m, φ(x, y) = mx, and φ(x, y) = my.

     

Acute perturbation of Drazin inverse and oblique projectors

For an n×n complex matrix A with ind(A) = r; let A^D and A^π = I–AA^D be respectively the Drazin inverse and the eigenprojection corresponding to the eigenvalue 0 of A: For an n×n complex singular matrix B with ind(B) = s, it is said to be a stable perturbation of A, if I–(B^π–A^π)² is nonsingular, equivalently, if the matrix B satisfies the condition \(\mathcal{R}(B^s)\cap\mathcal{N}(A^r)=\left\{0\right\}\) and \(\mathcal{N}(B^s)\cap\mathcal{R}(A^r)=\left\{0\right\}\), introduced by Castro-González, Robles, and Vélez-Cerrada. In this paper, we call B an acute perturbation of A with respect to the Drazin inverse if the spectral radius ρ(B^π–A^π) < 1: We present a perturbation analysis and give suffcient and necessary conditions for a perturbation of a square matrix being acute with respect to the matrix Drazin inverse. Also, we generalize our perturbation analysis to oblique projectors. In our analysis, the spectral radius, instead of the usual spectral norm, is used. Our results include the previous results on the Drazin inverse and the group inverse as special cases and are consistent with the previous work on the spectral projections and the Moore-Penrose inverse.     

<Emphasis Type="Italic">M</Emphasis><Superscript><Emphasis Type="Italic">X</Emphasis></Superscript>/<Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">c</Emphasis> Queue with catastrophes and state-dependent control at idle time

We consider an M ^X /M/c queue with catastrophes and state-dependent control at idle time. Properties of the queues which terminate when the servers become idle are first studied. Recurrence, equilibrium distribution, and equilibrium queue-size structure are studied for the case of resurrection and no catastrophes. All of these properties and the first effective catastrophe occurrence time are then investigated for the case of resurrection and catastrophes. In particular, we obtain the Laplace transform of the transition probability for the absorbing M ^X /M/c queue.     

bmo _ρ(ω) Spaces and Riesz transforms associated to Schrdinger operators

We introduce the BMO-type space bmoρ(ω) and establish the duality between h_ρ~1(ω) and bmo _ρ(ω),where ω∈A_1~(ρ, ∞)(R~n) and ω's locally behave as Muckenhoupt's weights but actually include them. We also give the Fefferman-Stein type decomposition of bmoρ(ω) with respect to Riesz transforms associated to Schrdinger operator L, where L =-? + V is a Schrdinger operator on R~n(n≥3) and V is a non-negative function satisfying the reverse Hlder inequality.     

Universal rigidity of bar frameworks via the geometry of spectrahedra

A bar framework (G, p) in dimension r is a graph G whose nodes are points \(p^1,\ldots ,p^n\) in \(\mathbb {R}^r\) and whose edges are line segments between pairs of these points. Two frameworks (G, p) and (G, q) are equivalent if each edge of (G, p) has the same (Euclidean) length as the corresponding edge of (G, q). A pair of non-adjacent vertices i and j of (G, p) is universally linked if \(||p^i-p^j||\) = \(||q^i-q^j||\) in every framework (G, q) that is equivalent to (G, p). Framework (G, p) is universally rigid iff every pair of non-adjacent vertices of (G, p) is universally linked. In this paper, we present a unified treatment of the universal rigidity problem based on the geometry of spectrahedra. A spectrahedron is the intersection of the positive semidefinite cone with an affine space. This treatment makes it possible to tie together some known, yet scattered, results and to derive new ones. Among the new results presented in this paper are: (1) The first sufficient condition for a given pair of non-adjacent vertices of (G, p) to be universally linked. (2) A new, weaker, sufficient condition for a framework (G, p) to be universally rigid thus strengthening the existing known condition. An interpretation of this new condition in terms of the Strong Arnold Property is also presented.     

Local analysis of a polynomial system and its perturbations

On the real (x, y)-plane, we consider an autonomous system of differential equations whose right-hand sides are polynomials of special form in x and y and a perturbed system obtained from the former by varying the coefficients in the class of functions of (x, y) satisfying the Lipschitz condition. We study the behavior of trajectories of the system in a neighborhood of the isolated equilibrium point O = (0, 0). For the main (polynomial) system, we find all possible types of arrangement of the trajectories in a neighborhood of O. For the case in which the system has TO-curves, we give coefficient criteria for each of the possible types of the point O and study conditions under which the type is preserved in the perturbed system.     

Bounded rationality and correlated equilibria

We study an interactive framework that explicitly allows for nonrational behavior. We do not place any restrictions on how players’ behavior deviates from rationality, but rather, on players’ higher-order beliefs about the frequency of such deviations. We assume that there exists a probability p such that all players believe, with at least probability p, that their opponents play rationally. This, together with the assumption of a common prior, leads to what we call the set of p-rational outcomes, which we define and characterize for arbitrary probability p. We then show that this set varies continuously in p and converges to the set of correlated equilibria as p approaches 1, thus establishing robustness of the correlated equilibrium concept to relaxing rationality and common knowledge of rationality. The p-rational outcomes are easy to compute, also for games of incomplete information. Importantly, they can be applied to observed frequencies of play for arbitrary normal-form games to derive a measure of rationality \(\overline{p}\) that bounds from below the probability with which any given player chooses actions consistent with payoff maximization and common knowledge of payoff maximization.     

Rainbow matchings in bipartite multigraphs

Suppose that k is a non-negative integer and a bipartite multigraph G is the union of

$$\begin{aligned} N=\left\lfloor \frac{k+2}{k+1}n\right\rfloor -(k+1) \end{aligned}$$

matchings \(M_1,\dots ,M_N\), each of size n. We show that G has a rainbow matching of size \(n-k\), i.e. a matching of size \(n-k\) with all edges coming from different \(M_i\)’s. Several choices of the parameter k relate to known results and conjectures.

     

Characterization of 2-Local Derivations and Local Lie Derivations on Some Algebras

We prove that each 2-local derivation from the algebra M_n(A ) (n > 2) into its bimodule M_n(M) is a derivation, where A is a unital Banach algebra and M is a unital A -bimodule such that each Jordan derivation from A into M is an inner derivation, and that each 2-local derivation on a C*-algebra with a faithful traceable representation is a derivation. We also characterize local and 2-local Lie derivations on some algebras such as von Neumann algebras, nest algebras, the Jiang–Su algebra, and UHF algebras.     

Note: A conjecture on partitions of groups

We conjecture that every infinite group G can be partitioned into countably many cells \(G = \bigcup\limits_{n \in \omega } {A_n }\) such that cov(A _n A _n ^?1 ) = |G| for each n ∈ ω Here cov(A) = min{|X|: X} ? G, G = X A}. We confirm this conjecture for each group of regular cardinality and for some groups (in particular, Abelian) of an arbitrary cardinality.