4 papers
A Nearly Tight Lower Bound for Matroid Intersection Prophet Inequalities
Dimitris Fotakis, Charalampos Platanos, Thanos Tolias
We study prophet inequalities under intersections of partition matroids, where an online algorithm irrevocably selects elements with independent nonnegative values drawn from k…
The Knapsack Secretary Problem is Strictly Harder Than the Secretary Problem
Eric Balkanski, Jason Chatzitheodorou, Dimitris Fotakis +1
The knapsack secretary problem is a generalization of the classical secretary problem where the accepted items must satisfy a knapsack constraint. A line of work has developed cons…
A Unified Framework for Uniform-Price Resource Allocation Mechanisms
Ioannis Caragiannis, Dimitris Fotakis, Stratis Skoulakis
Mechanisms for allocating a divisible resource among strategic agents have been widely studied. The prominent paradigm is the proportional (Kelly) mechanism, which elicits a scalar…
Repeated Descent: A Framework for Online Budget-Feasible Auctions
Andreas Charalampopoulos, Dimitris Fotakis, Thanos Tolias
We study budget feasible procurement auctions, in which agents, each with a privately held service cost, offer their services to an employer. The employer seeks to maximize a p…