Document Open Access Logo

Inequity Aversion Pricing over Social Networks: Approximation Algorithms and Hardness Results

Authors Georgios Amanatidis, Evangelos Markakis, Krzysztof Sornat

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.9.pdf
  • Filesize: 0.56 MB
  • 13 pages

Document Identifiers

Author Details

Georgios Amanatidis
Evangelos Markakis
Krzysztof Sornat

Cite As Get BibTex

Georgios Amanatidis, Evangelos Markakis, and Krzysztof Sornat. Inequity Aversion Pricing over Social Networks: Approximation Algorithms and Hardness Results. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 9:1-9:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.MFCS.2016.9

Abstract

We study a revenue maximization problem in the context of social networks. Namely, we consider a model introduced by Alon, Mansour, and Tennenholtz (EC 2013) that captures inequity aversion, i.e., prices offered to neighboring vertices should not be significantly different. We first provide approximation algorithms for a natural class of instances, referred to as the class of single-value revenue functions. Our results improve on the current state of the art, especially when the number of distinct prices is small. This applies, for example, to settings where the seller will only consider a fixed number of discount types or special offers. We then resolve one of the open questions posed in Alon et al., by establishing APX-hardness for the problem. Surprisingly, we further show that the problem is NP-complete even when the price differences are allowed to be relatively large. Finally, we also provide some extensions of the model of Alon et al., regarding the allowed set of prices.

Subject Classification

Keywords
  • inequity aversion
  • social networks
  • revenue maximization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. H. Akhlaghpour, M. Ghodsi, N. Haghpanah, H. Mahini, V. S. Mirrokni, and A. Nikzad. Optimal iterative pricing over social networks (extended abstract). In Proceedings of the 6th Workshop on Internet and Network Economics, WINE 2010, pages 415-423, 2010. Google Scholar
  2. N. Alon, Y. Mansour, and M. Tennenholtz. Differential pricing with inequity aversion in social networks. In ACM Conference on Economics and Computation, EC 2013, pages 9-24, 2013. Google Scholar
  3. S. Bhattacharya, J. Kulkarni, K. Munagala, and X. Xu. On allocations with negative externalities. In Proceedings of the 7th Workshop on Internet and Network Economics, WINE 2011, pages 25-36, 2011. Google Scholar
  4. G. E. Bolton and A. Ockenfels. A theory of equity, reciprocity and competition. American Economic Review, 100:166-193, 2000. Google Scholar
  5. Z. Cao, X. Chen, X. Hu, and C. Wang. Pricing in social networks with negative externalities. In Proceedings of the 4th International Conference on Computational Social Networks, CSoNet 2015, pages 14-25, 2015. Google Scholar
  6. W. H. Cunningham. The optimal multiterminal cut problem. In Reliability Of Computer And Communication Networks, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, December 2-4, 1989, pages 105-120, 1989. Google Scholar
  7. P. Domingos and M. Richardson. Mining the network value of customers. In Proceedings of the 7th ACM International Conference on Knowledge Discovery and Data Mining, KDD 2001, pages 57-66, 2001. Google Scholar
  8. E. Fehr and K. M. Schmidt. A theory of fairness, competition and co-operation. Quarterly Journal of Economics, 114:817-868, 1999. Google Scholar
  9. D. Fotakis and P. Siminelakis. On the efficiency of influence-and-exploit strategies for revenue maximization under positive externalities. In Proceedings of the 8th Workshop on Internet and Network Economics, WINE 2012, pages 270-283, 2012. Google Scholar
  10. N. Garg, V. V. Vazirani, and M. Yannakakis. Multiway cuts in node weighted graphs. J. Algorithms, 50(1):49-61, 2004. Google Scholar
  11. A. Goldberg, J. Hartline, A. Karlin, M. Saks, and A. Wright. Competitive auctions. Games and Economic Behavior, 55(2):242-269, 2006. Google Scholar
  12. N. Haghpanah, N. Immorlica, V. S. Mirrokni, and K. Munagala. Optimal auctions with positive network externalities. In Proceedings of the 12th ACM Conference on Electronic Commerce, EC 2011, pages 11-20, 2011. Google Scholar
  13. J. Hartline, V. S. Mirrokni, and M. Sundararajan. Optimal marketing strategies over social networks. In Proceedings of the 17th international conference on World Wide Web, pages 189-198, 2008. Google Scholar
  14. D. Kempe, J. Kleinberg, and É. Tardos. Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 137-146, 2003. Google Scholar
  15. J. Kleinberg. Cascading behavior in networks: Algorithmic and economic issues. In N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, editors, Algorithmic Game Theory, chapter 24, pages 613-632. Cambridge University Press, Cambridge, 2007. Google Scholar
  16. M. D. Plummer and L. Lovász. Matching Theory. North-Holland Mathematics Studies. Elsevier Science, 1986. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact