論文の概要: Fairer LP-based Online Allocation

• arxiv url: http://arxiv.org/abs/2110.14621v1
• Date: Wed, 27 Oct 2021 17:45:20 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-28 15:34:39.274346
• Title: Fairer LP-based Online Allocation
• Title（参考訳）: Fairer LPベースのオンラインアロケーション
• Authors: Guanting Chen, Xiaocheng Li, Yinyu Ye
• Abstract要約: 本稿では,リニアプログラム(LP)に基づくオンラインリソース割り当て問題について考察する。 内部点LPソルバを用いて不公平な資源支出を動的に検出するフェアアルゴリズムを提案する。 提案手法は最適化インスタンスの制約としてフェアネス要件を定式化せず,アルゴリズム設計の観点からこの問題に対処する。
• 参考スコア（独自算出の注目度）: 13.478067250930101
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we consider a Linear Program (LP)-based online resource allocation problem where a decision maker accepts or rejects incoming customer requests irrevocably in order to maximize expected revenue given limited resources. At each time, a new order/customer/bid is revealed with a request of some resource(s) and a reward. We consider a stochastic setting where all the orders are i.i.d. sampled from an unknown distribution. Such formulation contains many classic applications such as the canonical (quantity-based) network revenue management problem and the Adwords problem. Specifically, we study the objective of providing fairness guarantees while maintaining low regret. Our definition of fairness is that a fair online algorithm should treat similar agents/customers similarly and the decision made for similar individuals should be consistent over time. We define a fair offline solution as the analytic center of the offline optimal solution set, and propose a fair algorithm that uses an interior-point LP solver and dynamically detects unfair resource spending. Our algorithm can control cumulative unfairness (the cumulative deviation from the online solutions to the offline fair solution) on the scale of order $O(\log(T))$, while maintaining the regret to be bounded with dependency on $T$. Our approach do not formulate the fairness requirement as a constrain in the optimization instance, and instead we address the problem from the perspective of algorithm design. We get the desirable fairness guarantee without imposing any fairness constraint, and our regret result is strong for the reason that we evaluate the regret by comparing to the original objective value.
• Abstract（参考訳）: 本稿では,リニアプログラム(LP)に基づくオンラインリソース割り当ての問題について考察する。 それぞれの時間に、いくつかのリソースと報酬の要求により、新しい注文/顧客/ビッドが明らかにされる。 我々は、すべての順序が未知の分布から標本化される確率的設定を考える。 このような定式化には、標準的(量的)ネットワーク収益管理問題やadwords問題など、多くの古典的な応用が含まれている。 具体的には,後悔度を低く保ちながら公平性を保証する目的について検討する。 公正性の定義では、公正なオンラインアルゴリズムは類似のエージェント/顧客を同じように扱うべきであり、類似の個人に対する決定は時間とともに一貫性を持つべきである。 オフライン最適解集合の分析中心としてフェアオフライン解を定義し,インテリアポイントLPソルバを用いて不公平な資源支出を動的に検出するフェアアルゴリズムを提案する。 このアルゴリズムは、o(\log(t))$のオーダースケールで累積不公平性(オンラインソリューションからオフラインフェアソリューションへの累積偏差)を制御できるが、t$への依存で境界付けられたことを後悔し続けることができる。 提案手法は最適化インスタンスの制約としてフェアネス要件を定式化せず,アルゴリズム設計の観点からこの問題に対処する。 公平性制約を課さずに望ましい公平性保証を得ることができ、我々の後悔の結果は、元の客観的値と比較して後悔を評価する理由から強いものである。

関連論文リスト

• A Primal-Dual Online Learning Approach for Dynamic Pricing of Sequentially Displayed Complementary Items under Sale Constraints [54.46126953873298]
  顧客に対して順次表示される補完アイテムの動的価格設定の問題に対処する。 各項目の価格を個別に最適化するのは効果がないため、補完項目のコヒーレントな価格ポリシーが不可欠である。 実世界のデータからランダムに生成した合成設定を用いて,我々のアプローチを実証的に評価し,制約違反や後悔の観点からその性能を比較した。
  論文  参考訳（メタデータ） (2024-07-08T09:55:31Z)
