Ning Chen

Search for another author

Author Description

Ask a Question About This Mathematician

On the approximability of budget feasible mechanisms

2011-01-23

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.

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

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

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

Optimal competitive auctions

2014-05-31

Ning Chen , Nick Gravin , Pinyan Lu

View PDF Chat

Frugal Mechanism Design via Spectral Techniques

2010-10-01

Ning Chen , Edith Elkind , Nick Gravin +1 more

We study the design of truthful mechanisms for set systems, i.e., scenarios where a customer needs to hire a team of agents to perform a complex task. In this setting, … We study the design of truthful mechanisms for set systems, i.e., scenarios where a customer needs to hire a team of agents to perform a complex task. In this setting, frugality [Archer&Tardos'02] provides a measure to evaluate the "cost of truthfulness", that is, the overpayment of a truthful mechanism relative to the "fair" payment. We propose a uniform scheme for designing frugal truthful mechanisms for general set systems. Our scheme is based on scaling the agents' bids using the eigenvector of a matrix that encodes the interdependencies between the agents. We demonstrate that the r-out-of-k-system mechanism and the \sqrt-mechanism for buying a path in a graph [Karlin et. al'05] can be viewed as instantiations of our scheme. We then apply our scheme to two other classes of set systems, namely, vertex cover systems and k-path systems, in which a customer needs to purchase k edge-disjoint source-sink paths. For both settings, we bound the frugality of our mechanism in terms of the largest eigenvalue of the respective interdependency matrix. We show that our mechanism is optimal for a large subclass of vertex cover systems satisfying a simple local sparsity condition. For k-path systems, while our mechanism is within a factor of k + 1 from optimal, we show that it is, in fact, optimal, when one uses a modified definition of frugality proposed in [Elkind et al.'07]. Our lower bound argument combines spectral techniques and Young's inequality, and is applicable to all set systems. As both r-out-of-k systems and single path systems can be viewed as special cases of k-path systems, our result improves the lower bounds of [Karlin et al.'05] and answers several open questions proposed in that paper.

View PDF Chat

On revenue maximization with sharp multi-unit demands

2014-12-08

Ning Chen , Xiaotie Deng , Paul W. Goldberg +1 more

View PDF Chat

Dynamics of Profit-Sharing Games

2013-08-02

John Augustine , Ning Chen , Edith Elkind +3 more

An important task in the analysis of multiagent systems is to understand how groups of selfish players can form coalitions, i.e., work together in teams. In this paper, we study … An important task in the analysis of multiagent systems is to understand how groups of selfish players can form coalitions, i.e., work together in teams. In this paper, we study the dynamics of coalition formation under bounded rationality. We consider settings whereby each team's profit is given by a submodular function and propose three profit-sharing schemes, each of which is based on the concept of marginal utility. The agents are assumed to be myopic, i.e., they keep changing teams as long as they can increase their payoff by doing so. We study the properties (such as closeness to Nash equilibrium or total profit) of the states that result after a polynomial number of such moves, and prove bounds on the price of anarchy and the price of stability of the corresponding games.

View PDF Chat

On the Approximability of Budget Feasible Mechanisms

2010-01-01

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 general submodular functions: we give a randomized mechanism with approximation ratio $7.91$ (improving the previous best-known result 112), and a deterministic mechanism with approximation ratio $8.34$. Further we study the knapsack problem, which is special submodular function, give a $2+\sqrt{2}$ approximation deterministic mechanism (improving the previous best-known result 6), and a 3 approximation randomized mechanism. We provide a similar result 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 approximation ratio of $1+\sqrt{2}$ for deterministic mechanisms and 2 for randomized mechanisms for knapsack, as well as the general submodular functions. Our lower bounds are unconditional, which do not rely on any computational or complexity assumptions.

View PDF Chat

On Nash Dynamics of Matching Market Equilibria

2011-01-01

Ning Chen , Xiaotie Deng

In this paper, we study the Nash dynamics of strategic interplays of n buyers in a matching market setup by a seller, the market maker. Taking the standard market equilibrium … In this paper, we study the Nash dynamics of strategic interplays of n buyers in a matching market setup by a seller, the market maker. Taking the standard market equilibrium approach, upon receiving submitted bid vectors from the buyers, the market maker will decide on a price vector to clear the market in such a way that each buyer is allocated an item for which he desires the most (a.k.a., a market equilibrium solution). While such equilibrium outcomes are not unique, the market maker chooses one (maxeq) that optimizes its own objective --- revenue maximization. The buyers in turn change bids to their best interests in order to obtain higher utilities in the next round's market equilibrium solution. This is an (n+1)-person game where buyers place strategic bids to gain the most from the market maker's equilibrium mechanism. The incentives of buyers in deciding their bids and the market maker's choice of using the maxeq mechanism create a wave of Nash dynamics involved in the market. We characterize Nash equilibria in the dynamics in terms of the relationship between maxeq and mineq (i.e., minimum revenue equilibrium), and develop convergence results for Nash dynamics from the maxeq policy to a mineq solution, resulting an outcome equivalent to the truthful VCG mechanism. Our results imply revenue equivalence between maxeq and mineq, and address the question that why short-term revenue maximization is a poor long run strategy, in a deterministic and dynamic setting.

View PDF Chat

Competitive Analysis via Benchmark Decomposition

2015-06-12

Ning Chen , Nick Gravin , Pinyan Lu

We propose a uniform approach for the design and analysis of prior-free competitive auctions and online auctions. Our philosophy is to view the benchmark function as a variable parameter of … We propose a uniform approach for the design and analysis of prior-free competitive auctions and online auctions. Our philosophy is to view the benchmark function as a variable parameter of the model and study a broad class of functions instead of a individual target benchmark. We consider a multitude of well-studied auction settings, and improve upon a few previous results. Multi-unit auctions. Given a β-competitive unlimited supply auction, the best previously known multi-unit auction is 2β-competitive. We design a (1+β)-competitive auction reducing the ratio from 4.84 to 3.24. These results carry over to matroid and position auctions. General downward-closed environments. We design a 6.5-competitive auction improving upon the ratio of 7.5. Our auction is noticeably simpler than the previous best one. Unlimited supply online auctions. Our analysis yields an auction with a competitive ratio of 4.12, which significantly narrows the margin of [4, 4.84] previously known for this problem.

