Program

Jump directly to Monday, Tuesday, Wednesday, Thursday.

The COMSOC-2010 program consists of five invited talks and the presentation of 39 contributed papers, which have been selected from amongst the 57 submissions received by the program committee. In addition, there are four tutorials and three short talks in a special LogICCC session at the LogICCC Tutorial Day.

Registration: starting Monday 08:30
Social Dinner: Wednesday 20:00 (details)
Welcome: Monday 09:00-09:15

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

Monday, 13 September 2010

LogICCC Tutorial Day

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

9:15-10:30  Introductory Tutorial   (Chair: Jörg Rothe) A Brief Introductory Tutorial on Computational Social Choice Vincent Conitzer

10:30-11:00  Coffee Break

11:00-12:15  Invited Tutorial   (Chair: Gabrielle Demange) Different Approaches to Influence in Social Networks Agnieszka Rusinowska

12:15-13:45  Lunch

13:45-15:00  Invited Tutorial   (Chair: Hannu Nurmi) Some Research Problems in Computational Social Choice Nicolaus Tideman

15:00-15:15  Coffee Break

15:15-16:30  Invited Tutorial   (Chair: Mike Fellows) Where are the Hard Manipulation Problems? Toby Walsh

16:30-16:45  Coffee Break

16:45-17:45  LogICCC session  (Chair: Arkadii Slinko) Problem Solving on Simple Games via BDDs Rudolf Berghammer and Stefan Bolus Consensus Measures Generated by Weighted Kemeny Distances on Linear Orders José Luis García-Lapresta and David Pérez-Román Strategy and Manipulation in Medieval Elections Sara L. Uckelman and Joel Uckelman

Tuesday, 14 September 2010

9:00-10:00  Invited Talk   (Chair: Jörg Rothe) Collective Attention and Ranking Methods Gabrielle Demange

10:00-10:10  Short Break

10:10-11:10  Winner Determination in Voting and Tournament Solutions  (Chair: Toby Walsh) Partial Kernelization for Rank Aggregation: Theory and Experiments Nadja Betzler, Robert Bredereck, and Rolf Niedermeier On the Fixed-Parameter Tractability of Composition-Consistent Tournament Solutions Felix Brandt, Markus Brill, and Hans Georg Seedig Budgeted Social Choice: A Framework for Multiple Recommendations in Consensus Decision Making Tyler Lu and Craig Boutilier

11:10-11:35  Coffee Break

11:35-12:35  Computing Strategic Manipulations  (Chair: Jérôme Lang) An Algorithm for the Coalitional Manipulation Problem under Maximin Michael Zuckerman, Omer Lev, and Jeffrey S. Rosenschein Complexity of Safe Strategic Voting Noam Hazon and Edith Elkind An Empirical Study of Borda Manipulation Jessica Davies, George Katsirelos, Nina Narodytska, and Toby Walsh

12:35-14:05  Lunch

14:05-15:05  Invited Talk   (Chair: Vincent Conitzer) Collective Time Preferences Matthew O. Jackson

15:05-15:15  Short Break

15:15-16:35  Multiagent Resource Allocation, Fairness, and Judgment Aggregation  (Chair: Matthew O. Jackson) Fair Division under Ordinal Preferences: Computing Envy-Free Allocations of Indivisible Goods Sylvain Bouveret, Ulle Endriss, and Jérôme Lang A Maximin Approach to Finding Fair Spanning Trees Andreas Darmann, Christian Klamler, and Ulrich Pferschy Approximate Judgement Aggregation Ilan Nehama Complexity of Winner Determination and Strategic Manipulation in Judgment Aggregation Ulle Endriss, Umberto Grandi, and Daniele Porello

16:35-17:00  Coffee Break

17:00-18:00  Bribery, Control, and Cloning in Elections  (Chair: Fran Rosamond) Multivariate Complexity Analysis of Swap Bribery Britta Dorn and Ildikó Schlotter Parameterized Control Complexity in Bucklin Voting and in Fallback Voting Gábor Erdélyi and Michael Fellows Cloning in Elections Edith Elkind, Piotr Faliszewski, and Arkadii Slinko

Wednesday, 15 September 2010

9:00-10:00  Invited Talk   (Chair: Hervé Moulin) Allocation via Deferred-Acceptance under Responsive Priorities Bettina Klaus

10:00-10:10  Short Break

