論文の概要: Automated Mechanism Design for Classification with Partial Verification
- arxiv url: http://arxiv.org/abs/2104.05182v1
- Date: Mon, 12 Apr 2021 03:29:31 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-14 04:25:27.924739
- Title: Automated Mechanism Design for Classification with Partial Verification
- Title（参考訳）: 部分検証による分類の自動機構設計
- Authors: Hanrui Zhang, Yu Cheng, Vincent Conitzer
- Abstract要約: 部分検証による自動機構設計の問題点について検討する。
私たちは、すべてのタイプが結果よりも同じ好みを共有する設定における真実のメカニズムに焦点を当てています。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: そこで本研究では,各型が (他の型よりも) 制限された型のみを報告できる部分的検証による自動機構設計の問題について検討する。
啓示原理が必ずしも成り立たない場合や、型が極端に異なる好みを持つ場合の硬さを証明します。
これらの難易度の結果を踏まえて、全ての型が結果に対して同じ好みを共有している設定における真理的なメカニズムに焦点を当てる。
本研究では, 最適決定論的真理機構を求める効率的なアルゴリズムを含む, アルゴリズム的, 構造的結果をいくつか提示し, 凸性に基づくキャラクタリゼーションにより, 最適ランダム化真理機構を求めるためのより高速なアルゴリズムを提案する。
次に、主のコストが各型に割り当てられた結果の組み合わせの関数であるより一般的な設定を考える。
特に、コスト関数が部分モジュラーな場合に着目し、コスト関数が加法的となる古典的な設定において、本質的に全ての結果の一般化を与える。
本結果は,部分検証による自動機構設計のための比較的完全な画像を提供する。
関連論文リスト
- Detecting and Identifying Selection Structure in Sequential Data [53.24493902162797]
我々は,音楽のシーケンスなどの実践的な状況において,潜在目的に基づくデータポイントの選択的包摂が一般的である,と論じる。
選択構造はパラメトリックな仮定や介入実験なしで識別可能であることを示す。
また、他の種類の依存関係と同様に、選択構造を検知し、識別するための証明可能な正当性アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-29T20:56:34Z) - Facility Location Games with Scaling Effects [69.28397508730046]
古典的な施設配置問題を考慮し、各エージェントの個々のコスト関数が、スケーリング係数によって乗算された施設からの距離と等しくなる変動を考察する。
戦略と匿名のメカニズムによって達成できる総コストと最大コストの近似比について結果が得られた。
論文 参考訳（メタデータ） (2024-02-29T07:08:18Z) - Differentially Private Range Queries with Correlated Input Perturbation [9.169888822435757]
本稿では,線形クエリに対して,不偏性,一貫性,統計的透明性,ユーティリティ要件に対する制御を実現するために,相関入力摂動を利用した微分プライベートなメカニズムのクラスを提案する。
我々の理論的および実証的な分析は、我々はほぼ最適の効用を達成し、他の方法と効果的に競合し、議論された全ての好ましい統計特性を維持できることを示す。
論文 参考訳（メタデータ） (2024-02-10T23:42:05Z) - Generating collective counterfactual explanations in score-based
classification via mathematical optimization [4.281723404774889]
インスタンスの反実的な説明は、このインスタンスを最小限に修正して、摂動インスタンスを望ましいクラスに分類する方法を示している。
カウンターファクト・アナリティクスの文献の多くは、単一インスタンスの単一カウントファクト・セッティングに焦点を当てている。
新規な数学的最適化モデルにより、興味ある群における各インスタンスに対する対実的説明を提供する。
論文 参考訳（メタデータ） (2023-10-19T15:18:42Z) - Refined Mechanism Design for Approximately Structured Priors via Active
Regression [50.71772232237571]
我々は、大量の商品を戦略的入札者に販売する収益を最大化する販売業者の問題を考える。
この設定の最適かつほぼ最適のメカニズムは、特徴付けや計算が難しいことで有名である。
論文 参考訳（メタデータ） (2023-10-11T20:34:17Z) - An Algorithm and Complexity Results for Causal Unit Selection [16.307996243413967]
単位選択問題は、刺激を受ける際に望ましい振る舞いを示す可能性が最も高い、単位と呼ばれる物体を特定することを目的としている。
本稿では,幅広い因果的目的関数のクラスと完全に定義された構造因果的モデルに与えられた最適単位を求めるための,最初の正確なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-28T08:46:51Z) - Stop Overcomplicating Selective Classification: Use Max-Logit [2.3677503557659705]
我々は、データセットの望ましいカバレッジで最高のパフォーマンスを達成することを目標とする選択分類の問題に取り組む。
最近の最先端の選択手法は、別個のセレクションヘッドを導入するか、余分な禁忌ロジットを導入することによってアーキテクチャの変更が伴う。
我々は,より一般化可能な分類器の訓練に,最先端手法の優れた性能を負うことを確認することで,選択分類の驚くべき結果を示す。
論文 参考訳（メタデータ） (2022-06-17T22:23:11Z) - Understanding Interlocking Dynamics of Cooperative Rationalization [90.6863969334526]
選択的合理化(Selective rationalization)は、ニューラルネットワークの出力を予測するのに十分な入力の小さなサブセットを見つけることによって、複雑なニューラルネットワークの予測を説明する。
このような合理化パラダイムでは,モデルインターロックという大きな問題が浮かび上がっている。
A2Rと呼ばれる新しい合理化フレームワークを提案し、アーキテクチャに第3のコンポーネントを導入し、選択とは対照的にソフトアテンションによって駆動される予測器を提案する。
論文 参考訳（メタデータ） (2021-10-26T17:39:18Z) - Dynamic Instance-Wise Classification in Correlated Feature Spaces [15.351282873821935]
典型的な機械学習環境では、すべてのテストインスタンスの予測は、モデルトレーニング中に発見された機能の共通サブセットに基づいている。
それぞれのテストインスタンスに対して個別に評価する最適な特徴を順次選択し、分類精度に関して更なる改善が得られないことを判断すると、選択プロセスが終了して予測を行う新しい手法を提案する。
提案手法の有効性, 一般化性, 拡張性について, 多様なアプリケーション領域の様々な実世界のデータセットで説明する。
論文 参考訳（メタデータ） (2021-06-08T20:20:36Z) - Generalization Guarantees for Multi-item Profit Maximization: Pricing,
Auctions, and Randomized Mechanisms [86.81403511861788]
購入者の価値に根ざした分布が存在する場合のマルチイテム利益について検討する。
購入者の値の任意のセットに対して、利益はメカニズムのパラメーターにおいて断片的に線形である。
我々は、まだサンプルベースのメカニズム設計文献にはないメカニズムクラスに対する新しい境界を証明した。
論文 参考訳（メタデータ） (2017-04-29T22:02:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。