Home

Amos Fiat

  1. Combinatorial Auctions with Budgets.

    Wed, 04/21/2010 - 15:02 — SomNambul
    Authors: Amos Fiat, Jared Saia, Piotr Sankowski, Stefano Leonardi
    Subjects: Computer Science and Game Theory
    Abstract

    We consider budget constrained combinatorial auctions where bidder $i$ has a
    private value $v_i$, a budget $b_i$, and is interested in all the items in
    $S_i$. The value to agent $i$ of a set of items $R$ is $|R \cap S_i| \cdot
    v_i$. Such auctions capture adword auctions, where advertisers offer a bid for
    ads in response to an advertiser-dependent set of adwords, and advertisers have
    budgets. It is known that even of all items are identical and all budgets are
    public it is not possible to be truthful and efficient.

  2. On the Interplay between Incentive Compatibility and Envy Freeness.

    Tue, 03/30/2010 - 15:02 — SomNambul
    Authors: Edith Cohen, Michal Feldman, Amos Fiat, Haim Kaplan, Svetlana Olonetsky
    Subjects: Computer Science and Game Theory
    Abstract

    We study mechanisms for an allocation of goods among agents, where agents
    have no incentive to lie about their true values (incentive compatible) and for
    which no agent will seek to exchange outcomes with another (envy-free).
    Mechanisms satisfying each requirement separately have been studied
    extensively, but there are few results on mechanisms achieving both.

  3. Truth and Envy in Capacitated Allocation Games.

    Tue, 03/30/2010 - 15:02 — SomNambul
    Authors: Edith Cohen, Michal Feldman, Amos Fiat, Haim Kaplan, Svetlana Olonetsky
    Subjects: Computer Science and Game Theory
    Abstract

    We study auctions with additive valuations where agents have a limit on the
    number of items they may receive. We refer to this setting as {\em capacitated
    allocation games.} We seek truthful and envy free mechanisms that maximize the
    social welfare. {\sl I.e.}, where agents have no incentive to lie and no agent
    seeks to exchange outcomes with another. In 1983, Leonard showed that VCG with
    Clarke Pivot payments (which is known to be truthful, individually rational,
    and have no positive transfers), is also an envy free mechanism for the special
    case of $n$ items and $n$ unit capacity agents.

  4. Envy-Free Makespan Approximation.

    Tue, 09/08/2009 - 12:16 — SomNambul
    Authors: Edith Cohen, Michal Feldman, Amos Fiat, Haim Kaplan, Svetlana Olonetsky
    Subjects: Computer Science and Game Theory
    Abstract

    We study envy-free mechanisms for scheduling tasks on unrelated machines
    (agents) that approximately minimize the makespan. For indivisible tasks, we
    put forward an envy-free poly-time mechanism that approximates the minimal
    makespan to within a factor of $O(\log m)$, where $m$ is the number of
    machines. We also show a lower bound of $\Omega(\log m / \log\log m)$. This
    improves the recent result of Hartline {\sl et al.} \cite{Ahuva:2008} who give
    an upper bound of $(m+1)/2$, and a lower bound of $2-1/m$.

Math-arch

Syndicate content