69 citations · 423 across the 56 of their papers we have counts for
7 papers · 1 filter
Ironing in the Dark
Tim Roughgarden, Okke Schrijvers
This paper presents the first polynomial-time algorithm for position and matroid auction environments that learns, from samples from an unknown bounded valuation distribution, an a…
A PAC Approach to Application-Specific Algorithm Selection
Rishi Gupta, Tim Roughgarden
The best algorithm for a computational problem generally depends on the "relevant inputs," a concept that depends on the application domain and often defies formal articulation. Wh…
Communication Complexity (for Algorithm Designers)
Tim Roughgarden
This document collects the lecture notes from my course "Communication Complexity (for Algorithm Designers),'' taught at Stanford in the winter quarter of 2015. The two primary goa…
The Pseudo-Dimension of Near-Optimal Auctions
Jamie Morgenstern, Tim Roughgarden
This paper develops a general approach, rooted in statistical learning theory, to learning an approximately revenue-maximizing auction from data. We introduce -level auctions to…
Public projects, Boolean functions and the borders of Border's theorem
Parikshit Gopalan, Noam Nisan, Tim Roughgarden
Border's theorem gives an intuitive linear characterization of the feasible interim allocation rules of a Bayesian single-item environment, and it has several applications in econo…
The Price of Anarchy in Large Games
Michal Feldman, Nicole Immorlica, Brendan Lucier +2
Game-theoretic models relevant for computer science applications usually feature a large number of players. The goal of this paper is to develop an analytical framework for boundin…