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.     

Formulas for approximating pseudo-Boolean random variables

We consider {0,1}ⁿ as a sample space with a probability measure on it, thus making pseudo-Boolean functions into random variables. We then derive explicit formulas for approximating a pseudo-Boolean random variable by a linear function if the measure is permutation-invariant, and by a function of degree at most k if the measure is a product measure. These formulas generalize results due to Hammer-Holzman and Grabisch-Marichal-Roubens. We also derive a formula for the best faithful linear approximation that extends a result due to Charnes-Golany-Keane-Rousseau concerning generalized Shapley values. We show that a theorem of Hammer-Holzman that states that a pseudo-Boolean function and its best approximation of degree at most k have the same derivatives up to order k does not generalize to this setting for arbitrary probability measures, but does generalize if the probability measure is a product measure.     

Transforms of pseudo-Boolean random variables

As in earlier works, we consider {0,1}ⁿ as a sample space with a probability measure on it, thus making pseudo-Boolean functions into random variables. Under the assumption that the coordinate random variables are independent, we show it is very easy to give an orthonormal basis for the space of pseudo-Boolean random variables of degree at most k. We use this orthonormal basis to find the transform of a given pseudo-Boolean random variable and to answer various least squares minimization questions.     

Recognition problems for special classes of polynomials in 0–1 variables

This paper investigates the complexity of various recognition problems for pseudo-Boolean functions (i.e., real-valued functions defined on the unit hypercubeB ⁿ = {0, 1} ⁿ ), when such functions are represented as multilinear polynomials in their variables. Determining whether a pseudo-Boolean function (a) is monotonic, or (b) is supermodular, or (c) is threshold, or (d) has a unique local maximum in each face ofB ⁿ , or (e) has a unique local maximum inB ⁿ , is shown to be NP-hard. A polynomial-time recognition algorithm is presented for unimodular functions, previously introduced by Hansen and Simeone as a class of functions whose maximization overB ⁿ is reducible to a network minimum cut problem.     

Les derivees partielles des fonctions pseudo-booleennes generalisees

This paper is devoted to a study of differential calculus for generalised pseudo-Boolean functions with finite domain and antidomain P with a ring structure which may be infinite. A completely new definition is given of partial derivatives of generalised pseudo-Boolean functions $\text{?f}{}_{\mathrm{q}}\text{?x}{}_{\mathrm{i}}\text{=f(x}{}_1\text{,…,x}{}_{\mathrm{i?1}}\text{,a,x}{}_{\mathrm{i+1}}\text{,…,x}{}_{\mathrm{n}}\text{)?f(x}{}_1\text{,…,x}{}_{\mathrm{n}}\text{)}$. Further are given some properties of these partial derivatives and a new Taylor expansion.M. Davio, J.P. Deschamps, A. Thayse, Belgian mathematicians, have studied the differential calculus for discrete functions with finite domain and antidomain which is a totally ordered lattice 0<1<?<m?1 with a structure of a ring of integers modulo m. If P is finite, then generalised pseudo-Boolean functions are discrete functions, but the partial derivatives of generalised pseudo-Boolean functions are different from the partial derivatives of discrete functions which were studied by the Belgian mathematicians.     

Difference operators and extended truth vectors for discrete functions

Discrete functions are mappings ? of a finite set $\text{d}\text{}$ into a lattice $\text{L}$. Prime blocks and prime antiblocks generalize for discrete functions the well known concepts of prime implicants and of prime implicates for Boolean functions. A lattice difference operator is defined for discrete functions which, together with the concept of extended vector, allows us to derive new attractive algorithms for obtaining the prime blocks and antiblocks of a discrete function. Applications of the theory to p-symmetric Boolean functions and to transient analysis of binary switching networks are mentioned.     

On the Isomorphism of Fractional Factorial Designs

Two fractional factorial designs are called isomorphic if one can be obtained from the other by relabeling the factors, reordering the runs, and switching the levels of factors. To identify the isomorphism of two s-factor n-run designs is known to be an NP hard problem, when n and s increase. There is no tractable algorithm for the identification of isomorphic designs. In this paper, we propose a new algorithm based on the centered L₂-discrepancy, a measure of uniformity, for detecting the isomorphism of fractional factorial designs. It is shown that the new algorithm is highly reliable and can significantly reduce the complexity of the computation. Theoretical justification for such an algorithm is also provided. The efficiency of the new algorithm is demonstrated by using several examples that have previously been discussed by many others.     

