History and Importance of the problem

Since the spectrum auction of Federal Communications Commission (FCC) in 1989, combinatorial auction becomes a very active field between economy and computer science [1]. On the other hand, the posted price mechanism is the cornerstone of the E-commerce, especially in online shopping. Therefore, it is meaningful to design combinatorial auction mechanisms via posted price.
In combinatorial auction, the valuation of bundle is not always equal to the sum of items in bundle naively (e.g. subaddictive, submodular, XOS, etc.). The aim of combinatorial auction is to maximize the social welfare by allocating the items. It is obvious that we can solve this problem by running VCG algorithm. However, VCG algorithm is computationally infeasible for complex problems [2]. Thus, a natural idea appears: can we design an approximate algorithm which can be implemented in polynomial time?

Main results

(The content of this part is a summary of “Combinatorial Auctions via Posted Prices, 1.3 Our results”)
Feldman et al. designed posted price mechanisms for XOS valuations and MPH-k valuations with constant approximation of social welfare, which can be computed in polynomial time. The valuation of buyers for items are independent to each other.

2-approximation algorithm for XOS
The algorithm has a low bound
$$ \frac{1}{2}E{v} \sim {F}\textrm{[A(v)]}-\epsilon $$
of social welfare and can be compute in
$$ POLY(n,m,\frac{1}{e}) $$
which is independent to the type space size.
For XOS and submodular & gross substitutes(GS), which are the 2 special cases of XOS, the novel DSIC mechanism has the lower bound with corresponding appropriate price assignment strategies that:

XOS: $$ \frac{e}{2(e-1)} - approximation $$
Submodular: $$ \frac{e}{2(e-1)} - approximation $$
GS: $$ \frac{1}{2} – approximation $$

k-approximation algorithm for MPH-k
The algorithm has low bound
$$ \frac{1}{2}E{v} \sim {F}\textrm{[A(v)]}-\epsilon $$
of social welfare and can be compute in
$$ POLY(n,m^{k},\frac{1}{e}) $$

Posted price for XOS valuations

(The content of this part is a summary of “Combinatorial Auctions via Posted Prices, 3 Posted Prices for XOS Valuations”. The MPH-k valuations is a more general situation and the algorithm for XOS valuation can be applied on it. The MPH-k part will be discussed in the presentation.)

Basic model of Combinatorial Auction
In this paper, the basic model is very similar with the model discussed in COMP559 lectures with a new element:

Demand correspondence: $$ D{i}(M,p)$$
$$ D{i}(M,p)$$ is a set of objects that maximize the utility of buyer i
Demand correspondence is easy to describe a set of items and the price when utility is maximized. And it also breaks the ties arbitrarily but consistently

Posted Price mechanism for XOS valuation
Input: n players, m items, valuation profile v
Output: Allocation profile A(v)
To reduce the size of input, there are 3 oracles are used in this mechanism:

Value Oracle: Input set T and return $$ v_{i}(T) $$
Demand Oracle: Input price vector p and return demand correspondence $$ D_{i}(M,p)$$
XOS Oracle: Input set T and return addictive function $$ A{i}(T) $$
The main theorem of this part is the theorem 3.1. It sets the constrains of $$ v{i} \sim F{i} $$. By using a-approximation algorithm based on theorem we can get an approximation factor a/2 with a small error variable. The results of XOS, GS and submodular can be seen in the “Main result” part.
To prove the theorem 3.1, the Lemma 3.1 provide a condition of appropriate choice price vector p’. p’ is computed by the Algorithm 1. Then sample a valuation profile $$ \hat{v}{i} \sim F{i} $$ repeatedly and compute the $$ \frac{1}{2} SW{j}(\hat{v}) $$. Because $$ \frac{1}{2} SW{j}(\hat{v}) $$ is sampled randomly and $$ 0\geq \frac{1}{2} SW{j}(\hat{v}) \leq1 $$. Then we can calculate the $$ X(\frac{1}{2} SW_{j}(\hat{v})) $$ with a small number of sampled items. The author provides the upper bound of t that
$$ t=\frac{4m^{2}(\log{m}+\log{n}-\log{\epsilon})}{\epsilon^{2}} $$

Suggestions for future directions

(The content of this part is a summary of “Combinatorial Auctions via Posted Prices, 5 Discussion and Open Problems”)

Constant approximation for subadditive valuation
The standard hierarchy of complement -free valuations are [3]: $$ additive \subset GS \subset submodular \subset XOS \subset subadditive $$ [3]. Now the mechanism with constant approximation of XOS can be implied. Is it possible to design a mechanism with constant approximation of subadditive?
Relax the constrains of items
The items are indivisible and heterogeneous in this paper. But the indivisible property is far away from the market in reality that every item may has several copies, which can be access by every buyer. Thus, the author provides a direction that use the posted price mechanism as the function to minimize the copy of items and find the positive results after the relaxation.

Reference:

[0]M.Feldman, N.Gravin, B.Lucier, “Combinatorial Auctions via Posted Prices”
[1]D. Porter, S. Rassenti, A. Roopnarine and V. Smith, “Combinatorial auction design”, Contributed by Vernon Smith, June 17, 2003,
[2] N.Nisan, A.Ronen,” Computationally Feasible VCG Mechanisms”, Journal of Artificial Intelligence Research 29 (2007) 19–47
[3] Benny Lehmann, Daniel Lehmann, and Noam Nisan. “Combinatorial auctions with decreasing marginal utilities”. Games and Economic Behavior, 55(2):270 – 296, 2006. Mini Special Issue: Electronic Market Design