k-Level Truthful Incentivizing Mechanism and Generalized k-MAB Problem

Multi-armed bandits problem has been widely utilized in economy-related areas. Incentives are explored in the sharing economy to inspire users for better resource allocation. Previous works build a budget-feasible incentive mechanism to learn users’ cost distribution. However, they only consider a special case that all tasks are considered as the same. The general problem asks for finding a solution when the cost for different tasks varies. In this paper, we investigate this problem by considering a system with $k$ levels of difficulty. We present two incentivizing strategies for offline and online implementation, and formally derive the ratio of utility between them in different scenarios. We propose a regret-minimizing mechanism to decide incentives by dynamically adjusting budget assignment and learning from users’ cost distributions. We further extend the problem to a more generalized k-MAB problem by removing the contextual information of difficulties. CUE-UCB algorithm is proposed to address the online advertisement problem for multi-platforms. Our experiment demonstrates utility improvement about 7 times and time saving of 54% to meet a utility objective compared to the previous works in sharing economy, and up to 175% increment of utility for online advertising.

1 Introduction

RECENT trends of applying Reinforcement Learning (RL) mechanisms in economy related areas have shed light on better resolutions to these human-involved fields. Economic problems such as sharing economy, incentivizing mechanisms, online advertising, gambling-like problems are highly complicated due to the dynamic and unpredicted nature of the involving humans. The performance of traditionally heuristic algorithms is diminished in face of the varying cases due to human actions. However, the reinforcement learning can explore and exploit the human factors, which automatically provides ongoing solutions while also converges to the best solutions simultaneously via learning the behaviors of the participants dealt with.