My name is Mahyar Salek. I am a PhD candidate at University of Southern California, department of Computer Science. I completed my undergraduate degree in computer engineering from Sharif University of Technology in Tehran, Iran.

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.

My advisor is Professor David Kempe.

Internships:

• Algorithmic Game Theory Group, Centrum Wiskunde & Informatica. Summer 2009.
• Microsoft Research, New England. Summer 2010

Contact info:

Email : salek AT usc DOT edu

Voice :  310 597 9328

CV

• 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(n2ⁿ) competitive mechanisms, and prove a lower bound of Ω(2ⁿ). 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