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

arXiv:1311.6883v2 [cs.GT] 29 Sep 2016

Hadi Minooei†

Chaitanya Swamy

†

Abstract
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 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 singledimensional settings, this black-box reduction applies even when we only have an LP-relative
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.

1

Introduction

In a covering mechanism-design problem, there are players who provide covering objects and a buyer
who needs to obtain a suitable collection of objects so as to satisfy certain covering constraints (e.g.,
covering a ground set); each player incurs a certain private cost, which we refer to as his type, for
providing his objects, and the mechanism must therefore pay the players from whom objects are
procured. We consider the problem of designing incentive-compatible, ex-post individually rational
(IR) mechanisms for covering problems (also called procurement auctions) 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. Consider the simplest such
setting of a single-item procurement auction, where a buyer wants to buy an item from any one
of n sellers. Each seller’s private type is the cost he incurs for supplying the item and the sellers
must therefore be incentivized via a suitable payment scheme. Myerson’s seminal result [19] solves
this problem (and other single-dimensional problems) when players’ private types are independent.
However, no such result (or characterization) is known when players’ types are correlated. This is
the question that motivates our work.
Whereas the analogous revenue-maximization problem for packing domains, such as combinatorial auctions (CAs), has been extensively studied in the algorithmic mechanism design (AMD)
literature, both in the case of independent and correlated (even interdependent) player-types (see,
e.g., [3, 4, 2, 1, 5, 9, 8, 21, 2, 25] and the references therein), surprisingly, there are almost no results
on the payment-minimization problem for covering settings in the AMD literature (see however the
discussion in “Related work” for some exceptions). The economics literature does contain various
general results that apply to both covering and packing problems. However much of this work
∗

A preliminary version appeared as [18].
{hminooei,cswamy}@uwaterloo.ca. Dept. of Combinatorics and Optimization, Univ. Waterloo, Waterloo, ON
N2L 3G1. Research supported partially by NSERC grant 327620-09 and the second author’s Discovery Accelerator
Supplement Award, and Ontario Early Researcher Award.
†

1

focuses on characterizing special cases; see, e.g., [14, 13]. An exception is the work of Crémer and
McLean [6, 7], which shows that under certain conditions, one can devise a Bayesian-incentivecompatible (BIC) mechanism whose expected total payment exactly equal to the expected cost
incurred by the players, albeit one where players may incur negative utility under certain typeprofile realizations.
Our contributions. We initiate a study of payment-minimization (PayM) problems from the
AMD perspective of designing computationally efficient, near-optimal mechanisms. We develop
black-box reductions from mechanism design to algorithm design whose application yields a variety of optimal and near-optimal mechanisms. As we elaborate below, covering problems turn
out to behave quite differently in certain respects from packing problems, which necessitates new
approaches (and solution concepts).
Formally, we consider the setting of correlated players in the explicit model, that is, where we
have an explicitly-specified arbitrary discrete joint distribution of players’ types. A commonlyused solution concept in Bayesian settings is Bayesian incentive compatibility (BIC) and interim
individual rationality (interim IR), wherein at the interim stage when a player knows his type but
is oblivious of the random choice of other players’ types, truthful participation in the mechanism
by all players forms a Bayes-Nash equilibrium. Two serious drawbacks of this solution concept
(which are exploited strikingly and elegantly in [6, 7]) are that: (i) a player may regret his decision
of participating and/or truthtelling ex post, that is, after observing the realization of other players’
types; and (ii) it is overly-reliant on having precise knowledge of the true underlying distribution
making this a rather non-robust concept: if the true distribution differs, possibly even slightly, from
the mechanism designer’s and/or players’ beliefs or information about it, then the mechanism could
lose its IC and IR properties.
On the other hand, the solution concept of dominant-strategy incentive compatibility (DSIC)
and ex-post IR ensures that truthful participation is the best choice, and a no-regret choice, for
every player regardless of the other players’ reported types. This is the most robust notion of IC
and IR, since it is a completely distribution-independent.
We consider the problem of designing near-optimal mechanisms for payment-minimization problems with robustness being an important consideration. This makes (DSIC, ex-post IR), which we
abbreviate to (DSIC, IR), as the natural ideal. However, certain difficulties arise in achieving this
goal for covering problems (see “Differences . . . packing problems” below). We formulate a notion
of incentive compatibility that we call support-based IC1 that, while somewhat weaker than DSIC,
is still substantially more robust than BIC and at the same time is flexible enough that it allows one
to obtain various polytime near-optimal mechanisms satisfying this notion. A support-based-(IC,
IR) mechanism (see Section 2) ensures that truthful participation in the mechanism is in the best
interest of every player (i.e. a “no-regret” choice) for every type profile in a certain subset of the
type space: for every player i, we impose the IC and IR conditions for all type profiles of the form
(·, c−i ) for every profile c−i of other players’ types coming from the support of the underlying distribution. In particular, a support-based-(IC, IR) mechanism ensures that truthful participation is
the best choice for every player even at the ex-post stage when the other players’ (randomly-chosen)
types are revealed to him. Such a mechanism is significantly more robust than a (BIC, interim-IR)
mechanism since it retains its IC and IR properties for a large class of distributions that contains
(in particular) every distribution whose support is a subset of the support of the actual distribution. In other words, in keeping with Wilson’s doctrine of detail-free mechanisms, the mechanism
functions robustly even under fairly limited information about the type-distribution.
1

The conference version [18] of this paper referred to this as “robust Bayesian IC.”

2

We show that for a variety of settings, one can reduce the support-based-(IC, IR) paymentminimization (PayM) mechanism-design problem to the algorithmic cost-minimization (CM) problem of finding an outcome that minimizes the total cost incurred. Moreover, this black-box reduction applies to: (a) single-dimensional settings even when we only have an LP-relative approximation
algorithm for the CM problem (that is required to work only with nonnegative costs) (Theorem 4.2);
and (b) multidimensional problems with additive types (Corollary 3.3).
Our reduction yields near-optimal support-based (IC-in-expectation, IR) mechanisms for a variety of covering settings such as (a) various single-dimensional covering problems including singleitem procurement auctions (Table 1); (b) multi-item procurement auctions (Theorem 5.1); and (c)
multidimensional facility location (Theorem 5.3). (Support-based IC-in-expectation means that the
support-based-IC guarantee holds for the expected utility of a player, where the expectation is over
the random coin tosses of the mechanism.) In Section 6, we consider some extensions involving both
weaker (but more robust than (BIC, interim IR)) solution concepts and the stronger (DSIC, IR)
solution concept. We obtain the same guarantees under the various weaker solution concepts, and
adapt our techniques to obtain (DSIC-in-expectation, IR) mechanisms with the same guarantees
for single-dimensional problems in time exponential in the number of players (Section 6.2). These
are the first results for the PayM mechanism-design problem for covering settings with correlated
players under a notion stronger than (BIC, interim IR). To our knowledge, our results are new even
for the simplest covering setting of single-item procurement auctions.
Our techniques. The starting point for our construction is a linear-programming (LP) relaxation
(P) for the problem of computing an optimal support-based-(IC, IR)-in-expectation mechanism.
This was also the starting point in the work of [8], which considers the revenue-maximization problem for CAs, but the covering nature of the problem makes it difficult to apply certain techniques
utilized successfully in the context of packing problems (as described below).
We show that an optimal solution to (P) can be computed given an optimal algorithm A for the
CM problem since A can be used to obtain a separation oracle for the dual LP. Next, we prove that
a feasible solution to (P) can be extended to a support-based-(IC-in-expectation, IR) mechanism
with no larger objective value.
For single-dimensional problems, we show that even LP-relative ρ-approximation algorithms for
the CM problem can be utilized, as follows. We move to a relaxation of (P), where we replace the
set of allocations with the feasible region of the CM-LP. This can be solved efficiently, since the
separation oracle for the dual can be obtained by optimizing over the feasible region of CM-LP,
which can be done efficiently! But now we need to work harder to “round” an optimal solution (x, p)
to the relaxation of (P) and obtain a support-based-(IC-in-expectation, IR) mechanism. Here, we
exploit the Lavi-Swamy [12] convex-decomposition procedure, using which we can show (roughly
speaking) that we can decompose ρx into a convex combination of allocations. This allows us
to obtain a support-based-(IC-in-expectation, IR) mechanism while blowing up the payment by a
ρ-factor.
In comparison with the reduction in [8], which is the work most closely-related to ours, our
reduction from support-based-IC mechanism design to the algorithmic CM problem is stronger in
the following sense. For single-dimensional settings, it applies even with LP-relative approximation
algorithms, and the approximation algorithm is required to work only for “proper inputs” with
nonnegative costs. (Note that whereas for packing problems, allowing negative-value inputs can be
benign, this can change the character of a covering problem considerably.) In contrast, Dobzinski
et al. [8] require an exact algorithm for the analogous social-welfare-maximization (SWM) problem.

3

Differences with respect to packing problems. At a high level, our method of writing an LP
for the underlying mechanism-design problem and solving it given an algorithm for an associated
algorithmic problem is similar to the procedure in Dobzinski et al. [8]. However, we encounter three
distinct sources of difficulty when dealing with covering problems vis-a-vis packing problems.
First, as noted in [8], the LP can only encode the IC and IR conditions for a finite set of type
profiles, whereas, with an infinite type space, both support-based-(IC, IR) and (DSIC, IR) require
the mechanism to satisfy the IC and IR conditions for an infinite set of type profiles. Therefore,
to translate the LP solution to a suitable mechanism, we need to solve the “extension problem”
of extending an allocation and pricing rule defined on a (finite) subset of the type space to the
entire type space while preserving its IC and IR properties. This turns out to be a much more
difficult task for covering problems than for packing domains. The key difference is that for a
packing setting such as combinatorial auctions, one can show that any LP solution—in particular,
the optimal LP solution—can be converted into a (DSIC-in-expectation, IR) mechanism without
any loss in expected revenue (see Section C.1). (Consequently, [8] obtain (DSIC-in-expectation,
IR) mechanisms.) Intuitively, this works because one can focus on a single player by allocating no
items to the other players. Clearly, one cannot mimic this for covering problems: dropping players
may render the problem infeasible, and it is not clear how to extend an LP-solution to a (DSICin-expectation, IR) mechanism for covering problems. We suspect that not every LP solution or
support-based-(IC, IR) mechanism can be extended to a (DSIC, IR) mechanism, and that there is
a gap between the optimal expected total payments of support-based-(IC-in-expectation, IR) and
(DSIC, IR) mechanisms. We leave these as open problems.2
Due to this complication, we sacrifice a modicum of the IC, IR properties in favor of obtaining polytime near-optimal mechanisms and settle for the weaker, but still quite robust notion of
support-based (IC-in-expectation, IR). We consider this to be a reasonable starting point for exploring mechanism-design solutions for covering problems, which leads to various interesting research
directions.3
A second difficulty, which we have alluded to above, arises due to the fact that solving the LP
requires one to solve the CM problem with negative-valued inputs. This is also true of packing
problems [8] (where one needs to solve the SWM problem), even in the single-item setting [19]
(where reserve prices arise due to negative virtual valuations). While this is not a problem if
we have an optimal algorithm for the CM problem, it creates serious issues, even in the singledimensional setting, if we only have an approximation algorithm at hand; in particular, the standard
notion of approximation becomes meaningless since the optimum could be negative. In contrast,
for packing problems with single-dimensional types (or additive types [2, 3, 4]), these issues are
more benign since one may always discard players (or options of players) with negative value. In
particular, an approximation algorithm can be used to obtain an approximate separation oracle for
the dual LP, and thus obtain a near-optimal solution to the primal LP via a well-known technique
in approximation algorithms. (We sketch this extension of a result of [8] in Appendix C.1.)
Finally, a stunning aspect where covering and packing problems diverge can be seen when one
considers the idea of a k-lookahead auction [22, 8]. This was used by [8] to convert their results in
2