View PDF Chat

On Revenue Maximization with Sharp Multi-Unit Demands

2012-01-01

Ning Chen , Xiaotie Deng , Paul W. Goldberg +1 more

We consider markets consisting of a set of indivisible items, and buyers that have {\em sharp} multi-unit demand. This means that each buyer $i$ wants a specific number $d_i$ of … We consider markets consisting of a set of indivisible items, and buyers that have {\em sharp} multi-unit demand. This means that each buyer $i$ wants a specific number $d_i$ of items; a bundle of size less than $d_i$ has no value, while a bundle of size greater than $d_i$ is worth no more than the most valued $d_i$ items (valuations being additive). We consider the objective of setting prices and allocations in order to maximize the total revenue of the market maker. The pricing problem with sharp multi-unit demand buyers has a number of properties that the unit-demand model does not possess, and is an important question in algorithmic pricing. We consider the problem of computing a revenue maximizing solution for two solution concepts: competitive equilibrium and envy-free pricing. For unrestricted valuations, these problems are NP-complete; we focus on a realistic special case of "correlated values" where each buyer $i$ has a valuation $v_i\qual_j$ for item $j$, where $v_i$ and $\qual_j$ are positive quantities associated with buyer $i$ and item $j$ respectively. We present a polynomial time algorithm to solve the revenue-maximizing competitive equilibrium problem. For envy-free pricing, if the demand of each buyer is bounded by a constant, a revenue maximizing solution can be found efficiently; the general demand case is shown to be NP-hard.

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.

Optimal Competitive Auctions

2014-01-01

Ning Chen , Nick Gravin , Pinyan Lu

We study the design of truthful auctions for selling identical items in unlimited supply (e.g., digital goods) to n unit demand buyers. This classic problem stands out from profit-maximizing auction … We study the design of truthful auctions for selling identical items in unlimited supply (e.g., digital goods) to n unit demand buyers. This classic problem stands out from profit-maximizing auction design literature as it requires no probabilistic assumptions on buyers' valuations and employs the framework of competitive analysis. Our objective is to optimize the worst-case performance of an auction, measured by the ratio between a given benchmark and revenue generated by the auction. We establish a sufficient and necessary condition that characterizes competitive ratios for all monotone benchmarks. The characterization identifies the worst-case distribution of instances and reveals intrinsic relations between competitive ratios and benchmarks in the competitive analysis. With the characterization at hand, we show optimal competitive auctions for two natural benchmarks. The most well-studied benchmark $\mathcal{F}^{(2)}(\cdot)$ measures the envy-free optimal revenue where at least two buyers win. Goldberg et al. [13] showed a sequence of lower bounds on the competitive ratio for each number of buyers n. They conjectured that all these bounds are tight. We show that optimal competitive auctions match these bounds. Thus, we confirm the conjecture and settle a central open problem in the design of digital goods auctions. As one more application we examine another economically meaningful benchmark, which measures the optimal revenue across all limited-supply Vickrey auctions. We identify the optimal competitive ratios to be $(\frac{n}{n-1})^{n-1}-1$ for each number of buyers n, that is $e-1$ as $n$ approaches infinity.

View PDF Chat

Competitive analysis via benchmark decomposition

2014-01-01

Ning Chen , Nick Gravin , Pinyan Lu

We propose a uniform approach for the design and analysis of prior-free competitive auctions and online auctions. Our philosophy is to view the benchmark function as a variable parameter of … We propose a uniform approach for the design and analysis of prior-free competitive auctions and online auctions. Our philosophy is to view the benchmark function as a variable parameter of the model and study a broad class of functions instead of a individual target benchmark. We consider a multitude of well-studied auction settings, and improve upon a few previous results. (1) Multi-unit auctions. Given a $\beta$-competitive unlimited supply auction, the best previously known multi-unit auction is $2\beta$-competitive. We design a $(1+\beta)$-competitive auction reducing the ratio from $4.84$ to $3.24$. These results carry over to matroid and position auctions. (2) General downward-closed environments. We design a $6.5$-competitive auction improving upon the ratio of $7.5$. Our auction is noticeably simpler than the previous best one. (3) Unlimited supply online auctions. Our analysis yields an auction with a competitive ratio of $4.12$, which significantly narrows the margin of $[4,4.84]$ previously known for this problem. A particularly important tool in our analysis is a simple decomposition lemma, which allows us to bound the competitive ratio against a sum of benchmark functions. We use this lemma in a "divide and conquer" fashion by dividing the target benchmark into the sum of simpler functions.

View PDF Chat

SOME NEW RANDOM FIXED POINT THEOREMS AND APPLICATION

2016-01-12

Ning Chen , Yang Chen , Jiqian Chen

Enlightening the Mathematical Talents of Children in Kindergarten

2006-08-01

Jiannong Shi , Ning Chen

Questions such as “Is it necessary to teach mathematics in kindergarten?” and “how to teach mathematics in kindergarten?” are controversial issues in China. According to many years experience of studying … Questions such as “Is it necessary to teach mathematics in kindergarten?” and “how to teach mathematics in kindergarten?” are controversial issues in China. According to many years experience of studying on the development of gifted children and education of young children in kindergarten the authors summarize that mathematics education in kindergarten is necessary but it should not be instructed rather should be experienced by children through touching, feeling, manipulating, playing and experiencing. Based on the law of psychological development of young children, a series of everyday activities for young children’s experiencing mathematics was designed in an experimental kindergarten. In the present presentation, the notions and experience of mathematics education in preschoolers in kindergarten will be presented and shared.

Dynamics of Profit-Sharing Games

2010-10-25

John Augustine , Ning Chen , Edith Elkind +3 more

An important task in the analysis of multiagent systems is to understand how groups of selfish players can form coalitions, i.e., work together in teams. In this paper, we study … An important task in the analysis of multiagent systems is to understand how groups of selfish players can form coalitions, i.e., work together in teams. In this paper, we study the dynamics of coalition formation under bounded rationality. We consider settings where each team's profit is given by a convex function, and propose three profit-sharing schemes, each of which is based on the concept of marginal utility. The agents are assumed to be myopic, i.e., they keep changing teams as long as they can increase their payoff by doing so. We study the properties (such as closeness to Nash equilibrium or total profit) of the states that result after a polynomial number of such moves, and prove bounds on the price of anarchy and the price of stability of the corresponding games.

Budget Feasible Mechanism Design: From Prior-Free to Bayesian

2012-03-20

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

Dynamics of Profit-Sharing Games

2010-01-01

John Augustine , Ning Chen , Edith Elkind +3 more

An important task in the analysis of multiagent systems is to understand how groups of selfish players can form coalitions, i.e., work together in teams. In this paper, we study … An important task in the analysis of multiagent systems is to understand how groups of selfish players can form coalitions, i.e., work together in teams. In this paper, we study the dynamics of coalition formation under bounded rationality. We consider settings where each team's profit is given by a convex function, and propose three profit-sharing schemes, each of which is based on the concept of marginal utility. The agents are assumed to be myopic, i.e., they keep changing teams as long as they can increase their payoff by doing so. We study the properties (such as closeness to Nash equilibrium or total profit) of the states that result after a polynomial number of such moves, and prove bounds on the price of anarchy and the price of stability of the corresponding games.

View PDF Chat

SOME NEW RANDOM FIXED POINT THEOREMS AND APPLICATION

2016-01-12

Ning Chen , Yang Chen , Jiqian Chen

Competitive Analysis via Benchmark Decomposition

2015-06-12

Ning Chen , Nick Gravin , Pinyan Lu

View PDF Chat

On revenue maximization with sharp multi-unit demands

2014-12-08

Ning Chen , Xiaotie Deng , Paul W. Goldberg +1 more

View PDF Chat

Optimal competitive auctions

2014-05-31

Ning Chen , Nick Gravin , Pinyan Lu

View PDF Chat

Optimal Competitive Auctions

2014-01-01

Ning Chen , Nick Gravin , Pinyan Lu

View PDF Chat

Competitive analysis via benchmark decomposition

2014-01-01

Ning Chen , Nick Gravin , Pinyan Lu

We propose a uniform approach for the design and analysis of prior-free competitive auctions and online auctions. Our philosophy is to view the benchmark function as a variable parameter of … We propose a uniform approach for the design and analysis of prior-free competitive auctions and online auctions. Our philosophy is to view the benchmark function as a variable parameter of the model and study a broad class of functions instead of a individual target benchmark. We consider a multitude of well-studied auction settings, and improve upon a few previous results. (1) Multi-unit auctions. Given a $\beta$-competitive unlimited supply auction, the best previously known multi-unit auction is $2\beta$-competitive. We design a $(1+\beta)$-competitive auction reducing the ratio from $4.84$ to $3.24$. These results carry over to matroid and position auctions. (2) General downward-closed environments. We design a $6.5$-competitive auction improving upon the ratio of $7.5$. Our auction is noticeably simpler than the previous best one. (3) Unlimited supply online auctions. Our analysis yields an auction with a competitive ratio of $4.12$, which significantly narrows the margin of $[4,4.84]$ previously known for this problem. A particularly important tool in our analysis is a simple decomposition lemma, which allows us to bound the competitive ratio against a sum of benchmark functions. We use this lemma in a "divide and conquer" fashion by dividing the target benchmark into the sum of simpler functions.

View PDF Chat

Dynamics of Profit-Sharing Games

2013-08-02

John Augustine , Ning Chen , Edith Elkind +3 more

View PDF Chat

Budget feasible mechanism design: from prior-free to bayesian

2012-05-19

Xiaohui Bei , Ning Chen , Nick Gravin +1 more

View PDF Chat

Budget feasible mechanism design

2012-05-19

Xiaohui Bei , Ning Chen , Nick Gravin +1 more

View PDF Chat

Budget Feasible Mechanism Design: From Prior-Free to Bayesian

2012-03-20

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

On Revenue Maximization with Sharp Multi-Unit Demands

2012-01-01

Ning Chen , Xiaotie Deng , Paul W. Goldberg +1 more

View PDF Chat

On the approximability of budget feasible mechanisms

2011-01-23

Ning Chen , Nick Gravin , Pinyan Lu

On the Approximability of Budget Feasible Mechanisms

2011-01-23

Ning Chen , Nick Gravin , Pinyan Lu

View PDF Chat

Budget Feasible Mechanism Design via Random Sampling

2011-01-01

Xiaohui Bei , Ning Chen , Nick Gravin +1 more

On Nash Dynamics of Matching Market Equilibria

2011-01-01

Ning Chen , Xiaotie Deng

View PDF Chat

Dynamics of Profit-Sharing Games

2010-10-25

John Augustine , Ning Chen , Edith Elkind +3 more

An important task in the analysis of multiagent systems is to understand how groups of selfish players can form coalitions, i.e., work together in teams. In this paper, we study … An important task in the analysis of multiagent systems is to understand how groups of selfish players can form coalitions, i.e., work together in teams. In this paper, we study the dynamics of coalition formation under bounded rationality. We consider settings where each team's profit is given by a convex function, and propose three profit-sharing schemes, each of which is based on the concept of marginal utility. The agents are assumed to be myopic, i.e., they keep changing teams as long as they can increase their payoff by doing so. We study the properties (such as closeness to Nash equilibrium or total profit) of the states that result after a polynomial number of such moves, and prove bounds on the price of anarchy and the price of stability of the corresponding games.

Frugal Mechanism Design via Spectral Techniques

2010-10-01

Ning Chen , Edith Elkind , Nick Gravin +1 more

View PDF Chat

On the Approximability of Budget Feasible Mechanisms

2010-01-01

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 general submodular functions: we give a randomized mechanism with approximation ratio $7.91$ (improving the previous best-known result 112), and a deterministic mechanism with approximation ratio $8.34$. Further we study the knapsack problem, which is special submodular function, give a $2+\sqrt{2}$ approximation deterministic mechanism (improving the previous best-known result 6), and a 3 approximation randomized mechanism. We provide a similar result 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 approximation ratio of $1+\sqrt{2}$ for deterministic mechanisms and 2 for randomized mechanisms for knapsack, as well as the general submodular functions. Our lower bounds are unconditional, which do not rely on any computational or complexity assumptions.

View PDF Chat

Dynamics of Profit-Sharing Games

2010-01-01

John Augustine , Ning Chen , Edith Elkind +3 more

An important task in the analysis of multiagent systems is to understand how groups of selfish players can form coalitions, i.e., work together in teams. In this paper, we study … An important task in the analysis of multiagent systems is to understand how groups of selfish players can form coalitions, i.e., work together in teams. In this paper, we study the dynamics of coalition formation under bounded rationality. We consider settings where each team's profit is given by a convex function, and propose three profit-sharing schemes, each of which is based on the concept of marginal utility. The agents are assumed to be myopic, i.e., they keep changing teams as long as they can increase their payoff by doing so. We study the properties (such as closeness to Nash equilibrium or total profit) of the states that result after a polynomial number of such moves, and prove bounds on the price of anarchy and the price of stability of the corresponding games.

View PDF Chat

Enlightening the Mathematical Talents of Children in Kindergarten

2006-08-01

Jiannong Shi , Ning Chen

Coauthor	Papers Together
Nick Gravin	15
Pinyan Lu	11
Edith Elkind	4
Xiaohui Bei	4
Dmitry Shiryaev	3
Angelo Fanelli	3
Xiaotie Deng	3
Paul W. Goldberg	2
John Augustine	2
Jinshan Zhang	2
John Augustine	1
Yang Chen	1
Jiqian Chen	1
Jiannong Shi	1
Fedor Petrov	1

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

Competitive Auctions for Markets with Positive Externalities

2013-01-01

Nick Gravin , Pinyan Lu

View PDF Chat

On random sampling auctions for digital goods

2009-07-06

Saeed Alaei , Azarakhsh Malekian , Aravind Srinivasan

In the context of auctions for digital goods, an interesting Random Sampling Optimal Price auction (RSOP) has been proposed by Goldberg, Hartline and Wright; this leads to a truthful mechanism. … In the context of auctions for digital goods, an interesting Random Sampling Optimal Price auction (RSOP) has been proposed by Goldberg, Hartline and Wright; this leads to a truthful mechanism. Since random sampling is a popular approach for auctions that aims to maximize the seller's revenue, this method has been analyzed further by Feige, Flaxman, Hartline and Kleinberg, who have shown that it is 15-competitive in the worst case -- which is substantially better than the previously proved bounds but still far from the conjectured competitive ratio of 4. In this paper, we prove that RSOP is indeed 4-competitive for a large class of instances in which the number λ of bidders receiving the item at the optimal uniform price, is at least 6. We also show that it is 4.68 competitive for the small class of remaining instances thus leaving a negligible gap between the lower and upper bound. Furthermore, we develop a robust version of RSOP -- one in which the seller's revenue is, with high probability, not much below its mean -- when the above parameter λ grows large. We employ a mix of probabilistic techniques and dynamic programming to compute these bounds.

View PDF Chat

Frugal and Truthful Auctions for Vertex Covers, Flows and Cuts

2010-10-01

David Kempe , Mahyar Salek , Cristopher Moore

We study truthful mechanisms for hiring a team of agents in three classes of set systems: Vertex Cover auctions, How auctions, and cut auctions. For Vertex Cover auctions, the vertices … We study truthful mechanisms for hiring a team of agents in three classes of set systems: Vertex Cover auctions, How auctions, and cut auctions. For Vertex Cover auctions, the vertices are owned by selfish and rational agents, and the auctioneer wants to purchase a vertex cover from them. For k-flow auctions, the edges are owned by the agents, and the auctioneer wants to purchase k edge-disjoint s-t paths, for given s and t. In the same setting, for cut auctions, the auctioneer wants to purchase an s-t cut. Only the agents know their costs, and the auctioneer needs to select a feasible set and payments based on bids made by the agents. We present constant-competitive truthful mechanisms for all three set systems. That is, the maximum overpayment of the mechanism is within a constant factor of the maximum overpayment of any truthful mechanism, for every set system in the class. The mechanism for Vertex Cover is based on scaling each bid by a multiplier derived from the dominant eigenvector of a certain matrix. The mechanism for k-flows prunes the graph to be minimally (k + 1)-connected, and then applies the Vertex Cover mechanism. Similarly, the mechanism for cuts contracts the graph until all s-t paths have length exactly 2, and then applies the Vertex Cover mechanism.

View PDF Chat

Budget constrained auctions with heterogeneous items

2010-06-05

Sayan Bhattacharya , Gagan Goel , Sreenivas Gollapudi +1 more

In this paper, we present the first approximation algorithms for the problem of designing revenue optimal Bayesian incentive compatible auctions when there are multiple (heterogeneous) items and when bidders have … In this paper, we present the first approximation algorithms for the problem of designing revenue optimal Bayesian incentive compatible auctions when there are multiple (heterogeneous) items and when bidders have arbitrary demand and budget constraints (and additive valuations). Our mechanisms are surprisingly simple: We show that a sequential all-pay mechanism is a 4 approximation to the revenue of the optimal ex-interim truthful mechanism with a discrete type space for each bidder, where her valuations for different items can be correlated. We also show that a sequential posted price mechanism is a O(1) approximation to the revenue of the optimal ex-post truthful mechanism when the type space of each bidder is a product distribution that satisfies the standard hazard rate condition. We further show a logarithmic approximation when the hazard rate condition is removed, and complete the picture by showing that achieving a sub-logarithmic approximation, even for regular distributions and one bidder, requires pricing bundles of items. Our results are based on formulating novel LP relaxations for these problems, and developing generic rounding schemes from first principles.

