On Truthful Item-Acquiring Mechanisms for Reward Maximization

Liang Shan, Shuo Zhang, Jie Zhang, Zihe Wang

Research output: Chapter or section in a book/report/conference proceedingChapter in a published conference proceeding

39 Downloads (Pure)

Abstract

In this research, we study the problem that a collector acquires items from the owner based on the item qualities the owner declares and an independent appraiser's assessments. The owner is interested in maximizing the probability that the collector acquires the items and is the only one who knows the items' factual quality. The appraiser performs her duties with impartiality, but her assessment may be subject to random noises, so it may not accurately reflect the factual quality of the items. The main challenge lies in devising mechanisms that prompt the owner to reveal accurate information, thereby optimizing the collector's expected reward. We consider the menu size of mechanisms as a measure of their practicability and study its impact on the attainable expected reward. For the single-item setting, we design optimal mechanisms with a monotone increasing menu size. Although the reward gap between the simplest and optimal mechanisms is bounded, we show that simple mechanisms with a small menu size cannot ensure any positive fraction of the optimal reward of mechanisms with a larger menu size. For the multi-item setting, we show that an ordinal mechanism that only takes the owner's ordering of the items as input is not incentive-compatible. We then propose a set of Union mechanisms that combine single-item mechanisms. Moreover, we run experiments to examine these mechanisms' robustness against the independent appraiser's assessment accuracy and the items' acquiring rate.

Original languageEnglish
Title of host publicationWWW 2024 - Proceedings of the ACM Web Conference
Place of PublicationNew York, U. S. A.
PublisherAssociation for Computing Machinery
Pages25-35
Number of pages11
ISBN (Electronic)9798400701719
DOIs
Publication statusPublished - 13 May 2024
Event33rd ACM Web Conference, WWW 2024 - Singapore, Singapore
Duration: 13 May 202417 May 2024

Publication series

NameWWW 2024 - Proceedings of the ACM Web Conference

Conference

Conference33rd ACM Web Conference, WWW 2024
Country/TerritorySingapore
CitySingapore
Period13/05/2417/05/24

Funding

ZiheWang was partially supported by the National Natural Science Foundation of China (Grant No. 62172422). Jie Zhang was partially supported by a Leverhulme Trust Research Project Grant (2021 - 2024) and the EPSRC grant (EP/W014912/1).

FundersFunder number
National Natural Science Foundation of China62172422
National Natural Science Foundation of China
Leverhulme Trust2021 - 2024
Leverhulme Trust
Engineering and Physical Sciences Research CouncilEP/W014912/1
Engineering and Physical Sciences Research Council

Keywords

  • incentive compatibility
  • item-acquiring mechanism
  • reward maximization

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Software

Fingerprint

Dive into the research topics of 'On Truthful Item-Acquiring Mechanisms for Reward Maximization'. Together they form a unique fingerprint.

Cite this