Responzivní rozšíření sady - Responsive set extension

v teorie užitečnosti, responzivní sada (RS) rozšíření je příponou a preferenční vztah u jednotlivých položek k částečnému preferenčnímu vztahu svazků položek.

Příklad

Předpokládejme, že existují čtyři položky: ${ displaystyle w, x, y, z}$ . Osoba prohlásí, že hodnotí položky podle následujícího celková objednávka:

{ displaystyle w prec x prec y prec z}

(tj. z je jeho nejlepší položka, pak y, pak x, pak w). Za předpokladu, že položky jsou nezávislé zboží, lze odvodit, že:

{ displaystyle {w, x } prec {y, z }}

- osoba dává přednost svým dvěma nejlepším položkám před svými dvěma nejhoršími položkami;

{ displaystyle {w, y } prec {x, z }}

- osoba dává přednost svým nejlepším a třetím nejlepším předmětům před svými nejlepšími a čtvrtými nejlepšími položkami.

O svazcích však nelze odvodit nic ${ displaystyle {w, z }, {x, y }}$ ; nevíme, které z nich daná osoba preferuje.

Rozšíření RS žebříčku ${ displaystyle w prec x prec y prec z}$ je částečná objednávka na svazcích položek, který zahrnuje všechny vztahy, které lze odvodit z pořadí položek a předpokladu nezávislosti.

Definice

Nechat ${ displaystyle O}$ být souborem předmětů a ${ displaystyle preceq}$ celková objednávka dne ${ displaystyle O}$ .

Rozšíření RS o ${ displaystyle preceq}$ je částečná objednávka dne ${ displaystyle 2 ^ {O}}$ . Lze jej definovat několika ekvivalentními způsoby.^[1]

Responzivní sada (RS)

Originální rozšíření RS^[2]^:44–48 je konstruován následovně. Pro každý balíček ${ displaystyle X subseteq O}$ , každá položka ${ displaystyle x v X}$ a každou položku ${ displaystyle y notin X}$ , vezměte následující vztahy:

${ displaystyle X setminus {x } prec ^ {RS} X}$ (- přidání položky vylepší balíček)
Li ${ displaystyle x preceq y}$ pak ${ displaystyle X preceq ^ {RS} (X setminus {x }) pohár {y }}$ (- výměna položky za lepší položku balíček zlepší).

Rozšíření RS je přechodné uzavření těchto vztahů.

Pairwise dominance (PD)

Rozšíření PD je založeno na a párování položek v jednom balíčku s položkami v druhém balíčku.

Formálně, ${ displaystyle X preceq ^ {PD} Y}$ if-and-only-if there is an Injekční funkce ${ displaystyle f}$ z ${ displaystyle X}$ na ${ displaystyle Y}$ takové, že pro každého ${ displaystyle x v X}$ , ${ Displaystyle x preceq f (x)}$ .

Stochastická dominance (SD)

Přípona SD (pojmenovaná po stochastická dominance ) je definován nejen na samostatných svazcích, ale také na zlomkových svazcích (svazcích, které obsahují zlomky položek). Neformálně je svazek Y upřednostňován před svazkem X, pokud pro každou položku z obsahuje svazek Y alespoň tolik objektů, které jsou alespoň stejně dobré jako z, jako svazek X.

Formálně, ${ displaystyle X preceq ^ {SD} Y}$ iff, pro každou položku ${ displaystyle z}$ :

{ displaystyle sum _ {x succeq z} X [x] leq sum _ {y succeq z} Y [y]}

kde ${ displaystyle X [x]}$ je zlomek položky ${ displaystyle x}$ ve svazku ${ displaystyle X}$ .

Pokud jsou svazky diskrétní, má definice jednodušší formu. ${ displaystyle X preceq ^ {SD} Y}$ iff, pro každou položku ${ displaystyle z}$ :

{ displaystyle | {x v X | x succeq z } | leq | {y v Y | y succeq z } |}

Aditivní utilita (AU)

Rozšíření AU je založeno na pojmu aditivní utilita funkce.

S daným objednáním je kompatibilních mnoho různých užitných funkcí. Například objednávka ${ displaystyle w prec x prec y prec z}$ je kompatibilní s následujícími obslužnými funkcemi:

{ displaystyle u_ {1} (w) = 0, u_ {1} (x) = 2, u_ {1} (y) = 4, u_ {1} (z) = 7}

{ displaystyle u_ {2} (w) = 0, u_ {2} (x) = 2, u_ {2} (y) = 4, u_ {2} (z) = 5}

Za předpokladu, že jsou položky nezávislé, je obslužná funkce na svazcích aditivní, takže obslužnost svazku je součtem obslužných programů jejích položek, například:

{ displaystyle u_ {1} ( {w, x }) = 2, u_ {1} ( {w, z }) = 7, u_ {1} ( {x, y }) = 6 }

{ displaystyle u_ {2} ( {w, x }) = 2, u_ {2} ( {w, z }) = 5, u_ {2} ( {x, y }) = 6 }

Balíček ${ displaystyle {w, x }}$ má menší užitečnost než ${ displaystyle {w.z }}$ podle obou užitných funkcí. Navíc pro každý užitková funkce ${ displaystyle u}$ kompatibilní s výše uvedeným hodnocením:

