4 Search Results for "Megiddo, Nimrod"


Document
Equilibrium Computation (Dagstuhl Seminar 14342)

Authors: Nimrod Megiddo, Kurt Mehlhorn, Rahul Savani, and Vijay V. Vazirani

Published in: Dagstuhl Reports, Volume 4, Issue 8 (2015)


Abstract
This report documents the program and outcomes of Dagstuhl Seminar 14342 "Equilibrium Computation". The seminar was at the leading edge of current topics related to equilibrium computation for games and markets. We summarize these topics, give the talk abstracts, and give brief summaries of the problems that were discussed in the open problem sessions.

Cite as

Nimrod Megiddo, Kurt Mehlhorn, Rahul Savani, and Vijay V. Vazirani. Equilibrium Computation (Dagstuhl Seminar 14342). In Dagstuhl Reports, Volume 4, Issue 8, pp. 73-88, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@Article{megiddo_et_al:DagRep.4.8.73,
  author =	{Megiddo, Nimrod and Mehlhorn, Kurt and Savani, Rahul and Vazirani, Vijay V.},
  title =	{{Equilibrium Computation (Dagstuhl Seminar 14342)}},
  pages =	{73--88},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{4},
  number =	{8},
  editor =	{Megiddo, Nimrod and Mehlhorn, Kurt and Savani, Rahul and Vazirani, Vijay V.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.4.8.73},
  URN =		{urn:nbn:de:0030-drops-47990},
  doi =		{10.4230/DagRep.4.8.73},
  annote =	{Keywords: Algorithms, Computational Complexity, Equilibrium Computation, Game Theory, Market Equilibrium, Nash Equilibrium}
}
Document
10171 Abstracts Collection – Equilibrium Computation

Authors: Edith Elkind, Nimrod Megiddo, Peter Bro Miltersen, Bernhard von Stengel, and Vijay V. Vazirani

Published in: Dagstuhl Seminar Proceedings, Volume 10171, Equilibrium Computation (2010)


Abstract
From April 25 to April 30, 2010, the Dagstuhl Seminar 10171 ``Equilibrium Computation'' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Edith Elkind, Nimrod Megiddo, Peter Bro Miltersen, Bernhard von Stengel, and Vijay V. Vazirani. 10171 Abstracts Collection – Equilibrium Computation. In Equilibrium Computation. Dagstuhl Seminar Proceedings, Volume 10171, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{elkind_et_al:DagSemProc.10171.1,
  author =	{Elkind, Edith and Megiddo, Nimrod and Miltersen, Peter Bro and von Stengel, Bernhard and Vazirani, Vijay V.},
  title =	{{10171 Abstracts Collection – Equilibrium Computation}},
  booktitle =	{Equilibrium Computation},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10171},
  editor =	{Edith Elkind and Nimrod Megiddo and Peter Bro Miltersen and Vijay V. Vazirani and Bernahrd von Stengel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10171.1},
  URN =		{urn:nbn:de:0030-drops-26738},
  doi =		{10.4230/DagSemProc.10171.1},
  annote =	{Keywords: Equilibrium computation, algorithmic game theory}
}
Document
Improved Algorithms for Computing Fisher's Market Clearing Prices

Authors: James B. Orlin

Published in: Dagstuhl Seminar Proceedings, Volume 10171, Equilibrium Computation (2010)


Abstract
We give the first strongly polynomial time algorithm for computing an equilibrium for the linear utilities case of Fisher's market model. We consider a problem with a set $B$ of buyers and a set $G$ of divisible goods. Each buyer $i$ starts with an initial integral allocation $e_i$ of money. The integral utility for buyer $i$ of good $j$ is $U_{ij}$. We first develop a weakly polynomial time algorithm that runs in $O(n^4 log U_{max} + n^3 e_{max})$ time, where $n = |B| + |G|$. We further modify the algorithm so that it runs in $O(n^4 log n)$ time. These algorithms improve upon the previous best running time of $O(n^8 log U_{max} + n^7 log e_{max})$, due to Devanur et al.

Cite as

James B. Orlin. Improved Algorithms for Computing Fisher's Market Clearing Prices. In Equilibrium Computation. Dagstuhl Seminar Proceedings, Volume 10171, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{orlin:DagSemProc.10171.2,
  author =	{Orlin, James B.},
  title =	{{Improved Algorithms for Computing Fisher's Market Clearing Prices}},
  booktitle =	{Equilibrium Computation},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10171},
  editor =	{Edith Elkind and Nimrod Megiddo and Peter Bro Miltersen and Vijay V. Vazirani and Bernahrd von Stengel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10171.2},
  URN =		{urn:nbn:de:0030-drops-26720},
  doi =		{10.4230/DagSemProc.10171.2},
  annote =	{Keywords: Market equilibrium, Fisher, strongly polynomial}
}
Document
Proportional Response as Iterated Cobb-Douglas

Authors: Michael J. Todd

Published in: Dagstuhl Seminar Proceedings, Volume 10171, Equilibrium Computation (2010)


Abstract
We show that the proportional response algorithm for computing an economic equilibrium in a Fisher market model can be interpreted as iteratively approximating the economy by one with Cobb-Douglas utilities, for which a closed-form equilibrium can be obtained. We also extend the method to allow elasticities of substitution at most one.

Cite as

Michael J. Todd. Proportional Response as Iterated Cobb-Douglas. In Equilibrium Computation. Dagstuhl Seminar Proceedings, Volume 10171, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{todd:DagSemProc.10171.3,
  author =	{Todd, Michael J.},
  title =	{{Proportional Response as Iterated Cobb-Douglas}},
  booktitle =	{Equilibrium Computation},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10171},
  editor =	{Edith Elkind and Nimrod Megiddo and Peter Bro Miltersen and Vijay V. Vazirani and Bernahrd von Stengel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10171.3},
  URN =		{urn:nbn:de:0030-drops-26713},
  doi =		{10.4230/DagSemProc.10171.3},
  annote =	{Keywords: Computing equilibria, Fisher market, proportional response algorithm, Cobb-Douglas utilities}
}
  • Refine by Author
  • 2 Megiddo, Nimrod
  • 2 Vazirani, Vijay V.
  • 1 Elkind, Edith
  • 1 Mehlhorn, Kurt
  • 1 Miltersen, Peter Bro
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 1 Algorithms
  • 1 Cobb-Douglas utilities
  • 1 Computational Complexity
  • 1 Computing equilibria
  • 1 Equilibrium Computation
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 3 2010
  • 1 2014

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