Technical Report PHD-2009-06

Title: Stability in Multi-Agent Environments and Approximation Algorithms for NP-Hard Graph Problems
Authors: Roee Engelberg
Supervisors: Prof. Seffi Naor
Abstract: 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 Autonomous Systems (ASes) that make up today's Internet. Informally, BGP requires ASes to continuously choose their most preferred routes out of the most recently announced routes from neighboring ASes. The convergence of this route selection process is referred to as BGP safety, which is of high importance since in the resulted equilibrium the routing outcome is stable. We study AS's preference classes for which BGP safety is guaranteed while relying on the substitution of the traditional worst-case analysis with a more realistic probabilistic approach.

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.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF or PS files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2009
To the main CS technical reports page

Computer science department, Technion