8 papers
Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems
Evripidis Bampis, Bruno Escoffier, Dimitris Fotakis +2
We consider a learning-augmented framework for NP-hard permutation problems. The algorithm has access to predictions telling, given a pair of elements, whether is before…
A Competitive Posted-Price Mechanism for Online Budget-Feasible Auctions
Andreas Charalampopoulos, Dimitris Fotakis, Panagiotis Patsilinakos +1
We consider online procurement auctions, where the agents arrive sequentially, in random order, and have private costs for their services. The buyer aims to maximize a monotone sub…
On the Distortion of Committee Election with 1-Euclidean Preferences and Few Distance Queries
Dimitris Fotakis, Laurent Gourvès, Panagiotis Patsilinakos
We consider committee election of (out of ) candidates, where the voters and the candidates are associated with locations on the real line. Each voter's card…
Sampling and Optimal Preference Elicitation in Simple Mechanisms
Ioannis Anagnostides, Dimitris Fotakis, Panagiotis Patsilinakos
In this work we are concerned with the design of efficient mechanisms while eliciting limited information from the agents. First, we study the performance of sampling approximation…
Dimensionality, Coordination, and Robustness in Voting
Ioannis Anagnostides, Dimitris Fotakis, Panagiotis Patsilinakos
We study the performance of voting mechanisms from a utilitarian standpoint, under the recently introduced framework of metric-distortion, offering new insights along three main li…
Metric-Distortion Bounds under Limited Information
Ioannis Anagnostides, Dimitris Fotakis, Panagiotis Patsilinakos
In this work we study the metric distortion problem in voting theory under a limited amount of ordinal information. Our primary contribution is threefold. First, we consider mechan…