Bargaining sets in cooperative games with limited communication

Given a connected undirected graph ϕ with vertex set N, cooperative games (N, v) are considered in which players can cooperate only when the corresponding vertices form a connected subgraph in the graph ϕ. For such games, two generalizations of the bargaining set M ₁ ⁱ , which was introduced by Aumann and Maschler, are investigated.     

PiecewiseL-splines

Leta=x ₀<x ₁<...<x _N =b be a partition of the interval [a, b] and letL be a normalm-th order linear differential operator. The purpose of this note is to point out that spline functions in one variable need not be excluded to piecewise fits of functions belonging to the null spaceN(L ^* L) on each closed subinterval [x _i,x _i+1], 0in-1 but may be extended to piecewise fits of functions belonging toN(L _i ^* L _i) on each subinterval [x _i,x _i+1] provided theL _i's are selected from a uniformly bounded family of normal linear differential operators. Furthermore when theL _i's are so selected one obtains the usual integral relations and error estimates obtained for splines [2, 8 and 9] including the extended error estimates obtained by Swartz and Varga [10].     

On computational complexity of membership test in flow games and linear production games

Let Γ≡(N,v) be a cooperative game with the player set N and characteristic function v: 2^N→R. An imputation of the game is in the core if no subset of players could gain advantage by splitting from the grand coalition of all players. It is well known that, for the flow game (and equivalently, for the linear production game), the core is always non-empty and a solution in the core can be found in polynomial time. In this paper, we show that, given an imputation x, it is NP-complete to decide x is not a member of the core, for the flow game. And because of the specific reduction we constructed, the result also holds for the linear production game. Received: October 2000/Final version: March 2002     

Dynamic linear programming games with risk-averse players

Motivated by situations in which independent agents wish to cooperate in some uncertain endeavor over time, we study dynamic linear programming games, which generalize classical linear production games to multi-period settings under uncertainty. We specifically consider that players may have risk-averse attitudes towards uncertainty, and model this risk aversion using coherent conditional risk measures. For this setting, we study the strong sequential core, a natural extension of the core to dynamic settings. We characterize the strong sequential core as the set of allocations that satisfy a particular finite set of inequalities that depend on an auxiliary optimization model, and then leverage this characterization to establish sufficient conditions for emptiness and non-emptiness. Qualitatively, whereas the strong sequential core is always non-empty when players are risk-neutral, our results indicate that cooperation in the presence of risk aversion is much more difficult. We illustrate this with an application to cooperative newsvendor games, where we find that cooperation is possible when it least benefits players, and may be impossible when it offers more benefit.     

SHAPEI PRESERVING PIECEWISE CUBIC INTERPOLATION

This paper presents a C^1-interpolation which preserves convexity to scattered convex data. The interpolant is local and explicitly described. The interpolating function si(x) is C^2 on each interval (xi, xi 1). Error will be O(h^2) when the function to he interpolated is C^3.     

NONLINEAR HOMOTOPY AND PRE-POINCARÉ LEMMAS

Abstract

Most homotopies considered in the literature are linear homotopies of the form h ⁱ (λ) = λx ⁱ + (1—λ)y ⁱ , 0 ≤ λ ≤ 1. Although these prove to be adequate in most instances, they lack direct geometric significance because {h ⁱ (λ) | 0 ≤ λ ≤ 1} are not orbits of a vector field. On the other hand, the nonlinear homotopy g ⁱ (s) = e ^s x ⁱ + (1—e ^s )y ⁱ ,—∞ ≤ s ≤ 0, are orbits of a vector field (i.e., dg ⁱ /ds = g ⁱ —y ⁱ , g ⁱ (0) = x ⁱ ), and thus have direct geometric significance. This suggests that useful results can be obtained by replacing linear homotopy by transport along flows of smooth vector fields. The purpose of this paper is to elaborate on this simple idea. We define prehomotopy operators induced by vector fields on a manifold. These allow us to obtain finite transport relations and pre-Poincaré lemmas that generalize the classical results. They are shown to reproduce the classical results as asymptotic limits and to obtain representations of all solutions of complete systems of exterior differential equations on a star shaped region of a manifold.     

