Recording 2020-12-03

00:17:37 Luis Sánchez Fernández: Hi all, unfortunately my camera does not seem to work. I don't know why.

00:18:08 Dominik Peters: Apologies for easy riddle

00:18:15 Dominik Peters: Ask questions like this:

00:18:20 Dominik Peters: QUESTION: Is this a question?

00:30:19 Reshef Meir: QUESTION: Shouldn't D just be part of the output (i.e. candidates with 0 seats)? why restrict up front?

00:31:05 Ulle Endriss: I think this maximin think is defined for *every* set D.

00:31:21 Ulle Endriss: think —> thing

00:31:39 Luis Sánchez Fernández: Hi. I'm not sure what you mean. But you could compute the maximin support for any subset D.

00:32:13 Hayrullah Dindar: Yeah, probably you might restrict attention to only sets of cardinality of 2 or 3 at the outset but other than that it was just an example

00:33:35 Reshef Meir: ok I see now. It is defined for every D and they we look for a "good" D

00:33:55 Luis Sánchez Fernández: You can compute how to distribute the support for any candidate subset (of any size) so that the support of the least supported candidate is maximized.

00:34:26 Rida Laraki: 32

00:34:29 Christian Stricker: E with 32?

00:34:33 Rob LeGrand: maximin({E}) = 32

00:34:33 Arthur Boixel: {E} 32

00:34:36 Hayrullah Dindar: E

00:34:47 matthias.bentert@tu-berlin.de: E (32)`?

00:35:38 matthias.bentert@tu-berlin.de: E, S (18)?

00:35:39 Krzysztof Sornat: E,B -> 20

00:35:41 xmora: Now S, I suppose

00:35:46 Martin Bullinger: {E,L} with 21

00:35:58 Rida Laraki: E+S...

00:36:03 Hayrullah Dindar: EL 21

00:36:09 matthias.bentert@tu-berlin.de: E+L 21 should be right

00:36:11 Umberto Grandi: E,L

00:39:57 Nisarg Shah: QUESTION: What about global MMS vs global Phragmen?

00:40:04 Nisarg Shah: OK well, that answers my question.

00:40:30 Rida Laraki: QUESTION: Is the algorithm convergence to the same solution if you start with all candidates then remove one by one the candidates…

00:41:41 Luis Sánchez Fernández: Good question. We have not tried that. In general it could be much more computationally costly (you can have much more candidates tan k).

00:43:35 Rida Laraki: Question: Thanks Luis. Is there a full axiomatic characterisation?

00:43:36 Nisarg Shah: QUESTION: If you look at the Phragmen objective, is there an opposite result where sequential Phragmen gives a constant approximation but sequential MMS does not?

00:43:38 Rupert Freeman: QUESTION: Does the approximation to the maximin support objective imply an approximation to the optimal load balancing?

00:43:40 Paul Harrenstein: Doesn't the efficiency of the method not also depend on the growth of the size of the LPs that need to be solved?

00:44:39 Rob LeGrand: QUESTION: How do MMS/Phragmen winner sets compare to the minimax method of Brams, Kilgour, Sanver (also NP-hard to compute but approximable in practice)?

00:48:39 Vincent Conitzer: QUESTION: if the goal is to approximate maximin support, we could presumably do better at least in practice (i.e., consider pairs of candidates to add at the same time instead of individual ones). Would that lose you properties you care about?

00:48:44 Luis Sánchez Fernández: I believe that the constant factor approximation to maximin support implies a constant factor to optimal load.

00:50:38 Luis Sánchez Fernández: We have made experiments with millions of voters and tenths of candidates elected.

00:52:38 Luis Sánchez Fernández: My conjecture is 4/3

00:54:08 Marcus Pivato: Will this be on the final exam?

00:54:17 Rob LeGrand: Like Vince, my semester just ended so I finally have time.

00:54:54 Krzysztof Sornat: Regarding Edith last question: in Lemma 9 of the work by Cevallos et al. they 1.2-eps hardness of approximation by reduction from k-Independent Set on cubic graphs.

00:55:01 Ulle Endriss: BREAK NOW: back around __:50

01:10:41 Paolo: Is the graph undirected?

01:11:34 Leon Kellerhals: Yes, in this model the edges are undirected.

01:13:44 Umberto Grandi: Question: is it the same setting of the segregation game by Schelling (but not on a grid)?

01:14:10 Reshef Meir: In the segregation game they jump to another location

01:14:21 Umberto Grandi: No, it’s not! (I answer to myself).

01:14:55 Reshef Meir: this looks like a special case of recurrent neural networks (at least in the binary case), which allows arbitrary weights on edges.

01:17:26 William Zwicker: Have you considered a relation on the set of opinions? For example a 1-dimensional spectrum, in which people are influenced by opinions of neighbors that might pull them to the left or right along the spectrum — a model for polarization.

01:29:16 Umberto Grandi: Question: the results by Goles and Olives work for generalisations of majority? (I think so) How about your results?

01:30:04 Umberto Grandi: generalisations of majority=threshold functions

01:30:10 Judy: are there real world phenomena modeled by this? (cool work, btw.)

01:30:36 Joe Singleton: Question: can the model be generalised to weighted graphs, where nodes may influence each other to varying degrees?

01:31:03 Reshef Meir: Bruck, Jehoshua. "On the convergence properties of the Hopfield model." Proceedings of the IEEE 78.10 (1990): 1579-1585.

01:31:05 Judy: also have you looked at probabilistic updates?

01:31:27 Reshef Meir: this is for arbitrary edge weights and threshold but only binary vertices

01:32:49 Rob LeGrand: Thanks everyone!

01:33:30 Ulle Endriss: Bye!