ABSTRACT

In a given social network G, we study the problems of iterative pricing a product to consumers. We hope to maximize the revenue for seller. The value of product is determined by two factors: Consumer’s intrinsic value and the variable externalities. The consumer’s intrinsic value is fixed and the variable externality is negative or positive. In complete information network, we find that it is NP-hard to find an optimal iterative pricing. This paper gives the optimal strategies and revenues for the star network. We also proved that single pricing works well with 2-approximation for it.

Keywords:Social Network, Externality, Pricing Model, NP-Hard, Approximation

外部性商品的定价模型研究

徐汇成

浙江师范大学数理与信息工程学院，浙江 金华

收稿日期：2018年2月7日；录用日期：2018年2月21日；发布日期：2018年2月27日

摘 要

本文主要研究商品的定价问题，在给定的社会网络图G中，我们希望商家的收益最大化。商品的总价值取决于两个因素： 该商品对于消费者的固有价值；‚ 不断变化的外部性影响。在图G中，商品的固定价值以及外部性影响都是给定的，其中外部影响包括负外部性影响和正外部性影响，在这样的完全信息网络中，我们得出：找到最优的交互式定价策略是NP-难的。在星状网络图中，我们给出了最优的定价方案以及最大收益，并且证明了，通过单一定价能得到近似比为2的定价策略。

关键词 :社会网络，外部性影响，定价模型，NP难，近似比

Copyright © 2018 by author and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

对于社会网络重要性及其外部性的研究最早出现在经济领域。1984年Farrellhe 和Saloner在 [1] 一文中提到，在非完全信息网络中，可以通过外部性影响做出改革，从而找到更好的协调机制，替代原来的商品定价标准；1985年，Katz和Shapiro在 [2] 中进一步阐明了消费正外部性的存在，从而使得对商品的外部性有了更明确的定位。至此，外部性商品定价问题开始引起大家的注意。2008年，Hartline和 Mirrokni在 [3] 中首次从网络定价方面探讨商品扩散问题。他们发现：在允许区别定价的条件下，对于“目光短浅”的消费者，通过网络的正外部性影响及压榨式的定价方式，能够在全信息的社会网络中找到近似的最优营销策略(定价方案)。2010年，Akhlaghpour，Ghodsi和Haghpanah在 [4] 中首次介绍了正外部性商品的交互式定价，并构建了两个交互式定价模型。2011年，Chen, Lu, Sun, Tang, Wang和Zhu在 [5] 中讨论研究了非完全信息社会网络中，正外部性商品如何运用营销策略使得商家的利益最大化。2011年，Bhattacharya，Kulkarni，Munagala and Xu在 [6] 中证明了即使在树状网络图中，找到最优均衡依然是NP难的。2013年，Alon，Mansour，和Tenneholtz [7] 研究了区别定价造成消费者不公平心理所带来的负外部性。2014年和2017年，Cao，Chen，Hu and Wang [8] [9] 证明了找到最优定价的问题是NP难的，并且给出一些近似算法，对负外部性商品的定价进行了非常深入的研究。

本文主要是在 [9] 的基础上重新构建IPE (Iterative Pricing with Externalities)商品定价模型，进一步研究双重外部性影响下的商品定价问题。这里，我们同时考虑网络中的正负外部性。负外部性是指相关的消费者间，购买行为会降低未购买消费者对该商品的价值预估，正外部性影响则相反，会增加未购买消费者对该商品的价值预估。我们希望能找到定价策略，使得商家的收益达到最大化。

在第二节我们给出了IPE模型的介绍。在第三节我们证明了对IPE问题找到最优定价是NP难的，并且在星状网络图中给出了最优的交互式定价方案以及最大收益。在第四节我们证明了在星状网络图中，通过单一定价能得到近似比为2的定价策略。

2. 模型介绍