Minimizing bumps in linear extensions of ordered sets

A linear extension x ₁ x ₂ x ₃ ... of a partially ordered set (X, <) has a bump whenever x _i <x _i +1. We examine the problem of determining linear extensions with as few bumps as possible. Heuristic algorithms for approximate bump minimization are considered.     

Functional central limit theorems for self-normalized least squares processes in regression with possibly infinite variance data

Based on an R²-valued random sample {(y_i,x_i),1≤i≤n} on the simple linear regression model y_i=x_iβ+α+ε_i with unknown error variables ε_i, least squares processes (LSPs) are introduced in D[0,1] for the unknown slope β and intercept α, as well as for the unknown β when α=0. These LSPs contain, in both cases, the classical least squares estimators (LSEs) for these parameters. It is assumed throughout that {(x,ε),(x_i,ε_i),i≥1} are i.i.d. random vectors with independent components x and ε that both belong to the domain of attraction of the normal law, possibly both with infinite variances. Functional central limit theorems (FCLTs) are established for self-normalized type versions of the vector of the introduced LSPs for (β,α), as well as for their various marginal counterparts for each of the LSPs alone, respectively via uniform Euclidean norm and sup–norm approximations in probability. As consequences of the obtained FCLTs, joint and marginal central limit theorems (CLTs) are also discussed for Studentized and self-normalized type LSEs for the slope and intercept. Our FCLTs and CLTs provide a source for completely data-based asymptotic confidence intervals for β and α.     

Speed of convergence in nonparametric kernel estimation of a regression function and its derivatives

Summary The objective in nonparametric regression is to infer a functiong(x) and itspth order derivativesg ^(g)(x),p≧1 fixed, on the basis of a finite collection of pairs {x _i, g(x_i)+Z _i} _i=1 ⁿ , where the noise componentsZ _i satisfy certain modest assumptions and the domain pointsx _i are selected non-randomly. This paper exhibits a new class of kernel estimatesg _n ^(p) ,p≧0 fixed. The main theoretical results of this study are the rates of convergence obtained for mean square and strong consistency ofg _n ^(p) each of them being uniform on the (0,1).     

Bargaining sets of cooperative games without side payments

In this paper an analogue of the bargaining setM ₁ ⁱ is defined for cooperative games without side payments. An existence theorem is proved for games of pairs, while it is shown by an example that no general existence theorem holds.     

On the Asymptotics of Fekete-Type Points for Univariate Radial Basis Interpolation

Suppose that K ^d is compact and that we are given a function fC(K) together with distinct points x_iK, 1in. Radial basis interpolation consists of choosing a fixed (basis) function g : ⁺→ and looking for a linear combination of the translates g(|x−x_j|) which interpolates f at the given points. Specifically, we look for coefficients c_j such that has the property that F(x_i)=f(x_i), 1in. The Fekete-type points of this process are those for which the associated interpolation matrix [g(|x_i−x_j|)]_1i,jn has determinant as large as possible (in absolute value). In this work, we show that, in the univariate case, for a broad class of functions g, among all point sequences which are (strongly) asymptotically distributed according to a weight function, the equally spaced points give the asymptotically largest determinant. This gives strong evidence that the Fekete points themselves are indeed asymptotically equally spaced.     

Finite‐difference approximation for the u(k)‐derivative with O(hM−k+1) accuracy: An analytical expression

An approximation of function u(x) as a Taylor series expansion about a point x₀ at M points x_i, ～ i = 1,2,…,M is used where x_i are arbitrary‐spaced. This approximation is a linear system for the derivatives u^(k) with an arbitrary accuracy. An analytical expression for the inverse matrix A ^?1 where A = [A_ik] = (x_i ? x₀)^k is found. A finite‐difference approximation of derivatives u^(k) of a given function u(x) at point x₀ is derived in terms of the values u(x_i). © 2006 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2006     

Greedy linear extensions for minimizing bumps

