Inverse problems on multi-unit assignment valuations

Inverse and bilevel optimization problems play a central role in both theory and applications. These two classes are known to be closely related and thus have often been discussed together In a recent paper titled On the Complexity of Inverse Bivariate Multi-unit Assignment Valuation Problems, we consider inverse problems for multi-unit assignment valuations. Multi-unit assignment valuations form a subclass of strong-substitutes valuations that can be represented by edge-weighted complete bipartite graphs. These valuations play a key role in auction theory as the strong substitutes condition implies the existence of a Walrasian equilibrium. A recent line of research concentrated on the problem of deciding whether a bivariate valuation function is an assignment valuation or not. In the paper, we consider an inverse variant of the problem: we are given a bivariate function g, and our goal is to find a bivariate multi-unit assignment valuation function f that is as “close” to g as possible. Using tools from discrete convex analysis, we show that the problem is strongly NP-hard. On the other hand, we derive linear programming formulations that solve relaxed versions of the problem.