Arrow Research search

Author name cluster

Ning Chen 0005

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers
1 author row

Possible papers

7

STOC Conference 2013 Conference Paper

On the complexity of trial and error

  • Xiaohui Bei
  • Ning Chen 0005
  • Shengyu Zhang 0002

Motivated by certain applications from physics, biochemistry, economics, and computer science in which the objects under investigation are unknown or not directly accessible because of various limitations, we propose a trial-and-error model to examine search problems in which inputs are unknown . More specifically, we consider constraint satisfaction problems ⋀ i C i , where the constraints C i are hidden, and the goal is to find a solution satisfying all constraints. We can adaptively propose a candidate solution (i.e., trial ), and there is a verification oracle that either confirms that it is a valid solution, or returns the index i of a violated constraint (i.e., error ), with the exact content of C i still hidden. We studied the time and trial complexities of a number of natural CSPs, summarized as follows. On one hand, despite the seemingly very little information provided by the oracle, efficient algorithms do exist for Nash, Core, Stable Matching, and SAT problems, whose unknown-input versions are shown to be as hard as the corresponding known-input versions up to a factor of polynomial. The techniques employed vary considerably, including, e.g., order theory and the ellipsoid method with a strong separation oracle. On the other hand, there are problems whose complexities are substantially increased in the unknown-input model. In particular, no time-efficient algorithms exist for Graph Isomorphism and Group Isomorphism (unless PH collapses or P = NP). The proofs use quite nonstandard reductions, in which an efficient simulator is carefully designed to simulate a desirable but computationally unaffordable oracle. Our model investigates the value of input information, and our results demonstrate that the lack of input information can introduce various levels of extra difficulty. The model accommodates a wide range of combinatorial and algebraic structures, and exhibits intimate connections with (and hopefully can also serve as a useful supplement to) certain existing learning and complexity theories.

Details

SODA Conference 2011 Conference Paper

On the Approximability of Budget Feasible Mechanisms

  • Ning Chen 0005
  • Nikolai 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 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.

Details

FOCS Conference 2010 Conference Paper

Frugal Mechanism Design via Spectral Techniques

  • Ning Chen 0005
  • Edith Elkind
  • Nikolai Gravin
  • Fedor Petrov 0001

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 [2] 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 √-mechanism for buying a path in a graph [18] 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, our mechanism is within a factor of k + 1 from optimal; moreover, we show that it is, in fact, optimal, when one uses a modified definition of frugality proposed in [10]. 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 [18] and answers several open questions proposed in [18].

Details