Poly-time algorithm for L-convex fn minimization

From himtp
Revision as of 13:44, 8 October 2015 by Shioura (Talk | contribs) (Problem Statement)

Jump to: navigation, search

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)


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. We need a polynomial-time algorithm which is much simpler, due to the request from auction theory.