Traceable Graphs and Fair Division

3rd October 2022, at 14:00

Room: TBD

Speaker: WILLIAM  S.  ZWICKER, Murat Sertel Center for Advanced Economic Studies, Istanbul Bilgi University, and William D. Williams Professor of Mathematics Emeritus, Union College

Title: Traceable Graphs and Fair Division

Abstract:

We consider the algorithmic problem of finding the optimal weights and biases for a two layer fully connected neural network to fit a given set of data points. This problem is known as "empirical risk minimization" in the machine learning community.

Three recent papers have explored the connection between the traceability of a finite graph G, and the ability to divide G fairly.  We'll discuss an open question: exactly how tight is the connection?  Here a graph is traceable if there is a Hamiltonian path – one that visits each vertex exactly once.   In fair division of a graph G we allocate G's vertices to finitely many agents so that 

·       each agent's share forms a connected subgraph, and 

·       no agent prefers another's share to her own by more than one vertex

We say that such an allocation exists universally for G if it exists for every choice of number of agents and for every assignment to agents of monotonic preferences over sets of vertices.  Is it true that 

G is traceable iff fair allocations exist universally for G?

Recent work by A. Igarashi shows that traceability implies fair allocations exist universally.  The converse is open.  If it held, then the fair division question would inherit NP-completeness from the traceability question. We will discuss a few specific graphs that seem particularly relevant.