# Poly-time algorithm for L-convex fn minimization

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

## Problem Statement

Let $g: \mathbb{Z}_+^n \to \R\cup\{+\infty\}$ be an $L^\natural$-convex function, and denote $T=\min\{\|x_*\|_\infty \mid x_* \in {\rm arg} \min g\}.$ Is there a (simple) primal algorithm to find a minimizer of $g$ by using the following oracle at most poly n log T time?

Input of oracle: $p \in \mathbb{Z}^n_+, d \in \{0, + 1\}^n \cup \{0, -1\}$

Output of oracle: the value $g(p+d)-g(p)$

## Comment

This problem is motivated by mutil-item auction. In a multi-item auction with gross-substitutes valuation functions, the problem of finding equilibrium prices can be reduced to the minimization of a certain $L^\natural$-convex function (called Lyapunov function), and the oracle mentioned above can be implemented if each valuation function is given with a demand oracle.

Note that the polynomial-time solvability of the problem mentioned above is already known; for example, we can apply the cutting-plane algorithm of Lee, Sidford, and Wong (2015). We need a polynomial-time algorithm which is much simpler, due to the request from auction theory.