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
Students
- Sarah Bluhme (FoPra: "A graphical tool for computing tournament solutions"), completed 11/2008
- Maximilian Mair ("Implementing the tournament equilibrium set")
- Maximilian Meier (FoPra: "Computing Nash equilibria of normal-form games using support enumeration"), completed 12/2006
- 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 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 and P. Harrenstein.
Characterization of dominance relations in finite coalitional
games.
Theory and Decision, 2009.
To Appear.
[ .pdf ]
F. Brandt, F. Fischer, P. Harrenstein, and M. Mair.
A computational analysis of the tournament equilibrium set.
Social Choice and Welfare, 2009.
Accepted subject to minor revision.
[ .pdf ]
F. Brandt, M. Brill, F. Fischer, and J. Hoffmann.
The computational complexity of weak saddles.
2009.
Working Paper.
[ .pdf ]
F. Brandt.
Some remarks on Dodgson's voting rule.
Mathematical Logic Quarterly, 55(4):460-463, 2009.
[ .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), 2009.
To Appear.
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).
[ .pdf |
.ps.gz |
venue |
slides ]
F. Brandt, M. Brill, F. Fischer, and P. Harrenstein.
Computational aspects of Shapley's saddles.
In K. S. Decker and J. S. Sichman, editors, Proceedings of the
8th International Joint Conference on Autonomous Agents and Multi-Agent
Systems (AAMAS), 2009.
[ .pdf |
.ps.gz ]
D. Baumeister, F. Brandt, F. Fischer, and J. Rothe.
Deciding membership in minimal upward covering sets is hard for
parallel access to NP.
Technical report, http://arxiv.org/abs/0901.3692, 2009.
[ link |
.pdf ]
D. Baumeister, F. Brandt, F. Fischer, and J. Rothe.
Deciding membership in minimal upward covering sets is hard for
parallel access to NP.
2009.
Working Paper.
F. Brandt, M. Brill, F. Fischer, and P. Harrenstein.
On the complexity of iterated weak dominance in constant-sum
games.
2009.
Working Paper.
[ .pdf ]
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.
Minimal stable sets in tournaments.
Technical report, http://arxiv.org/abs/0803.2138, 2008.
Presented at the 9th International Meeting of the Society of Social
Choice and Welfare.
[ link |
.pdf ]
F. Brandt, F. Fischer, and P. Harrenstein.
The computational complexity of choice sets.
Mathematical Logic Quarterly, 55(4):444-459, 2009.
[ .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 M. Mair.
A computational analysis of the tournament equilibrium set.
In U. Endriss and P. Goldberg, editors, Proceedings of the 2nd
International Workshop on Computational Social Choice (COMSOC), 2008.
[ venue ]
F. Brandt and P. Harrenstein.
Dominance in social choice and coalitional game theory.
In G. Bonanno, B. Löwe, and W. van der Hoek, editors,
Proceedings of the 8th Conference on Logic and the Foundations of Game and
Decision Theory (LOFT), 2008.
[ .pdf ]
F. Brandt, F. Fischer, P. Harrenstein, and Y. Shoham.
Ranking games.
Artificial Intelligence, 173(2):221-239, 2009.
[ link |
.pdf ]
F. Brandt and T. Sandholm.
Efficient privacy-preserving protocols for multi-unit auctions.
2007.
Working Paper.
F. Brandt and F. Fischer.
Computing the minimal covering set.
Mathematical Social Sciences, 56(2):254-268, 2008.
[ link |
.pdf ]
F. Brandt, F. Fischer, and M. Holzer.
On iterated dominance, matrix elimination, and matched paths.
Technical Report TR08-077, Electronic Colloquium on Computational
Complexity (ECCC), 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, F. Fischer, and M. Holzer.
Equilibria of graphical games with symmetries.
Technical Report TR07-136, Electronic Colloquium on Computational
Complexity (ECCC), 2007.
[ link |
.pdf ]
F. Brandt, F. Fischer, and P. Harrenstein.
Recognizing members of the Tournament Equilibrium set is
NP-hard.
Technical report, http://arxiv.org/abs/0711.2961, 2007.
[ link |
.pdf ]
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 ]
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, F. Fischer, and P. Harrenstein.
The computational complexity of choice sets.
In U. Endriss and J. Lang, editors, Proceedings of the 1st
International Workshop on Computational Social Choice (COMSOC), 2006.
[ venue ]
F. Brandt, F. Fischer, and M. Holzer.
Symmetries and the complexity of pure Nash equilibrium.
Technical Report TR06-091, Electronic Colloquium on Computational
Complexity (ECCC), 2006.
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 ]
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