My research interest lies in the intersection of theoretical computer
science, game theory, economics and mathematical sociology. In particular, I am
interested in optimization, auction and mechanism design, algorithmic game
theory and social networks.
- Frugal Mechanism Design:
David Kempe, Mahyar Salek and Cristopher Moore:
Frugal and Truthful Auctions for Vertex Covers, Flows, and Cuts.
Proceedings of FOCS 2010, Las Vegas, USA.
- We study truthful mechanisms for hiring a team of agents in three classes of set systems: Vertex Cover auctions, k-flow auctions, and cut auctions. We present constant-competitive truthful mechanisms for all three set systems. That is, the maximum overpayment of the mechanism is within a constant factor of the maximum overpayment of any truthful mechanism, for every set system in the class. The mechanism for Vertex Cover is based on scaling each bid by a multiplier derived from the dominant eigenvector of a certain matrix. The mechanism for k-flows prunes the graph to be minimally (k+1)-connected, and then applies the Vertex Cover mechanism. Similarly, the mechanism for cuts contracts the graph until all s-t paths have length exactly 2 via primal-dual approaches, and then applies the Vertex Cover mechanism.
Atsushi Iwasaki, David Kempe, Yasumasa Saito, Mahyar Salek, Makoto Yokoo:
False-name-proof mechanisms for hiring a team. In
Proceedings of WINE 2007, San Diego, CA.
- We study false-name proof auctions in which an auctioneer is trying
to hire a team of elements owned by individually paid agents. The goal
is to design incentive-compatible mechanisms which will make agents
reveal both ownership of elements and true costs, while minimizing
total payments. We formally present two natural models. For one, we
give an O(n2n) competitive mechanisms, and prove a lower bound of
Ω(2n). For the second, we present a mechanism with a reserve
price, which does not always purchase a solution.
- Externalities in Auctions:
Mahyar Salek and David Kempe:
Auctions for Share-averse Bidders. In
Proceedings of WINE 2008, Shanghai, China.
- We study auctions in which the item(s) being auctioned can be shared among multiple winners, but the valuation of winners decreases as more and more others share with them. We derive the optimal truthful auction for a single item in the sense of Meyerson, and observe several properties depending on the rate at which utility decreases. We also examine share-averse combinatorial auctions with single-minded bidders, prove sufficient conditions for incentive compatibility, and give an essentially tight approximation algorithm.
With Saeed Alaei, Janina Brenner, and Guido Shaefer: Mechanism Design with Congestion Externalities
In Preparation.
- We study mechanisms for resource allocation problems subject to congestion.
To do this, we adopt a standard model used in the field of congestion games.
First, we develop a natural model for players' utility functions in the presence of congestion. Then, we design a generic truthful mechanism that approximates social welfare.
Our approach is based on reducing the problem to singleton strategy instances using hyper-graph duality.
- Influence in Social Networks:
Mahyar Salek, Shahin Shayandeh and David Kempe:
You Share, I Share: Network Effects and Economic Incentives in P2P File-Sharing Systems.
Proceedings of WINE 2010, Shanghai, China.
- We study the interaction between network effects and
external incentives on file sharing behavior in Peer-to-Peer (P2P)
networks. We formulate a natural model for the network effects of
sharing behavior and prove that the model has desirable
concavity properties, meaning that the network benefit of
increasing payments decreases when the payments are
already high.
Shishir Bharathi, David Kempe, Mahyar Salek:
Competitive Influence Maximization in Social Networks. In Proceedings of
WINE 2007, San Diego, CA.
- We study viral marketing in a scenario of multiple competing
companies. We give a 1-1/e approximation for the last mover, prove a
price of anarchy of 2, give first-mover algorithms for some very
restricted graph structure, and present an FPTAS for the one-company
version on bidirected trees.
With Yashodhan Kanoria, Hamid Nazerzadeh and Renatp Paes Leme:
Social Targetting via Ising Model. In Preparation.
- We study the problem of social targetting by correlating individuals' interests via Ising model and prove near optimal algorithms.
- Misc:
David Kempe, Ahuva Mu'Alem and Mahyar Salek:
Envy Free Allocations for Budgeted Bidders. In
Proceedings of WINE 2009, Rome, Italy.
- We study the problem of allocating items to bidders who are not only constrained by their valuations for items, but also by their budgets, i.e., ability to pay. We present efficient algorithms for finding maximal and minimal price vectors supporting a given allocation, and also show a structural condition guaranteeing minimal price vectors for different allocations to be the same.
With Vincenzo Bonifaci and Guido Schaefer:
Efficiency of Restricted Tolls in Non-Atomic Network Routing Games.
In Proceeding of SAGT 2011.
- In this paper, we study the restricted network toll problem in which tolls can be
imposed on the arcs of the network but are restricted to not exceed a predefined
threshold for every arc. We show that optimal restricted tolls can be computed
efficiently for parallel-arc networks and affine latency functions. This generalizes
a previous work on taxing subnetworks to arbitrary restrictions. Our algorithm
is quite simple, but relies on solving several convex programs. The key to our
approach is a characterization of the flows that are inducible by restricted tolls
for single-commodity networks. We also derive bounds on the efficiency of restricted
tolls for multi-commodity networks and polynomial latency functions.
These bounds are tight even for parallel-arc networks. Our bounds show that
restricted tolls can significantly reduce the price of anarchy if the restrictions
imposed on arcs with high-degree polynomials are not too severe.
Undergraduate Thesis (in Persian) : Web
Communities and Algorithms, Under supervision of Professor
Mohammad Ghodsi, Computer Engineering
Department, Sharif University of Technology.
- We study and compare several approaches for indentifying communities on the web-graph both from theoretical and experimental viewpoints.
About me
The University of Southern California does not screen or control the content on this website and thus does not guarantee the accuracy, integrity, or quality of such content. All content on this website is provided by and is the sole responsibility of the person from which such content originated, and such content does not necessarily reflect the opinions of the University administration or the Board of Trustees