Arity of polynomials for equivalence classes of pseudo-Boolean functions

Abstract

Pseudo-Boolean functions, which map binary inputs to rational numbers, are widely used in areas such as local search, evolutionary biology and decision science. These functions can be uniquely represented by multi-linear polynomials, where the arity denotes the maximum number of variables that co-occur in a monomial. In many settings, however, we lack access to exact function values and only observe how certain outputs compare to one another. This ambiguity allows multiple multi-linear polynomials to represent the same outcome order, raising our main question: What is the minimal arity among all multi-linear polynomials whose outputs are consistent with a given outcome order? We present criteria to determine when all variables must co-occur in a monomial, and develop methods to assess whether an arity of at least $k$ is required. As a case study, we apply our framework to Matoušek functions which are important in the analysis of simplex algorithms. We show that any pseudo-Boolean function that behaves like a Matoušek function must include certain monomials in its multilinear polynomial representation.