Theory Lunch This Week (Thursday 2/6, GCS 502C, 12:00 PM)

[Grayson York]

Hi all,

This Thursday 2/6 Jason Liu will be giving the following talk at 12:00PM in GCS 502C. Hope to see you all there!

In multiwinner approval voting, forming a committee that proportionally represents large cohesive groups of voters is an essential task. In common, there are two definitions for ''cohesiveness'' and two definitions for ''representation''. Three of the four combinations had been studied, leading to axioms known as PJR, EJR, and FJR. We investigated the fourth possibility, which we call Full Proportional Justified Representation (FPJR). We compared FPJR with the known ones, and showed that several proportionality axioms (priceability, perfect representation, etc.) and efficient rules (Monroe, method of equal shares, etc) satisfy FPJR. We also showed that verifying FPJR and verifying FJR are coNP-complete, the latter of which was open for years.

Joint work with Yusuf Hakan Kalacyi and David Kempe.