TL;DR
This paper explores how to optimally price "public goods" (like a shared snowblower or neighborhood Wi-Fi) that benefit not just the buyer, but also their social network neighbors. By modeling this as a two-stage network game, the authors show that simple, uniform pricing strategies can achieve a constant-factor approximation of optimal revenue, even when buyers strategize and attempt to free-ride.
What Problem Does This Paper Address?
Standard pricing models assume that a product only benefits the person who buys it. However, many products exhibit positive externalities on non-purchasers. If you buy a poster printer for your lab, neighboring labs might ask to use it. If you buy a snowblower, you might clear your neighbor's sidewalk. Because rational agents know they can benefit from their neighbors' purchases, they are incentivized to "free-ride" and wait for someone else to buy the good.
If a seller is forced to sell these (locally) public goods via private, individual sales, how should they set the price to maximize revenue? This is highly complex because buyers' decisions depend on the network topology and what they predict their neighbors will do. This leads to a Bayesian game with multiple Nash equilibria—some of which might result in terrible revenue for the seller if everyone decides to wait out their neighbors. The authors seek to find pricing mechanisms that guarantee high revenue even in the worst-case equilibrium.
Methods
The authors model the scenario as a two-stage game:
- The Seller posts a price (or a vector of prices) for the good.
- The Buyers (nodes in a graph $G$) observe the price and their own private valuation for the good (drawn from a known distribution $F$). They then play a simultaneous Bayesian game, deciding whether to buy based on a threshold strategy: they buy if their private value exceeds the price divided by the probability that none of their neighbors buy.
To analyze this, the authors use tools from mechanism design and auction theory. They draw a novel mathematical connection between the public goods pricing problem and the optimal single-item auction (Myerson's Lemma), as well as optimal stopping theory (the Prophet Inequality). For general networks, they formulate the equilibrium conditions as a mathematical program and use complexity theory (a reduction from 3-SAT) to prove the hardness of revenue approximation.
Datasets
Not discussed in the paper. (This is a theoretical paper focused on algorithmic game theory and mechanism design; it relies on mathematical proofs rather than empirical datasets).
Key Insights and Ideas
- The Single-Buyer Reduction: In a globally public good (a clique where everyone benefits if anyone buys), buyers strategize so that, in expectation, only one person will buy the product. This beautifully reduces the multi-buyer public goods problem to a single-item auction, allowing the authors to leverage existing auction theory.
- The "Hipster Game" Equivalence: The authors introduce a game with extreme negative externalities, where a buyer only gets value from a good if no one else in their neighborhood has it (e.g., a unique fashion statement). Surprisingly, the mathematical equilibrium structure and expected revenue of this Hipster Game are identical to the Public Goods game.
- Decoupling Price and Network Structure: For general networks, calculating the exact revenue for a given price is impossibly hard. However, if buyer valuations are uniformly distributed, the revenue equation can be mathematically decoupled into a "price component" and an "equilibrium/network component." This allows the seller to optimize the price without needing to know the actual structure of the social network.
Key Results
- Globally Public Goods (Cliques): The authors define a specific uniform price that guarantees the revenue in the worst-case equilibrium is at least a constant fraction (approx. 1/4) of the optimal Myerson revenue. This proves that complex price discrimination doesn't significantly outperform a single, well-chosen uniform price.
- $d$-Regular Graphs: For networks where everyone has exactly $d$ neighbors, a uniform price depending only on $d$ and the valuation distribution $F$ guarantees a constant fraction of the worst-case revenue of any other price.
- General Graphs are NP-Hard: For arbitrary networks, it is NP-hard to approximate the worst-case revenue for a given price to within a factor of $n^{1-\epsilon}$, even when valuations are drawn from a simple uniform distribution.
- A Simple Rule for Uniform Distributions: Despite the NP-hardness, if buyer values are drawn from a uniform distribution $[0,1]$, a seller who simply prices the good at $1/2$ is guaranteed to capture at least an $e/4$ fraction of the optimal worst-case revenue, completely independent of the network's shape.
Limitations and Future Work
Limitations: * The elegant result for general graphs relies heavily on the mathematical properties of the uniform distribution; the authors note it is an open question whether this extends to all regular distributions. * The model assumes the good is a perfect public good (the buyer and the neighbor get the exact same utility) and that consumption is binary (buy or don't buy).
Future Work: * Imperfect Public Goods: Modifying the utility function so the actual purchaser gets slightly more value than the free-riding neighbor. * Sequential Purchases: Analyzing the game if the seller approaches buyers one by one (using subgame perfect equilibrium) rather than forcing simultaneous decisions. * Alternative Objectives: Applying this framework to policy-making, such as a landlord setting a fine to encourage at least one tenant to shovel the snow, balancing revenue against social welfare.
Summary updated