Approximations of pseudo-Boolean functions; applications to game theory

This paper studies the approximation of pseudo-Boolean functions by linear functions and more generally by functions of (at most) a specified degree. Here a pseudo-Boolean function means a real valued function defined on {0,1} ⁿ , and its degree is that of the unique multilinear polynomial that expresses it; linear functions are those of degree at most one. The approximation consists in choosing among all linear functions the one which is closest to a given function, where distance is measured by the Euclidean metric onR ²ⁿ . A characterization of the best linear approximation is obtained in terms of the average value of the function and its first derivatives. This leads to an explicit formula for computing the approximation from the polynomial expression of the given function. These results are later generalized to handle approximations of higher degrees, and further results are obtained regarding the interaction of approximations of different degrees. For the linear case, a certain constrained version of the approximation problem is also studied. Special attention is given to some important properties of pseudo-Boolean functions and the extent to which they are preserved in the approximation. A separate section points out the relevance of linear approximations to game theory and shows that the well known Banzhaf power index and Shapley value are obtained as best linear approximations of the game (each in a suitably defined sense).Supported by the Air Force Office of Scientific Research (under grant number AFOSR 89-0512 and AFOSR 90-0008 to Rutgers University), as well as the National Science Foundation (under grant number DMS 89-06870).     

Solitaire Lattices

 One of the classical problems concerning the peg solitaire game is the feasibility issue. Tools used to show the infeasibility of various peg games include valid inequalities, known as pagoda-functions, and the so-called rule-of-three. Here we introduce and study another necessary condition: the solitaire lattice criterion. While the lattice criterion is shown to be equivalent to the rule-of-three for the classical English 33-board and French 37-board as well as for any m×n board, the lattice criterion is stronger than the rule-of-three for games played on more complex boards. In fact, for a wide family of boards presented in this paper, the lattice criterion exponentially outperforms the rule-of-three. Received: February 22, 1999?Final version received: June 19, 2000     

An aperiodic hexagonal tile

We show that a single prototile can fill space uniformly but not admit a periodic tiling. A two-dimensional, hexagonal prototile with markings that enforce local matching rules is proven to be aperiodic by two independent methods. The space-filling tiling that can be built from copies of the prototile has the structure of a union of honeycombs with lattice constants of n²a, where a sets the scale of the most dense lattice and n takes all positive integer values. There are two local isomorphism classes consistent with the matching rules and there is a nontrivial relation between these tilings and a previous construction by Penrose. Alternative forms of the prototile enforce the local matching rules by shape alone, one using a prototile that is not a connected region and the other using a three-dimensional prototile.     

Viscosity Solutions of Systems of PDEs with Interconnected Obstacles and Switching Problem

This paper deals with existence and uniqueness of a solution in viscosity sense, for a system of m variational partial differential inequalities with inter-connected obstacles. A particular case is the Hamilton-Jacobi-Bellmann system of the Markovian stochastic optimal m-states switching problem. The switching cost functions depend on (t,x). The main tool is the notion of systems of reflected backward stochastic differential equations with oblique reflection.     

Even signings,signed switching classes,and (−1, 1)-matrices

In this paper, algebraic and combinatorial techniques are used to establish results concerning even signings of graphs, switching classes of signed graphs, and (?1, 1)-matrices. These results primarily deal with enumeration of isomorphism types, and determining whether there are fixed elements under the action of automorphisms. A formula is given for the number of isomorphism types of even signings of any fixed simple graph. This is shown to be equal to the number of isomorphism types of switching classes of signings of the graph. A necessary and sufficient criterion is found for all switching classes fixed by a given graph automorphism to contain signings fixed by that automorphism. It is determined whether this criterion is met for all automorphisms of various graphs, including complete graphs, which yields a known result of Mallows and Sloane. As an application, a formula is developed for the number of H-equivalence classes of (?1, 1)-matrices of fixed size. Independently, using Molien's theorem and following a suggestion of Cameron's, generating series for these numbers are given. As a final application, a necessary and sufficient condition that a square (?1, 1)-matrix be switching equivalent to a symmetric matrix is given.     

Lattice tensor products. II

G. Grätzer and F. Wehrung has recently introduced the lattice tensor product, A?B, of the lattices A and B. In this note, for a finite lattice A and an arbitrary lattice B, we compute the ideal lattice of A?B, obtaining the isomorphism Id(A?B)≌A?Id B. This generalizes an earlier result of G. Grätzer and F. Wehrung proving this isomorphism for A = M_3 and B n-modular. We prove this isomorphism by utilizing the coordinatization of A?B introduced in Part I of this paper.     

