Mechanism Design via Dantzig-Wolfe
Decomposition
Salman Fadaei

⋆⋆

arXiv:1508.04250v2 [cs.GT] 15 Aug 2016

salman.fadaei@gmail.com

Abstract. In random allocation rules, typically first an optimal fractional point is calculated via solving a linear program. The calculated
point represents a fractional assignment of objects or more generally
packages of objects to agents. In order to implement an expected assignment, the mechanism designer must decompose the fractional point
into integer solutions, each satisfying underlying constraints. The resulting convex combination can then be viewed as a probability distribution
over feasible assignments out of which a random assignment can be sampled. This approach has been successfully employed in combinatorial
optimization as well as mechanism design with or without money.
In this paper, we show that both finding the optimal fractional point as
well as its decomposition into integer solutions can be done at once. We
propose an appropriate linear program which provides the desired solution. We show that the linear program can be solved via Dantzig-Wolfe
decomposition. Dantzig-Wolfe decomposition is a direct implementation
of the revised simplex method which is well known to be highly efficient in
practice. We also show how to use the Benders decomposition as an alternative method to solve the problem. The proposed method can also find
a decomposition into integer solutions when the fractional point is readily present perhaps as an outcome of other algorithms rather than linear
programming. The resulting convex decomposition in this case is tight in
terms of the number of integer points according to the Carathéodory’s
theorem.
Keywords: Mechanism design, Random allocation, Convex decomposition, Dantzig-Wolfe decomposition, Benders decomposition

1

Introduction

The technique of finding a fractional solution, and decomposing it into polynomiallymany integer points has been successfully employed in many problems. For a
usage of the technique in combinatorial optimization, for instance, see Carr and
Vempala [4]. In mechanism design with bidders who have quasi-linear valuations, the framework presented by Lavi and Swamy for designing truthful and
approximate mechanisms strongly relies on this technique [13,12]. Perhaps the
⋆⋆

This work was done while the author was a graduate student in the Department of
Informatics, TU München, Munich, Germany.

2

Fadaei

best connection between linear programming and algorithmic mechanism design
has been established by this framework. Finally, for applications in mechanism
design without money see e.g. Budish et al. [3], and Nguyen et al. [14].
Typically in such applications, first a fractional optimal point is calculated,
and in a second step, the point is represented as a convex combination of integer
points usually using the ellipsoid method. A subroutine or an approximation
algorithm which returns an integer point with respect to any cost vector is employed to construct the separation oracle for the ellipsoid method. A separation
oracle, in the ellipsoid method, states if a given point is feasible, or in case it
is not feasible, the oracle returns a violated constraint. A natural question that
arises here is to ask if the two steps, optimization as well as convex decomposition, can be done at once without employing the ellipsoid method?
1.1

Results and Techniques

We propose an appropriate linear program for finding an optimal fractional point
and its decomposition into integer points. We show how to use the DantzigWolfe decomposition which is based on the revised simplex to solve the linear
program. More specifically, we show that finding a convex combination of integer
points whose value is maximum is indeed equivalent to solving a linear program
using the Dantzig-Wolfe decomposition. The proposed method will improve the
connection between linear programming and algorithmic mechanism design.
Dantzig-Wolfe (DW) decomposition comprises a master problem and a subproblem. DW decomposition proceeds in iterations by solving the two problems
in each iteration until the subproblem is not able to find any point which can
contribute to the objective value of the master problem [2]. Since we are interested in integer points, we run a subroutine or an approximation algorithm
which returns integer solutions as the subproblem. DW decomposition has been
previously used for optimizing over a discrete set using branch and cut to obtain integer solutions [6]. However, here we assume the existence of a subroutine
which returns an approximate integer solution of good quality and prove that
the algorithm ends in optimality. To the best of our knowledge, this usage of
DW decomposition in mechanism design has not been introduced before.
Dantzig-Wolfe decomposition is a variant of the revised simplex algorithm.
A computational evaluation of the Dantzig-Wolfe decomposition has been done
in [15]. The study shows DW decomposition has a high performance, especially
when a reasonable block structure can be found.
The convex combination calculated by our method is tight in terms of the
number of integer solutions according to the Carathéodory’s theorem provided
that the number of constraints representing the underlying polytope is less than
the dimension of the polytope. We explain this fact further in the following.
Theorem 1 (Carathéodory). Given a polytope in Rn , any point in the polytope is a convex combination of at most n + 1 vertices of the polytope.
By standard polyhedra theory, the number of nonzero variables in an extreme
point is upper bounded by the number of constraints in the underlying linear

Mechanism Design via Dantzig-Wolfe Decomposition

3

program (see e.g. [5]). The proposed algorithm produces a convex combination
of at most m + 1 integer points, where m is the number of constraints, and
thus the solution is tight in this sense. It is very common that the number
of constraints m is less than the number of variables n. For example, in the
relaxations of combinatorial auctions, this is usually the case because the bidders
may obtain any package of items (for which one decision variable is needed) and
there are exponentially many packages of items. Thus, given that m < n, the
number of integer solutions will be at most n + 1 which is tight according to the
Carathéodory’s theorem.
Sometimes, a fractional point - not necessarily an optimum - is calculated via
other methods rather than linear programming. For example, a greedy algorithm
might be used to find a fractional point. This is because truthfulness 1 can be
guaranteed via the greedy algorithm, but directly solving the linear program
cannot assure truthfulness (see e.g. [8]). Our method can find a decomposition
into integer solutions for such readily-present fractional points.
We also show how to apply the Benders decomposition to the problem. Benders decomposition is known to be the dual of the Dantzig-Wolfe decomposition
technique [2]. We observe that sometimes working with the Benders decomposition has advantages over the DW decomposition. We discuss these advantages
further in a separate section of the paper.
1.2

