Lecture: Combinatorial Auctions (Spring 2014)

This course will cover the economic and computational aspects of "combinatorial auctions," one of the most important paradigms in electronic market design. The prime example for combinatorial auctions are combinatorial spectrum auctions which have been used by governments around the world to auction off 3G and 4G spectrum, often generating billions of dollars in a single auction. But combinatorial auctions can also be used in many other domains, including to optimize a company's supply chain, to auction off airport take-off slots, or to auction off Wi-Fi bandwidth.

In the first half of the course, we will study the economic concepts that are foundational for an understanding of combinatorial auctions, including game theory, auction theory, and mechanism design. Furthermore, we will cover the computational techniques called "Linear Programming" and "Integer Programming" which are necessary to solve large combinatorial auction problems. Students will be engaged in theoretical and computational exercises to practice the new economic and computational concepts. In the second half of the course, we will read research papers on various combinatorial auction designs, and each student will present one of the research papers to the class. Finally, students will work on a small combinatorial auction project (likely in groups of 2), combining all of the knowledge learned in the course.

• 3.3.2014: The new assignment "Auction Theory" is now available on NB.
• 21.2.2014: The new assignment "Game Theory" is now available on NB.
• 19.2.2014: The course is now available on OLAT (under the name "Combinatorial Auctions"). Please enroll there if you are taking the course.
• 18.2.2014: Note: the NB server is sometimes down. Thus, please download the PDF files to make sure you can do the reading even if NB is down.
• 18.2.2014: Final version of the Game Theory chapter posted on NB (skip Sections 2.7 and 2.8).
• 17.2.2014: Lectures slides from first lecture posted on NB.
• 16.2.2014: Sign up for NB. link (use your real name!)
• 12.9.2013: Tentative course schedule posted.

Lectures (tentative schedule)

Homework Assignments (tentative schedule)

Note: there will only be homework assignments in the first half of the semester, and each individual assignment will be relatively short. There will be four theoretical assignments to practice the new economic concepts, and two applied assignments to learn how to use AMPL (a mathematical modeling language) and CPLEX (an optimization software package) to solve combinatorial auction problems.

1. For the first half of the course we will use lecture notes (approx. 15-25 pages per lecture) that students must read before class to learn the new material at their own pace. We will use the collaborative PDF annotation tool NB (nb.mit.edu) such that students can ask questions online and receive timely feedback/answers. During class, we will not go over all of the material from the lecture notes. Instead, lectures will be interactive, illustrating the concepts from the lecture notes, and students are expected to participate during class discussions. In addition to the lectures, there will be 6 short homework exercises in the first half of the semester to practice the new theoretical concepts learned.
2. In the second half of the semester, we will read research papers covering combinatorial auctions. All students must present one research paper to the class (likely in pairs) and lead the class discussion.
3. Students must answer 3-4 short comprehension questions before every class to show they have completed the readings. The comprehension questions will be graded on a pass/fail basis. Furthermore, class participation will be graded. If a student misses a lecture but still wants a good participation grade, then he can write a 1/2 page response essay (per lecture missed) which will then be graded instead of the class participation.
4. During the semester, every student must choose a project related to combinatorial auctions to work on (likely in pairs). The project can be theoretical or computational/experimental. Students can propose their own projects, or they can choose a project from a list of topics provided by the teaching staff. A list of possible topics is provided below. In the last class of the semester, the teams will present the results of their project. Shortly after the end of the semester, students must submit a final report (10-15 pages) describing the outcome of their projects.

1. Implement two auction mechanisms and compare them
2. Implement a particular auction mechanism and find manipulation strategies
3. Implement an expressive commerce interface using a reverse combinatorial auction
4. Test the sensitivity of the outcome of a particular auction mechanism
5. Implement a particular auction and test the effect of setting reserve prices

The successful completion of all classes from the assessment level is required. No additional prior knowledge is required. Any background in microeconomics, game theory, or optimization methods would be helpful but is not necessary. Students need to be proficient in math to solve the theoretical homework exercises and to be able to read the combinatorial auction papers. Some prior programming experience (e.g., Java, Python, C#) is necessary to be able to do the final project. This course can be taken before or after taking the lecture "Economics and Computation".

Recommended for all BSc and MSc students with an interest in topics at the intersection of economics and computer science.

1. Obtain a deep understanding of the economic and computational aspects of combinatorial auctions.
2. Be able to read advanced research papers on combinatorial auctions.
3. Be able to implement and solve optimization problems using AMPL and CPLEX.
4. Be able to implement a particular combinatorial auction mechanism using AMPL and CPLEX.
5. Understand the goals and challenges involved in designing combinatorial auction mechanisms.

1. Homework exercises: 20%
2. Presentation: 20%
3. Class participation (or alternatively response essays) + NB comments: 20%
4. Comprehension Questions: 5%
5. Final Project: 35%

The grade for "participation" will be based on the student's participation during the lecture and the student's contributions to NB. If a student misses a lecture but still wants a good participation grade, then the student can also write a 1/2 page response essay (per lecture missed) which will then be graded instead of the class participation. The comprehension questions will be graded on a pass/fail basis (i.e, 1 or 0).

The information provided on this page is "unofficial." For the official information, please see the course description in UZH's course catalog.