Seventh International Workshop on Computational Social Choice (COMSOC-2018)

Troy, NY, USA, 25-27 June 2018

About COMSOC-2018

Computational social choice is a rapidly growing discipline at the interface of social choice theory and computer science. It is concerned with the application of computational techniques to the study of social choice mechanisms, and with the integration of social choice paradigms into computing (Read more).

The Seventh International Workshop on Computational Social Choice (COMSOC-2018) will take place on June 25–27, 2018, in Troy, NY, USA. It will be hosted by Rensselaer Polytechnic Institute (RPI). The aim of the workshop is to bring together different communities: computer scientists interested in computational issues in social choice; people working in artificial intelligence and multiagent systems who are using ideas from social choice to organize societies of artificial software agents; logicians interested in the logic-based specification and analysis of social procedures; computer science theorists analyzing algorithmic properties of social phenomena; and last but not least people coming from social choice theory itself: economists, mathematicians, and political scientists.

News

  • Registration is open, see here. Early registration until June 1.

  • Accepted papers are updated, camera ready due: April 30, 2018

  • Poster submission deadline April 30, 2018. To submit, please sent the title and abstract of the poster (up to 250 words) by email to comsoc2018.rpi@gmail.com, with the subject "COMSOC-18 poster submission",

Open Poster Session Submission

COMSOC-2018 will include a open poster session. Posters will be selected based on abstracts. Unlike regular submissions, they will not be reviewed by the program committee. Posters will be selected based on abstracts of up to 250 words, which can be sent by email to comsoc2018.rpi@gmail.com, with the subject "COMSOC-18 poster submission", anytime until April 30, 2018.

Paper Submission and Camera Ready

The camera-ready version of accepted papers can be uploaded on the Easychair submission webpage, following the same requirements for submission as detailed below.

Regular papers should not exceed 12 pages in length, excluding references, contact information and a clearly-marked appendix of arbitrary length that will be read at the discretion of the PC members. When preparing your submission, please follow these formatting instructions. The easiest way of doing so is to use the Latex typesetting system with the class file comsoc2018.cls. The formatting instructions are based on a sample file (comsoc18.tex), which you can use as a starting point for your own paper.

You will be able to revise your submission any number of times before the deadline (March 1st, anywhere in the world).

All submitted papers will be reviewed by the program committee. Accepted papers will be collected in informal workshop notes that will not be printed. To accomodate the publishing needs of different scientific communities, we stress that authors will retain the copyright of their papers and that submitting to COMSOC-2018 does not preclude publication of the same material in a journal or in a conference with formal proceedings.

Submission of regular papers is restricted by the rule that a single person can present at most one paper at the workshop.

Call for Papers: Seventh International Workshop on Computational Social Choice (COMSOC-2018)

Troy, NY, USA, June 25--27, 2018

Webpage: www.cs.rpi.edu/~xial/COMSOC18

Mission

Computational social choice is a rapidly growing discipline at the interface of social choice theory and computer science. It is concerned with the application of computational techniques to the study of social choice mechanisms, and with the integration of social choice paradigms into computing. The aim of the workshop is to bring together different communities: computer scientists interested in computational issues in social choice; people working in artificial intelligence and multiagent systems who are using ideas from social choice to organize societies of artificial software agents; logicians interested in the logic-based specification and analysis of social procedures; and last but not least, researchers coming from social choice theory itself: economists, mathematicians and computer scientists.

Paper submission

Submissions of papers describing original, under review, or recently published work on all aspects of computational social choice are invited. Topics of interest include, but are not limited to computational issues that arise in the analysis of

  • Preference elicitation

  • Preference representation languages

  • Restricted preference domains

  • Voting rules

    • axiomatic properties

    • manipulation, control and bribery

    • voting equilibria and dynamics

  • Judgement aggregation

  • Fair division and allocation

  • Matching and coalition formation

  • Opinion diffusion and aggregation on social networks

  • Recommendation systems

  • Software for collective decision-making

We welcome both theoretical and empirical work on these topics, including, in particular, research on algorithms (exact, approximate, parameterized, online and distributed), learning, logic, uncertainty and simulations in the context of social choice.

Papers will have to be submitted electronically via Easychair. All submitted papers will be reviewed by the program committee. Accepted papers will be collected in informal workshop notes; however, the workshop has no formal proceedings and the authors retain their copyright. Each accepted paper will have to be presented by one of the authors, with the constraint that each workshop participant gives at most one talk (exceptions can be made due to unforeseen circumstances).

