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.

Papers

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 (www.sylwiasolak.pl).