Seminar
| Parent Program: | |
|---|---|
| Location: | SLMath: Eisenbud Auditorium, Online/Virtual |
On the Price of Anarchy of the Probabilistic Serial Mechanism
Semi-Random Process
"Semi-Random Process" - Pawel Pralat
Abstract: The semi-random graph process is a single-player game that begins with an empty graph on n vertices. In each round, a vertex u is presented to the player independently and uniformly at random. The player then adaptively selects a vertex v and adds the edge uv to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible.
During the talk, we will focus on constructing perfect matchings but Hamilton cycles and constructing a subgraph isomorphic to an arbitrary fixed graph G will be briefly discussed. We will also consider a natural generalization of the process to s-uniform hypergraphs.
"On the Price of Anarchy of the Probabilistic Serial Mechanism" - Adrian Vetta
 |
"Semi-Random Process"
|