In a one-sided matching market, we are given a set G of goods and a set A of agents with |A| = |G|. Agents have preferences over the goods and each agent is to be assigned exactly one good. The goal is to design a mechanism without monetary transfers which finds a perfect matching satisfying desirable game-theoretic properties. Markets of this kind arise in many scenarios where payments are impractical or immoral such as when assigning students to schools or doctors to hospitals.

In a recent paper, Beniamini and Nisan [4] gave a closed-form formula for the unique multilinear polynomial for the Boolean function determining whether a given bipartite graph G⊆Kn,n has a perfect matching, together with an efficient algorithm for computing the coefficients of the monomials of this polynomial. We give the following generalization: Given an arbitrary weight function w on the edges of Kn,n, consider its set of minimum weight perfect matchings. We give the real multilinear polynomial for the Boolean function which determines if a graph G⊆Kn,n contains one of these minimum weight perfect matchings. Finally, we discuss a number of open problems which follow from [4] and our work; in particular, extending the main theorem of [4] to non-bipartite graphs.