Related Literature

Prior to this work, there have been other attempts to replace the ellipsoid in
finding convex decompositions. An alternative method is given by Kraft et al.
[11]. The main component of that work is an algorithm which is based on a simple
geometric idea that computes a convex combination within an arbitrarily small
distance ǫ > 0 to the fractional point. Our proposed method has advantages
over the result in [11]. First, the size of the convex decomposition (number of
integer solutions) is strictly smaller than the size of the convex decomposition
produced by the method in [11]. The size of the convex decomposition in [11]
might be as large as O(s3 ǫ−2 ), where s is the number of nonzero components of
the fractional point, and ǫ > 0. Our solution will have a size of at most s + 1.
Second, our decomposition is exact and does not suffer from an ǫ > 0 compromise in the solution. However, we provide no theoretical upper bound on
the number of iterations, and the proposed method relies on the performance of
Dantzig-Wolfe decomposition in practice.
Elbassioni et al. present an alternative method for finding a convex decomposition of a given fractional point [9]. Their method relies on the multiplicative
weights update method which is a general technique for solving packing and
covering problems [1,10]. While the algorithm presented in [9] has a theoretical
upper bound on the number of iterations, the algorithm is inferior to the presented method here in two aspects. First, their convex decomposition might have
1

Truthfulness is a desired property in algorithmic mechanism design, and assures that
no bidder would benefit from reporting false valuations.

4

Fadaei

a size (the number of integer solutions) of s(⌈ǫ−2 ln s⌉ + 1), s being the number
of nonzero components of the fractional point, and ǫ > 0. As mentioned earlier,
our solution will have a size of at most s + 1. Second, their convex decomposition
1
times the fractional solution (for some ǫ > 0) at the
can be as precise as 1+4ǫ
expense of increasing runtime, while our convex decomposition is exact.
1.3

Structure

In Section 2, we formally introduce the setting of the problem. In Section 3,
we provide a short summary of DW decomposition technique. In Section 4, we
establish our main result and show how the DW principle can be applied to our
setting. Section 5 is devoted to the Benders decomposition applied to our setting.
Section 6 discusses two applications of the adapted DW principle. Finally, in
Section 7, we provide a numerical example for the adapted DW technique.

2

Setting

Consider a finite set of integer points in Zn+ . Let Q denote the convex hull of
all these
 points. That is Q defines a polytope with integral extreme points. Let
P = x ∈ Rn | Ax ≤ b & x ≥ 0 denote a polytope, where A is an m by
n matrix, and b an m-dimensional column vector. A subroutine A for any cost
n
∗
function c ∈ R
 returns an integer point X ∈ Q such that cX ≥ cx , where
x∗ = arg max cx | x ∈ P . Equivalently, we say subroutine A will return for
any cost vector c an integer point X ∈ Q such that cX ≥ cx for any x in P . Let
I denote the
 index set for integer points in Q. The set of integer points in Q is
therefore Xj j∈I .
Usually, subroutine A only accepts non-negative cost vectors. Examples are
approximation algorithms for NP-hard optimization problems. For instance, the
approximation algorithm provided for the knapsack problem works with nonnegative profits of items. However, in our setting, we expect A to work with any
arbitrary cost vector. In such cases, an assumption that Q is a packing polytope
is required: if x ∈ Q and y ≤ x then y ∈ Q. See Lavi and Swamy for more
information [13].
In this paper,
problem. Given a cost vector c ≥
 we address the following P
∗
= 1, and ii) |{λ∗j | j ∈
0, find values λ∗j ≥ 0 j∈I such that i)
j∈I λj P
∗
∗
∗
I, λj > 0}| is polynomial in m and n, and iii)
j∈I λj Xj = x , where

x∗ = arg max cx | x ∈ P .
Using the ellipsoid method, it can be shown that every point in P can be
written as a convex combination of the extreme points in Q [4,13]. In this work,
aside from answering the question above, we give an alternative proof for this
fact.

3

Summary of Dantzig-Wolfe Decomposition

Dantzig-Wolfe decomposition belongs to column generation techniques. We shall
here briefly go over the Dantzig-Wolfe Decomposition. For a detailed explanation

Mechanism Design via Dantzig-Wolfe Decomposition

5

of the method we refer the reader to [2]. Consider the following linear program.
Minimize

cx

subject to Ax = b
x∈X
Where X is a bounded polyhedral of special structure, A is a m × n matrix,
c is a n-dimensional vector and b is a m-dimensional vector.
Since X is a bounded polyhedra, then any point x ∈ X can be represented as
a convex combination of a finite number of extreme points of X. Let us denote
these points by x1 , x2 , . . . , xl , and substitute x with its convex combination
of extreme points, then the aforementioned LP can be transformed into the
following program in which the variables are λ1 , λ2 , . . . , λl .

Minimize

l
X

(cxj )λj

(1)

(Axj )λj = b

(2)

λj = 1,

(3)

j=1

subject to

l
X
j=1

l
X
j=1

λj ≥ 0

j = 1, 2, . . . , l

(4)

