IMS workshops on Algorithmic Game Theory and Computational Social Choice


Mini-workshop on Mechanism Design: 10 - 11 Jan 2013.
Winter School and Workshop on Algorithmic Game Theory: 14 - 18 Jan 2013.
Winter School and Workshop on Computational Social Choice: 21 - 25 Jan 2013.

This is a brief and personalised report on the Algorithmic Game Theory and Computational Social Choice workshops held from 14-25 January 2013 in Singapore. The workshops were focussed on the general interface between economics and computation. A wide variety of topics were covered. The talks initially focussed on mechanism design and auctions and then slowly turned towards game theory and finally social choice and fair division.

When I arrived in Singapore on the 13th of January, the mini-workshop on mechanism design had already finished. The workshop's highlight was an extensive tutorial by Jason Hartline. Singapore provided a great backdrop to the workshops. Algorithmic game theory and computational social choice has received a great boost in Singapore with the establishment of the research group by Edith Elkind and Ning Chen. I was also looking forward to my stay since Singapore has so many cultural aspects to explore and savour including the tasty fusion of Malay, Chinese and Indian food.

The algorithmic game theory workshop was held at the campus of Nanyang Technological University (NTU).
The workshop featured a number of talks on auctions and mechanism design by Stefano Leonardi, Amos Fiat, Mansour, Singer, Pai and co. Gianluigi Greco presented a tutorial on how structural decomposition methods are helpful in getting positive algorithmic results in equilibrium computation and winner determination. Martin Hoefer gave an entertaining talk on dynamics in matching markets. Since I had not heard Martin before, it was nice to get an overview of some of his interesting recent work. Jean-Francois Laslier gave a masterly whiteboard tutorial on tournament solutions. He focussed on some of the prominent results in the area such as uniqueness of minimal covering set and bipartisan set. Lirong took time out of his other speaking commitments to discuss  maximum likelihood approaches to social choice.

The afternoon session on the Thursday proved to be the most enjoyable with impressive talks by Xiaohui Bei, Xiaotie Deng, and Nicole Immorlica on resource allocation, incentives in games, and Schelling's segregation model. The final day of the game theory workshop featured tutorials from Kevin Leyton-Brown and Nicole Immorlica on modeling game-theoretic problems and matching markets respectively. Kevin was very convincing about the merit of modelling complex situations via action-graph games.

The weekend between the game theory and social choice workshops provided extra time for us to explore the sights, sounds, and especially the tastes of the city. China town looked especially festive because of the countdown to the Chinese New Year.

The computational social choice workshop was held at NUS (National University Singapore). The workshop started slowly with the first one and a half days focussing on tutorials on judgement aggregation and simple games by Ulle Endriss and Arkardi Slinko. One of the most interesting talks was by Biaoshuai Tao on ``Optimal proportional cake cutting with connected pieces''. Piotr Faliszewski's tutorial on multiwinner elections provided us with a window into the rich domain of algorithmic issues in multiwinner elections especially when the chosen winners need to maximize representation of the voters. Andrei Gomberg---one of the few economists at the worksop--- contributed greatly to the workshop with his tutorial and talk on revealed preferences and his numerous inputs to the discussions.  Yair Zick and Edith Elkind described some of their recent work on the Shapley value in weighted voting games. The workshop concluded with a tutorial by Jerome Lang on graphical languages for preference representation.

Nicta had a decent representation at the workshops. Nick Mattei presented on the ``Empirical analysis of voting rules and large datasets''. Toby Walsh gave a tutorial on the ``complexity of manipulating voting rules'' and a talk on sequential allocation of indivisible goods. I talked about `` the tradeoff between economic efficiency and strategyproofness in randomized social choice''. The talk was based on joint work with Markus Brill and Felix Brandt.

The workshops were organized by Ning Chen and
Edith Elkind both from Nanyang Technological University. It is hoped that we will see further editions of such meetings.

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

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

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