k-Balanced games and capacities

In this paper, we present a generalization of the concept of balanced game for finite games. Balanced games are those having a nonempty core, and this core is usually considered as the solution of the game. Based on the concept of k-additivity, we define the so-called k-balanced games and the corresponding generalization of core, the k-additive core, whose elements are not directly imputations but k-additive games. We show that any game is k-balanced for a suitable choice of k, so that the corresponding k-additive core is not empty. For the games in the k-additive core, we propose a sharing procedure to get an imputation and a representative value for the expectations of the players based on the pessimistic criterion. Moreover, we look for necessary and sufficient conditions for a game to be k-balanced. For the general case, it is shown that any game is either balanced or 2-balanced. Finally, we treat the special case of capacities.     

On the set of imputations induced by the k-additive core

An extension to the classical notion of core is the notion of k-additive core, that is, the set of k-additive games which dominate a given game, where a k-additive game has its Möbius transform (or Harsanyi dividends) vanishing for subsets of more than k elements. Therefore, the 1-additive core coincides with the classical core. The advantages of the k-additive core is that it is never empty once k ? 2, and that it preserves the idea of coalitional rationality. However, it produces k-imputations, that is, imputations on individuals and coalitions of at most k individuals, instead of a classical imputation. Therefore one needs to derive a classical imputation from a k-order imputation by a so-called sharing rule. The paper investigates what set of imputations the k-additive core can produce from a given sharing rule.     

On the vertices of the -additive core

The core of a game v on N, which is the set of additive games φ dominating v such that φ(N)=v(N), is a central notion in cooperative game theory, decision making and in combinatorics, where it is related to submodular functions, matroids and the greedy algorithm. In many cases however, the core is empty, and alternative solutions have to be found. We define the k-additive core by replacing additive games by k-additive games in the definition of the core, where k-additive games are those games whose Möbius transform vanishes for subsets of more than k elements. For a sufficiently high value of k, the k-additive core is nonempty, and is a convex closed polyhedron. Our aim is to establish results similar to the classical results of Shapley and Ichiishi on the core of convex games (corresponds to Edmonds’ theorem for the greedy algorithm), which characterize the vertices of the core.     

k-intolerant capacities and Choquet integrals

We define an aggregation function to be (at most) k-intolerant if it is bounded from above by its kth lowest input value. Applying this definition to the discrete Choquet integral and its underlying capacity, we introduce the concept of k-intolerant capacities which, when varying k from 1 to n, cover all the possible capacities on n objects. Just as the concepts of k-additive capacities and p-symmetric capacities have been previously introduced essentially to overcome the problem of computational complexity of capacities, k-intolerant capacities are proposed here for the same purpose but also for dealing with intolerant or tolerant behaviors of aggregation. We also introduce axiomatically indices to appraise the extent to which a given capacity is k-intolerant and we apply them on a particular recruiting problem.     

Hessian Measures III

In this paper, we continue previous investigations into the theory of Hessian measures. We extend our weak continuity result to the case of mixed k-Hessian measures associated with k-tuples of k-convex functions, on domains in Euclidean n-space, k=1,2,…,n. Applications are given to capacity, quasicontinuity, and the Dirichlet problem, with inhomogeneous terms, continuous with respect to capacity or combinations of Dirac measures.     

On a combinatorial property of choice functions of finite sets

We consider choice functions k[X]→X, where X is a finite set and k[X] denotes the set of all k-subsets of X. We define a property of domination for such maps generalizing the classical case k=2 (tournaments) and prove the existence of a dominating element generalizing the existence of a 2-root (king) in the classical case.     

Beatty sequences and prime numbers with restrictions on strongly <Emphasis Type="Italic">q</Emphasis>-additive functions