We show in Section 6.2 that if we expand our LP to include IC and IR constraints for a much larger (exponentialsized) set of type-profiles then, for single-dimensional settings, it is possible to extend an LP-solution to a (DSIC-inexpectation, IR) mechanism.
3
For covering problems, even formulating the LP in a way that its solution can be extended to a support-based-(IC,
IR) mechanism is somewhat tricky due to the following complication. We need to argue (see Lemma 2.3) that there
is an optimal support-based-(IC-in-expectation, IR) mechanism such that for every player i, and every profile c−i
coming from the support of the underlying distribution, there is a type profile (mi , c−i ) under which the mechanism
never procures objects from i, and include this condition in the LP (otherwise, the IC and IR conditions would force
the LP-extension to make arbitrarily large payments).

4

the explicit model to the oracle model introduced by [22]. This however fails spectacularly in the
covering setting. One can show that even for single-item procurement auctions, dropping even a
single player can lead to an arbitrarily large payment compared to the optimum (see Appendix B).
Other related work. In the economics literature, the classical results of Crémer and McLean [6,
7] and McAfee and Reny [16], also apply to covering problems, and show that one can devise a
(BIC, interim IR) mechanism with correlated players whose expected total payment is at most the
expected total cost incurred provided the underlying type-distribution satisfies a certain full-rank
assumption. These mechanisms may however cause a player to have negative utility under certain
realizations of the random type profile.
The AMD literature has concentrated mostly on the independent-players setting [3, 4, 2, 1, 5, 9].
There has been some, mostly recent, work that also considers correlated players [22, 23, 8, 21, 2, 25].
Much of this work pertains to the revenue-maximization setting; an exception is [23], which is
discussed below. Ronen [22] considers the single-item auction setting in the oracle model, where one
samples from the distribution conditioned on some players’ values. He proposes the (1-) lookahead
auction and shows that it achieves a 12 -approximation. Papadimitriou and Pierrakos [21] show that
the optimal (DSIC, IR) mechanism for the single-item auction can be computed efficiently with at
most 2 players, and is NP-hard otherwise. Cai et al. [2] give a characterization of the optimal auction
under certain settings. Roughgarden and Talgam-Cohen [25] consider interdependent types, which
generalizes the correlated type-distribution setting, and develop an analog of Myerson’s theory for
certain such settings.
Ronen and Lehmann [23] consider the PayM problem in the setting where a buyer wants to buy
an item from sellers who can supply the item in on of many configurations and incur private costs
for supplying the item. However, this procurement problem is in fact a packing problem: one can
view a solution to be feasible if it selects at most one configuration for procurement; in particular,
the buyer has the flexibility of not procuring the item. As noted earlier, this flexibility drastically
alters the character of the mechanism-design problem. Not surprisingly, the results therein, which
are based on lookahead auctions, do not apply in the covering setting (as noted above).
Various reductions from revenue-maximization to SWM are given in [2, 3, 4]. The reductions
in [2, 4] also apply to covering problems and the PayM objective, but they are incomparable to our
results. These works focus on the (BIC, interim-IR) solution concept, which is a rather weak/liberal
notion for correlated distributions. Most (but not all) of these consider independent players and additive valuations, and often require that the SWM-algorithm also work with negative values, which
is a benign requirement for downward-closed environments such as CAs but is quite problematic
for covering problems when only has an approximation algorithm. Cai et al. [2] consider correlated
players and obtain mechanisms having running time polynomial in the maximum support-size of
the marginal distribution of a player, which could be substantially smaller than the support-size
of the entire distribution. This savings can be traced to the use of the (BIC, interim-IR) notion
which allows [2] to work with a compact description of the mechanism. It is unclear if these ideas
are applicable when one considers robust-(BIC, IR) mechanisms. A very interesting open question is whether one can design robust-(BIC-in-expectation, IR) mechanisms having running time
polynomial in the support-sizes of the marginal player distributions (as in [2, 8]).

2

Preliminaries

Covering mechanism-design problems. We adopt the formulation in [17] to describe general
covering mechanism-design problems. There are some items that need to be covered, and n players
who provide covering objects. Let [k] denote the set {1, . . . , k}. Each player i provides a set Ti
5

of covering objects. All this information is public knowledge. Player i has a private cost or type
vector ci = {ci,v }v∈Ti , where
ci,v ≥ 0 is the cost he incurs for providing object v ∈ Ti ; for T ⊆ Ti ,
P
we use ci (T ) to denote v∈T ci,v . A feasible solution or allocation
selects a subset Ti ⊆ Ti for each
S
agent i, denoting that i provides the objects in Ti , such that i Ti covers all the items. Given this
solution, each agent i incurs the private cost ci (Ti ), and the mechanism designer incurs a publicly
known cost pub(T1 , . . . , Tn ) ≥ 0, which may be used to encode any feasibility constraints in the
covering problem.
Q
Let Ci denote the set of all possible types of agent i, and C = ni=1 Ci . We assume (for
|T |
notational simplicity) that Ci = R+ i . Let Ω := {(T1 , . . . , Tn ) : pub(T1 , . . . , Tn ) < ∞} be
the (finite) set of all feasible allocations. For aQtuple x = (x1 , . . . , xn ), we use x−i to denote
(x1 , . . . , xi−1 , xi+1 , . . . , xn ). Similarly, let C−i = j6=i Cj . For an allocation ω = (T1 , . . . , Tn ), we
sometimes use ωi to denote Ti , ci (ω) to denote ci (ωi ) = ci (Ti ), and pub(ω) to denote pub(T1 , . . . , Tn ).
We make the mild assumption that pub(ω ′ ) ≤ pub(ω) if ωi ⊆ ωi′ for all i; so in particular, if ω is
feasible, then adding covering objects to the ωi s preserves feasibility.
A (direct revelation) mechanism M = (A, p1 , . . . , pn ) for a covering problem consists of an
allocation algorithm A : C 7→ Ω and a payment function pi : C 7→ R for each agent i. Each agent
i reports a cost function ci (that might be different from his true cost function). The mechanism
computes the allocation A(c) = (T1 , . . . , Tn ) = ω ∈ Ω, and pays pi (c) to each agent i. The utility
ui (ci , c−i ; ci ) that player i derives when he reports ci and the others report c−i is pi (c) − ci (ωi )
where ci is his true cost function, and each agent i aims to maximize his own utility. We refer
to maxi |Ti | as the dimension of a covering problem. Thus, for a single-dimensional problem, each
player i’s cost can be specified as ci (ω) = ci αi,ω , where ci ∈ R+ is his private type and αi,ω = 1 if
ωi 6= ∅ and 0 otherwise.
The above setup yields a multidimensional covering mechanism-design problem with additive
types, where by additivity we mean that the private cost thatP
a player i incurs for providing a set
T ⊆ Ti of objects is additive across the objects in T (i.e., it is v∈Ti ci,v ). Notice that if ci , c′i ∈ Ci ,
then the type ci + c′i defined by {ci,v + c′i,v }v∈Ti is also in Ci and satisfies (ci + c′i )(ω) = ci (ω) + c′i (ω)
for all ω ∈ Ω. It is possible to define more general multidimensional settings, but additive types
is a reasonable starting point to explore the multidimensional covering mechanism-design setting.
(As noted earlier, there has been almost no work on designing polytime, near-optimal mechanisms
for covering problems.)
The Bayesian setting. We consider Bayesian settings where there is an underlying publiclyknown discrete and possibly correlated joint type-distribution on C from which the players’ types are
drawn. We consider the so-called explicit model, where the players’ type distribution is explicitly
specified. We use D ⊆ C to denote the support of the type distribution, and PrD (c) to denote the
probability of realization of c ∈ C. Also, we define Di := {ci ∈ Ci : ∃c−i s.t. (ci , c−i ) ∈ D}, and
D−i to be {c−i : ∃ci s.t. (ci , c−i ) ∈ D}.
Solution concepts. A mechanism sets up a game between players, and the solution concept
dictates certain desirable properties that this game should satisfy, so that one can reason about the
outcome when rational players are presented with a mechanism satisfying the solution concept. The
two chief properties that one seeks to capture relate to incentive compatibility (IC), which (roughly
speaking) means that every agent’s best interest is to reveal his type truthfully, and individual
rationality (IR), which is the notion that no agent is harmed by participating in the mechanism.
Differences and subtleties arise in Bayesian settings depending on the stage at which we impose
these properties and how robust we would like these properties to be with respect to the underlying
type distribution.
6


Definition 2.1 A mechanism M = A, {pi } is Bayesian incentive compatible (BIC) and interim
IR if for every player i and every ci ∈ Di , ci ∈ Ci , we have Ec−i [ui (ci , c−i ; ci )|ci ] ≥ Ec−i [ui (ci , c−i ; ci )|ci ]
(BIC) and Ec−i [ui (ci , c−i ; ci )|ci ] ≥ 0 (interim IR), where Ec−i [.|ci ] denotes the expectation over the
other players’ types conditioned on i’s type being ci .
As mentioned earlier, the (BIC, interim-IR) solution concept may yet lead to ex-post “regret”,
and is quite non-robust in the sense that the mechanism’s IC and IR properties rely on having detailed knowledge of the distribution; thus, in order to be confident that a BIC mechanism achieves
its intended functionality, one must be confident about the “correctness” of the underlying distribution, and learning this information might entail significant cost. To remedy these weaknesses,
we propose and investigate the following stronger IC and IR notions.