The linear program (1) − (4) is called the master problem and the program
which finds an appropriate x ∈ X in each iteration is called the subproblem.
Since the number of extreme points of set X is exponentially many, we follow
the idea of column generation to find appropriate extreme point in each iteration.
The information is passed back and forth between the master problem and the
subproblem as follows. In each iteration a different cost coefficient is passed down
by the master problem to the subproblem and the subproblem finds an extreme
point xk , and sends it to the master problem.
Dantzig-Wolfe decomposition is an implementation of the revised simplex
method. Let vector w and α denote the dual variables corresponding to equations
(2) and (3), respectively. We first need an initial solution to generate the simplex
tableau. Suppose we have a basic feasible solution λ = (λB , λN ) to system
(2)−(4), where λB and λN denote the basic and nonbasic variables, respectively.
The initial (m + 1) × (m + 1) basis inverse B−1 hence will be known. The cost for
each basic variable λj is in fact ĉj = cxj . Therefore, we get (w, α) = ĉBB −1 ,
b
where ĉB is the cost vector of the basic variables. Denoting b̄ = B −1
, we
1
see the revised simplex tableau in Table 1.
The revised simplex proceeds by improving the current solution via finding
an entering and a leaving variable. In other words, the set of basic and nonbasic

6

Fadaei
BASIS RHS
(w, α)

ĉB b̄

B −1
b̄
Table 1. Simplex tableau. RHS stands for right-hand side.

variables exchange one element. When such an exchange is not possible then the
current solution is optimal. The entering variable is in fact a variable λkassoci
Axk
ated with extreme point xk for which zk − ĉk > 0, where zk = (w, α)
1
and ĉk = cxk .
We observe that zk − ĉk = (wA − c)xk + α denotes the value of point xk
with respect to current costs wA − c and dual variable α. In order to find such
a point, we solve the following subproblem which gives us the required index or
tells that the current solution is optimal when the maximum value is zero.
Maximize

(wA − c)x + α

subject to

x∈X

Notice that the objective function contains a constant and therefore it can be
replaced by (wA−c)x. Assuming that xk is the optimal solution to the program
above, the revised simplex method goes on as follows. If zk − ĉk = 0 then the
algorithm stops and the last solution to the master problem is an optimal of the
overall problem.


Axk
,
If zk − ĉk > 0 the master problem proceeds as follows. Let yk = B −1
1


z − ĉk
. In order to find the leaving column,
the entering column then will be k
yk
let index r be determined as follows:
(
)
b̄r
b̄i
= Minimum
: yik > 0 .
1≤i≤m+1
yrk
yik
We pivot at yrk which will update the dual variables, the basis inverse, and the
right-hand side. More specifically, pivoting on yrk can be stated as follows.
1. Divide row r by yrk .
2. For i = 1, . . . m and i 6= r, update the ith row by adding to it −yik times
the new rth row.
3. Update row zero by adding to it zk − ĉk times the new rth row.
After pivoting, the column λk is deleted and the algorithm repeats.
An important observation about the DW principle is as follows. The DW
principle expects the Subproblem to return any point x ∈ X where (wA −

Mechanism Design via Dantzig-Wolfe Decomposition

7

c)x + α > 0 and it does not impose any other specific requirement on the
selected point. We shall use this observation in our adaptation of the method.
Another observation is that, in each iteration, the master program finds the
best solution using known extreme points. This is done in an organized manner
as described above.

4

Applying Dantzig-Wolfe Decomposition

A wide range of combinatorial
optimization problems can be formulated
using


the integer program max cx | x ∈ P and integer . Recall, P = x ∈ Rn | Ax ≤
b & x ≥ 0 . For example, in combinatorial auctions, c denotes the accumulated
valuations of the players, and the integer program therefore expresses the welfare
maximization objective subject to feasibility constraints encoded as P .
Usually, using simplex method or other standard linear programming techniques, first a relaxed linear program of the integer program above is solved:
Maximize

cx

(5)

subject to

Ax ≤ b
x≥0

(6)
(7)

Notice, constraints (6) and (7) together are equivalent to x ∈ P . Next, the
solution is rounded to an integer solution at the expense of a value loss or slightly
violating the constraints. Given subroutine A, we wish to find a solution to the
linear program above as well as a convex decomposition of it into integer points.
We wish to achieve both goals at once. Recall, subroutine A returns for any cost
vector c an integer point X ∈ Q such that cX ≥ cx for any x in P .
Generally speaking, Dantzig-Wolfe principle uses the fact that if we relax
some constraints and obtain a simpler polyhedra then the solution to the original problem can be written as a convex combination of extreme points of the
simpler polyhedra. The simplicity refers to the fact that the extreme points of
the new polyhedra can be found more easily than those of the original problem. While Dantzig-Wolfe principle is useful when the underlying constraints
are decomposable into simpler regions, we use it in a slightly different manner
by looking at Q as the polyhedra over which we can efficiently optimize. Recall,
Q denotes the convex hull of a finite set of integer points. To apply the idea of
Dantzig-Wolfe decomposition to the problem (5) − (7), we add a new constraint
to the program.
x∈Q

(8)

We will show that an optimal solution to problem (5) − (8) is also an optimal
solution to (5)−(7), and thus adding the new constraint is harmless. We represent
x ∈ Q as a convex combination of extreme
points of Q. Recall, I denote the

index set for integer points in Q, and Xj j∈I is the set of integer points in Q.

8

Fadaei

Substitute x with its convex combination of extreme points of Q, then program
(5) − (8) can be transformed into the following program where the variables are

λj j∈I .
Maximize

X

(cXj )λj

(9)

j∈I

subject to

X

(AXj )λj + s = b

(10)

λj = 1

(11)

j∈I

X
j∈I

λj ≥ 0

∀j ∈ I

s ≥ 0.

(12)
(13)

The linear program (9) − (13) is the master problem. Notice, we have added
slack variables s ∈ Rm
+ to convert the inequalities into equality as needed by the
DW principle (see Section 3). The DW subproblem is defined below.
max (c + wA)Xj
j∈I

(14)

While our problem is a maximization problem, the procedure in Section 3
is presented for a minimization problem, thus we substitute the −c with c in
the objective function of the subproblem. P
That means, we change
P the objective
function of the master problem from max j∈I (cXj )λj to min j∈I (−cXj )λj ,
and apply the theory provided in Section 3.
We assume 0 ∈ Q thus the initial basic solution is simply defined by letting
λ0 , the variable corresponding to point X = 0, equal 1 (λ0 = 1), and letting
s = b.2 Assuming that program (14) can be efficiently solved for any cost vector,
then we are exactly following the DW principle, and therefore, we can successfully
solve the overall problem as DW principle does this. However, program (14) is
an integer program and solving it may not be computationally tractable.
To address this issue, we propose using subroutine A to approximate program
(14). Let (w̄, ᾱ) be the last dual variables calculated by the master program. In
each iteration, we call subroutine A with current cost vector c + w̄A to find a
point Xk ∈ Q to pass to the master problem. This substitution seemingly comes
at the expense of stopping at a local optimum, as explained in the following.
As long as the algorithm continues by using the points returned by subroutine
A, we are exactly running DW principle. Recall the important observation that
in DW principle, the subproblem need not be completely optimized and any
point Xk with (c + w̄A)Xk + ᾱ > 0 suffices to proceed. However, there might
be an iteration in which there exists a point X′ ∈ Q for which we have (c +
w̄A)X′ + ᾱ > 0, but for the integer point Xk returned by subroutine A, we have
2

Note that 0 ∈ Q is a consequence of the assumption that Q is a packing polytope.

Mechanism Design via Dantzig-Wolfe Decomposition

9

(c + w̄A)Xk + ᾱ ≤ 0. Therefore, DW stops at a suboptimal point. Nevertheless,
below, we argue that this cannot happen. That means as long as DW has not
reached the optimum to problem (5) − (7), subroutine A, given the current cost
vector (c + w̄A), returns a point Xk with (c + w̄A)Xk + ᾱ > 0.
Let x∗ denote the optimal solution to program (5) − (7). It is instructive to
see what the master step would do if the subproblem passes the point x∗ , rather
than an integer point, to the master problem. While we do not know such an
optimal point, but we know that such a point exists and this suffices for our
reasoning. We argue that the master step will set λx∗ = 1 and λj = 0 for all
other λj ’s which are currently in the base. In other words, the master program
returns the best possible convex combination which is in fact λx∗ = 1. This is
discussed in the following observation.
Observation 1 Let x∗ denote the optimal solution to program (5) − (7). If
supposedly the subproblem in any iteration passes x∗ to the master problem,
then the master step will set λx∗ = 1 and λj = 0 for all other λj ’s which are
currently in the base.
Proof. First, we observe that if the first subproblem (right after the initialization) passes x∗ to the master problem, then the master step will set λx∗ = 1
and λ0 = 0. Clearly, in the solution s needs to be evaluated accordingly. Second,
by looking more closely at what simplex does in each iteration, we observe that
in any further iteration, if the subproblem passes x∗ to the master problem, the
master step will set λx∗ = 1 and λj = 0 for all other λj ’s.
The simplex method, in each iteration, performs a set of row operations on
the constraints when it pivots (see pivoting steps in Section 3). The constraints,
in any iteration, are thus the initial constraints after a series of row operations.
This will certify that the aforementioned solution (λx∗ = 1) will be feasible in
any further iteration. If the subproblem passes x∗ to the master problem, our
entering variable will be λx∗ . The simplex algorithm then increases the entering
variable λx∗ as much as one basic variable gets zero. However, as discussed, the
solution λx∗ = 1 is feasible, and it is possible to increase λx∗ up to 1 and set
all other λj ’s to zero. The algorithm will behave as such to produce the highest
increase in the objective value, the desired conclusion.
Theorem 2. If the subproblem (14) calls subroutine A to return an integer point
in each iteration, the DW principle never stops until it gets to an optimal solution
to problem (5) − (7).
Proof. Let x∗ denote the optimal solution
P to program (5) − ∗(7). Assume the
algorithm stops at a suboptimal point:
j∈I (cXj )λj < cx . Let (w̄, ᾱ) be
the last dual variables calculated by the master program. Let Xk be the point
returned by subroutine A, given cost vector (c + w̄A), in the last iteration. We
must have (c + w̄A)Xk + ᾱ ≤ 0 because DW has stopped.
If supposedly the subproblem in the last iteration passes x∗ to the master
problem, according to Observation 1, the master step will increase λx∗ up to
1 and set all other λj ’s to zero. Since we assumed the algorithm has stopped

10

Fadaei