COMSOC-2018 will also include a poster session. Posters will be selected based on abstracts. Unlike regular submissions, they will not be reviewed by the program committee; the intention is to accept all posters that fall within the scope of the workshop subject to space constraints. Posters will be selected based on abstracts of up to 250 words, which can be sent by email to comsoc2018.rpi@gmail.com, with the subject "COMSOC-18 poster submission", anytime until April 30, 2018.

Please contact either one of the program chairs in case of any questions:

  • Edith Elkind (elkind@cs.ox.ac.uk)

  • Lirong Xia (xialirong@gmail.com)

IMPORTANT DATES

  • Paper submission deadline: March 1, 2018

  • Notification of authors: April 4, 2018

  • Poster submission deadline: April 30, 2018

  • Camera ready due: April 30, 2018

  • Workshop dates: June 25-27, 2018

Invited Speakers


David Chaum,

CEO of Privategrity and inventor of Random Sample Voting


Ashish Goel,

Professor, MS&E, Stanford University

Title: Decision Making at Scale: Algorithms and Markets

Abstract. YouTube competes with Hollywood as an entertainment channel, and also supplements Hollywood by acting as a distribution mechanism. Twitter has a similar relationship to news media, and Coursera to Universities. But there are no online alternatives for making democratic decisions at large scale as a society. In this talk, we will describe some algorithmic and market-inspired approaches towards large scale decision making that we are exploring. In particular, we will describe three recent results:

(1) We will show how a series of incremental votes can lead to an optimum solution to many budgeting problems. The incremental voting algorithms are inspired by prediction markets, where each subsequent participant provides a small correction to the market.

(2) We will describe how one can construct a market for public-decision-making inspired by the celebrated work of Foley and others on public good markets.

3) We will describe a deliberation mechanism where a group comes to a decision by a series of pairwise negotiations. We will show that this results in provably good decisions on median spaces.

The above results are in increasing order of interaction among decision makers -- in the first, individuals are reacting to an entire decision made by the rest of the society; in the second, individuals are participants in a market that looks very much like a traditional Fisher market, and in the third, participants interact with other participants directly as opposed to via aggregated prices.

This represents joint work with Brandon Fain, Nikhil Garg, Vijay Kamble, David Marn, Kamesh Munagala, Benjamin Plaut, and Sukolsak Sakshuwong.

Bio. Ashish Goel is a Professor of Management Science and Engineering and (by courtesy) Computer Science at Stanford University, and a member of Stanford's Institute for Computational and Mathematical Engineering. He received his PhD in Computer Science from Stanford in 1999, and was an Assistant Professor of Computer Science at the University of Southern California from 1999 to 2002. His research interests lie in the design, analysis, and applications of algorithms; current application areas of interest include social networks, participatory democracy, Internet commerce, and large scale data processing. Professor Goel is a recipient of an Alfred P. Sloan faculty fellowship (2004-06), a Terman faculty fellowship from Stanford, an NSF Career Award (2002-07), and a Rajeev Motwani mentorship award (2010). He was a co-author on the paper that won the best paper award at WWW 2009, an Edelman Laureate in 2014, and a co-winner of the SigEcom Test of Time Award in 2018. Professor Goel was a research fellow and technical advisor at Twitter, Inc. from July 2009 to Aug 2014.


E. Glen Weyl

Principal Researcher, Microsoft Research New England

Title: Radical Markets and Quadratic Voting

Abstract. In a new book with Eric Posner, Radical Markets: Uprooting Capitalism and Democracy for a Just Society, we argue that markets can be a radically egalitarian and emancipatory force, but only if they are freed from the shackles of conventional institutions such as private property, which is inherently monopolistic, and one-person-one-vote, which prevents market trade. In this talk I will present the basic paradigm of Radical Markets with a focus on Quadratic Voting (QV), an efficient market alternatives to one-person-one-vote, and the ways we have tried to operationalize it in practice. I will also highlight a range of open computational social choice problems around QV. Overall, my message is that by thinking bigger and bolder, computational social choice can be a force for social transformation and contribute importantly to the solution of our most pressing social crises: rising inequality, stagnating economies and increasing political tensions.

Bio. E. (Eric) Glen Weyl is a Principal Researcher at Microsoft Research New York City and a Visiting Research Scholar at Princeton University’s economics department. His work combines insights from economics, law, philosophy, computer science, political science, history and sociology radically expand the scope of market institutions so as to increase broadly shared prosperity and resolve social conflicts. His recent book with his most common collaborator, Eric Posner, Radical Markets: Uprooting Capitalism and Democracy for a Just Society ties together much of his work on these themes. He also works to put these ideas into practice through working with policymakers and through entrepreneurship, including his start-up Collective Decision Engines commercializing a Pareto-efficient voting technique he invented, Quadratic Voting.

