17 Search Results for "Miltersen, Peter Bro"

Document
DOI: 10.4230/LIPIcs.MFCS.2017.80
Walrasian Pricing in Multi-Unit Auctions

Authors: Simina Brânzei, Aris Filos-Ratsikas, Peter Bro Miltersen, and Yulong Zeng

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
Multi-unit auctions are a paradigmatic model, where a seller brings multiple units of a good, while several buyers bring monetary endowments. It is well known that Walrasian equilibria do not always exist in this model, however compelling relaxations such as Walrasian envy-free pricing do. In this paper we design an optimal envy-free mechanism for multi-unit auctions with budgets. When the market is even mildly competitive, the approximation ratios of this mechanism are small constants for both the revenue and welfare objectives, and in fact for welfare the approximation converges to 1 as the market becomes fully competitive. We also give an impossibility theorem, showing that truthfulness requires discarding resources, and in particular, is incompatible with (Pareto) efficiency.
Cite as

Simina Brânzei, Aris Filos-Ratsikas, Peter Bro Miltersen, and Yulong Zeng. Walrasian Pricing in Multi-Unit Auctions. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 80:1-80:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{branzei_et_al:LIPIcs.MFCS.2017.80,
  author =	{Br\^{a}nzei, Simina and Filos-Ratsikas, Aris and Miltersen, Peter Bro and Zeng, Yulong},
  title =	{{Walrasian Pricing in Multi-Unit Auctions}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{80:1--80:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.80},
  URN =		{urn:nbn:de:0030-drops-81197},
  doi =		{10.4230/LIPIcs.MFCS.2017.80},
  annote =	{Keywords: mechanism design, multi-unit auctions, Walrasian pricing, market share}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.STACS.2014.11
Semi-algebraic geometry in computational game theory - a consumer's perspective (Invited Talk)

Authors: Peter Bro Miltersen

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
We survey recent applications of real algebraic and semi-algebraic geometry in (computational) game theory.
Cite as

Peter Bro Miltersen. Semi-algebraic geometry in computational game theory - a consumer's perspective (Invited Talk). In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 11-12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{miltersen:LIPIcs.STACS.2014.11,
  author =	{Miltersen, Peter Bro},
  title =	{{Semi-algebraic geometry in computational game theory - a consumer's perspective}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{11--12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.11},
  URN =		{urn:nbn:de:0030-drops-44994},
  doi =		{10.4230/LIPIcs.STACS.2014.11},
  annote =	{Keywords: Real Algebraic Geometry, Computational Game Theory}
}
Document
DOI: 10.4230/DagSemProc.10171.1
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.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
DOI: 10.4230/DagSemProc.10171.2
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.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
DOI: 10.4230/DagSemProc.10171.3
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.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}
}
Document
DOI: 10.4230/DagSemProc.08381.4
Depth Reduction for Circuits with a Single Layer of Modular Counting Gates

Authors: Kristoffer Arnsfelt Hansen

Published in: Dagstuhl Seminar Proceedings, Volume 8381, Computational Complexity of Discrete Problems (2008)

Abstract
We consider the class of constant depth AND/OR circuits augmented with a layer of modular counting gates at the bottom layer, i.e ${AC}^0 circ {MOD}_m$ circuits. We show that the following holds for several types of gates $G$: by adding a gate of type $G$ at the output, it is possible to obtain an equivalent randomized depth 2 circuit of quasipolynomial size consisting of a gate of type $G$ at the output and a layer of modular counting gates, i.e $G circ {MOD}_m$ circuits. The types of gates $G$ we consider are modular counting gates and threshold-style gates. For all of these, strong lower bounds are known for (deterministic) $G circ {MOD}_m$ circuits.
Cite as

Kristoffer Arnsfelt Hansen. Depth Reduction for Circuits with a Single Layer of Modular Counting Gates. In Computational Complexity of Discrete Problems. Dagstuhl Seminar Proceedings, Volume 8381, pp. 1-11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{hansen:DagSemProc.08381.4,
  author =	{Hansen, Kristoffer Arnsfelt},
  title =	{{Depth Reduction for Circuits with a Single Layer of Modular Counting Gates}},
  booktitle =	{Computational Complexity of Discrete Problems},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8381},
  editor =	{Peter Bro Miltersen and R\"{u}diger Reischuk and Georg Schnitger and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08381.4},
  URN =		{urn:nbn:de:0030-drops-17824},
  doi =		{10.4230/DagSemProc.08381.4},
  annote =	{Keywords: Boolean Circuits, Randomized Polynomials, Fourier sums}
}
Document
DOI: 10.4230/DagSemProc.08381.6
Understanding space in resolution: optimal lower bounds and exponential trade-offs

Authors: Eli Ben-Sasson and Jakob Nordström

Published in: Dagstuhl Seminar Proceedings, Volume 8381, Computational Complexity of Discrete Problems (2008)

Abstract
We continue the study of tradeoffs between space and length of resolution proofs and focus on two new results: begin{enumerate} item We show that length and space in resolution are uncorrelated. This is proved by exhibiting families of CNF formulas of size $O(n)$ that have proofs of length $O(n)$ but require space $Omega(n / log n)$. Our separation is the strongest possible since any proof of length $O(n)$ can always be transformed into a proof in space $O(n / log n)$, and improves previous work reported in [Nordstr"{o}m 2006, Nordstr"{o}m and H{aa}stad 2008]. item We prove a number of trade-off results for space in the range from constant to $O(n / log n)$, most of them superpolynomial or even exponential. This is a dramatic improvement over previous results in [Ben-Sasson 2002, Hertel and Pitassi 2007, Nordstr"{o}m 2007]. end{enumerate} The key to our results is the following, somewhat surprising, theorem: Any CNF formula $F$ can be transformed by simple substitution transformation into a new formula $F'$ such that if $F$ has the right properties, $F'$ can be proven in resolution in essentially the same length as $F$ but the minimal space needed for $F'$ is lower-bounded by the number of variables that have to be mentioned simultaneously in any proof for $F$. Applying this theorem to so-called pebbling formulas defined in terms of pebble games over directed acyclic graphs and analyzing black-white pebbling on these graphs yields our results.
Cite as

Eli Ben-Sasson and Jakob Nordström. Understanding space in resolution: optimal lower bounds and exponential trade-offs. In Computational Complexity of Discrete Problems. Dagstuhl Seminar Proceedings, Volume 8381, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{bensasson_et_al:DagSemProc.08381.6,
  author =	{Ben-Sasson, Eli and Nordstr\"{o}m, Jakob},
  title =	{{Understanding space in resolution: optimal lower bounds and exponential trade-offs}},
  booktitle =	{Computational Complexity of Discrete Problems},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8381},
  editor =	{Peter Bro Miltersen and R\"{u}diger Reischuk and Georg Schnitger and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08381.6},
  URN =		{urn:nbn:de:0030-drops-17815},
  doi =		{10.4230/DagSemProc.08381.6},
  annote =	{Keywords: Proof complexity, Resolution, Pebbling.}
}
Document
DOI: 10.4230/DagSemProc.08381.1
08381 Abstracts Collection – Computational Complexity of Discrete Problems

Authors: Peter Bro Miltersen, Rüdiger Reischuk, Georg Schnitger, and Dieter van Melkebeek

Published in: Dagstuhl Seminar Proceedings, Volume 8381, Computational Complexity of Discrete Problems (2008)

Abstract
From the 14th of September to the 19th of September, the Dagstuhl Seminar 08381 ``Computational Complexity of Discrete Problems'' was held in Schloss Dagstuhl - Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work as well as 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 report. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Peter Bro Miltersen, Rüdiger Reischuk, Georg Schnitger, and Dieter van Melkebeek. 08381 Abstracts Collection – Computational Complexity of Discrete Problems. In Computational Complexity of Discrete Problems. Dagstuhl Seminar Proceedings, Volume 8381, pp. 1-18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{miltersen_et_al:DagSemProc.08381.1,
  author =	{Miltersen, Peter Bro and Reischuk, R\"{u}diger and Schnitger, Georg and van Melkebeek, Dieter},
  title =	{{08381 Abstracts Collection – Computational Complexity of Discrete Problems}},
  booktitle =	{Computational Complexity of Discrete Problems},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8381},
  editor =	{Peter Bro Miltersen and R\"{u}diger Reischuk and Georg Schnitger and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08381.1},
  URN =		{none},
  doi =		{10.4230/DagSemProc.08381.1},
  annote =	{Keywords: Computational complexity, discrete problems, Turing machines, circuits, proof complexity, pseudorandomness, derandomization, cryptography, computational learning, communication complexity, query complexity, hardness of approximation}
}
Document
DOI: 10.4230/DagSemProc.08381.2
08381 Executive Summary – Computational Complexity of Discrete Problems

Authors: Peter Bro Miltersen, Rüdiger Reischuk, Georg Schnitger, and Dieter van Melkebeek

Published in: Dagstuhl Seminar Proceedings, Volume 8381, Computational Complexity of Discrete Problems (2008)

Abstract
Estimating the computational complexity of discrete problems constitutes one of the central and classical topics in the theory of computation. Mathematicians and computer scientists have long tried to classify natural families of Boolean relations according to fundamental complexity measures like time and space, both in the uniform and in the nonuniform setting. Several models of computation have been developed in order to capture the various capabilities of digital computing devices, including parallelism, randomness, and quantum interference.
Cite as

Peter Bro Miltersen, Rüdiger Reischuk, Georg Schnitger, and Dieter van Melkebeek. 08381 Executive Summary – Computational Complexity of Discrete Problems. In Computational Complexity of Discrete Problems. Dagstuhl Seminar Proceedings, Volume 8381, pp. 1-7, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{miltersen_et_al:DagSemProc.08381.2,
  author =	{Miltersen, Peter Bro and Reischuk, R\"{u}diger and Schnitger, Georg and van Melkebeek, Dieter},
  title =	{{08381 Executive Summary – Computational Complexity of Discrete Problems}},
  booktitle =	{Computational Complexity of Discrete Problems},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8381},
  editor =	{Peter Bro Miltersen and R\"{u}diger Reischuk and Georg Schnitger and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08381.2},
  URN =		{urn:nbn:de:0030-drops-17789},
  doi =		{10.4230/DagSemProc.08381.2},
  annote =	{Keywords: Computational complexity, discrete problems, Turing machines, circuits, proof complexity, pseudorandomness, derandomization, cryptography, computational learning, communication complexity, query complexity, hardness of approximation}
}
Document
DOI: 10.4230/DagSemProc.08381.3
Approximation norms and duality for communication complexity lower bounds

Authors: Troy Lee and Adi Shraibman

Published in: Dagstuhl Seminar Proceedings, Volume 8381, Computational Complexity of Discrete Problems (2008)

Abstract
Abstract: We will discuss a general norm based framework for showing lower bounds on communication complexity. An advantage of this approach is that one can use duality theory to obtain a lower bound quantity phrased as a maximization problem, which can be more convenient to work with in showing lower bounds. We discuss two applications of this approach. 1. The approximation rank of a matrix A is the minimum rank of a matrix close to A in ell_infty norm. The logarithm of approximation rank lower bounds quantum communication complexity and is one of the most powerful techniques available, albeit difficult to compute in practice. We show that an approximation norm known as gamma_2 is polynomially related to approximation rank. This results in a polynomial time algorithm to approximate approximation rank, and also shows that the logarithm of approximation rank lower bounds quantum communication complexity even with entanglement which was previously not known. 2. By means of an approximation norm which lower bounds multiparty number-on-the-forehead complexity, we show non-trivial lower bounds on the complexity of the disjointness function for up to c log log n players, c <1.
Cite as

Troy Lee and Adi Shraibman. Approximation norms and duality for communication complexity lower bounds. In Computational Complexity of Discrete Problems. Dagstuhl Seminar Proceedings, Volume 8381, pp. 1-9, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{lee_et_al:DagSemProc.08381.3,
  author =	{Lee, Troy and Shraibman, Adi},
  title =	{{Approximation norms and duality for communication complexity lower bounds}},
  booktitle =	{Computational Complexity of Discrete Problems},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8381},
  editor =	{Peter Bro Miltersen and R\"{u}diger Reischuk and Georg Schnitger and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08381.3},
  URN =		{urn:nbn:de:0030-drops-17768},
  doi =		{10.4230/DagSemProc.08381.3},
  annote =	{Keywords: Communication complexity, lower bounds}
}
Document
DOI: 10.4230/DagSemProc.08381.5
Fast polynomial factorization and modular composition

Authors: Kiran Kedlaya and Christopher Umans

Published in: Dagstuhl Seminar Proceedings, Volume 8381, Computational Complexity of Discrete Problems (2008)

Abstract
We obtain randomized algorithms for factoring degree $n$ univariate polynomials over $F_q$ requiring $O(n^{1.5 + o(1)} log^{1+o(1)} q+ n^{1 + o(1)}log^{2+o(1)} q)$ bit operations. When $log q < n$, this is asymptotically faster than the best previous algorithms (von zur Gathen & Shoup (1992) and Kaltofen & Shoup (1998)); for $log q ge n$, it matches the asymptotic running time of the best known algorithms. The improvements come from new algorithms for modular composition of degree $n$ univariate polynomials, which is the asymptotic bottleneck in fast algorithms for factoring polynomials over finite fields. The best previous algorithms for modular composition use $O(n^{(omega + 1)/2})$ field operations, where $omega$ is the exponent of matrix multiplication (Brent & Kung (1978)), with a slight improvement in the exponent achieved by employing fast rectangular matrix multiplication (Huang & Pan (1997)). We show that modular composition and multipoint evaluation of multivariate polynomials are essentially equivalent, in the sense that an algorithm for one achieving exponent $alpha$ implies an algorithm for the other with exponent $alpha + o(1)$, and vice versa. We then give two new algorithms that solve the problem optimally (up to lower order terms): an algebraic algorithm for fields of characteristic at most $n^{o(1)}$, and a nonalgebraic algorithm that works in arbitrary characteristic. The latter algorithm works by lifting to characteristic 0, applying a small number of rounds of {em multimodular reduction}, and finishing with a small number of multidimensional FFTs. The final evaluations are reconstructed using the Chinese Remainder Theorem. As a bonus, this algorithm produces a very efficient data structure supporting polynomial evaluation queries, which is of independent interest. Our algorithms use techniques which are commonly employed in practice, so they may be competitive for real problem sizes. This contrasts with all previous subquadratic algorithsm for these problems, which rely on fast matrix multiplication. This is joint work with Kiran Kedlaya.
Cite as

Kiran Kedlaya and Christopher Umans. Fast polynomial factorization and modular composition. In Computational Complexity of Discrete Problems. Dagstuhl Seminar Proceedings, Volume 8381, pp. 1-33, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{kedlaya_et_al:DagSemProc.08381.5,
  author =	{Kedlaya, Kiran and Umans, Christopher},
  title =	{{Fast polynomial factorization and modular composition}},
  booktitle =	{Computational Complexity of Discrete Problems},
  pages =	{1--33},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8381},
  editor =	{Peter Bro Miltersen and R\"{u}diger Reischuk and Georg Schnitger and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08381.5},
  URN =		{urn:nbn:de:0030-drops-17771},
  doi =		{10.4230/DagSemProc.08381.5},
  annote =	{Keywords: Modular composition; polynomial factorization; multipoint evaluation; Chinese Remaindering}
}
Document
DOI: 10.4230/DagSemProc.07471.1
07471 Abstracts Collection – Equilibrium Computation

Authors: P. Jean-Jacques Herings, Marcin Jurdzinski, Peter Bro Miltersen, Eva Tardos, and Bernhard von Stengel

Published in: Dagstuhl Seminar Proceedings, Volume 7471, Equilibrium Computation (2008)

Abstract
From 18 to 23 November 2007, the Dagstuhl Seminar 07471 ``Equilibrium Computation'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. 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

P. Jean-Jacques Herings, Marcin Jurdzinski, Peter Bro Miltersen, Eva Tardos, and Bernhard von Stengel. 07471 Abstracts Collection – Equilibrium Computation. In Equilibrium Computation. Dagstuhl Seminar Proceedings, Volume 7471, pp. 1-15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{herings_et_al:DagSemProc.07471.1,
  author =	{Herings, P. Jean-Jacques and Jurdzinski, Marcin and Bro Miltersen, Peter and Tardos, Eva and von Stengel, Bernhard},
  title =	{{07471 Abstracts Collection – Equilibrium Computation}},
  booktitle =	{Equilibrium Computation},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7471},
  editor =	{P. Jean-Jacques Herings and Marcin Jurdzinski and Peter Bro Miltersen and Eva Tardos and Bernhard von Stengel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07471.1},
  URN =		{urn:nbn:de:0030-drops-15286},
  doi =		{10.4230/DagSemProc.07471.1},
  annote =	{Keywords: Equilibrium, algorithm, polynomial time, game theory, economics}
}
Document
DOI: 10.4230/DagSemProc.07471.2
Equilibrium Tracing in Bimatrix Games

Authors: Anne Balthasar

Published in: Dagstuhl Seminar Proceedings, Volume 7471, Equilibrium Computation (2008)

Abstract
We analyze the relations of the van den Elzen-Talman algorithm, the Lemke-Howson algorithm and the global Newton method introduced by Govindan and Wilson. It is known that the global Newton method encompasses the Lemke-Howson algorithm; we prove that it also comprises the van den Elzen-Talman algorithm, and more generally, the linear tracing procedure, as a special case. This will lead us to a discussion of traceability of equilibria of index +1. We answer negatively the open question of whether, generically, the van den Elzen-Talman algorithm is flexible enough to trace all equilibria of index +1.
Cite as

Anne Balthasar. Equilibrium Tracing in Bimatrix Games. In Equilibrium Computation. Dagstuhl Seminar Proceedings, Volume 7471, pp. 1-14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{balthasar:DagSemProc.07471.2,
  author =	{Balthasar, Anne},
  title =	{{Equilibrium Tracing in Bimatrix Games}},
  booktitle =	{Equilibrium Computation},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7471},
  editor =	{P. Jean-Jacques Herings and Marcin Jurdzinski and Peter Bro Miltersen and Eva Tardos and Bernhard von Stengel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07471.2},
  URN =		{urn:nbn:de:0030-drops-15265},
  doi =		{10.4230/DagSemProc.07471.2},
  annote =	{Keywords: Bimatrix games, Equilibrium computation, Homotopy methods, Index}
}
Document
DOI: 10.4230/DagSemProc.07471.3
Homotopy Methods to Compute Equilibria in Game Theory

Authors: P. Jean-Jacques Herings and Ronald Peeters

Published in: Dagstuhl Seminar Proceedings, Volume 7471, Equilibrium Computation (2008)

Abstract
This paper presents a survey of the use of homotopy methods in game theory. Homotopies allow for a robust computation of game-theoretic equilibria and their refinements. Homotopies are also suitable to compute equilibria that are selected by various selection theories. We present the relevant techniques underlying homotopy algorithms. We give detailed expositions of the Lemke-Howson algorithm and the van den Elzen-Talman algorithm to compute Nash equilibria in 2-person games, and the Herings-van den Elzen, Herings-Peeters, and McKelvey-Palfrey algorithms to compute Nash equilibria in general $n$-person games. We explain how the main ideas can be extended to compute equilibria in extensive form and dynamic games, and how homotopies can be used to compute all Nash equilibria.
Cite as

P. Jean-Jacques Herings and Ronald Peeters. Homotopy Methods to Compute Equilibria in Game Theory. In Equilibrium Computation. Dagstuhl Seminar Proceedings, Volume 7471, pp. 1-40, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{herings_et_al:DagSemProc.07471.3,
  author =	{Herings, P. Jean-Jacques and Peeters, Ronald},
  title =	{{Homotopy Methods to Compute Equilibria in Game Theory}},
  booktitle =	{Equilibrium Computation},
  pages =	{1--40},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7471},
  editor =	{P. Jean-Jacques Herings and Marcin Jurdzinski and Peter Bro Miltersen and Eva Tardos and Bernhard von Stengel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07471.3},
  URN =		{urn:nbn:de:0030-drops-15257},
  doi =		{10.4230/DagSemProc.07471.3},
  annote =	{Keywords: Homotopy, Equilibrium computation, Non-cooperative games, Nash Equilibrium}
}
Document
DOI: 10.4230/DagSemProc.07471.4
Simple Stochastic Games, Parity Games, Mean Payoff Games and Discounted Payoff Games are all LP-Type Problems

Authors: Nir Halman

Published in: Dagstuhl Seminar Proceedings, Volume 7471, Equilibrium Computation (2008)

Abstract
We show that a Simple Stochastic Game (SSG) can be formulated as an LP-type problem. Using this formulation, and the known algorithm of Sharir and Welzl for LP-type problems, we obtain the first strongly subexponential solution for SSGs (a strongly subexponential algorithm has only been known for binary SSGs). Using known reductions between various games, we achieve the first trongly subexponential solutions for Discounted and Mean Payoff Games. We also give alternative simple proofs for the best known upper bounds for Parity Games and binary SSGs. To the best of our knowledge, the LP-type framework has been used so far only in order to yield linear or close to linear time algorithms for various problems in computational geometry and location theory. Our approach demonstrates the applicability of the LP-type framework in other fields, and for achieving subexponential algorithms. This work has been published in Algorithmica, volume 49 (September 2007), pages 37-50
Cite as

Nir Halman. Simple Stochastic Games, Parity Games, Mean Payoff Games and Discounted Payoff Games are all LP-Type Problems. In Equilibrium Computation. Dagstuhl Seminar Proceedings, Volume 7471, pp. 1-2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{halman:DagSemProc.07471.4,
  author =	{Halman, Nir},
  title =	{{Simple Stochastic Games, Parity Games, Mean Payoff Games and Discounted Payoff Games are all LP-Type Problems}},
  booktitle =	{Equilibrium Computation},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7471},
  editor =	{P. Jean-Jacques Herings and Marcin Jurdzinski and Peter Bro Miltersen and Eva Tardos and Bernhard von Stengel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07471.4},
  URN =		{urn:nbn:de:0030-drops-15274},
  doi =		{10.4230/DagSemProc.07471.4},
  annote =	{Keywords: Subexponential algorithm, LP-type framework}
}
  • Refine by Author
  • 7 Miltersen, Peter Bro
  • 2 Herings, P. Jean-Jacques
  • 2 Reischuk, Rüdiger
  • 2 Schnitger, Georg
  • 2 van Melkebeek, Dieter
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 3 Equilibrium computation
  • 2 Computational complexity
  • 2 Turing machines
  • 2 circuits
  • 2 communication complexity
  • Show More...

  • Refine by Type
  • 17 document

  • Refine by Publication Year
  • 10 2008
  • 3 2010
  • 2 2006
  • 1 2014
  • 1 2017

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact