Programme

Jump directly to Wednesday, Thursday, Friday. The programme is also available as a PDF file.

The COMSOC-2006 programme consists of five invited talks and the presentation of 38 contributed papers, which have been selected from amongst the 48 submissions received by the programme committee. The slides of most talks are now available. We also have some photos of the workshop.

Registration: from Wednesday 08:15		Social Dinner: Thursday 20:00 (details)
Welcome: Wednesday 08:50-09:00		Farewell Drinks: Friday 17:15-18:30

Each invited talk is 50 minutes long and followed by a 10 minute break. Contributed talks have been allocated 20 minutes each, including questions and change-over to the next speaker. Here is a rough schedule of the programme (see the full programme for the exact time slots):

Wednesday morning	Thursday morning	Friday morning
Francesca Rossi (invited)	Noam Nisan (invited)	Boi Faltings (invited)
Hard Problems in Computing Voting Rules 1	Mechanism Design and Related Issues	Hard Problems in Computing Voting Rules 2
Coffee Break	Coffee Break	Coffee Break
Computational Barriers to Manipulation and Control	Ranking Systems / Designing Voting Rules	Resource Allocation and Fair Division 2
Lunch	Lunch	Lunch
Wednesday afternoon	Thursday afternoon	Friday afternoon
Harrie de Swart (invited)	Steven Brams (invited)	Fair Representation / Preference Elicitation
Logics for Social Choice	Resource Allocation and Fair Division 1	Coffee Break
Coffee Break	Coffee Break	Coalition Formation / Experimental Computations
Strategy-Proofness	Judgment Aggregation and Related Issues

Wednesday, 6 December 2006

8:50-9:00:  Welcome   (Registration: from 8:15 onwards)

9:00-9:50:  Invited Talk   (Chair: Krzysztof Apt)

Incomparability and Uncertainty in Preference Aggregation Francesca Rossi

10:00-10:40:  Hard Problems in Computing Voting Rules 1   (Chair: Jörg Rothe)

The Computational Complexity of Choice Sets Felix Brandt, Felix Fischer and Paul Harrenstein Approval Voting: Local Search Heuristics and Approximation Algorithms for the Minimax Solution Rob LeGrand, Evangelos Markakis and Aranyak Mehta

10:40-11:10:  Coffee Break

11:10-12:30:  Computational Barriers to Manipulation and Control   (Chair: Michael Trick)

Hybrid Elections Broaden Complexity-Theoretic Resistance to Control Edith Hemaspaandra, Lane Hemaspaandra and Jörg Rothe Hybrid Voting Protocols and Hardness of Manipulation Edith Elkind and Helger Lipmaa The Complexity of Bribery in Elections Piotr Faliszewski, Edith Hemaspaandra and Lane Hemaspaandra On Complexity of Lobbying in Multiple Referenda Robin Christian, Mike Fellows, Frances Rosamond and Arkadii Slinko

12:30-14:00:  Lunch

14:00-14:50:  Invited Talk   (Chair: Hans Peters)

Social Software for Coalition Formation Harrie de Swart

15:00-15:40:  Logics for Social Choice   (Chair: Johan van Benthem)

Towards a Logic of Social Welfare Thomas Ågotnes, Wiebe van der Hoek and Michael Wooldridge Social Choice and the Logic of Simple Games Tijmen Daniëls

15:40-16:10:  Coffee Break

16:10-17:30:  Strategy-Proofness   (Chair: Christian List)

On the Robustness of Preference Aggregation in Noisy Environments Ariel Procaccia, Jeffrey Rosenschein and Gal Kaminka Anonymous Voting and Minimal Manipulability Stefan Maus, Hans Peters and Ton Storcken Domains of Social Choice Functions on which Coalition Strategy-Proofness and Maskin Monotonicity are Equivalent Koji Takamiya Simulating the Effects of Misperception on the Manipulability of Voting Johann Mitlöhner, Daniel Eckert and Christian Klamler

Thursday, 7 December 2006

9:00-9:50:  Invited Talk   (Chair: Vincent Conitzer)

Approximation Mechanisms and Characterization of Implementable Social Choice Rules Noam Nisan

10:00-11:00:  Mechanism Design and Related Issues   (Chair: Noam Nisan)

