Home

Brendan Lucier

  1. On the efficiency of equilibria in generalized second price auctions.

    Wed, 02/01/2012 - 15:01 — SomNambul
    Authors: Brendan Lucier, Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos, Maria Kyropoulou, Renato Paes Leme, Éva Tardos
    Subjects: Computer Science and Game Theory
    Abstract

    The Generalized Second Price (GSP) auction is the primary auction used for
    monetizing the use of the Internet. It is well-known that truthtelling is not a
    dominant strategy in this auction and that inefficient equilibria can arise. In
    this paper we study the space of equilibria in GSP, and quantify the efficiency
    loss that can arise in equilibria under a wide range of sources of uncertainty,
    as well as in the full information setting. The traditional Bayesian game
    models uncertainty in the valuations (types) of the participants.

  2. Beyond Equilibria: Mechanisms for Repeated Combinatorial Auctions.

    Thu, 10/01/2009 - 20:55 — SomNambul
    Authors: Brendan Lucier
    Subjects: Computer Science and Game Theory
    Abstract

    We study the design of mechanisms in combinatorial auction domains. We focus
    on settings where the auction is repeated, motivated by auctions for licenses
    or advertising space. We consider models of agent behaviour in which they
    either apply common learning techniques to minimize the regret of their bidding
    strategies, or apply short-sighted best-response strategies. We ask: when can a
    black-box approximation algorithm for the base auction problem be converted
    into a mechanism that approximately preserves the original algorithm's
    approximation factor on average over many iterations?

  3. Bayesian Algorithmic Mechanism Design.

    Mon, 09/28/2009 - 15:24 — SomNambul
    Authors: Brendan Lucier, Jason D. Hartline
    Subjects: Computer Science and Game Theory
    Abstract

    The principal problem in algorithmic mechanism design is in merging the
    incentive constraints imposed by selfish behavior with the algorithmic
    constraints imposed by computational intractability.

  4. Price of Anarchy for Greedy Auctions.

    Mon, 09/07/2009 - 22:13 — SomNambul
    Authors: Brendan Lucier, Allan Borodin
    Subjects: Computer Science and Game Theory
    Abstract

    We consider mechanisms for utilitarian combinatorial allocation problems,
    where agents are not assumed to be single-minded. This class of problems
    includes combinatorial auctions, multi-unit auctions, unsplittable flow
    problems, profit-maximizing scheduling, and others. We study the price of
    anarchy for such mechanisms, which is a bound on the approximation ratio
    obtained at any mixed Nash equilibrium. We demonstrate that a broad class of
    greedy approximation algorithms can be implemented as mechanisms for which the
    price of anarchy nearly matches the performance of the original algorithm.

Math-arch

Syndicate content