Pricing with Fairness: Navigating the Complexity of Inequity Aversion in Social Networks

TL;DR

How do you maximize revenue when your customers get angry because their friends got a better price? This paper provides the first comprehensive complexity map for Inequity Aversion Pricing. It introduces an exact polynomial-time algorithm for scenarios with two price points (e.g., a standard price and one discount tier) and proves that once you introduce a third price tier, the problem becomes NP-complete and APX-hard.

The Friction of Price Discrimination: Why Motivation Matters

Price discrimination is a double-edged sword. While it allows a seller to capture more surplus, the transparency of social networks (or geographic proximity of retail stores) leads to inequity aversion. If a customer sees their neighbor paying significantly less for the same digital good, they may decline the purchase entirely out of spite or perceived unfairness.

Previous research extensively covered positive externalities (how one person's purchase encourages others). This work flips the script, focusing on the negative constraints imposed by social links. The seller must decide not just individual prices, but also where to introduce discontinuities—essentially choosing not to offer a product to certain nodes to "break" the chain of price constraints and maximize global revenue.

Methodology: From Bipartite Graphs to Inductive Approximations

1. The Two-Price Breakthrough

The authors' most elegant contribution is solving the case of two available prices ($p_1,p_2$) exactly. They reduce the problem to a Maximum Weight Independent Set on a bipartite graph.

• The Intuition: If you only have a low price and a high price, the conflict only occurs on edges where the price difference exceeds a threshold. By modeling these conflicts as edges in a new graph $H$ and assigning weights to nodes, the optimal pricing strategy becomes a standard graph traversal problem.

Image Placeholder: Conceptual Flow of Bipartite Reduction

2. Generalizing for Few Discrete Prices

In the real world, airlines or software companies don't offer infinite prices; they offer "Gold," "Silver," and "Bronze" tiers. The authors provide an inductive algorithm that outperforms the broad $1/\ln (n)$ bounds typically used. By solving a simplified version of the problem and comparing it to a "single-price" baseline, they achieve much tighter approximation ratios for small sets of prices.

Complexity Results: The "Three is a Crowd" Rule

The paper's theoretical centerpiece is the proof of APX-hardness. By reducing from 3-Terminal Node Cut, the authors show that:

1. Setting $k=2$ prices is Easy (P-time).
2. Setting $k=3$ prices is Hard (NP-complete).
3. The problem is hard even if you allow very large price differences between neighbors, contradicting the intuition that "relaxed" constraints make the problem significantly easier.

Above: A comparison showing Algorithm 2 reaching a 1.0 (Optimal) ratio for two prices, unlike previous harmonic bounds.

Deep Insights: Multi-Unit Demand & Future Directions

One of the most surprising findings is that multi-unit demand (e.g., a customer wanting $s$ copies of a game) does not fundamentally change the complexity. As long as the demand is polynomially bounded, the problem reduces back to the single-unit case.

Takeaway for Practitioners

If you are designing automated pricing engines for a social platform:

• Limit your tiers: Managing more than two pricing tiers (beyond "standard" and "discounted") on a connected network introduces massive computational overhead if you want to be optimal.
• Targeted "Silence": Sometimes the most profitable move is to not make an offer to a "bridge" person in a social network, preventing a price conflict that would have forced lower prices on their entire social circle.

Final Thoughts

This work brilliantly bridges the gap between behavioral economics (fairness) and hard-core algorithmic theory. It reminds us that while "fairness" is often a social preference, for an algorithm designer, it is just another set of constraints that can turn a simple problem into a combinatorial puzzle.