June 2018 Project: Judgment Aggregation

This is the website for the June 2018 Master of Logic project on Judgment Aggregation. We will post all information related to the project on this page.
This project is based on the Computational Social Choice course given by Ulle Endriss in 2015.

• Instructors: Sirin Botan & Zoi Terzopoulou
• Meetings: Mon-Thu, 11:00-13:00 in room F2.19 (SP 107).

Materials:

The Handbook of Computational Social Choice is a great resource for further reading on the topics covered in the project and many more. Trends in Computational Social Choice is also a good reference for what's going on with more current research (chapter 7 is about belief merging and JA, and chapter 8 is about complexity & strategic behavior in JA. Chapter 9 is about social networks and there are parts that are relevant to JA).

Homeworks:

We'll have four homeworks, one for each lecture in the first week. These should not take up too much time, and are mostly a way for you (and us) to check if you've understood the material. They are due the day after we post them, at 11am. You can email them to us or bring a paper copy to the lecture.

Presentations:

Your presentations in the second week should be similar to the format of the lectures of the first week. Each presentation should be around one hour including questions. The purpose is for each of you to present your paper in such a way that everyone in the audience leaves with a basic understanding of what the paper is about, and the main results. You will be the only one in the room who has read the paper, so when in doubt, go slow. Don't be afraid to make things interactive (we'd love to see some stars in the slides)!

Here is some advice on giving a talk by Ulle Endriss. Most things you need to consider before giving any kind of presentation are mentioned, so it's helpful to read even if you might not end up implementing all his suggestions. Note that some of it is written with conference-style talks in mind, so you can ignore those parts, or save them somewhere in the back of your mind for future endeavors.

When you are in the audience, ask questions! Even if you think they might be stupid (this doubles as a charitable act: you'll help out the person with the same question who is too concerned with looking smart to ask). These presentations are a prime opportunity to get used to interrupting lectures in a friendly environment, and for the presenters to get used to being interrupted. Note that it is obligatory to attend all these presentations.

Here is a simple beamer template for those of you who might want it to make your slides. Feel free to use/create your own or play around with this one to make it more your own style.

Papers:

In the third week you should all have chosen a paper topic and have started working on your idea. During this week we want to set up meetings with each of you to discuss (and approve) your idea and discuss what you'll focus on going forward. By the end of the second week you should have already thought a bit about a potential topic and have scheduled a meeting with us for either Monday (18th) or Tuesday (19th).

What we Expect from your Paper: You have two options for the final paper. You can either come up with an original idea and develop it as far as you can, or you can do a thorough analysis of existing work (note that this does not mean summarising a few papers, your insights should still be original even though you do not prove new results). We highly encourage you to go with the first option, even if you only have the seed of an idea. Since this is a short project, it is ok if you don't manage to prove some amazing result, as long as you explain what your goal was and why you did not manage to come up with a proof (this does not mean something like "it was hard and I didn't have much time"). We expect everything in your papers to be correct, and well written.

The deadline for the paper is at the end of the fourth week, but you will need considerable time for the pre-writing work that goes into the paper so get started early.

In principle, any paper topic related to JA is fair game. If anything piqued your interest during the first couple weeks and you already have a vague idea, that's great! Come talk to us and we'll help you make it less vague.

For those of you who aren't sure what to write about, we have a few suggestions for possible topics below (of course, you can also find inspiration in the list of papers we posted for the presentations):

• Comparing other Frameworks to JA. We'll see presentations on a few other frameworks and how they relate to JA (belief merging and BA). As mentioned, the framework for voting can also be embedded into JA (J. Lang, and M.Slavkovik. Judgment Aggregation and Voting Rules. (ADT 2013)) Your paper could explore some other related framework. One nice idea might be to look at approval voting (S.J. Brams, and P.C.Fishburn. Approval Voting. The American Political Science Review, 72(3), 831-847, 1978). Some questions you could ask: Is the embedding you find useful? Is it possible to transfer results from one framework to the other? Maybe you think some of the restrictions of the JA framework are unrealistic and want to explore what happens when you relax them? (for inspiration, see: U. Endriss. Judgment Aggregation with Rationality and Feasibility Constraints. (AAMAS 2018)).
• Analysis of JA from Complexity Point of View: We'll see a few complexity results in JA in the presentation week, but there are tons more! For example, there have been several papers which explore complexity as a barrier to strategic behavior (D. Baumeister, J. Rothe, and A. Selker. Complexity of Bribery and Control for Uniform Premise-Based Quota Rules Under Various Preference Types. (ADT 2015)). Maybe you can think of some other phenomenon in JA where a complexity-based analysis would be interesting? Perhaps with some extra assumptions or in some special cases some of the hardness results in the literature will no longer hold? Another angle: We've seen that the Kemeny rule seems reasonable but determining the outcome is not possible in polynomial time. Is it possible to define a new aggregation rule which approximates Kemeny for which determining the outcome is computationally tractable? (for inspiration, see: P. Skowron, P. Faliszewski, and A. Slinko. Achieving fully proportional representation: Approximability results. Artifical Intelligence 222, 67-103, 2015.)
• Further Analysis of Strategic Behavior. We discussed how one might want to study manipulation for a different class of preferences, or with different assumptions about what information is available to agents; maybe you want to include more game theoretic aspects like bargaining or cooperation. Maybe you have a favorite game theoretic concept that you'd like to explore in the JA framework. Here are a few papers to look at for ideas:
  • U. Grandi, D. Grossi, and P. Turrini. Equilibrium Refinement through Negotiation in Binary Voting. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015).
  • S. Botan, A. Novaro, and U. Endriss. Group Manipulation in Judgment Aggregation. In Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2015).
  • Z. Terzopoulou, and U. Endriss. Modelling Iterative Judgment Aggregation. In Proceedings of the 32th AAAI Conference on Artificial Intelligence (AAAI 2018).
