Nash Social Welfare, Matrix Permanent, and Stable Polynomials
Nima Anari1 , Shayan Oveis Gharan2 , Amin Saberi1 , and Mohit Singh3
1

Stanford University.
University of Washington.
3
Microsoft Research, Redmond.

arXiv:1609.07056v2 [cs.DS] 23 Sep 2016

2

Abstract
We study the problem of allocating m items to n agents subject to maximizing the Nash social
welfare (NSW) objective. We write a novel convex programming relaxation for this problem,
and we show that a simple randomized rounding algorithm gives a 1/e approximation factor of
the objective.
Our main technical contribution is an extension of Gurvits’s lower bound on the coefficient
of the square-free monomial of a degree m-homogeneous stable polynomial on m variables to
all homogeneous polynomials. We use this extension to analyze the expected welfare of the
allocation returned by our randomized rounding algorithm.

1

Introduction

We study the problem of allocating a set of indivisible items to agents subject to maximizing the
Nash social welfare (NSW). We are given a set of m indivisible items and we want to assign them
to n agents. An allocation vector is a vector x ∈ {0, 1}n×m such that for each j, exactly one xi,j is
1. We assume that agents have additive valuations. That is, each agent i has non-negative value
vi,j for an item j and the value that i receives for an allocation x is
vi (x) =

m
X

xi,j vi,j .

j=1

The NSW objective is to compute an allocation x that maximizes the geometric mean of agents’
values,
!1
n
n
Y
.
vi (x)
i=1

