Document Open Access Logo

Beyond Worst-Case Budget-Feasible Mechanism Design

Authors Aviad Rubinstein, Junyao Zhao

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.93.pdf
  • Filesize: 0.88 MB
  • 22 pages

Document Identifiers

Author Details

Aviad Rubinstein
  • Computer Science Department, Stanford University, CA, USA
Junyao Zhao
  • Computer Science Department, Stanford University, CA, USA

Funding

  • Rubinstein, Aviad: Supported by NSF CCF-1954927, and a David and Lucile Packard Fellowship.
  • Zhao, Junyao: Supported by NSF CCF-1954927.

Cite As Get BibTex

Aviad Rubinstein and Junyao Zhao. Beyond Worst-Case Budget-Feasible Mechanism Design. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 93:1-93:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ITCS.2023.93

Abstract

Motivated by large-market applications such as crowdsourcing, we revisit the problem of budget-feasible mechanism design under a "small-bidder assumption". Anari, Goel, and Nikzad (2018) gave a mechanism that has optimal competitive ratio 1-1/e on worst-case instances. However, we observe that on many realistic instances, their mechanism is significantly outperformed by a simpler open clock auction by Ensthaler and Giebe (2014), although the open clock auction only achieves competitive ratio 1/2 in the worst case. Is there a mechanism that gets the best of both worlds, i.e., a mechanism that is worst-case optimal and performs favorably on realistic instances? To answer this question, we initiate the study of beyond worst-case budget-feasible mechanism design. 
Our first main result is the design and the analysis of a natural mechanism that gives an affirmative answer to our question above:  
- We prove that on every instance, our mechanism performs at least as good as all uniform mechanisms, including Anari, Goel, and Nikzad’s and Ensthaler and Giebe’s mechanisms. 
- Moreover, we empirically evaluate our mechanism on various realistic instances and observe that it beats the worst-case 1-1/e competitive ratio by a large margin and compares favorably to both mechanisms mentioned above. 
Our second main result is more interesting in theory: We show that in the semi-adversarial model of budget-smoothed analysis, where the adversary designs a single worst-case market for a distribution of budgets, our mechanism is optimal among all (including non-uniform) mechanisms; furthermore our mechanism guarantees a strictly better-than-(1-1/e) expected competitive ratio for any non-trivial budget distribution regardless of the market. (In contrast, given any bounded range of budgets, we can construct a single market where Anari, Goel, and Nikzad’s mechanism achieves only 1-1/e competitive ratio for every budget in this range.) We complement the positive result with a characterization of the worst-case markets for any given budget distribution and prove a fairly robust hardness result that holds against any budget distribution and any mechanism.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational pricing and auctions
Keywords
  • Procurement auctions
  • Mechanism design
  • Beyond worst-case analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Georgios Amanatidis, Pieter Kleer, and Guido Schäfer. Budget-feasible mechanism design for non-monotone submodular objectives: Offline and online. In Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019, pages 901-919, 2019. URL: https://doi.org/10.1145/3328526.3329622.
  2. Nima Anari, Gagan Goel, and Afshin Nikzad. Budget feasible procurement auctions. Operations Research, 66(3):637-652, 2018. Google Scholar
  3. Ashwinkumar Badanidiyuru, Robert Kleinberg, and Yaron Singer. Learning on a budget: posted price mechanisms for online procurement. In Proceedings of the 13th ACM Conference on Electronic Commerce, EC 2012, Valencia, Spain, June 4-8, 2012, pages 128-145, 2012. URL: https://doi.org/10.1145/2229012.2229026.
  4. Eric Balkanski, Pranav Garimidi, Vasilis Gkatzelis, Daniel Schoepflin, and Xizhi Tan. Deterministic budget-feasible clock auctions. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2940-2963. SIAM, 2022. Google Scholar
  5. Eric Balkanski and Jason D. Hartline. Bayesian budget feasibility with posted pricing. In Proceedings of the 25th International Conference on World Wide Web, WWW 2016, Montreal, Canada, April 11 - 15, 2016, pages 189-203, 2016. URL: https://doi.org/10.1145/2872427.2883032.
  6. Hau Chan and Jing Chen. Truthful multi-unit procurements with budgets. In Web and Internet Economics - 10th International Conference, WINE 2014, Beijing, China, December 14-17, 2014. Proceedings, pages 89-105, 2014. URL: https://doi.org/10.1007/978-3-319-13129-0_7.
  7. Hau Chan and Jing Chen. Budget feasible mechanisms for dealers. In Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, Singapore, May 9-13, 2016, pages 113-122, 2016. URL: http://dl.acm.org/citation.cfm?id=2936945.
  8. Ning Chen, Nick Gravin, and Pinyan Lu. On the approximability of budget feasible mechanisms. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 685-699. Society for Industrial and Applied Mathematics, 2011. Google Scholar
  9. Shahar Dobzinski, Christos H. Papadimitriou, and Yaron Singer. Mechanisms for complement-free procurement. In Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), San Jose, CA, USA, June 5-9, 2011, pages 273-282, 2011. URL: https://doi.org/10.1145/1993574.1993615.
  10. Ludwig Ensthaler and Thomas Giebe. A dynamic auction for multi-object procurement under a hard budget constraint. Research Policy, 43(1):179-189, 2014. URL: https://doi.org/10.1016/j.respol.2013.06.011.
  11. Gagan Goel, Afshin Nikzad, and Adish Singla. Mechanism design for crowdsourcing markets with heterogeneous tasks. In Proceedings of the Seconf AAAI Conference on Human Computation and Crowdsourcing, HCOMP 2014, November 2-4, 2014, Pittsburgh, Pennsylvania, USA, 2014. URL: http://www.aaai.org/ocs/index.php/HCOMP/HCOMP14/paper/view/8968.
  12. Nick Gravin, Yaonan Jin, Pinyan Lu, and Chenhao Zhang. Optimal budget-feasible mechanisms for additive valuations. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 887-900. ACM, 2019. Google Scholar
  13. Thibaut Horel, Stratis Ioannidis, and S. Muthukrishnan. Budget feasible mechanisms for experimental design. In LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31 - April 4, 2014. Proceedings, pages 719-730, 2014. URL: https://doi.org/10.1007/978-3-642-54423-1_62.
  14. Pooya Jalaly Khalilabadi and Éva Tardos. Simple and efficient budget feasible mechanisms for monotone submodular valuations. In Web and Internet Economics - 14th International Conference, WINE 2018, Oxford, UK, December 15-17, 2018, Proceedings, pages 246-263, 2018. URL: https://doi.org/10.1007/978-3-030-04612-5_17.
  15. Stefano Leonardi, Gianpiero Monaco, Piotr Sankowski, and Qiang Zhang. Budget feasible mechanisms on matroids. In Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings, pages 368-379, 2017. URL: https://doi.org/10.1007/978-3-319-59250-3_30.
  16. Juan Li, Yanmin Zhu, and Jiadi Yu. Redundancy-aware and budget-feasible incentive mechanism in crowd sensing. Comput. J., 63(1):66-79, 2020. URL: https://doi.org/10.1093/comjnl/bxy139.
  17. Roger B Myerson. Optimal auction design. Mathematics of operations research, 6(1):58-73, 1981. Google Scholar
  18. Besmira Nushi, Adish Singla, Andreas Krause, and Donald Kossmann. Learning and feature selection under budget constraints in crowdsourcing. In Proceedings of the Fourth AAAI Conference on Human Computation and Crowdsourcing, HCOMP 2016, 30 October - 3 November, 2016, Austin, Texas, USA, pages 159-168, 2016. URL: http://aaai.org/ocs/index.php/HCOMP/HCOMP16/paper/view/14032.
  19. Aviad Rubinstein and Junyao Zhao. Budget-Smoothed Analysis for Submodular Maximization. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), pages 113:1-113:23, Dagstuhl, Germany, 2022. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ITCS.2022.113.
  20. Yaron Singer. Budget feasible mechanisms. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 765-774. IEEE, 2010. Google Scholar
  21. Yaron Singer and Manas Mittal. Pricing mechanisms for crowdsourcing markets. In 22nd International World Wide Web Conference, WWW '13, Rio de Janeiro, Brazil, May 13-17, 2013, pages 1157-1166, 2013. URL: https://doi.org/10.1145/2488388.2488489.
  22. Dong Zhao, Xiang-Yang Li, and Huadong Ma. Budget-feasible online incentive mechanisms for crowdsourcing tasks truthfully. IEEE/ACM Trans. Netw., 24(2):647-661, 2016. URL: https://doi.org/10.1109/TNET.2014.2379281.
  23. Zhenzhe Zheng, Fan Wu, Xiaofeng Gao, Hongzi Zhu, Shaojie Tang, and Guihai Chen. A budget feasible incentive mechanism for weighted coverage maximization in mobile crowdsensing. IEEE Trans. Mob. Comput., 16(9):2392-2407, 2017. URL: https://doi.org/10.1109/TMC.2016.2632721.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact