2nd International Workshop on Computational Social Choice
Liverpool, 3-5 September 2008

COMSOC-2008 Program

  • This program starts with the tutorials on Sept 2nd.
  • The business meeting and conference dinner will be at The Athenaeum, Liverpool, on the Thursday evening (i.e. Sept 4th). We will have a (fairly short) business meeting combined with a reception, in the "News room" of the Athenaeum (6:30 to 8:00), then the conference dinner will begin at 8:00, in the Dining Room. The News Room (which has tables, chairs, cash bar and coffee) will be available for informal discussions afterwards, until about midnight.
  • Click on the title to show the abstract for that talk; clicking again toggles it off.
  • For printing this web page, you can use the following buttons to select talk abstracts to display:

Tuesday 2nd September 2008

9:00-10:00 MBC talk (invited talk by Sarit Kraus)

10:00-10:30 Coffee

10:30-11:15 Tutorial:

Overview of the COMSOC Research Area

11:30-13:00 Tutorial:

Computational Complexity for Social Choice Theorists

13:00-14:30 Lunch

14:30-16:00 Tutorial:

Judgment Aggregation for Logicians and Computer Scientists

16:00-16:30 Coffee

16:30-17:30 MBC talk (invited talk by Amy Greenwald)

Wednesday 3rd September 2008

8:55-9:00 Opening remarks (Paul Goldberg)

9:00-10:00 Invited Talk

(session chair: Paul Goldberg)
Ranking, Trust, and Recommendation Systems: An Axiomatic Approach

10:00-10:40 Social Choice and Graphs

On the Complexity of Rationalizing Behavior
Computing Spanning Trees in a Social Choice Context

10:40-11:10 Coffee

11:10-12:30 Ranking

(session chair: Peter McBurney)
Approval-rating systems that never reward insincerity
Aggregating Referee Scores: an Algebraic Approach
Computing Kemeny Rankings, Parameterized by the Average KT-Distance
Preference Functions That Score Rankings and Maximum Likelihood Estimation
Vincent Conitzer, Matthew Rognlie and Lirong Xia

12:30-14:00 Lunch break

14:00-15:00 Invited Talk:

(session chair: Jérôme Lang)
Lorenz rankings of rules for the adjudication of conflicting claims

15:00-15:40 Belief merging

Equilibria in Social Belief Removal
Richard Booth and Thomas Meyer
Confluence Operators: Negotiation as Pointwise Merging
Sébastien Konieczny and Ramón Pino Pérez

15:40-16:10 Coffee

16:10-17:30 Computational obstacles to election manipulation

(session chair: Edith Elkind)
Llull and Copeland Voting Computationally Resist Bribery and Control
Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra and Jörg Rothe
Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control
Gábor Erdélyi, Markus Nowak and Jörg Rothe
Approximability of Manipulating Elections
Eric Brelsford, Piotr Faliszewski, Edith Hemaspaandra, Henning Schnoor and Ilka Schnoor
Complexity of Unweighted Coalitional Manipulation Under Some Common Voting Rules

Thursday 4th September 2008

9:00-10:00 Invited Talk:

(session chair: Vincent Conitzer)
Expressiveness in mechanisms and its relation to efficiency: Our experience from $40 billion of combinatorial multi-attribute auctions and recent theory

10:00-10:40 Mechanism design

A Qualitative Vickrey Auction
The Cost and Windfall of Manipulability

10:40-11:10 Coffee

11:10-12:30 Tournaments

(session chair: Sébastien Konieczny)
On the Agenda Control Problem for Knockout Tournaments
Thuc Vu, Alon Altman and Yoav Shoham
How to Rig Elections and Competitions
On Voting Caterpillars: Approximating Maximum Degree in a Tournament by Binary Trees
A Computational Analysis of the Tournament Equilibrium Set
Felix Brandt, Felix Fischer, Paul Harrenstein and Maximilian Mair.

12:30-14:00 Lunch break

14:00-15:00 Invited Talk

(session chair: Christian List)
Individual and group strategy proofness of voting rules. The case for restricted domains.

15:00-15:40 Manipulability

Non-dictatorial Social Choice Rules are Safely Manipulable
Arkadii Slinko and Shaun White
Computing the Degree of Manipulability in the Case of Multiple Choice
Fuad Aleskerov, Daniel Karabekyan, Remzi Sanver and Vyacheslav Yakuba

15:40-16:10 Coffee

16:10-17:30 Judgment aggregation

(session chair: Ulle Endriss)
Majority voting on restricted domains: a summary
A geometric approach to judgment aggregation
Christian Klamler and Daniel Eckert
From Preferences to Judgments and Back
Davide Grossi
Judgment Aggregation as Maximization of Epistemic and Social Utility
Szymon Klarman

Friday 5th September 2008

9:00-10:00 Invited Talk:

(session chair: Mike Wooldridge)
Talk, Cheap Talk, and States of Knowledge

10:00-10:40 Logic and argumentation

A Deontic Logic for Socially Optimal Norms
Welfare properties of argumentation-based semantics
Kate Larson and Iyad Rahwan

10:40-11:10 Coffee

11:10-12:30 Computing social choice functions

(session chair: Ariel Procaccia)
Dodgson's Rule: Approximations and Absurdity
Informational requirements of social choice rules
Shin Sato
Compiling the votes of a subelectorate
Yann Chevaleyre, Jérôme Lang, Nicolas Maudet and Guillaume Ravilly-Abadie
Alternatives to Truthfulness are Hard to Recognize

12:30-14:00 Lunch break

14:00-15:20 Coalitional voting games

(session chair: Arkadii Slinko)
Complexity of comparison of influence of players in simple games
Coalition Structures in Weighted Voting Games
Georgios Chalkiadakis, Edith Elkind and Nick Jennings
Divide and Conquer: False-Name Manipulations in Weighted Voting Games
Yoram Bachrach and Edith Elkind.
Computing the Nucleolus of Weighted Voting Games
Edith Elkind and Dmitrii Pasechnik.

15:20-15:50 Coffee

15:50-16:30 Coalition formation

(session chair: Wiebe Van der Hoek)
A fair payoff distribution for myopic rational agents
Stéphane Airiau and Sandip Sen
Three-sided stable matchings with cyclic preferences and the kidney exchange problem