Definition 2.2 A mechanism M = A, {pi } is support-based IC and support-based IR, if for
every player i, every ci , ci ∈ Ci , and every c−i ∈ D−i , we have ui (ci , c−i ; ci ) ≥ ui (ci , c−i ; ci ) (supportbased IC) and ui (ci , c−i ; ci ) ≥ 0 (support-based IR).
Support-based (IC, IR) ensures that participating truthfully in the mechanism is in the best
interest of every player even at the ex-post stage when he knows the realized types of all players.
To ensure that support-based IC and support-based IR are compatible, we focus on monopoly-free
settings: for every player i, there is some ω ∈ Ω with ωi = ∅.
Notice that support-based (IC, IR) is subtly weaker than the notion of (dominant-strategy
IC (DSIC), IR), wherein the IC and IR conditions of Definition 2.2 must hold for all c−i ∈ C−i ,
ensuring that truthtelling and participation are no-regret choices for a player even if the other
players’ reports are outside the support of the underlying type-distribution. We focus on supportbased IC because it forms a suitable middle-ground between BIC and DSIC: it inherits the desirable
robustness properties of DSIC, making it much more robust than BIC (and closer to a worst-case
notion), and yet is flexible enough that one can devise polytime mechanisms satisfying this solution
concept.
It might seem strange that in the definition of support-based (IC, IR), we consider player i’s
incentives for types outside of i’s support and for type-profiles that are inconsistent with the underlying distribution. Keeping robustness in mind, our goal here is to approach the ideal of (DSIC,
IR) and we have therefore formulated the most-robust notion that permits us to devise polytime
near-optimal mechanisms satisfying this notion. In Section 6, we consider various alternate solution
concepts that, while weaker than support-based (IC, IR), still retain its robustness properties to a
large extent, and show that our results extend easily to these solution concepts.
The above definitions are stated for a deterministic mechanism, but they have analogous extensions to a randomized mechanism M ; the only change is that the ui (.) and pi (.) terms are now
replaced by the expected utility EM [ui (.)] and expected price EM [pi (.)] respectively, where the
expectation is over the random coin tosses of M . We denote the analogous solution concept for a
randomized mechanism by appending “in expectation” to the solution concept, e.g., a (BIC, interim
IR)-in-expectation mechanism denotes a randomized mechanism whose expected utility satisfies the
BIC and interim-IR requirements stated in Definition 2.1.

A support-based-(IC, IR)-in-expectation mechanism M = A, {pi } can be easily modified so
that the IR condition holds with probability 1 (with respect to M ’s coin tosses) while the expected
payment to a player (again over M ’s coin tosses) is unchanged: on input c, if A(c) = ω ∈ Ω
with probability q, the new mechanism returns, with probability q, the allocation ω, and payment
M [pi (c)]
ci (ω) · EEM
[ci (ω)] to each player i (where we take 0/0 to be 0, so if ci (ω) = 0, the payment to i is 0).
Thus, we obtain a mechanism whose expected utility satisfies the support-based-IC condition, and

7

IR holds with probability 1 for all ci ∈ Ci , c−i ∈ D−i , A similar transformation can be applied to a
(DSIC, IR)-in-expectation mechanism.
Optimization problems. Our main consideration is to minimize the expected total payment of
the mechanism. It is natural to also incorporate the
 mechanism-designer’s

Pcost into the objective.
Define the disutility of a mechanism M = A, {pi } under input c to be i pi (c) + κ · pub A(c) ,
where κ ≥ 0 is a given scaling factor. Our objective is to devise a polynomial-time support-based(IC (in-expectation), IR)-mechanism with minimum expected disutility. Since most problems we
consider have pub(ω) = 0 for all feasible allocations, in which case disutility equals the total
payment, abusing terminology slightly, we refer to the above mechanism-design problem as the
payment-minimization (PayM) problem. (An exception is metric uncapacitated facility location
(UFL), where players provide facilities and the underlying metric is public knowledge; here, pub(ω)
is the total client-assignment cost of the solution ω.) We always use O∗ to denote the expected
disutility of an optimal mechanism for the PayM problem under consideration.
We define the cost minimization
(CM) problem to be the algorithmic problem of finding ω ∈ Ω
P
that minimizes the total cost i ci (ω) + pub(ω) incurred.
The following technical lemma, whose proof we defer to Appendix A, will prove quite useful
since it allows us to restrict the domain to a bounded set, which is essential to achieve IR with
finite prices. (For example, in the single-dimensional setting, the payment is equal to the integral
of a certain quantity from 0 to ∞, and a bounded domain ensures that this is well defined.) Note
that such complications do not arise for packing problems. Let 1Ti be the |Ti |-dimensional all 1s
vector. Let I denote the input size.
Lemma 2.3 We can efficiently compute an estimate mi > maxci ∈Di ,v∈Ti ci,v with log mi = poly(I)
for all i such that there is an optimal support-based-(IC-in-expectation, IR) mechanism M ∗ =
A∗ , {p∗i } where A∗ (mi 1Ti , c−i )i = ∅ with probability 1 (over the random choices of M ∗ ) for all i
and all c−i ∈ D−i .
It is easy to obtain the stated estimates if we consider only deterministic mechanisms, but it
turns out to be tricky to obtain this when one allows randomized mechanisms due to the artifact
that a randomized mechanism may choose arbitrarily high-cost solutions as long as they are chosen
with S
small enough probability. In the sequel, we set Di := Di ∪ {mi 1Ti } for all i ∈ [n], and
D := i (D i × D−i ). Note that |D| = O(n|D|2 ).

3

LP-relaxations for the payment-minimization problem

The starting point for our results is the LP (P) that essentially encodes the payment-minimization
problem. Throughout, we use i to index players, c to index type-profiles in D, and ω to index
Ω. We use variables xc,ω to denote the probability of choosing ω, S
and pi,c to denote the expected
payment to player i, for input c. For c ∈ D, let Ω(c) = Ω if c ∈ i (Di × D−i ), and otherwise if
c = (mi 1Ti , c−i ), let Ω(c) = {ω ∈ Ω : ωi = ∅} (which is non-empty since we are in a monopoly-free
setting).

8

X

min

c∈D

X

X
PrD (c)
pi,c + κ
xc,ω pub(ω)
X

s.t.

(P)

ω

i

∀c ∈ D

xc,ω = 1

ω

pi,(ci ,c−i ) −

X

ci (ω)x(ci ,c−i ),ω ≥ pi,(c′i ,c−i ) −

pi,(ci ,c−i ) −

X

ci (ω)x(ci ,c−i ),ω ≥ 0

ω

X

ci (ω)x(c′i ,c−i ),ω

(1)

∀i, ci , c′i ∈ D i , c−i ∈ D−i (2)

ω

∀i, ci ∈ D i , c−i ∈ D−i

(3)

∀c, ω ∈
/ Ω(c).

(4)

ω

p, x ≥ 0,

xc,ω = 0

(1) encodes that an allocation is chosen for every c ∈ D, and (2) and (3) encode the support-basedIC and support-based-IR conditions respectively. Lemma 2.3 ensures that (P) correctly encodes
PayM, so that OPT := OPT P is a lower bound on the expected disutility of an optimal mechanism.
Our results are obtained by computing an optimal solution to (P), or a further relaxation
of it, and translating this to a near-optimal support-based-(IC-in-expectation, IR) mechanism.
Both steps come with their own challenges. Except in very simple settings (such as single-item
procurement auctions), |Ω| is typically exponential in the input size, and therefore it is not clear how
to solve (P) efficiently. We therefore consider the dual LP (D), which has variables γc , yi,(ci ,c−i ),c′i
and βi,(ci ,c−i ) corresponding to (1), (2) and (3) respectively.
X

max
s.t.

X

c

γc

X

i:c∈Di ×D−i c′i ∈Di

X

c′i ∈D i

yi,(ci ,c−i ),c′i

(D)


ci (ω)yi,(ci ,c−i ),c′i − c′i (ω)yi,(c′i ,c−i ),ci + ci (ω)βi,c
+ κ · PrD (c) pub(ω) ≥ γc

− yi,(c′i ,c−i ),ci + βi,ci ,c−i ≤ PrD (c)

y, β ≥ 0.

∀c ∈ D, ω ∈ Ω(c)
∀i, ci ∈ D i , c−i ∈ D−i

(5)
(6)
(7)

P
With additive types, one can encode the LHS of (5) as i c̃i (ω) for a suitably-defined additive
type (depending on c) c̃i = (c̃i,v )v∈Ti . Thus, the separation problem for constraints (5) amounts
to determining if the optimal value of the CM problem defined by a certain additive type profile,
with possibly negative values, is at least γc . Hence, an optimal algorithm for the CM problem can
be used to solve (D), and hence, (P), efficiently.
Theorem 3.1 With additive types, one can efficiently solve (P) given an optimal algorithm for the
CM problem.
Proof : Let A be an optimal algorithm for the CM problem. Note that A is only required to work
with nonnegative inputs. We first observe that we can use A to find a solution that minimizes
P
i ci (ω) + κ · pub(ω) for any κ ≥ 0, even for an input c = {ci,v }i,v∈Ti where some of the ci,v s
are negative. Let Ai = {v ∈ Ti : ci,v < 0}. Clearly, if ω ∗ is an optimal solution, then Ai ⊆ ωi∗
(since pub(.) does not increase upon adding covering objects). Define c+
i,v := max(0, ci,v ) and
+
c+
:=
{c
}
.
i
i,v v∈Ti
Let Γ = κ1 if κ > 0; otherwise let Γ = N U , where U is a strict upper bound on maxω∈Ω pub(ω)
1
′
and N is an integer such that all the c+
i,v s are integer multiples of N . Note that for any ω, ω ∈ Ω,
9

P
P + ′
1
if i c+
i (ω) −
i ci (ω ) is non-zero, then its absolute value is at least N . Also, U and N may be
efficiently computed (for rational data) and log(N U ) is polynomially bounded. Let (S1 , . . . , Sn ) be
the solution returned by A for the CM problem on the input where all the c+
i,v s are scaled by Γ.
The choice of Γ ensures that
X
X

 X + ∗
ci (ωi∗ ) − ci (Ai ) + κ · pub(ω ∗ ).
ci (ωi ) + κ · pub(ω ∗ ) =
c+
i (Si ) + κ · pub S1 , . . . , Sn ≤
i

i

i

P

P + ∗
+
(The first
inequality
clearly
holds
if
κ
>
0.
If
κ
=
0
and
c
(S
)
>
i
i
i
i ci (ωi ), then we have
P + ∗
P +
P + ∗
Γ
∗
that Γ i ci (Si ) ≥ Γ i ci (ωi ) + N > Γ i ci (ωi ) + pub(ω ), which contradicts the optimality of
′
(S1 , . . . , SnP
) for the input {Γc+
i .) So setting ωi = Ai ∪ Si for every i yields a feasible solution
i,v }i,v∈T
P
such that i ci (ω ′ ) + κ · pub(ω ′ ) ≤ i ci (ω ∗ ) + κ · pub(ω ∗ ); hence ω ′ is an optimal solution.

Given a dual solution (y, β, γ), we can easily P
check if (6), (7) hold. Fix c ∈ D and
 player i.
c =
′ y
′
′
Since we have additive types, if we define θi,v
c
y
−
c
′
i,v
i,(ci ,c−i ),ci
i,v i,(ci ,c−i ),ci + ci,v βi,c ,
ci ∈Di

P
′
then for every ω ∈ Ω, we can equate c′ ∈Di ci (ω)yi,(ci ,c−i ),c′i − ci (ω)yi,(c′i ,c−i ),ci + ci (ω)βi,c with
i
P
c .
θic (ω) := v∈ωi θi,v
P
c
Let I = {i : c ∈ Di × D−i }. Constraints (5) for c can then be written as minω∈Ω(c)
i∈I θ (ω) +
κ PrD (c) pub(ω) ≥ γc . Define c̃ as follows:
c̃i,v



