Randomized Pricing with Deferred Acceptance for Revenue Maximization with Submodular Objectives
Open Access
- 30 April 2023
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 3530-3540
Abstract
A lot of applications in web economics need to maximize the revenue under a budget for payments and also guarantee the truthfulness of users, so Budget-Feasible Mechanism (BFM) Design has aroused great interests during last decade. Most of the existing BFMs concentrate on maximizing a monotone submodular function subject to a knapsack constraint, which is insufficient for many applications with complex objectives or constraints. Observing this, the recent studies (e.g., [4, 5, 11]) have considered non-monotone submodular objectives or more complex constraints such as a k-system constraint. In this study, we follow this line of research and propose truthful BFMs with improved performance bounds for non-monotone submodular objectives with or without a k-system constraint. Our BFMs leverage the idea of providing random prices to users while deferring the decision on the final winning set, and are also based on a novel randomized algorithm for the canonical constrained submodular maximization problem achieving better performance bounds compared to the state-of-the-art. Finally, the effectiveness and efficiency of our approach are demonstrated by extensive experiments on several applications about social network marketing, crowdsourcing and personalized recommendation.Keywords
Funding Information
- National Natural Science Foundation of China (62172384, U20A20182, U22B2060)
This publication has 29 references indexed in Scilit:
- Budget-Feasible Mechanism Design for Non-monotone Submodular Objectives: Offline and OnlineMathematics of Operations Research, 2022
- Simple and Efficient Budget Feasible Mechanisms for Monotone Submodular ValuationsACM Transactions on Economics and Computation, 2021
- Timeliness-Aware Incentive Mechanism for Vehicular Crowdsourcing in Smart CitiesIEEE Transactions on Mobile Computing, 2021
- Budget Feasible Mechanisms on MatroidsAlgorithmica, 2020
- Clock Auctions and Radio Spectrum ReallocationJournal of Political Economy, 2020
- Revenue maximization in incentivized social advertisingProceedings of the VLDB Endowment, 2017
- Budget feasible mechanism designACM SIGecom Exchanges, 2014
- Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack ConstraintsMathematics of Operations Research, 2013
- Maximizing a Monotone Submodular Function Subject to a Matroid ConstraintSIAM Journal on Computing, 2011
- Constrained Non-monotone Submodular Maximization: Offline and Secretary Algorithms2010