An Optimal Bidimensional Multi-Armed Bandit Auction for Multi-unit Procurement

摘要

We study the problem of a buyer (aka auctioneer) who gains stochastic rewards by procuring multiple units of a service or item from a pool of heterogeneous strategic agents. The reward obtained for a single unit from an allocated agent depends on the inherent quality of the agent; the agent's quality is fixed but unknown. Each agent can only supply a limited number of units (capacity of the agent). The costs incurred per unit and capacities are private information of the agents. With known qualities, a) we provide the characterization for any Bayesian incentive compatible (BIC) and Individually rational (IR) mechanism, and b) we propose an optimal, truthful mechanism 2D-OPT. To learn the qualities in addition, a) we provide sufficiency conditions for an allocation rule to be stochastic BIC and IR, and b) we design a novel learning, stochastic BIC and IR mechanism, 2D-UCB.