  Strategic interactions often take place in an environment rife with
uncertainty. As a result, the equilibrium of a game is intimately related to
the information available to its players. The \emph{signaling problem}
abstracts the task faced by an informed "market maker", who must choose how to
reveal information in order to effect a desirable equilibrium.
  In this paper, we consider two fundamental signaling problems: one for
abstract normal form games, and the other for single item auctions. For the
former, we consider an abstract class of objective functions which includes the
social welfare and weighted combinations of players' utilities, and for the
latter we restrict our attention to the social welfare objective and to
signaling schemes which are constrained in the number of signals used. For both
problems, we design approximation algorithms for the signaling problem which
run in quasi-polynomial time under various conditions, extending and
complementing the results of various recent works on the topic.
  Underlying each of our results is a "meshing scheme" which effectively
overcomes the "curse of dimensionality" and discretizes the space of
"essentially different" posterior beliefs -- in the sense of inducing
"essentially different" equilibria. This is combined with an algorithm for
optimally assembling a signaling scheme as a convex combination of such
beliefs. For the normal form game setting, the meshing scheme leads to a convex
partition of the space of posterior beliefs and this assembly procedure is
reduced to a linear program, and in the auction setting the assembly procedure
is reduced to submodular function maximization.
