区分定数評価

区分定数評価は、土地などの連続的な資源に対するエージェントの効用を表す関数の一種です。これは、資源が有限個の領域に分割可能であり、各領域においてエージェントの価値密度が一定である場合に発生します。区分均一評価は、すべての領域で定数が同一である区分定数評価です。

区分定数と区分均一評価は、公平なケーキカットのアルゴリズムにおいて特に有用である。^{[1] [2] [3] [4]}

正式な定義

集合Cで表される資源が存在する。資源に対する評価は連続測度 として定義される。測度Vは値密度関数で表すことができる。値密度関数は、資源の各点に実数値を割り当てる。Cの各部分集合Xの測度Vは、 vをX上で積分したものである。 ${\displaystyle V:2^{C}\to \mathbb {R} }$ ${\displaystyle v:C\to \mathbb {R} }$

評価値Vは、対応する値密度関数v が区分定数関数である場合、区分定数と呼ばれます。言い換えれば、リソースCが有限個の領域C ₁ ,..., C _kに分割され、 1,..., k内の各jについて、 C _j内の関数vが定数U _jに等しいということになります。

評価Vは、定数がすべての領域で同じである場合、つまり、1,..., k内の各jに対して、 C _j内の関数v が定数Uに等しい場合、区分的に均一であると呼ばれます。

一般化

区分線形評価は区分定数評価の一般化であり、各領域jの値密度は線形関数a _j x + b _jとなります (区分定数は、すべてのjに対してa _j =0 となる特殊なケースに対応します)。

参考文献

1. Aziz, Haris; Ye, Chun (2014). 「区分定数および区分一様評価のためのケーキカットアルゴリズム」 Liu, Tie-Yan, Qi, Qi, Ye, Yinyu (編). Web and Internet Economics . Lecture Notes in Computer Science. Vol. 8877. Cham: Springer International Publishing. pp.  1– 14. doi :10.1007/978-3-319-13129-0_1. ISBN 978-3-319-13129-0. S2CID  18365892。
2. Cohler, Yuga J.; Lai, John K.; Parkes, David C.; Procaccia, Ariel D. (2011-08-04). 「嫉妬のない最適なケーキカット」.第25回AAAI人工知能会議. 25 : 626–631 . doi : 10.1609/aaai.v25i1.7874 . S2CID  5234366.
3. Brams, Steven; Feldman, Michal; Lai, John; Morgenstern, Jamie ; Procaccia, Ariel (2012). 「Maxsum Fair Cake Divisionsについて」. AAAI人工知能会議論文集. 26 (1): 1285– 1291. doi : 10.1609/aaai.v26i1.8237 . ISSN  2374-3468. S2CID  13013907.
4. Menon, Vijay; Larson, Kate (2017-05-17). 「決定論的、戦略証明可能、そして公平なケーキカット」arXiv : 1705.06306 [cs.GT].