Accueil

Tim Roughgarden

  1. Combinatorial Auctions with Restricted Complements.

    Mon, 05/21/2012 - 15:01 — SomNambul
    Authors: Moshe Babaioff, Tim Roughgarden, Shaddin Dughmi, Ittai Abraham
    Subjects: Computer Science and Game Theory
    Abstract

    Complements between goods - where one good takes on added value in the
    presence of another - have been a thorn in the side of algorithmic mechanism
    designers. On the one hand, complements are common in the standard motivating
    applications for combinatorial auctions, like spectrum license auctions. On the
    other, welfare maximization in the presence of complements is notoriously
    difficult, and this intractability has stymied theoretical progress in the
    area.

  2. The Median Mechanism: Interactive and Efficient Privacy with Multiple Queries.

    Wed, 11/11/2009 - 16:01 — SomNambul
    Authors: Aaron Roth, Tim Roughgarden
    Subjects: Cryptography and Security
    Abstract

    We define a new interactive differentially private mechanism -- the median
    mechanism -- for answering arbitrary predicate queries that arrive online.
    Relative to fixed accuracy and privacy constraints, this mechanism can answer
    exponentially more queries than the previously best known interactive privacy
    mechanism (the Laplace mechanism, which independently perturbs each query
    result). Our guarantee is almost the best possible, even for non-interactive
    privacy mechanisms.

Math-arch

Syndicate content