社会网络图 $G\left(V,E\right)$ 是一个简单图， $V$ 是表示所有节点(消费者)的集合， $E\left(G\right)$ 是表示所有消费者关联的边集合，其中消费者间的相互影响力(外部性影响力)用边的权重表示，并做如下规定：对 $\forall v_i,v_j\in V$ ，记权函数为 $w_{ij}\in {{\rm Z}}^{V\times V}$ ，当且仅当 $ij\notin E$ 时， $w_{ij}=w_{ji}=0$ ；默认相互间的影响力相同，即 $w_{ij}=w_{ji}$ ；若 $v_i,v_j$ 之间的外部性影响是正的，则 $w_{ij}=w_{ji}<0$ ，且 $e_{ij}\in E^{-}\left(G\right)$ ；反之，则 $w_{ij}=w_{ji}>0$ ，且 $e_{ij}\in E^{+}\left(G\right)$ ，记 $E\left(G\right)=E^{-}\left(G\right)\cup E^{+}\left(G\right)$ ，我们用 $\beta$ 表示 $E^{+}\left(G\right)$ 在 $E\left(G\right)$ 所占比例，即 $\beta =\frac{\left|E^{+}\left(G\right)\right|}{\left|E\left(G\right)\right|}$ 。

对任意消费者 $v_i\in V$ ，及任意消费者群体 $S\in V$ ，消费者 $v_i$ 在群体 $S$ 中受到的外部性影响等于 $v_i$ 与 $S$ 中所有关联边的权重之和，记为 $w_i\left(S\right)={\displaystyle {\sum }_{j\in S}{w}_{ij}}$ 。若图G不计权重，则 $w={\left\{-1,0,1\right\}}^{V\times V}$ 。

另外，消费者 $v_i\left(v_i\in V\right)$ 的商品固有价值，我们记为 $\gamma \left(i\right),\left(\gamma \left(i\right)\in R\right)$ 。在定价的过程中，消费者根据 $t$ 时刻的定价决定是否购买该产品，我们规定：每一次定价后未购买该商品的消费者群体 $Q\in V$ ，那么对任意消费者 $v_i$ ，此刻该商品的总价值等于固有价值与外部性影响之和，即 $\gamma \left(i\right)+w_i\left(Q\right)$ ，在给定的图 $G$ 中，所有消费者的商品总价值都不小于0，也就是说，对于 $\forall v_i\in V\left(G\right)$ ， $\gamma \left(i\right)+w_i\left(V\right)\ge 0$ 。

显然，初始值 $Q=V$ ，IPE模型如下进行：

l 交互式定价：商家按时公布价格，在一个时间序列下给出对应的价格序列；

l 消费者是冲动的：当商品的定价低于消费者的预估价值，消费者第一时间会购买；

l 商家是贪婪的：当该商品对消费者的总价值增加时，商家随时会涨价；

l 同步购买：新的定价一经公布，所有消费者会第一时间做出选择，购买或放弃；

给定时间序列 $T=\left(1,2,\cdots ,\tau \right)$ ，对应价格序列 $P=\left(p_1,p_2,\cdots ,p_{\tau }\right)$ ， $t$ 时刻的定价记 $p_t$ ，对任意的 $t\in \left\{1,2,\cdots ,\tau \right\}$ ，我们定义 $B\left(p_t\right)$ 为 $t$ 时刻以 $p_t$ 价格购买该商品所有消费者群体， $R\left(B\left(p_t\right)\right)$ 是通过第 $t$ 轮销售商家所获得的收益，是在价格序列的定价下商家所获得的收益，即。在单一定价时，，我们通常用表示。为了方便起见，我们也用表示价格的集合，用标号表示价格序列中一项。

值得注意的是，中的消费者若在时刻未消费，可能会在时刻以更高的价格购入该商品。直到所有消费者都购入，商家停止定价，此时。

通常，我们用表示最佳收益，在不赋权且内在价值统一为的情况下，我们也会用来表示最佳收益。