{ displaystyle u ( {w, x })

.

Naproti tomu užitečnost svazku ${ displaystyle {w, z }}$ může být menší nebo větší než užitečnost ${ displaystyle {x, y }}$ .

To motivuje k následující definici:

${ displaystyle X preceq ^ {AU} Y}$ iff, pro každou doplňkovou užitnou funkci ${ displaystyle u}$ kompatibilní s ${ displaystyle preceq}$ :

{ displaystyle u (X) leq u (Y)}

Rovnocennost

${ displaystyle X preceq ^ {SD} Y}$ naznačuje ${ displaystyle X preceq ^ {RS} Y}$ .^[1]
${ displaystyle X preceq ^ {RS} Y}$ a ${ displaystyle X preceq ^ {PD} Y}$ jsou rovnocenné.^[1]
${ displaystyle X preceq ^ {PD} Y}$ naznačuje ${ displaystyle X preceq ^ {AU} Y}$ . Důkaz: Pokud ${ displaystyle X preceq ^ {PD} Y}$ , pak je tu injekce ${ displaystyle f: X až Y}$ takové, že pro všechny ${ displaystyle x v X}$ , ${ Displaystyle x preceq f (x)}$ . Proto pro každou užitnou funkci ${ displaystyle u}$ kompatibilní s ${ displaystyle preceq}$ , ${ Displaystyle u (x) leq u (f (x))}$ . Proto pokud ${ displaystyle u}$ je tedy aditivní ${ displaystyle u (X) leq u (Y)}$ .^[1]
Je známo že ${ displaystyle preceq ^ {AU}}$ a ${ displaystyle preceq ^ {SD}}$ jsou ekvivalentní, viz např.^[3]

Proto čtyři rozšíření ${ displaystyle preceq ^ {RS}}$ a ${ displaystyle preceq ^ {PD}}$ a ${ displaystyle preceq ^ {SD}}$ a ${ displaystyle preceq ^ {AU}}$ jsou rovnocenné.

Schopnost reagovat

Vyvolá se celková objednávka na svazky citlivý^[4]^:287–288 pokud to obsahuje responzivní sadu-rozšíření nějaké celkové objednávky na položkách. Tj. Obsahuje všechny vztahy, které jsou implikovány základním uspořádáním položek, a přidává další vztahy, které nejsou implicitně ani v rozporu.

Schopnost reagovat je naznačena aditivitou, ale ne naopak:

Pokud je celková objednávka aditivní (představovaná znakem aditivní funkce ) poté podle definice obsahuje příponu AU ${ displaystyle preceq ^ {AU}}$ , což odpovídá ${ displaystyle preceq ^ {RS}}$ , takže je responzivní.
Na druhou stranu může celková objednávka reagovat, ale ne aditivně: může obsahovat příponu AU, která je konzistentní se všemi aditivními funkcemi, ale může také obsahovat další vztahy, které jsou nekonzistentní s jedinou aditivní funkcí.

Například,^[5] Předpokládejme, že existují čtyři položky s ${ displaystyle w prec x prec y prec z}$ . Schopnost reagovat omezuje pouze vztah mezi svazky stejné velikosti s jednou nahrazenou položkou nebo svazky různých velikostí, kde malý je obsažen ve velkém. Nic o svazcích různých velikostí, které nejsou navzájem podmnožinami. Například, responzivní objednávka může mít obojí ${ displaystyle {x } prec {y, z }}$ a ${ displaystyle {w, x } succ {w, y, z }}$ . To je ale nekompatibilní s aditivitou: pro kterou neexistuje žádná aditivní funkce ${ displaystyle u ( {x })$ zatímco ${ displaystyle u ( {w, x })> u ( {w, y, z })}$ .

Viz také

Slabě aditivní

Reference

^ ^A ^b ^C ^d Aziz, Haris; Gaspers, Serge; MacKenzie, Simon; Walsh, Toby (2015). Msgstr "Spravedlivé přiřazení nedělitelných předmětů pod řadovými preferencemi". Umělá inteligence. 227: 71–92. arXiv:1312.6546. doi:10.1016 / j.artint.2015.06.002.
^ Barberà, S., Bossert, W., Pattanaik, P. K. (2004). „Hodnocení sad objektů.“ (PDF). Příručka teorie užitečnosti. Springer USA.CS1 maint: více jmen: seznam autorů (odkaz)
^ Katta, Akshay-Kumar; Sethuraman, Jay (2006). Msgstr "Řešení problému náhodného přiřazení v doméně plné preference". Journal of Economic Theory. 131 (1): 231. doi:10.1016 / j.jet.2005.05.001.
^ Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Příručka výpočetní sociální volby. Cambridge University Press. ISBN 9781107060432. (bezplatná online verze )
^ Moshe, Babaioff; Noam, Nisan; Inbal, Talgam-Cohen (2017-03-23). „Konkurenční rovnováha s nedělitelným zbožím a obecnými rozpočty“. arXiv:1703.08150. Bibcode:2017arXiv170308150B. Citovat deník vyžaduje | deník = (Pomoc)

[agmw15-1] A ^b ^C ^d Aziz, Haris; Gaspers, Serge; MacKenzie, Simon; Walsh, Toby (2015). Msgstr "Spravedlivé přiřazení nedělitelných předmětů pod řadovými preferencemi". Umělá inteligence. 227: 71–92. arXiv:1312.6546. doi:10.1016 / j.artint.2015.06.002.

[bbp04-2] Barberà, S., Bossert, W., Pattanaik, P. K. (2004). „Hodnocení sad objektů.“ (PDF). Příručka teorie užitečnosti. Springer USA.CS1 maint: více jmen: seznam autorů (odkaz)

[3] Katta, Akshay-Kumar; Sethuraman, Jay (2006). Msgstr "Řešení problému náhodného přiřazení v doméně plné preference". Journal of Economic Theory. 131 (1): 231. doi:10.1016 / j.jet.2005.05.001.

[handbook-4] Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Příručka výpočetní sociální volby. Cambridge University Press. ISBN 9781107060432. (bezplatná online verze )

[5] Moshe, Babaioff; Noam, Nisan; Inbal, Talgam-Cohen (2017-03-23). „Konkurenční rovnováha s nedělitelným zbožím a obecnými rozpočty“. arXiv:1703.08150. Bibcode:2017arXiv170308150B. Citovat deník vyžaduje | deník = (Pomoc)

[1]

[2]

[3]

[4]

[5]