Accepted Papers (Oral and Poster)

  • Zack Fitzsimmons and Edith Hemaspaandra. High-Multiplicity Election Problems
  • Takashi Kurihara. Leximax and leximin extension rules for ranking sets as final outcomes with null alternatives
  • Umberto Grandi, Sirin Botan and Laurent Perrussel. Multi-Issue Opinion Diffusion under Constraints
  • Martin Lackner and Piotr Skowron. A Quantitative Analysis of Multi-Winner Rules
  • Hongyao MaReshef Meir and David C. Parkes. Social Choice with Non Quasi-linear Utilities
  • Alex Carver and Paolo Turrini. Peer reviewing and manipulation under uncertainty
  • Erel Segal-Halevi and Warut Suksompong. Democratic Fair Allocation of Indivisible Goods
  • Omer Lev and Yoad Lewenberg. "Reverse Gerrymandering'': a Decentralized Model for Multi-Group Decision Making
  • Hanrui ZhangYu Cheng and Vincent Conitzer. A Better Algorithm for Societal Tradeoffs
  • Allan BorodinOmer LevNisarg Shah and Tyrone Strangway. Big City vs. the Great Outdoors: Voter Distribution and How it Affects Gerrymandering
  • Nawal BenabbouMithun ChakrabortyXuan-Vinh Ho, Jakub Sliwinski and Yair Zick. The Assignment Problem with Diversity Constraints with an application to Ethnic Integration in Public Housing
  • Moshe Mash, Yoram Bachrach, Kobi Gal and Yair Zick. How to Form Winning Coalitions in Mixed Human-Computer Settings
  • Ta Duy Nguyen and Yair Zick. Resource Based Cooperative Games: Optimization, Fairness and Stability
  • Umberto Grandi, James Stewart and Paolo Turrini. Personalised Rating
  • Akihiro Kawana and Tomomi Matsui. Trading Transforms of Non-weighted Simple Games and Integer Weights of Weighted Simple Games
  • Hadi Hosseini and Kate Larson. Strategyproof Quota Mechanisms for Multiple Assignment Problems
  • Piotr Faliszewski, Stanisław Szufa and Nimrod Talmon. Optimization-Based Voting Rule Design: The Closer to Utopia the Better
  • Rupert FreemanSeyed Majid ZahediVincent Conitzer and Benjamin C Lee. Dynamic Proportional Sharing: A Game-Theoretic Approach
  • Po-Ting Ling, Hung-Lung Wang and Kun-Mao Chao. Determining a social choice with respect to linear preferences
  • Arianna Novaro, Umberto Grandi, Dominique Longin and Emiliano Lorini. Goal-Based Collective Decisions: Axiomatics and Computational Complexity
  • Sefi Erlich, Noam Hazon and Sarit Kraus. Negotiation Strategies for Agents with Ordinal Preferences
  • Kazunori Ota, Nathanaël Barrot, Yuko Sakurai and Makoto Yokoo. Impact of the Number of Neutrals on Stability Concepts in Friends Oriented Hedonic Games
  • Felix Brandt, Johannes Hofbauer and Martin Strobel. Exploring the No-Show Paradox for Condorcet Extensions Using Ehrhart Theory and Computer Simulations
  • James Bailey and Craig Tovey. The Price of Deception in Spatial Social Choice
  • Marc Neveling and Jörg Rothe. Closing the gap of control complexity in Borda elections: Solving twelve open cases
  • Aleksei Kondratev and Alexander Nesterov. Random Paths To Popularity In Two-Sided Matching
  • Aleksei Kondratev and Alexander Nesterov. Weak Mutual Majority Criterion for Voting Rules
  • Sebastian Frederik Schneckenburger and Justin Kruger. Fall if it lifts your teammate: a novel type of candidate manipulation
  • Benno Kuckuck and Jörg Rothe. Sequential Allocation Rules are Separable: Refuting a Conjecture on Scoring-Based Allocation of Indivisible Goods
  • Zoi TerzopoulouUlle Endriss and Ronald de Haan. Aggregating Incomplete Judgments: Axiomatisations for Scoring Rules
  • Gal Cohensius, Omer Ben Porat, Reshef Meir and Ofra Amir. Efficient Crowdsourcing via Proxy Voting
  • Jakub Sliwinski, Yair Zick and Ayumi Igarashi. Statistically Stable Communities with Limited Interactions
  • Jakub Sliwinski and Yair Zick. Learning Hedonic Games
  • Karl-Dieter Crisman, Jian Cui and Min-Sun Kim. Broad Support in Two-Person Elections
  • Markus Brill and Nimrod Talmon. Pairwise Liquid Democracy
  • Max Bender, Kirk Pruhs and Alireza Samadian. Need-Aware College Admissions and the Stability of Marriage
  • Christian Saile and Warut Suksompong. Robust Bounds on Choosing from Large Tournaments
  • Georgios AmanatidisGeorgios Birmpas and Evangelos Markakis. Comparing Approximate Relaxations of Envy-Freeness
  • Elizabeth Silver, Chris Guest and Richard de Rozario. Adaptive voting aggregation for partial ballots in crowdsourcing
  • Andreas Darmann, Janosch Döcker, Britta Dorn, Jérôme Lang and Sebastian Frederik Schneckenburger. Simplified Group Activity Selection
  • Felix Brandt, Chrisitan Saile and Christian Stricker. Voting with Ties: Strong Impossibilities via SAT Solving
  • Stéphane Airiau, Haris Aziz, Ioannis Caragiannis, Justin Kruger and Jérôme Lang. Positional Social Decision Schemes: Fair and Efficient Portioning
  • Daniele PorelloNicolas TroquardRafael PenalozaRoberto Confalonieri, Pietro Galliani and Oliver Kutz. Social Mechanisms for the Collective Engineering of Ontologies
  • Manel Ayadi, Nahla Ben Amor and Jérôme Lang. The Communication Burden of Single Transferable Vote, in Practice
  • Elliot Anshelevich and Wennan Zhu. Tradeoffs Between Information and Ordinal Approximation for Bipartite Matching
  • Dorothea Baumeister, Daniel NeugebauerJörg Rothe and Hilmar Schadrack. Complexity of Verification in Incomplete Argumentation Frameworks
  • Dorothea Baumeister, Tobias Hogrebe and Lisa Rey. Generalized Distance Bribery
  • Abhijin Adiga, Chris J Kuhlman, Madhav V Marathe, S. S. Ravi, Daniel J Rosenkrantz and Richard E. Stearns. Inferring Users’ Choice Functions in Networked Social Systems Through Active Queries
  • Nicholas Mattei, Abdallah Saffidine and Toby Walsh. An Axiomatic and Empirical Analysis of Mechanisms for Online Organ Matching
  • Vijay Menon and Kate Larson. Robust and Approximately Stable Marriages under Partial Information
  • Zack Fitzsimmons, Edith Hemaspaandra, Alexander Hoover and David Narvaez. Very Hard Electoral Control Problems
  • Robert Bredereck, Piotr Faliszewski, Ayumi Igarashi, Martin Lackner and Piotr Skowron. Multiwinner Elections with Diversity Constraints
  • Omer LevReshef Meir, Svetlana Obraztsova and Maria Polukarov. Heuristic Voting as Ordinal Dominance Strategies
  • Dominik Peters. Proportionality and Strategyproofness in Multiwinner Elections
  • Ilan NehamaTaiki Todo and Makoto Yokoo. Manipulations-resistant facility location mechanisms for ZV-line graphs
  • Kumap Nahro. The Museum of Social Choice

Monday, June 25

9:00-10:00
Session 1: Invited talk
Invited talk: David Chaum
10:00-10:20 Coffee break
10:20-11:20
Session 2: Fair allocation
Chair: Ioannis Caragiannis
Rupert Freeman, Seyed Majid Zahedi, Vincent Conitzer and Benjamin C Lee. Dynamic proportional sharing: A game-theoretic approach
Georgios Amanatidis, Georgios Birmpas and Evangelos Markakis. Comparing approximate relaxations of envy-freeness
Erel Segal-Halevi and Warut Suksompong. Democratic fair allocation of indivisible goods
11:20-11:40 Coffee break
11:40-12:40
Session 3: Manipulation and control
Chair: Joerg Rothe
Sebastian Frederik Schneckenburger and Justin Kruger. Fall if it lifts your teammate: a novel type of candidate manipulation
Zack Fitzsimmons, Edith Hemaspaandra, Alexander Hoover and David Narvaez. Very hard electoral control problems
Zack Fitzsimmons and Edith Hemaspaandra. High-multiplicity election problems
12:40-14:10 Lunch (Russel Sage Dinning Hall)
14:10-15:50
Session 4: Empirical analysis Chair: Piotr Skowron
Nawal Benabbou, Mithun Chakraborty, Xuan-Vinh Ho, Jakub Sliwinski and Yair Zick. The assignment problem with diversity constraints with an application to ethnic integration in public housing
Nicholas Mattei, Abdallah Saffidine and Toby Walsh. An axiomatic and empirical analysis of mechanisms for online organ matching
Manel Ayadi, Nahla Ben Amor and Jérôme Lang. The communication burden of single transferable vote, in practice
Allan Borodin, Omer Lev, Nisarg Shah and Tyrone Strangway. Big city vs. the great outdoors: voter distribution and how it affects gerrymandering
Gal Cohensius, Omer Ben Porat, Reshef Meir and Ofra Amir. Efficient crowdsourcing via proxy voting
15:50 - 17:30 Coffee and poster session

 

