Source-linked AI summary
Optimal Pricing in Networks with Externalities
Ozan Candogan, Kostas Bimpikis, Asuman Ozdaglar
TL;DR
The paper asks how a monopolist should price a divisible service when consumers’ usage is linked through local positive network effects. It models pricing and consumption as a network game and characterizes optimal policies under several pricing restrictions. Individualized prices depend on Bonacich centrality, uniform pricing is computable in polynomial time, and the two-price selection problem is NP-hard but admits an 88% approximation guarantee.
Problem
The paper studies how a monopolist can use network interactions to improve pricing for divisible goods whose consumers experience local positive network effects.
Method
The paper models sequential pricing and consumption as a network game and analyzes individualized, uniform, and two-price pricing policies using network structure.
Results
Individualized prices are characterized using Bonacich centrality, uniform-price optimization is polynomial-time computable, and the two-price problem is NP-hard with an 88% approximation guarantee.
Takeaways & Limitations
Network information has explicit value for pricing, and the paper provides a bound on the profit gains from using that information optimally.
Takeaways & Limitations
The tractable closed-form characterization relies on assumptions that sacrifice generality; relaxing some assumptions may produce multiple equilibria and prevent closed-form optimal prices.
Abstract
from arXiv · showhide
We study the optimal pricing strategies of a monopolist selling a divisible good (service) to consumers that are embedded in a social network. A key feature of our model is that consumers experience a (positive) local network effect. In particular, each consumer's usage level depends directly on the usage of her neighbors in the social network structure. Thus, the monopolist's optimal pricing strategy may involve offering discounts to certain agents, who have a central position in the underlying network. First, we consider a setting where the monopolist can offer individualized prices and derive an explicit characterization of the optimal price for each consumer as a function of her network position. In particular, we show that it is optimal for the monopolist to charge each agent a price that is proportional to her Bonacich centrality in the social network. In the second part of the paper, we discuss the optimal strategy of a monopolist that can only choose a single uniform price for the good and derive an algorithm polynomial in the number of agents to compute such a price. Thirdly, we assume that the monopolist can offer the good in two prices, full and discounted, and study the problem of determining which set of consumers should be given the discount. We show that the problem is NP-hard, however we provide an explicit characterization of the set of agents that should be offered the discounted price. Next, we describe an approximation algorithm for finding the optimal set of agents. We show that if the profit is nonnegative under any feasible price allocation, the algorithm guarantees at least 88% of the optimal profit. Finally, we highlight the value of network information by comparing the profits of a monopolist that does not take into account the network effects when choosing her pricing policy to those of a monopolist that uses this information optimally.
1. Introduction
The paper studies how a monopolist can use local positive network effects and social-interaction data to improve pricing for divisible services. It characterizes pricing under individualized, uniform, and two-price policies, including centrality-based discounts, a polynomial-time uniform-price algorithm, and an 88% approximation guarantee for the two-price problem.
- Motivation: Social-network data can improve firms’ business strategies because networks transmit information and influence among consumers.The paper motivates using observed interaction structure in pricing decisions.
- Motivation: Local positive network effects arise when a consumer’s usage increases the usage of her peers, potentially depending on the network’s broader structure.The model contrasts these local interactions with earlier global network-externality models.
- Pricing strategies: The monopolist may discount central consumers whose usage positively affects others’ purchasing decisions.The paper frames free or discounted access to selected consumers as an extreme version of this strategy.
- Pricing strategies: Individualized optimal prices decompose into a fixed cost, markup, and discount, with markup and discount proportional to neighbors’ Bonacich centrality.The result gives an economic interpretation of Bonacich centrality as a measure of network influence.
- Pricing strategies: A polynomial-time algorithm computes the optimal uniform price by evaluating a small number of consumer subsets ordered by weighted centrality.For each candidate subset, the algorithm obtains the constrained optimal price in closed form.
- Pricing strategies: 88% of optimal revenue is guaranteed by the approximation algorithm for selecting discounted consumers, while determining the optimal discounted set is NP-hard.The guarantee holds when profit is nonnegative under any feasible price allocation.
2. Model
The model describes a two-stage game in which a monopolist sets prices for a divisible good and consumers then choose usage levels under local positive network effects. Profits depend on price revenue and marginal production costs, while consumer utility combines intrinsic consumption value, network benefits, and payment.
- Network and pricing: Consumers are embedded in a network represented by adjacency matrix G, whose entry gij measures agent j’s influence on agent i.The model normalizes self-influence to zero and restricts influence strengths to [0,1].
- Network and pricing: The monopolist chooses an allowable price vector p, with pi denoting the per-unit price offered to consumer i.Pricing policies may map agents to prices in the general formulation.
- Consumer utility: Consumer i chooses usage xi ≥ 0 to maximize utility, which includes intrinsic utility, positive network effects, and the payment pixi.The network-effect term explicitly depends on the interaction structure and other consumers’ usage.
- Two-stage game: The game has two stages: the monopolist sets prices to maximize profit, then each consumer chooses usage given prices and peers’ usage.The analysis concerns subgame-perfect equilibria of this pricing-consumption game.
- Two-stage game: Consumption equilibria are defined for a fixed price vector, and the paper first analyzes this subgame before optimizing the monopolist’s pricing policy.The set of consumption equilibria at prices p is denoted C[p].
3. Consumption Equilibria
Under the paper’s assumptions, the consumption game has a unique equilibrium for every price vector and admits a closed-form characterization. The quadratic specification makes the analysis tractable while representing positive network effects and bounded consumption.
- Payoff assumptions: The paper assumes a quadratic payoff function combining intrinsic utility, positive network effects, and usage cost.The quadratic form is also described as a second-order approximation of broader concave payoffs.
- Payoff assumptions: Assumption 1 ensures that each agent’s optimal consumption level is bounded.Without it, a complete unit-weight network can yield payoffs that diverge as common consumption increases.
- Equilibrium existence: The equilibrium of the consumption game is unique for any price vector.The result is stated as the paper’s first equilibrium contribution under Assumption 1.
- Equilibrium existence: Positive externalities create strategic complementarities, allowing ordered equilibria to be used in proving uniqueness.The proof exploits monotonic ordering of equilibria.
- Equilibrium characterization: The unique equilibrium has a closed-form expression for some subset S of consumers with positive consumption.The equilibrium characterization uses restricted vectors and matrices associated with S.
- Equilibrium characterization: Each consumer’s equilibrium consumption is weakly decreasing in every offered price.If all prices rise componentwise, no consumer’s equilibrium usage increases.
4. Optimal Pricing
The paper analyzes three pricing regimes for a monopolist facing local positive network effects: individualized prices, one uniform price, and two prices. Network centrality shapes individualized discounts and markups, uniform pricing is polynomial-time computable, while two-price optimization is NP-hard but admits an approximation guarantee.
- Pricing regimes: The analysis covers perfect price discrimination, a single uniform price, and two exogenously specified prices.The pricing regimes are studied sequentially as restrictions on the monopolist’s price choices.
- Perfect Price Discrimination: Under symmetry and regularity assumptions, optimal individualized prices decompose into a nominal component, a network-based markup, and a network-based discount.The markup reflects utility derived from peers, while the discount reflects the positive effect of a consumer’s usage on peers.
- Perfect Price Discrimination: Agents influencing highly central consumers receive the most favorable individualized prices, with the relevant terms proportional to Bonacich centrality.When consumer parameters differ, the same structure extends using weighted Bonacich centrality.
- Choosing a Single Uniform Price: With one uniform price, equilibrium consumption decreases with price, and the active purchasing set changes according to consumers’ centrality gains.For prices between successive thresholds, precisely the agents in the corresponding active set purchase positive quantities.
- Choosing a Single Uniform Price: A polynomial-time algorithm computes the optimal uniform price by sequentially removing consumers with the lowest centrality gain.The algorithm evaluates candidate prices for the remaining consumers under the associated equilibrium.
5. How valuable is it to know the network structure?
The paper compares profits when the monopolist ignores network effects with profits under perfect network information and price discrimination. Network information is most valuable in asymmetric networks, while symmetric networks yield no gain from exploiting these effects.
- Information value: The comparison defines Π0 as profit from pricing as if gij = 0 and ΠN as profit from perfect network knowledge with price discrimination.The profit ratio Π0/ΠN measures the impact of network externalities.
- Bounds and simulations: Theoretical bounds relate the profit ratio to eigenvalues of Λ − G, which quantify deviation from symmetric interaction structures.The simulations use parameters making M = Λ − G positive definite and compare bounds with ratios computed from Lemma 3.
- Symmetric networks: Symmetric interaction networks provide no profit gain from accounting for network effects.For symmetric G, MM^-T = M^TM^-1 = I, simplifying the bounds and matching the stated corollary.
- Star networks: 15% higher profits occur for star networks with bi = n/10, while bi = n/20 produces a 100-fold increase at the asymmetric extremes.Smaller bi makes network effects relatively more significant; the simulations report a tight lower bound and an upper bound apparently equal to 1.
- Asymmetric networks: Asymmetric random matrices produce profit increases of almost 15% or 40%, depending on bi, whereas symmetric networks produce no gain.The lower bound is not tight for this network family, and smaller bi again yields a larger improvement.
- Preferential-attachment networks: Preferential-attachment simulations show larger profit losses from ignoring effects when older agents influence newer agents, because older agents are expected to have higher centrality.The plots are asymmetric because G1 and G2 are normalized differently, and smaller bi increases the improvement.
6. Conclusions
The paper characterizes optimal pricing for divisible goods over social networks and shows that network structure informs monopolist profits. Its tractable conclusions rely on restrictive assumptions and leave dynamic, incomplete-information, and competitive settings for future study.
- The paper gives explicit optimal-pricing characterizations for a monopolist selling divisible goods when consumers influence one another through a social network.
- The paper illustrates the value of network information by providing an explicit bound on the monopolist’s profit gains from knowing the network structure.
- Assumptions 1, 2, and 4 improve tractability and enable simple optimal-price expressions, but removing Assumptions 2 or 4 may create multiple subgame-perfect equilibria and prevent closed-form characterization.
- The analysis assumes static pricing and complete information about the network and utility functions, leaving dynamic pricing under incomplete information as a future direction.
- The model has a single monopolist; competitive sellers could offer larger discounts to central consumers, while disjoint subnetworks might permit market segmentation and local monopoly power.
Proof of Theorem 1
The proof establishes equilibrium properties using spectral-radius bounds, matrix invertibility, and supermodularity. These steps imply uniqueness of equilibrium and monotonicity of equilibrium consumption in prices.
- Under Assumption 1, the spectral radius of Λ^-1G is below 1, so I − Λ^-1G is invertible.
- The games with unrestricted and bounded strategy sets have the same pure Nash equilibrium set because no equilibrium can give any player consumption above the imposed bound.
- The bounded game is supermodular because strategy sets are lattices and cross-partial utilities are nonnegative, yielding minimum and maximum equilibrium elements.
- The maximum and any distinct equilibrium lead to a contradiction through the largest consumption difference, proving that both games have a unique equilibrium.
- Nonnegative entries of (Λ_S − G_S)^-1 imply that equilibrium consumption x_i(p) is weakly decreasing in every price.
Proof of Theorem 2
The proof shows that every consumer purchases a positive amount at an optimal price allocation. It does so by lowering one inactive consumer’s price while raising others’ prices without reducing their equilibrium consumption.
- Under Assumptions 1 and 2, every consumer purchases a positive amount at the optimal consumption equilibrium.
- Assuming some consumer purchases zero, the proof constructs a price vector that makes that consumer active while preserving the other consumers’ consumptions.
- The argument relies on the equilibrium best-response conditions and on nonsingularity of Λ − G to derive the required consumption response.
- The constructed price change increases the monopolist’s profit, contradicting optimality and establishing the positive-consumption result.
Proof of Theorem 3
The proof derives the optimal-price expression by rearranging the equilibrium system and applying a matrix inversion lemma. Under the stated parameter restriction, the resulting price vector has a simplified form.
- The equilibrium system is rearranged using the nonsingularity of Λ − G before deriving the optimal-price expression.
- The matrix inversion lemma is applied with specified matrix substitutions to obtain the needed inverse expression.
- Under Assumption 3, substituting Λ = 2b_0I and a = a_01 rewrites the vector of optimal prices in simplified form.
Proof of Theorem 4
The proof derives the result directly from an earlier equation and the definition of weighted Bonacich centrality.
- The claim follows immediately from equation (19) and the definition of weighted Bonacich centrality.
Proof of Lemma 2
The proof establishes positivity and strict monotonicity of equilibrium consumption as the price increases.
- The equilibrium consumption vector is characterized using the inverse matrix (ΛS − GS)^−1.
- Positive entries of the inverse matrix imply that each consuming agent’s consumption strictly decreases in p0.
- The proof relies on invertibility and nonnegative entries to rule out identically zero rows and establish positive consumption responses.
Proof of Theorem 5
The proof characterizes how agents exit consumption as prices rise, then establishes NP-hardness and an SDP-based approximation guarantee for the associated optimization problem.
- Price monotonicity: As price increases, equilibrium consumption decreases, and the agent with the smallest centrality gain stops purchasing first at a price proportional to that gain.
- Price monotonicity: At successive threshold prices pk, groups Dk stop purchasing, while the remaining agents Ik continue consuming positive quantities.
- NP-hardness: The reduction from MAX-CUT establishes that P1 is NP-hard.
- NP-hardness: The construction reduces P1 to an instance of F, and therefore shows that F and OPT are NP-hard.
- Approximation: Algorithm 2 uses an SDP relaxation and achieves at least 0.878 times the optimal objective value of the original quadratic problem.
- Approximation: The approximation result transfers to the pricing problem by rewriting it in the quadratic formulation and applying Corollary 2.