論文の概要: Probabilistic Serial Mechanism for Multi-Type Resource Allocation

• arxiv url: http://arxiv.org/abs/2004.12062v1
• Date: Sat, 25 Apr 2020 05:38:06 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-09 22:12:16.513155
• Title: Probabilistic Serial Mechanism for Multi-Type Resource Allocation
• Title（参考訳）: 多型資源配分の確率的シリアルメカニズム
• Authors: Xiaoxi Guo, Sujoy Sikdar, Haibin Wang, Lirong Xia, Yongzhi Cao, Hanpin Wang
• Abstract要約: 既存の多型確率シリアル (MPS) 機構は, より高効率なレキシ効率の概念を満足することを示す。 また,MPSはレキシミンの最適性とアイテムワイドの順序性の両方によって特徴付けられることも証明した。
• 参考スコア（独自算出の注目度）: 32.93710648011737
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In multi-type resource allocation (MTRA) problems, there are p $\ge$ 2 types of items, and n agents, who each demand one unit of items of each type, and have strict linear preferences over bundles consisting of one item of each type. For MTRAs with indivisible items, our first result is an impossibility theorem that is in direct contrast to the single type (p = 1) setting: No mechanism, the output of which is always decomposable into a probability distribution over discrete assignments (where no item is split between agents), can satisfy both sd-efficiency and sd-envy-freeness. To circumvent this impossibility result, we consider the natural assumption of lexicographic preference, and provide an extension of the probabilistic serial (PS), called lexicographic probabilistic serial (LexiPS).We prove that LexiPS satisfies sd-efficiency and sd-envy-freeness, retaining the desirable properties of PS. Moreover, LexiPS satisfies sd-weak-strategyproofness when agents are not allowed to misreport their importance orders. For MTRAs with divisible items, we show that the existing multi-type probabilistic serial (MPS) mechanism satisfies the stronger efficiency notion of lexi-efficiency, and is sd-envy-free under strict linear preferences, and sd-weak-strategyproof under lexicographic preferences. We also prove that MPS can be characterized both by leximin-ptimality and by item-wise ordinal fairness, and the family of eating algorithms which MPS belongs to can be characterized by no-generalized-cycle condition.
• Abstract（参考訳）: マルチタイプリソース割り当て(MTRA)問題では、p$\ge$2のアイテムとnエージェントがあり、それぞれが各タイプのアイテムの1つのユニットを要求し、各タイプの1つのアイテムからなるバンドルよりも厳密な線形嗜好を持つ。 非可分な項目を持つ MTRA に対して、最初の結果は単型 (p = 1) の設定と直接対照的な不合理性定理である: メカニズムなし、その出力は常に離散代入上の確率分布に分解可能であり(エージェント間でアイテムが分割されない)、sd-効率とsd-envy-freenessの両方を満たすことができる。 この不可能性を回避すべく,辞書選好の自然な仮定を考察し,確率的連続 (ps) の拡張として lexicographic probabilistic serial (lexips) を提案する。 lexipsがsd効率とsd-envy-freenessを満足し、psの望ましい特性を保っていることを証明した。 さらにlexipsは、エージェントが彼らの重要な命令を誤って報告できない場合、sd-weak-strategyproofnessを満たす。 分割可能な項目を持つmtraに対して,既存のマルチタイプ確率直列(mps)機構はレキシ効率のより強力な効率概念を満足し,厳密な線形選好下ではsd-envyフリーであり,辞書選好下ではsd-weak-strategyproofであることを示す。 また,MPSはレキシミン最適性とアイテムワイドの順序性の両方で特徴付けることができ,MPSに属する摂食アルゴリズムのファミリーは,非一般化サイクル条件で特徴付けることができることを示した。

関連論文リスト

• OD-Stega: LLM-Based Near-Imperceptible Steganography via Optimized Distributions [7.611860976107124]
  本研究では,Large Language Modelが算術符号デコーダを駆動してステゴテキストを生成する,隠蔽型ステガノグラフィについて考察する。 効率的な方法は、秘密のメッセージビットをできるだけ少数の言語トークンに埋め込む必要がある。
  論文  参考訳（メタデータ） (2024-10-06T01:30:45Z)