Let P be a finite poset and let L={x ₁<...n} be a linear extension of P. A bump in L is an ordered pair (x _i , x _i+1) where x _ii+1 in P. The bump number of P is the least integer b(P), such that there exists a linear extension of P with b(P) bumps. We call L optimal if the number of bumps of L is b(P). We call L greedy if x _{i j} for every j>i, whenever (x _i, x _i+1) is a bump. A poset P is called greedy if every greedy linear extension of P is optimal. Our main result is that in a greedy poset every optimal linear extension is greedy. As a consequence, we prove that every greedy poset of bump number k is the linear sum of k+1 greedy posets, each of bump number zero.This research (Math/1406/31) was supported by the Research Center, College of Science, King Saud University, Riyadh, Saudi Arabia.     

Eigenvalue Intervals for 2mth Order Sturm—Liouville Boundary Value Problems

Values of λ are determined for which there exist positive solutions of the 2mth order differential equation on a measure chain, (-1)^m x ^?2m (t)=λa(t)f(u(σ(t))), y? [0,1], satisfying α _i+1 u ^?21(0)+0, γ _i+1 u ^?21(σ(1))=0, 0≤i≤m?1 with αi,βi,γi,δi≥0, where a and f are positive valued, and both lim _x-0+ (f(x)/x) and lim _x-0+ (f(x)/x) exist.     

Inequalities for the greedy dimensions of ordered sets

Every linear extension L: [x ₁<x ₂<...<x _m ] of an ordered set P on m points arises from the simple algorithm: For each i with 0i<m, choose x _i+1 as a minimal element of P–{x _j :ji}. A linear extension is said to be greedy, if we also require that x _i+1 covers x _i in P whenever possible. The greedy dimension of an ordered set is defined as the minimum number of greedy linear extensions of P whose intersection is P. In this paper, we develop several inequalities bounding the greedy dimension of P as a function of other parameters of P. We show that the greedy dimension of P does not exceed the width of P. If A is an antichain in P and |P–A|2, we show that the greedy dimension of P does not exceed |P–A|. As a consequence, the greedy dimension of P does not exceed |P|/2 when |P|4. If the width of P–A is n and n2, we show that the greedy dimension of P does not exceed n ²+n. If A is the set of minimal elements of P, then this inequality can be strengthened to 2n–1. If A is the set of maximal elements, then the inequality can be further strengthened to n+1. Examples are presented to show that each of these inequalities is best possible.Research supported in part by the National Science Foundation under ISP-80110451.Research supported in part by the National Science Foundation under ISP-80110451 and DMS-8401281.     

Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in