We estimate exponential sums over a non-homogenous Beatty sequence with restriction on strongly q-additive functions. We then apply our result in a few special cases to obtain an asymptotic formula for the number of primes \(p=\lfloor \alpha n +\beta \rfloor \) and \(f(p)\equiv a (\mathrm{mod\,}b)\), with \(n\ge N \), where \(\alpha \), \(\beta \) are real numbers and f is a strongly q-additive function (for example, the sum of digits function in base q is a strongly q-additive function). We also prove that for any fixed integer \(k\ge 3 \), all sufficiently large \(N\equiv k (\mathrm{mod\,}2) \) could be represented as a sum of k prime numbers from a Beatty sequence with restriction on strongly q-additive functions.     

The k-Dominating Graph

Given a graph G, the k-dominating graph of G, D _k (G), is defined to be the graph whose vertices correspond to the dominating sets of G that have cardinality at most k. Two vertices in D _k (G) are adjacent if and only if the corresponding dominating sets of G differ by either adding or deleting a single vertex. The graph D _k (G) aids in studying the reconfiguration problem for dominating sets. In particular, one dominating set can be reconfigured to another by a sequence of single vertex additions and deletions, such that the intermediate set of vertices at each step is a dominating set if and only if they are in the same connected component of D _k (G). In this paper we give conditions that ensure D _k (G) is connected.     

Absolutely continuous invariant measures for random maps with position dependent probabilities

A random map is discrete-time dynamical system in which one of a number of transformations is randomly selected and applied at each iteration of the process. Usually the map τ_k is chosen from a finite collection of maps with constant probability p_k. In this note we allow the p_k's to be functions of position. In this case, the random map cannot be considered to be a skew product. The main result provides a sufficient condition for the existence of an absolutely continuous invariant measure for position dependent random maps on [0,1]. Geometrical and topological properties of sets of absolutely continuous invariant measures, attainable by means of position dependent random maps, are studied theoretically and numerically.     

Minimum 2-tuple dominating set of permutation graphs

For a fixed positive integer k, a k-tuple dominating set of a graph G=(V,E) is a subset D?V such that every vertex in V is dominated by at least k vertex in D. The k-tuple domination number γ _×k (G) is the minimum size of a k-tuple dominating set of G. The special case when k=1 is the usual domination. The case when k=2 was called double domination or 2-tuple domination. A 2-tuple dominating set D ₂ is said to be minimal if there does not exist any D′?D ₂ such that D′ is a 2-tuple dominating set of G. A 2-tuple dominating set D ₂, denoted by γ _×2(G), is said to be minimum, if it is minimal as well as it gives 2-tuple domination number. In this paper, we present an efficient algorithm to find a minimum 2-tuple dominating set on permutation graphs with n vertices which runs in O(n ²) time.     

Solving Ck/Cm/1/N queues by using characteristic roots in matrix analytic methods

In this paper, we study a C_k/C_m/1/N open queueing system with finite capacity. We investigate the property which shows that a product of the Laplace Stieltjes Transforms of interarrival and service times distributions satisfies an equation of a simple form. According to this equation, we present that the stationary probabilities on the unboundary states can be written as a linear combination of vector product-forms. Each component of these products is expressed in terms of roots of an associated characteristic polynomial. As a result, we carry out an algorithm for solving stationary probabilities in C_k/C_m/1/N systems, which is independent of N, hence greatly reducing the computational complexity.     

Asymptotic Expansions for Large Deviation Probabilities of Noncentral Generalized Chi-Square Distributions

Asymptotic expansions for large deviation probabilities are used to approximate the cumulative distribution functions of noncentral generalized chi-square distributions, preferably in the far tails. The basic idea of how to deal with the tail probabilities consists in first rewriting these probabilities as large parameter values of the Laplace transform of a suitably defined function f_k; second making a series expansion of this function, and third applying a certain modification of Watson's lemma. The function f_k is deduced by applying a geometric representation formula for spherical measures to the multivariate domain of large deviations under consideration. At the so-called dominating point, the largest main curvature of the boundary of this domain tends to one as the large deviation parameter approaches infinity. Therefore, the dominating point degenerates asymptotically. For this reason the recent multivariate asymptotic expansion for large deviations in Breitung and Richter (1996, J. Multivariate Anal.58, 1–20) does not apply. Assuming a suitably parametrized expansion for the inverse g⁻¹ of the negative logarithm of the density-generating function, we derive a series expansion for the function f_k. Note that low-order coefficients from the expansion of g⁻¹ influence practically all coefficients in the expansion of the tail probabilities. As an application, classification probabilities when using the quadratic discriminant function are discussed.     

