7 papers
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…
Autobidding Equilibria in Sponsored Shopping
Paul Dütting, Yuhao Li, Renato Paes Leme +2
As commerce shifts to digital marketplaces, platforms increasingly monetize traffic through Sponsored Shopping auctions. Unlike classic ``Sponsored Search", where an advertiser typ…
When Contracts Get Complex: Information-Theoretic Barriers
Paul Dütting, Michal Feldman, Yoav Gal-Tzur +1
In the combinatorial-action contract model (Dütting et al., FOCS'21) a principal delegates the execution of a complex project to an agent, who can choose any subset from a given s…
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…
Approximate Optimality of Linear Contracts Under Uncertainty
Tal Alon, Paul Dütting, Yingkai Li +1
We consider a hidden-action principal-agent model, in which actions require different amounts of effort, and the agent privately knows his ability that determines his cost of effor…
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…