A geometric connection to threshold logic via cubical lattices

A cut-complex is a cubical complex whose vertices are strictly separable from the rest of the vertices of the n-cube by a hyperplane of R ⁿ . These objects render geometric presentations for threshold Boolean functions, the core objects of study in threshold logic. By applying cubical lattices and geometry of rotating hyperplanes, we prove necessary and sufficient conditions to recognize the cut-complexes with 2 or 3 maximal faces. This result confirms a positive answer to an old conjecture of Metropolis-Rota concerning cubical lattices.     

Geometry of cut-complexes and threshold logic

Geometric methods of convex polytopes are applied to demonstrate a new connection between convexity and threshold logic. A cut-complex is a cubical complex whose vertices are strictly separable from rest of the vertices of then-cube by a hyperplane ofRⁿ. Cutcomplexes are geometric presentations for threshold Boolean functions and thus are related to threshold logic. For an old classical theorem of threshold logic a shorter but geometric proof is given. The dimension of the cube hull of a cut-complex is shown to be the same as the maximum degree of the vertices in the complex. A consequence of the latter result indicates that any two isomorphic cut-complexes are isometric.This research was partially supported by FIPI-University of Puerto Rico, by Inter American University of Puerto Rico at Bayamon and by IPM, Tehran, Iran.     

Robust game theory

We present a distribution-free model of incomplete-information games, both with and without private information, in which the players use a robust optimization approach to contend with payoff uncertainty. Our ``robust game' model relaxes the assumptions of Harsanyi's Bayesian game model, and provides an alternative distribution-free equilibrium concept, which we call ``robust-optimization equilibrium,' to that of the ex post equilibrium. We prove that the robust-optimization equilibria of an incomplete-information game subsume the ex post equilibria of the game and are, unlike the latter, guaranteed to exist when the game is finite and has bounded payoff uncertainty set. For arbitrary robust finite games with bounded polyhedral payoff uncertainty sets, we show that we can compute a robust-optimization equilibrium by methods analogous to those for identifying a Nash equilibrium of a finite game with complete information. In addition, we present computational results. The research of the author was partially supported by a National Science Foundation Graduate Research Fellowship and by the Singapore-MIT Alliance. The research of the author was partially supported by the Singapore-MIT Alliance.     

A game semantics for disjunctive logic programming

Denotational semantics of logic programming and its extensions (by allowing negation, disjunctions, or both) have been studied thoroughly for many years. In 1998, a game semantics was given to definite logic programs by Di Cosmo, Loddo, and Nicolet, and a few years later it was extended to deal with negation by Rondogiannis and Wadge. Both approaches were proven equivalent to the traditional semantics. In this paper we define a game semantics for disjunctive logic programs and prove soundness and completeness with respect to the minimal model semantics of Minker. The overall development has been influenced by the games studied for PCF and functional programming in general, in the styles of Abramsky–Jagadeesan–Malacaria and Hyland–Ong–Nickau.     

Comparative cooperative game theory

Given two side-payment gamesv andw, both defined for the same finite player-setN, the following three welfare criteria are characterized in terms of the datav andw: (A) For everyy C(w) there existsx C(v) such thatyx; (A) For everyxC(v) there existsyC(w) such thatyx; and (B) There existyC(w) andxC(v) such thatyx. (HereC(v) denotes the core ofv.) Given two non-side-payment gamesv andw, sufficient conditions for the criteria (A) and (B) are established, by observing that an ordinal convex game has a large core.In memory of my teacher in Japan, Professor Ryuichi Watanabe, 1928–1986.     

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

Applications of the theory of semi-embeddings to Banach space theory

Let X and Y be Banach spaces and T:X → Y an injective bounded linear operator. T is called a semi-embedding if T maps the closed unit ball of X to a closed subset of Y. (This concept was introduced by Lotz, Peck, and Porta, Proc. Edinburgh Math. Soc.22 (1979), 233–240.) It is proved that if X semi-embeds in Y, and X is separable, then X has the Radon-Nikodym property provided Y does. It is shown that if L¹ semi-embeds in Y, then Y fails the Schur property and contains a subspace isomorphic to l¹. As a consequence of the proof, it is shown that if X is a subspace of L¹, either L¹ embeds in X or l¹ embeds in $\text{L}{}^1\text{X}$. The simpler result that L¹ does not semi-embed in c₀ is treated separately. This result is used to deduce the classic result of Menchoff that there exists a singular probability measure on the circle with Fourier coefficients vanishing at infinity. Some generalizations of the notion of semi-embedding are given, and several complements and open questions are discussed.     

