[Facets-of-complexity] Invitation to Monday's Lecture & Colloquium July 11.

[Ita Brunke <i.brunke@fu-berlin.de>]

Dear all,

next Monday's Lecture and Colloquium will take place on July 11 at 14:15 & 16:00 at TU Berlin.

You all are cordially invited.

Location:

Room MA 041 - Ground Floor
Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin

Time: Monday, July 11 - 14:15

Lecture: Bill Zwicker (Union College, USA)

Title: Higher-order Condorcet cycles

Abstract:

In an ordinary Condorcet cycle one can identify, for each candidate, a second candidate preferred, by a majority of voters, to the first.  In a Condorcet cycle of order 2 one can identify, for each pair of candidates, a third candidate preferred, by a majority of voters, to both.  We construct two Condorcet cycles of order 2.  The first, with 11 alternatives and 11 voters, improves the example of 15 alternatives and 15 voters given in [1].  The second, with 7 alternatives and 21 voters, shows that the lower bound on alternatives established in [4] and [3] (and independently in [1]) is sharp. Both our constructions use the method of horizontal rotation, introduced here, which generalizes the more typical form of rotation used to construct standard Condorcet cycles. The second example also makes use of a beautifully symmetric tournament constructed in [3].

William S. Zwicker^a (joint work with Davide P. Cervone^b)

keywords: Condorcet cycle of order 2, Condorcet winning set, tournament

[1] Elkind, E., Lang, J., and Saffidine, A., Condorcet Winning Sets, Soc Choice Welf 44, 493-517 (2015)

[2] Erdös, P., On a problem of graph theory, Math Gaz 47, 220-223 (1963)

[3] Graham, R.L. and Spencer, J.H., A constructive solution to a tournament problem, Can Math Bul 14, 45-48 (1971)

[4] Szekeres, E. and Szekeres,G., On a problem of Schütte and Erdös, Math Gaz 49, 290-293 (1965)

^aWilliam D Williams Professor of Mathematics Emeritus, Union College, New York; and Murat Sertel Center for Advanced Economic Studies, Istanbul Bilgi University

^bMathematics Department, Union College, New York

Coffee & Tea Break :

Room MA 316 - Third Floor


Time: Monday, July 11 - 16:00 s.t.

Colloquium: Warut Suksompong (National University of Singapore)

Title: The Price of Connectivity in Fair Division

Abstract:

We study the allocation of indivisible goods that form an undirected graph and quantify the loss of fairness when we impose a constraint that each agent must receive a connected subgraph. Our focus is on well-studied fairness notions including envy-freeness and maximin share fairness. We introduce the price of connectivity to capture the largest gap between the graph-specific and the unconstrained maximin share, and derive bounds on this quantity which are tight for large classes of graphs in the case of two agents and for paths and stars in the general case. For instance, with two agents we show that for biconnected graphs it is possible to obtain at least 3/4 of the maximin share with connected allocations, while for the remaining graphs the guarantee is at most 1/2. In addition, we determine the optimal relaxation of envy-freeness that can be obtained with each graph for two agents, and characterize the set of trees and complete bipartite graphs that always admit an allocation satisfying envy-freeness up to one good (EF1) for three agents. Our work demonstrates several applications of graph-theoretic tools and concepts to fair division problems. Joint work with Xiaohui Bei, Ayumi Igarashi, and Xinhang Lu.