In this paper we consider the problem of determining whether an unknown arithmetic circuit, for which we have oracle access, computes the identically zero polynomial. This problem is known as the black-box polynomial identity testing (PIT) problem. Our focus is on polynomials that can be written in the form f([`(x)]) = ?<sub>i = 1</sub><sup>k</sup> h<sub>i</sub> ([`(x)]) ·g_i ([`(x)])f(\bar x) = \sum\nolimits_{i = 1}^k {h_i (\bar x) \cdot g_i (\bar x)} , where each h _i is a polynomial that depends on only ρ linear functions, and each g _i is a product of linear functions (when h _i = 1, for each i, then we get the class of depth-3 circuits with k multiplication gates, also known as ΣΠΣ(k) circuits, but the general case is much richer). When max _i (deg(h _i · g _i )) = d we say that f is computable by a ΣΠΣ(k; d;ρ) circuit. We obtain the following results.

Nash-solvable two-person symmetric cycle game forms

A two-person positional game form g (with perfect information and without moves of chance) is modeled by a finite directed graph (digraph) whose vertices and arcs are interpreted as positions and moves, respectively. All simple directed cycles of this digraph together with its terminal positions form the set A of the outcomes. Each non-terminal position j is controlled by one of two players i∈I={1,2}. A strategy x_i of a player i∈I involves selecting a move (j,j^′) in each position j controlled by i. We restrict both players to their pure positional strategies; in other words, a move (j,j^′) in a position j is deterministic (not random) and it can depend only on j (not on preceding positions or moves or on their numbers). For every pair of strategies (x₁,x₂), the selected moves uniquely define a play, that is, a directed path form a given initial position j₀ to an outcome (a directed cycle or terminal vertex). This outcome a∈A is the result of the game corresponding to the chosen strategies, a=a(x₁,x₂). Furthermore, each player i∈I={1,2} has a real-valued utility function u_i over A. Standardly, a game form g is called Nash-solvable if for every u=(u₁,u₂) the obtained game (g,u) has a Nash equilibrium (in pure positional strategies).A digraph (and the corresponding game form) is called symmetric if (j,j^′) is its arc whenever (j^′,j) is. In this paper we obtain necessary and sufficient conditions for Nash-solvability of symmetric cycle two-person game forms and show that these conditions can be verified in linear time in the size of the digraph.     

The Latent Scale Covariogram: A Tool for Exploring the Spatial Dependence Structure of Nonnormal Responses

When modeling spatially distributed normal responses Y_i in terms of vectors x_i of explanatory variables, one may fit a linear model assuming independence, and then use the empirical variogram of the residuals to determine an appropriate parametric form for the autocorrelation function. Suppose, however, that the responses are not normally distributed—for example, Poisson or Bernoulli. One may model spatial dependence using a hierarchical generalized linear model in which, conditional on a latent Gaussian field Z = {Z_i}, the Y_i have independent distributions from the exponential family, with an appropriate link function connecting their conditional means with the linear predictors x^t_iβ + Z_i. The question then is how to determine an appropriate model for the autocorrelation function of Z. The empirical variogram of the Y_i is no longer appropriate, since (unless the link function is the identity) it is on the wrong scale. We propose here an alternative, the latent scale covariogram, whose graph reflects the autocorrelation structure of the underlying normal field. We illustrate its use on several real datasets, together with a simulated dataset, and obtain results quite different from those obtained using the variogram. Supplementary materials for this article are available online.     

Lacunary Quadrature Formulae and Interpolation Singularity

Birkholl quadrature formulae (q.f.), which have algebraic degree of precision (ADP) greater than the number of values used, are studied. In particular, we construct a class of quadrature rules of ADP = 2n + 2r + 1 which are based on the information {ƒ^(j)(−1), ƒ^(j)(−1), j = 0, ..., r − 1 ; ƒ(x_i), ƒ^(2m)(x_i), i = 1, ..., n}, where m is a positive integer and r = m, or r = m − 1. It is shown that the corresponding Birkhoff interpolation problems of the same type are not regular at the quadrature nodes. This means that the constructed quadrature formulae are not of interpolatory type. Finally, for each In, we prove the existence of a quadrature formula based on the information {ƒ(x_i), ƒ^(2m)(x_i), i = 1, ..., 2m}, which has algebraic degree of precision 4m + 1.     

A Finite Algorithm for Solving Infinite Dimensional Optimization Problems

We consider the general optimization problem (P) of selecting a continuous function x over a -compact Hausdorff space T to a metric space A, from a feasible region X of such functions, so as to minimize a functional c on X. We require that X consist of a closed equicontinuous family of functions lying in the product (over T) of compact subsets Y _t of A. (An important special case is the optimal control problem of finding a continuous time control function x that minimizes its associated discounted cost c(x) over the infinite horizon.) Relative to the uniform-on-compacta topology on the function space C(T,A) of continuous functions from T to A, the feasible region X is compact. Thus optimal solutions x ^* to (P) exist under the assumption that c is continuous. We wish to approximate such an x ^* by optimal solutions to a net {P _i }, iI, of approximating problems of the form min_{xX i} c i(x) for each iI, where (1) the net of sets {X _i } _I converges to X in the sense of Kuratowski and (2) the net {c _i } _I of functions converges to c uniformly on X. We show that for large i, any optimal solution x ^* _i to the approximating problem (P _i ) arbitrarily well approximates some optimal solution x ^* to (P). It follows that if (P) is well-posed, i.e., limsupX _i ^* is a singleton {x ^*}, then any net {x _i ^*} _I of (P _i )-optimal solutions converges in C(T,A) to x ^*. For this case, we construct a finite algorithm with the following property: given any prespecified error and any compact subset Q of T, our algorithm computes an i in I and an associated x _i ^* in X _i ^* which is within of x ^* on Q. We illustrate the theory and algorithm with a problem in continuous time production control over an infinite horizon.