25 citations · 121 across the 26 of their papers we have counts for
27 papers
Consistent Submodular Maximization with Full Foresight
Eric Balkanski, Paul Dütting, Federico Fusco +4
Online algorithms with bounded recourse face three intertwined obstacles: uncertainty about the future, computational limits, and a limited budget for changes. We ask a fundamental…
Profit Maximization in Bilateral Trade against a Smooth Adversary
Simone Di Gregorio, Paul Dütting, Federico Fusco +1
Bilateral trade models the task of intermediating between two strategic agents, a seller and a buyer, who wish to trade a good. We study this problem from the perspective of a prof…
Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade
Simone Di Gregorio, Paul Dütting, Federico Fusco +1
Bilateral trade models the task of intermediating between two strategic agents, a seller and a buyer, willing to trade a good for which they hold private valuations. We study this…
The Cost of Consistency: Submodular Maximization with Constant Recourse
Paul Dütting, Federico Fusco, Silvio Lattanzi +3
In this work, we study online submodular maximization, and how the requirement of maintaining a stable solution impacts the approximation. In particular, we seek bounds on the best…
Selling Joint Ads: A Regret Minimization Perspective
Gagan Aggarwal, Ashwinkumar Badanidiyuru, Paul Dütting +1
Motivated by online retail, we consider the problem of selling one item (e.g., an ad slot) to two non-excludable buyers (say, a merchant and a brand). This problem captures, for ex…
Consistent Submodular Maximization
Paul Dütting, Federico Fusco, Silvio Lattanzi +2
Maximizing monotone submodular functions under cardinality constraints is a classic optimization task with several applications in data mining and machine learning. In this paper w…
The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations
Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni +2
We study the problem of regret minimization for a single bidder in a sequence of first-price auctions where the bidder discovers the item's value only if the auction is won. Our ma…
Bandits with Replenishable Knapsacks: the Best of both Worlds
Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1
The bandits with knapsack (BwK) framework models online decision-making problems in which an agent makes a sequence of decisions subject to resource consumption constraints. The tr…
Fully Dynamic Submodular Maximization over Matroids
Paul Dütting, Federico Fusco, Silvio Lattanzi +2
Maximizing monotone submodular functions under a matroid constraint is a classic algorithmic problem with multiple applications in data mining and machine learning. We study this c…
Fairness in Streaming Submodular Maximization over a Matroid Constraint
Marwa El Halabi, Federico Fusco, Ashkan Norouzi-Fard +2
Streaming submodular maximization is a natural model for the task of selecting a representative subset from a large-scale dataset. If datapoints have sensitive attributes such as g…
Pandora's Problem with Combinatorial Cost
Ben Berger, Tomer Ezra, Michal Feldman +1
Pandora's problem is a fundamental model in economics that studies optimal search strategies under costly inspection. In this paper we initiate the study of Pandora's problem with…
Repeated Bilateral Trade Against a Smoothed Adversary
Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni +2
We study repeated bilateral trade where an adaptive -smooth adversary generates the valuations of sellers and buyers. We provide a complete characterization of the regret regime…
Truthful Matching with Online Items and Offline Agents
Michal Feldman, Federico Fusco, Stefano Leonardi +2
We study truthful mechanisms for welfare maximization in online bipartite matching. In our (multi-parameter) setting, every buyer is associated with a (possibly private) desired se…
Learning on the Edge: Online Learning with Stochastic Feedback Graphs
Emmanuel Esposito, Federico Fusco, Dirk van der Hoeven +1
The framework of feedback graphs is a generalization of sequential decision-making with bandit or full information feedback. In this work, we study an extension where the directed…
An -regret analysis of Adversarial Bilateral Trade
Yossi Azar, Amos Fiat, Federico Fusco
We study sequential bilateral trade where sellers and buyers valuations are completely arbitrary (i.e., determined by an adversary). Sellers and buyers are strategic agents with pr…
Deletion Robust Non-Monotone Submodular Maximization over Matroids
Paul Dütting, Federico Fusco, Silvio Lattanzi +2
Maximizing a submodular function is a fundamental task in machine learning and in this paper we study the deletion robust version of the problem under the classic matroids constrai…
Deletion Robust Submodular Maximization over Matroids
Paul Dütting, Federico Fusco, Silvio Lattanzi +2
Maximizing a monotone submodular function is a fundamental task in machine learning. In this paper, we study the deletion robust version of the problem under the classic matroids c…
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,…
Bilateral Trade: A Regret Minimization Perspective
Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni +2
Bilateral trade, a fundamental topic in economics, models the problem of intermediating between two strategic agents, a seller and a buyer, willing to trade a good for which they h…
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…
Beyond Bandit Feedback in Online Multiclass Classification
Dirk van der Hoeven, Federico Fusco, Nicolò Cesa-Bianchi
We study the problem of online multiclass classification in a setting where the learner's feedback is determined by an arbitrary directed graph. While including bandit feedback as…
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…
A Regret Analysis of Bilateral Trade
Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni +2
Bilateral trade, a fundamental topic in economics, models the problem of intermediating between two strategic agents, a seller and a buyer, willing to trade a good for which they h…
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…