View PDF Chat

On the approximability of budget feasible mechanisms

2011-01-23

Ning Chen , Nick Gravin , Pinyan Lu

Bayesian mechanism design for budget-constrained agents

2011-06-05

Shuchi Chawla , David L. Malec , Azarakhsh Malekian

We study Bayesian mechanism design problems in settings where agents have budgets. Specifically, an agent's utility for an outcome is given by his value for the outcome minus any payment … We study Bayesian mechanism design problems in settings where agents have budgets. Specifically, an agent's utility for an outcome is given by his value for the outcome minus any payment he makes to the mechanism, as long as the payment is below his budget, and is negative infinity otherwise. This discontinuity in the utility function presents a significant challenge in the design of good mechanisms, and classical mechanisms fail to work in settings with budgets. The goal of this paper is to develop general reductions from budget-constrained Bayesian MD to unconstrained Bayesian MD with small loss in performance. We consider this question in the context of the two most well-studied objectives in mechanism design---social welfare and revenue---and present constant factor approximations in a number of settings. Some of our results extend to settings where budgets are private and agents need to be incentivized to reveal them truthfully.

View PDF Chat

Bayesian algorithmic mechanism design

2010-06-05

Jason D. Hartline , Brendan Lucier

The principal problem in algorithmic mechanism design is in merging the incentive constraints imposed by selfish behavior with the algorithmic constraints imposed by computational intractability. This field is motivated by … The principal problem in algorithmic mechanism design is in merging the incentive constraints imposed by selfish behavior with the algorithmic constraints imposed by computational intractability. This field is motivated by the observation that the preeminent approach for designing incentive compatible mechanisms, namely that of Vickrey, Clarke, and Groves; and the central approach for circumventing computational obstacles, that of approximation algorithms, are fundamentally incompatible: natural applications of the VCG approach to an approximation algorithm fails to yield an incentive compatible mechanism. We consider relaxing the desideratum of (ex post) incentive compatibility (IC) to Bayesian incentive compatibility (BIC), where truthtelling is a Bayes-Nash equilibrium (the standard notion of incentive compatibility in economics). For welfare maximization in single-parameter agent settings, we give a general black-box reduction that turns any approximation algorithm into a Bayesian incentive compatible mechanism with essentially the same approximation factor.

View PDF Chat

Envy Freedom and Prior-free Mechanism Design

2012-01-01

Nikhil R. Devanur , Jason D. Hartline , Qiqi Yan

We consider the provision of an abstract service to single-dimensional agents. Our model includes position auctions, single-minded combinatorial auctions, and constrained matching markets. When the agents' values are drawn from … We consider the provision of an abstract service to single-dimensional agents. Our model includes position auctions, single-minded combinatorial auctions, and constrained matching markets. When the agents' values are drawn from a distribution, the Bayesian optimal mechanism is given by Myerson (1981) as a virtual-surplus optimizer. We develop a framework for prior-free mechanism design and analysis. A good mechanism in our framework approximates the optimal mechanism for the distribution if there is a distribution; moreover, when there is no distribution this mechanism still performs well. We define and characterize optimal envy-free outcomes in symmetric single-dimensional environments. Our characterization mirrors Myerson's theory. Furthermore, unlike in mechanism design where there is no point-wise optimal mechanism, there is always a point-wise optimal envy-free outcome. Envy-free outcomes and incentive-compatible mechanisms are similar in structure and performance. We therefore use the optimal envy-free revenue as a benchmark for measuring the performance of a prior-free mechanism. A good mechanism is one that approximates the envy free benchmark on any profile of agent values. We show that good mechanisms exist, and in particular, a natural generalization of the random sampling auction of Goldberg et al. (2001) is a constant approximation.

View PDF Chat

Concentration inequalities using the entropy method

2003-06-12

Stéphane Boucheron , Gábor Lugosi , Pascal Massart

We investigate a new methodology, worked out by Ledoux and Massart, to prove concentration-of-measure inequalities. The method is based on certain modified logarithmic Sobolev inequalities. We provide some very simple … We investigate a new methodology, worked out by Ledoux and Massart, to prove concentration-of-measure inequalities. The method is based on certain modified logarithmic Sobolev inequalities. We provide some very simple and general ready-to-use inequalities. One of these inequalities may be considered as an exponential version of the Efron--Stein inequality. The main purpose of this paper is to point out the simplicity and the generality of the approach. We show how the new method can recover many of Talagrand's revolutionary inequalities and provide new applications in a variety of problems including Rademacher averages, Rademacher chaos, the number of certain small subgraphs in a random graph, and the minimum of the empirical risk in some statistical estimation problems.

View PDF Chat

Correlation inequalities on some partially ordered sets

1971-06-01

C.M. Fortuin , Piet Kasteleyn , J. Ginibre

View PDF Chat

Pricing Ad Slots with Consecutive Multi-unit Demand

2013-01-01

Xiaotie Deng , Paul W. Goldberg , Yang Sun +2 more

