COST-ADT Doctoral School on Computational Social Choice


The COST Action IC0602 ``ADT (Algorithmic Decision Theory)’’ is a collaborative project to build European-wide capability in algorithmic decision theory. A COST-ADT Doctoral School on Computational Social Choice was held in Estoril, Portugal from 9 to14 April 2010. There were more than 50 participants spanning more than twenty countries and the following research areas: computational social choice theory, multiple criteria decision analysis, decision under risk and uncertainty, algorithmic decision theory and welfare economics. The main local organizer of the school was José Rui Figueira. The school was based on a series of tutorials: 
  • Christian Klamer (Institute of Public Economics at Graz University) lectured on the mathematical aspects of voting theory. In the first lecture he outlined the commonly used voting rules. In the second lecture, he was successful in his ambitious goal of explaining the proofs of three classic impossibility results in social choice theory: Arrow’s impossibility theorem Gibbard Sattherwaite theorem and Sen’s Liberal Paradox. His third lecture was based on Saari’s Geometry of voting.   
  • Ulle Endriss (ILLC, University of Amsterdam) presented well organized lectures on fair division aspects of social choice theory. In his first lecture, he introduced social welfare theory. The second and third lectures were on fair division of divisible objects (cake cutting) and indivisible objects respectively. 
  • Jerôme Lang (CNRS-LAMSADE, Paris) presented interactive lectures on computational and communication complexity aspects of social choice theory including complexity of computing winners, agenda control and voting insincerely. 

The tutorial lecturers not only introduced the material but discussed recent results and future research directions. Apart from the three main tutorials, invited senior researchers also gave single lectures. José Rui Figueira presented the history of social choice theory and its contributors. Felix Brandt surveyed important axiomatic result in social choice theory and discussed three possible escape routes from Arrow’s impossibility theorem. Stefano Moretti presented the application of simple coalitional games and Shapley value to bioinformatics.  Sébastien Konieczny and Thierry Marchant presented lectures on `Information Fusion and Social Choice’ and `From Social Choice to Multi-criteria Decision Analysis’ respectively.

During the event, participants also presented contributed talks. The highlights of the student talks were the following: Markus Brill’s presentation on the Tournament Equilibrium Set; Britta Dorn’s outline of  the complexity aspect of scoring rules with incomplete preferences; Christian Geist’s impressive results on using SAT solvers and induction arguments to generate new and old impossibility results; and Paul Dütting’s talk on the state of the art of combinatorial auctions.

The school was organized in a relaxed manner with plenty of opportunities for participants to mingle and socialize. This included an enjoyable concert by a local band and an excurison. Apart from the COST Action and its relevant committees which were the driving force behind the school, the following sponsors of the school should also be acknowledged: CEG-IST, NANO-Risk Project, IST (TagusPark) and BPI (Banco Português de Investimentos). The talks and lectures are planned to be uploaded on the following website: http://cost-ic0602.org/.

Comments

Post a Comment

Popular posts from this blog

Smart Lotteries in School Choice Ex-ante Pareto-Improvement with Ex-post Stability

Image
Working Paper: https://cgi.cse.unsw.edu.au/~haziz/PIRMES.pdf  Abstract: In a typical school choice application, the students have strict preferences over the schools while the schools have coarse priorities over the students based on their distance and their enrolled siblings. The outcome of a centralized admission mechanism is then usually obtained by the Deferred Acceptance (DA) algorithm with random tie-breaking. Therefore, every possible outcome of this mechanism is a stable solution for the coarse priorities that will arise with certain probability. This implies a probabilistic assignment, where the admission probability for each student-school pair is specified. In this paper, we propose a new efficiency-improving stable `smart lottery' mechanism. We aim to improve the probabilistic assignment ex-ante in a stochastic dominance sense, while ensuring that the improved random matching is still ex-post stable, meaning that it can be decomposed into stable matchings regarding the ...
Read more

Fair budgets from ranked ballots: PB-EAR

How do you split a shared budget fairly when people rank projects that cost very different amounts? PB-EAR, from our AAAI 2021 paper  Proportionally Representative Participatory Budgeting with Ordinal Preferences  ( AAAI version ), gives every voter an equal slice of the budget and lets groups pool their slices to fund the projects they rank highest, looking further down the ballots only when nothing is yet affordable. Every cohesive group is guaranteed its proportional share, and the rule extends our  Expanding Approvals Rule  for elections to budgets with project costs, ties and unequal voter weights.  That makes it a natural fit for DAO grant rounds such as   TheDAO Security Fund 's ETHSecurity Initiatives, where badge holders will rank the security initiatives listed on   the app  to allocate the fund's budget. The two-minute video below walks through a worked example. Here's an educational tool someone built to show how PB-EAR works. 
Read more

Proportionally Representative Clustering

Image
H. Aziz, B. Lee, S. Morota Chu, and J. Vollen. Proportionally Representative Clustering.  WINE 2024 .  [  Pdf  ]  In recent years, there has been a surge in effort to formalize notions of fairness in machine learning. We focus on centroid clustering— one of the fundamental tasks in unsupervised machine learning. We pro- pose a new axiom “proportionally representative fairness” (PRF) that is designed for clustering problems where the selection of centroids re- flects the distribution of data points and how tightly they are clustered together. Our fairness concept is not satisfied by existing fair cluster- ing algorithms. We design efficient algorithms to achieve PRF both for unconstrained and discrete clustering problems. Our algorithm for the unconstrained setting is also the first known polynomial-time approxi- mation algorithm for the well-studied Proportional Fairness (PF) axiom [ 13 ]. Our algorithm for the discrete setting also matches the best kn...
Read more