Instructor:   George Karakostas

Lectures:   M: 4:30 - 6:00 PM, Th: 4:00 - 5:30 PM, ITB/222    *** Note the time/day change ***

Office hours:  By appointment (or just walk in if I'm in my office and free)

Textbook:  "Algorithmic game theory"  by N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani. A non-printable electronic copy of the text can be found here.

Study material:

• Any books on game theory can be useful. An example is "Game Theory", 3rd ed., by G. Owen.
  
• For material more specific to this course, you can look at the list of similar courses compiled by Noam Nisan in his blog. Look at the last item on the right of the page. You'll see many courses sorted by the instructor who has taught them. It's a great source of lecture notes (usually by grad students) that can help you understand the material.
• For those of you more curious in what are the current open problems that occupy the community, Noam's blog is an excellent source. You can take a look at papers that appeared in recent relevant conferences (also on the right of the blog home page).
• Ten little treasures of game theory and ten intuitive contradictions, American Economic Review, 91, pp1402-1422, 2001
  

Course description:  

The course will concetrate on the study of algorithmic game-theory, i.e., the support that algorithms, and computer science in general, can provide to the efficient solution of problems that arise in competitive environments (such as markets). Game theory has been used ever since it was initiated by John von Neumann to model such environments, mainly by economists. We will try to understand the dual interaction between algorithms and competiveness: On the one hand, what properties should be present in algorithms whose users are self-interested entities? And, on the other hand,  how can  algorithmic design influence the behaviour of such entities? For example, if I am an eBay bidder, what should be my bidding strategy(algorithm) in order to gain  an item at the best possible price? (is it by chance that you see many bidders placing their bids in the last few seconds of the auction?) On the other hand, how would the bidding of eBay users change if I were to put a reserve price on an item? (what should this reserve be? and would you care to know, if you prove that computing it is NP-complete?) The range of applications is a little bigger than the entire universe, but we will try to pick and study topics with applicability to the real world and computational efficiency always at the back of our minds. 


Topics

1. Introduction (1.1 - 1.3 from AGT)
2. The inefficiency of equilibria (ch. 17 from AGT)
3. Network formation games and the potential function method (ch. 19 from AGT)
4. Introduction to mechanism design (9.1 - 9.5 from AGT)
5. Combinatorial auctions (ch. 11 from AGT)
6. Cost sharing (ch. 15 from AGT)
7. Computational evolutionary game theory (ch. 29 from AGT)
8. ....

Student evaluation:

The evaluation will be based on individual projects. Each project will be based on a particular research topic, and its grading will be done in 3 stages:

1. Project proposal (30%). The student should pick a general topic/problem that he/she finds interesting, and formulate it in a mathematically rigorous way. If the mathematical formulation of the problem is already available (use The Force, i.e., search engines, to start looking for similar problems that people have already tackled; game theory and economics are older than you, so libraries and real books are still full of things that you don't know, so look for them as well), the student should formulate at least 3 extensions of the basic formulation that may arise in practice. Do a carefull write-up and this completes the first step.
2. Project presentation  (40%). The student should prepare a slide presentation with the formulation of the problem, what has been done (you won't have time for technical lemmas and details; you should give us an idea of what people try to do to solve this problem, why it works, why it really doesn't, and how you'd improve if you could). Remember: your presentation goal is for the rest of us to remember some of it before we go to sleep that night (many people seem to forget that, and send us to sleep during the presentation).  Very important: Practice your presentation to make sure that you know exactly what to say, and that you finish on time!
3. Project write-up (30%). Do a write-up of your presentation, but in a more technical and detailed way.
4. Bonus: If the problem/topic you've considered seems novel, and/or you believe you have some ideas on how to improve on it, please come to see me, it may be interesting to work on for both of us.  
   

Prerequisites

Mathematical maturity and comfort with the design and analysis of algorithms is required, although no previous knowledge of game theory will be assumed. Undergrads that feel comfortable with their math are welcome to audit.


McMaster Course Policies
 
"The instructor and university reserve the right to modify elements of the course during the term. The university may change the dates and deadlines for any or all courses in extreme circumstances. If either type of modification becomes necessary, reasonable notice and communication with the students will be given with explanation and the opportunity to comment on changes. It is the responsibility of the student to check their McMaster email and course websites weekly during the term and to note any changes."

Academic Dishonesty

"Academic dishonesty consists of misrepresentation by deception or by other
fraudulent means and can result in serious consequences, e.g. the grade of
zero on an assignment, loss of credit with a notation on the transcript
(notation reads:  "Grade of F assigned for academic dishonesty"), and/or
suspension or expulsion from the university.

It is your responsibility to understand what constitutes academic
dishonesty.  For information on the various kinds of academic dishonesty
please refer to the Academic Integrity Policy, specifically Appendix 3,
located at http://www.mcmaster.ca/senate/academic/ac_integrity.htm

The following illustrates only three forms of academic dishonesty:
1.    Plagiarism, e.g. the submission of work that is not one's own or for which other credit has been obtained.  (e.g. submitting a copy of someone else's writeup for an assignment)
2.    Improper collaboration in group work. (e.g. collaboration between groups in an assignment)
3.    Copying or using unauthorized aids in tests and examinations."

 
Faculty Notices

"The Faculty of Engineering is concerned with ensuring an environment that is free of all discrimination.  If there is a problem, individuals are reminded that they should contact the Department Chair, the Sexual Harrassment Officer or the Human Rights Consultant, as the problem occurs." 

"The instructor and university reserve the right to modify elements of the
course during the term. The university may change the dates and deadlines
for any or all courses in extreme circumstances. If either type of
modification becomes necessary, reasonable notice and communication with the
students will be given with explanation and the opportunity to comment on
changes. It is the responsibility of the student to check their McMaster
email and course websites weekly during the term and to note any changes."