In revenue maximization of selling a digital product in a social network, the utility of an agent is often considered to have two parts: a private valuation, and linearly additive influences from other agents. We study the incomplete information case where agents know a common distribution about others' private valuations, and make decisions simultaneously. The "rational behavior" of agents in this case is captured by the well-known Bayesian Nash equilibrium. Two challenging questions arise: how to compute an equilibrium and how to optimize a pricing strategy accordingly to maximize the revenue assuming agents follow the equilibrium? In this paper, we mainly focus on the natural model where the private valuation of each agent is sampled from a uniform distribution, which turns out to be already challenging. Our main result is a polynomial-time algorithm that can exactly compute the equilibrium and the optimal price, when pairwise influences are non-negative. If negative influences are allowed, computing any equilibrium even approximately is PPAD-hard. Our algorithm can also be used to design an FPTAS for optimizing discriminative price profile.
The concept and existence of pessimistic and optimistic equilibria is not new. For instance, in analogous problems with externalities, Milgrom and Roberts @cite_10 and Vives @cite_2 have witnessed the existence of such equilibria in the complete information setting. Notice that our pricing problem, when restricted to complete information, can be trivially solved by an iterative method.
@cite_10 @cite_2
2130752181 2132275236
The authors study a rich class of noncooperative games that includes models of oligopoly competition, macroeconomic coordination failures, arms races, bank runs, technology adoption and diffusion, R&D competition, pretrial bargaining, coordination in teams, and many others. For all these games, the sets of pure strategy Nash equilibria, correlated equilibria, and rationalizable strategies have identical bounds. Also, for a class of models of dynamic adaptive choice behavior that encompasses both best-response dynamics and Bayesian learning, the players' choices lie eventually within the same bounds. These bounds are shown to vary monotonically with certain exogenous parameters. Copyright 1990 by The Econometric Society. Abstract Using lattice-theoretical methods, we analyze the existence and order structure of Nash equilibria of non-cooperative games where payoffs satisfy certain monotonicity properties (which are directly related to strategic complementarities) but need not be quasiconcave. In games with strategic complementarities the equilibrium set is always non-empty and has an order structure which ranges from the existence of a minimum and a maxinum element to being a complete lattice. Some stability properties of equilibria are also pointed out.