Remarkable polyhedra related to set functions,games and capacities

Set functions are widely used in many domains of operations research (cooperative game theory, decision under risk and uncertainty, combinatorial optimization) under different names (TU-game, capacity, nonadditive measure, pseudo-Boolean function, etc.). Remarkable families of set functions form polyhedra, e.g., the polytope of capacities, the polytope of p-additive capacities, the cone of supermodular games, etc. Also, the core of a set function, defined as the set of additive set functions dominating that set function, is a polyhedron which is of fundamental importance in game theory, decision-making and combinatorial optimization. This survey paper gives an overview of these notions and studies all these polyhedra.     

Edge-dominating cycles in graphs

A set S of vertices in a graph G is said to be an edge-dominating set if every edge in G is incident with a vertex in S. A cycle in G is said to be a dominating cycle if its vertex set is an edge-dominating set. Nash-Williams [Edge-disjoint hamiltonian circuits in graphs with vertices of large valency, Studies in Pure Mathematics, Academic Press, London, 1971, pp. 157-183] has proved that every longest cycle in a 2-connected graph of order n and minimum degree at least is a dominating cycle. In this paper, we prove that for a prescribed positive integer k, under the same minimum degree condition, if n is sufficiently large and if we take k disjoint cycles so that they contain as many vertices as possible, then these cycles form an edge-dominating set. Nash-Williams’ Theorem corresponds to the case of k=1 of this result.     

On the univalence of derivatives of functions which are univalent in angular domains

We consider functions f that are univalent in a plane angular domain of angle απ, 0 < α ≤ 2. It is proved that there exists a natural number k depending only on α such that the kth derivatives f ^(k) of these functions cannot be univalent in this angle. We find the least of the possible values of for k. As a consequence, we obtain an answer to the question posed by Kir’yatskii: if f is univalent in the half-plane, then its fourth derivative cannot be univalent in this half-plane.     

Some results related to the toughness of 3-domination critical graphs

A graph G is said to be k-γ-critical if the size of any minimum dominating set of vertices is k, but if any edge is added to G the resulting graph can be dominated with k−1 vertices. The structure of k-γ-critical graphs remains far from completely understood, even in the special case when the domination number γ=3. In a 1983 paper, Sumner and Blitch proved a theorem which may regarded as a result related to the toughness of 3-γ-critical graphs which says that if S is any vertex cutset of such a graph, then G−S has at most |S|+1 components. In the present paper, we improve and extend this result considerably.     

A characterization of the 2-additive Choquet integral through cardinal information

In the context of multiple criteria decision analysis, we present the necessary and sufficient conditions to represent a cardinal preferential information by the Choquet integral w.r.t. a 2-additive capacity. These conditions are based on some complex cycles called cyclones.     

Unicity of meromorphic functions and their derivatives

In this paper, we prove that if a transcendental meromorphic function f shares two distinct small functions CM with its kth derivative f^(k) (k>1), then f=f^(k). We also resolve the same question for the case k=1. These results generalize a result due to Frank and Weissenborn.     

Multisummability of formal power series solutions of partial differential equations with constant coefficients

In an earlier paper of the author's, partial differential equations with constant coefficients have been studied. Under a certain (restrictive) assumption upon the equation, those initial conditions were characterized for which the normalized formal solution of a corresponding Cauchy problem is k-summable. Here we treat the general situation and prove an analogous result, using multisummability instead of k-summability. The appropriate multisummability type is shown to depend upon the given PDE only, and can be determined from a corresponding Newton polygon.