• Truth Tracking. We saw some quite simple results related to truth tracking in JA (for the premise-based and conclusion-based rules), but many rules remain unexamined. One possible idea would be to look at how well some other known rules uncover a ground truth. Maybe under some assumptions about the agents some rules are better than others? In Voting, some rules can be defined as maximum likelihood estimators-there is a ground truth and each vote is a "noisy" estimate of this truth. Several of the results in E. Elkind, P. Faliszewski, and A. Slinko. Good Rationalizations of Voting Rules (AAAI 2010), are of this nature and are about voting rules which have counterparts in JA. You could examine whether their results still hold in the more general JA framework (or under which assumptions) or, if they fail, why.
• Axiomatic Characterisations We saw characterisations and (im)possibility results for judgment aggregation rules satisfying specific axioms. Do some of the axioms seem too strong to you? You could then try to relax them, motivate the new versions you design, and check which rules satisfy them. You could also try to investigate the safety of the agenda problem for your new axioms. This paper does something along these lines: F. Dietrich, and Christian List. Judgment Aggregation without Full Rationality. Social Choice and Welfare, 31(1), 15-39, 2008.

When you get to the writing stage, Ulle has you covered once again with some advice on writing a paper.

Your paper should be around 4-5 pages long (including references), using the IJCAI LaTeX style. The submission deadline for the paper is Friday 29 June 2018.

Possible papers for presentation:

Reserved papers have your name at the end.

• C. Duddy, and A. Piggins. Many-valued Judgment Aggregation: Characterising the Possibility/Impossibility Boundary. Journal of Economic Theory, 148, 793-805, 2013.
• M. van Hees. The Limits of Epistemic Democracy. Social Choice and Welfare, 28(4), 649-666, 2007.
• F. Dietrich, and Christian List. Judgment Aggregation without Full Rationality. Social Choice and Welfare, 31(1), 15-39, 2008.

• U. Endriss, U. Grandi, and D. Porello. Complexity of Judgment Aggregation. Journal of Artificial Intelligence Research, 45, 481-514, 2012. (Rachael)
• R. de Haan, and M. Slavkovik. Complexity Results for Aggregating Judgments using Scoring or Distance-based Procedures. In Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2017).

• F. Dietrich. A Generalised Model of Judgment Aggregation. Social Choice and Welfare, 28(4), 529-565, 2007.
• G. Cina, and U. Endriss. A Syntactic Proof of Arrow's Theorem in Modal Logic of Social Choice Functions. In Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2015).

• C. List. Group Communication and the Transformation of Judgments: an Impossibility Result. Journal of Political Philosophy, 19(1), 1-27, 2011.
• Z. Christoff, and D. Grossi. Stability in Binary Opinion Diffusion. In Proceedings of the 6th International Conference on Logic, Rationality and Interaction (LORI 2017).(Dimitris)

• F. Dietrich. Judgment Aggregation and Agenda Manipulation. Games and Economic Behavior, 95, 113-136, 2016.(Sven)
• N. Alon, D. Falik, R. Meir, and M.Tennenholtz. Bundling Attacks in Judgment Aggregation. In Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI 2013).

• İ. Bozbay, F. Dietrich, and H. Peters. Judgment Aggregation in Search for the Truth. Games and Economic Behavior, 87, 571-590, 2014. (Kristoffer)
• L.Bovens and W. Rabinowicz. Democratic Answers to Complex Questions - An Epistemic Perspective. Synthese, 150, 131-153, 2006.

• U. Grandi, and U. Endriss. Binary Aggregation with Integrity Constraints. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011). (Federico)
• P. Everaere, S. Konieczny, and P. Marquis. Belief Merging versus Judgment Aggregation. In Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2015). (May)
• J. Lang, and M.Slavkovik. Judgment Aggregation and Voting Rules. In Proceedings of the 3rd International Conference on Algorithmic Decision Theory (ADT 2013).