Complements between goods - where one good takes on added value in the
presence of another - have been a thorn in the side of algorithmic mechanism
designers. On the one hand, complements are common in the standard motivating
applications for combinatorial auctions, like spectrum license auctions. On the
other, welfare maximization in the presence of complements is notoriously
difficult, and this intractability has stymied theoretical progress in the
area. For example, there are no known positive results for combinatorial
auctions in which bidder valuations are multi-parameter and
non-complement-free, other than the relatively weak results known for general
valuations.
To make inroads on the problem of combinatorial auction design in the
presence of complements, we propose a model for valuations with complements
that is parameterized by the "size" of the complements. A valuation in our
model is represented succinctly by a weighted hypergraph, where the size of the
hyper-edges corresponds to degree of complementarity. Our model permits a
variety of computationally efficient queries, and non-trivial
welfare-maximization algorithms and mechanisms.
We design the following polynomial-time approximation algorithms and truthful
mechanisms for welfare maximization with bidders with hypergraph valuations.
1- For bidders whose valuations correspond to subgraphs of a known graph that
is planar (or more generally, excludes a fixed minor), we give a truthful and
(1+epsilon)-approximate mechanism.
2- We give a polynomial-time, r-approximation algorithm for welfare
maximization with hypergraph-r valuations. Our algorithm randomly rounds a
compact linear programming relaxation of the problem.
3- We design a different approximation algorithm and use it to give a
polynomial-time, truthful-in-expectation mechanism that has an approximation
factor of O(log^r m).

研究中提出了一种评估具有互补性的商品的模型，该模型的参数化方法取决于互补性的 “大小”，并为各种计算机查询、效用最大化算法和机制提供了一种选择。