Working Papers
Auctions with Budget-Constrained Bidders, joint with I. Hafalir and R. Ravi [pdf]
We study single item multi-unit auctions where bidders have budget constraints. An impossibility result by Dobzinski et al. precludes the existence of a truthful mechanism with Pareto-optimal allocations in this important setting. We propose Sort-Cut, a mechanism which does the next best thing from the auctioneer's point of view, that we term semi-truthful. In our mechanism, it is a weakly dominant strategy for all agents to state their true budgets and to not understate their values. Thus the only way a bidder can possibly benefit from lying in a semi-truthful mechanism is by overstating their value, which leads to good revenue properties for the auctioneer at equilibria. We formalize the revenue results by showing that any equilibrium of Sort-Cut extracts a large portion of the revenue of a non-discriminatory monopoly that knows all the budgets and values of the players, and has to determine a single unit-price at which the item will be sold. Finally, we extend our results from the setting of hard budget constraints to one where the marginal disutility of spending the next dollar increases with the payment.
Part of our results appeared in the Fifth Workshop on Ad Auctions, AAW '09.
Expressive Auctions for Externalities in Online Advertising, joint with A. Ghosh [pdf]
When online ads are shown together, they compete for user attention and conversions, imposing negative externalities on each other. While the competition for user attention in sponsored search can be captured via models of clickthrough rates, the post-click competition for conversions cannot: since the value-per-click of an advertiser is proportional to the conversion probability conditional on a click, which depends on the other ads displayed, the private value of an advertiser is no longer one-dimensional, and the GSP mechanism is not adequately expressive. We study the design of expressive GSP-like mechanisms for the simplest form that an advertiser's private value can have in the presence of such externalities--- an advertiser's value depends on exclusivity, i.e., whether her ad is shown exclusively, or along with other ads.
Part of our results appeared in the Fifth Workshop on Ad Auctions, AAW '09.
Publications
Mechanism Design for Complexity-constrained Bidders, joint with R. Kumar and M. Mahdian [pdf]
A well-known result due to Vickery gives a mechanism for selling a number of goods to interested buyers in a way that achieves the maximum social welfare. In practice, a problem with this mechanism is that it requires the buyers to specify a large number of values. In this paper we study the problem of designing optimal mechanisms subject to constraints on the complexity of the bidding language in a setting where buyers have additive valuations for a large set of goods. This setting is motivated by sponsored search auctions, where the valuations of the advertisers are more or less additive, and the number of keywords that are up for sale is huge. We give a complete solution for this problem when the valuations of the buyers are drawn from simple classes of prior distributions. For a more realistic class of priors, we show that a mechanism akin to the broad match mechanism currently in use provides a reasonable bicriteria approximation.
To appear in the Fifth Workshop on Internet and Network Economics, WINE '09.
Minimizing Movement, joint with E. Demaine, M. Hajiaghayi, H. Mahini, S. Oveisgharan and M. Zadimoghaddam
Journal Version [pdf] Conference Version [pdf]
We give approximation algorithms and inapproximability results for a class of movement problems. In general, these problems involve planning the coordinated motion of a large collection of objects (representing anything from a robot swarm or firefighter team to map labels or network messages) to achieve a global property of the network while minimizing the maximum or average movement. In particular, we consider the goals of achieving connectivity (undirected and directed), achieving connectivity between a given pair of vertices, achieving independence (a dispersion problem), and achieving a perfect matching (with applications to multicasting). This general family of movement problems encompass an intriguing range of graph and geometric algorithms, with several real-world applications and a surprising range of approximability. In some cases, we obtain tight approximation and inapproximability results using direct techniques (without use of PCP), assuming just that P != NP.
Journal version appeared in ACM Transactions on Algorithms ACM TALG 5(3) 2009.
Conference version appeared in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '07 .
Scheduling to Minimize Gaps and Power Consumption, joint with E. Demaine, M. Ghodsi, M. Hajiaghayi and M. Zadimoghaddam [pdf]
This paper considers scheduling tasks while minimizing the power consumption of one or more processors, each of which can go to sleep at a fixed cost alpha. There are two natural versions of this problem, both considered extensively in recent work: minimize the total power consumption (including computation time), or minimize the number of "gaps" in execution. For both versions in a multiprocessor system, we develop a polynomial-time algorithm based on sophisticated dynamic programming. In a generalization of the power-saving problem, where each task can execute in any of a specified set of time intervals, we develop a (1 + (2/3)alpha)-approximation, and show that dependence on alpha is necessary. In contrast, the analogous multi-interval gap scheduling problem is set-cover hard (and thus not o(lg n)-approximable), even in the special cases of just two intervals per job or just three unit intervals per job. We also prove several other hardness-of-approximation results. Finally, we give an O(sqrt(n))-approximation for maximizing throughput given a hard upper bound on the number of gaps.
Appeared in Proceedings of 19th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '07 .
Spanning Trees with Minimum Weighted Degrees, joint with M. Ghodsi, H. Mahini, K. Mirjalali, S. Oveisgharan and M. Zadimoghaddam [pdf]
Given a metric graph G, we are concerned with finding a spanning tree of G where the maximum weighted degree of its vertices is minimum. In a metric graph (or its spanning tree), the weighted degree of a vertex is defined as the sum of the weights of its incident edges. In this paper, we propose a 4.5-approximation algorithm for this problem. We also prove it is NP-hard to approximate this problem within a 2-epsilon factor.
Appeared in Information Processing Letters, IPL 104(3) 2007.