25 citations · 124 across the 24 of their papers we have counts for
6 papers · 1 filter
Single-Sample Prophet Inequalities via Greedy-Ordered Selection
Constantine Caramanis, Paul Dütting, Matthew Faw +6
We study single-sample prophet inequalities (SSPIs), i.e., prophet inequalities where only a single sample from each prior distribution is available. Besides a direct, and optimal,…
Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness
Georgios Amanatidis, Georgios Birmpas, Federico Fusco +3
We consider the problem of fairly allocating a set of indivisible goods to a set of strategic agents with additive valuation functions. We assume no monetary transfers and, therefo…
Prophet Inequalities for Matching with a Single Sample
Paul Dütting, Federico Fusco, Philip Lazos +2
We consider the prophet inequality problem for (not necessarily bipartite) matching problems with independent edge values, under both edge arrivals and vertex arrivals. We show con…
On the Complexity of Equilibrium Computation in First-Price Auctions
Aris Filos-Ratsikas, Yiannis Giannakopoulos, Alexandros Hollender +2
We consider the problem of computing a (pure) Bayes-Nash equilibrium in the first-price auction with continuous value distributions and discrete bidding space. We prove that when b…
RPPLNS: Pay-per-last-N-shares with a Randomised Twist
Philip Lazos, Francisco J. Marmolejo-Cossío, Xinyu Zhou +1
"Pay-per-last--shares" (PPLNS) is one of the most common payout strategies used by mining pools in Proof-of-Work (PoW) cryptocurrencies. As with any payment scheme, it is impera…
Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity
Georgios Amanatidis, Federico Fusco, Philip Lazos +3
Submodular maximization is a classic algorithmic problem with multiple applications in data mining and machine learning; there, the growing need to deal with massive instances moti…