10:10-11:10  Possible Winners and Single-Peaked Electorates  (Chair: Piotr Faliszewski) On Problem Kernels for Possible Winner Determination Under the k-Approval Protocol Nadja Betzler Possible Winners When New Alternatives Join: New Results Coming Up! Lirong Xia, Jérôme Lang, and Jérôme Monnot Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates Felix Brandt, Markus Brill, Edith Hemaspaandra, and Lane A. Hemaspaandra

11:10-11:35  Coffee Break

11:35-12:35  Cake-cutting Algorithms  (Chair: Ulle Endriss) The Efficiency of Fair Division with Connected Pieces Yonatan Aumann and Yair Dombb Truth, Justice, and Cake Cutting Yiling Chen, John K. Lai, David C. Parkes, and Ariel D. Procaccia Online Cake Cutting Toby Walsh

12:35-14:05  Lunch

14:05-15:05  Invited Talk   (Chair: Ariel Procaccia) Impartial Peer Evaluation Hervé Moulin

15:05-15:15  Short Break

15:15-16:35  Coalition Formation and Cooperative Game Theory  (Chair: Edith Elkind) Three Hierarchies of Simple Games Parameterized by "Resource" Parameters Tatyana Gvozdeva, Lane A. Hemaspaandra, and Arkadii Slinko Optimal Partitions in Additively Separable Hedonic Games Haris Aziz, Felix Brandt, and Hans Georg Seedig Fractional Solutions for NTU-Games Péter Biró and Tamás Fleiner Dependence in Games and Dependence Games Davide Grossi and Paolo Turrini

16:35-17:00  Coffee Break

17:00-18:00  Mechanism Design with Payments  (Chair: Remzi Sanver) Optimization in Payments in Dominant Strategy Mechanisms for Single-Parameter Domains Victor Naroditskiy, Maria Polukarov, and Nicholas R. Jennings Strong Implementation of Social Choice Functions in Dominant Strategies Sven O. Krumke and Clemens Thielen A Combinatorial Algorithm for Strong Implementation of Social Choice Functions Clemens Thielen and Stephan Westphal

18:00-19:00  Business Meeting

20:00-  Conference Dinner at the Rheinturm

Thursday, 16 September 2010

9:00-10:00  Invited Talk   (Chair: Felix Brandt) Nice, but Are They Relevant? A Political Scientist Looks at Social Choice Results Hannu Nurmi

10:00-10:10  Short Break

10:10-11:10  Matchings and Social Choice  (Chair: Bettina Klaus) Algorithms for Pareto Stable Assignment Ning Chen and Arpita Ghosh Stable Marriage Problems with Quantitative Preferences Maria Silvia Pini, Francesca Rossi, Kristen Brent Venable, and Toby Walsh Local Search for Stable Marriage Problems Mirco Gelain, Maria Silvia Pini, Francesca Rossi, Kristen Brent Venable, and Toby Walsh

11:10-11:35  Coffee Break

11:35-12:35  Social Choice  (Chair: Jean-François Laslier) Distance Rationalization of Voting Rules Edith Elkind, Piotr Faliszewski, and Arkadii Slinko Social Choice without the Pareto Principle under Weak Independence Ceyhun Coban and M. Remzi Sanver An Optimal Single-Winner Preferential Voting System Based on Game Theory Ronald L. Rivest and Emily Shen

12:35-14:05  Lunch

14:05-14:45  Strategic Voting  (Chair: Arkadii Slinko) Convergence to Equilibria in Plurality Voting Reshef Meir, Maria Polukarov, Jeffrey S. Rosenschein, and Nicholas R. Jennings The Probability of Safe Manipulation Mark C. Wilson and Reyhaneh Reyhani

14:45-14:55  Short Break

14:55-15:35  Approximation of Voting Rules  (Chair: Brent Venable) Socially Desirable Approximations for Dodgson's Voting Rule Ioannis Caragiannis, Christos Kaklamanis, Nikos Karanikolas, and Ariel D. Procaccia Approximation Algorithms and Mechanism Design for Minimax Approval Voting Ioannis Caragiannis, Dimitris Kalaitzis, and Evangelos Markakis

15:35-16:00  Coffee Break

16:00-17:00  Mechanism Design in Social Choice   (Chair: Francesca Rossi) Group-Strategyproof Irresolute Social Choice Functions Felix Brandt Sum of Us: Strategyproof Selection from the Selectors Noga Alon, Felix Fischer, Ariel D. Procaccia, and Moshe Tennenholtz Complexity Consideration on the Existence of Strategy-Proof Social Choice Functions Koji Takamiya

17:00-17:30  Farewell Coffee