|
1. An O(log n/log log n)-Approximation
Algorithm for the Asymmetric Traveling Salesman Problem, with M. Goemans, A. Mądry, S. Oveis Gharan, and A. Saberi. [PDF]
We finally break the barrier of O(log n)-approximation factor of
Frieze, et al. for the Asymmetric Traveling Salesman Problem after almost 30
years by providing an O(log n / log log n)-approximation algorithm. Our
approach is based on constructing a “thin” (undirected) spanning tree from
the solution of a classical linear programming relaxation of the problem and
augmenting the tree to an Eulerian subgraph through
min-cost flow. Our rounding method is based on sampling from a maximum
entropy distribution.
This paper will appear in the 21st ACM-SIAM Symposium
on Discrete Algorithms [SODA], 2010.
Winner of the Best Paper Award.
2. Maximizing Stochastic Monotone Submodular Functions, with H. Nazerzadeh and A. Saberi.
[PDF]
We study the problem of maximizing a stochastic monotone submodular function
with respect to a matroid constraint. Our model can capture the effect of
uncertainty in different problems, such as cascade effects in social
networks, capital budgeting, sensor placement, etc. We study the adaptivity
gap of this problem, i.e. the ratio between the values of optimal adaptive
and non-adaptive policies, and show that it is equal to e/(e-1). This result
implies that the benefit of adaptivity is bounded. We also study the myopic
policy and show that it is a 1/2-approximation. Furthermore, when the matroid
is uniform, approximation ratio of the myopic policy becomes 1-1/e that is
optimum.
A preliminary version of this paper is appeared in the 4th Workshop on Internet and Network Economics
[WINE], 2008.
3. An Approximation Algorithm for Max-min Fair Allocation of
indivisible good, with A. Saberi. [PDF]
The max-min fair allocation is the problem of how to distribute a number of
indivisible goods between people so that the least happy person becomes as
happy as possible, i.e. the minimum utility among the people is maximized. In
this work we provided the first non-trivial approximation algorithm for this
problem based on rounding the solution of an exponential size Configuration
LP. As a part of our work, we developed a method for rounding fractional
matchings on trees via Bayesian updates, which later provided the first
foundations of our Maximum Entropy Rounding scheme.
A preliminary version of this paper is appeared in the 39th ACM
Symposium on Theory of Computing [STOC], 2007. The more detailed manuscript
will appear in SIAM Journal of Computing [SICOMP].
4.
On the Inefficiency
Ratio of Stable Equilibria in Congestion Games, with A. Saberi. [PDF]
Price of anarchy and price of stability are the primary notions for measuring
the efficiency or social welfare of the outcome of a game. Both of these
notions focus on extreme cases: one is defined as the inefficiency ratio of
the worst-case equilibrium and the other as the best one. Therefore, studying
both these notions often results in discovering equilibria that are not
necessarily the most likely outcomes of the dynamics of selfish and
non-coordinating agents.
The current paper studies the inefficiency of the equilibria that are most
stable in the presence of noise. In particular, we study two variations of
non-cooperative games: atomic congestion games and selfish load balancing.
The noisy best-response dynamics in these games keeps the joint action
profile around a particular set of equilibria that minimize the potential
function. The inefficiency ratio
in the neighborhood of these “stable” equilibria is much better than the
price of anarchy. Furthermore, the dynamics reaches these equilibria in polynomial
time.
These observations show that in games in which a small noise is expected, the
system as a whole works better than what a pessimist may predict. It also
suggests that in congestion games, introducing a small noise in the payoff of
the agents may improve the social welfare.
A preliminary version of
this paper is appeared in the 5th
Workshop on Internet and Network Economics [WINE], 2009.
5.
Santa Claus Meets
Hypergraph Matchings, with U. Feige and A.
Saberi. [PDF]
Santa Claus problem is a restricted case of the max-min fair allocation,
where each item has some universal value that is the same for everybody who
is interested in it. We show how this problem is related to the problem of
finding perfect matchings in the (bipartite) hypergraphs. Then, we provide a
generalization of Hungarian method to the hypergraphs in order to find such
perfect matching. Our approach gives a local search, which eventually finds a
4-approximate solution for this problem. Although, we still do not know if
the local search converges in polynomial time.
A preliminary version of
this paper (with approximation factor 5) is appeared in the 12th
Workshop on Approximation Algorithms for Combinatorial Optimization Problems
[APPROX], 2008.
6.
Approximate Pure
Equilibria in Cut Games, with T. Feder and A.
Saberi. [PDF]
A cut game is defined on a weighted graph where each player controls one of
the vertices. Each agent can adopt one of the k possible strategies. The
payoff of an agent controlling a vertex u is defined to be the total sum of
the weights of the edges (u, v) so that v is taking a strategy different from
u. We study different variations of this problem (namely, symmetric cut
games, asymmetric cut games, and love-hate games) and provide various
approximation algorithms and hardness results for finding pure Nash
equilibriums in such games.
submitted.
7.
Maximum Entropy
Sampling: a Randomized Rounding Scheme, with A. Saberi.
We present a new randomized rounding method based on maximum entropy
sampling. For a wide variety of combinatorial optimization problems, one can
find an optimal fractional solution by relaxing the problem into the
fractional domain and solve the corresponding mathematical program (LP, CP,
SDP, etc). However, usually one needs an integral solution for such problems.
Hence, a final step is needed which is to round this fractional solution to
an integral one. Our idea is to sample an integral instance from a
distribution that maximizes the entropy with respect to the marginal
probabilities given by the original fractional solution. The main advantage
of this rounding scheme is that it preserves any negative correlation in the
combinatorial structure of the problem (i.e. if there exists negative
correlation in the uniform sampling of this combinatorial structure, there
will be negative correlation in the maximum entropy sampling too). This
negative correlation allows us to use all the concentration bounds in the
independent randomized rounding and hence, provide a powerful tool of
rounding.
The combinatorial structures that satisfy such property include (but are not
limited to) balanced matroids (a family of matroids, including partition
graphical matroids, matroid, uniform matroids, etc), and matchings.
In a series of previous works, we showed how this method is useful to find
approximate solutions of the fair allocation
problem and the asymmetric traveling salesman
problem. We will also show here how one can solve a broad range of assignment
problems using maximum entropy sampling on matchings.
manuscript.
8.
What are the Limits of
Market Scoring Rules?, with S. Oveis Gharan and
A. Saberi.
In designing prediction markets, one of the most critical concerns is to
ensure that there will be no (or very small) arbitrage, no matter what the
betting sequence is. In this work, we find a necessary and sufficient
condition for the market pricing functions that guarantees a
"low"-arbitrage prediction market. We show that the growth rate of
the pricing function is the determinant factor in emerging any arbitrage in
the market. Our result implies that the growth rate of the pricing function
with respect to the fair portion of each asset must be super-polynomial in
order to have a low enough arbitrage (see the theorems for a more detailed
description).
We also find a sufficient condition for the pricing functions so that the
prices can be efficiently (i.e. in polynomial time) computed. This will put
an upperbound on the growth rate of the pricing functions in an efficiently
computable prediction market.
By combining these two results, one can find a class of pricing functions
that lead to low-arbitrage and efficient prediction markets.
manuscript.
9.
Two-dimensional
(Frictional) Matching Markets: Equilibrium, Homophily and Mixing, with D. Acemoglu, C.
Borgs, J. Chayes, and A. Saberi.
Consider a heterogeneous matching market in which the payoff of each individual
is determined by a given function of her own type and her partner's type. It
has been shown that under weak assumptions, such markets lead to equilibrium
with complete homophily (Becker
1973, Coles and Burdett 1997, Smith 2006). In particular, it has been shown
that in the frictionless instances of such markets each individual only
matches with her own type. Moreover, in the frictional matching markets we
will observe block segregation. In other words, the type spectrum will be
partitioned into groups (block) and in the equilibrium each individual will
only match with the people of her own group.
We show that the block segregation phenomenon is in fact a consequence of our
assumption that the types are one-dimensional. We investigate such markets in
a more natural setting where the individual types have multiple dimensions
(in our model, two). Moreover, there are different groups of individuals,
each of which interested in one of the dimensions of their partner's type. In
other words, their payoff is a given function of their own type and the
corresponding dimension of their partner's type.
We characterize the equilibrium in such markets (in both frictional and
frictionless instances) and show that a combination of homophily and mixing
appears in the equilibrium. We also do a comparative study to understand the
effect of small changes in population on the emerging equilibrium. Our
results establish a framework to study the effect of dimensionality of
preferences in matching markets on the outcome of such markets.
work in progress.
|