Report from COMSOC 2012

Guest post by Yair Zick.

COMSOC 2012 in Numbers:

54 papers were submitted, with 38 accepted; the review process was handled by 21 committee members who handled a total of 162 reviews. The workshop held 4 keynote talks and one tutorial. Germany had the greatest number of publications, with the United States in second place and Israel at a respectable third. Attendance and submission were slightly lower this year; this may be attributed to the lack of tutorial days and the clash with the start of the semester in the U.S. and Canada. Papers were presented in a single session format, spanning three days.

The Workshop at a Glance:

Piotr Faliszewski and Felix Brandt organized a great workshop. The schedule was busy, but the long breaks (with plenty of food and coffee provided) allowed for continued focus throughout the day. Another culinary point to note is the provision of meals for those with special dietary needs. The lunches and the social dinner (held in the old Jewish quarter) had vegetarian and Kosher food options, both reportedly palatable. COMSOC really stands out in this respect as many big conferences have a poor track record with providing for special dietary restrictions. The workshop was held in the AGH university of science and technology; the new facilities allowed for a smooth experience (with the exception of a few adversarial laptops refusing to obey their owners).

The Business Meeting:

During the business meeting, it was suggested that future workshops include a poster session as well. A poster session would allow for an increase in the number of accepted papers while largely maintaining the workshop format: avoiding parallel sessions, and avoiding an overly long or packed schedule. It was suggested that papers would be put in poster sessions according to both quality and their publication history. The logic being that a paper that has previously appeared in previous venues should appear in a poster session over a new line of research. If such a poster session is to take place in future COMSOCs, the organizers would then be faced with the following preference elicitation problem: which should be a poster paper? a lower merit new paper, or a higher quality published work? Another point that was argued for was allowing papers from less prominent disciplines to take precedence over those dealing with well-established problems. This would arguably provide more focus on interdisciplinary and innovative work.

Another topic raised at the business meeting was the timing of the workshop. Currently COMSOC is held in even years around September-October; this allows both for ample time to organize the workshop and avoids competition with other conferences that are usually held during the summer. However, this poses a problem for researchers hailing from America, which was indeed evident in the number of accepted papers. This is understandable as the workshop fell on exactly the first week of the semester in the U.S. and Canada; however, an agreement as to the best time has yet to be reached.

Some suggested holding the workshop in conjunction with events in the non-computational social choice community, which will improve the interaction between the two communities, but would also increase the number of constraints as to workshop timing and venue. The venue for the next workshop is yet undecided, though several attendees called for a location outside Europe.

Research Topics:

The topics presented this year did not radically differ from those presented in COMSOC 2010; though new models were presented, most papers focused on analysis and extension of existing models. Here are some highlights.

There was a significant focus on judgment and preference aggregation. In his keynote talk, Clemens Puppe discussed paradoxes in various preference aggregation problems. He showed a characterization of such scenarios where paradoxes do not exist, and some ways of avoiding paradoxes while maintaining a rich problem structure. Some of the work on the topic was quite high-level: Umberto Grandi presented a general model for studying paradoxes in voting and judgment aggregation; Dvir Falik presented impossibility (and possibility) results for a general model of binary evaluation aggregation. Some discussed aspects or variations of known problems: Dorothea Baumeister discussed the complexity of bribery and manipulation in judgment aggregation; Ulle Endriss explained what happens when agents need to agree on a common graph structure; Jerome Mengin presented aggregation problems in the multi-issue domain, and Amirali Salehi-Abari talked about the impact of an underlying social network on preference aggregation.

Uncertainty and randomness in elections was also mentioned in several papers. Uncertainty was studied in voters’ preferences (Aziz et al.), candidate deletion (Boutilier et al.), scores assigned by voters (Baumeister et al.), the voting rule used (Erdelyi & Elkind) and the way ties are broken (Obraztsova et al.).

Parameterized complexity was also discussed to an extent. We started with an excellent tutorial by Rolf Niedermeier on parameterized complexity. Rolf introduced some basic concepts from the theory of parameterized complexity, such as fixed parameter tractability (FPT), as well as a high-level overview of the higher complexity classes. He then proceeded to discuss methodologies for proving membership in FPT or some of the higher complexity classes used in the study of parameterized complexity. Although some papers applied parameterized complexity analysis, I believe that there is still plenty of room for applying parameterized complexity techniques in computational social choice.

Some speakers employed interesting and powerful tools from abstract algebra and geometry. The keynote talk by Craig Tovey discussed the geometry of spatial voting: a higher-dimension equivalent of hotelling’s voting model. Geometric analysis of the problem allows one to identify sets of points that have some highly desirable properties (one with a particularly cute name is the yolk). The keynote talk by Michel Le Breton also showed some interesting uses of Erhart polynomials in the combinatorial analysis of the probability that a player is pivotal in a simple game. Apart from that, he discussed how different assumptions on the underlying probability space lead to different power indices (with a natural focus on the Shapley-Shubik, Banzhaf and Penrose measures). He showed some results on the social welfare achieved by these power indices, and the combinatorial structure of various voting models. There were other papers that employed geometric analysis. Lirong Xia talked about the number of swaps required in order to manipulate an election, essentially measuring the maximal hamming distance between an election and a successful manipulation. Dimitrii Shiryaev talked about upper and lower bounds on the volume of the space of elections where a given candidate is a winner. Schurmann showed how to use Erhart polynomials in order to compute the probability of a condorcet paradox in an election, and how to mitigate the exponential blowup of the problem using known properties of the underlying polyhedron.

The last keynote talk was by Gerhard Woeginger, who talked about the complexity of core stability in cooperative hedonic games. He discussed in length the complexity of some classes of hedonic games, and presented a host of open problems in the field. One interesting class of games he discussed was those induced by friendship relations. Briefly, these are games where one values a coalition based on an underlying preference order on the other agents.

Ambience:

COMSOC 2012 was held in the beautiful city of Krakow, Poland. The city provides plenty of scenery and cultural experiences. I didn’t get much time to see the historical sites, but the old Jewish quarter (Kazimierz) and the city castle (Wawel) both provided for very picturesque walks. The old city holds the impressive market square (Rynek Glowny), boasting a huge antiques market, where you could get wartime artifacts as well as old silverware and kitchen items. The non-antiques market had really fun stalls. I was particularly impressed with the fur-selling stalls, where one could get rabbit-fur hats, lambskin coats and whole reindeer pelts. Those seemed less attractive to me for both practical reasons (wearing a fur hat in Singapore is a very bad idea), and my own personal tastes. However, the stalls selling woodwork, displaying hand-carved toy trains, jewelry boxes and chess sets provided more tropical-weather-friendly items. Under the generous guidance of two of the locals, Piotr and Piotr, we were introduced to East-European restaurants, serving simple and delicious food which certainly exceeded its dismal reputation (gefilte fish anyone?).

Advertisement