Computational Perspectives on Economic Questions
University of British Columbia, Winter 2017 Term 1
Staff and Office Hours
Office hours: by appointment
There's no TA for the class.
We introduce some basic concepts in game theory and microeconomics but quickly delve into computational tools that are useful in reasoning about them. Emphasis will be on these tools; beautiful connections between the two areas come as bonuses.
- Possible topics to be covered:
- Linear programming; duality and its use in the design of appxorimation algorithms;
- Online learning;
- Optimization under uncertainty, e.g. correlation gap, prophet inequalities
- Communication complexity
- Some combinatorial structures, e.g. matroids, submodular functions.
Homework and Exams
- Proficiency with probability theory (not necessarily using measure theoretic language).
- Familiarity with undergraduate level algorithms and complexity theory (e.g., running time, NP-completeness, matching algorithms).
- No background knowledge in game theory or economics will be assumed.
- There will be roughly four take-home problem sets, a final exam and a project proposal. For most problems in the problem sets and the final exam, students are asked to give mathematical proofs.
- Students may work on homework in groups of up to 3 people. Each
group may turn in a single solution set that applies to all members of the
group. However, students are asked to understand each of their group's
solutions well enough to give an impromptu white-board presentation of
- For project proposal the students may also work in groups of up to 3 people. The proposal should outline motivations, concrete objectives, and viable attacks of the project, which is preferably related to some topic covered in class.
- The final is a take-home, non-cooperative exam. Students are asked to solve the problems independently.
Discussion Forum (Piazza)
- Your course grade will be based on homework, the exam and the project proposal. The weights are 50% for homework, 30% for the final exam and 20% for the project proposal.
- Students are highly encouraged to typeset their solutions for the homework problem sets and the final exam. Points will be taken off for ambiguous writing (e.g. using undefined notations in a proof), poorly organized arguments, or incomprehensible writing (e.g. sentences that are hard to parse).
We will be using Piazza
as an online discussion forum for the class. This allows for an open
discussion of questions related to CPSC 536F, visible to the
instructor and the other students in the course. You will
need to register as a student in the course by visiting