Tuesday, June 26

9:00-10:00
Session 6: Invited talk
Ashish Goel: Decision Making at Scale: Algorithms and Markets
10:00-10:20 Coffee break
10:20-11:20
Session 7: Matching
Chair: Nick Mattei
Elliot Anshelevich and Wennan Zhu. Tradeoffs between information and ordinal approximation for bipartite matching
Vijay Menon and Kate Larson. Robust and approximately stable marriages under partial information
Aleksei Kondratev and Alexander Nesterov. Random paths to popularity In two-sided matching
11:20-11:40 Coffee break
11:40-12:40
Session 8: Graph-theoretic approaches
Chair: Elliot Anshelevich
Christian Saile and Warut Suksompong. Robust bounds on choosing from large tournaments
Dorothea Baumeister, Daniel Neugebauer, Jörg Rothe and Hilmar Schadrack. Complexity of verification in incomplete argumentation frameworks
Sirin Botan, Umberto Grandi and Laurent Perrussel. Multi-issue opinion diffusion under constraints
12:40-14:10 Lunch (Russel Sage Dinning Hall)
14:10-15:30
Session 9: Multiwinner elections
Chair: Reshef Meir
Piotr Faliszewski, Stanisław Szufa and Nimrod Talmon . Optimization-based voting rule design: the closer to utopia the better
Martin Lackner and Piotr Skowron. A quantitative analysis of multi-winner rules
Dominik Peters. Proportionality and strategyproofness in multiwinner elections
Robert Bredereck, Piotr Faliszewski, Ayumi Igarashi, Martin Lackner and Piotr Skowron. Multiwinner elections with diversity constraints
15:30-16:00 Coffee break
16:00-17:20
Session 10: Cooperative games
Chair: Bill Zwicker
Andreas Darmann, Janosch Döcker, Britta Dorn, Jérôme Lang and Sebastian Frederik Schneckenburger. Simplified group activity selection
Jakub Sliwinski, Yair Zick and Ayumi Igarashi. Statistically stable communities with limited interactions
Akihiro Kawana and Tomomi Matsui. Trading transforms of non-weighted simple games and integer weights of weighted simple games
Moshe Mash, Yoram Bachrach, Kobi Gal and Yair Zick. How to form winning coalitions in mixed human-computer settings
17:20-17:40 Coffee break
17:40-18:40 Business meeting
19:00- Banquet (Russel Sage Dinning Hall)

 

Wednesday, June 27

9:00-10:00
Session 11: Invited talk
Glen Weyl: Radical Markets and Quadratic Voting
10:00-10:30 Coffee break
10:30-11:50
Session 12: Axiomatic analysis
Chair: Piotr Faliszewski
Stéphane Airiau, Haris Aziz, Ioannis Caragiannis, Justin Kruger and Jérôme Lang. Positional social decision schemes: fair and efficient portioning
Zoi Terzopoulou, Ulle Endriss and Ronald de Haan. Aggregating incomplete judgments: axiomatisations for scoring rules
Felix Brandt, Chrisitan Saile and Christian Stricker. Voting with ties: strong impossibilities via SAT solving
Hongyao Ma, Reshef Meir and David C. Parkes. Social choice with non quasi-linear utilities
11:50-13:20 Lunch (Russel Sage Dinning Hall)
13:20-14:20 Rump session. Chair: Umberto Grandi
14:20-14:50 Coffee break
14:50-16:30
Session 13: Further topics
Chair: Vincent Conitzer
Omer Lev, Reshe