28 citations · 127 across the 46 of their papers we have counts for
9 papers · 1 filter
CLS Hardness of 2D Min-Max Optimization with Product Constraints
Alkis Kalavasis, Panagiotis Patsilinakos, Stratis Skoulakis +1
We study the complexity of computing approximate first-order Nash equilibria in min-max optimization problems with one dimensional min and max players and product constraints. For…
Restoring Incentive Compatibility in Two-Stage Energy Markets with Prosumers
Nikolas Koumpis, Koushik Kar, Leandros Tassiulas +1
A central challenge in modern energy market design is the formulation of a strategy-proof imbalance settlement layer that secures both the economic efficiency of the institution an…
Fixed Point Computation: Beating Brute Force with Smoothed Analysis
Idan Attias, Yuval Dagan, Constantinos Daskalakis +2
We propose a new algorithm that finds an -approximate fixed point of a smooth function from the -dimensional unit ball to itself. We use the general framew…
Imperfect-Recall Games: Equilibrium Concepts and Their Complexity
Emanuel Tewolde, Brian Hu Zhang, Caspar Oesterheld +4
We investigate optimal decision making under imperfect recall, that is, when an agent forgets information it once held before. An example is the absentminded driver game, as well a…
On the Complexity of Computing Sparse Equilibria and Lower Bounds for No-Regret Learning in Games
Ioannis Anagnostides, Alkis Kalavasis, Tuomas Sandholm +1
Characterizing the performance of no-regret dynamics in multi-player games is a foundational problem at the interface of online learning and game theory. Recent results have reveal…
Algorithmic Contract Design for Crowdsourced Ranking
Kiriaki Frangias, Andrew Lin, Ellen Vitercik +1
Ranking is fundamental to many areas, such as search engine optimization, human feedback for language models, as well as peer grading. Crowdsourcing, which is often used for these…
Estimation of Standard Auction Models
Yeshwanth Cherapanamjeri, Constantinos Daskalakis, Andrew Ilyas +1
We provide efficient estimation methods for first- and second-price auctions under independent (asymmetric) private values and partial observability. Given a finite set of observat…
Robust Learning of Optimal Auctions
Wenshuo Guo, Michael I. Jordan, Manolis Zampetakis
We study the problem of learning revenue-optimal multi-bidder auctions from samples when the samples of bidders' valuations can be adversarially corrupted or drawn from distributio…
Certified Computation from Unreliable Datasets
Themis Gouleakis, Christos Tzamos, Manolis Zampetakis
A wide range of learning tasks require human input in labeling massive data. The collected data though are usually low quality and contain inaccuracies and errors. As a result, mod…