Shahar Dobzinski

STOC Conference 2024 Conference Paper

A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations

• Shahar Dobzinski
• Wenzheng Li
• Aviad Rubinstein
• Jan Vondrák

We present a constant-factor approximation algorithm for the Nash Social Welfare (NSW) maximization problem with subadditive valuations accessible via demand queries. More generally, we propose a framework for NSW optimization which assumes two subroutines which (1) solve a configuration-type LP under certain additional conditions, and (2) round the fractional solution with respect to utilitarian social welfare. In particular, a constant-factor approximation for submodular valuations with value queries can also be derived from our framework.

STOC Conference 2024 Conference Paper

Bilateral Trade with Correlated Values

• Shahar Dobzinski
• Ariel Shaulker

STOC Conference 2022 Conference Paper

On the hardness of dominant strategy mechanism design

• Shahar Dobzinski
• Shiri Ron
• Jan Vondrák

We study the communication complexity of dominant strategy implementations of combinatorial auctions. We start with two domains that are generally considered “easy”: multi-unit auctions with decreasing marginal values and combinatorial auctions with gross substitutes valuations. For both domains we have fast algorithms that find the welfare-maximizing allocation with communication complexity that is poly-logarithmic in the input size. This immediately implies that welfare maximization can be achieved in ex-post equilibrium with no significant communication cost, by using VCG payments. In contrast, we show that in both domains the communication complexity of any dominant strategy implementation that achieves the optimal welfare is polynomial in the input size. We then move on to studying the approximation ratios achievable by dominant strategy mechanisms. For multi-unit auctions with decreasing marginal values, we provide a dominant-strategy communication FPTAS. For combinatorial auctions with general valuations, we show that there is no dominant strategy mechanism that achieves an approximation ratio better than m 1−є that uses poly ( m , n ) bits of communication, where m is the number of items and n is the number of bidders. In contrast, a randomized dominant strategy mechanism that achieves an O (√ m ) approximation with poly ( m , n ) communication is known. This proves the first gap between computationally efficient deterministic dominant strategy mechanisms and randomized ones. En route, we answer an open question on the communication cost of implementing dominant strategy mechanisms for more than two players, and also solve some open problems in the area of simultaneous combinatorial auctions.

STOC Conference 2021 Conference Paper

The communication complexity of payment computation

• Shahar Dobzinski
• Shiri Ron

Let ( f , P ) be an incentive compatible mechanism where f is the social choice function and P is the payment function. In many important settings, f uniquely determines P (up to a constant) and therefore a common approach is to focus on the design of f and neglect the role of the payment function. Fadel and Segal [JET, 2009] question this approach by taking the lenses of communication complexity: can it be that the communication complexity of an incentive compatible mechanism that implements f (that is, computes both the output and the payments) is much larger than the communication complexity of computing the output? I.e., can it be that cc IC ( f )>> cc ( f )? Fadel and Segal show that for every f , cc IC ( f )≤ exp ( cc ( f )). They also show that fully computing the incentive compatible mechanism is strictly harder than computing only the output: there exists a social choice function f such that cc IC ( f )= cc ( f )+1. In a follow-up work, Babaioff, Blumrosen, Naor, and Schapira [EC’08] provide a social choice function f such that cc IC ( f )=Θ( n · cc ( f )), where n is the number of players. The question of whether the exponential upper bound of Fadel and Segal is tight remained wide open. In this paper we solve this question by explicitly providing a function f such that cc IC ( f )= exp ( cc ( f )). In fact, we establish this via two very different proofs. In contrast, we show that if the players are risk-neutral and we can compromise on a randomized truthful-in-expectation implementation (and not on deterministic ex-post implementation) gives that cc TIE ( f )= poly ( n , cc ( f )) for every function f , as long as the domain of f is single parameter or a convex multi-parameter domain. We also provide efficient algorithms for deterministic computation of payments in several important domains.

STOC Conference 2019 Conference Paper

The communication complexity of local search

• Yakov Babichenko
• Shahar Dobzinski
• Noam Nisan

We study a communication variant of local search. There is some fixed, commonly known graph G . Alice holds f A and Bob holds f B , both are functions that specify a value for each vertex. The goal is to find a local maximum of f A + f B with respect to G , i.e., a vertex v for which ( f A + f B )( v )≥ ( f A + f B )( u ) for each neighbor u of v .

IJCAI Conference 2018 Conference Paper

Combinatorial Cost Sharing

• Shahar Dobzinski
• Shahar Ovadia

