Source author record

Hadi Minooei

Hadi Minooei appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computer Science and Game Theory Data Structures and Algorithms

Catalog footprint

What is connected

2works

2topics

1close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2016arXiv

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

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

preprint2013arXiv

Truthful Mechanism Design for Multidimensional Covering Problems

We investigate {\em multidimensional covering mechanism-design} problems, wherein there are $m$ items that need to be covered and $n$ agents who provide covering objects, with each agent $i$ having a private cost for the covering objects he provides. The goal is to select a set of covering objects of minimum total cost that together cover all the items. We focus on two representative covering problems: uncapacitated facility location (\ufl) and vertex cover (\vcp). For multidimensional \ufl, we give a black-box method to transform any {\em Lagrangian-multiplier-preserving} $ρ$-approximation algorithm for \ufl to a truthful-in-expectation, $ρ$-approx. mechanism. This yields the first result for multidimensional \ufl, namely a truthful-in-expectation 2-approximation mechanism. For multidimensional \vcp (\mvcp), we develop a {\em decomposition method} that reduces the mechanism-design problem into the simpler task of constructing {\em threshold mechanisms}, which are a restricted class of truthful mechanisms, for simpler (in terms of graph structure or problem dimension) instances of \mvcp. By suitably designing the decomposition and the threshold mechanisms it uses as building blocks, we obtain truthful mechanisms with the following approximation ratios ($n$ is the number of nodes): (1) $O(r^2\log n)$ for $r$-dimensional \vcp; and (2) $O(r\log n)$ for $r$-dimensional \vcp on any proper minor-closed family of graphs (which improves to $O(\log n)$ if no two neighbors of a node belong to the same player). These are the first truthful mechanisms for \mvcp with non-trivial approximation guarantees.