Skip to main content

Imre Bárány Publications

Publish Date
Mathematics of Operations Research
Abstract

Given a generic m by n matrix A, a lattice point h in Z is a neighbor of the origin if the body {x : Ax < b}, with bi = max{0, aih}, i = 1, …, m, contains no lattice point other than 0 and h. The set of neighbors, N(A), is finite and Asymmetric. We show that if A’ is another matrix of the same size with the property that sign aih = sign ai’ h for every i and every h in N(A), then A’ has precisely the same set of neighbors as A. The collection of such matrices is a polyhedral cone, described by a finite set of linear inequalities, each such inequality corresponding to a generator of one of the cones Ci = pos(h in N(A) : aih < 0}. Computational experience shows that Ci has “few” generators. We demonstrate this in the first nontrivial case n = 3, m = 4.

Mathematical Programming
Abstract

The simplicial complex K(A) is defined to be the collection of simplices, and their proper subsimplices, representing maximal lattice free bodies of the form {x : Ax < b}, with A a fixed (n + 1) × n matrix. The topological space associated with K(A) is shown to be homeomorphic to Rn, and the space obtained by identifying lattice translates of these simplices is homeomorphic to the n-torus.

Abstract

The set of possible outcomes of a strongly ordinal bimatrix game is studied by imbedding each pair of possible payoffs as a point on the standard two-dimensional integral lattice. In particular, we count the number of different Pareto optimal sets of each cardinality; we establish asymptotic bounds for the number of different convex hulls of the point sets, for the average shape of the set of points dominated by the Pareto optimal set, and for the average shape of the convex hull of the point set. We also indicate the effect of individual rationality considerations on our results. As most of our results are asymptotic, the appendix includes a careful examination of the important case of 2 x 2 games.

Abstract

Given a polyhedron P subset Rn we write PI for the convex hull of the integral points in P. It is known that PI can have at most O(ϕn-1) vertices if P is a rational polyhedron with size ϕ. Here we give an example showing that PI can have as many as Ω(ϕn-1) vertices. The construction uses the Dirichlet unit theorem.

Keywords: Polyhedra; integral points, Dirichlet unit theorem

JEL Classification: 213