We consider the optimal pricing problem for a model of the rich media advertisement market, as well as other related applications. In this market, there are multiple buyers (advertisers), and … We consider the optimal pricing problem for a model of the rich media advertisement market, as well as other related applications. In this market, there are multiple buyers (advertisers), and items (slots) that are arranged in a line such as a banner on a website. Each buyer desires a particular number of {\em consecutive} slots and has a per-unit-quality value $v_i$ (dependent on the ad only) while each slot $j$ has a quality $q_j$ (dependent on the position only such as click-through rate in position auctions). Hence, the valuation of the buyer $i$ for item $j$ is $v_iq_j$. We want to decide the allocations and the prices in order to maximize the total revenue of the market maker. A key difference from the traditional position auction is the advertiser's requirement of a fixed number of consecutive slots. Consecutive slots may be needed for a large size rich media ad. We study three major pricing mechanisms, the Bayesian pricing model, the maximum revenue market equilibrium model and an envy-free solution model. Under the Bayesian model, we design a polynomial time computable truthful mechanism which is optimum in revenue. For the market equilibrium paradigm, we find a polynomial time algorithm to obtain the maximum revenue market equilibrium solution. In envy-free settings, an optimal solution is presented when the buyers have the same demand for the number of consecutive slots. We conduct a simulation that compares the revenues from the above schemes and gives convincing results.

View PDF Chat

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

Prior-free auctions for budgeted agents

2013-06-16

Nikhil R. Devanur , Bach Q. Ha , Jason D. Hartline

We consider prior-free auctions for revenue and welfare maximization when agents have a common budget. The abstract environments we consider are ones where there is a downward-closed and symmetric feasibility … We consider prior-free auctions for revenue and welfare maximization when agents have a common budget. The abstract environments we consider are ones where there is a downward-closed and symmetric feasibility constraint on the probabilities of service of the agents. These environments include position auctions where slots with decreasing click-through rates are auctioned to advertisers. We generalize and characterize the envy-free benchmark from Hartline and Yan [2011] to settings with budgets and characterize the optimal envy-free outcomes for both welfare and revenue. We give prior-free mechanisms that approximate these benchmarks. A building block in our mechanism is a clinching auction for position auction environments. This auction is a generalization of the multi-unit clinching auction of Dobzinski et al. [2008] and a special case of the polyhedral clinching auction of Goel et al. [2012]. For welfare maximization, we show that this clinching auction is a good approximation to the envy-free optimal welfare for position auction environments. For profit maximization, we generalize the random sampling profit extraction auction from Fiat et al. [2002] for digital goods to give a 10.0-approximation to the envy-free optimal revenue in symmetric, downward-closed environments. Even without budgets this revenue maximization question is of interest and we obtain an improved approximation bound of 7.5 (from 30.4 by Ha and Hartline [2012]).

View PDF Chat

Frugal Mechanism Design via Spectral Techniques

2010-10-01

Ning Chen , Edith Elkind , Nick Gravin +1 more

View PDF Chat

Optimal competitive auctions

2014-05-31

Ning Chen , Nick Gravin , Pinyan Lu

View PDF Chat

Sequential Posted Pricing and Multi-parameter Mechanism Design

2009-01-01

Shuchi Chawla , Jason D. Hartline , David Malec +1 more

