Optimization with demand oracles

Authors

Ashwinkumar Badanidiyuru, Shahar Dobzinski, Sigal Oren

Type: Article

Publication Date: 2012-06-04

Citations: 17

DOI: https://doi.org/10.1145/2229012.2229025

Ask PDF

Abstract

We study combinatorial procurement auctions, where a buyer with a valuation function v and budget B wishes to buy a set of items. Each item i has a cost ci and the buyer is interested in a set S that maximizes v(S) subject to ∑i∈Sci ≤ β. Special cases of combinatorial procurement auctions are well-studied problems from submodular optimization. In particular, when the costs are all equal (cardinality constraint), a classic result by Nemhauser et al shows that the greedy algorithm provides an e/e-1 approximation.

Locations

arXiv (Cornell University)
View PDF

Ask a Question About This Paper

Summary

Optimization with Demand Oracles

2011-07-14

Ashwinkumar Badanidiyuru , Shahar Dobzinski , Sigal Oren

We study \emph{combinatorial procurement auctions}, where a buyer with a valuation function $v$ and budget $B$ wishes to buy a set of items. Each item $i$ has a cost $c_i$ … We study \emph{combinatorial procurement auctions}, where a buyer with a valuation function $v$ and budget $B$ wishes to buy a set of items. Each item $i$ has a cost $c_i$ and the buyer is interested in a set $S$ that maximizes $v(S)$ subject to $\Sigma_{i\in S}c_i\leq B$. Special cases of combinatorial procurement auctions are classical problems from submodular optimization. In particular, when the costs are all equal (\emph{cardinality constraint}), a classic result by Nemhauser et al shows that the greedy algorithm provides an $\frac e {e-1}$ approximation. Motivated by many papers that utilize demand queries to elicit the preferences of agents in economic settings, we develop algorithms that guarantee improved approximation ratios in the presence of demand oracles. We are able to break the $\frac e {e-1}$ barrier: we present algorithms that use only polynomially many demand queries and have approximation ratios of $\frac 9 8+\epsilon$ for the general problem and $\frac 9 8$ for maximization subject to a cardinality constraint. We also consider the more general class of subadditive valuations. We present algorithms that obtain an approximation ratio of $2+\epsilon$ for the general problem and 2 for maximization subject to a cardinality constraint. We guarantee these approximation ratios even when the valuations are non-monotone. We show that these ratios are essentially optimal, in the sense that for any constant $\epsilon>0$, obtaining an approximation ratio of $2-\epsilon$ requires exponentially many demand queries.

Optimization with Demand Oracles

2011-01-01

Ashwinkumar Badanidiyuru , Shahar Dobzinski , Sigal Oren

View PDF Chat

Procurement Auctions via Approximately Optimal Submodular Optimization

2024-11-20

Yuan Deng , Amin Karbasi , Vahab Mirrokni +3 more

We study procurement auctions, where an auctioneer seeks to acquire services from strategic sellers with private costs. The quality of services is measured by a submodular function known to the … We study procurement auctions, where an auctioneer seeks to acquire services from strategic sellers with private costs. The quality of services is measured by a submodular function known to the auctioneer. Our goal is to design computationally efficient procurement auctions that (approximately) maximize the difference between the quality of the acquired services and the total cost of the sellers, while ensuring incentive compatibility (IC), individual rationality (IR) for sellers, and non-negative surplus (NAS) for the auctioneer. Our contributions are twofold: (i) we provide an improved analysis of existing algorithms for non-positive submodular function maximization, and (ii) we design efficient frameworks that transform submodular optimization algorithms into mechanisms that are IC, IR, NAS, and approximation-preserving. These frameworks apply to both the offline setting, where all sellers' bids and services are available simultaneously, and the online setting, where sellers arrive in an adversarial order, requiring the auctioneer to make irrevocable decisions. We also explore whether state-of-the-art submodular optimization algorithms can be converted into descending auctions in adversarial settings, where the schedule of descending prices is determined by an adversary. We show that a submodular optimization algorithm satisfying bi-criteria $(1/2, 1)$-approximation in welfare can be effectively adapted to a descending auction. Additionally, we establish a connection between descending auctions and online submodular optimization. Finally, we demonstrate the practical applications of our frameworks by instantiating them with state-of-the-art submodular optimization algorithms and empirically comparing their welfare performance on publicly available datasets with thousands of sellers.

View PDF Chat

Budget-Feasible Mechanism Design for Non-Monotone Submodular Objectives: Offline and Online

2019-01-01

Georgios Amanatidis , Pieter Kleer , Guido Schäfer

The framework of budget-feasible mechanism design studies procurement auctions where the auctioneer (buyer) aims to maximize his valuation function subject to a hard budget constraint. We study the problem of … The framework of budget-feasible mechanism design studies procurement auctions where the auctioneer (buyer) aims to maximize his valuation function subject to a hard budget constraint. We study the problem of designing truthful mechanisms that have good approximation guarantees and never pay the participating agents (sellers) more than the budget. We focus on the case of general (non-monotone) submodular valuation functions and derive the first truthful, budget-feasible and $O(1)$-approximate mechanisms that run in polynomial time in the value query model, for both offline and online auctions. Prior to our work, the only $O(1)$-approximation mechanism known for non-monotone submodular objectives required an exponential number of value queries. At the heart of our approach lies a novel greedy algorithm for non-monotone submodular maximization under a knapsack constraint. Our algorithm builds two candidate solutions simultaneously (to achieve a good approximation), yet ensures that agents cannot jump from one solution to the other (to implicitly enforce truthfulness). Ours is the first mechanism for the problem where---crucially---the agents are not ordered with respect to their marginal value per cost. This allows us to appropriately adapt these ideas to the online setting as well. To further illustrate the applicability of our approach, we also consider the case where additional feasibility constraints are present. We obtain $O(p)$-approximation mechanisms for both monotone and non-monotone submodular objectives, when the feasible solutions are independent sets of a $p$-system. With the exception of additive valuation functions, no mechanisms were known for this setting prior to our work. Finally, we provide lower bounds suggesting that, when one cares about non-trivial approximation guarantees in polynomial time, our results are asymptotically best possible.

