Budget-feasible mechanism design for non-monotone submodular objectives: Offline and online

Georgios Amanatidis, Pieter Kleer, Guido Schäfer

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

The framework of budget-feasible mechanism design studies procurement auctions where the auctioneer (buyer) aims to maximize his valuation function subject to a hard budget constraint. We study the problem of designing truthful mechanisms that have good approximation guarantees and never pay the participating agents (sellers) more than the budget. We focus on the case of general (non-monotone) submodular valuation functions and derive the first truthful, budget-feasible and O(1)-approximation mechanisms that run in polynomial time in the value query model, for both offline and online auctions. Since the introduction of the problem by Singer [40], obtaining efficient mechanisms for objectives that go beyond the class of monotone submodular functions has been elusive. Prior to our work, the only O(1)-approximation mechanism known for non-monotone submodular objectives required an exponential number of value queries. At the heart of our approach lies a novel greedy algorithm for non-monotone submodular maximization under a knapsack constraint. Our algorithm builds two candidate solutions simultaneously (to achieve a good approximation), yet ensures that agents cannot jump from one solution to the other (to implicitly enforce truthfulness). Ours is the first mechanism for the problem where-crucially-the agents are not ordered according to their marginal value per cost. This allows us to appropriately adapt these ideas to the online setting as well. To further illustrate the applicability of our approach, we also consider the case where additional feasibility constraints are present, e.g., at most k agents can be selected. We obtain O(p)-approximation mechanisms for both monotone and non-monotone submodular objectives, when the feasible solutions are independent sets of a p-system. With the exception of additive valuation functions, no mechanisms were known for this setting prior to our work. Finally, we provide lower bounds suggesting that, when one cares about non-trivial approximation guarantees in polynomial time, our results are asymptotically best possible.

Original languageEnglish
Title of host publicationACM EC 2019 - Proceedings of the 2019 ACM Conference on Economics and Computation
PublisherAssociation for Computing Machinery, Inc
Pages901-919
Number of pages19
ISBN (Electronic)9781450367929
DOIs
Publication statusPublished - 17 Jun 2019
Event20th ACM Conference on Economics and Computation, EC 2019 - Phoenix, United States
Duration: 24 Jun 201928 Jun 2019

Conference

Conference20th ACM Conference on Economics and Computation, EC 2019
CountryUnited States
CityPhoenix
Period24/06/1928/06/19

Fingerprint

Mechanism Design
Approximation
Valuation
Polynomials
Polynomial time
Query
Online Auctions
Submodular Function
Budget Constraint
Knapsack
Monotone Function
Auctions
Greedy Algorithm
Independent Set
Mechanism design
Exception
Monotone
Jump
Costs
Maximise

Keywords

  • Budget-feasible mechanism design
  • Non-monotone submodular maximization
  • Procurement auctions

Cite this

Amanatidis, G., Kleer, P., & Schäfer, G. (2019). Budget-feasible mechanism design for non-monotone submodular objectives: Offline and online. In ACM EC 2019 - Proceedings of the 2019 ACM Conference on Economics and Computation (pp. 901-919). Association for Computing Machinery, Inc. https://doi.org/10.1145/3328526.3329622
Amanatidis, Georgios ; Kleer, Pieter ; Schäfer, Guido. / Budget-feasible mechanism design for non-monotone submodular objectives : Offline and online. ACM EC 2019 - Proceedings of the 2019 ACM Conference on Economics and Computation. Association for Computing Machinery, Inc, 2019. pp. 901-919
@inproceedings{a065b1963bc64c29b635370de59498db,
title = "Budget-feasible mechanism design for non-monotone submodular objectives: Offline and online",
abstract = "The framework of budget-feasible mechanism design studies procurement auctions where the auctioneer (buyer) aims to maximize his valuation function subject to a hard budget constraint. We study the problem of designing truthful mechanisms that have good approximation guarantees and never pay the participating agents (sellers) more than the budget. We focus on the case of general (non-monotone) submodular valuation functions and derive the first truthful, budget-feasible and O(1)-approximation mechanisms that run in polynomial time in the value query model, for both offline and online auctions. Since the introduction of the problem by Singer [40], obtaining efficient mechanisms for objectives that go beyond the class of monotone submodular functions has been elusive. Prior to our work, the only O(1)-approximation mechanism known for non-monotone submodular objectives required an exponential number of value queries. At the heart of our approach lies a novel greedy algorithm for non-monotone submodular maximization under a knapsack constraint. Our algorithm builds two candidate solutions simultaneously (to achieve a good approximation), yet ensures that agents cannot jump from one solution to the other (to implicitly enforce truthfulness). Ours is the first mechanism for the problem where-crucially-the agents are not ordered according to their marginal value per cost. This allows us to appropriately adapt these ideas to the online setting as well. To further illustrate the applicability of our approach, we also consider the case where additional feasibility constraints are present, e.g., at most k agents can be selected. We obtain O(p)-approximation mechanisms for both monotone and non-monotone submodular objectives, when the feasible solutions are independent sets of a p-system. With the exception of additive valuation functions, no mechanisms were known for this setting prior to our work. Finally, we provide lower bounds suggesting that, when one cares about non-trivial approximation guarantees in polynomial time, our results are asymptotically best possible.",
keywords = "Budget-feasible mechanism design, Non-monotone submodular maximization, Procurement auctions",
author = "Georgios Amanatidis and Pieter Kleer and Guido Sch{\"a}fer",
year = "2019",
month = "6",
day = "17",
doi = "10.1145/3328526.3329622",
language = "English",
pages = "901--919",
booktitle = "ACM EC 2019 - Proceedings of the 2019 ACM Conference on Economics and Computation",
publisher = "Association for Computing Machinery, Inc",

}

