Multi-unit Budget Feasible Mechanisms for Cellular Traffic Offloading

Cellular traffic offloading is nowadays an important problem in mobile networking. Since the offloading resource owners (agents) are self-interested and have private costs, it is highly challenging to design procurement mechanisms that motivate agents to reveal their true costs and achieve guaranteed performance under the constraint of a strict budget. In this paper, we model cellular traffic offloading as a multi-unit budget feasible procurement auction design problem with diminishing return valuations. We design a novel greedy-based randomized mechanism, and prove it is budget-feasible, truthful, individually rational and a (3 + 2 ln 𝑁)-approximation, where 𝑁 is the total number of available resource units. We also propose a deterministic mechanism which achieves (2 + ln 𝑁 + √︀ 2 + 3 ln 𝑁 + ln 2 𝑁)-approximation. We prove no budget-feasible and truthful mechanism can do better than ln 𝑁-approximation in our setting, thus our mechanism approaches the optimal to a constant factor. In addition to solving the cellular traffic offloading problem, our work successfully extends solvable valuation class of greedy-based multi-unit budget-feasible mechanism with performance guarantees from the concave-additive valuations to more general local diminishing return valuations.