at a suboptimal point, by setting λx∗ = 1 the objective value will increase. If
entering λx∗ improves the objective value, we must have (c + w̄A)x∗ + ᾱ > 0
from the theory of DW principle provided in Section 3: if (c + w̄A)x∗ + ᾱ ≤ 0
then entering variable λx∗ cannot improve the objective value.
By the property of the subroutine, we have (c + w̄A)Xk ≥ (c + w̄A)x∗ .
Thus, in the last iteration, we must have (c + w̄A)Xk + ᾱ > 0. This contradicts
our assumption that (c + w̄A)Xk + ᾱ ≤ 0. Consequently, as long as we have not
reached the optimum, the subroutine returns a point Xk with (c + w̄A)Xk + ᾱ >
0. This completes the proof.
We draw the conclusion that substituting program (14) with subroutine A is
harmless. Therefore, we have shown that finding a convex decomposition of maximum value is indeed equivalent to solving a linear program via DW principle.
Let us call the method integer DW.

5

Benders Decomposition

It is known that the Dantzig-Wolfe Decomposition has an equivalent decomposition technique namely Benders decomposition [2]. Benders decomposition is a
row generation technique in contrast with the Dantzig-Wolfe column generation
procedure. Sometimes, working with Benders decomposition has advantages over
Dantzig-Wolfe decomposition. We explain how to apply the Benders algorithm
to our problem. Later, we discuss the advantages of the method.
Recall, polytope Q is a bounded polyhedra.
Hence, there exist matrix D ∈

′
′
Rm ×n and d ∈ Rm such that Q = x ∈ Rn | Dx ≤ d & x ≥ 0 . We add
constraint x ∈ Q to program (5) − (7) and work with the new program. We
will see that adding this constraint has no influence on the region of feasible
solutions to program (5) − (7). Following the standard procedure [2], we can
write the Benders decomposition for this new program. The Benders master
problem will be as follows.
Maximize z

(15)

subject to z ≤ wb − (c + wA)Xj
w≤0
z

unrestricted.

∀j ∈ I

(16)
(17)
(18)

The variables of the master problem are z and w. Variable vector w is the
vector of dual variables associated to the constraints (6). The Benders master
problem has exponentially many constraints, thus it is inconvenient to solve
directly. Hence, we maintain only a few of the constraints (16). Assuming 0 ∈ Q,
we start with only one constraint: z ≤ wb − (c + wA)0 = wb. Notice, we can
use any Xj ∈ Q to start with. We solve the master problem and let (z̄, w̄) be
the solution. The value of z̄ is an upper bound on the optimal value to the
master problem. If (z̄, w̄) satisfies constraints (16) for all j ∈ I, then (z̄, w̄) is
optimal for the master problem. We can check constraints (16) by examining if
z̄ ≤ w̄b − maxj∈I (c + w̄A)Xj .

Mechanism Design via Dantzig-Wolfe Decomposition

11

Thus, the Benders subproblem will be as the following.
max (c + w̄A)Xj
j∈I

(19)

Note that the Benders subproblem is also the subproblem solved by the
Dantzig-Wolfe decomposition. Furthermore, the Benders master problem is the
dual to the Dantzig-Wolfe master problem (9) − (13). The Benders subproblem,
in each iteration, is solved by calling subroutine A with cost vector c+ w̄A. If the
subproblem returns Xk that violates the constraints (16): z̄ > w̄b− (c + w̄A)Xk ,
we can generate the new constraint z ≤ wb − (c + wA)Xk , and add it to
the current master program, and reoptimize. We repeat this process until the
solution returned by subroutine A does not violate the constraints. We claim
that at this iteration, the value of z̄ is the optimal value to the master problem.
The Benders decomposition provides a more concise proof that the decomposition techniques in companion with the subroutine A work correctly.
Theorem 3. If the subproblem (19) calls subroutine A to return an integer point
in each iteration, the Benders algorithm never stops until it reaches an optimal
solution to problem (5) − (7).
Proof. Let x∗ denote an optimal solution to problem (5) − (7). Let z ∗ denote
an optimal value of the Benders master problem. We have z ∗ = (−c)x∗ by
the construction of the Benders master problem, and the duality theorem. Let
z̄ be the final solution to the master problem and Xk the solution returned
by subroutine A when the Benders algorithm stops. Since the algorithm stops,
we must have z̄ ≤ w̄b − (c + w̄A)Xk . We always have z ∗ ≤ z̄ because z̄ is
an upper bound on the optimal solution to the master problem. Assume z̄ is
not optimal: z̄ > z ∗ . Remember, by the definition of subroutine A, we have
(c + w̄A)Xk ≥ (c + w̄A)x∗ . Therefore,

⇒
⇒
⇒
⇒

Ax∗

≤b

since x∗ is a solution to
problem (5) − (7)
since w̄ ≤ 0

w̄Ax∗
−cx∗
−cx∗
z̄

≥ w̄b
≥ w̄b − cx∗ − w̄Ax∗
≥ w̄b − (c + w̄A)Xk since (c + w̄A)Xk ≥ (c + w̄A)x∗
> w̄b − (c + w̄A)Xk since z̄ > z ∗ = −cx∗

But, this contradicts z̄ ≤ w̄b − (c + w̄A)Xk . The contradiction arises from
the assumption that z̄ is not optimal. Thus, when the algorithm stops, we have
the optimal solution, the desired conclusion.
After solving the Benders master problem, we can use the provided integer
solutions and solve the restricted primal to obtain a convex decomposition.
Another advantage of the Benders decomposition arises from the fact that in
each iteration, we optimize an LP in the master step. Solving an LP is sometimes
more convenient than the implementation of the pivoting steps done in each
iteration in the master step of the DW principle.

