Consider optimization problems of the following form. Let $f(x)$ be a polynomial-time computable function that maps a string $x$ into a rational number. The optimization problem is this: what is the maximum value of $f(x)$ over $n$-bit strings $x$?
Let us say that such a problem has a minimax characterization, if there is another polynomial-time computable function $g$, such that $$\max_x f(x) = \min_y g(y)$$ holds. Here $x$ runs over all $n$-bit strings, and $y$ runs over all $m$-bit strings; $n$ and $m$ may be different, but they are polynomially related.
Numerous natural and important optimization problems have such minimax characterization. A few examples (the theorems on which the characterizations are based shown in parenthesis):
Linear Programming (LP Duality Thm), Maximum Flow (Max Flow Min Cut Thm), Max Bipartite Matching (Konig-Hall Thm), Max Non-Bipartite Matching (Tutte's Thm, Tutte-Berge formula), Max Disjoint Arborescences in directed graph (Edmond's Disjoint Branching Thm), Max Spanning Tree Packing in undirected graph (Tutte's Tree Packing Thm), Min Covering by Forests (Nash-Williams Thm), Max Directed Cut Packing (Lucchesi-Younger Thm), Max 2-Matroid Intersection (Matroid Intersection Thm), Max Disjoint Paths (Menger's Thm), Max Antichain in Partially Ordered Set (Dilworth Thm), and many others.
In all these examples, a polynomial-time algorithm is also available to find the optimum. My question:
Is there any optimization problem with a minimax characterization, for which no polynomial-time algorithm has been found so far?
Note: Linear Programming was in this status for about 30 years!