Ph.D Thesis | |

Ph.D Student | Engelberg Roee |
---|---|

Subject | Stability in Multi-Agent Environments and Approximation Algorithms for NP-Hard Graph Problems |

Department | Department of Computer Science |

Supervisor | PROF. Joseph Naor |

Full Thesis text |

We study decision making under different types of limitations.

In the first part,
we concentrate on *games* where several *players* continually
interact. The players are selfish and have their own goals, but no single
player has full control over its performance as the outcome depends on the
choices of all of the players. The solution concept we study is the *equilibrium*
of the game, which can be thought of as a *status quo* in which no player
has an incentive to deviate from its current choices. Specifically, we study
the following:

** Online
games** are non-cooperative games that model scenarios combining online
decision making with interaction between non-cooperative agents. Roughly
speaking, an online game captures systems in which independent agents serve
requests that arrive in an online fashion in a common environment. The players
have to choose as a strategy an online algorithm. After presenting our model,
we focus on characterizing the equilibria in online games.

** **

The ** Border
Gateway Protocol (BGP)** establishes routes between the

In the second
part we study NP-hard optimization problems. It is commonly believed that the
optimal solution for these problems is intractable and thus cannot be found
efficiently. Instead, we look for the best solution that can be computed
efficiently by *approximation algorithms*. Specifically, we study the
approximability of the following graph problems:

** **

**Cut Problems
with a Budget Constraint -** A *cut* in a connected graph is a set of
edges whose removal from the graph disconnects the vertex set. We study
budgeted variants of classical cut problems.

** **

**The Spanning Star Forest Problem** - A *star* graph is a tree of diameter at most two. A
*star forest* is a graph that consists of node-disjoint star graphs. The
spanning star forest problem is to find a star forest that contains all the
vertices of the given graph and has the maximum number of edges.