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. 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
3. 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
4. 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))
5. Randomized Truthful Auctions with Learning Agents

   Aggarwal, G; Gupta, A; Perlroth, A; Velegkas, G (December 2024, 38th Conference on Neural Information Processing Systems (NeurIPS 2024))