Amanatidis, G, Kleer, P & Schäfer, G 2019, Budget-feasible mechanism design for non-monotone submodular objectives: Offline and online. in ACM EC 2019 - Proceedings of the 2019 ACM Conference on Economics and Computation. Association for Computing Machinery, Inc, pp. 901-919, 20th ACM Conference on Economics and Computation, EC 2019, Phoenix, United States, 24/06/19. https://doi.org/10.1145/3328526.3329622

Budget-feasible mechanism design for non-monotone submodular objectives : Offline and online. / Amanatidis, Georgios; Kleer, Pieter; Schäfer, Guido.

ACM EC 2019 - Proceedings of the 2019 ACM Conference on Economics and Computation. Association for Computing Machinery, Inc, 2019. p. 901-919.

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Budget-feasible mechanism design for non-monotone submodular objectives

T2 - Offline and online

AU - Amanatidis, Georgios

AU - Kleer, Pieter

AU - Schäfer, Guido

PY - 2019/6/17

Y1 - 2019/6/17

N2 - The framework of budget-feasible mechanism design studies procurement auctions where the auctioneer (buyer) aims to maximize his valuation function subject to a hard budget constraint. We study the problem of designing truthful mechanisms that have good approximation guarantees and never pay the participating agents (sellers) more than the budget. We focus on the case of general (non-monotone) submodular valuation functions and derive the first truthful, budget-feasible and O(1)-approximation mechanisms that run in polynomial time in the value query model, for both offline and online auctions. Since the introduction of the problem by Singer [40], obtaining efficient mechanisms for objectives that go beyond the class of monotone submodular functions has been elusive. Prior to our work, the only O(1)-approximation mechanism known for non-monotone submodular objectives required an exponential number of value queries. At the heart of our approach lies a novel greedy algorithm for non-monotone submodular maximization under a knapsack constraint. Our algorithm builds two candidate solutions simultaneously (to achieve a good approximation), yet ensures that agents cannot jump from one solution to the other (to implicitly enforce truthfulness). Ours is the first mechanism for the problem where-crucially-the agents are not ordered according to their marginal value per cost. This allows us to appropriately adapt these ideas to the online setting as well. To further illustrate the applicability of our approach, we also consider the case where additional feasibility constraints are present, e.g., at most k agents can be selected. We obtain O(p)-approximation mechanisms for both monotone and non-monotone submodular objectives, when the feasible solutions are independent sets of a p-system. With the exception of additive valuation functions, no mechanisms were known for this setting prior to our work. Finally, we provide lower bounds suggesting that, when one cares about non-trivial approximation guarantees in polynomial time, our results are asymptotically best possible.

AB - The framework of budget-feasible mechanism design studies procurement auctions where the auctioneer (buyer) aims to maximize his valuation function subject to a hard budget constraint. We study the problem of designing truthful mechanisms that have good approximation guarantees and never pay the participating agents (sellers) more than the budget. We focus on the case of general (non-monotone) submodular valuation functions and derive the first truthful, budget-feasible and O(1)-approximation mechanisms that run in polynomial time in the value query model, for both offline and online auctions. Since the introduction of the problem by Singer [40], obtaining efficient mechanisms for objectives that go beyond the class of monotone submodular functions has been elusive. Prior to our work, the only O(1)-approximation mechanism known for non-monotone submodular objectives required an exponential number of value queries. At the heart of our approach lies a novel greedy algorithm for non-monotone submodular maximization under a knapsack constraint. Our algorithm builds two candidate solutions simultaneously (to achieve a good approximation), yet ensures that agents cannot jump from one solution to the other (to implicitly enforce truthfulness). Ours is the first mechanism for the problem where-crucially-the agents are not ordered according to their marginal value per cost. This allows us to appropriately adapt these ideas to the online setting as well. To further illustrate the applicability of our approach, we also consider the case where additional feasibility constraints are present, e.g., at most k agents can be selected. We obtain O(p)-approximation mechanisms for both monotone and non-monotone submodular objectives, when the feasible solutions are independent sets of a p-system. With the exception of additive valuation functions, no mechanisms were known for this setting prior to our work. Finally, we provide lower bounds suggesting that, when one cares about non-trivial approximation guarantees in polynomial time, our results are asymptotically best possible.

KW - Budget-feasible mechanism design

KW - Non-monotone submodular maximization

KW - Procurement auctions

UR - http://www.scopus.com/inward/record.url?scp=85069053229&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85069053229&partnerID=8YFLogxK

U2 - 10.1145/3328526.3329622

DO - 10.1145/3328526.3329622

M3 - Conference contribution

SP - 901

EP - 919

BT - ACM EC 2019 - Proceedings of the 2019 ACM Conference on Economics and Computation

PB - Association for Computing Machinery, Inc

ER -

Amanatidis G, Kleer P, Schäfer G. Budget-feasible mechanism design for non-monotone submodular objectives: Offline and online. In ACM EC 2019 - Proceedings of the 2019 ACM Conference on Economics and Computation. Association for Computing Machinery, Inc. 2019. p. 901-919 https://doi.org/10.1145/3328526.3329622