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

Who: Claire Mathieu and Franco P. Preparata

When: MF 1:30-2:50

Where: CIT 506

What: The first half of the course (up until Spring break) will be on connecting computer science to economics: introduction to mechanism design, combinatorial auctions, computational efficiency in mechanisms, profit maximization, distributed aspects, cost sharing, and online mechanisms. The second half of the course consists of two topics in algorithmic theory: 3D-computational geometry, its model and foundations, convex hulls, intersection, proximity; introduction to quantum computing, foundations, networks, notable algorithms, and a critical review.

Evaluation: There will be one numerical grade for each half of the course, then the two grades will be reconciled by the two instructors into a final letter grade. Each student can choose whether they want a letter grade or prefer S/NC.

Algorithmic Game Theory (Claire Mathieu)

Here is how it will be.

Assignments:

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.

Schedule:

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