AOArgyris Oikonomou

Argyris Oikonomou

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Argyris Oikonomou has a total of 5 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Tight Last-Iterate Convergence of the Extragradient and the Optimistic Gradient Descent-Ascent Algorithm for Constrained Monotone Variational Inequalities

    by Yang Cai, Argyris Oikonomou, Weiqiang Zheng

    The monotone variational inequality is a central problem in mathematical programming that unifies and generalizes many important settings such as smooth convex optimization, two-player zero-sum games, convex-concave saddle point problems, etc. The extragradient algorithm by Korpelevich [1976] and the optimistic gradient descent-ascent algorithm by Popov [1980] are arguably the two most classical and popular methods for solving monotone variational inequalities. Despite their long histories, the following major problem remains open. What is the last-iterate convergence rate of the extragradient algorithm or the optimistic gradient descent-ascent algorithm for monotone and Lipschitz variational inequalities with constraints? We resolve this open problem by showing that both the extragradient algorithm and the optimistic gradient descent-ascent algorithm have a tight $O\left(\frac{1}{\sqrt{T}}\right)$ last-iterate convergence rate for arbitrary convex feasible sets, which matches the lower bound by Golowich et al. [2020a,b]. Our rate is measured in terms of the standard gap function. At the core of our results lies a non-standard performance measure -- the tangent residual, which can be viewed as an adaptation of the norm of the operator that takes the local constraints into account. We use the tangent residual (or a slight variation of the tangent residual) as the the potential function in our analysis of the extragradient algorithm (or the optimistic gradient descent-ascent algorithm) and prove that it is non-increasing between two consecutive iterates.

  • Open Access

    Computing Simple Mechanisms: Lift-and-Round over Marginal Reduced Forms

    by Yang Cai, Argyris Oikonomou, Mingfei Zhao

    We study revenue maximization in multi-item multi-bidder auctions under the natural item-independence assumption - a classical problem in Multi-Dimensional Bayesian Mechanism Design. One of the biggest challenges in this area is developing algorithms to compute (approximately) optimal mechanisms that are not brute-force in the size of the bidder type space, which is usually exponential in the number of items in multi-item auctions. Unfortunately, such algorithms were only known for basic settings of our problem when bidders have unit-demand [CHMS10,CMS15] or additive valuations [Yao15]. In this paper, we significantly improve the previous results and design the first algorithm that runs in time polynomial in the number of items and the number of bidders to compute mechanisms that are $O(1)$-approximations to the optimal revenue when bidders have XOS valuations, resolving an open problem raised in [CM16,CZ17]. Moreover, the computed mechanism has a simple structure: It is either a posted price mechanism or a two-part tariff mechanism. As a corollary of our result, we show how to compute an approximately optimal and simple mechanism efficiently using only sample access to the bidders' value distributions. Our algorithm builds on two innovations that allow us to search over the space of mechanisms efficiently: (i) a new type of succinct representation of mechanisms - the marginal reduced forms, and (ii) a novel Lift-and-Round procedure that concavifies the problem.

  • Open Access

    An Efficient $\varepsilon$-BIC to BIC Transformation and Its Application to Black-Box Reduction in Revenue Maximization

    by Yang Cai, Argyris Oikonomou, Grigoris Velegkas, Mingfei Zhao

    We consider the black-box reduction from multi-dimensional revenue maximization to virtual welfare maximization. Cai et al. show a polynomial-time approximation-preserving reduction, however, the mechanism produced by their reduction is only approximately Bayesian incentive compatible ($\varepsilon$-BIC). We provide two new polynomial time transformations that convert any $\varepsilon$-BIC mechanism to an exactly BIC mechanism with only a negligible revenue loss. Our first transformation applies to any mechanism design setting with downward-closed outcome space and only requires sample access to the agents' type distributions. Our second transformation applies to the fully general outcome space, removing the downward-closed assumption, but requires full access to the agents' type distributions. Both transformations only require query access to the original $\varepsilon$-BIC mechanism. Other $\varepsilon$-BIC to BIC transformations for revenue exist in the literature but all require exponential time to run in both of the settings we consider. As an application of our transformations, we improve the reduction by Cai et al. to generate an exactly BIC mechanism.