We consider the classical mathematical economics problem of {\em Bayesian optimal mechanism design} where a principal aims to optimize expected revenue when allocating resources to self-interested agents with preferences drawn … We consider the classical mathematical economics problem of {\em Bayesian optimal mechanism design} where a principal aims to optimize expected revenue when allocating resources to self-interested agents with preferences drawn from a known distribution. In single-parameter settings (i.e., where each agent's preference is given by a single private value for being served and zero for not being served) this problem is solved [Myerson '81]. Unfortunately, these single parameter optimal mechanisms are impractical and rarely employed [Ausubel and Milgrom '06], and furthermore the underlying economic theory fails to generalize to the important, relevant, and unsolved multi-dimensional setting (i.e., where each agent's preference is given by multiple values for each of the multiple services available) [Manelli and Vincent '07]. In contrast to the theory of optimal mechanisms we develop a theory of sequential posted price mechanisms, where agents in sequence are offered take-it-or-leave-it prices. These mechanisms are approximately optimal in single-dimensional settings, and avoid many of the properties that make optimal mechanisms impractical. Furthermore, these mechanisms generalize naturally to give the first known approximations to the elusive optimal multi-dimensional mechanism design problem. In particular, we solve multi-dimensional multi-unit auction problems and generalizations to matroid feasibility constraints. The constant approximations we obtain range from 1.5 to 8. For all but one case, our posted price sequences can be computed in polynomial time.

Envy, Multi Envy, and Revenue Maximization

2009-01-01

Amos Fiat , Amiram Wingarten

View PDF Chat

A Note on the Power of Truthful Approximation Mechanisms

2009-01-01

Shahar Dobzinski

We study the power of polynomial-time truthful mechanisms comparing to polynomial time (non-truthful) algorithms. We show that there is a setting in which deterministic polynomial-time truthful mechanisms cannot guarantee a … We study the power of polynomial-time truthful mechanisms comparing to polynomial time (non-truthful) algorithms. We show that there is a setting in which deterministic polynomial-time truthful mechanisms cannot guarantee a bounded approximation ratio, but a non-truthful FPTAS exists. We also show that in the same setting there is a universally truthful mechanism that provides an approximation ratio of 2. This shows that the cost of truthfulness is unbounded. The proofs are almost standard in the field and follow from known results.

The power of randomness in bayesian optimal mechanism design

2010-06-07

Shuchi Chawla , David L. Malec , Balasubramanian Sivan

We investigate the power of randomness in the context of a fundamental Bayesian optimal mechanism design problem - a single seller aims to maximize expected revenue by allocating multiple kinds … We investigate the power of randomness in the context of a fundamental Bayesian optimal mechanism design problem - a single seller aims to maximize expected revenue by allocating multiple kinds of resources to "unit-demand" agents with preferences drawn from a known distribution. When the agents' preferences are single-dimensional Myerson's seminal work [14] shows that randomness offers no benefit - the optimal mechanism is always deterministic. In the multi-dimensional case, where each agent's preferences are given by different values for each of the available services, Briest et al.[6] recently showed that the gap between the expected revenue obtained by an optimal randomized mechanism and an optimal deterministic mechanism can be unbounded even when a single agent is offered only 4 services. However, this large gap is attained through unnatural instances where values of the agent for different services are correlated in a specific way. We show that when the agent's values involve no correlation or a specific kind of positive correlation, the benefit of randomness is only a small constant factor (4 and 8 respectively). Our model of positively correlated values (that we call the common base value model) is a natural model for unit-demand agents and items that are substitutes. Our results extend to multiple agent settings as well.

View PDF Chat

Efficient Coordination Mechanisms for Unrelated Machine Scheduling

2012-04-24

Ioannis Caragiannis

View PDF Chat

Mechanism Design without Money via Stable Matching

2011-01-01

Ning Chen , Nick Gravin , Pinyan Lu

Mechanism design without money has a rich history in social choice literature. Due to the strong impossibility theorem by Gibbard and Satterthwaite, exploring domains in which there exist dominant strategy … Mechanism design without money has a rich history in social choice literature. Due to the strong impossibility theorem by Gibbard and Satterthwaite, exploring domains in which there exist dominant strategy mechanisms is one of the central questions in the field. We propose a general framework, called the generalized packing problem (\gpp), to study the mechanism design questions without payment. The \gpp\ possesses a rich structure and comprises a number of well-studied models as special cases, including, e.g., matroid, matching, knapsack, independent set, and the generalized assignment problem. We adopt the agenda of approximate mechanism design where the objective is to design a truthful (or strategyproof) mechanism without money that can be implemented in polynomial time and yields a good approximation to the socially optimal solution. We study several special cases of \gpp, and give constant approximation mechanisms for matroid, matching, knapsack, and the generalized assignment problem. Our result for generalized assignment problem solves an open problem proposed in \cite{DG10}. Our main technical contribution is in exploitation of the approaches from stable matching, which is a fundamental solution concept in the context of matching marketplaces, in application to mechanism design. Stable matching, while conceptually simple, provides a set of powerful tools to manage and analyze self-interested behaviors of participating agents. Our mechanism uses a stable matching algorithm as a critical component and adopts other approaches like random sampling and online mechanisms. Our work also enriches the stable matching theory with a new knapsack constrained matching model.

View PDF Chat

The Biased Sampling Profit Extraction Auction

2012-01-01

Bach Q. Ha , Jason D. Hartline

We give an auction for downward-closed environments that generalizes the random sampling profit extraction auction for digital goods of Fiat et al. (2002). The mechanism divides the agents in to … We give an auction for downward-closed environments that generalizes the random sampling profit extraction auction for digital goods of Fiat et al. (2002). The mechanism divides the agents in to a market and a sample using a biased coin and attempts to extract the optimal revenue from the sample from the market. The latter step is done with the downward-closed profit extractor of Ha and Hartline (2012). The auction is a 11-approximation to the envyfree benchmark in downward-closed permutation environments. This is an improvement on the previously best known results of 12.5 for matroid and 30.4 for downward-closed permutation environments that are due to Devanur et al. (2012) and Ha and Hartline (2012), respectively.

Approximating the revenue maximization problem with sharp demands

2016-12-22

Vittorio Bilò , Michele Flammini , Gianpiero Monaco

View PDF Chat

Settling the Complexity of Local Max-Cut (Almost) Completely

2011-01-01

Robert Elsässer⋆ , Tobias Tscheuschner

View PDF Chat

Frugality ratios and improved truthful mechanisms for vertex cover

2007-06-11

Edith Elkind , Leslie Ann Goldberg , Paul W. Goldberg

In set-system auctions, there are several overlapping teams of agents, and a task that can be completed by any of these teams. The auctioneer's goal is to hire a team … In set-system auctions, there are several overlapping teams of agents, and a task that can be completed by any of these teams. The auctioneer's goal is to hire a team and pay as little as possible. Examples of this setting include shortest-path auctions and vertex-cover auctions. Recently, Karlin, Kempe and Tamir introduced a new definition of for this problem. Informally, the frugality ratio is the of the total payment of a mechanism to a desired payment bound. The captures the extent to which the mechanism overpays, relative to perceived fair cost in a truthful auction. In this paper, we propose a new truthful polynomial-time auction for the vertex cover problem and bound its ratio. We show that the solution quality is with a constant factor of optimal and the is within a constant factor of the best possible worst-case bound; this is the first auction for this problem to have these properties. Moreover, we show how to transform any truthful auction into a frugal one while preserving the approximation ratio. Also, we consider two natural modifications of the definition of Karlin et al., and we analyse the properties of the resulting payment bounds, such as monotonicity, computational hardness, and robustness with respect to the draw-resolution rule. We study the relationships between the different payment bounds, both for general set systems and for specific set-system auctions, such as path auctions and vertex-cover auctions. We use these new definitions in the proof of our main result for vertex-cover auctions via a boot-strapping technique, which may be of independent interest.

View PDF Chat

The number sense: how the mind creates mathematics

1998-03-01

Stanislas Dehaene

L'A. propose quelques observations concernant l'ouvrage de Stanislas Dehaene The number sense. How the mind creates mathematics (1997) qui explore tous les aspects de la relation entre les hommes et … L'A. propose quelques observations concernant l'ouvrage de Stanislas Dehaene The number sense. How the mind creates mathematics (1997) qui explore tous les aspects de la relation entre les hommes et les nombres : la numerosite chez les autres animaux, la numerosite et le calcul simple chez les bebes, l'histoire de l'expression du nombre dans le langage, l'histoire de la notation du nombre, le circuit neuronal necessaire pour faire de l'arithmetique et du calcul, la localisation dans le cerveau, l'ordre mathematique de l'univers, etc ... L'A. examine ici en particulier les questions portant sur la relation entre les nombres et le langage dans une perspective cognitive, puis explique ce que Dehaene entend par le sens du nombre en caracterisant les mathematiques comme une formalisation progressive de nos intuitions sur les ensembles, le nombre, l'espace, le temps et la logique

Young Children's Number Sense in China and Finland

2006-09-29

Pirjo Aunio , Markku Niemivirta , Jarkko Hautamäki +3 more

This study examined the influence of nationality, age and gender on Chinese (N = 130) and Finnish (N = 203) pre‐schoolers' number sense. Two highly correlated aspects of number sense … This study examined the influence of nationality, age and gender on Chinese (N = 130) and Finnish (N = 203) pre‐schoolers' number sense. Two highly correlated aspects of number sense were extracted: one reflecting the children's ability to organise and compare quantities (i.e. relational skills), and another pertaining to their ability to operate with number‐word sequence (i.e. counting skills). The results showed a significant age‐related gain in both aspects of number sense, whereas no gender differences were found. With respect to counting skills, the Chinese children outperformed the Finnish children irrespective of age, whereas in relation to relational skills, this was true only among the older children. Differences in language, teaching and cultural ethos are considered as alternative explanations for the findings.

Addition and subtraction by human infants

1992-08-27

Karen Wynn

Approximate revenue maximization with multiple items

2012-06-04

Sergiu Hart , Noam Nisan

Myerson's classic result provides a full description of how a seller can maximize revenue when selling a single item. We address the question of revenue maximization in the simplest possible … Myerson's classic result provides a full description of how a seller can maximize revenue when selling a single item. We address the question of revenue maximization in the simplest possible multi-item setting: two items and a single buyer who has independently distributed values for the items, and an additive valuation. In general, the revenue achievable from selling two independent items may be strictly higher than the sum of the revenues obtainable by selling each of them separately. In fact, the structure of optimal (i.e., revenue-maximizing) mechanisms for two items even in this simple setting is not understood.

View PDF Chat

Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms

2013-02-14

George Christodoulou , Kurt Mehlhorn , Evangelia Pyrga

View PDF Chat

Pricing Ad Slots with Consecutive Multi-unit Demand

2013-01-01

Xiaotie Deng , Paul W. Goldberg , Yang Sun +2 more

View PDF Chat

Frugal and Truthful Auctions for Vertex Covers, Flows, and Cuts

2009-12-17

David Kempe , Mahyar Salek , Cristopher Moore

We study truthful mechanisms for hiring a team of agents in three classes of set systems: Vertex Cover auctions, k-flow auctions, and cut auctions. For Vertex Cover auctions, the vertices … We study truthful mechanisms for hiring a team of agents in three classes of set systems: Vertex Cover auctions, k-flow auctions, and cut auctions. For Vertex Cover auctions, the vertices are owned by selfish and rational agents, and the auctioneer wants to purchase a vertex cover from them. For k-flow auctions, the edges are owned by the agents, and the auctioneer wants to purchase k edge-disjoint s-t paths, for given s and t. In the same setting, for cut auctions, the auctioneer wants to purchase an s-t cut. Only the agents know their costs, and the auctioneer needs to select a feasible set and payments based on bids made by the agents. We present constant-competitive truthful mechanisms for all three set systems. That is, the maximum overpayment of the mechanism is within a constant factor of the maximum overpayment of any truthful mechanism, for every set system in the class. The mechanism for Vertex Cover is based on scaling each bid by a multiplier derived from the dominant eigenvector of a certain matrix. The mechanism for k-flows prunes the graph to be minimally (k+1)-connected, and then applies the Vertex Cover mechanism. Similarly, the mechanism for cuts contracts the graph until all s-t paths have length exactly 2, and then applies the Vertex Cover mechanism.

Approximating the Revenue Maximization Problem with Sharp Demands

2013-12-13

Vittorio Bilò , Michele Flammini , Gianpiero Monaco

We consider the revenue maximization problem with sharp multi-demand, in which $m$ indivisible items have to be sold to $n$ potential buyers. Each buyer $i$ is interested in getting exactly … We consider the revenue maximization problem with sharp multi-demand, in which $m$ indivisible items have to be sold to $n$ potential buyers. Each buyer $i$ is interested in getting exactly $d_i$ items, and each item $j$ gives a benefit $v_{ij}$ to buyer $i$. We distinguish between unrelated and related valuations. In the former case, the benefit $v_{ij}$ is completely arbitrary, while, in the latter, each item $j$ has a quality $q_j$, each buyer $i$ has a value $v_i$ and the benefit $v_{ij}$ is defined as the product $v_i q_j$. The problem asks to determine a price for each item and an allocation of bundles of items to buyers with the aim of maximizing the total revenue, that is, the sum of the prices of all the sold items. The allocation must be envy-free, that is, each buyer must be happy with her assigned bundle and cannot improve her utility. We first prove that, for related valuations, the problem cannot be approximated to a factor $O(m^{1-\epsilon})$, for any $\epsilon>0$, unless {\sf P} = {\sf NP} and that such result is asymptotically tight. In fact we provide a simple $m$-approximation algorithm even for unrelated valuations. We then focus on an interesting subclass of instances, that do not contain buyers a priori known not being able to receive any item. For such instances, we design an interesting $2$-approximation algorithm and show that no $(2-\epsilon)$-approximation is possible for any $0<\epsilon\leq 1$, unless {\sf P} $=$ {\sf NP}. We observe that it is possible to efficiently check if an instance is proper, and if discarding useless buyers is allowed, an instance can be made proper in polynomial time, without worsening the value of its optimal solution.

Prior-free auctions for budgeted agents

2013-06-11

Nikhil R. Devanur , Bach Q. Ha , Jason D. Hartline

View PDF Chat

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.

On Profit-Maximizing Pricing for the Highway and Tollbooth Problems

2009-01-01

Khaled Elbassioni , Rajiv Raman , Saurabh Ray +1 more

View PDF Chat

A note on concentration of submodular functions

2010-05-17

J. Vondrák

We survey a few concentration inequalities for submodular and fractionally subadditive functions of independent random variables, implied by the entropy method for self-bounding functions. The power of these concentration bounds … We survey a few concentration inequalities for submodular and fractionally subadditive functions of independent random variables, implied by the entropy method for self-bounding functions. The power of these concentration bounds is that they are dimension-free, in particular implying standard deviation O(\sqrt{\E[f]}) rather than O(\sqrt{n}) which can be obtained for any 1-Lipschitz function of n variables.