Home

Sayan Bhattacharya

  1. Budget Constrained Auctions with Heterogeneous Items.

    Wed, 10/07/2009 - 12:26 — SomNambul
    Authors: Sayan Bhattacharya, Gagan Goel, Sreenivas Gollapudi, Kamesh Munagala
    Subjects: Computer Science and Game Theory
    Abstract

    In this paper, we present the first approximation algorithms for the
    celebrated problem of designing revenue optimal Bayesian incentive compatible
    auctions when there are multiple (heterogeneous) items and when bidders can
    have arbitrary demand and budget constraints. Our mechanisms are surprisingly
    simple: We show that a sequential all-pay mechanism is a 4 approximation to the
    revenue of the optimal ex-interim truthful mechanism with discrete correlated
    type space for each bidder.

  2. On Necessary and Sufficient Number of Cops in the Game of Cops and Robber in Multidimensional Grids.

    Wed, 09/09/2009 - 22:08 — SomNambul
    Authors: Sayan Bhattacharya, Goutam Paul, Swagato Sanyal
    Subjects: Discrete Mathematics
    Abstract

    We theoretically analyze the Cops and Robber Game for the first time in a
    multidimensional grid. It is shown that for an $n$-dimensional grid, at least
    $n$ cops are necessary to ensure capture of the robber. We also present a set
    of cop strategies for which $n$ cops are provably sufficient to catch the
    robber. Further, for two-dimensional grid, we provide an efficient cop strategy
    for which the robber is caught even by a single cop under certain conditions.

Math-arch

Syndicate content