Topics in Advanced Algorithmics: Algorithmic Game Theory, 3D Computational Geometry, Quantum Computing

Algorithmic Game Theory (Claire Mathieu)

Here is how it will be.


  • Assignment 1 due Feb 4 at 1:30pm.
  • Assignment 2, handed out in class, is due Feb 18 at 1:30pm, say.

    Office hours:

    M 3-5, CIT 555 and ("and"? Or is it "or"?) by appointment.


  • Class on Wednesday 2/13 at 1:30pm, root CIT Library (4th floor) to make up for Friday 2/8 snowday. W 2/13
  • First class at a special time, On Wednesday 1/23 at 1:30pm, room CIT 506. We covered: Book chapter 1 sections 1.1.1, 1.1.2, 1.1.4, 1.3.1, 1.3.3, 1.3.4, and 1.3.5. (did not finish the proof, which is not in the book)
  • The second class will be on Friday 1/25 at 1:30pm. Please read section 1.3.5 before then so that you can follow the end of the proof.
  • There will be no class on 1/28 and 1/31 (Claire is at a conference).
  • To make up for it, on the week of 2/3 there will be three classes instead of two, on M 2/4, W 2/6, and F 2/8.

  • References:

    We will use a tiny bit of the following textbook:
  • Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani. Algorithmic Game Theory. Cambridge University Press, New York, NY, USA, 2007. You can view the entire book online by going to the first page of the preface (viewable on Amazon for example) and folowing the instructions therein.

  • We will also read and present a selection of papers such as the following:
  • David Bindel, Jon M. Kleinberg, and Sigal Oren. How bad is forming your own opinion? CoRR, abs/1203.2973, 2012

  • Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, and Alexander Skopalik. Efficient computation of approximate pure nash equilibria in congestion games. In Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS '11, pages 532{541, Washington, DC, USA, 2011. IEEE Computer Society

  • Richard Cole, Vasilis Gkatzelis, and Vahab S. Mirrokni. Coordination mech- anisms for weighted sum of completion times in machine scheduling. CoRR, abs/1010.1886, 2010.

  • Paul W. Goldberg, Christos H. Papadimitriou, and Rahul Savani. The com- plexity of the homotopy method, equilibrium selection, and lemke-howson solutions. CoRR, abs/1006.5352, 2010.

  • Nicole Immorlica, Adam Tauman Kalai, Brendan Lucier, Ankur Moitra, Andrew Postlewaite, and Moshe Tennenholtz. Dueling algorithms. CoRR, abs/1101.2883, 2011.

  • Jon Kleinberg and Sigal Oren. Mechanisms for (mis)allocating scientic credit. In Proceedings of the 43rd annual ACM symposium on Theory of computing, STOC '11, pages 529{538, New York, NY, USA, 2011. ACM.

  • Stefano Leonardi and Tim Roughgarden. Prior-free auctions with ordered bidders. In Proceedings of the 44th symposium on Theory of Computing, STOC '12, pages 427{434, New York, NY, USA, 2012. ACM.

  • 3D Computational Geometry (Franco Preparata)

    Model and foundations, convex hulls, intersection, proximity.

    Quantum Computing (Franco Preparata)

    Introduction quantum computing, foundations, networks, notable algorithms, and a critical review