Monday, January 11, 2016
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
Room: MA 041
Lecture - 14:15
Abstract:
Bargaining is a central topic of study in economics and in the social
sciences. In the most basic setting, two agents A & B negotiate how to
split a dollar. Assume the agents have monetary outside options a & b,
respectively, that they receive, should negotiations fail; Nash's
famous bargaining solution predicts that in an equilibrium, the agents
each receive their outside options, and that the remainder is split
evenly; i.e., the agents receive x_A and x_B such that x_A-a=x_B-b.
In this talk we will look at a natural generalization of Nash
bargaining to agents interacting in social networks. We will present a
natural equilibrium concept extending Nash's condition, and present
Kleinberg & Tardos' recent characterization of graphs that admit
equilibria. We will present connections between bargaining
theory, cooperative games, and matching theory and use these to
derive elegant algorithms for the computation of equilibria.
Colloquium - 16:00
Abstract:
We discuss a connection between the chromatic index χ'(G) and the
treewidth of a simple graph G. The treewidth of a graph measures the
graph's similarity to a tree and χ'(G) gives the number of distinct
colours needed to properly colour the edges of G. The chromatic index
equals either the maximal degree Δ(G) or Δ(G) + 1, but its
determination is non-trivial. We conjecture that any graph G with
treewidth k and Δ(G) ≥ k + √k satisfies
χ'(G) = Δ(G). To support our conjecture we prove its fractional
version. We show the proposed bound is tight and that
χ'(G ) = Δ(G) if Δ(G) ≥ 2k-1.
This is joint work with Henning Bruhn and Richard Lang.