Near-Optimal and Robust Mechanism Design for Covering Problems with\n Correlated Players

We consider the problem of designing incentive-compatible, ex-post\nindividually rational (IR) mechanisms for covering problems in the Bayesian\nsetting, where players' types are drawn from an underlying distribution and may\nbe correlated, and the goal is to minimize the expected total payment made by\nthe mechanism. We formulate a notion of incentive compatibility (IC) that we\ncall {\\em support-based IC} that is substantially more robust than Bayesian IC,\nand develop black-box reductions from support-based-IC mechanism design to\nalgorithm design. For single-dimensional settings, this black-box reduction\napplies even when we only have an LP-relative {\\em approximation algorithm} for\nthe algorithmic problem. Thus, we obtain near-optimal mechanisms for various\ncovering settings including single-dimensional covering problems, multi-item\nprocurement auctions, and multidimensional facility location.\n