We introduce a combinatorial variant of the cost sharing problem: several services can be provided to each player and each player values every combination of services differently. A publicly known cost function specifies the cost of providing every possible combination of services. A combinatorial cost sharing mechanism is a protocol that decides which services each player gets and at what price. We look for dominant strategy mechanisms that are (economically) efficient and cover the cost, ideally without overcharging (i. e. , budget balanced). Note that unlike the standard cost sharing setting, combinatorial cost sharing is a multi-parameter domain. This makes designing dominant strategy mechanisms with good guarantees a challenging task. We present the Potential Mechanism -- a combination of the VCG mechanism and a well-known tool from the theory of cooperative games: Hart and Mas-Colell's potential function. The potential mechanism is a dominant strategy mechanism that always covers the incurred cost. When the cost function is subadditive the same mechanism is also approximately efficient. Our main technical contribution shows that when the cost function is submodular the potential mechanism is approximately budget balanced in three settings: supermodular valuations, symmetric cost function and general symmetric valuations, and two players with general valuations.

STOC Conference 2016 Conference Paper

Breaking the logarithmic barrier for truthful combinatorial auctions with submodular bidders

• Shahar Dobzinski

We study a central problem in Algorithmic Mechanism Design: constructing truthful mechanisms for welfare maximization in combinatorial auctions with submodular bidders. Dobzinski, Nisan, and Schapira provided the first mechanism that guarantees a non-trivial approximation ratio of O(log^2 m) [STOC'06], where m is the number of items. This was subsequently improved to O( log m log log m) [Dobzinski, APPROX'07] and then to O(m) [Krysta and Vocking, ICALP'12]. In this paper we develop the first mechanism that breaks the logarithmic barrier. Specifically, the mechanism provides an approximation ratio of O( m). Similarly to previous constructions, our mechanism uses polynomially many value and demand queries, and in fact provides the same approximation ratio for the larger class of XOS (a.k.a. fractionally subadditive) valuations. We also develop a computationally efficient implementation of the mechanism for combinatorial auctions with budget additive bidders. Although in general computing a demand query is NP-hard for budget additive valuations, we observe that the specific form of demand queries that our mechanism uses can be efficiently computed when bidders are budget additive.

FOCS Conference 2016 Conference Paper

Computational Efficiency Requires Simple Taxation

• Shahar Dobzinski

We characterize the communication complexity of truthful mechanisms. Our departure point is the well known taxation principle. The taxation principle asserts that every truthful mechanism can be interpreted as follows: every player is presented with a menu that consists of a price for each bundle (the prices depend only on the valuations of the other players). Each player is allocated a bundle that maximizes his profit according to this menu. We define the taxation complexity of a truthful mechanism to be the logarithm of the maximum number of menus that may be presented to a player. Our main finding is that in general the taxation complexity essentially equals the communication complexity. The proof consists of two main steps. First, we prove that for rich enough domains the taxation complexity is at most the communication complexity. We then show that the taxation complexity is much smaller than the communication complexity only in "pathological" cases and provide a formal description of these extreme cases. Next, we study mechanisms that access the valuations via value queries only. In this setting we establish that the menu complexity - a notion that was already studied in several different contexts - characterizes the number of value queries that the mechanism makes in exactly the same way that the taxation complexity characterizes the communication complexity. Our approach yields several applications, including strengthening the solution concept with low communication overhead, fast computation of prices, and hardness of approximation by computationally efficient truthful mechanisms.

SODA Conference 2015 Conference Paper

On the Complexity of Computing an Equilibrium in Combinatorial Auctions

• Shahar Dobzinski
• Hu Fu 0001
• Robert Kleinberg

We study combinatorial auctions where each item is sold separately but simultaneously via a second price auction. We ask whether it is possible to efficiently compute in this game a pure Nash equilibrium with social welfare close to the optimal one. We show that when the valuations of the bidders are submodular, in many interesting settings (e. g. , constant number of bidders, budget additive bidders) computing an equilibrium with good welfare is essentially as easy as computing, completely ignoring incentives issues, an allocation with good welfare. On the other hand, for subadditive valuations, we show that computing an equilibrium requires exponential communication. Finally, for XOS (a. k. a. fractionally subadditive) valuations, we show that if there exists an efficient algorithm that finds an equilibrium, it must use techniques that are very different from the ones currently known.

STOC Conference 2014 Conference Paper

Economic efficiency requires interaction

• Shahar Dobzinski
• Noam Nisan
• Sigal Oren

SODA Conference 2013 Conference Paper

Communication Complexity of Combinatorial Auctions with Submodular Valuations

• Shahar Dobzinski
• Jan Vondrák

We prove the first communication complexity lower bound for constant-factor approximation of the submodular welfare problem. More precisely, we show that a -approximation (≃ 0. 816) for welfare maximization in combinatorial auctions with submodular valuations would require exponential communication. We also show NP-hardness of -approximation in a computational model where each valuation is given explicitly by a table of constant size. Both results rule out better than (1 − )-approximations in every oracle model with a separate oracle for each player, such as the demand oracle model. Our main tool is a new construction of monotone submodular functions that we call multi-peak submodular functions. Roughly speaking, given a family of sets, we construct a monotone submodular function f with a high value f ( S ) for every set S ∊ (a “peak”), and a low value on every set that does not intersect significantly any set in. We also study two other related problems: max-min allocation (for which we also get hardness of -approximation, in both models), and combinatorial public projects (for which we prove hardness of -approximation in the communication model, and hardness of -approximation in the computational model, using constant size valuations).

STOC Conference 2012 Conference Paper

From query complexity to computational complexity

• Shahar Dobzinski
• Jan Vondrák

We consider submodular optimization problems, and provide a general way of translating oracle inapproximability results arising from the symmetry gap technique to computational complexity inapproximability results, where the submodular function is given explicitly (under the assumption that NP ≠ RP). Applications of our technique include an optimal computational hardness of (1/2 + ε)-approximation for maximizing a symmetric nonnegative submodular function, an optimal hardness of (1-(1-1/k) k + ε)-approximation for welfare maximization in combinatorial auctions with k submodular bidders (for constant k), super-constant hardness for maximizing a nonnegative submodular function over matroid bases, and tighter bounds for maximizing a monotone submodular function subject to a cardinality constraint. Unlike the vast majority of computational inapproximability results, our approach does not use the PCP machinery or the Unique Games Conjecture, but relies instead on a direct reduction from Unique-SAT using list-decodable codes.

SODA Conference 2012 Conference Paper

Sketching valuation functions

• Ashwinkumar Badanidiyuru
• Shahar Dobzinski
• Hu Fu 0001
• Robert Kleinberg
• Noam Nisan
• Tim Roughgarden

Motivated by the problem of querying and communicating bidders' valuations in combinatorial auctions, we study how well different classes of set functions can be sketched. More formally let f be a function mapping subsets of some ground set [ n ] to the non-negative real numbers. We say that f′ is an α-sketch of f if for every set S, the value f′ ( S ) lies between f ( S )/α and f ( S ), and f′ can be specified by poly( n ) bits. We show that for every subadditive function f there exists an α-sketch where α = n 1/2 · O (polylog( n )). Furthermore, we provide an algorithm that finds these sketches with a polynomial number of demand queries. This is essentially the best we can hope for since: 1. We show that there exist subadditive functions (in fact, XOS functions) that do not admit an o ( n 1/2 ) sketch. (Balcan and Harvey [3] previously showed that there exist functions belonging to the class of substitutes valuations that do not admit an O ( n 1/3 ) sketch.) 2. We prove that every deterministic algorithm that accesses the function via value queries only cannot guarantee a sketching ratio better than n 1−ε. We also show that coverage functions, an interesting subclass of submodular functions, admit arbitrarily good sketches. Finally, we show an interesting connection between sketching and learning. We show that for every class of valuations, if the class admits an α-sketch, then it can be α-approximately learned in the PMAC model of Balcan and Harvey. The bounds we prove are only information-theoretic and do not imply the existence of computationally efficient learning algorithms in general.

STOC Conference 2011 Conference Paper

An impossibility result for truthful combinatorial auctions with submodular valuations

• Shahar Dobzinski

We show that every universally truthful randomized mechanism for combinatorial auctions with submodular valuations that provides an approximation ratio of m 1/ 2 -ε must use exponentially many value queries, where m is the number of items. In contrast, ignoring incentives there exist constant ratio approximation algorithms for this problem. Our approach is based on a novel direct hardness technique that completely skips the notoriously hard step of characterizing truthful mechanisms. The characterization step was the main obstacle for proving impossibility results in algorithmic mechanism design so far. We demonstrate two additional applications of our new technique: (1) an impossibility result for universally-truthful polynomial time flexible combinatorial public projects and (2) an impossibility result for truthful-in-expectation mechanisms for exact combinatorial public projects. The latter is the first result that bounds the power of polynomial-time truthful in expectation mechanisms in any setting.

STOC Conference 2011 Conference Paper

Optimal auctions with correlated bidders are easy

• Shahar Dobzinski
• Hu Fu 0001
• Robert Kleinberg

We consider the problem of designing a revenue-maximizing auction for a single item, when the values of the bidders are drawn from a correlated distribution. We observe that there exists an algorithm that finds the optimal randomized mechanism that runs in time polynomial in the size of the support. We leverage this result to show that in the oracle model introduced by Ronen and Saberi [FOCS'02], there exists a polynomial time truthful in expectation mechanism that provides a (1.5+ε)-approximation to the revenue achievable by an optimal truthful-in-expectation mechanism, and a polynomial time deterministic truthful mechanism that guarantees 5/3 approximation to the revenue achievable by an optimal deterministic truthful mechanism. We show that the 5/3-approximation mechanism provides the same approximation ratio also with respect to the optimal truthful-in-expectation mechanism. This shows that the performance gap between truthful-in-expectation and deterministic mechanisms is relatively small. En route, we solve an open question of Mehta and Vazirani [EC'04]. Finally, we extend some of our results to the multi-item case, and show how to compute the optimal truthful-in-expectation mechanisms for bidders with more complex valuations.

FOCS Conference 2009 Conference Paper

On the Power of Randomization in Algorithmic Mechanism Design

• Shahar Dobzinski
• Shaddin Dughmi

In many settings the power of truthful mechanisms is severely bounded. In this paper we use randomization to overcome this problem. In particular, we construct an FPTAS for multi-unit auctions that is truthful in expectation, whereas there is evidence that no polynomial-time truthful deterministic mechanism provides an approximation ratio better than 2. We also show for the first time that truthful in expectation polynomial-time mechanisms are provably stronger than polynomial-time universally truthful mechanisms. Specifically, we show that there is a setting in which: (1) there is a non-polynomial time truthful mechanism that always outputs the optimal solution, and that (2) no universally truthful randomized mechanism can provide an approximation ratio better than 2 in polynomial time, but (3) an FPTAS that is truthful in expectation exists.

FOCS Conference 2008 Conference Paper

Multi-unit Auctions with Budget Limits

• Shahar Dobzinski
• Ron Lavi
• Noam Nisan

We study multi-unit auctions where the bidders have a budget constraint, a situation very common in practice that has received very little attention in the auction theory literature. Our main result is an impossibility: there are no incentive-compatible auctions that always produce a Pareto-optimal allocation. We also obtain some surprising positive results for certain special cases.

FOCS Conference 2008 Conference Paper

Truthful Approximation Schemes for Single-Parameter Agents

• Peerapong Dhangwatnotai
• Shahar Dobzinski
• Shaddin Dughmi
• Tim Roughgarden

We present the first monotone randomized polynomial-time approximation scheme (PTAS) for minimizing the makespan of parallel related machines (Q||C max ), the paradigmatic problem in single-parameter algorithmic mechanism design. This result immediately gives a polynomial-time, truthful (in expectation) mechanism whose approximation guarantee attains the best-possible one for all polynomial-time algorithms (assuming P not equal to NP). Our algorithmic techniques are flexible and also yield, among other results, a monotone deterministic quasi-PTAS for Q||C max and a monotone randomized PTAS for max-min scheduling on related machines.

STOC Conference 2007 Conference Paper

Limitations of VCG-based mechanisms

• Shahar Dobzinski
• Noam Nisan

We consider computationally-efficient incentive-compatiblemechanisms that use the VCG payment scheme, and study how well theycan approximate the social welfare in auction settings. We present anovel technique for setting lower bounds on the approximation ratioof this type of mechanisms. Specifically, for combinatorial auctionsamong submodular (and thus also subadditive) bidders we prove an Ω(m 1/6 ) lower bound, which is close to the knownupper bound of O(m 1/2 ), and qualitatively higher than theconstant factor approximation possible from a purely computationalpoint of view.

SODA Conference 2006 Conference Paper

An improved approximation algorithm for combinatorial auctions with submodular bidders

• Shahar Dobzinski
• Michael Schapira

STOC Conference 2006 Conference Paper

Truthful randomized mechanisms for combinatorial auctions

• Shahar Dobzinski
• Noam Nisan
• Michael Schapira

We design two computationally-efficient incentive-compatible mechanisms for combinatorial auctions with general bidder preferences. Both mechanisms are randomized, and are incentive-compatible 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.

STOC Conference 2005 Conference Paper

Approximation algorithms for combinatorial auctions with complement-free bidders

• Shahar Dobzinski
• Noam Nisan
• Michael Schapira

We exhibit three approximation algorithms for the allocation problem in combinatorial auctions with complement free bidders. The running time of these algorithms is polynomial in the number of items $m$ and in the number of bidders n, even though the "input size" is exponential in m. The first algorithm provides an O(log m) approximation. The second algorithm provides an O(√ m) approximation in the weaker model of value oracles. This algorithm is also incentive compatible. The third algorithm provides an improved 2-approximation for the more restricted case of " XOS bidders", a class which strictly contains submodular bidders. We also prove lower bounds on the possible approximations achievable for these classes of bidders. These bounds are not tight and we leave the gaps as open problems.