  The optimal pricing problem is a fundamental problem that arises in
combinatorial auctions. Suppose that there is one seller who has indivisible
items and multiple buyers who want to purchase a combination of the items. The
seller wants to sell his items for the highest possible prices, and each buyer
wants to maximize his utility (i.e., valuation minus payment) as long as his
payment does not exceed his budget. The optimal pricing problem seeks a price
of each item and an assignment of items to buyers such that every buyer
achieves the maximum utility under the prices. The goal of the problem is to
maximize the total payment from buyers. In this paper, we consider the case
that the valuations are submodular. We show that the problem is computationally
hard even if there exists only one buyer. Then we propose approximation
algorithms for the unlimited budget case. We also extend the algorithm for the
limited budget case when there exists one buyer and multiple buyers collaborate
with each other.
