Fourth International Workshop on Computational Social Choice
Kraków, Poland, September 11–13, 2012

COMSOC 2012 Program

The COMSOC-2012 program consists of an invited tutorial, four invited talks, and the presentation of 38 contributed papers, which have been selected from amongst 54 submissions received by the program committee.

Additional information:

  • Registration: starting Tuesday 08:30
  • Social Dinner: Wednesday 20:00
  • Welcome: Tuesday 08:50-09:00

Each invited talk is 60 minutes long. Contributed talks have been allocated 20 minutes each, including questions and change-over to the next speaker.


All COMSOC-2012 papers are available through the accepted papers page.

Overview of the Schedule

Detailed Schedule

  • Tuesday, September 11th
    • 8:50--9:00 Welcome to COMSOC 2012

    • 9:00--10:30 Invited Tutorial (Chair: Piotr Faliszewski)
      • Parameterized Complexity Analysis for Social Choice Problems
        Rolf Niedermeier
    • 10:30--10:50 Coffee Break
    • 10:50--11:30 Session 1: Revealed Preferences and Incomplete Information (Chair: Christian Klamler)
      • Goodness of Fit Measures for Revealed Preference Tests: Complexity Results and Algorithms
        Bart Smeulders, Frits Spieksma, Laurens Cherchye, Bram De Rock
      • Possible and Necessary Winners of Partial Tournaments
        Haris Aziz, Markus Brill, Felix Fischer, Paul Harrenstein, Jérôme Lang, Hans Georg Seedig
    • 11:30--12:00 Break
    • 12:00--13:00 Session 2: Multi-Winner Elections (Chair: Lirong Xia)
      • Online (Budgeted) Social Choice
        Brendan Lucier, Joel Oren
      • On the Complexity of Voting Manipulation Under Randomized Tie-Breaking
        Svetlana Obraztsova, Yair Zick, Edith Elkind
      • Bounded Single-Peaked Width and Proportional Representation
        Lucie Galand, Denis Cornaz, Olivier Spanjaard
    • 13:00--14:30 Lunch Break
    • 14:30--15:30 Invited Talk (Chair: Jérôme Lang)
      • Majority Voting over Interconnected Propositions: The Condorcet Set
        Clemens Puppe
    • 15:30--16:00 Coffee Break
    • 16:00--17:00 Session 3: Judgement Aggregation (Chair: Daniel Eckert)
      • The Common Structure of Paradoxes in Aggregation Theory
        Umberto Grandi
      • Models of Manipulation on Aggregation of Binary Evaluations
        Dvir Falik, Elad Dokow
      • Bribery and Control in Judgment Aggregation
        Dorothea Baumeister, Gábor Erdélyi, Olivia J. Erdélyi, Jörg Rothe
    • 17:00--17:30 Break
    • 17:30--18:30 Session 4: New Models of Aggregation (Chair: Clemens Puppe)
      • Graph Aggregation
        Ulle Endriss, Umberto Grandi
      • Aggregating Conditionally Lexicographic Preferences on Multi-Issue Domains
        Jérôme Lang, Jérôme Mengin, Lirong Xia
      • Empathetic Social Choice on Social Networks
        Amirali Salehi-Abari, Craig Boutilier
    • 18:30--19:30 Business Meeting

  • Wednesday, September 12th
    • 9:00--10:00 Invited Talk (Chair: Vincent Merlin)
      • Simple Games and the Probability of Casting a Decisive Vote
        Michel Le Breton
    • 10:00--10:30 Coffee Break
    • 10:30--11:30 Session 5: Manipulation and Distributions (Chair: Mark C. Wilson)
      • Exploiting Polyhedral Symmetries in Social Choice
        Achill Schürmann
      • An Empirical Study of Voting Rules and Manipulation with Large Datasets
        Nicholas Mattei, James Forshee, Judy Goldsmith
      • How Many Vote Operations Are Needed to Manipulate A Voting System?
        Lirong Xia
    • 11:30--12:00 Break
    • 12:00--13:00 Session 6: Domain Restrictions (Chair: Toby Walsh)
      • Analysis and Optimization of Multi-dimensional Percentile Mechanisms
        Xin Sui, Craig Boutilier, Tuomas Sandholm
      • The Complexity of Nearly Single-Peaked Consistency
        Gábor Erdélyi, Martin Lackner, Andreas Pfandler
      • A Characterization of the Single-Crossing Domain
        Robert Bredereck, Jiehua Chen, Gerhard Woeginger
    • 13:00--14:30 Lunch Break
    • 14:30--15:30 Invited Talk (Chair: Jörg Rothe)
      • Computational Methods for the Spatial Model of Social Choice
        Craig A. Tovey
    • 15:30--16:00 Coffee Break
    • 16:00--17:00 Session 7: Cost Sharing and Winner Determination (Chair: Michel Le Breton)
      • Cost-Sharing of Continuous Knapsacks
        Andreas Darmann, Christian Klamler
      • Bounding the Cost of Stability in Games with Restricted Interaction
        Reshef Meir, Yair Zick, Edith Elkind, Jeffrey Rosenschein
      • Robust Winners and Winner Determination Policies under Candidate Uncertainty
        Craig Boutilier, Jérôme Lang, Joel Oren, Hector Palacios
    • 17:00--17:30 Break
    • 17:30--18:30 Session 8: Hardness of Manipulation (Chair: Craig A. Tovey)
      • Manipulating Two Stage Voting Rules
        Nina Narodytska, Toby Walsh
      • Manipulation Under Voting Rule Uncertainty
        Gábor Erdélyi, Edith Elkind
      • The Complexity of Online Manipulation of Sequential Elections
        Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe
    • 20:00 Social Dinner

  • Thursday, September 13th
    • 9:00--10:00 Session 9: Possible Winners (Chair: Jeffrey S. Rosenschein)
      • The Price of Neutrality for the Ranked Pairs Method
        Markus Brill, Felix Fischer
      • The Possible Winner Problem with Uncertain Weights
        Dorothea Baumeister, Magnus Roos, Jörg Rothe, Lena Schend, Lirong Xia
      • Voting with Partial Information: Minimal Sets of Questions to Decide an Outcome
        Ning Ding, Fangzhen Lin
    • 10:00--10:30 Coffee Break
    • 10:30--11:30 Session 10: Resource Allocation (Chair: Ulle Endriss)
      • Computing Socially-Efficient Cake Divisions
        Yonatan Aumann, Yair Dombb, Avinatan Hassidim
      • Complexity and Approximability of Social Welfare Optimization in Multiagent Resource Allocation
        Nhan-Tam Nguyen, Trung Thanh Nguyen, Magnus Roos, Jörg Rothe
      • Elicitation-free Protocols for Allocating Indivisible Goods
        Thomas Kalinowski, Nina Narodytska, Toby Walsh, Lirong Xia
    • 11:30--12:00 Break
    • 12:00--13:00 Session 11: Matching and Coalition Formation (Chair: Maria Silvia Pini)
      • Housing Markets with Indifferences: a Tale of Two Mechanisms
        Haris Aziz, Bart de Keijzer
      • College Admissions with Stable Score-Limits
        Peter Biro, Sofya Kiselgof
      • Group Activity Selection Problem
        Andreas Darmann, Edith Elkind, Sascha Kurz, Jérôme Lang, Joachim Schauer, Gerhard Woeginger
    • 13:00--14:30 Lunch Break
    • 14:30--15:30 Invited Talk (Chair: Peter Biro)
      • Coalitions in Hedonic Games
        Gerhard Woeginger
    • 15:30--16:00 Coffee Break
    • 16:00--17:00 Session 12: Voting Equilibria (Chair: Felix Brandt)
      • Empirical Aspects of Plurality Election Equilibria
        David Thompson, Omer Lev, Kevin Leyton-Brown, Jeffrey Rosenschein
      • Coordination via Polling in Plurality Voting Games under Inertia
        Reyhaneh Reyhani, Mark Wilson, Javad Khazaei
      • Implementation by Agenda Voting
        Sean Horan
    • 17:00--17:30 Break
    • 17:30--18:30 Session 13: Bribery and Control (Chair: Rolf Niedermeier)
      • On Elections with Robust Winners
        Dmitry Shiryaev, Lan Yu, Edith Elkind
      • Resistance to Bribery when Aggregating Soft Constraints
        Alberto Amaran, Maria Silvia Pini, Francesca Rossi, Kristen Brent Venable
      • Being Caught Between a Rock and a Hard Place in an Election–Voter Deterrence by Deletion of Candidates
        Britta Dorn, Dominikus Krüger

Photos by Sylwia Solak (