所谓IPE问题就是找到一个定价序列使得达到最大值，其中序列长度，以及每一序列项都是可确定的。当取到0时，只考虑正外部性影响；当取到1时，只考虑负外部性影响，即是IPN问题。

3. 交互式定价

定理1 [8] 对于IPN问题，计算出最优定价序列不仅在一般网络图上是NP难的，即使是在不带权且内在价值都为的树状网络图中也不例外。

事实上，IPN问题是IPE问题在时的一种特殊情况，显然IPE问题也是NP难的。所以我们有下面的推论。

推论2 对于IPE问题，计算出最优定价序列不仅在一般网络图上是NP难的，即使是在不带权且内在价值都为的树状网络图中也不例外。■

本节讨论在不带权且内在价值都为的星状网络图中，我们如何通过多次定价使得收益最大化。

定理3 图是以为中心点的不带权星状网络图中，若，点集，且，那么。

证明：如图1，令，满足对，，对，。已知，易得：对，，对，，且对中心点，满足。根据定义可知，，下面依据的大小进行分类讨论，其中分别表示不同的定价方案。

情形1

这种情况下，，其中。此时我们需要讨论三种方案：

图1. 具有外部性的星状网络图

l 方案：，；，；；

l 方案：，；，；；

l 方案：，；

故是最佳方案，可获得收益。

情形2

这种情况下，，其中，根据情形1的讨论易得：对于情形2，只用考虑情形1的后两种方案，显然最佳方案还是，可获得收益。

情形3

这种情况下，，其中。此时我们需要讨论三种方案：

l 方案：，，；，，，；

l 方案：，；，，；

l 方案：，；

故，是最佳方案，可获得收益；

情形4

这种情况下，有，其中，根据情形3的讨论易得：对于情形4，只用考虑情形1的，方案，显然最佳方案是，可获得收益；

情形5

这种情况下，，其中。此时我们需要讨论三种方案：

l 方案：，，。，，，；

l 方案：，。，，；

l 方案：，；

故是最佳方案，可获得收益。

综上所述，当，商家的最大收益是；当，商家的最大收益可以达到。由定义可知，，由此可得

. ■

4. 单一定价

定理3中我们已经证明了，对于星状网络图，通过多次定价能达到最优值，同时也给出了相应的最大收益。事实上，很多时候商家销售某商品都是进行统一固定的定价，很自然地，我们会思考：在单一定价下，商家是否依然能够获得比较好的收益呢？本节我们将证明，在星状网络图中，运用单一定价也能得到好的近似。

引理4 [8] 在不带权且不含孤立点的森林状网络图上，若每个点的固定价值相等，则能获得最大收益的单一定价是对IPN问题的1.5-近似的解决方案。

定理5 在不带权的星状网络图上，若每个点的固定价值都为，则存在近似比为2的单一定价策略用以解决IPE问题。

证明 图是不带权的星状网络图，，且每个点的固定价值都为，只要取或，那么得到的收益一定大于。

当时，结论是平凡的。下面考虑。

当时，，令，则，由定理3可知，最大收益，故

当时，根据引理4可知，能找到近似比为3/2的单一定价策略，令，则，由定理3可知，。

下面考虑且时，令，，则。

若，则，根据定理3，当时，能获得的最大收益是，令，则

.

当时，，令，则.

若，我们分4种情形进行讨论。

情形1

则，，令，有

.

情形2

则，若，那么，因此；若， 那么，。

情形3

则，当，令，则，当时，令或，都满足。

情形4

则，且，，若，那么，因此，若，依然满足。

综上所述，。 ■

致谢

感谢朱绪鼎教授对本文的帮助,也感谢所有匿名审稿人对本文的指导意见。

基金项目

国家自然科学基金项目资助(CNSF 00571319)。

文章引用

徐汇成. 外部性商品的定价模型研究
Pricing Model with Network Externalities[J]. 应用数学进展, 2018, 07(02): 189-194. http://dx.doi.org/10.12677/AAM.2018.72023

参考文献 (References)