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).     

Contributions to the theory of stochastic programming

Two stochastic programming decision models are presented. In the first one, we use probabilistic constraints, and constraints involving conditional expectations further incorporate penalties into the objective. The probabilistic constraint prescribes a lower bound for the probability of simultaneous occurrence of events, the number of which can be infinite in which case stochastic processes are involved. The second one is a variant of the model: two-stage programming under uncertainty, where we require the solvability of the second stage problem only with a prescribed (high) probability. The theory presented in this paper is based to a large extent on recent results of the author concerning logarithmic concave measures.This work was supported in part by the Institute of Economic Planning, Budapest.This paper was presented at the 7th Mathematical Programming Symposium 1970, The Hague, The Netherlands, under the title Programming under probabilistic constraints and programming under constraints involving conditional expectations.     

Weighted stability number of graphs and weighted satisfiability: The two facets of pseudo-Boolean optimization

We exhibit links between pseudo-Boolean optimization, graph theory and logic. We show the equivalence of maximizing a pseudo-Boolean function and finding a maximum weight stable set; symmetrically minimizing a pseudo-Boolean function is shown to be equivalent to solving a weighted satisfiability problem.     

Irredundant optimization of a pseudo-Boolean function

In Ref. 1, methods for solving bivalent, linear or nonlinear programs were given, and various applications to operations research, graph theory, and related areas were described. The basic algorithm of Ref. 1 gives the maximum (minimum) of any real-valued functionf(x ₁,...,x _n) with (0, 1) variables. It provides a parametric representation of all theN points wheref reaches its optimum. In all concrete applications, it turned out that the numberm of parameters actually appearing in the representation was the smallest integer such thatN2 ^m .In this paper, we show that the latter property need not hold in all cases, but we can choose the parameters so as to obtain each optimizing point once, and only once.     

Solving a cut problem in bipartite graphs by linear programming: Application to a forest management problem

Given a bipartite graph G=(V,E)$G=(V\text{,}E)$, a weight for each node, and a weight for each edge, we consider an extension of the MAX-CUT problem that consists in searching for a partition of V$V$ into two subsets _V1$V_1$ and _V2$V_2$ such that the sum of the weights of the edges from E$E$ that have one endpoint in each set plus the sum of the weights of the nodes from V$V$ that are in _V1$V_1$, is maximal. We prove that this problem can be modeled as a linear program (with real variables) and therefore efficiently solved by standard algorithms. Then, we show how this result can be applied to model a land allocation problem by a 0–1 linear program. This problem consists in determining the cells of a land area, divided into a matrix of identical square cells, which must be harvested and the cells which must be left in old growth so that the weighted sum of the expected populations of some species is maximized. Some computational results are presented to illustrate the efficiency of the method.     

Intersection theory for graphs

An intersection theory developed by the author for matroids embedded in uniform geometries is applied to the case when the ambient geometry is the lattice of partitions of a finite set so that the matroid is a graph. General embedding theorems when applied to graphs give new interpretations to such invariants as the dichromate of Tutte. A polynomial in n + 1 variables, the polychromate, is defined for graphs with n vertices. This invariant is shown to be strictly stronger than the dichromate, it is edge-reconstructible and can be calculated for proper graphs from the polychromate of the complementary graph. By using Tutte's construction for codichromatic graphs (J. Combinatorial Theory 16 (1974), 168–174), copolychromatic (and therefore codichromatic) graphs of arbitrarily high connectivity are constructed thereby solving a problem posed in Tutte's paper.     

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.     

线性规划中的退化最优基图

Abstract. The basis graph G for a linear programming consists of all bases under pivot transfor-mations. A degenerate optimal basis graph G is a subgraph of G induced by all optimal bases ata degenerate optimal vertex x. In this paper, several conditions for the characterization of G“are presented.     

Application of graphs to the Gaussian elimination method

Certain algebraic operations (in the Boolean sense) are developed for directed graphs. Nonsingular and inverse graphs are defined and some of their characteristics are derived. The results are applied for the Gaussian elimination process.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 58, pp. 72–79, 1976.     

An integer programming formulation of the Steiner problem in graphs

A succinct integer linear programming model for the Steiner problem in networks is presented.     

A theory of degeneracy graphs

Using some results of the theory of finite sets, a characterization of ×n-degeneracy graphs is developed. This result can be used to derive various structural properties of degeneracy graphs.     

On some applications of dynamic programming to information theory

The technique of dynamic programming is employed to find the number of subevents into which each event of a finite generalised probability scheme should be divided so as to optimize the expressions for entropies given by Shannon, Renyi and the author. Attention is drawn to a new class of non-linear integer programming problems which arise during the course of the discussion.     

Contributions to the theory of domination,independence and irredundance in graphs

A vertex x in a subset X of vertices of an undirected graph is redundant if its closed neighbourhood is contained in the union of closed neighbourhoods of vertices of X?{x}. In the context of a communications network, this means that any vertex which may receive communications from X may also be informed from X?{x}. The lower and upper irredundance numbers ir(G) and IR(G) are respectively the minimum and maximum cardinalities taken over all maximal sets of vertices having no redundancies. The domination number γ(G) and upper domination number Γ(G) are respectively the minimum and maximum cardinalities taken over all minimal dominating sets of G. The independent domination number i(G) and the independence number β(G) are respectively the minimum and maximum cardinalities taken over all maximal independent sets of vertices of G.A variety of inequalities involving these quantities are established and sufficient conditions for the equality of the three upper parameters are given. In particular a conjecture of Hoyler and Cockayne [9], namely $\text{i+β?2p + 2δ - 2}\text{2pδ}$, is proved.     

Discrete Morse theory on graphs

We characterize the topology of a graph in terms of the critical elements of a discrete Morse function defined on it. Besides, we study the structure and some properties of the gradient vector field induced by a discrete Morse function defined on a graph. Finally, we get results on the number of non-homologically equivalent excellent discrete Morse functions defined on some kind of graphs.     

A polyhedral theory on graphs

This paper provides a polyhedral theory on graphs from which the criteria of Whitney and MacLane for the planarity of graphs are unified, and a brief proof of the Gauss crossing conjecture is obtained. Supported by the National Natural Science Foundation of China.     

Knot theory for self-indexed graphs

We introduce and study so-called self-indexed graphs. These are (oriented) finite graphs endowed with a map from the set of edges to the set of vertices. Such graphs naturally arise from classical knot and link diagrams. In fact, the graphs resulting from link diagrams have an additional structure, an integral flow. We call a self-indexed graph with integral flow a comte. The analogy with links allows us to define transformations of comtes generalizing the Reidemeister moves on link diagrams. We show that many invariants of links can be generalized to comtes, most notably the linking number, the Alexander polynomials, the link group, etc. We also discuss finite type invariants and quandle cocycle invariants of comtes.

     

Random graphs in the monadic theory of order

We continue the works of Gurevich-Shelah and Lifsches-Shelah by showing that it is consistent with ZFC that the first-order theory of random graphs is not interpretable in the monadic theory of all chains. It is provable from ZFC that the theory of random graphs is not interpretable in the monadic second order theory of short chains (hence, in the monadic theory of the real line). Received: 18 July 1996