Combinatorial Auctions without Money

Dimitris Fotakis, Piotr Krysta, Carmine Ventre

    Research output: Contribution to journalArticleResearchpeer-review

    14 Downloads (Pure)

    Abstract

    Algorithmic Mechanism Design attempts to marry computation and incentives, mainly by leveraging monetary transfers between designer and selfish agents involved. This is principally because in absence of money, very little can be done to enforce truthfulness. However, in certain applications, money is unavailable, morally unacceptable or might simply be at odds with the objective of the mechanism. For example, in Combinatorial Auctions (CAs), the paradigmatic problem of the area, we aim at solutions of maximum social welfare but still charge the society to ensure truthfulness. Additionally, truthfulness of CAs is poorly understood already in the case in which bidders happen to be interested in only two different sets of goods. We focus on the design of incentive-compatible CAs without money in the general setting of k- minded bidders. We trade monetary transfers with the observation that the mechanism can detect certain lies of the bidders: i.e., we study truthful CAs with verification and without money. We prove a characterization of truthful mechanisms, which makes an interesting parallel with the well-understood case of CAs with money for single-minded bidders. We then give a host of upper bounds on the approximation ratio obtained by either deterministic or randomized truthful mechanisms when the sets and valuations are private knowledge of the bidders. (Most of these mechanisms run in polynomial time and return solutions with (nearly) best possible approximation guarantees.) We complement these positive results with a number of lower bounds (some of which are essentially tight) that hold in the easier case of public sets. We thus provide an almost complete picture of truthfully approximating CAs in this general setting with multi-dimensional bidders.
    Original languageEnglish
    Pages (from-to)756-785
    JournalAlgorithmica
    Volume77
    Issue number3
    DOIs
    Publication statusPublished - 29 Dec 2015

    Fingerprint

    Combinatorial Auctions
    Incentives
    Polynomials
    Algorithmic Mechanism Design
    Odds
    Welfare
    Best Approximation
    Polynomial time
    Complement
    Charge
    Money
    Lower bound
    Upper bound

    Cite this

    Fotakis, D., Krysta, P., & Ventre, C. (2015). Combinatorial Auctions without Money. Algorithmica, 77(3), 756-785. https://doi.org/10.1007/s00453-015-0105-8
    Fotakis, Dimitris ; Krysta, Piotr ; Ventre, Carmine. / Combinatorial Auctions without Money. In: Algorithmica. 2015 ; Vol. 77, No. 3. pp. 756-785.
    @article{3845b1a70bcf46f9b3391caa41a640c9,
    title = "Combinatorial Auctions without Money",
    abstract = "Algorithmic Mechanism Design attempts to marry computation and incentives, mainly by leveraging monetary transfers between designer and selfish agents involved. This is principally because in absence of money, very little can be done to enforce truthfulness. However, in certain applications, money is unavailable, morally unacceptable or might simply be at odds with the objective of the mechanism. For example, in Combinatorial Auctions (CAs), the paradigmatic problem of the area, we aim at solutions of maximum social welfare but still charge the society to ensure truthfulness. Additionally, truthfulness of CAs is poorly understood already in the case in which bidders happen to be interested in only two different sets of goods. We focus on the design of incentive-compatible CAs without money in the general setting of k- minded bidders. We trade monetary transfers with the observation that the mechanism can detect certain lies of the bidders: i.e., we study truthful CAs with verification and without money. We prove a characterization of truthful mechanisms, which makes an interesting parallel with the well-understood case of CAs with money for single-minded bidders. We then give a host of upper bounds on the approximation ratio obtained by either deterministic or randomized truthful mechanisms when the sets and valuations are private knowledge of the bidders. (Most of these mechanisms run in polynomial time and return solutions with (nearly) best possible approximation guarantees.) We complement these positive results with a number of lower bounds (some of which are essentially tight) that hold in the easier case of public sets. We thus provide an almost complete picture of truthfully approximating CAs in this general setting with multi-dimensional bidders.",
    author = "Dimitris Fotakis and Piotr Krysta and Carmine Ventre",
    year = "2015",
    month = "12",
    day = "29",
    doi = "10.1007/s00453-015-0105-8",
    language = "English",
    volume = "77",
    pages = "756--785",
    journal = "Algorithmica",
    issn = "0178-4617",
    publisher = "Springer New York",
    number = "3",

    }

    Fotakis, D, Krysta, P & Ventre, C 2015, 'Combinatorial Auctions without Money', Algorithmica, vol. 77, no. 3, pp. 756-785. https://doi.org/10.1007/s00453-015-0105-8

    Combinatorial Auctions without Money. / Fotakis, Dimitris; Krysta, Piotr; Ventre, Carmine.

    In: Algorithmica, Vol. 77, No. 3, 29.12.2015, p. 756-785.

    Research output: Contribution to journalArticleResearchpeer-review

    TY - JOUR

    T1 - Combinatorial Auctions without Money

    AU - Fotakis, Dimitris

    AU - Krysta, Piotr

    AU - Ventre, Carmine

    PY - 2015/12/29

    Y1 - 2015/12/29

    N2 - Algorithmic Mechanism Design attempts to marry computation and incentives, mainly by leveraging monetary transfers between designer and selfish agents involved. This is principally because in absence of money, very little can be done to enforce truthfulness. However, in certain applications, money is unavailable, morally unacceptable or might simply be at odds with the objective of the mechanism. For example, in Combinatorial Auctions (CAs), the paradigmatic problem of the area, we aim at solutions of maximum social welfare but still charge the society to ensure truthfulness. Additionally, truthfulness of CAs is poorly understood already in the case in which bidders happen to be interested in only two different sets of goods. We focus on the design of incentive-compatible CAs without money in the general setting of k- minded bidders. We trade monetary transfers with the observation that the mechanism can detect certain lies of the bidders: i.e., we study truthful CAs with verification and without money. We prove a characterization of truthful mechanisms, which makes an interesting parallel with the well-understood case of CAs with money for single-minded bidders. We then give a host of upper bounds on the approximation ratio obtained by either deterministic or randomized truthful mechanisms when the sets and valuations are private knowledge of the bidders. (Most of these mechanisms run in polynomial time and return solutions with (nearly) best possible approximation guarantees.) We complement these positive results with a number of lower bounds (some of which are essentially tight) that hold in the easier case of public sets. We thus provide an almost complete picture of truthfully approximating CAs in this general setting with multi-dimensional bidders.

    AB - Algorithmic Mechanism Design attempts to marry computation and incentives, mainly by leveraging monetary transfers between designer and selfish agents involved. This is principally because in absence of money, very little can be done to enforce truthfulness. However, in certain applications, money is unavailable, morally unacceptable or might simply be at odds with the objective of the mechanism. For example, in Combinatorial Auctions (CAs), the paradigmatic problem of the area, we aim at solutions of maximum social welfare but still charge the society to ensure truthfulness. Additionally, truthfulness of CAs is poorly understood already in the case in which bidders happen to be interested in only two different sets of goods. We focus on the design of incentive-compatible CAs without money in the general setting of k- minded bidders. We trade monetary transfers with the observation that the mechanism can detect certain lies of the bidders: i.e., we study truthful CAs with verification and without money. We prove a characterization of truthful mechanisms, which makes an interesting parallel with the well-understood case of CAs with money for single-minded bidders. We then give a host of upper bounds on the approximation ratio obtained by either deterministic or randomized truthful mechanisms when the sets and valuations are private knowledge of the bidders. (Most of these mechanisms run in polynomial time and return solutions with (nearly) best possible approximation guarantees.) We complement these positive results with a number of lower bounds (some of which are essentially tight) that hold in the easier case of public sets. We thus provide an almost complete picture of truthfully approximating CAs in this general setting with multi-dimensional bidders.

    U2 - 10.1007/s00453-015-0105-8

    DO - 10.1007/s00453-015-0105-8

    M3 - Article

    VL - 77

    SP - 756

    EP - 785

    JO - Algorithmica

    JF - Algorithmica

    SN - 0178-4617

    IS - 3

    ER -

    Fotakis D, Krysta P, Ventre C. Combinatorial Auctions without Money. Algorithmica. 2015 Dec 29;77(3):756-785. https://doi.org/10.1007/s00453-015-0105-8