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.

Open Position for PhD Student or Post-Doc

Staff

Dr. Felix Brandt (principal investigator), Room 39
Markus Brill, Room 41
Felix Fischer, Room 41
Dr. Paul Harrenstein, Room 41

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

Vorlesung Algorithmische Graphentheorie (WS 2008/09)
Vorlesung Computational Social Choice (WS 2007/08)
Vorlesung Multiagentensysteme (SS 2007)
Hauptseminar Multiagentensysteme (WS 2006/07)
Hauptseminar Spieltheorie (SS 2006)

Visitors

Leon van der Torre, University of Luxembourg (July 2006)
Jan Remy, ETH Zurich (August 2006)
Vincent Conitzer, Duke University (December 2006)
Ariel Procaccia, Hebrew University (October 2007)
Xinhui Wang, University of Twente (September 2008)
Igor Razgon, University College Cork (October 2008)
Mathijs de Weerdt, Delft University of Technology (November 2008)
Davide Grossi, University of Luxembourg (November 2008)

Recent Publications

F. Brandt. Some remarks on Dodgson's voting rule. Mathematical Logic Quarterly, 55(4), 2009. To Appear. [ .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), 2009. To Appear. [ .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), 2009. To Appear. [ .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, 2008. To Appear. Early versions were presented at the 24th International Symposium on Theoretical Aspects of Computer Science (STACS) and the 17th International Conference on Game Theory (Stony Brook). [ link | .pdf ]

F. Brandt and P. Harrenstein. Dominance in social choice and coalitional game theory. 2008. Working Paper. Early versions were presented at the 5th International Conference on Logic, Game Theory and Social Choice (LGS), the Dagstuhl Seminar on Computational Issues in Social Choice, and the 8th Conference on Logic and the Foundations of Game and Decision Theory (LOFT). [ .pdf ]

F. Brandt, F. Fischer, P. Harrenstein, and Y. Shoham. Ranking games. Artificial Intelligence, 173(2):221-239, 2009. [ link | .pdf ]

F. Fischer, A. D. Procaccia, and A. Samorodnitsky. A new perspective on implementation by voting trees. 2008. Working Paper. 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 and F. Fischer. Computing the minimal covering set. Mathematical Social Sciences, 56(2):254-268, 2008. Early versions were presented at the 5th International Conference on Logic, Game Theory and Social Choice (LGS) and the 22nd Conference on Artificial Intelligence (AAAI). [ 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 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, 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 has been generated by bibtex2html 1.85.

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