Optimizing Streaming Applications with Self-Interested Users using M-DPOP Boi Faltings, David Parkes, Adrian Petcu and Jeff Shneidman Weak Monotonicity and Bayes-Nash Incentive Compatibility Rudolf Müller, Andrés Perea and Sascha Wolf Decentralization and Mechanism Design for Online Machine Scheduling Birgit Heydenreich, Rudolf Müller and Marc Uetz

11:00-11:30:  Coffee Break

11:30-12:30: Ranking Systems / Designing Voting Rules   (Chair: Vangelis Markakis)

QuickRank: A Recursive Ranking Algorithm Amy Greenwald and John Wicks Automated Design of Voting Rules by Learning from Examples Ariel Procaccia, Aviv Zohar and Jeffrey Rosenschein Small Binary Voting Trees Michael Trick

12:30-14:00:  Lunch

14:00-14:50:  Invited Talk   (Chair: Eric Pacuit)

Better Ways to Cut a Cake Steven Brams

15:00-15:40:  Resource Allocation and Fair Division 1   (Chair: Ulle Endriss)

Some Results on Adjusted Winner Eric Pacuit, Rohit Parikh and Samer Salame How to Allocate Hard Candies Fairly Marco Dall'Aglio and Raffaele Mosca

15:40-16:10:  Coffee Break

16:10-17:30:  Judgment Aggregation and Related Issues   (Chair: Harrie de Swart)

Judgment Aggregation without Full Rationality Franz Dietrich and Christian List Merging Judgments and the Problem of Truth-Tracking Gabriella Pigozzi and Stephan Hartmann The Discursive Dilemma as a Lottery Paradox Igor Douven and Jan-Willem Romeijn Natural Rules for Optimal Debates: Preliminaries for a Combinatorial Exploration Yann Chevaleyre and Nicolas Maudet

20:00-late:  Social Dinner   (details)

Friday, 8 December 2006

9:00-9:50:  Invited Talk   (Chair: Yann Chevaleyre)

Budget-Balance in Social Choice Boi Faltings

10:00-11:00:  Hard Problems in Computing Voting Rules 2   (Chair: Edith Hemaspaandra)

Approximability of Dodgson's Rule John Christopher McCabe-Dansted, Geoffrey Pritchard and Arkadii Slinko Guarantees for the Success Frequency of an Algorithm for Finding Dodgson Winners Christopher Homan and Lane A. Hemaspaandra On Determining Dodgson Winners by Frequently Self-Knowingly Correct Algorithms and in Average-Case Polynomial Time Jörg Rothe and Holger Spakowski

11:00-11:30:  Coffee Break

11:30-12:30:  Resource Allocation and Fair Division 2   (Chair: Nicolas Maudet)

Bicriteria Models for Fair Resource Allocation Wlodzimierz Ogryczak Finding Leximin-Optimal Solutions using Constraint Programming Sylvain Bouveret and Michel Lemaître The Distributed Negotiation of Egalitarian Allocations Paul-Amaury Matt, Francesca Toni and Dionysis Dionysiou

12:30-14:00:  Lunch

14:00-15:20:  Fair Representation / Preference Elicitation   (Chair: Jérôme Lang)

Welfarism and the Assessments of Social Decision Rules Claus Beisbart and Stephan Hartmann Equal Representation in Two-tier Voting Systems Nicola Maaser and Stefan Napel Eliciting Single-Peaked Preferences using Comparison Queries Vincent Conitzer Retrieving the Structure of Utility Graphs used in Multi-Item Negotiation through Collaborative Filtering Valentin Robu and Han La Poutré

15:20-15:50:  Coffee Break

15:50-17:10:  Coalition Formation / Experimental Computations   (Chair: Jan-Willem Romeijn)

A Generic Approach to Coalition Formation Krzysztof Apt and Andreas Witzel The Probability of Sen's Liberal Paradox Keith Dougherty and Julian Edward Voting Cycles in a Computational Electoral Competition Model with Endogenous Interest Groups Vjollca Sadiraj, Jan Tuinstra and Frans van Winden Voting Systems and Automated Reasoning: The QBFEVAL Case Study Massimo Narizzano, Luca Pulina and Armando Tacchella

17:15-18:30:  Farewell Drinks   (3rd floor lobby)