12

5.1

Fadaei

Polynomial Runtime Using Ellipsoid

It is instructive to note that Theorem 3 implies that if the integer solution returned by subroutine A does not violate constraints (16), then the current master
solution is optimal. Exploiting this fact, we can use the ellipsoid method to solve
problem (15) − (18) to certify a polynomial runtime which might be of theoretical interest. To use the ellipsoid method, we need to implement a separation
oracle. Recall that a separation oracle, given a solution, either confirms that it
is a feasible solution, or returns the constraint violated by the solution. Using
subroutine A as the separation oracle, as long as we find a violated constraint,
we cut the current ellipsoid and continue. When the subroutine A cannot return
a violating constraint, according to Theorem 3, the algorithm has reached the
optimum.

6
6.1

Application of the Method in Mechanism Design

The Framework Proposed by Lavi and Swamy

Let X = x ∈ Rn | Ax ≤ b & x ≥ 0 denote the underlying polytope of a
linear program, and x∗ denote an optimal solution to the program with respect
to some cost vector. The maximum ratio between the value of an integer program and its relaxation, with respect to all cost vectors, is called the integrality
gap of the relaxation. Assuming that, the integrality gap of X is β ≥ 1, and
that a β integrality-gap-verifier is given, Lavi and Swamy propose a method to
∗
decompose the scaled-down fractional solution xβ into a convex combination of
integer solutions [13]. A β integrality-gap-verifier is an algorithm that, given any
cost vector, returns an integer solution whose value is at least 1/β times the
optimal relaxed solution.
This decomposition technique was originally observed by Carr and Vempala
[4], and later adapted by Lavi and Swamy to mechanism design problems provided that the underlying polytope of the relaxation of the problem has the
packing property [13]. The approach requires only a polynomial number of calls
to the integrality-gap-verifier with respect to the number of positive components
in x∗ . Yet, the approach strongly relies on the ellipsoid method, and hence it is
more of theoretical importance than of practical use.
In order to view the LS framework
 in our setting, the integrality-gap-verifier
is used as subroutine A and X/β = x | βx ∈ X is treated as P in our setting
introduced in Section 2. This way, the integer DW finds the maximum value
in X/β as well as its decomposition into integer points, both in one step. This
improves upon other implementations of the LS framework which require two
steps to find the convex decomposition [13,11,9].
It is instructive to note that solving program (9) − (13), essentially defines a
Maximal-In-Distributional-Range (MIDR) allocation rule. An MIDR algorithm
fixes a set of distributions over feasible solutions (the distributional range) independently of the valuations reported by the self-interested players, and outputs

Mechanism Design via Dantzig-Wolfe Decomposition

13

a random sample from the distribution that maximizes expected (reported) welfare [7]. Here, we optimize over a range which is independent of bidder’s private
information. The range is in fact the feasible region of the program: all probability distributions over integer solutions which satisfy constraints (10) − (13).
The range is obviously independent of bidders’ valuations.
6.2

Existing Fractional Point

Sometimes a fractional point x∗ ∈ Q is present, and we wish to find a convex
decomposition of x∗ into extreme points of Q. This can happen when we use
other methods to find a fractional point rather than linear programming. Recall,
we assume that Q satisfy the packing property.

For this case, we can use the integer DW as follows. Define P = x ∈
Rn | x ≤ x∗ & x ≥ 0 and let c = x∗ . Now, apply the integer DW. All
arguments follow accordingly, assuming that a subroutine A with the following
property is available. Subroutine A will return for any cost vector c an integer
point X ∈ Q such that cX ≥ cx∗ . Because the number of constraints in P is at
most n, the resulting convex decomposition in this case is tight in terms of the
number of integer points, according to the Carathéodory’s theorem.

7

Numerical Example for Integer DW

In this section, we apply the integer DW to an instance of multi-unit auctions
to see how the method works. We relegate the details to the appendix.

References
1. Arora, S., Hazan, E., Kale, S.: The multiplicative weights update method: a metaalgorithm and applications. Theory of Computing 8(1), 121–164 (2012)
2. Bazaraa, M.S., Jarvis, J.J., Sherali, H.D.: Linear programming and network flows.
John Wiley & Sons (2011)
3. Budish, E., Che, Y.K., Kojima, F., Milgrom, P.: Designing random allocation mechanisms: Theory and applications. The American Economic Review 103(2), 585–623
(2013)
4. Carr, R., Vempala, S.: Randomized metarounding. In: Proceedings of the thirtysecond annual ACM symposium on Theory of computing. pp. 58–62. ACM (2000)
5. Chvátal, V.: Linear programming. WH Freeman and Company, New York (1983)
6. Desrosiers, J., Lübbecke, M.E.: A primer in column generation. Springer (2005)
7. Dobzinski, S., Dughmi, S.: On the power of randomization in algorithmic mechanism design. In: Foundations of Computer Science, 2009. FOCS’09. 50th Annual
IEEE Symposium on. pp. 505–514. IEEE (2009)
8. Dughmi, S., Ghosh, A.: Truthful assignment without money. In: Proceedings of
the 11th ACM conference on Electronic commerce. pp. 325–334. ACM (2010)
9. Elbassioni, K., Mehlhorn, K., Ramezani, F.: Towards more practical linear
programming-based techniques for algorithmic mechanism design. In: Algorithmic
Game Theory, pp. 98–109. Springer (2015)

14

Fadaei

