Algorithms for Strategic Agents (2025)

Hard-to-Manipulate Combinatorial Auctions

2010

Mechanism design provides a framework to solve distributed optimization problems in systems of self-interested agents. The combinatorial auction is one such problem, in which there is a set of discrete items to allocate to agents. Unfortunately, recent results suggest that it is impossible to implement reasonable approximations without losing robustness to manipulation. Furthermore, the Vickrey-Clarke-Groves (VCG) mechanism is known to be vulnerable to manipulation when agents can bid under multiple false names. In this paper we relax incentive constraints and require only that useful manipulation be NP-hard. We prove that any tractable approximation algorithm can be made to produce a hard-to-manipulate (VCG-based) mechanism, providing a useful counterpoint to these negative results. We also show that falsename bid manipulation in the VCG is NP-hard.Engineering and Applied Science

The Complexity of Optimal Mechanism Design

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Myerson's seminal work provides a computationally efficient revenue-optimal auction for selling one item to multiple bidders [18]. Generalizing this work to selling multiple items at once has been a central question in economics and algorithmic game theory, but its complexity has remained poorly understood. We answer this question by showing that a revenue-optimal auction in multi-item settings cannot be found and implemented computationally efficiently, unless ZPP ⊇ P #P. This is true even for a single additive bidder whose values for the items are independently distributed on two rational numbers with rational probabilities. Our result is very general: we show that it is hard to compute any encoding of an optimal auction of any format (direct or indirect, truthful or non-truthful) that can be implemented in expected polynomial time. In particular, under well-believed complexity-theoretic assumptions, revenue-optimization in very simple multi-item settings can only be tractably approximated. We note that our hardness result applies to randomized mechanisms in a very simple setting, and is not an artifact of introducing combinatorial structure to the problem by allowing correlation among item values, introducing combinatorial valuations, or requiring the mechanism to be deterministic (whose structure is readily combinatorial). Our proof is enabled by a flow-interpretation of the solutions of an exponential-size linear program for revenue maximization with an additional supermodularity constraint.

On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions

Lecture Notes in Computer Science, 2010

We study mechanisms for the combinatorial auction (CA) problem, in which m objects are sold to rational agents and the goal is to maximize social welfare. Of particular interest is the special case of s-CAs, where agents are interested in sets of size at most s, for which a simple greedy algorithm obtains an s + 1 approximation but no deterministic truthful mechanism is known to attain an approximation ratio better than O(m/ √ log m). We view this as an extreme gap not only between the power of greedy auctions and truthful greedy auctions, but also as an apparent gap between the known power of truthful and nontruthful deterministic algorithms. We associate the notion of greediness with a broad class of algorithms, known as priority algorithms, which encapsulates many natural auction methods. This motivates us to ask: how well can a truthful greedy algorithm approximate the optimal social welfare for CA problems? We show that no truthful greedy priority algorithm can obtain an approximation to the CA problem that is sublinear in m, even for s-CAs with s ≥ 2. We conclude that any truthful combinatorial auction mechanism with non-trivial approximation factor must fall outside the scope of many natural auction methods.

An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents

Internet Mathematics, 2004

Mechanism design seeks algorithms whose inputs are provided by selfish agents who would lie if it were to their advantage. Incentive-compatible mechanisms c o m p e lt h ea g e n t st ot e l lt h et r u t hb ym a k i n gi ti nt h e i rs e l f -i n t e r e s tt od os o . O ften, as in combinatorial auctions, such mechanisms involve the solution of NP-hard problems. Unfortunately, approximation algorithms typically destroy incentive compatibility. Randomized rounding is a commonly used technique for designing approximation algorithms. We devise a version of randomized rounding that is incentivecompatible, giving a truthful mechanism for combinatorial auctions with single parameter agents (e.g., "single minded bidders") that approximately maximizes the social value of the auction. We discuss two orthogonal notions of truthfulness for a randomized mechanism-truthfulness with high probability and in expectation-and give a mechanism that achieves both simultaneously.

On designing truthful mechanisms for online scheduling

Theoretical Computer Science, 2009

We study the online version of the scheduling problem involving selfish agents considered by Archer and Tardos [FOCS 2001]: jobs must be scheduled on m parallel related machines, each of them owned by a different selfish agent.

combinatorial auctions without money

Algorithmic Mechanism Design attempts to marry computation and incentives, mainly by leveraging monetary transfers between designer and selfish agents involved. This is principally because in absence of money, very little can be done to enforce truthfulness. However, in certain applications, money is unavailable, morally unacceptable or might simply be at odds with the objective of the mechanism. For example, in Combinatorial Auctions (CAs), the paradigmatic problem of the area, we aim at solutions of maximum social welfare, but still charge the society to ensure truthfulness. We focus on the design of incentive-compatible CAs without money in the general setting of k-minded bidders. We trade monetary transfers with the observation that the mechanism can detect certain lies of the bidders: i.e., we study truthful CAs with verification and without money. In this setting, we characterize the class of truthful mechanisms and give a host of upper and lower bounds on the approximation ratio obtained by either deterministic or randomized truthful mechanisms. Our results provide an almost complete picture of truthfully approximating CAs in this general setting with multi-dimensional bidders.

Truthful randomized mechanisms for combinatorial auctions

Journal of Computer and System Sciences, 2012

We design two computationally-efficient incentive-compatible mechanisms for combinatorial auctions with general bidder preferences. Both mechanisms are randomized, and are incentivecompatible in the universal sense. This is in contrast to recent previous work that only addresses the weaker notion of incentive compatibility in expectation. The first mechanism obtains an O( √ m)-approximation of the optimal social welfare for arbitrary bidder valuations -this is the best approximation possible in polynomial time. The second one obtains an O(log 2 m)approximation for a subclass of bidder valuations that includes all submodular bidders. This improves over the best previously obtained incentive-compatible mechanism for this class which only provides an O( √ m)-approximation.

Understanding Incentives: Mechanism Design Becomes Algorithm Design

2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 2013

We provide a computationally efficient black-box reduction from mechanism design to algorithm design in very general settings. Specifically, we give an approximation-preserving reduction from truthfully maximizing any objective under arbitrary feasibility constraints with arbitrary bidder types to (not necessarily truthfully) maximizing the same objective plus virtual welfare (under the same feasibility constraints). Our reduction is based on a fundamentally new approach: we describe a mechanism's behavior indirectly only in terms of the expected value it awards bidders for certain behavior, and never directly access the allocation rule at all. Applying our new approach to revenue, we exhibit settings where our reduction holds both ways. That is, we also provide an approximation-sensitive reduction from (non-truthfully) maximizing virtual welfare to (truthfully) maximizing revenue, and therefore the two problems are computationally equivalent. With this equivalence in hand, we show that both problems are NP-hard to approximate within any polynomial factor, even for a single monotone submodular bidder. We further demonstrate the applicability of our reduction by providing a truthful mechanism maximizing fractional max-min fairness. This is the first instance of a truthful mechanism that optimizes a non-linear objective.

Mechanism Design for Complexity-Constrained Bidders

Lecture Notes in Computer Science, 2009

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.

A Characterization of 2-Player Mechanisms for Scheduling

Algorithms-ESA 2008, 2008