Algorithmic Economics 1000-2M23ALE
The lecture deals with issues at the intersection of computer science, artificial intelligence and economics.
We consider systems with multiple independent participants who potentially have different goals. They may cooperate, but there may
also be conflicts of interest between them. We will discuss methods of analyzing such systems and of designing algorithms for them. These
algorithms, in addition to having low computational complexity, must satisfy other desiderata, such as fairness (to the participants of the
system), stability (participants do not want to leave the system) or strategy-proofness (participants do not have incentives to play against
the system).
Examples of specific models and issues discussed in the lecture include:
1. Social network analysis (centrality measures, PageRank).
2. Algorithms for barter markets (based on the example of the kidney exchange in the United States).
3. Mechanisms for conducting auctions (used in Internet marketing, among other things).
4. Algorithms for finding fair allocation of goods, algorithms for finding stable matchings and algorithms for fair election.
5. Algorithms for finding equilibria based on concepts from game theory (and their applications in security systems).
6. Solution concepts from coalition game theory (used, among others, in the SHAP library explaining the outputs of ML
We will discuss key issues from game theory (cooperative and non- cooperative), social choice theory, mechanism design and social network analysis. The lecture will focus on algorithms and solutions that are practically relevant.
Course coordinators
Learning outcomes
Knowledge:
1. Has fundamental knowledge in the key areas of research at the interface of artificial intelligence and economics: game theory, mechanism design, social choice, social networks.
Competences:
1. Knows limitations of his/her knowledge, is willing to constantly upgrade and update his/her knowledge and raise qualifications within the field of computer science and related scientific areas and disciplines (K_K01)
2. Knows how to precisely formulate questions in order to deepen own understanding of the studied subject (in particular in contacts with non-computer scientists) or to find gaps in own reasoning about the subject (K_K02)
3. Is able to formulate opinions about fundamental topics in computer sciences (K_K06).
4. Understands the need of systematically updating one's own knowledge by reading scientific and popular scientific journals (K_K08).
Assessment criteria
The course will be divided into three independent modules. The first module will consist of 5 lectures, and the other two will consist of 4 lectures each. There will be an exam after each module.
To pass the course, students must pass all three modules. The grades for Modules 2 and 3 will depend solely on the exam results. In Module 1, there will also be a homework assignment, and the grade will be based 50% on the homework and 50% on the exam result. The final course grade will be the median of the grades from all three modules.
In the retake exam session, students will be allowed to retake exams from selected modules only, while the grades from the remaining modules will be carried over from the first session. The grade for the retake exam in Module 1 will not include the homework component. The final grade in the retake session will also be the median of the module grades.
Bibliography
Algorithmic game theory, N. Nisan, T. Roughgarden, É. Tardos, V. Vazirani
Handbook of computational social choice, Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, Ariel D. Procaccia
Multiagent systems: algorithmic, game-theoretic, and Logical Foundations, Yoav Shoham, Kevin Leyton-Brown
Network Analysis: Methodological Foundations, Urlik Brandes, Thomas Erlebach
Additional information
Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes:
- Bachelor's degree, first cycle programme, Computer Science
- Master's degree, second cycle programme, Computer Science
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: