Search Results

Documents authored by Nisan, Noam

Document
DOI: 10.4230/LIPIcs.ICALP.2017.134
Selling Complementary Goods: Dynamics, Efficiency and Revenue

Authors: Moshe Babaioff, Liad Blumrosen, and Noam Nisan

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We consider a price competition between two sellers of perfect-complement goods. Each seller posts a price for the good it sells, but the demand is determined according to the sum of prices. This is a classic model by Cournot (1838), who showed that in this setting a monopoly that sells both goods is better for the society than two competing sellers. We show that non-trivial pure Nash equilibria always exist in this game. We also quantify Cournot's observation with respect to both the optimal welfare and the monopoly revenue. We then prove a series of mostly negative results regarding the convergence of best response dynamics to equilibria in such games.
Cite as

Moshe Babaioff, Liad Blumrosen, and Noam Nisan. Selling Complementary Goods: Dynamics, Efficiency and Revenue. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 134:1-134:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{babaioff_et_al:LIPIcs.ICALP.2017.134,
  author =	{Babaioff, Moshe and Blumrosen, Liad and Nisan, Noam},
  title =	{{Selling Complementary Goods: Dynamics, Efficiency and Revenue}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{134:1--134:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.134},
  URN =		{urn:nbn:de:0030-drops-74757},
  doi =		{10.4230/LIPIcs.ICALP.2017.134},
  annote =	{Keywords: Complements, Pricing, Networks, Game Theory, Price of Stability}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.140
Networks of Complements

Authors: Moshe Babaioff, Liad Blumrosen, and Noam Nisan

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We consider a network of sellers, each selling a single product, where the graph structure represents pair-wise complementarities between products. We study how the network structure affects revenue and social welfare of equilibria of the pricing game between the sellers. We prove positive and negative results, both of "Price of Anarchy" and of "Price of Stability" type, for special families of graphs (paths, cycles) as well as more general ones (trees, graphs). We describe best-reply dynamics that converge to non-trivial equilibrium in several families of graphs, and we use these dynamics to prove the existence of approximately-efficient equilibria.
Cite as

Moshe Babaioff, Liad Blumrosen, and Noam Nisan. Networks of Complements. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 140:1-140:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{babaioff_et_al:LIPIcs.ICALP.2016.140,
  author =	{Babaioff, Moshe and Blumrosen, Liad and Nisan, Noam},
  title =	{{Networks of Complements}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{140:1--140:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.140},
  URN =		{urn:nbn:de:0030-drops-62849},
  doi =		{10.4230/LIPIcs.ICALP.2016.140},
  annote =	{Keywords: Complements, Pricing, Networks, Game Theory, Price of Stability}
}
Document
DOI: 10.4230/DagRep.3.11.58
Electronic Markets and Auctions (Dagstuhl Seminar 13461)

Authors: Yishay Mansour, Benny Moldovanu, Noam Nisan, and Berthold Vöcking

Published in: Dagstuhl Reports, Volume 3, Issue 11 (2014)

Abstract
The main goal of this workshop was to study topics related to electronic markets and auctions both from the computational perspective and from a game-theoretic and economic one. From the computer science perspective, with the advent of the Internet, there has been a significant amount of work in Algorithmic Game Theory focusing on computational aspects of electronic markets and on algorithmic aspects of mechanism design. Economics have been traditionally interested in markets in general and designing efficient markets mechanisms (such as auctions) in particular. The recent emergence of electronic markets and auctions has only reemphasized the importance of this topic.
Cite as

Yishay Mansour, Benny Moldovanu, Noam Nisan, and Berthold Vöcking. Electronic Markets and Auctions (Dagstuhl Seminar 13461). In Dagstuhl Reports, Volume 3, Issue 11, pp. 58-78, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{mansour_et_al:DagRep.3.11.58,
  author =	{Mansour, Yishay and Moldovanu, Benny and Nisan, Noam and V\"{o}cking, Berthold},
  title =	{{Electronic Markets and Auctions (Dagstuhl Seminar 13461)}},
  pages =	{58--78},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{3},
  number =	{11},
  editor =	{Mansour, Yishay and Moldovanu, Benny and Nisan, Noam and V\"{o}cking, Berthold},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.11.58},
  URN =		{urn:nbn:de:0030-drops-44379},
  doi =		{10.4230/DagRep.3.11.58},
  annote =	{Keywords: Algorithmic game theory, mechanism design, economics, electronic markets}
}
Document
DOI: 10.4230/DagSemRep.172
Complexity of Boolean Functions (Dagstuhl Seminar 9711)

Authors: David Mix Barrington, Noam Nisan, Rüdiger Reischuk, and Ingo Wegener

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

David Mix Barrington, Noam Nisan, Rüdiger Reischuk, and Ingo Wegener. Complexity of Boolean Functions (Dagstuhl Seminar 9711). Dagstuhl Seminar Report 172, pp. 1-26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1997)

Copy BibTex To Clipboard

@TechReport{barrington_et_al:DagSemRep.172,
  author =	{Barrington, David Mix and Nisan, Noam and Reischuk, R\"{u}diger and Wegener, Ingo},
  title =	{{Complexity of Boolean Functions (Dagstuhl Seminar 9711)}},
  pages =	{1--26},
  ISSN =	{1619-0203},
  year =	{1997},
  type = 	{Dagstuhl Seminar Report},
  number =	{172},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.172},
  URN =		{urn:nbn:de:0030-drops-150594},
  doi =		{10.4230/DagSemRep.172},
}
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