Amanatidis, Georgios and Fulla, Peter and Markakis, Evangelos and Sornat, Krzysztof (2021) Inequity aversion pricing over social networks: Approximation algorithms and hardness results. Theoretical Computer Science, 871. pp. 62-78. DOI https://doi.org/10.1016/j.tcs.2021.04.012
Amanatidis, Georgios and Fulla, Peter and Markakis, Evangelos and Sornat, Krzysztof (2021) Inequity aversion pricing over social networks: Approximation algorithms and hardness results. Theoretical Computer Science, 871. pp. 62-78. DOI https://doi.org/10.1016/j.tcs.2021.04.012
Amanatidis, Georgios and Fulla, Peter and Markakis, Evangelos and Sornat, Krzysztof (2021) Inequity aversion pricing over social networks: Approximation algorithms and hardness results. Theoretical Computer Science, 871. pp. 62-78. DOI https://doi.org/10.1016/j.tcs.2021.04.012
Abstract
We study a revenue maximization problem in the context of social networks. Namely, we generalize a model introduced by Alon, Mansour, and Tennenholtz [2] that captures inequity aversion, i.e., it captures the fact that prices offered to neighboring nodes should not differ significantly. We first provide approximation algorithms for a natural class of instances, where the total revenue is the sum 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 instance, to settings where the seller will only consider a fixed number of discount types or special offers. To complement our positive results, we resolve one of the open questions posed in [2] 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 large, or even when the number of allowed distinct prices is as small as three. Finally, we study extensions of the model regarding the demand type of the clients.
Item Type: | Article |
---|---|
Additional Information: | A preliminary conference version of this work appeared in MFCS 2016 |
Uncontrolled Keywords: | Revenue maximization; Inequity aversion; Social networks; Pricing; Approximation algorithms |
Divisions: | Faculty of Science and Health Faculty of Science and Health > Mathematics, Statistics and Actuarial Science, School of |
SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
Depositing User: | Unnamed user with email elements@essex.ac.uk |
Date Deposited: | 26 Nov 2021 14:41 |
Last Modified: | 07 Aug 2024 19:13 |
URI: | http://repository.essex.ac.uk/id/eprint/30374 |
Available files
Filename: Inequity_Aversion_Problem__TCS_j_version_(1).pdf
Licence: Creative Commons: Attribution-Noncommercial-No Derivative Works 3.0
Filename: 1606.06664v3.pdf