Automated Mechanism Design for Classification with Partial Verification
- URL: http://arxiv.org/abs/2104.05182v1
- Date: Mon, 12 Apr 2021 03:29:31 GMT
- Title: Automated Mechanism Design for Classification with Partial Verification
- Authors: Hanrui Zhang, Yu Cheng, Vincent Conitzer
- Abstract summary: We study the problem of automated mechanism design with partial verification.
We focus on truthful mechanisms in the setting where all types share the same preference over outcomes.
- Score: 64.69418921224529
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of automated mechanism design with partial verification,
where each type can (mis)report only a restricted set of types (rather than any
other type), induced by the principal's limited verification power. We prove
hardness results when the revelation principle does not necessarily hold, as
well as when types have even minimally different preferences. In light of these
hardness results, we focus on truthful mechanisms in the setting where all
types share the same preference over outcomes, which is motivated by
applications in, e.g., strategic classification. We present a number of
algorithmic and structural results, including an efficient algorithm for
finding optimal deterministic truthful mechanisms, which also implies a faster
algorithm for finding optimal randomized truthful mechanisms via a
characterization based on convexity. We then consider a more general setting,
where the principal's cost is a function of the combination of outcomes
assigned to each type. In particular, we focus on the case where the cost
function is submodular, and give generalizations of essentially all our results
in the classical setting where the cost function is additive. Our results
provide a relatively complete picture for automated mechanism design with
partial verification.
Related papers
- Detecting and Identifying Selection Structure in Sequential Data [53.24493902162797]
We argue that the selective inclusion of data points based on latent objectives is common in practical situations, such as music sequences.
We show that selection structure is identifiable without any parametric assumptions or interventional experiments.
We also propose a provably correct algorithm to detect and identify selection structures as well as other types of dependencies.
arXiv Detail & Related papers (2024-06-29T20:56:34Z) - Facility Location Games with Scaling Effects [69.28397508730046]
We take the classic facility location problem and consider a variation in which each agent's individual cost function is equal to their distance from the facility multiplied by a scaling factor.
We find results on the total and maximum cost approximation ratios achievable by strategyproof and anonymous mechanisms.
arXiv Detail & Related papers (2024-02-29T07:08:18Z) - Differentially Private Range Queries with Correlated Input Perturbation [9.169888822435757]
We propose a class of differentially private mechanisms for linear queries that leverage correlated input perturbations to achieve unbiasedness, consistency, statistical transparency, and control over utility requirements.
Our theoretical and empirical analysis demonstrates that we achieve near-optimal utility, effectively compete with other methods, and retain all the favorable statistical properties discussed earlier.
arXiv Detail & Related papers (2024-02-10T23:42:05Z) - Generating collective counterfactual explanations in score-based
classification via mathematical optimization [4.281723404774889]
A counterfactual explanation of an instance indicates how this instance should be minimally modified so that the perturbed instance is classified in the desired class.
Most of the Counterfactual Analysis literature focuses on the single-instance single-counterfactual setting.
By means of novel Mathematical Optimization models, we provide a counterfactual explanation for each instance in a group of interest.
arXiv Detail & Related papers (2023-10-19T15:18:42Z) - Refined Mechanism Design for Approximately Structured Priors via Active
Regression [50.71772232237571]
We consider the problem of a revenue-maximizing seller with a large number of items for sale to $n$ strategic bidders.
It is well-known that optimal and even approximately-optimal mechanisms for this setting are notoriously difficult to characterize or compute.
arXiv Detail & Related papers (2023-10-11T20:34:17Z) - An Algorithm and Complexity Results for Causal Unit Selection [16.307996243413967]
Unit selection problem aims to identify objects, called units, that are most likely to exhibit a desired mode of behavior when subjected to stimuli.
We propose the first exact algorithm for finding optimal units given a broad class of causal objective functions and a fully specified structural causal model.
arXiv Detail & Related papers (2023-02-28T08:46:51Z) - Stop Overcomplicating Selective Classification: Use Max-Logit [2.3677503557659705]
We tackle the problem of Selective Classification where the goal is to achieve the best performance on the desired coverages of the dataset.
Recent state-of-the-art selective methods come with architectural changes either via introducing a separate selection head or an extra abstention logit.
We present surprising results for Selective Classification by confirming that the superior performance of state-of-the-art methods is owed to training a more generalizable classifier.
arXiv Detail & Related papers (2022-06-17T22:23:11Z) - Understanding Interlocking Dynamics of Cooperative Rationalization [90.6863969334526]
Selective rationalization explains the prediction of complex neural networks by finding a small subset of the input that is sufficient to predict the neural model output.
We reveal a major problem with such cooperative rationalization paradigm -- model interlocking.
We propose a new rationalization framework, called A2R, which introduces a third component into the architecture, a predictor driven by soft attention as opposed to selection.
arXiv Detail & Related papers (2021-10-26T17:39:18Z) - Dynamic Instance-Wise Classification in Correlated Feature Spaces [15.351282873821935]
In a typical machine learning setting, the predictions on all test instances are based on a common subset of features discovered during model training.
A new method is proposed that sequentially selects the best feature to evaluate for each test instance individually, and stops the selection process to make a prediction once it determines that no further improvement can be achieved with respect to classification accuracy.
The effectiveness, generalizability, and scalability of the proposed method is illustrated on a variety of real-world datasets from diverse application domains.
arXiv Detail & Related papers (2021-06-08T20:20:36Z) - Generalization Guarantees for Multi-item Profit Maximization: Pricing,
Auctions, and Randomized Mechanisms [86.81403511861788]
We study multi-item profit when there is an underlying distribution over buyers' values.
For any set of buyers' values, profit is piecewise linear in the mechanism's parameters.
We prove new bounds for mechanism classes not yet in the sample-based mechanism design literature.
arXiv Detail & Related papers (2017-04-29T22:02:14Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.