• Trading-off price for data quality to achieve fair online allocation [25.154957931903525]
  オンラインアロケーションの問題は、長期的公正なペナルティに該当すると考えられる。 両問題を共同で解き,$mathcalO(sqrtT)$で有界な後悔を示すアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-23T11:09:43Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• Offline Minimax Soft-Q-learning Under Realizability and Partial Coverage [100.8180383245813]
  オフライン強化学習(RL)のための値ベースアルゴリズムを提案する。 ソフトマージン条件下でのバニラQ関数の類似した結果を示す。 我々のアルゴリズムの損失関数は、推定問題を非線形凸最適化問題とラグランジフィケーションとしてキャストすることによって生じる。
  論文  参考訳（メタデータ） (2023-02-05T14:22:41Z)
• Online Learning under Budget and ROI Constraints via Weak Adaptivity [57.097119428915796]
  制約付きオンライン学習問題に対する既存の原始双対アルゴリズムは、2つの基本的な仮定に依存している。 このような仮定は、標準の原始双対テンプレートを弱適応的後悔最小化器で与えることによって、どのように回避できるのかを示す。 上記の2つの前提が満たされていない場合に保証される、世界の最高の保証を証明します。
  論文  参考訳（メタデータ） (2023-02-02T16:30:33Z)
• Safe Online Bid Optimization with Return-On-Investment and Budget Constraints subject to Uncertainty [87.81197574939355]
  最適化問題と学習問題の両方について検討する。 我々は、潜在的に線形な数の制約違反を犠牲にして、サブ線形後悔を保証するアルゴリズム、すなわちGCBを提供する。 より興味深いことに、我々はGCB_safe(psi,phi)というアルゴリズムを提供し、サブ線形擬似回帰と安全性w.h.p.の両方を、耐性 psi と phi を受け入れるコストで保証する。
  論文  参考訳（メタデータ） (2022-01-18T17:24:20Z)
• Online Allocation with Two-sided Resource Constraints [44.5635910908944]
  我々は,要求が順次到着する,リソース制約の低いオンラインアロケーション問題を考える。 提案手法では, リクエスト全体を知るオフライン問題に対して, 1-O (fracepsilonalpha-epsilon)$-competitive ratioを求めるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-28T02:21:06Z)
• Algorithmic Challenges in Ensuring Fairness at the Time of Decision [6.228560624452748]
  社会的文脈におけるアルゴリズムによる意思決定は、帯域幅フィードバックの下で最適化される。 最近の訴訟は、アルゴリズムによる価格設定の慣行を展開している企業を非難している。 凸最適化の文脈において、遠心自由というよく研究された公正性の概念を導入する。
  論文  参考訳（メタデータ） (2021-03-16T19:06:28Z)
• Online Apprenticeship Learning [58.45089581278177]
  見習い学習(AL)では、コスト関数にアクセスせずにマルコフ決定プロセス(MDP)が与えられます。 目標は、事前に定義されたコスト関数のセットで専門家のパフォーマンスに一致するポリシーを見つけることです。 ミラー下降型ノンレグレットアルゴリズムを2つ組み合わせることで,OAL問題を効果的に解くことができることを示す。
  論文  参考訳（メタデータ） (2021-02-13T12:57:51Z)
• The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems [7.433931244705934]
  本稿では,意思決定者に対して未知の入力モデルを用いて,各要求に対する報酬とリソース消費を生成するデータ駆動型設定について考察する。 様々な入力モデルにおいて,どの入力に直面するかを知ることなく,優れた性能が得られるアルゴリズムの一般クラスを設計する。 我々のアルゴリズムはラグランジアン双対空間で動作し、オンラインミラー降下を用いて更新される各リソースに対して双対乗算器を保持する。
  論文  参考訳（メタデータ） (2020-11-18T18:39:17Z)
• Regularized Online Allocation Problems: Fairness and Beyond [7.433931244705934]
  本稿では, 総資源消費に作用する非線形正規化器を含む変種である, 語彙化オンライン割当問題を紹介する。 この問題では、要求は時間とともに繰り返し届き、各要求に対して、意思決定者は報酬を生成しリソースを消費するアクションを取る必要があります。 目的は、資源制約を受ける加算可分な報酬と非分離可正則化器の値とを同時に最大化することである。
  論文  参考訳（メタデータ） (2020-07-01T14:24:58Z)

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

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