ケーキ切断を越えて:均質な分割可能商品の配分【JST・京大機械翻訳】

Caragiannis Ioannis; Gkatzelis Vasilis; Psomas Alexandros; Schoepflin Daniel

プレプリント

J-GLOBAL ID：202202216196546801 整理番号：22P0026899

ケーキ切断を越えて:均質な分割可能商品の配分【JST・京大機械翻訳】

Beyond Cake Cutting: Allocating Homogeneous Divisible Goods

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (4件)： , , ,
資料名：
発行年： 2022年01月12日プレプリントサーバーでの情報更新日： 2022年01月12日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

「ケーキ切断」として知られる公正な分割問題は,数十年にわたる複数の論文の焦点であった。研究のこのラインにおける最も顕著な問題は,Robertson-Webbクエリモデルにおける無 envな結果の計算のクエリ複雑性を結合させることであった。しかし,この問題の複雑性の根は幾分人工的である:エージェントの値が「ケーキ」の異なる部分にわたって付加的であると仮定するが,各部品内で無限に複雑である。これは,ケークが均一な商品の有限収集を表す,ほとんどの動機付け例において非現実的である。これらのアプリケーションをより正確に捉える公正な分割モデルを導入することによって,この問題に取り組む:与えられた良好からエージェント利得が受信する良い値だけに依存するが,これは,この量の任意の関数であり,エージェントが標準ケーキ切断を超える選好を表現できるようにする。このモデルにおいて,著者らは,ちょうど無 envであるだけでなく,すべての無環境割当の中で,近似的にパレート最適である計算割当のクエリ複雑性を研究した。新しいフローベースアプローチを用いて,著者らは,線形プログラムを解くために著者らの問題を減らす,制約の多項式数を通して,ランダム化割当の事後実現可能性を符号化できることを示した。【JST・京大機械翻訳】

, , , , , , , ,
, , , , 【Automatic Indexing@JST】

その他のオペレーションズリサーチの手法 , 人工知能 , データベースシステム

, ,

前のページに戻る