Foci: Multiagent Systems, Game Theory, Mechanism Design, and Cryptographic Protocols
The PAMAS research group is devoted to studying distributed protocols that allow autonomous entities to aggregate their conflicting preferences. Well-known examples of conventional preference aggregation among humans are auctions and voting. Scientific fields that traditionally deal with preference aggregation, such as social choice theory, game theory, mechanism design, and implementation theory reside somewhere on the boundaries of economics, mathematics, and political science. During the last years, preference aggregation has experienced a dramatic increase of attention from computer scientists coming from various fields such as artificial intelligence, theory, or networking. Computer science extends existing research by introducing computational and communication efficiency, decentralized mechanism execution, correctness, privacy, or new applications like scheduling, file-sharing, or knowledge transfer. The lab is hosted by the chair for theoretical computer science at the University of Munich and is funded by the DFG (German Research Foundation) within the Emmy Noether Program.
-->
Staff
Former Members
Students
- Sarah Bluhme (FoPra: "A graphical tool for computing tournament solutions"), completed 11/2008
- Nico Grupp (DA about game-theoretical aspects of game balance, joint supervision with Axel Hoppe)
- Maximilian Mair ("Implementing the tournament equilibrium set")
- Maximilian Meier (FoPra: "Computing Nash equilibria of normal-form games using support enumeration"), completed 12/2006
- Boris Turovskiy (DA about blocking coalitions in coalitional games)
- Eimund Waldemar (DA: "The computational complexity of Nash equilibria in games with few outcomes", joint supervision with Martin Schottenloher), completed 07/2008
- Philip Wassenberg (FoPra: "Implementation of a cryptographic comparison-protocol", DA: "Implementation and evaluation of cryptographic auction protocols"), completed 05/2007, 10/2008
Courses
Visitors
- Edith Elkind, Nanyang Technological University Singapore (September 2009)
- Edith Hemaspaandra, Rochester Institute of Technology (July 2009)
- Lane Hemaspaandra, University of Rochester (July 2009)
- Davide Grossi, University of Luxembourg (November 2008)
- Mathijs de Weerdt, Delft University of Technology (November 2008)
- Igor Razgon, University College Cork (October 2008)
- Xinhui Wang, University of Twente (September 2008)
- Ariel Procaccia, Hebrew University (October 2007)
- Vincent Conitzer, Duke University (December 2006)
- Jan Remy, ETH Zurich (August 2006)
- Leon van der Torre, University of Luxembourg (July 2006)
Recent Publications
F. Brandt, F. Fischer, and P. Harrenstein.
On the rate of convergence of fictitious play.
2010.
Working paper.
[ .pdf ]
F. Brandt, F. Fischer, and M. Holzer.
Equilibria of graphical games with symmetries.
Theoretical Computer Science.
Accepted subject to minor revision.
[ .pdf ]
F. Brandt, M. Brill, F. Fischer, P. Harrenstein, and J. Hoffmann.
Computing Shapley's saddles.
ACM SIGecom Exchanges, 8(2), 2009.
[ link |
.pdf |
.ps.gz ]
F. Brandt, M. Brill, F. Fischer, and P. Harrenstein.
Minimal retentive sets in tournaments.
In W. van der Hoek and G. A. Kaminka, editors, Proceedings of
the 9th International Joint Conference on Autonomous Agents and Multi-Agent
Systems (AAMAS), 2010.
Forthcoming.
[ .pdf |
venue ]
F. Brandt, M. Brill, F. Fischer, P. Harrenstein, and J. Hoffmann.
Computing Shapley's saddles.
ACM SIGecom Exchanges, 8(2), 2009.
[ link |
.pdf ]
F. Brandt, F. Fischer, and M. Holzer.
On iterated dominance, matrix elimination, and matched paths.
In J.-Y. Marion and T. Schwentick, editors, Proceedings of the
27th International Symposium on Theoretical Aspects of Computer Science
(STACS), Lecture Notes in Computer Science (LNCS). Springer-Verlag, 2010.
Forthcoming.
[ .pdf |
venue ]
F. Brandt and P. Harrenstein.
Set-rationalizable choice and self-stability.
Technical report, http://arxiv.org/abs/0910.3580, 2009.
[ link |
.pdf ]
H. Aziz, F. Brandt, and P. Harrenstein.
Monotone cooperative games and their threshold versions.
In W. van der Hoek and G. A. Kaminka, editors, Proceedings of
the 9th International Joint Conference on Autonomous Agents and Multi-Agent
Systems (AAMAS), 2010.
Forthcoming.
[ .pdf |
venue ]
H. Aziz, O. Lachish, M. Paterson, and R. Savani.
Wiretapping a hidden network.
In Proceedings of the 5th International Workshop on Internet and
Network Economics (WINE), volume 5929 of Lecture Notes in Computer
Science (LNCS), pages 438-446. Springer-Verlag, 2009.
N. Alon, F. Fischer, A. D. Procaccia, and M. Tennenholtz.
Sum of us: Strategyproof selection from the selectors.
2009.
arXiv:0910.4699. Working paper.
[ .pdf |
.ps.gz ]
F. Brandt.
Tournament solutions - Extensions of maximality and their
applications to decision-making.
Habilitation Thesis, Faculty for Mathematics, Computer Science, and
Statistics, University of Munich, 2009.
F. Brandt.
Minimal stable sets in tournaments.
Technical report, http://arxiv.org/abs/0803.2138, 2009.
Presented at the 9th International Meeting of the Society of Social
Choice and Welfare.
[ link |
.pdf ]
F. Brandt, M. Brill, E. Hemaspaandra, and L. Hemaspaandra.
Bypassing combinatorial protections: Polynomial-time bribery
algorithms for single-peaked electorates.
2009.
Working paper.
F. Fischer.
Complexity results for some classes of strategic games.
Dissertation, Fakultät für Mathematik, Informatik und
Statistik, Ludwig-Maximilians-Universität München, 2009.
[ link |
.pdf |
.ps.gz |
slides ]
F. Brandt.
Auctions.
In B. Rosenberg, editor, Handbook of Financial Cryptography.
CRC Press, 2010.
Forthcoming.
[ .pdf ]
F. Brandt and P. Harrenstein.
Characterization of dominance relations in finite coalitional
games.
Theory and Decision, 2009.
Forthcoming.
[ link |
.pdf ]
F. Brandt, F. Fischer, P. Harrenstein, and M. Mair.
A computational analysis of the tournament equilibrium set.
Social Choice and Welfare, 2009.
Forthcoming.
[ link |
.pdf ]
F. Brandt, M. Brill, F. Fischer, and J. Hoffmann.
The computational complexity of weak saddles.
In M. Mavronicolas and V. G. Papadopoulou, editors, Proceedings
of the 2nd International Symposium on Algorithmic Game Theory (SAGT), volume
5814 of Lecture Notes in Computer Science (LNCS), pages 238-249.
Springer-Verlag, 2009.
[ link |
.pdf |
venue ]
F. Brandt.
Some remarks on Dodgson's voting rule.
Mathematical Logic Quarterly, 55(4):460-463, 2009.
[ link |
.pdf ]
F. Fischer, A. D. Procaccia, and A. Samorodnitsky.
A new perspective on implementation by voting trees.
In Proceedings of the 10th ACM Conference on Electronic Commerce
(ACM-EC), pages 31-40, 2009.
Supersedes ”On Voting Caterpillars: Approximating Maximum Degree in
a Tournament by Binary Trees”, Technical Report 2008-06, Leibniz Center for
Research in Computer Science, The Hebrew University of Jerusalem. Also
presented at the 2nd International Workshop on Computational Social Choice
(COMSOC).
[ link |
.pdf |
.ps.gz |
venue |
slides ]
D. Baumeister, F. Brandt, F. Fischer, J. Hoffmann, and J. Rothe.
The complexity of computing minimal unidirectional covering
sets.
Technical report, http://arxiv.org/abs/0901.3692, 2009.
[ link |
.pdf ]
F. Brandt, M. Brill, F. Fischer, and P. Harrenstein.
On the complexity of iterated weak dominance in constant-sum
games.
In M. Mavronicolas and V. G. Papadopoulou, editors, Proceedings
of the 2nd International Symposium on Algorithmic Game Theory (SAGT), volume
5814 of Lecture Notes in Computer Science (LNCS), pages 287-298.
Springer-Verlag, 2009.
[ link |
.pdf |
venue ]
F. Brandt, M. Brill, F. Fischer, and P. Harrenstein.
Computational aspects of Shapley's saddles.
In Proceedings of the 8th International Joint Conference on
Autonomous Agents and Multi-Agent Systems (AAMAS), pages 209-216, 2009.
[ .pdf ]
F. Brandt, F. Fischer, and P. Harrenstein.
The computational complexity of choice sets.
Mathematical Logic Quarterly, 55(4):444-459, 2009.
[ link |
.pdf ]
F. Brandt, F. Fischer, and M. Holzer.
Equilibria of graphical games with symmetries.
In C. Papadimitriou and S. Zhang, editors, Proceedings of the
4th International Workshop on Internet and Network Economics (WINE), volume
5385 of Lecture Notes in Computer Science (LNCS), pages 198-209.
Springer-Verlag, 2008.
[ link |
.pdf ]
F. Brandt, F. Fischer, and M. Holzer.
Symmetries and the complexity of pure Nash equilibrium.
Journal of Computer and System Sciences, 75(3):163-177, 2009.
[ link |
.pdf ]
F. Brandt, F. Fischer, P. Harrenstein, and Y. Shoham.
Ranking games.
Artificial Intelligence, 173(2):221-239, 2009.
[ link |
.pdf ]
F. Brandt and F. Fischer.
Computing the minimal covering set.
Mathematical Social Sciences, 56(2):254-268, 2008.
[ link |
.pdf ]
F. Brandt, F. Fischer, P. Harrenstein, and M. Mair.
A computational analysis of the tournament equilibrium set.
In D. Fox and C. P. Gomes, editors, Proceedings of the 23rd AAAI
Conference on Artificial Intelligence (AAAI), pages 38-43. AAAI Press,
2008.
Also presented at the 2nd International Workshop on Computational
Social Choice (COMSOC).
[ .pdf |
venue ]
F. Brandt and F. Fischer.
On the hardness and existence of quasi-strict equilibria.
In B. Monien and U.-P. Schroeder, editors, Proceedings of the
1st International Symposium on Algorithmic Game Theory (SAGT), volume 4997
of Lecture Notes in Computer Science (LNCS), pages 291-302.
Springer-Verlag, 2008.
[ link |
.pdf |
venue ]
O. Dekel, F. Fischer, and A. D. Procaccia.
Incentive compatible regression learning.
In S.-H. Teng, editor, Proceedings of the 19th Annual ACM-SIAM
Symposium on Discrete Algorithms (SODA), pages 884-893. SIAM, 2008.
Earlier version presented at the Dagstuhl Seminar on Computational
Social Systems and the Internet and published as Leibniz Center Technical
Report 2007-112.
[ link |
.pdf |
.ps.gz |
venue |
slides ]
F. Brandt and F. Fischer.
PageRank as a weak tournament solution.
In X. Deng and F. Chung Graham, editors, Proceedings of the
3rd International Workshop on Internet and Network Economics (WINE), volume
4858 of Lecture Notes in Computer Science (LNCS), pages 300-305.
Springer-Verlag, 2007.
[ .pdf |
venue ]
F. Brandt and T. Sandholm.
On the existence of unconditionally privacy-preserving auction
protocols.
ACM Transactions on Information and System Security, 11(2),
2008.
[ link |
.pdf ]
F. Brandt and F. Fischer.
Computational aspects of covering in dominance graphs.
In R. C. Holte and A. Howe, editors, Proceedings of the 22nd
AAAI Conference on Artificial Intelligence (AAAI), pages 694-699. AAAI
Press, 2007.
Also presented at the 5th International Conference on Logic, Game
Theory and Social Choice (LGS).
[ link |
.pdf |
venue ]
F. Brandt, F. Fischer, and P. Harrenstein.
The computational complexity of choice sets.
In D. Samet, editor, Proceedings of the 11th Conference on
Theoretical Aspects of Rationality and Knowledge (TARK), pages 82-91. ACM
Press, 2007.
An early version was presented at the 1st International Workshop on
Computational Social Choice (COMSOC).
[ link |
.pdf |
venue ]
P. Harrenstein, F. Brandt, and F. Fischer.
Commitment and extortion.
In M. Huhns and O. Shehory, editors, Proceedings of the 6th
International Joint Conference on Autonomous Agents and Multi-Agent Systems
(AAMAS), pages 108-115. ACM Press, 2007.
[ .pdf |
venue ]
F. Brandt, F. Fischer, and M. Holzer.
Symmetries and the complexity of pure Nash equilibrium.
In W. Thomas and P. Weil, editors, Proceedings of the 24th
International Symposium on Theoretical Aspects of Computer Science (STACS),
volume 4393 of Lecture Notes in Computer Science (LNCS), pages
212-223. Springer-Verlag, 2007.
An early version was presented at the 17th International Conference
on Game Theory (Stony Brook).
[ link |
.pdf |
venue ]
F. Brandt, T. Sandholm, and Y. Shoham.
Spiteful bidding in sealed-bid auctions.
In M. Veloso, editor, Proceedings of the 20th International
Joint Conference on Artificial Intelligence (IJCAI), pages 1207-1214, 2007.
[ link |
.pdf |
venue ]
F. Brandt, F. Fischer, P. Harrenstein, and Y. Shoham.
A game-theoretic analysis of strictly competitive multiagent
scenarios.
In M. Veloso, editor, Proceedings of the 20th International
Joint Conference on Artificial Intelligence (IJCAI), pages 1199-1206, 2007.
[ link |
.pdf |
venue ]
F. Brandt, F. Fischer, and Y. Shoham.
On strictly competitive multi-player games.
In Y. Gil and R. Mooney, editors, Proceedings of the 21st
National Conference on Artificial Intelligence (AAAI), pages 605-612. AAAI
Press, 2006.
Also presented at the 17th International Conference on Game Theory
(Stony Brook).
[ link |
.pdf |
.ps |
venue ]
F. Fischer, M. Holzer, and S. Katzenbeisser.
The influence of neighbourhood and choice on the complexity of
finding pure Nash equilibria.
Information Processing Letters, 99(6):239-245, 2006.
[ link |
.pdf |
.ps.gz |
slides ]
F. Brandt.
How to obtain full privacy in auctions.
International Journal of Information Security, 5(4):201-216,
2006.
[ link |
.pdf |
.ps ]
This bibliography was generated by
bibtex2html 1.92.
Legal note: The original versions of Springer publications are available at www.springerlink.com.
Location
Computer Science Department
Theoretical Computer Science
University of Munich
Oettingenstr. 67
80538 Munich, Germany
Directions