Before revision:  In this case, we prove that finding the optimal advertising strategy is equivalent to finding the concave closure of a function, which is NP-hard in general . Based on this observation, we prove some properties of the optimal mechanism, which allow us to solve for the optimal mechanism by a convex program (of exponential size in general, polynomial size for special cases). We also prove some interesting characterizations of the optimal mechanisms based on these properties. 2. For the general problem when the seller faces buyers of different types and only knows the distribution of their types, it is NP-hard to find a constant factor approximation.
After revision:  In this case, we prove that finding the optimal advertising strategy is equivalent to finding the concave closure of a function, which is NP-hard in general . Based on this observation, we prove some properties of the optimal mechanism, which allow us to solve for the optimal mechanism by a finite-size convex program. The convex program will have a polynomial size if the state of the world has a constant number of possible realizations or the buyers face a decision problem with a constant number of options. For the general problem when the seller faces buyers of different types and only knows the distribution of their types, it is NP-hard to find a constant factor approximation.