• Bounded and Unbiased Composite Differential Privacy [25.427802467876248]
  差分プライバシ(DP)の目的は、隣接する2つのデータベース間で区別できない出力分布を生成することにより、プライバシを保護することである。 既存のソリューションでは、後処理やトランケーション技術を使ってこの問題に対処しようとしている。 本稿では,合成確率密度関数を用いて有界および非偏りの出力を生成する新しい微分プライベート機構を提案する。
  論文  参考訳（メタデータ） (2023-11-04T04:43:47Z)
• Tuning Pre-trained Model via Moment Probing [62.445281364055795]
  本稿では,LP の可能性を探るため,新しい Moment Probing (MP) 法を提案する。 MPは、最終特徴の平均に基づいて線形分類ヘッドを実行する。 当社のMPはLPを著しく上回り、トレーニングコストの低い相手と競争しています。
  論文  参考訳（メタデータ） (2023-07-21T04:15:02Z)
• Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coverage [15.858892479232656]
  頑健なオフライン強化学習(ロバストオフラインRL)について検討する。 我々は、Douubly Pessimistic Model-based Policy Optimization(P2MPO$)と呼ばれる汎用アルゴリズムフレームワークを提案する。 P2MPO$は$tildemathcalO(n-1/2)$コンバーゼンスレートで、$n$はデータセットサイズである。
  論文  参考訳（メタデータ） (2023-05-16T17:58:05Z)
• Pseudo-Spherical Contrastive Divergence [119.28384561517292]
  エネルギーベースモデルの最大学習確率を一般化するために,擬球面コントラスト分散(PS-CD)を提案する。 PS-CDは難解な分割関数を避け、学習目的の一般化されたファミリーを提供する。
  論文  参考訳（メタデータ） (2021-11-01T09:17:15Z)
• PSD Representations for Effective Probability Models [117.35298398434628]
  最近提案された非負関数に対する正半定値(PSD)モデルがこの目的に特に適していることを示す。 我々はPSDモデルの近似と一般化能力の両方を特徴付け、それらが強い理論的保証を享受していることを示す。 本研究では,PSDモデルの密度推定,決定理論,推論への応用への道を開く。
  論文  参考訳（メタデータ） (2021-06-30T15:13:39Z)
• Probabilistic Generating Circuits [50.98473654244851]
  効率的な表現のための確率的生成回路(PGC)を提案する。 PGCは、非常に異なる既存モデルを統一する理論的なフレームワークであるだけでなく、現実的なデータをモデル化する大きな可能性も示している。 我々はPCとDPPの単純な組み合わせによって簡単に仮定されない単純なPGCのクラスを示し、一連の密度推定ベンチマークで競合性能を得る。
  論文  参考訳（メタデータ） (2021-02-19T07:06:53Z)
• A Unified Joint Maximum Mean Discrepancy for Domain Adaptation [73.44809425486767]
  本論文は,最適化が容易なjmmdの統一形式を理論的に導出する。 統合JMMDから、JMMDは分類に有利な特徴ラベル依存を低下させることを示す。 本稿では,その依存を促進する新たなmmd行列を提案し,ラベル分布シフトにロバストな新しいラベルカーネルを考案する。
  論文  参考訳（メタデータ） (2021-01-25T09:46:14Z)
• Information-theoretic Feature Selection via Tensor Decomposition and Submodularity [38.05393186002834]
  本稿では,全ての変数の結合PMFの低ランクテンソルモデルを導入し,複雑性を緩和し,与えられた特徴量の分類性能を最大化する手法として間接的ターゲットを提案する。 原目標変数の代わりにネイブベイズモデルの潜伏変数を間接的に予測することにより、濃度制約を受ける単調部分モジュラ函数として特徴選択問題を定式化することができる。
  論文  参考訳（メタデータ） (2020-10-30T10:36:46Z)
• Exact and Approximation Algorithms for Sparse PCA [1.7640556247739623]
  本稿では,MISDP(MISDP)とMISDP(MISDP)について述べる。 次に、それらの連続緩和値の理論的最適性ギャップを分析し、それらが最先端の値よりも強いことを証明する。 市販の解法は一般にMISDPを解くのが難しいため,MISDPと同等の大きさのMILP(mixed-integer linear program)を用いてSPCAを任意の精度で近似する。
  論文  参考訳（メタデータ） (2020-08-28T02:07:08Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。