  Budget feasible mechanism design studies procurement combinatorial auctions
where the sellers have private costs to produce items, and the
buyer(auctioneer) aims to maximize a social valuation function on subsets of
items, under the budget constraint on the total payment. One of the most
important questions in the field is "which valuation domains admit truthful
budget feasible mechanisms with `small' approximations (compared to the social
optimum)?" Singer showed that additive and submodular functions have such
constant approximations. Recently, Dobzinski, Papadimitriou, and Singer gave an
O(log^2 n)-approximation mechanism for subadditive functions; they also
remarked that: "A fundamental question is whether, regardless of computational
constraints, a constant-factor budget feasible mechanism exists for subadditive
functions."
  We address this question from two viewpoints: prior-free worst case analysis
and Bayesian analysis. For the prior-free framework, we use an LP that
describes the fractional cover of the valuation function; it is also connected
to the concept of approximate core in cooperative game theory. We provide an
O(I)-approximation mechanism for subadditive functions, via the worst case
integrality gap I of LP. This implies an O(log n)-approximation for subadditive
valuations, O(1)-approximation for XOS valuations, and for valuations with a
constant I. XOS valuations are an important class of functions that lie between
submodular and subadditive classes. We give another polynomial time O(log
n/loglog n) sub-logarithmic approximation mechanism for subadditive valuations.
  For the Bayesian framework, we provide a constant approximation mechanism for
all subadditive functions, using the above prior-free mechanism for XOS
valuations as a subroutine. Our mechanism allows correlations in the
distribution of private information and is universally truthful.