γc + 1
c
= θi,v


0

if ci = mi 1Ti ,
if i ∈ I, ci ∈ Di ,
otherwise.


P
It is easy to see that (5) holds for c iff minω∈Ω
i c̃i (ω)+κ·PrD (c) pub(ω) —which can be computed
using A—is at least γc . Thus, we can use the ellipsoid method to solve (D). This also yields a
compact dual consisting of constraints (6), (7) and the polynomially-many (5) constraints that were
returned by the separation oracle during the execution of the ellipsoid method, whose optimal value
is OPT D . The dual of this compact dual is an LP of the same form as (P) but with polynomially
many xc,ω -variables; solving this yields an optimal solution to (P).
Complementing Theorem 3.1, we argue that a feasible solution (x, p) to (P) can be extended to
a support-based-(IC-in-expectation, IR) mechanism having expected disutility at most the value
of (x, p) (Theorem 3.2). Combining this with Theorem 3.1 yields the corollary that an optimal
algorithm for the CM problem can be used to obtain an optimal mechanism for the PayM problem
(Corollary 3.3).
Theorem 3.2 We can extend a feasibleP
solution (x,P
p) to (P) toPa support-based-(IC-in-expectation,

IR) mechanism with expected disutility c PrD (c)
i pi,c + κ
ω xc,ω pub(ω) .
Proof : Let Ω′ = {ω : xc,ω > 0 for some c ∈ D}. We use xc to denote the vector {xc,ω }ω∈Ω′ .
Consider a player i, c−i ∈ D−i , and ci , c′i ∈ D i . Note that (2) implies that if x(ci ,c−i ) = x(c′i ,c−i ) ,

then pi,(ci ,c−i ) = pi,(c′i ,c−i ) . For c−i ∈ D−i , define R(i, c−i ) = x(ci ,c−i ) : (ci , c−i ) ∈ D , and for
y = x(ci ,c−i ) ∈ R(i, c−i ) define pi,y to be pi,(ci ,c−i ) (which is well
 defined by the above argument).
We now define the randomized mechanism M = A, {qi } , where A(c) and qi (c) denote respectively the probability distribution over allocations and the expected payment to player i, on input c.
We sometimes view A(c) equivalently as the random variable specifying the allocation chosen for input c. Fix an allocation ω0 ∈ Ω. Consider an input c. If c ∈ D, we set A(c) = xc , and qi (c) = pi,c for
all i. So consider c ∈
/ D. If there is no i such that c−i ∈ D−i , we simply set A(c) = ω0 , qi (c) = ci (ω0 )
10

for all i; such a c does not figure in the support-based (IC, IR) conditions. Otherwise
there is a
P
unique i such that c−i ∈ D−i , ci ∈ Ci \ D i . Set A(c) = arg maxy∈R(i,c−i ) pi,y − ω∈Ω′ ci (ω)yω
and qj (c) = pj,A(c) for all players j. Note that P
(ci , c−i ) figures in (2) only for player i. Crucially,
note that since y = x(mi ,c−i ) ∈ R(i, c−i ) and
ω∈Ω ci (ω)yω = 0 by definition, we always have
qi (c) − EA [ci (A(c))] ≥ 0. Thus, by definition, and by (2), we have ensured that M is supportbased (IC, IR)-in-expectation and its expected disutility is exactly the value of (x, p). This can be
modified so that IR holds with probability
P 1.
The above procedure is efficient if ω∈Ω′ ci (ω)xc,ω can be calculated efficiently. This is clearly
true if |Ω′ | is polynomially bounded, but it could hold under weaker conditions as well.
Corollary 3.3 Given an optimal algorithm for the CM problem, we can efficiently obtain an optimal support-based-(IC-in-expectation, IR) mechanism for the PayM problem in multidimensional
settings with additive types.
Using approximation algorithms. The CM problem is however often NP-hard (e.g., for vertex
cover), and we would like to be able to exploit approximation algorithms for the CM problem to
obtain near-optimal mechanisms. The usual approach is to use an approximation algorithm to
“approximately” separate over constraints (5).4 However, this does not work here since the CM
problem that one needs to solve in the separation problem involves negative costs, which renders
the usual notion of approximation meaningless. Instead, if the CM problem admits a certain type of
LP-relaxation (C-P), then we argue that one can solve a relaxation of (P) where the allocation-set is
the set of extreme points of (C-P) (Theorem 3.4). For single-dimensional problems (Section 4), we
leverage this to obtain strong and far-reaching results. We show that a ρ-approximation algorithm
relative to (C-P) can be used to “round” the optimal solution to this relaxation to a supportbased-(IC-in-expectation, IR)-mechanism losing a ρ-factor in the disutility (Theorem 4.2). Thus,
we obtain near-optimal mechanisms for a variety of single-dimensional problems.
Suppose that the CM problem admits an LP-relaxation of the following form, where c =
{ci,v }i∈[n],v∈Ti is the input type-profile.
min

cT x + dT z

Ax + Bz ≥ b,

s.t.

x, z ≥ 0.

(C-P)

Intuitively x encodes the allocation chosen, and dT z encodes pub(.). For x ≥ 0, define z(x) :=
arg min{dT z : (x, z) is feasible to (C-P)}; if there is no z such that (x, z) is feasible to (C-P), set
z(x) := ⊥. Define ΩLP := {x : z(x) 6= ⊥, 0 ≤ xi,v ≤ 1 ∀i, v ∈ Ti }. We require that: (a) a
{0, 1}-vector x is in ΩLP iff it is the characteristic vector of an allocation ω ∈ Ω, and in this case,
we have dT z(x) = pub(ω); (b) A ≥ 0; (c) for any input c ≥ 0 to the covering problem, (C-P) is
not unbounded, and if it has an optimal solution, it has one where x ∈ ΩLP ; (d) for any c, we can
efficiently find an optimal solution to (C-P) or detect that it is unbounded or infeasible.
We extend
the type ci of each player i and pub to assign values also to points in ΩLP : define
P
ci (x) = v∈Ti ci,v xi,v and pub(x) = dT z(x) for x ∈ ΩLP . Let Ωext denote the finite set of extreme
points of ΩLP . Condition (a) ensures that Ωext contains the characteristic vectors of all feasible
allocations. Let (P’) denote the relaxation of (P), where we replace the set of feasible allocations
Ω with Ωext (so ω indexes Ωext now), and for c ∈ D with ci = mi 1(Ti ), we now define Ω(c) :=
4

For revenue-maximization problems in packing domains, this simple approach does indeed work in singledimensional settings and settings with additive types. This is because the dual separation problem is now an SWM
problem, and it is easy to use a ρ-approximation algorithm for the SWM problem for nonnegative inputs to obtain
a ρ-approximate solution with arbitrary, positive or negative, inputs. This yields a simple extension of some of the
results in [8]; see Appendix C.1.

11

{ω ∈ Ωext : ωi,v = 0 ∀v ∈ Ti }. Since one can optimize efficiently over ΩLP , and hence Ωext , even for
negative type-profiles, we have the following.
Theorem 3.4 We can efficiently compute an optimal solution to (P’).

4

Single-dimensional problems

Corollary 3.3 immediately yields results for certain single-dimensional problems (see Table 1), most
notably, single-item procurement auctions. We now substantially expand the scope of PayM problems for which one can obtain near-optimal mechanisms by showing how to leverage “LP-relative”
approximation algorithms for the CM problem. (As noted earlier, and sketched in Appendix C.1,
a simpler approach can be used to leverage approximation algorithms for revenue-maximization
in packing domains.) Suppose that the CM problem can be encoded as (C-P). An LP-relative
ρ-approximation algorithm for the CM problem is a polytime algorithm that for any input c ≥ 0 to
the covering problem, returns a {0, 1}-vector x ∈ ΩLP such that cT x + dT z(x) ≤ ρOPT C-P . Using
the convex-decomposition procedure in [12] (see Section 5.1 of [12]), one can show the following;
the proof appears at the end of this section.
Lemma 4.1 Let x ∈ ΩLP . Given an LP-relative ρ-approximation
algorithm A for the CM problem,
P
one can efficiently obtain (λ(1) , x(1) ), . . . , (λ(k) , x(k) ), where ℓ λ(ℓ) = 1, λ ≥ 0, and x(ℓ) is a {0, 1}P
P
(ℓ)
vector in ΩLP for all ℓ, such that ℓ λ(ℓ) xi,v = min(ρxi,v , 1) for all i, v ∈ Ti , and ℓ λ(ℓ) dT z(x(ℓ) ) ≤
ρdT z(x).
Theorem 4.2 Given an LP-relative ρ-approximation algorithm for the CM problem, one can obtain a polytime ρ-approximation support-based-(IC-in-expectation, IR) mechanism for the PayM
problem.
Proof : We solve (P’) to obtain an optimal solution (x, p). Since |Ti | = 1 for all i, it will be
convenient to view ω ∈ ΩLP as a vector {ωi }i∈[n] ∈ [0, 1]n , where ωi ≡ ωi,v for the single covering
P
object v ∈ Ti . Fix c ∈ D. Define yc = ω∈Ωext xc,ω ω (which can be efficiently computed since
P
P
x has polynomial support). Then, ω∈Ωext ci (ω)xc,ω =Pci yc,i and dT z(y) ≤ ω∈Ωext
Ppub(ω)xc,ω .
By Lemma 4.1, we can efficiently find a point ỹc =
x̃
ω,
where
x̃
≥
0,
c
ω∈Ω c,ω
w∈Ω x̃c,ω =
1, in the convex hull of the {0, 1}-vectors in ΩLP such that ỹc,i = min(ρyc,i , 1) for all i, and
P
T
w∈Ω x̃c,ω pub(ω) ≤ ρd z(y).
We now argue that one can obtain payments {qi,c } such that (x̃, q) is feasible to (P) and
qi,c ≤ ρpi,c for all i, c ∈ D. Thus, the value of (x̃, q) is at most ρ times the value of (x, p). Applying
Theorem 3.2 to (x̃, q) yields the desired result.
Fix i and c−i ∈ D−i . Constraints (4) and (2) ensure that y(mi ,c−i ),i = 0, and y(ci ,c−i ),i ≥ y(c′i ,c−i ),i
for all ci , c′i ∈ Di s.t. ci < c′i . Hence, ỹ(mi ,c−i ),i = 0, ỹ(ci ,c−i ),i ≥ ỹ(c′i ,c−i ),i for ci , c′i ∈ Di , ci > c′i .
Define qi,(mi ,c−i ) = 0. Let 0 ≤ c1i < c2i < . . . < cki i be the values in Di . For ci = cℓi , define
qi,(ci ,c−i ) = ci ỹ(ci ,c−i ),i +

ki
X

(cti − ct−1
i )ỹ(cti ,c−i ),i .

t=ℓ+1

P

Since ω∈Ω ci (ω)x̃(ci ,c−i ),ω = ci ỹ(ci ,c−i ),i , (3) holds. By construction, for consecutive values ci =

cℓi , c′i = cℓ+1
i , we have qi,(ci ,c−i ) − qi,(c′i ,c−i ) = ci ỹ(ci ,c−i ),i − ỹ(c′i ,c−i ),i , which is at most


ρ · ci y(ci ,c−i ),i − y(c′i ,c−i ),i ≤ ρ pi,(ci ,c−i ) − pi,(c′i ,c−i ) .
12

Since qi,(mi ,c−i ) = 0 ≤ ρpi,(mi ,c−i ) , this implies that qi,(ci ,c−i ) ≤ ρpi,(ci ,c−i ) . Finally,
 it is easy to verify
that for any ci , c′i ∈ Di , we have qi,(ci ,c−i ) − qi,(c′i ,c−i ) ≥ ci ỹ(ci ,c−i ),i − ỹ(c′i ,c−i ),i , so (x̃, q) satisfies
(2).
Corollary 3.3 and Theorem 4.2 yield polytime near-optimal mechanisms for a host of singledimensional PayM problems. Table 1 summarizes a few applications. Even for single-item procurement auctions, these are the first results for PayM problems with correlated players satisfying a
notion stronger than (BIC, interim IR).
Problem

Approximation

Single-item procurement auction: buy one item provided
by n players
Metric UFL: players are facilities, output should be a
UFL solution
Vertex cover: players are nodes, output should be a vertex cover
Set cover: players are sets, output should be a set cover
Steiner forest: players are edges, output should be a
Steiner forest
Multiway cut (a), Multicut (b): players are edges, output
should be a multiway cut in (a), or a multicut in (b)

Due to

1

Corollary 3.3

1.488 using [15]

Theorem 4.2

2

Theorem 4.2

O(log n)
2

Theorem 4.2
Theorem 4.2

2 for (a)
O(log n) for (b)

Theorem 4.2

Table 1: Results for some representative single-dimensional PayM problems.
Proof of Lemma 4.1 : It suffices to show that the LP (Q) can be solved in polytime and its optimal
value is 1. Throughout, we use ℓ to index {0, 1} vectors in ΩLP . (Recall that these correspond to
feasible allocations.)
X

max
s.t.

λ(ℓ)

X


λ(ℓ) dT z(x(ℓ) ) ≤ ρdT z(x)

(ℓ)

X

X

min(ρxi,v , 1)αi,v + ρdT z(x) · β + θ

X


(ℓ)
xi,v αi,v + dT z(x(ℓ) ) β + θ ≥ 1

(R)

i,v∈Ti

λ(ℓ) xi,v = min(ρxi,v , 1) ∀i, v ∈ Ti

ℓ

min

ℓ

X
ℓ

(Q)

λ(ℓ) ≤ 1

(8)

s.t.

i,v∈Ti

(9)

∀ℓ (11)

β, θ ≥ 0.

(10)

ℓ

λ ≥ 0.

Here the αℓ s, β and θ are the dual variables corresponding to constraints (8), (9), and (10)
respectively. Clearly, OPT (R) ≤ 1 since θ = 1, αi,v = 0 = β for all i, v is a feasible dual solution.
Suppose (α̂, β̂, θ̂) is a feasible dual solution of value less than 1. Set α̃i,v = α̂i,v if α̂i,v ≥ 0 and
ρxi,v ≤ 1, and α̃i,v = 0 otherwise. Let Γ = 1 if β̂ > 0 and equal to 2N dT z otherwise, where N is
β̂

is such that for all {0, 1}-vectors x(ℓ) ∈ ΩLP , we have that cT x(ℓ) > cT x implies cT x(ℓ) ≥ cT x + N1 .
Note that we can choose N so that its size is poly(I, size of x). Consider the CM problem defined
by the input Γα̃. Running A on this input, we obtain a {0, 1}-vector x(ℓ) ∈ ΩLP whose total cost
is at most ρ times the cost of the fractional solution x, z(x) . This translates to

X
X (ℓ)

xi,v α̃i,v + dT z(x) · β̂ .
(12)
xi,v α̃i,v + dT z(x(ℓ) ) β̂ ≤ ρ
i,v

i,v

13

Now augment x(ℓ) to the following {0, 1}-vector x̂: set x̂i,v = 1 if ρxi,v > 1 or α̂i,v < 0, and
(ℓ)
xi,v otherwise. Then x̂ is the characteristic vector of a feasible allocation, since we have only
added covering objects to the allocation
corresponding to x(ℓ) ; hence x̂ ∈ ΩLP . We have dT z(x̂) =

pub(x̂) ≤ pub(x(ℓ) ) = dT z(xℓ ) and
X
i,v

x̂i,v α̂i,v =

X

α̂i,v +

i,v:ρxi,v >1
or α̂i,v <0

X
i,v

Combined with (12), this shows that
X
X
x̂i,v α̂i,v + dT z(x̂)β̂ ≤
i,v

(ℓ)

xi,v α̃i,v ≤

X

min(ρxi,v , 1)α̂i,v +

i,v:ρxi,v >1
or α̂i,v <0

min(ρxi,v , 1)α̂i,v +

i,v:ρxi,v >1
or α̂i,v <0

=

X

X

(ℓ)

xi,v α̃i,v .

i,v

X

ρxi,v α̃i,v + ρdT z(x) · β̂

i,v:α̃i,v >0

min(ρxi,v , 1)α̂i,v + ρdT z(x) · β̂ < 1 − θ̂

i,v

which contradicts that (α̂, β̂, θ̂) is feasible to (R). Hence, OPT (Q) = OPT (R) = 1.
P
Thus, we can add the constraint i,v∈Ti min(ρxi,v , 1)αi,v + ρdT z(x) · β + θ ≤ 1 to (R) without
altering anything. If we solve the resulting LP using the ellipsoid method, and take the inequalities
corresponding to the violated inequalities (11) found by A during the ellipsoid method, then we
obtain a compact LP with only a polynomial number of constraints that is equivalent to (R). The
dual of this compact LP yields an LP equivalent to (Q) with a polynomial number of λ(ℓ) variables
which we can solve to obtain the desired convex decomposition.

5

Multidimensional problems

We obtain results for multidimensional PayM problems via two distinct approaches. One is by
directly applying Corollary 3.3 (e.g., Theorem 5.1). The other approach is based on again moving
to an LP-relaxation of the CM problem and utilizing Theorem 3.4 in conjunction with a stronger
LP-rounding approach. This yields results for multidimensional (metric) UFL and its variants
(Theorem 5.3).
Multi-item procurement auctions. Here, we have n sellers and k (heterogeneous) items. Each
seller i has a supply vector si ∈ Zk+ denoting his supply for the various items, and the buyer has a
demand vector d ∈ Zk+ specifying his demand for the various items. This is public knowledge. Each
seller i has a private cost-vector ci ∈ Rk+ , where ci,ℓ is the cost he incurs for supplying one unit
of item ℓ. A feasible solution is an allocation specifying how many units of each item each seller
supplies to the buyer such that for each item ℓ, each seller i provides at most si,ℓ units of ℓ and
the buyer obtains dℓ total units of ℓ. The corresponding CM problem is a min-cost flow problem
(in a bipartite graph), which can be efficiently solved optimally, thus we obtain a polytime optimal
mechanism.
Theorem 5.1 There is a polytime optimal support-based-(IC-in-expectation, IR) mechanism for
multi-unit procurement auctions.

14

Multidimensional budgeted (metric) uncapacitated facility location (UFL). Here, we
have a set E of clients that need to be serviced by facilities, and a set F of locations where facilities
may be opened. Each player i may provide facilities at the locations in Ti ⊆ F. We may assume
that the Ti s are disjoint. For each facility ℓ ∈ Ti that is opened, i incurs a private opening cost
fℓ ≡ fi,ℓ , and assigning client j to an open facility ℓ incurs a publicly-known assignment cost dℓj ,
where the dℓj s form a metric. We are also given a public assignment-cost budget B. The goal
in Budget-UFL is to open a subset
F ⊆P
F of facilities and assign
P
P each client j to an open facility
σ(j) ∈ F so as to minimize ℓ∈F fℓ + j∈E dσ(j)j subject to j∈E dσ(j)j ≤ B; UFL is the special
case where B = ∞. We can define pub(T1 , . . . , Tn ) to be the total assignment cost if this is at most
B, and ∞ otherwise.
Let O∗ denote the expected disutility of an optimal mechanism for Budget-UFL. We obtain
a mechanism with expected disutility at most 2O∗ that always returns a solution with expected
assignment cost at most 2B. Consider the following LP-relaxation for Budget-UFL.
X
X
min
f ℓ xℓ +
dℓj zℓj s.t.
(BFL-P)
X

j∈E,ℓ∈F

ℓ∈F

dℓj zℓj ≤ B,

X

j∈E,ℓ∈F

zℓj ≥ 1 ∀j ∈ E,

0 ≤ zℓj ≤ xℓ ∀ℓ ∈ F, j ∈ E.

ℓ∈F

