On Iterative Pricing And Fashion Game In Social Networks

This paper studies two optimization problems in social networks:the problem of iterative pricing with positive and negative externalities,and an optimization problem of the fashion game on graphs.The problem of iterative pricing with positive and negative externalities asks how a monop-olist seller should price an indivisible product iteratively to the consumers who are connected by a known link-weighted directed social network.For two consumers u and v,there is an arc directed from u to v if and only if v is a fashion leader of u.Assuming complete information about the network,the seller offers consumers a sequence of prices over time and the goal is to obtain the maximum revenue.We assume that the consumers buy the product as soon as the seller posts a price not greater than their valuations of the product.The product’s value for a consumer is determined by three factors:a fixed consumer specified intrinsic value and a variable positive（resp.negative）externality that is exerted from the consumer’s out（resp.in）-neighbours.The setting of positive externality is that the influence of fashion leaders on a consumer is the total weight of links from herself to her fashion leaders who have owned the product,and more fashion leaders of a consumer owning the product will increase the influence（external value）on the consumer.And the setting of negative externalities is that the product’s value of showing off for a consumer is the total weight of links from her followers who do not own the product to herself,and more followers of a consumer owning the product will decrease this external value for the consumer.We confirm that finding an optimal iterative pricing is NP-hard even for acyclic networks with maximum（unweighted）total degree 3 and with all intrinsic values zero.We design a greedy algorithm which achieves（n-1）-approximation for networks with all intrinsic values zero and show that the approximation ratio n-1 is tight.Complemen-tary to the hardness result,we design a（1.8+（?））-approximation algorithm for Barabási-Albert networks.We propose and study an optimization problem of the fashion game on graphs,which can be regarded as a graph extension of matching pennies.There are two kinds of players in a simple graph G:Conformists and Rebels.A graph containing both types of players（resp.only rebels,conformists）is called a hybrid（resp.rebel,conformist）graph.All players choose their actions from an identical set of the two symmetric actions,say{0,1}.An action profile（AP for short）πof G is a mapping from the vertex set of G to the action set{0,1}.A conformist（resp.rebel）likes people having the same（resp.different）action with her and dislikes people having the different（resp.same）action.The utility u（v,π）of a player v under the action profileπis the number of neighbors she likes minus the number of neighbors she dislikes.In the vertex-weighted version of fashion game,each vertex is associated with a positive integer weight,and the utility of a player is the sum of weights of neighbors that she likes minus the sum of weights of neighbors that she dislikes.LetΦ:V（G）→Z be a function.TheΦ-satisfiability problem is to determine whether a graph has aΦ-AP,i.e.,an action profile under which each player v has a utility at leastΦ（v）.Let t be an integer.The t-satisfiability problem is the specializedΦ-satisfiability problem whenΦ（v）=t,for each v∈V（G）,and in this case aΦ-AP is called a t-AP.The utility of G,denoted by u（G）,is defined to be the maximum t such that G is t-satisfiable.Letη:V（G）→N be a function.A mapping c:V（G）→{0,1}is called anη-2-coloring of G if every v∈V（G）has at mostη（v）neighbors that have the same color with it.We provide simple characterizations to determine the utilities of paths,cycles,and com-plete graphs.We design a linear-time algorithm to determine the utility of a tree.We ob-tain lower bounds of utilities of graphs containing only rebels,t-degenerate graphs,and the kth power of paths,respectively.For hardness results,we prove that for any fixed integer t≥-2,the t-satisfiability problem for hybrid graphs is NP-complete;for t∈{1,2,3},the t-satisfiability problem for planar rebel graphs is also NP-complete;for any fixed integer t≥1,the t-satisfiability problem for rebel graphs is NP-complete too;the 1-satisfiability problem is NP-complete,even for rebel planar graph with girth at least 4.We study the fashion game on rebel graphs on surfaces,especially on planar graphs.For rebel graphs embeddable in surfaces,upper bounds of their utilities are given.The rebel graphs embeddable in the torus（S₁）or the Klein bottle（N₂）whose utilities reach their upper bounds are determined.Then the complexity of the t-satisfiability problem for rebel graphs embeddable in the plane（S₀）,projective plane（N₁）,torus（S₁）and the Klein bottle（N₂）,is totally determined,i.e.,it is NP-complete if t∈{1,2,3},and is polynomial time solvable otherwise.A sufficient condition is given for rebel graphs embeddable in any one of the four surfaces above to be1-satisfiable.We study dynamic algorithms for fashion game and vertex-weighted fashion game.For any graph whose treewidth is bounded by a constant k,a dynamic algorithm is designed to solve theΦ-satisfiability problem,and the time complexity is O(k8^kn^2k+2),where n denotes the number of vertices of the graph.As a corollary,this algorithm can also solve theη-2-coloring problem for such a graph.For outerplanar graphs,we designed a dynamic algorithm whose time complexity is improved to O（n⁴）,to solve theΦ-satisfiability problem.We show that the t-satisfiability problem of vertex-weighted fashion game is NP-hard even for rebel complete graphs.A polynomial-time dynamic algorithm is designed to solve the t-satisfiability problem for complete k-partite（hybrid）graphs.As a corollary,with a slight modification,we provide a pseudopolynomial dynamic algorithm to solve the t-satisfiability problem for vertex-weighted（hybrid）complete graphs.Any vertex-weighted rebel graph is proved to be 0-satisfiable,and we design pseudopolynomial and linear-time algorithms that provide 0-APs for vertex-weighted rebel graphs and vertex-weighted rebel complete graphs,respectively.If the number of actions chosen by players is extended to 3,then every vertex-weighted rebel graph with minimum de-gree at least 1 is 1-satisfiable,and a pseudopolynomial algorithm providing such a 3-strategy1-AP is designed.We finally propose some further research problems.