10. Khandekar, R.: Lagrangian relaxation based algorithms for convex programming
problems. Ph.D. thesis, Indian Institute of Technology Delhi (2004)
11. Kraft, D., Fadaei, S., Bichler, M.: Fast convex decomposition for truthful social
welfare approximation. In: Web and Internet Economics, pp. 120–132. Springer
(2014)
12. Lavi, R., Swamy, C.: Truthful and near-optimal mechanism design via linear programming. In: Foundations of Computer Science, 2005. FOCS 2005. 46th Annual
IEEE Symposium on. pp. 595–604. IEEE (2005)
13. Lavi, R., Swamy, C.: Truthful and near-optimal mechanism design via linear programming. Journal of the ACM (JACM) 58(6), 25 (2011)
14. Nguyen, T., Peivandi, A., Vohra, R.: Assignment problems with complementarities.
Tech. rep., Mimeo., February (2015)
15. Tebboth, J.R.: A computational study of Dantzig-Wolfe decomposition. Ph.D. thesis, University of Buckingham (2001)

A

Numerical Example for Integer DW

In this section, we focus on applying the integer DW to an instance of multi-unit
auctions. In multi-unit auctions, there is a set of m identical items and a set of
players. Each player i has a valuation for any number of items denoted by vi (j)
for getting j items where 1 ≤ j ≤ m. The goal is to maximize social welfare by
distributing items among bidders.
The LP relaxation for this class of problems is as follows. Let xij denote if j
units is assigned to bidder i.
Maximize

X

vi (j)xij

(MU-P)

i,j

subject to

X

xij ≤ 1 for each player i

(20)

j · xij ≤ m

(21)

j

X
i,j

0 ≤ xij ≤ 1

for each i, j

(22)

Lavi and Swamy present a greedy algorithm which returns for any valuation
v an integer solution that is at least as good as half of the optimal fractional
solution to MU-P with respect to v [13]. Thus, we have a 2 integrality-gap-verifier
algorithm for MU-P. This greedy algorithm will serve as the subroutine in the
integer DW, and is called A.
We give a short example to demonstrate the proposed convex decomposition
method. Suppose a simple multi-unit auction with 3 players and 4 identical items.
The following valuation vectors vi (j) are given for each player i and quantity j:
j
v1 (j) = (
v2 (j) = (
v3 (j) = (

1234
6666 )
1446 )
0111 )

Mechanism Design via Dantzig-Wolfe Decomposition

15

We can reproduce program (9)−(13) for this instance as follows. Let I denote
the index set of integer points which satisfy inequalities (20) − (22).


 
111100000000
0.5
 0 0 0 0 1 1 1 1 0 0 0 0
0.5




 
Let c = 6 6 6 6 1 4 4 6 0 1 1 1 , b =  , and A = 
.
 0 0 0 0 0 0 0 0 1 1 1 1
0.5

123412341234
2
Notice the integrality gap has been reflected in defining b.
Initialization Step

Let the starting basis consist of s and λ0 where X0 = 0 is the starting integer
point. Therefore, the first simplex tableau is as the following.
BASIS INVERSE RHS

z
s1
s2
s3
s4
λ0

0
1
0
0
0
0

0
0
1
0
0
0

0
0
0
1
0
0

0
0
0
0
1
0

0
0
0
0
0
1

0
.5
.5
.5
2
1

Iteration 1


From the simplex tableau, we have w = 0 0 0 0 and α = 0.
As a result, wA + c = c. The subproblem therefore is maxj∈I cXj . Subroutine
A returns X such that X11 = X22 = 1 and all other entries of X are zero. The
objective of the point with respect to current cost is z − ĉ = 10 > 0. Let us call
this point X1 .
SUBPROBLEM.

MASTER PROBLEM.

 
1
 
1

# 
"
1

1


A
X
1
 
0
AX1 =  . Then y1 = B −1
=

.
0
1
 
3
3
1
Now, we insert the column into the foregoing tableau and pivot. Variable s1
leaves the basis and λ1 enters the basis.
BASIS INVERSE RHS

z
s1
s2
s3
s4
λ0

0
1
0
0
0
0

0
0
1
0
0
0

0
0
0
1
0
0

0
0
0
0
1
0

0
0
0
0
0
1

0
.5
.5
.5
2
1

λ1
10
1
1
0
3
1

After pivoting we obtain the following tableau.

16

Fadaei

BASIS INVERSE

z −10
λ1
1
s2 −1
s3
0
s4 −3
λ0 −1

0
0
1
0
0
0

0
0
0
1
0
0

0
0
0
0
1
0

RHS

0
0
0
0
0
1

−5
.5
0
.5
.5
.5

The best-known feasible solution of the overall problem is given by λ0 X0 +
λ1 X1 = 0.5X0 + 0.5X1 . The current objective value is 5.
Iteration 2


Fromthe simplex tableau, we havew = −10 0 0 0 and α = 0.
As a result, wA + c = −4 −4 −4 −4 1 4 4 6 0 1 1 1 . The subproblem therefore
is maxj∈I (wA + c)Xj . Subroutine A returns X such that X24 = 1 and all other
entries of X are zero. The objective of the point with respect to current cost is
z − ĉ = 6 > 0. Let us call this point X2 .
MASTER PROBLEM.
 
0
 
0

# 
"
1
1


AX2
 
0
=
AX2 =  . Then y2 = B −1

.
0
1
 
