This course will provide an introduction to the field of computational social choice, which deals with the formal and algorithmic aspects of mechanisms for collective decision making.
Computational social choice is currently a hot topic in AI. There are two very different reasons for this. One is that some of the ideas originating in social choice theory are relevant to application in AI. The most obvious example is the design of multiagent systems, where autonomous software agents have to make collective decisions, but computational social choice is also relevant to, e.g., recommender systems, search engines, and crowdsourcing. The second reason is that many of the methods and techniques developed in AI have turned out to be particularly useful to gaining a deeper understanding of collective decision making, with examples including algorithms and complexity, automated reasoning, and knowledge representation.
Each of the three sessions of the course will be devoted to a specific topic in computational social choice: (1) the fair allocation of resources, (2) voting theory, and (3) judgment aggregation. No specific technical background will be expected from the audience.
Session 1: Fair Allocation of Resources. In fair allocation problems, we have to distribute a number of resources to a number of agents, who each have a utility function defined over the set of resources they might receive, and we try to identify an allocation that satisfies suitable fairness requirements.
Session 2: Voting Theory. In voting theory, each agent is equipped with a linear order over a set of alternatives, representing her preferences, and we try to elect one of these alternatives in a way that appropriately respects the will of the group as a whole.
Session 3: Judgment Aggregation. In judgment aggregation, each agent expresses her beliefs by indicating for each of a number of formaulas of propositional logic which ones of these formulas she judges to be true, and we have to come to a collective position regarding the truth of all these formulas.
For additional material, please refer to my course on computational social choice, taught annually at the ILLC.