More Like this

1. Incentivized Truthful Communication for Federated Bandits

   Wei, Zhepei ; Li, Chuanhao ; Ren, Tianze ; Xu, Haifeng ; Wang, Hongning ( May 2024 , The EleventhInternational Conference on Learning Representations (ICLR'2024))
2. Truthful Data Acquisition via Peer Prediction

   Chen, Yiling ; Shen, Yiheng ; Zheng, Shuran. ( December 2020 , Proc. of the Thirty-fourth Conference on Neural Information Processing Systems (NeurIPS 2020))
3. A Truthful Mechanism for Interval Scheduling

   https://doi.org/10.1007/978-3-319-99660-8_10  

   Garg, Jugal ; McGlaughlin, Peter ( September 2018 , Lecture notes in computer science)

   Motivated by cloud computing, we study a market-based approach for job scheduling on multiple machines where users have hard deadlines and prefer earlier completion times. In our model, completing a job provides a benefit equal to its present value, i.e., the value discounted to the time when the job finishes. Users submit job requirements to the cloud provider who non-preemptively schedules jobs to maximize the social welfare, i.e., the sum of present values of completed jobs. Using a simple and fast greedy algorithm, we obtain a 1+s/(s−1) approximation to the optimal schedule, where s>1 is the minimum ratio of a job’s deadline to processing time. Building on our approximation algorithm, we construct a pricing rule to incentivize users to truthfully report all job requirements. 

   more » « less
4. Incentivized Truthful Communication for Federated Bandits

   Wei, Zhepei ; Li, Chuanhao ; Ren, Tianze ; Xu, Haifeng Xu ; Wang, Hongning ( May 2024 , 12th International Conference on Learning Representations (ICLR 2024))

   To enhance the efficiency and practicality of federated bandit learning, recent advances have introduced incentives to motivate communication among clients, where a client participates only when the incentive offered by the server outweighs its participation cost. However, existing incentive mechanisms naively assume the clients are truthful: they all report their true cost and thus the higher cost one participating client claims, the more the server has to pay. Therefore, such mechanisms are vulnerable to strategic clients aiming to optimize their own utility by misreporting. To address this issue, we propose an incentive compatible (i.e., truthful) communication protocol, named Truth-FedBan, where the incentive for each participant is independent of its self-reported cost, and reporting the true cost is the only way to achieve the best utility. More importantly, Truth-FedBan still guarantees the sub-linear regret and communication cost without any overhead. In other words, the core conceptual contribution of this paper is, for the first time, demonstrating the possibility of simultaneously achieving incentive compatibility and nearly optimal regret in federated bandit learning. Extensive numerical studies further validate the effectiveness of our proposed solution. 

   more » « less
5. Project-Fair and Truthful Mechanisms for Budget Aggregation

   https://doi.org/10.1609/aaai.v38i9.28828  

   Freeman, Rupert ; Schmidt-Kraepelin, Ulrike ( March 2024 , Proceedings of the AAAI Conference on Artificial Intelligence)

   We study the budget aggregation problem in which a set of strategic voters must split a finite divisible resource (such as money or time) among a set of competing projects. Our goal is twofold: We seek truthful mechanisms that provide fairness guarantees to the projects. For the first objective, we focus on the class of moving phantom mechanisms, which are -- to this day -- essentially the only known truthful mechanisms in this setting. For project fairness, we consider the mean division as a fair baseline, and bound the maximum difference between the funding received by any project and this baseline. We propose a novel and simple moving phantom mechanism that provides optimal project fairness guarantees. As a corollary of our results, we show that our new mechanism minimizes the L1 distance to the mean for three projects and gives the first non-trivial bounds on this quantity for more than three projects.

    

   more » « less