論文の概要: Reforming an Envy-Free Matching
- arxiv url: http://arxiv.org/abs/2207.02641v1
- Date: Wed, 6 Jul 2022 13:03:49 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-07 19:04:47.660724
- Title: Reforming an Envy-Free Matching
- Title(参考訳): ウィキフリーマッチングの改革
- Authors: Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke
Kobayashi, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki
- Abstract要約: 我々は,各エージェントが単一項目を割り当てられたときに,うらやましのないマッチングを再構築する問題を考察する。
我々は,エージェントの項目を,エージェントが好む指定されていない項目と交換する操作を考慮し,この操作は別のうらやましのないマッチングをもたらす。
- 参考スコア(独自算出の注目度): 3.615389896666528
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of reforming an envy-free matching when each agent is
assigned a single item. Given an envy-free matching, we consider an operation
to exchange the item of an agent with an unassigned item preferred by the agent
that results in another envy-free matching. We repeat this operation as long as
we can. We prove that the resulting envy-free matching is uniquely determined
up to the choice of an initial envy-free matching, and can be found in
polynomial time. We call the resulting matching a reformist envy-free matching,
and then we study a shortest sequence to obtain the reformist envy-free
matching from an initial envy-free matching. We prove that a shortest sequence
is computationally hard to obtain even when each agent accepts at most four
items and each item is accepted by at most three agents. On the other hand, we
give polynomial-time algorithms when each agent accepts at most three items or
each item is accepted by at most two agents. Inapproximability and
fixed-parameter (in)tractability are also discussed.
- Abstract(参考訳): 各エージェントが1つのアイテムを割り当てるときに、エンビーフリーマッチングを改革する問題を考える。
エンビーフリーマッチングが与えられた場合、エージェントのアイテムを別のエンビーフリーマッチングをもたらすエージェントが好む未割り当てアイテムと交換する操作を考える。
私たちはできる限りこの手術を繰り返します。
結果のenvy-freeマッチングは、初期envy-freeマッチングの選択によって一意に決定され、多項式時間で見つけることができることを示す。
結果として得られたマッチングを,改革的アンビフリーマッチングと呼び,その後最短シーケンスを研究して,最初のアンビフリーマッチングから改革的アンビフリーマッチングを得る。
各エージェントが最大4項目を受理し、各アイテムが少なくとも3つのエージェントによって受理された場合でも、最も短いシーケンスは計算的に取得しにくいことが証明される。
一方,各エージェントが最大3項目を受け入れるか,あるいは各アイテムが少なくとも2つのエージェントによって受け入れられる場合,多項式時間アルゴリズムを与える。
近似可能性と固定パラメータ(in)引き込み可能性についても論じる。
関連論文リスト
- Are Bounded Contracts Learnable and Approximately Optimal? [8.121834515103243]
本稿では,主エージェントが契約を用いてプロジェクトに取り組む動機付けを行う,主エージェント問題の隠れアクションモデルについて考察する。
本研究では,有界決済契約が学習可能か,ほぼ最適かを検討する。
論文 参考訳(メタデータ) (2024-02-22T12:19:19Z) - Pure Exploration under Mediators' Feedback [63.56002444692792]
マルチアームバンディット(Multi-armed bandits)は、各インタラクションステップにおいて、学習者が腕を選択し、報酬を観察する、シーケンシャルな意思決定フレームワークである。
本稿では,学習者が仲介者の集合にアクセスできるシナリオについて考察する。
本稿では,学習者には仲介者の方針が知られていると仮定して,最適な腕を発見するための逐次的意思決定戦略を提案する。
論文 参考訳(メタデータ) (2023-08-29T18:18:21Z) - On the Complexity of Multi-Agent Decision Making: From Learning in Games
to Partial Monitoring [105.13668993076801]
マルチエージェント強化学習(MARL)理論における中心的な問題は、構造条件やアルゴリズムの原理がサンプル効率の学習保証につながるかを理解することである。
本稿では,複数のエージェントを用いた対話型意思決定のための一般的な枠組みとして,この問題について考察する。
マルチエージェント意思決定における統計的複雑性を特徴付けることは、単一エージェント決定の統計的複雑性を特徴付けることと等価であることを示す。
論文 参考訳(メタデータ) (2023-05-01T06:46:22Z) - Doubly Adversarial Federated Bandits [7.23389716633927]
本稿では,複数のエージェントが通信ネットワークを介して協調する,非確率的フェデレーション型多武装バンディット問題について検討する。
我々のアルゴリズムは、Cesa-Bianchi et alで提案されたオープンな質問に対して肯定的な答えを与える。
論文 参考訳(メタデータ) (2023-01-22T22:36:43Z) - Thou Shalt not Pick all Items if Thou are First: of Strategyproof and
Fair Picking Sequences [7.2834950390171205]
受信した項目数と順序の優先順位のバランスをとる方法について検討する。
パラメータの有意義な選択については、最適なシーケンスを簡単な方法で計算できることが示される。
論文 参考訳(メタデータ) (2023-01-11T13:04:51Z) - The Dichotomous Affiliate Stable Matching Problem: Approval-Based
Matching with Applicant-Employer Relations [27.388757379210034]
本稿では,DASM問題(Dichotomous Affiliate Stable Matching)について紹介する。
その結果は,(1)実世界のマッチングランキングが仮定された評価関数に従うことを示すために人間による研究,(2)そのような解を見つけるための効率的で実装が容易なアルゴリズムを提供することによって,常に安定した解が存在することを証明し,(3)線形プログラミングに基づくアプローチと比較して,アルゴリズムの有効性を実験的に検証する。
論文 参考訳(メタデータ) (2022-02-22T18:56:21Z) - Deep Probabilistic Graph Matching [72.6690550634166]
本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。
提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
論文 参考訳(メタデータ) (2022-01-05T13:37:27Z) - On the Expressivity of Markov Reward [89.96685777114456]
本稿では,エージェントが実行するタスクをキャプチャする手段として,報酬の表現性を理解することを目的としている。
本研究は,(1)許容される行動の集合,(2)行動上の部分順序,(3)軌道上の部分順序の3つの新しい抽象概念「タスク」について考察する。
論文 参考訳(メタデータ) (2021-11-01T12:12:16Z) - Multi-agent Policy Optimization with Approximatively Synchronous
Advantage Estimation [55.96893934962757]
マルチエージェントシステムでは、異なるエージェントの警察を共同で評価する必要がある。
現在の方法では、バリュー関数やアドバンテージ関数は非同期に評価される対実関節アクションを使用する。
本研究では,近似的に同期する利点推定を提案する。
論文 参考訳(メタデータ) (2020-12-07T07:29:19Z) - Jealousy-freeness and other common properties in Fair Division of Mixed
Manna [2.28438857884398]
我々は、不特定項目をエージェントに割り当てる公平な区分について考察する。
エージェントに良く、他の人に悪いアイテムを区別します。
論文 参考訳(メタデータ) (2020-04-23T21:39:12Z) - Tight Lower Bounds for Combinatorial Multi-Armed Bandits [72.56064196252498]
Combinatorial Multi-Armed Bandit 問題は、エージェントが各ラウンドで一組の腕を選択する、シーケンシャルな意思決定問題である。
最近提案されたGini重み付き滑らか度パラメータが単調報酬関数の下限を決定することを示す。
論文 参考訳(メタデータ) (2020-02-13T08:53:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。