Skip to main content
construction release_alert
Scholars@Duke will be undergoing maintenance April 11-15. Some features may be unavailable during this time.
cancel
Journal cover image

On allocations with negative externalities

Publication ,  Conference
Bhattacharya, S; Kulkarni, J; Munagala, K; Xu, X
Published in: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
January 1, 2011

We consider the problem of a monopolist seller who wants to sell some items to a set of buyers. The buyers are strategic, unit-demand, and connected by a social network. Furthermore, the utility of a buyer is a decreasing function of the number of neighbors who do not own the item. In other words, they exhibit negative externalities, deriving utility from being unique in their purchases. In this model, any fixed setting of the price induces a sub-game on the buyers. We show that it is an exact potential game which admits multiple pure Nash Equilibria. A natural problem is to compute those pure Nash equilibria that raise the most and least revenue for the seller. These correspond respectively to the most optimistic and most pessimistic revenues that can be raised. We show that the revenues of both the best and worst equilibria are hard to approximate within sub-polynomial factors. Given this hardness, we consider a relaxed notion of pricing, where the price for the same item can vary within a constant factor for different buyers. We show a 4-approximation to the pessimistic revenue when the prices are relaxed by a factor of 4. The interesting aspect of this algorithm is that it uses a linear programming relaxation that only encodes part of the strategic behavior of the buyers in its constraints, and rounds this relaxation to obtain a starting configuration for performing relaxed Nash dynamics. Finally, for the maximum revenue Nash equilibrium, we show a 2-approximation for bipartite graphs (without price relaxation), and complement this result by showing that the problem is NP-Hard even on trees. © 2011 Springer-Verlag Berlin Heidelberg.

Duke Scholars

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

ISBN

9783642255090

Publication Date

January 1, 2011

Volume

7090 LNCS

Start / End Page

25 / 36

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Bhattacharya, S., Kulkarni, J., Munagala, K., & Xu, X. (2011). On allocations with negative externalities. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 7090 LNCS, pp. 25–36). https://doi.org/10.1007/978-3-642-25510-6_3
Bhattacharya, S., J. Kulkarni, K. Munagala, and X. Xu. “On allocations with negative externalities.” In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7090 LNCS:25–36, 2011. https://doi.org/10.1007/978-3-642-25510-6_3.
Bhattacharya S, Kulkarni J, Munagala K, Xu X. On allocations with negative externalities. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2011. p. 25–36.
Bhattacharya, S., et al. “On allocations with negative externalities.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7090 LNCS, 2011, pp. 25–36. Scopus, doi:10.1007/978-3-642-25510-6_3.
Bhattacharya S, Kulkarni J, Munagala K, Xu X. On allocations with negative externalities. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2011. p. 25–36.
Journal cover image

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

ISBN

9783642255090

Publication Date

January 1, 2011

Volume

7090 LNCS

Start / End Page

25 / 36

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences