The Effect of Collusion in Congestion Games
Ara Hayrapetyan, Éva Tardos and Tom Wexler
ACM Symposium on Theory of Computing (STOC), 2006
We consider the question of how collusion alters the quality of solutions
obtained in competitive games. The price of anarchy aims to measure the cost of the
lack of coordination by comparing the quality of a Nash equilibrium to that
of a centrally designed optimal solution. However, this notion assumes that players act
not only selfishly, but also independently. If a subset of players collude, this can improve
the social welfare of the participants, but it can also harm the welfare of those outside
the coalition. The question we study is what is the effect of such collusion on the
overall solution quality.
Unbalanced Graph Cuts
Ara Hayrapetyan, David Kempe, Martin Pál and Zoya Svitkina
European Symposium on Algorithms (ESA), 2005
We introduce the Minimum-Size Bounded-Capacity Cut (MSBCC) problem, in which we are given a graph
with an identified source and seek to find a cut minimizing the number of nodes on the source side
subject to the constraint that the capacity may not exceed a prescribed bound. Besides being of
interest in the study of graph cuts, this problem arises in many practical settings, such as
epidemiology, disaster control, military containment, as well as finding dense subgraphs and
communities in graphs. Our main result is a (1/λ, 1/(1 - λ)) - bicriteria approximation
algorithm for any 0 < λ < 1, where the first parameter is the extent by which the desired
capacity is violated, and the second parameter is the extent by which our solution is larger than the
optimal solution that does not violate the capacity constraint.
A Network Pricing Game for Selfish Traffic
Ara Hayrapetyan, Éva Tardos and Tom Wexler
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), 2005
Selected for publication in the special edition of the journal Distributed Computing.
The internet, unlike many small-scale networks, is built in a decentralized fashion and is controlled
by a large number of disparate service providers who are not interested in any global optimization.
Instead, the providers seek to maximize their own profit by charging users access to their service.
Users themselves behave selfishly, optimizing over price and quality of service. Game theory provides
a natural framework for a study of such a situation. However past work in this area has mostly focused
on either the service providers or the network users, but not both. The paper introduces a new model
for exploring the interaction of these two elements, in which network managers compete for users via
prices and quality of provided service. We study the extent to which competition between service
providers hurts the overall social utility of the system.
Network Design for Information Networks
Ara Hayrapetyan, Chaitanya Swamy and Éva Tardos
ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005
We define a new class of network design problems motivated by designing information networks. In our
model, the aggregate cost of transporting flow for a set of users depends on actual set of users, not
just the total demand. We assume that this aggregation cost follows economies of scale, that is,
incremental cost of a new user is less if the set of users already served is large. We provide
constant-factor approximation algorithms to two problems in this general model. In the
Group Facility Location problem, each user requests a resource, and the cost depends on the number of
resources (instead of the number of users). The Dependent Maybecast Problem extends the
Karger-Minkoff maybecast model to probabilities with limited correlation. We also show how to use
dependent maybecast to solve the k-stage stochastic Steiner tree problem for any fixed k.
A New
Decidability Technique for Ground Rewrite Systems with Applications
Rakesh Verma and Ara Hayrapetyan
ACM Transactions on Computational Logic (TOCL), 2005
Programming language interpreters, proving equations, abstract data types, program transformation and
optimization and even computation itself (e.g. turing machine) can be specified by a set of rules,
called a rewrite system. Two fundamental properties of a rewrite system are the confluence of
Church - Rosser property and the unique normalization property. In this article we develop a standard
form for ground rewrite systems and the concept of standard rewriting. These concepts are then used to
prove a pumping lemma for them and to derive a direct decidability technique for decision problems of
ground rewrite systems.