11 papers
Improved Multi-Dimensional Forecasting for Swap Regret
Joey Rivkin, Ramiro N. Deo-Campo Vuong, Robert Kleinberg +3
We study the problem of forecasting for an arbitrary number of downstream agents with unknown objectives, each of whom best responds to the forecaster's predictions. We seek a sing…
Price of Anarchy of Algorithmic Monoculture
Robert Kleinberg, Erald Sinanaj, Ãva Tardos
Several recent works investigate the effects of monoculture, the ever increasing phenomenon of (possibly) self-interested actors in a society relying on one common source of advice…
Oracle-efficient Hybrid Learning with Constrained Adversaries
Princewill Okoroafor, Robert Kleinberg, Michael P. Kim
The Hybrid Online Learning Problem, where features are drawn i.i.d. from an unknown distribution but labels are generated adversarially, is a well-motivated setting positioned betw…
The Keychain Problem: On Minimizing the Opportunity Cost of Uncertainty
Ramiro N. Deo-Campo Vuong, Robert Kleinberg, Aditya Prasad +2
In this paper, we introduce a family of sequential decision-making problems, collectively termed the Keychain Problem, that involve exploring a set of actions to maximize expected…
Near-Optimal Algorithms for Omniprediction
Princewill Okoroafor, Robert Kleinberg, Michael P. Kim
Omnipredictors are simple prediction functions that encode loss-minimizing predictions with respect to a hypothesis class , simultaneously for every loss function within a class…
Universal Connection Schedules for Reconfigurable Networking
Shaleen Baral, Robert Kleinberg, Sylvan Martin +3
Reconfigurable networks are a novel communication paradigm in which the pattern of connectivity between hosts varies rapidly over time. Prior theoretical work explored the inherent…