View PDF Chat

Budget-Feasible Mechanism Design for Non-monotone Submodular Objectives: Offline and Online

2022-01-19

Georgios Amanatidis , Pieter Kleer , Guido Schäfer

The framework of budget-feasible mechanism design studies procurement auctions where the auctioneer (buyer) aims to maximize his valuation function subject to a hard budget constraint. We study the problem of … The framework of budget-feasible mechanism design studies procurement auctions where the auctioneer (buyer) aims to maximize his valuation function subject to a hard budget constraint. We study the problem of designing truthful mechanisms that have good approximation guarantees and never pay the participating agents (sellers) more than the budget. We focus on the case of general (non-monotone) submodular valuation functions and derive the first truthful, budget-feasible, and O(1)-approximation mechanisms that run in polynomial time in the value query model, for both offline and online auctions. Prior to our work, the only O(1)-approximation mechanism known for non-monotone submodular objectives required an exponential number of value queries. At the heart of our approach lies a novel greedy algorithm for non-monotone submodular maximization under a knapsack constraint. Our algorithm builds two candidate solutions simultaneously (to achieve a good approximation), yet ensures that agents cannot jump from one solution to the other (to implicitly enforce truthfulness). The fact that in our mechanism the agents are not ordered according to their marginal value per cost allows us to appropriately adapt these ideas to the online setting as well. To further illustrate the applicability of our approach, we also consider the case where additional feasibility constraints are present, for example, at most k agents can be selected. We obtain O(p)-approximation mechanisms for both monotone and non-monotone submodular objectives, when the feasible solutions are independent sets of a p-system. With the exception of additive valuation functions, no mechanisms were known for this setting prior to our work. Finally, we provide lower bounds suggesting that, when one cares about nontrivial approximation guarantees in polynomial time, our results are, asymptotically, the best possible.

View PDF Chat

Combinatorial Assortment Optimization

2017-11-07

Nicole Immorlica , Brendan Lucier , Jieming Mao +2 more

Assortment optimization refers to the problem of designing a slate of products to offer potential customers, such as stocking the shelves in a convenience store. The price of each product … Assortment optimization refers to the problem of designing a slate of products to offer potential customers, such as stocking the shelves in a convenience store. The price of each product is fixed in advance, and a probabilistic choice function describes which product a customer will choose from any given subset. We introduce the combinatorial assortment problem, where each customer may select a bundle of products. We consider a model of consumer choice where the relative value of different bundles is described by a valuation function, while individual customers may differ in their absolute willingness to pay, and study the complexity of the resulting optimization problem. We show that any sub-polynomial approximation to the problem requires exponentially many demand queries when the valuation function is XOS, and that no FPTAS exists even for succinctly-representable submodular valuations. On the positive side, we show how to obtain constant approximations under a well-priced condition, where each product's price is sufficiently high. We also provide an exact algorithm for $k$-additive valuations, and show how to extend our results to a learning setting where the seller must infer the customers' preferences from their purchasing behavior.

Combinatorial Assortment Optimization

2017-01-01

Nicole Immorlica , Brendan Lucier , Jieming Mao +2 more

Assortment optimization refers to the problem of designing a slate of products to offer potential customers, such as stocking the shelves in a convenience store. The price of each product … Assortment optimization refers to the problem of designing a slate of products to offer potential customers, such as stocking the shelves in a convenience store. The price of each product is fixed in advance, and a probabilistic choice function describes which product a customer will choose from any given subset. We introduce the combinatorial assortment problem, where each customer may select a bundle of products. We consider a model of consumer choice where the relative value of different bundles is described by a valuation function, while individual customers may differ in their absolute willingness to pay, and study the complexity of the resulting optimization problem. We show that any sub-polynomial approximation to the problem requires exponentially many demand queries when the valuation function is XOS, and that no FPTAS exists even for succinctly-representable submodular valuations. On the positive side, we show how to obtain constant approximations under a "well-priced" condition, where each product's price is sufficiently high. We also provide an exact algorithm for $k$-additive valuations, and show how to extend our results to a learning setting where the seller must infer the customers' preferences from their purchasing behavior.

View PDF Chat

Truthful Multi-unit Procurements with Budgets

2014-01-01

Hau Chan , Jing Chen

We study procurement games where each seller supplies multiple units of his item, with a cost per unit known only to him. The buyer can purchase any number of units … We study procurement games where each seller supplies multiple units of his item, with a cost per unit known only to him. The buyer can purchase any number of units from each seller, values different combinations of the items differently, and has a budget for his total payment. For a special class of procurement games, the {\em bounded knapsack} problem, we show that no universally truthful budget-feasible mechanism can approximate the optimal value of the buyer within $\ln n$, where $n$ is the total number of units of all items available. We then construct a polynomial-time mechanism that gives a $4(1+\ln n)$-approximation for procurement games with {\em concave additive valuations}, which include bounded knapsack as a special case. Our mechanism is thus optimal up to a constant factor. Moreover, for the bounded knapsack problem, given the well-known FPTAS, our results imply there is a provable gap between the optimization domain and the mechanism design domain. Finally, for procurement games with {\em sub-additive valuations}, we construct a universally truthful budget-feasible mechanism that gives an $O(\frac{\log^2 n}{\log \log n})$-approximation in polynomial time with a demand oracle.

View PDF Chat

On Budget-Feasible Mechanism Design for Symmetric Submodular Objectives

2017-04-23

Georgios Amanatidis , Georgios Birmpas , Evangelos Markakis

We study a class of procurement auctions with a budget constraint, where an auctioneer is interested in buying resources or services from a set of agents. Ideally, the auctioneer would … We study a class of procurement auctions with a budget constraint, where an auctioneer is interested in buying resources or services from a set of agents. Ideally, the auctioneer would like to select a subset of the resources so as to maximize his valuation function, without exceeding a given budget. As the resources are owned by strategic agents however, our overall goal is to design mechanisms that are truthful, budget-feasible, and obtain a good approximation to the optimal value. Budget-feasibility creates additional challenges, making several approaches inapplicable in this setting. Previous results on budget-feasible mechanisms have considered mostly monotone valuation functions. In this work, we mainly focus on symmetric submodular valuations, a prominent class of non-monotone submodular functions that includes cut functions. We begin first with a purely algorithmic result, obtaining a $\frac{2e}{e-1}$-approximation for maximizing symmetric submodular functions under a budget constraint. We view this as a standalone result of independent interest, as it is the best known factor achieved by a deterministic algorithm. We then proceed to propose truthful, budget feasible mechanisms (both deterministic and randomized), paying particular attention on the Budgeted Max Cut problem. Our results significantly improve the known approximation ratios for these objectives, while establishing polynomial running time for cases where only exponential mechanisms were known. At the heart of our approach lies an appropriate combination of local search algorithms with results for monotone submodular valuations, applied to the derived local optima.

On Budget-Feasible Mechanism Design for Symmetric Submodular Objectives

2017-01-01

Georgios Amanatidis , Georgios Birmpas , Evangelos Markakis

View PDF Chat

Combinatorial Assortment Optimization

2021-01-28

Nicole Immorlica , Brendan Lucier , Jieming Mao +2 more

Assortment optimization refers to the problem of designing a slate of products to offer potential customers, such as stocking the shelves in a convenience store. The price of each product … Assortment optimization refers to the problem of designing a slate of products to offer potential customers, such as stocking the shelves in a convenience store. The price of each product is fixed in advance, and a probabilistic choice function describes which product a customer will choose from any given subset. We introduce the combinatorial assortment problem, where each customer may select a bundle of products. We consider a choice model in which each consumer selects a utility-maximizing bundle subject to a private valuation function, and study the complexity of the resulting optimization problem. Our main result is an exact algorithm for additive k -demand valuations, under a model of vertical differentiation in which customers agree on the relative value of each pair of items but differ in their absolute willingness to pay. For valuations that are vertically differentiated but not necessarily additive k -demand, we show how to obtain constant approximations under a “well-priced” condition, where each product’s price is sufficiently high. We further show that even for a single customer with known valuation, any sub-polynomial approximation to the problem requires exponentially many demand queries when the valuation function is XOS and that no FPTAS exists even when the valuation is succinctly representable.

View PDF Chat

On the Hardness of Welfare Maximization in Combinatorial Auctions with Submodular Valuations

2012-01-01

Shahar Dobzinski , J. Vondrák

We present a new type of monotone submodular functions: \emph{multi-peak submodular functions}. Roughly speaking, given a family of sets $\cF$, we construct a monotone submodular function $f$ with a high … We present a new type of monotone submodular functions: \emph{multi-peak submodular functions}. Roughly speaking, given a family of sets $\cF$, we construct a monotone submodular function $f$ with a high value $f(S)$ for every set $S \in {\cF}$ (a "peak"), and a low value on every set that does not intersect significantly any set in $\cF$. We use this construction to show that a better than $(1-\frac{1}{2e})$-approximation ($\simeq 0.816$) for welfare maximization in combinatorial auctions with submodular valuations is (1) impossible in the communication model, (2) NP-hard in the computational model where valuations are given explicitly. Establishing a constant approximation hardness for this problem in the communication model was a long-standing open question. The valuations we construct for the hardness result in the computational model depend only on a constant number of items, and hence the result holds even if the players can answer arbitrary queries about their valuation, including demand queries. We also study two other related problems that received some attention recently: max-min allocation (for which we also get hardness of $(1-\frac 1 {2e}+ε)$-approximation, in both models), and combinatorial public projects (for which we prove hardness of $(3/4+ε)$-approximation in the communication model, and hardness of $(1 -\frac 1 e+ε)$-approximation in the computational model, using constant size valuations).

Coverage, Matching, and Beyond: New Results on Budgeted Mechanism Design

2016-01-01

Georgios Amanatidis , Georgios Birmpas , Evangelos Markakis

We study a type of reverse (procurement) auction problems in the presence of budget constraints. The general algorithmic problem is to purchase a set of resources, which come at a … We study a type of reverse (procurement) auction problems in the presence of budget constraints. The general algorithmic problem is to purchase a set of resources, which come at a cost, so as not to exceed a given budget and at the same time maximize a given valuation function. This framework captures the budgeted version of several well known optimization problems, and when the resources are owned by strategic agents the goal is to design truthful and budget feasible mechanisms, i.e. elicit the true cost of the resources and ensure the payments of the mechanism do not exceed the budget. Budget feasibility introduces more challenges in mechanism design, and we study instantiations of this problem for certain classes of submodular and XOS valuation functions. We first obtain mechanisms with an improved approximation ratio for weighted coverage valuations, a special class of submodular functions that has already attracted attention in previous works. We then provide a general scheme for designing randomized and deterministic polynomial time mechanisms for a class of XOS problems. This class contains problems whose feasible set forms an independence system (a more general structure than matroids), and some representative problems include, among others, finding maximum weighted matchings, maximum weighted matroid members, and maximum weighted 3D-matchings. For most of these problems, only randomized mechanisms with very high approximation ratios were known prior to our results.

Coverage, Matching, and Beyond: New Results on Budgeted Mechanism Design

2016-10-04

Georgios Amanatidis , Georgios Birmpas , Evangelos Markakis

Breaking Barriers: Combinatorial Algorithms for Non-monotone Submodular Maximization with Sublinear Adaptivity and $1/e$ Approximation

2025-02-10

Yixin Chen , Wenjing Chen , Alan Kuhnle

With the rapid growth of data in modern applications, parallel combinatorial algorithms for maximizing non-monotone submodular functions have gained significant attention. The state-of-the-art approximation ratio of $1/e$ is currently achieved … With the rapid growth of data in modern applications, parallel combinatorial algorithms for maximizing non-monotone submodular functions have gained significant attention. The state-of-the-art approximation ratio of $1/e$ is currently achieved only by a continuous algorithm (Ene & Nguyen, 2020) with adaptivity $\mathcal O(\log(n))$. In this work, we focus on size constraints and propose a $(1/4-\varepsilon)$-approximation algorithm with high probability for this problem, as well as the first randomized parallel combinatorial algorithm achieving a $1/e-\varepsilon$ approximation ratio, which bridges the gap between continuous and combinatorial approaches. Both algorithms achieve $\mathcal O(\log(n)\log(k))$ adaptivity and $\mathcal O(n\log(n)\log(k))$ query complexity. Empirical results show our algorithms achieve competitive objective values, with the first algorithm particularly efficient in queries.

View PDF Chat

Approximations for Monotone and Non-monotone Submodular Maximization with Knapsack Constraints

2011-01-15

Ariel Kulik , Hadas Shachnai , Tami Tamir

Submodular maximization generalizes many fundamental problems in discrete optimization, including Max-Cut in directed/undirected graphs, maximum coverage, maximum facility location and marketing over social networks. In this paper we consider the … Submodular maximization generalizes many fundamental problems in discrete optimization, including Max-Cut in directed/undirected graphs, maximum coverage, maximum facility location and marketing over social networks. In this paper we consider the problem of maximizing any submodular function subject to $d$ knapsack constraints, where $d$ is a fixed constant. We establish a strong relation between the discrete problem and its continuous relaxation, obtained through {\em extension by expectation} of the submodular function. Formally, we show that, for any non-negative submodular function, an $\alpha$-approximation algorithm for the continuous relaxation implies a randomized $(\alpha - \eps)$-approximation algorithm for the discrete problem. We use this relation to improve the best known approximation ratio for the problem to $1/4- \eps$, for any $\eps > 0$, and to obtain a nearly optimal $(1-e^{-1}-\eps)-$approximation ratio for the monotone case, for any $\eps>0$. We further show that the probabilistic domain defined by a continuous solution can be reduced to yield a polynomial size domain, given an oracle for the extension by expectation. This leads to a deterministic version of our technique.

Approximations for Monotone and Non-monotone Submodular Maximization with Knapsack Constraints

2011-01-01

Ariel Kulik , Hadas Shachnai , Tami Tamir

View PDF Chat

Budget Feasible Mechanisms

2010-02-11

Yaron Singer

We study a novel class of mechanism design problems in which the outcomes are constrained by the payments. This basic class of mechanism design problems captures many common economic situations, … We study a novel class of mechanism design problems in which the outcomes are constrained by the payments. This basic class of mechanism design problems captures many common economic situations, and yet it has not been studied, to our knowledge, in the past. We focus on the case of procurement auctions in which sellers have private costs, and the auctioneer aims to maximize a utility function on subsets of items, under the constraint that the sum of the payments provided by the mechanism does not exceed a given budget. Standard mechanism design ideas such as the VCG mechanism and its variants are not applicable here. We show that, for general functions, the budget constraint can render mechanisms arbitrarily bad in terms of the utility of the buyer. However, our main result shows that for the important class of submodular functions, a bounded approximation ratio is achievable. Better approximation results are obtained for subclasses of the submodular functions. We explore the space of budget feasible mechanisms in other domains and give a characterization under more restricted conditions.

Budget Feasible Mechanisms

2010-01-01

Yaron Singer

View PDF Chat

Private Interdependent Valuations: New Bounds for Single-Item Auctions and Matroids

2024-02-19

Alon Eden , Michal Feldman , Simon Mauras +1 more

We study auction design within the widely acclaimed model of interdependent values, introduced by Milgrom and Weber [1982]. In this model, every bidder $i$ has a private signal $s_i$ for … We study auction design within the widely acclaimed model of interdependent values, introduced by Milgrom and Weber [1982]. In this model, every bidder $i$ has a private signal $s_i$ for the item for sale, and a public valuation function $v_i(s_1,\ldots,s_n)$ which maps every vector of private signals (of all bidders) into a real value. A recent line of work established the existence of approximately-optimal mechanisms within this framework, even in the more challenging scenario where each bidder's valuation function $v_i$ is also private. This body of work has primarily focused on single-item auctions with two natural classes of valuations: those exhibiting submodularity over signals (SOS) and $d$-critical valuations. In this work we advance the state of the art on interdependent values with private valuation functions, with respect to both SOS and $d$-critical valuations. For SOS valuations, we devise a new mechanism that gives an improved approximation bound of $5$ for single-item auctions. This mechanism employs a novel variant of an "eating mechanism", leveraging LP-duality to achieve feasibility with reduced welfare loss. For $d$-critical valuations, we broaden the scope of existing results beyond single-item auctions, introducing a mechanism that gives a $(d+1)$-approximation for any environment with matroid feasibility constraints on the set of agents that can be simultaneously served. Notably, this approximation bound is tight, even with respect to single-item auctions.

View PDF Chat

Fractionally Subadditive Maximization Under an Incremental Knapsack Constraint

2021-01-01

Yann Disser , Max Klimm , David Weckbecker

View PDF Chat

Tight Approximation for Unconstrained XOS Maximization

2018-01-01

Yuval Filmus , Yasushi Kawase , Yusuke Kobayashi +1 more

A set function is called XOS if it can be represented by the maximum of additive functions. When such a representation is fixed, the number of additive functions required to … A set function is called XOS if it can be represented by the maximum of additive functions. When such a representation is fixed, the number of additive functions required to define the XOS function is called the width. In this paper, we study the problem of maximizing XOS functions in the value oracle model. The problem is trivial for the XOS functions of width $1$ because they are just additive, but it is already nontrivial even when the width is restricted to $2$. We show two types of tight bounds on the polynomial-time approximability for this problem. First, in general, the approximation bound is between $O(n)$ and $\Omega(n / \log n)$, and exactly $\Theta(n / \log n)$ if randomization is allowed, where $n$ is the ground set size. Second, when the width of the input XOS functions is bounded by a constant $k \geq 2$, the approximation bound is between $k - 1$ and $k - 1 - \epsilon$ for any $\epsilon > 0$. In particular, we give a linear-time algorithm to find an exact maximizer of a given XOS function of width $2$, while we show that any exact algorithm requires an exponential number of value oracle calls even when the width is restricted to $3$.

View PDF Chat

On the Complexity of Computing an Equilibrium in Combinatorial Auctions

2014-12-22

Shahar Dobzinski , Hu Fu , 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 … 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.

View PDF Chat

Combinatorial walrasian equilibrium

2013-05-28

Michal Feldman , Nick Gravin , Brendan Lucier

We study a combinatorial market design problem, where a collection of indivisible objects is to be priced and sold to potential buyers subject to equilibrium constraints. The classic solution concept … We study a combinatorial market design problem, where a collection of indivisible objects is to be priced and sold to potential buyers subject to equilibrium constraints. The classic solution concept for such problems is Walrasian Equilibrium (WE), which provides a simple and transparent pricing structure that achieves optimal social welfare. The main weakness of the WE notion is that it exists only in very restrictive cases. To overcome this limitation, we introduce the notion of a Combinatorial Walrasian equilibium (CWE), a natural relaxation of WE. The difference between a CWE and a (non-combinatorial) WE is that the seller can package the items into indivisible bundles prior to sale, and the market does not necessarily clear. We show that every valuation profile admits a CWE that obtains at least half of the optimal (unconstrained) social welfare. Moreover, we devise a poly-time algorithm that, given an arbitrary allocation X, computes a CWE that achieves at least half of the welfare of X. Thus, the economic problem of finding a CWE with high social welfare reduces to the algorithmic problem of social-welfare approximation. In addition, we show that every valuation profile admits a CWE that extracts a logarithmic fraction of the optimal welfare as revenue. Finally, these results are complemented by strong lower bounds when the seller is restricted to using item prices only, which motivates the use of bundles. The strength of our results derives partly from their generality --- our results hold for arbitrary valuations that may exhibit complex combinations of substitutes and complements.

View PDF Chat

Tight Approximation for Unconstrained XOS Maximization

2021-03-29

Yuval Filmus , Yasushi Kawase , Yusuke Kobayashi +1 more

A set function is called XOS if it can be represented by the maximum of additive functions. When such a representation is fixed, the number of additive functions required to … A set function is called XOS if it can be represented by the maximum of additive functions. When such a representation is fixed, the number of additive functions required to define the XOS function is called the width. In this paper, we study the problem of maximizing XOS functions in the value oracle model. The problem is trivial for the XOS functions of width 1 because they are just additive, but it is already nontrivial even when the width is restricted to 2. We show two types of tight bounds on the polynomial-time approximability for this problem. First, in general, the approximation bound is between O(n) and [Formula: see text], and exactly [Formula: see text] if randomization is allowed, where n is the ground set size. Second, when the width of the input XOS functions is bounded by a constant k ≥ 2, the approximation bound is between k − 1 and k − 1 − ɛ for any ɛ > 0. In particular, we give a linear-time algorithm to find an exact maximizer of a given XOS function of width 2, whereas we show that any exact algorithm requires an exponential number of value oracle calls even when the width is restricted to 3.

View PDF Chat

Optimization with demand oracles

2012-06-04

Ashwinkumar Badanidiyuru , Shahar Dobzinski , Sigal Oren

We study combinatorial procurement auctions, where a buyer with a valuation function v and budget B wishes to buy a set of items. Each item i has a cost ci … We study combinatorial procurement auctions, where a buyer with a valuation function v and budget B wishes to buy a set of items. Each item i has a cost ci and the buyer is interested in a set S that maximizes v(S) subject to ∑i∈Sci ≤ β. Special cases of combinatorial procurement auctions are well-studied problems from submodular optimization. In particular, when the costs are all equal (cardinality constraint), a classic result by Nemhauser et al shows that the greedy algorithm provides an e/e-1 approximation.

View PDF Chat

Deterministic Budget-Feasible Clock Auctions

2021-01-01

Eric Balkanski , Pranav Garimidi , Vasilis Gkatzelis +2 more

We revisit the well-studied problem of budget-feasible procurement, where a buyer with a strict budget constraint seeks to acquire services from a group of strategic providers (the sellers). During the … We revisit the well-studied problem of budget-feasible procurement, where a buyer with a strict budget constraint seeks to acquire services from a group of strategic providers (the sellers). During the last decade, several strategyproof budget-feasible procurement auctions have been proposed, aiming to maximize the value of the buyer, while eliciting each seller's true cost for providing their service. These solutions predominantly take the form of randomized sealed-bid auctions: they ask the sellers to report their private costs and then use randomization to determine which subset of services will be procured and how much each of the chosen providers will be paid, ensuring that the total payment does not exceed budget. Our main result in this paper is a novel method for designing budget-feasible auctions, leading to solutions that outperform the previously proposed auctions in multiple ways. First, our solutions take the form of descending clock auctions, and thus satisfy a list of properties, such as obvious strategyproofness, group strategyproofness, transparency, and unconditional winner privacy; this makes these auctions much more likely to be used in practice. Second, in contrast to previous results that heavily depend on randomization, our auctions are deterministic. As a result, we provide an affirmative answer to one of the main open questions in this literature, asking whether a deterministic strategyproof auction can achieve a constant approximation when the buyer's valuation function is submodular over the set of services. In addition, we also provide the first deterministic budget-feasible auction that matches the approximation bound of the best-known randomized auction for the class of subadditive valuations. Finally, using our method, we improve the best-known approximation factor for monotone submodular valuations, which has been the focus of most of the prior work.

Combinatorial Walrasian Equilibrium

2013-04-08

Michal Feldman , Nick Gravin , Brendan Lucier

We study a combinatorial market design problem, where a collection of indivisible objects is to be priced and sold to potential buyers subject to equilibrium constraints.The classic solution concept for … We study a combinatorial market design problem, where a collection of indivisible objects is to be priced and sold to potential buyers subject to equilibrium constraints.The classic solution concept for such problems is Walrasian Equilibrium (WE), which provides a simple and transparent pricing structure that achieves optimal social welfare. The main weakness of the WE notion is that it exists only in very restrictive cases. To overcome this limitation, we introduce the notion of a Combinatorial Walrasian equilibium (CWE), a natural relaxation of WE. The difference between a CWE and a (non-combinatorial) WE is that the seller can package the items into indivisible bundles prior to sale, and the market does not necessarily clear. We show that every valuation profile admits a CWE that obtains at least half of the optimal (unconstrained) social welfare. Moreover, we devise a poly-time algorithm that, given an arbitrary allocation X, computes a CWE that achieves at least half of the welfare of X. Thus, the economic problem of finding a CWE with high social welfare reduces to the algorithmic problem of social-welfare approximation. In addition, we show that every valuation profile admits a CWE that extracts a logarithmic fraction of the optimal welfare as revenue. Finally, these results are complemented by strong lower bounds when the seller is restricted to using item prices only, which motivates the use of bundles. The strength of our results derives partly from their generality - our results hold for arbitrary valuations that may exhibit complex combinations of substitutes and complements.

Truthful Multi-unit Procurements with Budgets

2014-01-01

Hau Chan , Jing Chen

View PDF Chat

Simplicity in Auctions Revisited: The Primitive Complexity

2023-07-07

Moshe Babaioff , Shahar Dobzinski , Ron Kupfer

In this paper we revisit the notion of simplicity in mechanisms. We consider a seller of m heterogeneous items, facing a single buyer with valuation v. We observe that previous … In this paper we revisit the notion of simplicity in mechanisms. We consider a seller of m heterogeneous items, facing a single buyer with valuation v. We observe that previous attempts to define complexity measures often fail to classify mechanisms that are intuitively considered simple (e.g., the "selling separately" mechanism) as such. We suggest to view a menu as simple if a bundle that maximizes the buyer's profit can be found by conducting a few primitive operations that are considered simple. The primitive complexity of a menu is the number of primitive operations needed to (adaptively) find a profit-maximizing entry in the menu. In this paper, the primitive operation that we study is essentially computing the outcome of the "selling separately" mechanism.

View PDF Chat

Budget Feasible Mechanism Design via Random Sampling

2011-01-01

Xiaohui Bei , Ning Chen , Nick Gravin +1 more

Budget feasible mechanism considers algorithmic mechanism design questions where there is a budget constraint on the total payment of the mechanism. An important question in the field is that under … Budget feasible mechanism considers algorithmic mechanism design questions where there is a budget constraint on the total payment of the mechanism. An important question in the field is that under which valuation domains there exist budget feasible mechanisms that admit `small' approximations (compared to a socially optimal solution). Singer \cite{PS10} showed that additive and submodular functions admit a constant approximation mechanism. Recently, Dobzinski, Papadimitriou, and Singer \cite{DPS11} gave an $O(\log^2n)$ approximation mechanism for subadditive functions and remarked that: "A fundamental question is whether, regardless of computational constraints, a constant-factor budget feasible mechanism exists for subadditive function." In this paper, we give the first attempt to this question. We give a polynomial time $O(\frac{\log n}{\log\log n})$ sub-logarithmic approximation ratio mechanism for subadditive functions, improving the best known ratio $O(\log^2 n)$. Further, we connect budget feasible mechanism design to the concept of approximate core in cooperative game theory, and show that there is a mechanism for subadditive functions whose approximation is, via a characterization of the integrality gap of a linear program, linear to the largest value to which an approximate core exists. Our result implies in particular that the class of XOS functions, which is a superclass of submodular functions, admits a constant approximation mechanism. We believe that our work could be a solid step towards solving the above fundamental problem eventually, and possibly, with an affirmative answer.

Submodular function maximization via the multilinear relaxation and contention resolution schemes

2011-06-06

Chandra Chekuri , Jan Vondrák , Rico Zenklusen

We consider the problem of maximizing a non-negative submodular set function f:2N -> RR+ over a ground set N subject to a variety of packing type constraints including (multiple) matroid … We consider the problem of maximizing a non-negative submodular set function f:2N -> RR+ over a ground set N subject to a variety of packing type constraints including (multiple) matroid constraints, knapsack constraints, and their intersections. In this paper we develop a general framework that allows us to derive a number of new results, in particular when f may be a non-monotone function. Our algorithms are based on (approximately) solving the multilinear extension F of f [5] over a polytope P that represents the constraints, and then effectively rounding the fractional solution. Although this approach has been used quite successfully in some settings [6, 22, 24, 13, 3], it has been limited in some important ways. We overcome these limitations as follows.

View PDF Chat

Combinatorial auctions with decreasing marginal utilities

2001-10-14

Benny Lehmann , Daniel Lehmann , Noam Nisan

In most of microeconomic theory, consumers are assumed to exhibit decreasing marginal utilities. This paper considers combinatorial auctions among such buyers. The valuations of such buyers are placed within a … In most of microeconomic theory, consumers are assumed to exhibit decreasing marginal utilities. This paper considers combinatorial auctions among such buyers. The valuations of such buyers are placed within a hierarchy of valuations that exhibit no complementarities, a hierarchy that includes also OR and XOR combinations of singleton valuations, and valuations satisfying the gross substitutes property. While we show that the allocation problem among valuations with decreasing marginal utilities is NP-hard, we present an efficient greedy 2-approximation algorithm for this case. No such approximation algorithm exists in a setting allowing for complementarities. Some results about strategic aspects of combinatorial auctions among players with decreasing marginal utilities are also presented.

Non-monotone submodular maximization under matroid and knapsack constraints

2009-05-31

Jon Lee , Vahab Mirrokni , Viswanath Nagarajan +1 more

Submodular function maximization is a central problem in combinatorial optimization, generalizing many important problems including Max Cut in directed/undirected graphs and in hypergraphs, certain constraint satisfaction problems, maximum entropy sampling, … Submodular function maximization is a central problem in combinatorial optimization, generalizing many important problems including Max Cut in directed/undirected graphs and in hypergraphs, certain constraint satisfaction problems, maximum entropy sampling, and maximum facility location problems. Unlike submodular minimization, submodular maximization is NP-hard. In this paper, we give the first constant-factor approximation algorithm for maximizing any non-negative submodular function subject to multiple matroid or knapsack constraints. We emphasize that our results are for non-monotone submodular functions. In particular, for any constant k, we present a (1/k+2+1/k+ε)-approximation for the submodular maximization problem under k matroid constraints, and a (1/5-ε)-approximation algorithm for this problem subject to k knapsack constraints (ε>0 is any constant). We improve the approximation guarantee of our algorithm to 1/k+1+{1/k-1}+ε for k≥2 partition matroid constraints. This idea also gives a ({1/k+ε)-approximation for maximizing a monotone submodular function subject to k≥2 partition matroids, which improves over the previously best known guarantee of 1/k+1.

View PDF Chat

An impossibility result for truthful combinatorial auctions with submodular valuations

2011-06-06

Shahar Dobzinski

We show that every universally truthful randomized mechanism for combinatorial auctions with submodular valuations that provides an approximation ratio of m1/ 2 -ε must use exponentially many value queries, where … We show that every universally truthful randomized mechanism for combinatorial auctions with submodular valuations that provides an approximation ratio of m1/ 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.

View PDF Chat

Budget Feasible Mechanisms

2010-10-01

Yaron Singer

We study a novel class of mechanism design problems in which the outcomes are constrained by the payments. This basic class of mechanism design problems captures many common economic situations, … We study a novel class of mechanism design problems in which the outcomes are constrained by the payments. This basic class of mechanism design problems captures many common economic situations, and yet it has not been studied, to our knowledge, in the past. We focus on the case of procurement auctions in which sellers have private costs, and the auctioneer aims to maximize a utility function on subsets of items, under the constraint that the sum of the payments provided by the mechanism does not exceed a given budget. Standard mechanism design ideas such as the VCG mechanism and its variants are not applicable here. We show that, for general functions, the budget constraint can render mechanisms arbitrarily bad in terms of the utility of the buyer. However, our main result shows that for the important class of sub modular functions, a bounded approximation ratio is achievable. Better approximation results are obtained for subclasses of the sub modular functions. We explore the space of budget feasible mechanisms in other domains and give a characterization under more restricted conditions.

View PDF Chat

Budget feasible mechanism design: from prior-free to bayesian

2012-05-19

Xiaohui Bei , Ning Chen , Nick Gravin +1 more

Budget feasible mechanism design studies procurement combinatorial auctions in the sellers have private costs to produce items, and the buyer (auctioneer) aims to maximize a social valuation function on subsets … Budget feasible mechanism design studies procurement combinatorial auctions in the sellers have private costs to produce items, and the buyer (auctioneer) aims to maximize a social valuation function on subsets of items, under the budget constraint on the total payment. One of the most important questions in the field is which valuation domains admit truthful budget feasible mechanisms with 'small' approximations (compared to the social optimum)? Singer [35] showed that additive and submodular functions have a constant approximation mechanism. Recently, Dobzinski, Papadimitriou, and Singer [20] gave an O(log2n) approximation mechanism for subadditive functions; further, they remarked that: A fundamental question is whether, regardless of computational constraints, a constant-factor budget feasible mechanism exists for subadditive In this paper, we address this question from two viewpoints: prior-free worst case analysis and Bayesian analysis, are two standard approaches from computer science and economics, respectively. - For the prior-free framework, we use a linear program (LP) that describes the fractional cover of the valuation function; the LP is also connected to the concept of approximate core in cooperative game theory. We provide a mechanism for subadditive functions whose approximation is O(I), via the worst case integrality gap I of this LP. This implies an O(log n)-approximation for subadditive valuations, O(1)-approximation for XOS valuations, as well as for valuations having a constant integrality gap. XOS valuations are an important class of functions and lie between the submodular and the subadditive classes of valuations. We further give another polynomial time O(log n/(log log n)) sub-logarithmic approximation mechanism for subadditive functions. Both of our mechanisms improve the best known approximation ratio O(log2 n). - For the Bayesian framework, we provide a constant approximation mechanism for all subadditive functions, using the above prior-free mechanism for XOS valuations as a subroutine. Our mechanism allows correlations in the distribution of private information and is universally truthful.

View PDF Chat

Optimization with demand oracles

2012-06-04

Ashwinkumar Badanidiyuru , Shahar Dobzinski , Sigal Oren

View PDF Chat

On the approximability of budget feasible mechanisms

2011-01-23

Ning Chen , Nick Gravin , Pinyan Lu

Budget feasible mechanisms, recently initiated by Singer (FOCS 2010), extend algorithmic mechanism design problems to a realistic setting with a budget constraint. We consider the problem of designing truthful budget … Budget feasible mechanisms, recently initiated by Singer (FOCS 2010), extend algorithmic mechanism design problems to a realistic setting with a budget constraint. We consider the problem of designing truthful budget feasible mechanisms for monotone submodular functions: We give a randomized mechanism with an approximation ratio of 7.91 (improving on the previous best-known result 233.83), and a deterministic mechanism with an approximation ratio of 8.34. We also study the knapsack problem, which is a special submodular function, give a 2 + √2 approximation deterministic mechanism (improving on the previous best-known result 5), and a 3 approximation randomized mechanism. We provide similar results for an extended knapsack problem with heterogeneous items, where items are divided into groups and one can pick at most one item from each group.Finally we show a lower bound of 1 + √2 for the approximation ratio of deterministic mechanisms and 2 for randomized mechanisms for knapsack, as well as the general monotone submodular functions. Our lower bounds are unconditional, and do not rely on any computational or complexity assumptions.

Submodular Maximization by Simulated Annealing

2011-01-23

Shayan Oveis Gharan , Jan Vondrák

Previous chapter Next chapter Full AccessProceedings Proceedings of the 2011 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Submodular Maximization by Simulated AnnealingShayan Oveis Gharan and Jan VondrákShayan Oveis Gharan and Jan … Previous chapter Next chapter Full AccessProceedings Proceedings of the 2011 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Submodular Maximization by Simulated AnnealingShayan Oveis Gharan and Jan VondrákShayan Oveis Gharan and Jan Vondrákpp.1098 - 1116Chapter DOI:https://doi.org/10.1137/1.9781611973082.83PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract We consider the problem of maximizing a non-negative (possibly non-monotone) submodular set function with or without constraints. Feige et al. [9] showed a 2/5-approximation for the unconstrained problem and also proved that no approximation better than 1/2 is possible in the value oracle model. Constant-factor approximation has been also known for submodular maximization subject to a matroid independence constraint (a factor of 0.309 [33]) and for submodular maximization subject to a matroid base constraint, provided that the fractional base packing number v is bounded away from 1 (a 1/4-approximation assuming that v ≥ 2 [33]). In this paper, we propose a new algorithm for submodular maximization which is based on the idea of simulated annealing. We prove that this algorithm achieves improved approximation for two problems: a 0.41-approximation for unconstrained submodular maximization, and a 0.325-approximation for submodular maximization subject to a matroid independence constraint. On the hardness side, we show that in the value oracle model it is impossible to achieve a 0.478-approximation for submodular maximization subject to a matroid independence constraint, or a 0.394-approximation subject to a matroid base constraint in matroids with two disjoint bases. Even for the special case of cardinality constraint, we prove it is impossible to achieve a 0.491-approximation. (Previously it was conceivable that a 1/2-approximation exists for these problems.) It is still an open question whether a 1/2-approximation is possible for unconstrained submodular maximization. Previous chapter Next chapter RelatedDetails Published:2011ISBN:978-0-89871-993-2eISBN:978-1-61197-308-2 https://doi.org/10.1137/1.9781611973082Book Series Name:ProceedingsBook Code:PR138Book Pages:xviii-1788

View PDF Chat

On the Approximability of Budget Feasible Mechanisms

2011-01-23

Ning Chen , Nick Gravin , Pinyan Lu

Previous chapter Next chapter Full AccessProceedings Proceedings of the 2011 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)On the Approximability of Budget Feasible MechanismsNing Chen, Nick Gravin, and Pinyan LuNing Chen, … Previous chapter Next chapter Full AccessProceedings Proceedings of the 2011 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)On the Approximability of Budget Feasible MechanismsNing Chen, Nick Gravin, and Pinyan LuNing Chen, Nick Gravin, and Pinyan Lupp.685 - 699Chapter DOI:https://doi.org/10.1137/1.9781611973082.54PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract Budget feasible mechanisms, recently initiated by Singer (FOCS 2010), extend algorithmic mechanism design problems to a realistic setting with a budget constraint. We consider the problem of designing truthful budget feasible mechanisms for monotone submodular functions: We give a randomized mechanism with an approximation ratio of 7.91 (improving on the previous best-known result 233.83), and a deterministic mechanism with an approximation ratio of 8.34. We also study the knapsack problem, which is a special submodular function, give a 2 + √2 approximation deterministic mechanism (improving on the previous best-known result 5), and a 3 approximation randomized mechanism. We provide similar results for an extended knapsack problem with heterogeneous items, where items are divided into groups and one can pick at most one item from each group. Finally we show a lower bound of 1 + √2 for the approximation ratio of deterministic mechanisms and 2 for randomized mechanisms for knapsack, as well as the general monotone submodular functions. Our lower bounds are unconditional, and do not rely on any computational or complexity assumptions. Previous chapter Next chapter RelatedDetails Published:2011ISBN:978-0-89871-993-2eISBN:978-1-61197-308-2 https://doi.org/10.1137/1.9781611973082Book Series Name:ProceedingsBook Code:PR138Book Pages:xviii-1788

View PDF Chat

Optimization with Demand Oracles

2011-07-14

Ashwinkumar Badanidiyuru , Shahar Dobzinski , Sigal Oren

Approximations for Monotone and Non-monotone Submodular Maximization with Knapsack Constraints

2011-01-15

Ariel Kulik , Hadas Shachnai , Tami Tamir

Budget feasible mechanism design

2012-05-19

Xiaohui Bei , Ning Chen , Nick Gravin +1 more

Budget feasible mechanism design studies procurement combinatorial auctions where the sellers have private costs to produce items, and the buyer(auctioneer) aims to maximize a social valuation function on subsets of … Budget feasible mechanism design studies procurement combinatorial auctions where the sellers have private costs to produce items, and the buyer(auctioneer) aims to maximize a social valuation function on subsets of items, under the budget constraint on the total payment. One of the most important questions in the field is "which valuation domains admit truthful budget feasible mechanisms with `small' approximations (compared to the social optimum)?" Singer showed that additive and submodular functions have such constant approximations. Recently, Dobzinski, Papadimitriou, and Singer gave an O(log^2 n)-approximation mechanism for subadditive functions; they also remarked that: "A fundamental question is whether, regardless of computational constraints, a constant-factor budget feasible mechanism exists for subadditive functions." We address this question from two viewpoints: prior-free worst case analysis and Bayesian analysis. For the prior-free framework, we use an LP that describes the fractional cover of the valuation function; it is also connected to the concept of approximate core in cooperative game theory. We provide an O(I)-approximation mechanism for subadditive functions, via the worst case integrality gap I of LP. This implies an O(log n)-approximation for subadditive valuations, O(1)-approximation for XOS valuations, and for valuations with a constant I. XOS valuations are an important class of functions that lie between submodular and subadditive classes. We give another polynomial time O(log n/loglog n) sub-logarithmic approximation mechanism for subadditive valuations. For the Bayesian framework, we provide a constant approximation mechanism for all subadditive functions, using the above prior-free mechanism for XOS valuations as a subroutine. Our mechanism allows correlations in the distribution of private information and is universally truthful.

View PDF Chat