  We study fair allocation of indivisible public goods subject to cardinality
(budget) constraints. In this model, we have n agents and m available public
goods, and we want to select $k \leq m$ goods in a fair and efficient manner.
We first establish fundamental connections between the models of private goods,
public goods, and public decision making by presenting polynomial-time
reductions for the popular solution concepts of maximum Nash welfare (MNW) and
leximin. These mechanisms are known to provide remarkable fairness and
efficiency guarantees in private goods and public decision making settings. We
show that they retain these desirable properties even in the public goods case.
We prove that MNW allocations provide fairness guarantees of Proportionality up
to one good (Prop1), $1/n$ approximation to Round Robin Share (RRS), and the
efficiency guarantee of Pareto Optimality (PO). Further, we show that the
problems of finding MNW or leximin-optimal allocations are NP-hard, even in the
case of constantly many agents, or binary valuations. This is in sharp contrast
to the private goods setting that admits polynomial-time algorithms under
binary valuations. We also design pseudo-polynomial time algorithms for
computing an exact MNW or leximin-optimal allocation for the cases of (i)
constantly many agents, and (ii) constantly many goods with additive
valuations. We also present an O(n)-factor approximation algorithm for MNW
which also satisfies RRS, Prop1, and 1/2-Prop.