Let (FL-P) denote (BFL-P) with B = ∞, and OPT FL-P denote its optimal value. We say that
an algorithm A is a Lagrangian multiplier preserving (LMP)Pρ-approximation
algorithm for UFL if
P
for every instance, it returns a solution (F, σ) such that ρ ℓ∈F fℓ + j∈E dσ(j)j ≤ ρ · OPT FL-P .
In [17], it is shown that given such an algorithm A, one can take any solution (x, z) to (FL(k)
(k) , σ (k) )—so
P) andPobtain a convex combination
of UFL solutions (λ(1)P
; F (1) , σ (1)
P), . . . , (λ  ; F P
P
(r)
(r)
(r)
λ ≥ 0, r λ = 1—such that r:ℓ∈F (r) λ = xℓ for all ℓ and r λ
j,ℓ dℓj zℓj .
j dσ(r) (j)j ≤ ρ
An LMP 2-approximation algorithm for UFL is known [10].
Lemma 5.2 Given an LMP ρ-approximation algorithm for UFL, one can design a polytime supportbased-(IC-in-expectation, IR) mechanism for Budget-UFL whose expected disutility is at most ρO ∗
while violating the budget by at most a ρ-factor.
Proof : The LP-relaxation (BFL-P) for the CM problem is of the form (C-P) and satisfies the
required properties. Recall that for x ≥ 0, z(x) denotes the min-cost completion of x to a feasible
solution to (BFL-P) if one exists, and is ⊥ if there is no such completion of x. Let ΩLP := {x :
z(x) 6= ⊥, 0 ≤ xℓ ≤ 1 ∀ℓ}. For integral ω ∈ ΩLP , z(ω) specifies the assignment where each client
j is assigned to the nearest open facility. By Theorem 3.4, one can efficiently compute an optimal
solution (X, p) to the relaxation of (P) where the set of feasible allocations is the set Ωext of extreme
points of ΩLP .
We round (X, p) to a feasible solution to (P) by proceeding as in the proof of Theorem 4.2.
Let ΩUFL be the set of characteristic vectors of open facilities of all integral UFLP
solutions. We
yc = ω∈Ωext Xc,ω ω,
useP
ℓ to index facilities inPF and j to index clients
P
P in E. Fix c ∈ D. Define
zc,ℓj dℓj ≤ B. We use
so w∈Ωext ci (ω)Xc,ω = ℓ∈Ti fℓ yc,ℓ . Let zc = ω∈Ωext Xc,ω z(ω), so j,ℓP
the LMP ρ-approximation algorithm to express yc as a convex
PcombinationP ω∈ΩUFL x̃c,ω ω of (integral)
UFL-solutions
such
that
the
expected
assignment
cost
ω∈ΩUFL x̃c,ω
j,ℓ z(ω)ℓj dℓj is at most
P
ρ j,ℓ dℓj zc,ℓj ≤ ρB. Hence, (x̃, p) is a feasible solution to (P). Theorem 3.2 now yields the desired
mechanism.

15

Theorem 5.3 There is a polytime support-based-(IC-in-expectation, IR) mechanism for BudgetUFL with expected disutility at most 2O∗ , which always returns a solution with expected assignment
cost at most 2B.

6

Extensions: alternative solution concepts

We now investigate the PayM problem under various alternative solution concepts. In Section 6.1,
we consider solution concepts weaker than support-based (IC, IR), but yet robust enough to ensure
that truthful participation is an ex-post no-regret choice for every player at every type profile in
the support of the underlying distribution. We show that all our guarantees extend readily to
these solution concepts. (Note that a weaker solution concept does not necessarily mean that the
corresponding PayM mechanism-design problem is a simpler problem; a weaker solution concept
enlarges the space of allowed mechanisms, which could make it more- or less- difficult to search for
an optimal mechanism.) In Section 6.2, we consider the stronger solution concept of (DSIC (inexpectation, IR), and obtain results for single-dimensional settings but at the expense of increasing
the running time to exponential in the number of players.

6.1

Solution concepts weaker than support-based (IC, IR)

Consider the following weakenings of support-based (IC, IR) (Definition 2.2).
For every player i,
ui (ci , c−i ; ci ) ≥ ui (ci , c−i ; ci ),

ui (ci , c−i ; ci ) ≥ 0,

for all (ci , c−i ) ∈ D, ci : (ci , c−i ) ∈ D

(13)

ui (ci , c−i ; ci ) ≥ ui (ci , c−i ; ci ),

ui (ci , c−i ; ci ) ≥ 0,

for all (ci , c−i ) ∈ D, ci ∈ Ci

(14)

ui (ci , c−i ; ci ) ≥ ui (ci , c−i ; ci ),

ui (ci , c−i ; ci ) ≥ 0,

for all ci , ci ∈ Di , c−i ∈ D−i

(15)

All three solution concepts, (13)–(15), ensure that truthful participation is in the best interest
of every player i at every type-profile in D even at the ex-post stage when he knows the realized
types of all players, but for varying choices of lies: in (14), the lie could be anything, so a mechanism
satisfying (14) is (BIC, interim IR) for every distribution whose support is a subset of D; in (15),
the “best interest” is among lies consistent with i’s support; and in (13), the “best interest” is
among lies consistent with the support of the distribution.
We now argue that our results extend to these notions. For notions (13) and (15), one can
simply incorporate all the IC and IR constraints in the LP. Note that there are O(n|D|2 ) such
constraints under (13), and O(n|D|3 ) constraints under (15), so the size of the resulting LP is
poly(n, |D|). Theorem 3.1 continues to hold for the resulting LP, due to the same arguments. For
both notions, an LP solution immediately yields a randomized mechanism satisfying that notion,
except that utility is replaced by expected utility; for type profiles not included in the LP, we
may output any outcome ω0 (and any prices). The refinements for single-dimensional settings and
multidimensional FL work in the same fashion as before: the appropriate LP (e.g., (P’)) is modified
to include the appropriate set of IC and IR constraints and solved as before. The rounding of an
LP solution to obtain a suitable mechanism proceeds as before. Consequently, all of our results
extend to these two notions with minimal effort.
For notion (14), we incorporate constraints (14) but restrict ci to lie in D i . Recall that D i =
Di ∪ {mi 1Ti }. We also include constraints (4) as before. Again, the resulting LP can be solved
given an optimal algorithm for the CM problem. The LP solution can be extended to a mechanism
exactly as in Theorem 3.2, and it is easy to see that this extension satisfies (14). Therefore, all our
results extend to this notion as well.
16

6.2

Dominant-strategy IC mechanisms

We can strengthen our results from Section 4 to obtain (near-) optimal dominant-strategy incentive
compatible (DSIC) mechanisms for single-dimensional problems in time exponential in n. Thus, we
obtain polytime mechanisms for any constant number of players.
The key change is in Q
the LP (P) (or (P’)), where we now enforce (1)–(4) for every player i
and every type profile in i D i . (Note that, as before, we can only enforce IC and IR constraints
for a finite set of type profiles.) Theorem 3.1, as also the rounding procedure and arguments in
Theorem 4.2 proceed essentially identically to yield a near-optimal solution to
Q this LP. We prove
that in single-dimensional settings, enforcing the IC, IR constraints for the set i Di of type profiles
enables one to extend the LP solution to a (DSIC-in-expectation, IR) mechanism without increasing
the expected disutility. Thus, we obtain the same guarantees as in Table 1, but under the stronger
solution concept of (DSIC-in-expectation, IR).
We focus on single-dimensional settings here because at various places, our arguments rely on
the well-known equivalence between monotonic allocation rules and DSIC-implementable allocation
rules. We do not know if a similar result holds for multidimensional settings. This, and various
other unanswered questions emerge from our result; we mention a few of these below, before delving
into our construction for single-dimensional settings.
(a) In multidimensional settings, what finite subsets C ′ ⊆ C of the type space have the property
that enforcing the IC and IR constraints for every player i and every type profile in C ′ suffice
to extend an LP solution to a (DSIC-in-expectation, IR mechanism)?
Q
(b) Does C ′ = i D i have this extension property (as is the case in single-dimensional settings)?
(c) Is there some C ′ of size poly(n, |D|) with this extension property?

We now describe briefly the changes required to obtain (DSIC-in-expectation, IR) mechanisms.
Analogous to Lemma 2.3, we can
Q obtain estimates mi such that there is an optimal mechanism
M ∗ such that on any input c ∈ i (Di ∪ {mi }) where ci < mi for at least one i, M ∗ only buys the
item with
probability
from a player i with ci < mi (the same proof approach works). Let
Q
Q non-zero
e
ei := Di := Di ∪ {mi } for uniformity of notation. For
e
D := i D i and D−i := j6=i D j ; also, let D
e define Ω(c) = {ω ∈ Ω : ωi = ∅ for all i s.t. ci = mi }, if there is some i such that ci < mi ,
c ∈ D,
and Ω otherwise. In our LP (P), or its relaxation (P’) (where we move to an LP-relaxation of the
ei
CM problem and consider the allocation-set Ωext ), we now enforce (1)–(4) for all i, all ci , c′i ∈ D
e−i .
and all c−i ∈ D
Let (K-P), and (K-P’) (with allocation-set ΩLP ) denote these new LPs. When n is a constant,
both LPs have a polynomial number of constraints. So again by considering the dual, we can
efficiently compute: (i) an optimal solution to (K-P) given an optimal algorithm for the CM
problem; and (ii) an optimal solution to (K-P’). If the CM problem can be encoded via (C-P)
and we have an LP-relative approximation algorithm for the CM problem, then one can use the
rounding procedure described in Theorem 4.2 to round the optimal solution to (K-P’) to a nearoptimal solution to (K-P); the arguments are essentially identical.
So suppose that we have a near-optimal solution
(x, p) to (K-P). We extend (x, p) to a (DSIC
in-expectation, IR) mechanism M = A, {qi } without increasing the expected disutility. Here,
A(c) and qi (c) denote
as before the allocation-distribution and expected payment to i, on input c.
P
Define yc = ω xc,ω ω, where we treat ω as a vector in {0, 1}n with ωi ≡ ωi,v for the single
covering object v ∈ Ti . Let 0 ≤ c1i < c2i < . . . < cki i = cmax
be the values in Di , and set ciki +1 := mi .
i

e as follows: set H(c) := Hi (ci )
Define the mapping H : C → D
, where Hi (ci ) is cr+1
if
i
i=1,...,n

r+1
r
ci ∈ (ci , ci ], r ≤ ki , and mi if ci ≥ mi . Define H−i (c−i ) := Hj (cj ) j6=i .
17

Consider c ∈ C. If ci ≤ cmax
for at least one i, we set A(c) = yH(c) . If ci > cmax
for all i, we set
i
i
A(c) as in the VCG mechanism. Since we are in the single-dimensional setting, if we show that for
all i, c−i ∈ C−i , A(c)
R ∞ i is non-increasing in ci and hits 0 at some point, then we know that setting
qi (c) = ci A(c)i + ci A(t, c−i )i dt ensures such that M = A, {qi } is (DSIC, IR)-in-expectation.
Consider some i, c−i ∈ C−i . If cj ≤ cmax
for some j 6= i, then A(c) = yH(c) . Since Hi is
j
non-decreasing in ci and yc,i is non-increasing in ci (which is easily verified), it follows that A(c)i
e−i , then one can argue as in the proof of Theorem 4.2 that
is non-increasing in ci . Also, if c−i ∈ D
P
qi (c) ≤ pi,c . Hence, M has expected total payment at most c,i PrD (c)pi,c . Suppose cj > cmax
for
j
all j 6= i. Then, Hj (cj ) = mj for all j 6= i. So A(c) = yH(c) for ci ≤ cmax
,
and
is
the
VCG
allocation
i
max , and the VCG allocation for c > cmax , which is
for ci > cmax
.
Therefore,
A(c)
=
1
for
c
≤
c
i
i
i
i
i
i
clearly non-increasing in ci .
Theorem 6.1 For single-dimensional problems with a constant number of players, we obtain the
same guarantees as in Table 1, but under the stronger solution concept of DSIC-in-expectation and
IR.

Acknowledgments
We thank the anonymous reviewers and referees of the conference and journal submissions for
various useful comments. Section 6.1 was prompted by questions raised by an anonymous referee
of the journal submission regarding the solution concepts (13)-(15).

References
[1] S. Alaei, H. Fu, N. Haghpanah, J. Hartline, and A. Malekian. Bayesian optimal auctions via
multi- to single-agent reduction. In Proc., EC, 17, 2012.
[2] Y. Cai, C. Daskalakis, and S. Weinberg. Optimal multi-dimensional mechanism design: reducing revenue to welfare maximization. In Proc., FOCS, 130–139, 2012.
[3] Y. Cai, C. Daskalakis, and S. Weinberg. Reducing revenue to welfare maximization: approximation algorithms and other generalizations. In Proc., SODA, 2013.
[4] Y. Cai, C. Daskalakis, and S. M. Weinberg. Understanding incentives: mechanism design
becomes algorithm design. In Proc., FOCS, 2013.
[5] S. Chawla, J. Hartline, D. Malec, and B. Sivan. Multi-parameter mechanism design and
sequential posted pricing. In Proc., STOC, 311–320, 2010.
[6] J. Crémer, and R. McLean. Optimal selling strategies under uncertainty for a discriminating
monopolist when demands are interdependent. Econometrica, 53, 2, 345–361, 1985.
[7] J. Crémer, and R. McLean. Full extraction of the surplus in Bayesian and dominant strategy
auctions. Econometrica 56, 6, 1247–1257, 1988.
[8] S. Dobzinski, H. Fu, and R. Kleinberg. Optimal auctions with correlated bidders are easy. In
Proc. STOC, 129–138, 2011.
[9] S. Hart and N. Nisan. Approximate revenue maximization with multiple items. In Proc., EC,
656, 2012.
18

[10] K. Jain, M. Mahdian, E. Markakis, A. Saberi, and V. Vazirani. Greedy facility location
algorithms analyzed using dual fitting with factor-revealing LP. J. ACM, 50:795–824, 2003.
[11] K. Jain, M. Mahdian, and M. Salavatipour. Packing Steiner trees. In Proc. SODA, pages
266–274, 2003.
[12] R. Lavi and C. Swamy. Truthful and near-optimal mechanism design via linear programming.
Journal of the ACM, 58(6): 25, 2011.
[13] P. Klemperer. Auction theory: A guide to the literature. Journal of Economic Surveys 13,
227–286, 1999.
[14] V. Krishna. Auction Theory. Academic Press, 2010.
[15] S. Li. A 1.488 approximation algorithm for the uncapacitated facility location problem. Inf.
Comput., 222:45–58, 2013.
[16] R. McAfee and P. Reny. Correlated information and mechanism design. Econometrica 60, 2,
395–421, 1992.
[17] H. Minooei and C.
covering problems.

Swamy.
Truthful mechanism design for multidimensional
In Proc., WINE, 448–461, 2012.
Detailed version at
http://www.math.uwaterloo.ca/~cswamy/papers/coveringmech-arxiv.pdf.

[18] H. Minooei and C. Swamy. Near-optimal and robust mechanism design for covering problems
with correlated players. In Proc. WINE, 2013.
[19] R. Myerson. Optimal auction design. Math. of Operations Research, 6:58–73, 1981.
[20] N. Nisan, T. Roughgarden, É. Tardos, and V. Vazirani. Algorithmic Game Theory. Cambridge
University Press, September 2007.
[21] C. Papadimitriou and G. Pierrakos. On optimal single-item auctions. In Proc., STOC, 119–128,
2011.
[22] A. Ronen. On approximating optimal auctions. In Proc. EC, 11–17, 2001.
[23] A. Ronen and D. Lehmann. Nearly optimal multi attribute auctions. In Proc. EC, pages
279–285, 2005.
[24] A. Ronen and A. Saberi. On the hardness of optimal auctions. In Proc., FOCS, 396–405, 2002.
[25] T. Roughgarden and I. Talgam-Cohen. Optimal and near-optimal mechanism design with
interdependent values. In Proc., EC, 767–784, 2013.

19

A

Proof of Lemma 2.3

Consider the following LP, which is the same as (P) except that we only consider c ∈
X

X
X
min
PrD (c)
qi,c + κ
xc,ω pub(ω)
c∈D

s.t.

ω

i

X

∀c ∈

xc,ω = 1

ω

qi,(ci ,c−i ) −

X

ci (ω)x(ci ,c−i ),ω ≥ qi,(c′i ,c−i ) −

qi,(ci ,c−i ) −

X

ci (ω)x(ci ,c−i ),ω ≥ 0

ω

X

S

i (Di × D−i ).

[
(Di × D−i )

(LP)
(16)

i

ci (ω)x(c′i ,c−i ),ω ∀i, ci , c′i ∈ Di , c−i ∈ D−i (17)

ω

∀i, ci ∈ Di , c−i ∈ D−i

(18)

ω

q, x ≥ 0.
(19)

Let M = A, {pi } be an optimal mechanism. Recall that O∗ is the expected disutility of
M . Then, M naturally yields a feasible solution (x, q) to (LP) of objective value O∗ , where
xc,ω = PrM [A(c) = ω] and qi,c = EM [pi (c)]. Let (x̂, q̂) be an optimal basic solution to (LP). Then,
for some N such that log N is polynomially bounded in the input size I, we can say that the
1
values
S of all variables are integer multiples of N , and log(N x̂c,ω ), log(N q̂i,c ) = poly(I) for all i,
c ∈ i (Di × D−i ), ω.
First, we claim that we may assume that for every i, ci ∈ Di , c−i ∈ D−i , if whenever x̂c,ω > 0
we
P have ωi = ∅ (where c = (ci , c−i )), then q̂i,c = 0. If not, then (17) implies that q̂i,(c̃i ,c−i ) −
ω c̃i (ω)x(c̃i ,c−i ),ω ≥ q̂i,c for all c̃i ∈ Di and decreasing q̂i,(c̃i ,c−i ) by q̂i,c for all c̃i ∈ Di continues to
satisfy (17)–(19).

P
P
Set mi := max 2 i,v∈Ti maxci ∈Di ci,v , N i,c q̂i,c for all i. So log mi = poly(I). Recall that
S
D i := Di ∪ {mi 1Ti } for all i ∈ [n], and D := i (D i × D−i ).
S
Now we extend (x̂, q̂) to (x̃, q̃) that assigns values also to type-profiles in D\ i (Di ×D−i ) so that
′
constraints
(16)–(19) hold for all i, cS
i , ci ∈ D i , c−i ∈ D−i . First set x̃c,ω = x̂c,ω , q̃i,c = q̂i,c for all i, ω,
S
c ∈ i (Di × D−i ). Consider c ∈ D \ i (Di × D−i ), and let i be such that ci = mi 1Ti (there is exactly
one such i). We “run” VCG on c considering
only the cost incurred by the
P
Pplayers. That
P is, we set
x̃c,ω = 1 for ω = ω(c) := arg minω∈Ω i ci (ω) and pay q̃i,c = minω∈Ω:ωi =∅ j cj (ω) − j6=i cj ω(c)
to each player i. Note that the choice of mi ensures that ω(c)i = ∅ and hence, q̃i,c = 0.
We claim that this extension satisfies (16)–(19) for all i, ci , c′i ∈ Di , c−i ∈ D−i . Fix i, ci , c′i ∈ D i ,
c−i ∈ D−i . It is clear that (16), (19) hold. If ci ∈ Di , then (18) clearly holds; if ci = mi 1Ti , then
it again holds since x̃c,ω = 1 for ω = ω(c) and ω(c)i = ∅. To verify (17), we consider four cases.
If ci , c′i ∈ Di , then (17) holds since (x̃, q̃) extends (x̂, q̂). If ci = c′i = mi 1Ti , then (17) trivially
holds. If ci ∈ Di , c′i = mi 1Ti , then (17) holds since the RHS of (17) is 0 (as x̃(c′i ,c−i ),ω(c′i ,c−i ) = 1
and ω(c′i , c−i )i = ∅). We are left with the case ci = mi 1Ti and c′i ∈ Di . If whenever x̃(c′i ,c−i ),ω =
′
x̂(c′i ,c−i ),ω > 0 we have ωi = ∅, then we also have q̃i,(c′i ,c−i ) =
claim, so
Pq̂i,(ci ,c−i ) = 0 by ourmearlier
i
the RHS of (17) is 0, and (17) holds. Otherwise, we have ω ci (ω)x̃(c′i ,c−i ),ω ≥ N ≥ q̂i,(c′i ,c−i ) , so
the RHS of (17) is at most 0, and (17) holds.
Thus, we have shown that (x̃, q̃) is a feasible solution to (P). Now we can apply Theorem 3.2 to
extend (x̃, q̃) and obtain
IR) mechanism M ∗ whose expected

P a support-based-(IC-in-expectation,
P
∗
disutility is at most c,i PrD (c) q̃i,c + ω x̃c,ω pub(ω) ≤ O . Since x̃(mi 1Ti ,c−i ),ω > 0 implies that
ωi = ∅ for all i, M ∗ satisfies the required conditions.

20

B

Inferiority of k-lookahead procurement auctions

The following k-lookahead auction was proposed by [8] for the single-item revenue-maximization
problem generalizing the 1-lookahead auction considered by [22, 24]: on input v = (v1 , . . . , vn ), pick
the set I of k players with highest values, and run the revenue-maximizing (DSIC, IR) mechanism
for player-set I where the distribution we use for I is the conditional distribution of the values
for I given the values (vi )i∈I
/ for the other players. Dobzinski et al. [8] show that the k-lookahead
auction achieves a constant-fraction of the revenue of the optimal (DSIC, IR) mechanism.
For any k ≥ 2, we can consider an analogous definition of k-lookahead auction for the single-item
procurement problem: on input c, we pick the set I of k players with smallest costs, and run the
payment-minimizing support-based-(IC-in-expectation, IR) mechanism for I for the conditional
distribution of I’s costs given (ci )i∈I
/ . We call this the k-lookahead procurement auction. The
following example shows that the expected total payment of the k-lookahead procurement auction
can be arbitrarily large, even when k = n − 1 (that is, we drop only 1 player), and compared to
the optimal expected total payment of even a deterministic (DSIC, IR) mechanism.
Let t = K + ǫ where ǫ > 0, and δ > 0. The distribution D consists of n points: each c in
1−δ
, and the
{c : cn = t, ∃i ∈ [n − 1] s.t. ci = 0, cj = K ∀j 6= i, n} has probability PrD (c) = n−1
type-profile c where ci = K ∀i 6= n, cn = t has probability PrD (c) = δ.
Let k = n − 1. The k-lookahead procurement auction will always select the player-set I =
{1, . . . , n − 1}, and the conditional distribution of values of players in I is simply D. Let M ′ be
the support-based-(IC-in-expectation, IR) mechanism for the players in I under this conditional
distribution D. Suppose that on input (K, K, . . . , K, t), the k-lookahead
auction (which runs M ′ )
P
buys the item from player i ∈ I with probability xi . Clearly, i∈I xi = 1. Then, on the input c̃
where c̃i = 0, c̃j = K for all j 6= i, n, c̃n = t, the mechanism must also buy the item from player
i with probability at least xi since M ′ is support-based IC. So since M ′ is support-based (IC-inexpectation, IR), the payment to player i under input c̃ is at least K, and therefore the expected
P
1−δ
= K(1−δ)
total payment of the k-lookahead auction is at least K( i∈I xi ) · n−1
n−1 .

Now consider the following mechanism M = A, {pi } . Consider input c. If some player i < n
has ci = 0, M buys the item from such a player i (breaking ties in some fixed way). Otherwise, if
cn ≤ t, M buys from player n; else, M buys from the player i with smallest ci . It is easy to verify
that for every i and c−i , this allocation rule A is monotonically decreasing in ci . Let pi (c) = 0 if M
does not buy the item from i on input c, and max{z : M buys the item from i on input (z, c−i )}
otherwise. By a well-known fact, (see, e.g., Theorem 9.39 in [20]), M is DSIC and IR. Then, the
total payment under any c ∈ D for which ci = 0 for some i, is 0, and the total payment under the
input where ci = K for all i 6= n, cn = t is t. So the expected total payment of M is tδ.
K(1−δ)
, which can be
Thus the ratio of the expected total payments of M ′ and M is at least tδ(n−1)
made arbitrarily large by choosing δ and ǫ = t − K small enough.

C

Insights for revenue-maximization in packing domains

Our study of PayM problems also leads to some interesting insights into the revenue-maximization
problem in packing settings with correlated players. We state two results that are obtained via
relatively-simple observations, but we believe are nevertheless of interest.
In Section C.1, we justify our comment in the Introduction that the problem of extending an LP
solution to a suitable mechanism becomes much easier in a packing setting such as combinatorial
auctions (CAs). We show that any solution to an LP-relaxation similar to (P) for the revenuemaximization problem in CAs can be extended to a (DSIC-in-expectation, IR) mechanism without

21

any loss in revenue. In Section C.2, we obtain a noteworthy extension of a result in [8]. We show
that in single-dimensional packing settings, a ρ-approximation algorithm for the SWM problem
can be used to obtain a ρ-approximation (DSIC-in-expectation, IR)-mechanism for the revenuemaximization problem. We obtain this by noting that a ρ-approximation for the SWM problem can
be used to obtain a ρ-approximate separation oracle for the dual of the revenue-maximization LP,
despite the fact that the separation problem is an SWM problem possibly involving negative-valued
inputs5 , which then yields, in a fairly-standard way, a ρ-approximate solution to the revenuemaximization LP.

C.1

Extending LP solutions to (DSIC-in-expectation, IR) mechanisms

We consider the prototypical problem of combinatorial auctions; similar arguments can be made
for other packing domains. In CAs, a feasible allocation ω is one that allots a disjoint set ωi of
items (which could be empty) to each player i, and player i’s value under allocation ω is vi (ωi ),
where vi : 2[m] 7→ R+ is player i’s private valuation function.
Q We use vi (ω) to denote vi (ωi ). Let Vi
denote the set of all private types of player i, and V−i = j6=i Vj . As before, let Ω be the set of all
feasible solutions.
We consider the following LP along the lines of (P). Since we are in a packing setting, we do
not need the mi estimates. We may assume that each Di contains the valuation 0i , where 0i (ω) = 0
S
′
for all ω, since if not, we can just add this to Di , and set PrD (0i , v−i ) = 0. Let D := i (Di × D−i ).
X
X
max
PrD (v)
pi,v
(R-P)
v∈D

X

s.t.

i

ω∈Ω

X

vi (ω)x(vi ,v−i ),ω − pi,(vi ,v−i ) ≥

X

vi (ω)x(vi ,v−i ),ω − pi,(vi ,v−i ) ≥ 0

ω∈Ω

∀v ∈ D

xv,ω ≤ 1
X

vi (ω)x(vi′ ,v−i ),ω − pi,(vi′ ,v−i )

′

(20)

∀i, vi , vi′ ∈ Di , v−i ∈ D−i

ω∈Ω

∀i, v ∈ D

′

ω∈Ω

p, x ≥ 0.
The above LP-relaxation is similar to the LP in [8] for single-dimensional packing problems. For
CAs, the LP in [8] is subtly different from (R-P): their allocation variables encode the probability
that a player i receives a set S of items. If we let the allocation space in (R-P) be the set Ωext of
extreme points of the standard LP-relaxation for the CA problem, then our formulations coincide
since a feasible solution to the standard LP specifies the extent to which each player receives each
set. (The convex-decomposition technique in [12] directly implies that an integrality-gap verifying
ρ-approximation algorithm for the SWM problem can be used to decompose the fractional allocation
specified by the LP in [8] scaled by ρ into a distribution over Ω, and thereby obtain a solution to
(R-P).)
Let (x̃, p̃) be a solution
to (R-P). We convert (x̃, p̃) to a (DSIC-in-expectation, IR) mech
anism M = A, {qi } with no smaller expected total revenue. Here, A(v) and qi (v) are the
allocation-distribution and expected price of player i on input v. Since any support-based-(IC,
IR)-in-expectation mechanism yields a feasible solution to (R-P), this also shows that any supportbased-(IC, IR)-in-expectation mechanism for CAs can be extended to a (DSIC-in-expectation, IR)
mechanism without any loss in revenue.
5

Recall that negative costs are quite problematic for the CM problem, and hence, we had to resort to the method
outlined in Section 4.

22

Our argument is similar to that in the proof of Theorem 3.2, but the packing nature of the
problem simplifies things significantly. We may assume that all constraints (20) are tight; otherwise
P
′
if there is some v ∈ D with ω∈Ω x̃v,ω < 1, then letting ω 0 be allocation where ωi0 = ∅ for all i,
we can increase x̃v,ω0 to make this sum 1 without affecting feasibility.
′
First, we set A(v) = x̃v , qi (v) = p̃i,v for all v ∈ D and all i, so it is clear that the expected
total revenue of M is the value of (x̃, p̃).
If |{i : vi ∈
/ Di }| ≥ 2, then we give everyone the empty-set
and charge everyone 0. Otherwise,
P
(i) =
v
(ω)x̃
suppose vi ∈
/ Di , v−i ∈ D−i . Let v̄ (i) = arg maxṽi ∈Di
(ṽi ,v−i ),ω − p̃i,(ṽi ,v−i ) and ȳ
ω i
x̃(v̄(i) ,v−i ) . For ω ∈ Ω, let proji (ω) denote the allocation where player i receives ωi ⊆ [m], and the
other players receive ∅. Viewing A(v) as the random variable specifying the allocation selected,
(i)
we set A(v) = proji (ω)P
with probability ȳω . We set qi (v) = p̃i,(v̄(i) ,v−i ) . Since 0i ∈ Di , we have
EA [vi (A(v))] − qi (v) ≥ ω 0i (ω)x̃(0i ,v−i ),ω − p̃i,(0i ,v−i ) ≥ 0, so M is IR-in-expectation.
To see that M is DSIC in expectation, consider some i, vi , vi′ ∈ Vi , v−i ∈ V−i . If v−i ∈
/ D−i ,
then player i always receives the empty set and pays 0. Otherwise, we have ensured by definition
that player i does not benefit by lying.

C.2

Utilizing approximation algorithms for the SWM problem

We briefly sketch how to utilize a ρ-approximation algorithm for the SWM problem to obtain a
ρ-approximation (DSIC-in-expectation, IR)-mechanism for the revenue-maximization problem in
single-dimensional settings. Similar arguments apply to packing settings with additive types.
Consider again the LP (R-P). For all i, ω, we now have vi (ω) = vi αi,ω , where vi ∈ R is i’s
private type and αi,ω ≥ 0 is public knowledge. This is identical to the LP in [8] for single-parameter
revenue-maximization problems. It will be convenient to view ω ∈ Ω as the vector {αi,ω }i∈[n] ∈ Rn+ .
Since we are in a packing setting, Ω is downward closed, so ω ∈ Ω and ω ′ ≤ ω implies that ω ′ ∈ Ω.
The dual of (R-P) is:
X
min
γv
(R-D)
v

s.t.

X

X

i:v∈Di ×D−i vi′ ∈Di

X



vi (ω)yi,(vi ,v−i ),vi′ − vi′ (ω)yi,(vi′ ,v−i ),vi + vi (ω)βi,v

yi,(vi ,v−i ),vi′ − yi,(vi′ ,v−i ),vi

vi′ ∈Di



≤ γv
+ βi,vi ,v−i ≥ PrD (v)

′

∀v ∈ D , ω ∈ Ω
∀i, v ∈ D

y, β, γ ≥ 0.

′

(21)
(22)
(23)

P

Let optr be the common optimal value of (R-P) and (R-D). Define θiv = v′ ∈Di (vi yi,(vi ,v−i ),vi′ −
i
+ vi βi,v if v ∈ Di × D−i , and 0 otherwise. Then, the separation problem for (R-D)
P
′
amounts to determining if maxω∈Ω i θiv αi,ω ≤ γv for every v ∈ D ; that is, solving an SWM
problem over the allocation space Ω under the input θ v = {θiv }i∈[n] for every v. Given a ρapproximation algorithm A for the SWM problem (where ρ ≥ 1) that only works with nonnegative
inputs, we can obtain a ρ-approximate solution for the input θ v as follows. Set (θ + )vi := max(0, θiv ),
use A with the input (θ + )v = {(θ + )vi }i∈[n] to obtain a solution ω ′ , and let ωi′′ = ωi′ if θi ≥ 0 and
0 otherwise. Thus, A can be used to approximately separate over constraints (21). We now argue
that this implies that we can obtain a solution to (R-P) of value at least optr/ρ. This follows a
routine argument in the approximation-algorithms
literature (see, e.g., [11]).
P
Define P(ν) := {(y, β, γ) : (21)–(23),
v γv ≤ ν}. Note that optr is the smallest ν such that
P(ν) 6= ∅. Given ν, y, β, γ, we either show that (y, β, γρ) ∈ P(νρ), or we exhibit a hyperplane
vi′ yi,(vi′ ,v−i ),vi )

23

P
separating (y, β, γ) from P(ν). To do this, we first check if v γv ≤ ν, (22), (23) hold, and if not
′
use the appropriate inequality as the separating hyperplane. Next, for every v ∈ D , we use A as
specified above to obtain some ω ′′ ∈ Ω. If in this process, the LHS of (21) exceeds γv for some
v, then we return the corresponding inequality as the separating hyperplane. Otherwise, for all
′
v ∈ D and all ω ∈ Ω, the LHS of (21) is at most γρ, and so (y, β, γρ) ∈ P(νρ).
Thus, for a fixed ν, in polynomial time, the ellipsoid method either certifies that P(ν) = ∅, or
returns a point (y, β, γ) with (y, β, γρ) ∈ P(νρ). We find the smallest value ν ∗ (via binary search)
such that the ellipsoid method run for ν ∗ (with the above separation oracle) returns a solution
(y ∗ , β ∗ , γ ∗ ) with (y ∗ , β ∗ , γ ∗ ρ) ∈ P(ν ∗ ρ); hence, optr ≤ ν ∗ ρ. For any ǫ > 0, running the ellipsoid
method for ν ∗ − ǫ yields a polynomial-size certificate for the emptiness of P(ν ∗ − ǫ). This consists of
the polynomially many violated inequalities P
returned by the separation oracle during the execution
of the ellipsoid method and the inequality v γv ≤ ν ∗ − ǫ. By duality (or Farkas’ lemma), this
∗
means that here is a polynomial-size
 solution (x̃, p̃) to (R-P) whose value is at least ν − ǫ. Taking
1
ǫ to be 1/ exp(input size) (so ln ǫ is polynomially bounded), this also implies that (x̃, p̃) has value
at least ν ∗ ≥ optr/ρ.
We can now convert (x̃, p̃) to a (DSIC-in-expectation, IR) mechanism with revenue at least
optr/ρ via the procedure described in Section C.1.

24