Applications of the theory of modular forms to number theory

The survey is devoted to arithmetic questions in the theory of modular forms and, in particular, to arithmetic applications of modular functions; mainly only elementary and analytic aspects of this topic, as a rule, for the case of a single variable are presented.Translated from Itogi Nauki i Tekhniki, Algebra, Topologiya, Geometriya, Vol. 15, pp. 5–91, 1977.     

Useful equilibria for game theory

We suggest two new notions of equilibria for arbitrary game problems, both static and dynamic ones, whose definitions contain no artificial norms for the behavior of the players. In examples of static and differential games, we demonstrate the possibilities of these equilibria and a technique for finding them.     

Density estimation using game theory

In this note we show that the mathematical tools of cooperative game theory allow a successful approach to the statistical problem of estimating a density function. Specifically, any random sample of an absolutely continuous random variable determines a transferable utility game, the Shapley value of which proves to be an estimator of the density function of binned kernel and WARPing types, with good computational and statistical properties.Authors acknowledge the financial support of Spanish Ministry for Science and Technology and FEDER through projects BFM2002-03213 and BEC2002-04102-C02-02 and of Xunta de Galicia through projects PGIDT00PXI20104PR and PGIDT03PXIC20701PN. They also thank the comments of two anonymous referees.     

Axiomatization in cooperative game theory

We develop a theory of cooperative games based on a new concept of characteristic function. This approach substantially reduces the number of solutions and shows that noncooperative equilibria lead in some cases to a unique cooperative solution.Translated from Nelineinaya Dinamika i Upravlenie, No. 2, pp. 195–208, 2002.     

Cooperative game theory approach to allocating benefits of horizontal cooperation

Logistics costs in general, and transportation costs in particular, represent a large fraction of the operating costs of many companies. One way to try to reduce these costs is through horizontal cooperation among shippers. Thus, when the transportation needs of two or more companies are merged, their collective transportation requirements can be met at lower cost. The attainable cost savings are due to economies of scale, which translate into cheaper rates due to increased negotiation power, use of larger vehicles and bundling of shipments. In this paper, a linear model is presented and used to study the cost savings that different companies may achieve when they merge their transportation requirements. On the one hand, solving this optimization model for different collaboration scenarios allows testing and quantifying the synergies among different potential partners, thus identifying the most profitable collaboration opportunities. On the other, the problem of allocating the joint cost savings of the cooperation is tackled using cooperative game theory. The proposed approach is illustrated with an example in which different cooperative game solution concepts are compared. Extensive numerical experiments have also been carried out to gain insight into the properties of the corresponding cost savings game and the behavior of the different solution concepts.     

Applications of perturbation theory to iterated fibrations

For a class of spaces including simply connected spaces and classifying spaces of nilpotent groups, relatively small differential graded algebras are constructed over commutative rings with 1 which are chain homotopy equivalent to the singular cochain algebra. An application to finitely generated torsion-free nilpotent groups over the integers is given.     

Cutting planes,connectivity, and threshold logic

Originating from work in operations research the cutting plane refutation systemCP is an extension of resolution, where unsatisfiable propositional logic formulas in conjunctive normal form are recognized by showing the non-existence of boolean solutions to associated families of linear inequalities. Polynomial sizeCP proofs are given for the undirecteds-t connectivity principle. The subsystemsCP _q ofCP, forq2, are shown to be polynomially equivalent toCP, thus answering problem 19 from the list of open problems of [8]. We present a normal form theorem forCP ₂-proofs and thereby for arbitraryCP-proofs. As a corollary, we show that the coefficients and constant terms in arbitrary cutting plane proofs may be exponentially bounded by the number of steps in the proof, at the cost of an at most polynomial increase in the number of steps in the proof. The extensionCPLE ⁺, introduced in [9] and there shown top-simulate Frege systems, is proved to be polynomially equivalent to Frege systems. Lastly, since linear inequalities are related to threshold gates, we introduce a new threshold logic and prove a completeness theorem.Supported in part by NSF grant DMS-9205181 and by US-Czech Science and Technology Grant 93-205Partially supported by NSF grant CCR-9102896 and by US-Czech Science and Technology Grant 93-205