4
4
1
Now, we insert the column into the foregoing tableau and pivot. Variable s2
leaves the basis and λ2 enters the basis.
SUBPROBLEM.

BASIS INVERSE

z −10
λ1
1
s2 −1
s3
0
s4 −3
λ0 −1

0
0
1
0
0
0

0
0
0
1
0
0

0
0
0
0
1
0

RHS

0
0
0
0
0
1

−5
.5
0
.5
.5
.5

λ2
6
0
1
0
4
1

After pivoting we obtain the following tableau.
BASIS INVERSE

z
λ1
λ2
s3
s4
λ0

−4 −6
1
0
−1
1
0
0
1 −4
0 −1

0
0
0
1
0
0

0
0
0
0
1
0

RHS

0
0
0
0
0
1

−5
.5
0
.5
.5
.5

The best-known feasible solution of the overall problem is given by λ0 X0 +
λ1 X1 = 0.5X0 + 0.5X1 . The current objective value is 5.

Mechanism Design via Dantzig-Wolfe Decomposition

17

Iteration 3


−4
−6
0
0
From the
simplex
tableau,
we
have
w
=
and α =


0. As a result, wA+c = 2 2 2 2 −5 −2 −2 0 0 1 1 1 . The subproblem therefore
is maxj∈I (wA + c)Xj . Subroutine A returns X such that X11 = 1, X32 = 1 and
all other entries of X are zero. The objective of the point with respect to current
cost is z − ĉ = 3 > 0. Let us call this point X3 .
MASTER PROBLEM.
 
1
 
1

"
# 
−1
0


A
X
3
 
AX3 =  . Then y2 = B −1
=
1

.
1
1
 
4
 
3
1
Now, we insert the column into the foregoing tableau and pivot. Variable s4
leaves the basis and λ3 enters the basis.
SUBPROBLEM.

BASIS INVERSE

z
λ1
λ2
s3
s4
λ0

−4 −6
1
0
−1
1
0
0
1 −4
0 −1

0
0
0
1
0
0

0
0
0
0
1
0

RHS

0
0
0
0
0
1

−5
.5
0
.5
.5
.5

λ3
3
1
−1
1
4
1

After pivoting we obtain the following tableau.
BASIS INVERSE

z
λ1
λ2
s3
λ3
λ0

−4.75 −3
.75
1
−.75
0
−.25
1
.25 −1
−.25
0

0 −.75
0 −.25
0 .25
1 −.25
0 .25
0 −.25

RHS

0
0
0
0
0
1

−5.375
.375
.125
.375
.125
.375

The best-known feasible solution of the overall problem is given by λ0 X0 +λ1 X1 +
λ2 X2 + λ3 X3 = 0.375X0 + 0.375X1 + 0.125X2 + 0.125X3 . The current objective
value is 5.375.
Iteration 4


From the simplex tableau, we have w = −4.75 −3 0 −.75
and α = 0. As a result,

wA + c = .5 −.25 −1 −1.75 −2.75 −.5 −1.25 0 −.75 −.5 −1.25 −2 . The subproblem therefore is maxj∈I (wA + c)Xj . Subroutine A returns X such that
X11 = 1 and all other entries of X are zero. The objective of the point with
respect to current cost is z − ĉ = 0.5 > 0. Let us call this point X4 .
MASTER PROBLEM.
SUBPROBLEM.

18

Fadaei



.5
 
1

"
# 
−.5
0


A
X
4
 
−.5
AX4 =  . Then y2 = B −1
=

.
0
1


 .5 
1
.5
Now, we insert the column into the foregoing tableau and pivot. Variable λ3
leaves the basis and λ4 enters the basis.
BASIS INVERSE

z
λ1
λ2
s3
λ3
λ0

−4.75 −3
.75
1
−.75
0
−.25
1
.25 −1
−.25
0

0 −.75
0 −.25
0 .25
1 −.25
0 .25
0 −.25

0
0
0
0
0
1

RHS
λ4
−5.375 .5
.375 .5
.125 −.5
.375 −.5
.125 .5
.375 .5

After pivoting we obtain the following tableau.
BASIS INVERSE

z
−5 −2
λ1
.5 −2
λ2 −.5 −1
s3
0
0
.5 −2
λ4
λ0 −.5
1

0 −1
0 −.5
0 .5
1
0
0 .5
0 −.5

RHS

0
0
0
0
0
1

−5.5
.25
.25
.5
.25
.25

The best-known feasible solution of the overall problem is given by λ0 X0 +λ1 X1 +
λ2 X2 + λ4 X4 = 0.25X0 + 0.25X1 + 0.25X2 + 0.25X4 . The current objective value
is 5.5.
Iteration 5


From the simplex tableau, we have w = −5 −2 0 −1 and
α = 0. As a result,

wA + c = −6 −7 −8 −9 −3 −4 −5 −6 −1 −2 −3 −4 . The subproblem therefore is maxj∈I (wA + c)Xj . Subroutine A returns X = 0. The objective of the
point with respect to current cost is z − ĉ = 0. Therefore, the algorithm terminates. Our final solution is as follows.

  
 
 
 
 
0.5
0
1
0
1
x11

  
 
 
 
 
x∗ = x22  = 0.25 1 + 0.25 0 + 0.25 0 + 0.25 0 = 0.25 .
0.25
0
0
1
x24
0
SUBPROBLEM.

A simple examination shows that x∗ is in fact one half (scaled down by the
integrality gap) of the optimal solution to MU-P for our instance.

