Optimal mechanism design for the private supply of a public good

We study the problem of finding the profit-maximizing mechanism for a monopolistic provider of asingle, non-excludable public good. This problem has been well studied for the case when agents''types are independently distributed, but the literature is almost silent about the case of generaljoint distributions. We investigate the problem from an automated mechanism design perspective,meaning that we want to understand the algorithmic complexity of finding the optimal mechanismwhen we are given a finite set of type profiles and their distribution. We show that the optimaldeterministic, dominant strategy incentive compatible, ex-post individual rational mechanism canbe computed in polynomial time by reducing the problem to finding a maximal weight closure in adirected graph. Node weights in the graph correspond to conditional virtual values. Whenvaluations are independently distributed, the constructed mechanism is also optimal among allBayes-Nash implementable and ex-interim individual rational mechanisms. In contrast, for dependentvaluations strictly higher profit can be achieved if one allows for ex-interim individualrationality. By invoking techniques due to Crémer and McLean, we show that optimal deterministic,ex-interim individual rational, Bayes-Nash implementable or dominant strategy implementablemechanisms still can be found in polynomial time if the joint distribution of types satisfiescertain regularity conditions.