Christodoulos Santorinaios

Georgios Amanatidis, Evangelos Markakis, Christodoulos Santorinaios et al.

Augmenting the input of algorithms with predictions is an algorithm design paradigm that suggests leveraging a (possibly erroneous) prediction to improve worst-case performance guarantees when the prediction is perfect (consistency), while also providing a performance guarantee when the prediction fails (robustness). Recently, Xu and Lu [2022] and Agrawal et al. [2024] proposed to consider settings with strategic agents under this framework. In this paper, we initiate the study of budget-feasible mechanism design with predictions. These mechanisms model a procurement auction scenario in which an auctioneer (buyer) with a strict budget constraint seeks to purchase goods or services from a set of strategic agents, so as to maximize her own valuation function. We focus on the online version of the problem where the arrival order of agents is random. We design mechanisms that are truthful, budget-feasible, and achieve a significantly improved competitive ratio for both monotone and non-monotone submodular valuation functions compared to their state-of-the-art counterparts without predictions. Our results assume access to a prediction for the value of the optimal solution to the offline problem. We complement our positive results by showing that for the offline version of the problem, access to predictions is mostly ineffective in improving approximation guarantees.

Evangelos Markakis, Christodoulos Santorinaios

Our work revolves around Fictitious Play, one of the first iterative methods that is known to converge to a Nash equilibrium in zero-sum games. In recent years, there has been a revived interest, due to applications in various machine learning problems, which has motivated a line of work on its convergence properties and on proposing new variants of the initial algorithm. Our paper is along this direction and introduces one new variant, which we refer to as Almost Greedy Fictitious Play. The proposed algorithm greedily attempts to find the optimal stepsize at each iteration but its search space is constrained and includes almost all the line between the cumulative mixed strategy and the current best response. Our main result is that the method achieves an instance dependent convergence rate of $\mathcal{O}(1/T)$ with respect to the duality gap. This matches the rate of Continuous Fictitious Play, and offers an alternative to discretization. We complement our theoretical findings with experiments that demonstrate the effectiveness of the method.