On the complexity of inverse bivariate multi-unit assignment valuation problems

Abstract

Inverse and bilevel optimization problems play a central role in both theory and applications. These two classes are known to be closely related due to the pioneering work of Dempe and Lohse (2006), and thus have often been discussed together ever since. In this paper, 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 this 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. The difference between f and g can be measured either in ${\ell }_1$- or ${\ell }_{\mathrm{\infty }}$-norm. Using tools from discrete convex analysis, we show that the problem is strongly $\mathsf{NP}$-hard. On the other hand, we derive linear programming formulations that solve relaxed versions of the problem.

Keywords:

• Assignment valuations
• inverse problems
• linear programming
• $M^{\mathrm{♮}}$-concave sets
• product-mix auction

2020 Mathematics Subject Classifications:

• 91-10
• 90C60
• 90C05

Acknowledgments

The authors are truly grateful for the reviewers for their helpful comments.

Disclosure statement

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Additional information

Funding

The work was supported by the Lendület Programme of the Hungarian Academy of Sciences – grant number LP2021-1/2021, by the Ministry of Innovation and Technology of Hungary – grant number ELTE TKP 2021-NKTA-62, and by Dynasnet European Research Council Synergy project – grant number ERC-2018-SYG 810115.