We explore the relationship between two popular concepts on allocating divisible items: competitive equilibrium (CE) and allocations with maximum Nash welfare, i.e., allocations where the weighted geometric mean of the utilities is maximal. When agents have homogeneous concave utility functions, these two concepts coincide: the classical Eisenberg-Gale convex program that maximizes Nash welfare over feasible allocations yields a competitive equilibrium. However, these two concepts diverge for non-homogeneous utilities. From a computational perspective, maximizing Nash welfare amounts to solving a convex program for any concave utility functions, computing CE becomes PPAD-hard already for separable piecewise linear concave (SPLC) utilities.
We introduce the concept of Gale-substitute utility functions, an analogue of the weak gross substitutes (WGS) property for the so-called Gale demand system. For Gale-substitutes utilities, we show that any allocation maximizing Nash welfare provides an approximate-CE with surprisingly strong guarantees, where every agent gets at least half the maximum utility they can get at any CE, and is approximately envy-free. Gale-substitutes include examples of utilities where computing CE is PPAD hard: in particular, all separable concave utilities, and the previously studied non-separable class of Leontief-free utilities. We introduce a new, general class of utility functions called generalized network utilities based on the generalized flow model; this class includes SPLC and Leontief-free utilities. We show that all such utilities are Gale-substitutes. Conversely, although some agents may get much higher utility at a Nash welfare maximizing allocation than at a CE, we show a price of anarchy type result: for general concave utilities, every CE achieves at least $(1/e)^{1/e}>0.69$ fraction of the maximum Nash welfare, and this factor is tight.

Various first order approaches have been proposed in the literature to solve Linear Programming (LP) problems, recently leading to practically efficient solvers for large-scale LPs. We introduce a first order approach for LP optimization with a convergence rate depending polynomially on the circuit imbalance measure, which is a geometric parameter of the constraint matrix, and depending logarithmically on the right hand side, capacity, and cost vectors. This provides much stronger convergence guarantees than the previous known methods. For example, if the constraint matrix is totally unimodular, we obtain polynomial-time algorithms. Our approach is based on a fast gradient method due to Necoara, Nesterov, and Glineur (Math. Prog. 2019); this algorithm is called repeatedly in a framework that gradually fixes variables to the boundary. This technique is based on a new approximate version of Tardos's method, that was used to obtain a strongly polynomial algorithm for combinatorial LPs (Oper. Res. 1986).

We consider ascending auctions for finding Walrasian equilibria in markets with indivisible items and gross substitutes valuation functions. Each price increase step in the auction algorithm requires finding an inclusion-wise minimal maximal overdemanded set at the current prices. This can be formulated as a submodular function minimization problem. We observe that minimizing this submodular function corresponds to a polymatroid sum problem, and using this viewpoint, we give a fast and simple push-relabel algorithm for finding the minimal maximal overdemanded set.

Optimal auction design is a fundamental problem in algorithmic game theory. This problem is notoriously difficult already in very simple settings. Recent work in differentiable economics showed that neural networks can efficiently learn known optimal auction mechanisms and discover interesting new ones. In an attempt to theoretically justify their empirical success, we focus on one of the first such networks, RochetNet, and a generalized version for affine maximizer auctions. We prove that they satisfy mode connectivity, i.e., locally optimal solutions are connected by a simple, piecewise linear path such that every solution on the path is almost as good as one of the two local optima. Mode connectivity has been recently investigated as an intriguing empirical and theoretically justifiable property of neural networks used for prediction problems. Our results give the first such analysis in the context of differentiable economics, where neural networks are used directly for solving non-convex optimization problems.

For any $\varepsilon>0$, we give a simple, deterministic $(6+\varepsilon)$-approximation algorithm for the Nash social welfare (NSW) problem under submodular valuations. We also consider the asymmetric variant of the problem, where the objective is to maximize the weighted geometric mean of agents' valuations, and give an $(\omega + 2 + \varepsilon) e$-approximation if the ratio between the largest weight and the average weight is at most $\omega$.
We also show that the $1/2$-EFX envy-freeness property can be attained simultaneously with a constant-factor approximation. More precisely, we can find an allocation in polynomial time which is both $1/2$-EFX and a $(12+\varepsilon)$-approximation to the symmetric NSW problem under submodular valuations. The previous best approximation factor under $1/2$-EFX was linear in the number of agents.

We consider the minimum-norm-point (MNP) problem over zonotopes, a well-studied problem that encompasses linear programming. Inspired by Wolfe's classical MNP algorithm, we present a general algorithmic framework that performs first order update steps, combined with iterations that aim to `stabilize' the current iterate with additional projections, i.e., finding a locally optimal solution whilst keeping the current tight inequalities. We bound on the number of iterations polynomially in the dimension and in the associated circuit imbalance measure. In particular, the algorithm is strongly polynomial for network flow instances. The conic version of Wolfe's algorithm is a special instantiation of our framework; as a consequence, we obtain convergence bounds for this algorithm. Our preliminary computational experiments show a significant improvement over standard first-order methods.

The correlation gap of a set function measures the ratio between two natural extensions. It has has been identified as the performance guarantee in a range of approximation algorithms and mechanism design settings. It is known that the correlation gap of a monotone submodular function is $1-1/e$, and this is tight even for simple matroid rank functions.
We initiate a fine-grained study of correlation gaps of matroid rank functions. In particular, we present improved lower bounds on the correlation gap as parametrized by the rank and the girth of the matroid. We also show that the worst correlation gap of a weighted matroid rank function is achieved under uniform weights.

We introduce a new polynomial-time path-following interior point method where the number of iterations also admits a combinatorial upper bound $O(2^nn^{1.5}\log n)$ for an $n$-variable linear program in standard form. This complements previous work by Allamigeon, Benchimol, Gaubert, and Joswig (SIAGA 2018) that exhibited a family of instances where any path-following method must take exponentially many iterations. The number of iterations of our algorithm is at most $O(n^{1.5}\log n)$ times the number of segments of any piecewise linear curve in the wide neighborhood of the central path. In particular, it matches the number of iterations of any path following interior point method up to this polynomial factor. The overall exponential upper bound derives from studying the `max central path', a piecewise-linear curve with the number of pieces bounded by the total length of 2n shadow vertex simplex paths.

We study the circuit diameter of polyhedra, introduced by Borgwardt, Finhold, and Hemmecke (SIDMA, 2015) as a relaxation of the combinatorial diameter. We show that the circuit diameter of a system $\{x\in \mathbb{R}^n:\, Ax=b, 0\le x\le u\}$ for $A\in\mathbb{R}^{m\times n}$ is bounded as $O(m^2\log(m+\kappa_A)+n\log n)$, where $\kappa_A$ is the circuit imbalance measure of the constraint matrix. This yields a strongly polynomial circuit diameter bound e.g. if all entries of A have polynomially bounded encoding length in n. Further, we present circuit augmentation algorithms for LPs using the minimum-ratio circuit cancelling rule. Even though the standard minimum-ratio circuit cancelling algorithm is not finite in general, our variant can solve an optimization LP in $O(n^3\log(n+\kappa_A))$ augmentation steps.