Zobrazeno 1 - 10
of 159
pro vyhledávání: '"Végh, László A."'
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 agen
Externí odkaz:
http://arxiv.org/abs/2402.09994
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. From a theoretical perspective, linear convergence rates have been e
Externí odkaz:
http://arxiv.org/abs/2311.01959
Autor:
Eickhoff, Katharina, Neuwohner, Meike, Peis, Britta, Rieken, Niklas, Koch, Laura Vargas, Végh, László A.
We consider dynamic auctions for finding Walrasian equilibria in markets with indivisible items and strong gross substitutes valuation functions. Each price adjustment step in these auction algorithms requires finding an inclusion-wise minimal maxima
Externí odkaz:
http://arxiv.org/abs/2310.08454
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
Externí odkaz:
http://arxiv.org/abs/2305.11005
For any $\eps>0$, we give a simple, deterministic $(4+\eps)$-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
Externí odkaz:
http://arxiv.org/abs/2211.03883
We consider the minimum-norm-point (MNP) problem over polyhedra, a well-studied problem that encompasses linear programming. We present a general algorithmic framework that combines two fundamental approaches for this problem: active set methods and
Externí odkaz:
http://arxiv.org/abs/2211.02560
A set function can be extended to the unit cube in various ways; the correlation gap measures the ratio between two natural extensions. This quantity has been identified as the performance guarantee in a range of approximation algorithms and mechanis
Externí odkaz:
http://arxiv.org/abs/2209.09896
We develop a new `subspace layered least squares' interior point method (IPM) for solving linear programs. Applied to an $n$-variable linear program in standard form, the iteration complexity of our IPM is up to an $O(n^{1.5} \log n)$ factor upper bo
Externí odkaz:
http://arxiv.org/abs/2206.08810
We study the problem of maximizing Nash welfare (MNW) while allocating indivisible goods to asymmetric agents. The Nash welfare of an allocation is the weighted geometric mean of agents' utilities, and the allocation with maximum Nash welfare is know
Externí odkaz:
http://arxiv.org/abs/2112.10199
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\leq x\leq u\}$ for $A
Externí odkaz:
http://arxiv.org/abs/2111.07913