Isomorphism in 3-person games

We prove that two 3-person games with empty core are isomorphic if and only if they areS-equivalent, and up to isomorphism, there are 21 essential 3-person games with nonempty core.     

Correlation inequalities for statistical models of lattice gas

We consider models of statistical mechanics of the type of lattice gas with attractive interaction of general kind. We propose a method for obtaining inequalities that connect multipoint correlation functions of different order. This method allows one, on the one hand, to strengthen similar inequalities, which can be obtained within the framework of the FKG method, and on the other hand, to obtain new inequalities. We introduce the notion of duality for models of lattice gas. We show that if, under the transformation p ⇒ 1 - p, the correlation inequalities for a model with attraction turn into the corresponding inequalities that are also satisfied, then the correlation functions of the dual model also satisfy the latter inequalities. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 50, No. 6, pp. 765–773, June, 1998.     

A pseudo-Boolean consensus approach to nonlinear 0–1 optimization

It is proved that any pseudo-Boolean function f can be represented as , where z is the minimum of f and φ is a polynomial with positive coefficients in the original variables x_i and in their complements . A non-constructive proof and a constructive one are given. The latter, which is based on a generalization to pseudo-Boolean functions of the well-known Boolean-theoretical operation of consensus, provides a new algorithm for the minimization of pseudo-Boolean functions.     

The nucleolus and kernel for simple games or special valid inequalities for 0–1 linear integer programs

An equivalence between simplen-person cooperative games and linear integer programs in 0–1 variables is presented and in particular the nucleolus and kernel are shown to be special valid inequalities of the corresponding 0–1 program. In the special case of weighted majority games, corresponding to knapsack inequalities, we show a further class of games for which the nucleolus is a representation of the game, and develop a single test to show when payoff vectors giving identical amounts or zero to each player are in the kernel. Finally we give an algorithm for computing the nucleolus which has been used successfully on weighted majority games with over twenty players.     

The duality theorem for min-max functions

The set of min-max functions F : ℝⁿ → ℝⁿ is the least set containing coordinate substitutions and translations and closed under pointwise max, min, and function composition. The Duality Conjecture asserts that the trajectories of a min-max function, considered as a dynamical system, have a linear growth rate (cycle time) and shows how this can be calculated through a representation of F as an infimum of max-plus linear functions. We prove the conjecture using an analogue of Howard's policy improvement scheme, carried out in a lattice ordered group of germs of affine functions at infinity. The methods yield an efficient algorithm for computing cycle times.     

The connected partition lattice of a graph and the reconstruction conjecture

Previously we showed that many invariants of a graph can be computed from its abstract induced subgraph poset, which is the isomorphism class of the induced subgraph poset, suitably weighted by subgraph counting numbers. In this paper, we study the abstract bond lattice of a graph, which is the isomorphism class of the lattice of distinct unlabelled connected partitions of a graph, suitably weighted by subgraph counting numbers. We show that these two abstract posets can be constructed from each other except in a few trivial cases. The constructions rely on certain generalisations of a lemma of Kocay in graph reconstruction theory to abstract induced subgraph posets. As a corollary, trees are reconstructible from their abstract bond lattice. We show that the chromatic symmetric function and the symmetric Tutte polynomial of a graph can be computed from its abstract induced subgraph poset. Stanley has asked if every tree is determined up to isomorphism by its chromatic symmetric function. We prove a counting lemma, and indicate future directions for a study of Stanley's question.     

Characterizing fully principal congruence representable distributive lattices

Motivated by a recent paper of G. Grätzer, a finite distributive lattice D is called fully principal congruence representable if for every subset Q of D containing 0, 1, and the set J(D) of nonzero join-irreducible elements of D, there exists a finite lattice L and an isomorphism from the congruence lattice of L onto D such that Q corresponds to the set of principal congruences of L under this isomorphism. A separate paper of the present author contains a necessary condition of full principal congruence representability: D should be planar with at most one join-reducible coatom. Here we prove that this condition is sufficient. Furthermore, even the automorphism group of L can arbitrarily be stipulated in this case. Also, we generalize a recent result of G. Grätzer on principal congruence representable subsets of a distributive lattice whose top element is join-irreducible by proving that the automorphism group of the lattice we construct can be arbitrary.