The above objective naturally encapsulates both fairness and efficiency and has been extensively
studied as a notion of fair division (see [Mou04, CKM+ 16] and references therein).
Recently, there have been a number of results that study the computational complexity of the
Nash social welfare objective. For additive valuations it is shown that it is NP-hard to approximate
Lee15],
for some constant c > 0. On the positive side,
the NSW objective within (1 − c) [NNRR14,


1
Nguyen and Rothe [NR14] designed a m−n+1 approximation algorithm and Cole and Gkatzelis
1

[CG15] gave the first constant factor,



1
2e1/e


-approximation. Recently, Cole et al. [CDG+ 16] gave

a 21 -approximation for the problem.
A closely related problem, that captures only fairness, is the Santa-Clause problem where the
goal is to find an allocation to maximize the minimum value among all agents, i.e., maxx mini vi (x)
which has also been studied recently [AFS08, AS07, BS06, CCK09].

1.1

Our Contributions

Our main contribution is to show an intricate connection between the Nash welfare maximization
problem, the theory of real stable polynomials, and the problem of approximating the permanent.
We establish this connection in the following manner. We first give a new mathematical programming relaxation for the problem; indeed the standard relaxation has arbitrarily large integrality
gap as shown by Cole and Gkatzelis [CG15]. Our relaxation is a polynomial optimization problem1 which, despite not being convex in the standard form, can be solved efficiently by a change
of variables. We remark that a similar geometric program was used in the context of maximum
sub-determinant problem [NS16].
More precisely, we study a real stable polynomial p(y1 , . . . , ym ). We give a simple randomized
rounding algorithm such that the expected Nash welfare of the allocation returned by the algorithm
exactly equals the sum of square-free coefficients of p(y). Thus, our program needs to maximize
the sum of square-free coefficients of p(y). Unfortunately, such an optimization problem in not
convex. Instead, we maximize the following proxy
p(y).

inf
Q

y>0:
y
≥1,∀S∈([m]
i
i∈S
n )

The main part of our analysis is to relate the sum of square-free coefficients of p(y) to the above
proxy. This desired inequality is a generalization of an elegant result of Gurvits [Gur06] relating the
problem of approximating the permanent of a matrix with the theory of real stable polynomials.
We prove this generalization in Theorem 1.2. The connection to permanents allows us to use
algorithmic results for approximating the permanent due to Jerrum, Sinclair and Vigoda [JSV04]
and we obtain the following result.
Theorem 1.1. There is a randomized polynomial time algorithm for the Nash welfare maximization
problem that, with high probability, returns a solution with objective at least 1/e fraction of the
optimum.
We emphasize that unlike the constant factor approximation algorithm by Cole and Gkatzelis
[CG15], our algorithm and its analysis are purely algebraic and completely oblivious to the structure
of the underlying market. In particular, unlike other approaches we are not taking advantage of
the combinatorial structure of “spending restricted assignments” in our rounding algorithms (see
[CG15] for more information). This generality makes our approach potentially applicable to a
variety of resource allocation problems.
The crucial ingredient of our analysis is the following general inequality about real stable polynomials that generalizes the result of Gurvits [Gur06] (see Theorem 2.5) that provided an elegant
proof of the Van-der-Waerden conjecture.
1

It falls in the broad class of geometric programs, where the mathematical program is convex in logarithms of the
variables and not the variables itself.

2

Theorem 1.2. Let p be a degree n-homogeneous real stable polynomial in y1 , . . . , ym with
Q nonS
negative
coefficients. For any set S ⊆ [m], let cS denote the coefficient of monomial y := i∈S yi .
P
If S∈([m]) cS > 0, then
n

X

[m]
n

S∈(

cS
)

≥

m! · (m − n)m−n
mm · (m − n)!

≥ e−n

inf

p(y)

inf

(1)

y>0:
y S ≥1,∀S∈([m]
n )

p(y).

y>0:
y S ≥1,∀S∈([m]
n )
m−k

−k
Note that second inequality follows by Lemma A.1, mm!m · (m−k)
(m−k)! ≥ e . By setting n = m in
the above statement, we obtain the result of Gurvits as described in Theorem 2.5.
It is not hard to see that the above inequality is (almost) tight. For the stable n-homogeneous
polynomial p(y1 , . . . , ym ) = (y1 + · · · + yn )n , the LHS is n! and the RHS is (n/e)n .

2

Preliminaries

For a vector y, we write y ≤ 1 to denote that all coordinates of y are at most 1. For
an integer
[m]
n ≥ 1 we use [n] to denote the set of numbers {1, 2, . . . , n}. For any m, n, we let n denote the
collection of subsets of [m] of size n.

2.1

Stable Polynomials

Stable polynomials are natural multivariate generalizations of real-rooted univariate polynomials. For a complex number z, let Im(z) denote the imaginary part of z. We say a polynomial
p(z1 , . . . , zm ) ∈ C[z1 , . . . , zm ] is stable if whenever Im(zi ) > 0 for all 1 ≤ i ≤ m, p(z1 , . . . , zm ) 6= 0.
We say p(.) is real stable, if it is stable and all of its coefficients are real. It is easy to see that any
univariate polynomial is real stable if and only if it is real rooted.
We say a polynomial p(z1 , . . . , zm ) is degree n-homogeneous, or n-homogenous, if every monomial of p has degree exactly n. Equivalently, p is n-homogeneous if for all a ∈ R, we have
p(a · z1 , . . . , a · zm ) = an p(z1 , . . . , zm ).
αm is square-free if α , . . . , α ∈ {0, 1}. For a set S ⊂ 2[m] we write
We say a monomial z1α1 . . . zm
1
m
Y
zS =
zi .
i∈S

Thus, we can represent a square-free monomial with the set of indices of variables of that monomial.
Fact 2.1. If p(z1 , . . . , zm ) and q(z1 , . . . , zm ) are stable then p · q is stable.
P
Fact 2.2. The polynomial i ai zi is stable if ai ≥ 0 for all i.

Polynomial optimization problems involving real stable polynomials with nonnegative coefficients can often be turned into concave/convex programs. Such polynomials are log-concave in the
positive orthant:
3

Theorem 2.3 ([Gül97]). For any n-homogeneous stable polynomial p(x1 , . . . , xn ) with nonnegative
coefficients, ln p(x) is concave in the positive orthant, Rn++ .
It is also an immediate corollary of Hölder’s inequality that a polynomial with nonnegative
coefficients is log-convex in terms of the log of its variables (for more details on log-convex functions
see [BV06]).
Fact 2.4. For any polynomial p(y1 , . . . , ym ) with nonnegative coefficients, ln p(y) is convex in terms
of ln y. In other words ln p(ez1 , . . . , ezm ) is convex in terms of z.
The following theorem is proved by Gurvits [Gur06].
Theorem 2.5 ([Gur06]). For any degree m-homogeneous stable polynomial p(z1 , . . . , zm ) with positive coefficients, let c[m] denote the coefficient of the multilinear monomial z1 · · · zm . If c[m] > 0,
then
p(z1 , . . . , zm )
m!
.
c[m] ≥ m inf
z>0
m
z1 . . . zm

2.2

Counting Matchings in Bipartite Graphs

Given a bipartite graph G = (X, Y, E) with weights w : E → R. The weight of a perfect matching
M is defined as follows:
Y
w(M ) =
we .
e∈M

Jerrum, Sinclair, and Vigoda in their seminal work designed a FPRAS to count the sum of
(weighted) perfect matchings of an arbitrary bipartite graph with nonnegative weights. This problem is also equivalent to the computation of the permanent of a non-negative matrix.
Theorem 2.6 ([JSV04]). There exists a randomized polynomial time algorithm that for any arbitrary bipartite graph G with n vertices and nonnegative weights and ǫ > 0 in time polynomial in
the size of G and 1/ǫ approximates the sum of weights of all perfect matchings of G within a 1 + ǫ
multiplicative error, with high probability.
A k-matching of a bipartite graph G = (X, Y, E) is a set M ⊆ E of size |M | = k such that no
two edges share an endpoint. The following corollary follows immediately from the above theorem.
For completeness, we prove it in the appendix.
Corollary 2.7. There is a randomized polynomial time algorithm that for any arbitrary bipartite
graph G with nonnegative edge weights and for any given ǫ > 0 and integer k ≤ n in time polynomial
in the size of G and 1/ǫ approximates the sum of the weights of all k-matchings of G within 1 + ǫ
multiplicative error, with high probability.

3

Approximation Algorithm for NSW Maximization

In this section, we give an approximation algorithm for the NSW maximization problem. We begin
by giving a mathematical programming relaxation that can be efficiently solved. For convenience,
we will aim to optimize
!
n
Y
vi (x)
i=1

4

which is the nth power of the NSW objective. Thus, it is enough to give an e−n -approximation to
the above objective. With a slight abuse of notation, we will also refer to problem of maximizing
the new objective as the Nash welfare problem. In Subsection 3.2, we give a rounding algorithm
that proves the guarantee claimed in Theorem 1.1.

3.1

Mathematical Programming Relaxation

We use the following mathematical program.
max
x

inf

y>0:y S ≥1,∀S∈([m]
n )

s.t.

n
Y
i=1




n
X

m
X
j=1



xi,j vi,j yj  ,

xi,j ≤ 1

(2)
∀ 1 ≤ j ≤ m,

i=1

xi,j ≥ 0

∀i, j.

First, we show that (2) is a relaxation of the Nash welfare problem and can be optimized in
polynomial time to an arbitrary accuracy.
Lemma 3.1. The mathematical program (2) is a relaxation of the Nash welfare problem and can
be optimized in polynomial time.
Proof. Let x∗ ∈ {0, 1}n×m be an optimal solution of the Nash welfare problem and let σ : [m] → [n]
denote the assignment, i.e., σ(j) = i if and only if x∗ij = 1. We show that x∗ is a feasible solution

Q
(2) of objective ni=1 vi (x∗ ). Consider any y > 0 such that y S ≥ 1 for each S ⊆ [m]
. Moreover
n

∗ = 1}. We have
let S = {S ∈ [m]
:
∀i
∈
[n],
∃j
∈
S
such
that
x
ij
n


n
m
Y
X
Q
P

x∗i,j vi,j yj  = S∈S y S j∈S vσ(j),j
i=1

j=1

P
Q
≥ S∈S j∈S vσ(j),j

Q  Pm ∗
= ni=1
j=1 xi,j vi,j

S
as required where we use the fact
that the objective of the
Qn that y∗ ≥ 1 for each S ∈ S. To show
mathematical program equals i=1 vi (x ), we consider the solution yj∗ = 1 for
Q each
P j ∈ [m].
To solve the mathematical program, we observe that the function ln ni=1 m
j=1 xi,j vi,j yj is
concave in x and convex in ln y, where ln y is the vector defined by taking logarithms of the vector
y coordinate-wise. These follow from Theorem 2.3 and Fact 2.4. Moreover, the constraints on x
and ln y are linear. Thus the above program can be formulated as a convex program and solved to
an arbitrary accuracy.

3.2

Randomized Algorithm I

We now give a rounding algorithm that proves the required guarantee. Algorithm 1 will only
satisfy the guarantee in expectation. Later, we show how to give a randomized algorithm that
gives essentially the same guarantee with high probability.
5

Algorithm 1 An Algorithm for NSW Maximization
Check whether the optimal solution has weight strictly more than zero using the bipartite matching algorithm. Return zero if answer is false.
Find an optimal solution x∗ to the mathematical program (2).
Independently for each item j ∈ [m], assign item j to one agent where agent i ∈ [n] is chosen
with probability x∗ij .
The first step of the algorithm can be implemented by a bipartite matching problem. Indeed
consider the bipartite graph with one side as agents and other as items. We have an edge (i, j) for
agent i and item j if vij > 0. The optimal solution to the NSW maximization problem is strictly
positive if and only if this bipartite graph has a matching that includes an edge at every agent.
Thus, we can check in polynomial time whether the optimal solution has weight zero. For the
remainder of the section, we assume that the optimal solution is strictly positive.
P
n×m
is a fractional allocation vector if for each j ∈ [m], ni=1 xi,j = 1. Given any
We say x ∈ R+
fractional allocation x, consider the following polynomial in variables y1 , . . . , yn ,


n
m
Y
X

xi,j vi,j yj  .
px (y1 , . . . , yn ) =
i=1

j=1

Observe that px (y) is a degree n-homogenous polynomial in m variables for any x or the identically
0 polynomial.
Lemma 3.2. We have the following.

1. For S ⊆ [m] of size n, let cS denote the coefficient of y S in px∗ (y). Then expected value of
Algorithm 1 equals
X
cS .
S∈([m]
n )

2. The optimal value of the relaxation (2) is
inf

y:y S ≥1,∀S∈([m]
n )

px∗ (y).

Proof. Let P
Xi,j be the random variable indicating that j is assigned to i. Then, the value that i
receives is m
j=1 Xi,j vi,j . So, the expected value of the algorithm is


#
" n
n
m
n X
X
Y
X
Y

Y
vi,σ(i) .
P ∀i : Xi,σ(i) = 1
Xi,j vi,j  =
Xi,σ(i) vi,σ(i) =
E
E
i=1 j=1

σ:[n]→[m]

i=1

i=1

σ:[n]→[m]




where σ is summed over all functions from [n] to [m]. Observe that P ∀i
Qn: Xi,σ(i)=1 6= 0 only if
σ is a one-to-one function. In such a case, we have P ∀i : Xi,σ(i) = 1 = i=1 xi,σ(i) where we use
the fact that each item is assigned independently. Therefore,


m
n
n X
Y
Y
X
Xi,j vi,j  =
xi,σ(i) vi,σ(i) .
E
i=1 j=1

σ:[n]

→

[m] i=1

one-to-one

6

Q
The lemma follows by the fact that for any one-to-one σ, the term ni=1 xi,σ(i) vi,σ(i) on the RHS

Q
appears in the coefficient of the (square-free) monomial ni=1 yσ(i) of px∗ (y). For any S ∈ [m]
n the
coefficient of y S in px∗ (y) is the sum of all such terms where σ([n]) = S.
The proof of the second claim is immediate by definition.
We are now ready to apply Theorem 1.2 and obtain the following immediate corollary.
Corollary 3.3. The expected objective of Algorithm 1 is at least
e−n · OPT
where OPT is the optimal NSW objective.
Proof. From Fact 2.1 and Fact 2.2, it follows that px∗ (y) as defined above is real stable with nonnegative coefficients. Moreover, it is an m-variate polynomial that is degree
n-homogenous. Let

cS denote the coefficient of square-free monomial y S for any S ∈ [m]
.
Since,
we assume that
n
there
is at least one assignment that has strictly positive NSW objective, the sum of coefficients
P
[m] cS > 0. Thus, from Theorem 1.2, we have
S∈( )
n

X

S∈(

cS

≥ e−n

[m]
n

)

min

y:y S ≥1,∀S∈([m]
n )

px∗ (y).

Now the proof is immediate using Lemma 3.2.

3.3

Randomized Algorithm II

From Corollary 3.3, the expected NSW of the allocation returned by Algorithm 1 is at least 1/en
fraction of the optimum. Repeated applications of the algorithm to obtain a high probability
bound is not possible since the output of Algorithm 1 may have an exponentially large variance.
In this section, we prove Theorem 1.1 by giving an algorithm that returns the same guarantee as
Algorithm 1 with high probability.
Proof of Theorem 1.1. We use the method of conditional expectations to prove the theorem. We
iteratively assign one item at a time, making sure that conditional expectation over the random
assignment of the remaining items does not decrease (substantially). We now claim that for any
assignment x, the expected value of the objective as given by randomized algorithm Algorithm 1
equals the number of weighted n-matchings of a bipartite graph. Consider the weighted bipartite
graph G = ([n], [m], E) where for any 1 ≤ i ≤ n and 1 ≤ jQ≤ m, wi,j = xi,j vi,j . Then, for one-to-one
mapping σ : [n] → [m], the coefficient of the monomial ni=1 xi,σ(i) vi,σ(i) is equal to the weight of
the n-matching {(1, σ(1)), (2, σ(2)), . . . , (n, σ(n))}. Therefore, the sum of square-free monomials of
px (y) is equal to the sum of the weights of all n-matchings of G.
Now, pick any item j ∈ [m] and any fractional assignment x. Consider the following n assignments, x1 , . . . , xn . Assignment xi assigns item j to i and rest of the items identically to the
fractional assignment x. Thus xiij = 1, xii′ ,j = 0 for all i 6= i′ and xii′ j ′ = xi′ j ′ for any j ′ 6= j. Let
ALGi denote the objective value of the output of Algorithm 1 on solution xi and ALG on x. Since
the objective value of the Algorithm 1 is linear in {xij : i ∈ [n]} for fixed j, we have
ALG =

n
X

xij ALGi

i=1

7

Thus ALG is the expected value of the conditional expected value of the output of the Algorithm 1
when we assign item j to one of the agents; it is assigned to agent i with probability xij .
By Corollary 2.7, we can estimate ALG and ALGi within a factor of 1 + 1/m3 factor in polynomial time. Therefore, using the method of conditional expectations, we obtain an allocation of
OPT
3 m ≥
NSW of value at least OPT
n where OPT denotes the objective of the
en · (1 − 1/m )
((1+ n1 )e)
optimal allocation.

4

A Generalization of Gurvits’s Theorem

In this section we prove Theorem 1.2. Let
q(y1 , . . . , ym ) = (y1 + · · · + ym )m−n
be a degree (m − n)-homogenous polynomial. It is straightforward to see that it is real stable.
Consider the polynomial p(y)q(y). Observe that this is a degree m-homogeneous stable polynomial
with non-negative coefficients. Since from the assumption of Theorem 1.2, at least one of the squarefree monomials in p(y) has a non-zero coefficient, the coefficient of the square-free monomial in
p(y)q(y) is non-zero. Let α[m] be the coefficient of the square-free monomial y1 · · · ym in p(y)q(y).
Thus, from Theorem 2.5, we have
α[m] ≥

m!
p(y)q(y)
inf
.
m
m y>0 y1 . . . ym

(3)

To prove Theorem 1.2 it is enough to relate the LHS and the RHS of (3) to the two sides of
(1). This is done in Lemma 4.1 and Proposition 4.2.
Lemma 4.1. We have
(m − n)!

X

S∈(

cS = α[m] .

[m]
n

)

Proof. The RHS is the coefficient of the square-free monomial y1 . . . , ym in p(y)q(y). The squarefree monomial of p(y)q(y) is obtained whenever we multiply a square-free monomial y S of p(y)

with the square-free monomial y S of q(y) for some S ∈ [m]
statement follows by the
n . Lemma’s
[m]
S
fact that the coefficient of y in q(y) is (m − n)! for every S ∈ n and the coefficient of y S in
p(y) is cS .
The proof of Theorem 1.2 is now immediate from the following proposition which relates the
RHS of (3) and (1).
Proposition 4.2.
p(y)q(y)
p(y).
≥ (m − n)m−n
inf
y>0 y1 . . . ym
y>0:y S ≥1,∀S∈(m
n)
inf

In the rest of this section we prove the above proposition. We do the proof in two steps. First,
we use convex duality to simplify the RHS, and then we prove the proposition.

8

Lemma 4.3.
inf

y>0:y S ≥1,∀S∈ m
n

( )

p(y) =

sup
P

0≤θ≤1:

m
j=1 θj =n

inf
y>0

p(y)
y1θ1

θm
. . . ym

.

Proof. The proof follows by convex duality. By taking logarithm of p(y) and the change of variable
zj = eyj , we obtain the following equivalent convex program to the LHS of the above inequality.
log p(ez1 , . . . , ezm )
 
X
[m]
s.t.
zi ≥ 0
∀S ∈
.
n
inf

(4)

i∈S

Let λS be the Lagrange dual variable associated to the constraint corresponding to the set S ∈
The Lagrangian of the above convex program is defined as follows:
X
X
L(z, λ) = log p(ez1 , . . . , ezm ) −
zi .
λS
S∈([m]
n )

[m]
n



.

i∈S

The Lagrange dual to (4) is
sup inf L(z, λ).
λ≥0 z

Since p(y) has a non-zero coefficient for at least one of the square-free monomials, the objective of
the convex program (4) is finite for any z and it is easy to see that Slater conditions are satisfied.
Thus the optimum value of the Lagrange dual is exactly equal to the
of (4).
P optimum
∗
∗
∗
Let z , λ be an optimum of the aboveP
program. We claim that S λS = 1. This simply follows
from first order optimality conditions. If S λ∗S < 1, then
X
X
∗
∗
(zj∗ − ǫ)
L(z∗ − ǫ, λ∗ ) = log p(ez1 −ǫ , . . . , ezm −ǫ ) −
λ∗S
S∈([m]
n )

= L(z∗ , λ∗ ) − n · ǫ +

X

j∈S

nλ∗S ǫ < L(z∗ , λ∗ ).

S∈([m]
n )

Similarly, if

λS > 1, L(z∗ + ǫ, λ∗ ) < L(z∗ , λ∗ ).
S∈([m]
n )
P
let L′ (z, θ) = p(ez ) − m
j=1 zj θj Thus, we

P

of size n. We

sup
P

0≤θ≤1:

by setting θj∗ =

P

S∈([m]
:j∈S
n )

m
j=1 θj =n

So, λ∗ is a probability distribution on sets
obtain that

inf L′ (z, θ) ≥ sup inf L(z, λ).
z

λ≥0 z

λ∗S to be the marginal probability of the element j.

We now claim that equality must hold in the above. This follows since given any θ ∈ {0 ≤ θ ≤
P
1: m
j=1 θj = n}, there exists a probability distribution over sets of size n such that marginal of

every element is exactly θj . Setting λ′S to be the probability of set S ∈ [m]
n , we obtain that for
any z and θ, we have L′ (z, θ) = L(z, λ′ ). Putting this together we have,
P

inf

[m]
j∈S zj ≥0,∀S∈( n )

log p(ez ) =

sup
P

0≤θ≤1:

9

m
j=1 θj =n

inf log p(ez ) −
z

m
X
j=1

zj θj .

Substituting ezj to yj and taking the exponential of the objective functions we have
inf

y>0:y S ≥1,∀S∈([m]
n )

p(y) =

sup
P

p(y)

inf

m
y>0 y θ1
1
j=1 θj =n

0≤θ≤1:

θm
. . . ym

as desired.
Now we give the proof of Proposition 4.2.
Proof of Proposition 4.2. By Lemma 4.3, it is enough to show that
inf
y>0

p(y)q(y)
p(y)
.
≥ (m − n)m−n
sup
inf θ
Pm
θm
1
y>0
y1 . . . ym
y1 . . . ym
0≤θ≤1: j=1 θj =n

P
Let θ be any vector such that 0 ≤ θ ≤ 1 and i θi = k. Equivalently, it is enough to show for any
such θ,
p(y)q(y)
p(y)
.
inf
≥ (m − n)m−n inf θ1
θm
y>0 y1 . . . ym
y>0 y . . . ym
1
We prove a stronger statement,
inf
y>0

p(y)
y1θ1

θm
. . . ym

· inf
y>0

q(y)
y11−θ1

1−θm
· ym

≥ (m − n)m−n inf
y>0

p(y)
y1θ1

θm
. . . ym

.

Equivalently, we show that
q(y)

inf

y>0 y 1−θ1
1

1−θm
. . . ym

≥ (m − n)m−n

Taking (m − n)-th root of both sides it is enough to show that
y1 + · · · + ym
≥ m − n,
α
α
y>0 y1 1 . . . ymm
inf

where αj =

1−θj
m−n

(5)

for all j ∈ [m]. Note that by definition of θ, we have 0 ≤ αj ≤
X

αj =

i

m−

Pm

j=1 θj

m−n

1
m−n

and that

= 1.

Therefore, the ratio in the LHS of (5) is homogeneous in y. Thus, to prove (5), it is enough to
prove the following
1
αm
sup
y1α1 . . . ym
≤
.
(6)
Pm
m
−n
y>0: j=1 yj =1
Next, we use the weighted AM-GM inequality. We let α1 , . . . , αm be the weights, and recall that
αj ’s sum to 1. Weighted AM-GM implies that
m
X
j=1


m
m
m 
Y
yj αj Y −αj Y αj
yj
yj
αj
=
≥
αj
αj
αj
j=1

j=1

10

j=1

Therefore,
y>0:

sup
P
m

j=1

m
Y

yj =1 j=1

α
yj j

≤

m
Y

α

αj j .

j=1

To prove (6), it is enough to show that
m
Y

α

αj j ≤

j=1

Or equivalently,

m
X

1
.
m−n

−αj log αj ≥ log(m − n).

j=1

Since αj ≤

1
m−n
m
X
j=1

and that

−αj log αj

Pm

j=1 αj

≥

= 1, we have

m
X
j=1

m

X
1
−αj log
αj = log (m − n),
= log (m − n)
m−n
j=1

as required.

References
[AFS08]

Arash Asadpour, Uriel Feige, and Amin Saberi. Santa claus meets hypergraph matchings. In Approximation, Randomization and Combinatorial Optimization. Algorithms
and Techniques, pages 10–20. Springer, 2008. 2

[AS07]

Arash Asadpour and Amin Saberi. An approximation algorithm for max-min fair allocation of indivisible goods. In STOC, pages 114–121, 2007. 2

[BS06]

N Bansal and M Sviridenko. The santa claus problem. In Proceedings of Symposium
on Theory of Computing, pages 31–40, 2006. 2

[BV06]

S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press,
2006. 4

[CCK09]

Deeparnab Chakrabarty, Julia Chuzhoy, and Sanjeev Khanna. On allocating goods to
maximize fairness. In Foundations of Computer Science, 2009. FOCS’09. 50th Annual
IEEE Symposium on, pages 107–116. IEEE, 2009. 2

[CDG+ 16] Richard Cole, Nikhil R. Devanur, Vasilis Gkatzelis, Kamal Jain, Tung Mai, Vijay V.
Vazirani, and Sadra Yazdanbod. Convex program duality, fisher markets, and nash
social welfare. Manuscript, 2016. 2
[CG15]

Richard Cole and Vasilis Gkatzelis. Approximating the nash social welfare with indivisible items. In STOC, pages 371–380. ACM, 2015. 2

11

[CKM+ 16] Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah,
and Junxing Wang. The unreasonable fairness of maximum nash welfare. In EC, 2016.
1
[Gül97]

Osman Güler. Hyperbolic polynomials and interior point methods for convex programming. MOR, 22(2):350–77, 1997. 4

[Gur06]

Leonid Gurvits. Hyperbolic polynomials approach to van der waerden/schrijver-valiant
like conjectures: Sharper bounds, simpler proofs and algorithmic applications. In
STOC, STOC ’06, pages 417–426, 2006. 2, 4

[JSV04]

Mark Jerrum, Alistair Sinclair, and Eric Vigoda. A polynomial-time approximation
algorithm for the permanent of a matrix with nonnegative entries. J. ACM, 51(4):671–
697, July 2004. 2, 4

[Lee15]

Euiwoong Lee. Apx-hardness of maximizing nash social welfare with indivisible items.
arXiv preprint arXiv:1507.01159, 2015. 1

[Mou04]

Hervé Moulin. Fair division and collective welfare. MIT press, 2004. 1

[NNRR14] Nhan-Tam Nguyen, Trung Thanh Nguyen, Magnus Roos, and Jörg Rothe. Computational complexity and approximability of social welfare optimization in multiagent
resource allocation. Autonomous agents and multi-agent systems, 28(2):256–289, 2014.
1
[NR14]

Trung Thanh Nguyen and Jörg Rothe. Minimizing envy and maximizing average nash
social welfare in the allocation of indivisible goods. Discrete Applied Mathematics,
179:54–68, 2014. 1

[NS16]

Aleksandar Nikolov and Mohit Singh. Maximizing determinants under partition constraints. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of
Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 192–201,
2016. 2

A

Miscellaneous Lemmas

Lemma A.1. For any k ≤ m, we have
m! (m − k)m−k
≥ e−k .
·
mm
(m − k)!
Proof. We prove by induction on k. The claim obviously holds for k = 0. For the induction step,
it is sufficient to show that
1 m! (m − k)m−k
m! (m − (k + 1))m−(k+1)
· m·
≤ m·
.
e m
(m − k)!
m
(m − (k + 1))!
Equivalently, it is enough to show that


m−k
m − (k + 1)

m−(k+1)

12

≤ e.

The above can be written as (1 +
ex .

1
m−k−1
m−k−1 )

≤ e. The latter follows by the fact that 1 + x ≤

Proof of Corollary 2.7.
Suppose that we are given a bipartite graph G = (X, Y, E) where
X = {x1 , . . . , xm } and Y = {y1 , . . . , yn }. Note that m is not necessarily equal to n. We construct
another graph G′ = (X ′ , Y ′ , E ′ ) such there is a one-to-(m − k)!(n − k)! and onto mapping between
the k-matchings of G and the perfect matchings of G′ . That is each k-matching of G is mapped to
a unique set of (m − k)!(n − k)! perfect matchings of G′ , and for each perfect matching M ′ of G′
there is a k-matching of G that has M ′ in its image.
Let X ′ = X ∪ {xm+1 , . . . , xm+n−k } and Y ′ = Y ∪ {yn+1 , . . . , ym+n−k }. The set of edges E ′ is the
union of E and the following edges: Connect all vertices of X ′ − X to all vertices of Y with weight
1, and connect all vertices of Y ′ − Y to all vertices of X with weight 1. Observe that for any kmatching M of G there are exactly (m − k)!(n − k)! perfect matchings in G′ that contain M ; for any
such prefect matching M ′ , we have M ′ − M ⊆ E ′ − E. So, this mapping is one-to-(m − k)!(n − k)!.
Furthermore, any perfect matching M ′ of G′ has exactly k edges in E, i.e., |M ′ ∩ E| = k. So, this
mapping is onto.
It follows that a 1 + ǫ approximation to the sum of the weights of all perfect matchings of G′ is
a 1 + ǫ approximation to the sum of the weights of all k-matchings of G.

13

