Ceny bez závisti - Envy-free pricing

Tento článek má několik problémů. Prosím pomozte zlepšit to nebo diskutovat o těchto otázkách na internetu diskusní stránka. (Zjistěte, jak a kdy tyto zprávy ze šablony odebrat) Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Březen 2020) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) tento článek možná matoucí nebo nejasné čtenářům. Zejména potřebuje více kontextu a úvodu. Prosím, pomoz nám objasnit článek. O tom by mohla být diskuse diskusní stránka. (Březen 2020) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Ceny bez závisti je přístup ke spravedlivému rozdělování diskrétních objektů mezi lidi s různými preferencemi. Jedná se o speciální případ problému spravedlivé rozdělení položek, s následujícími rozlišovacími vlastnostmi:

• Peněžní platby jsou povoleny. Zejména je povoleno každému objektu přiřadit cenu a účtovat každé osobě celkovou cenu za předměty, které mu byly přiděleny.
• Lidé jsou považováni za kvazilineární v penězích. To znamená, že obslužný program, který agent získá ze svazku objektů, se rovná hodnotě agenta pro svazek mínus celková cena položek ve svazku.
• Přidělení by mělo být bez závisti: pro každého agenta je jeho utilita z jeho vlastního balíčku minimálně stejně velká jako utilita, kterou by mohl získat z jakéhokoli jiného možného balíčku (zejména z balíčků poskytnutých jiným agentům).
• Je povoleno ponechat některé položky nepřidělené. Je však nutné maximalizovat sociální zabezpečení a / nebo tržby prodávajícího (s výhradou závisti).

Termín vynalezl^[1] Guruwami, Hartline, Karlin, Kempe, Kenyon a McSherry. Zaměřili se na maximalizaci výnosů prodejce. Pro dvě třídy užitkových funkcí: jednotková poptávka a smýšlející, ukázali:

• Výpočet cen bez závisti pro maximalizaci výnosů prodejce je APX-tvrdé v obou případech.
• Algoritmus logaritmické aproximace výnosů v obou případech.
• Algoritmy polynomiálního času pro některé speciální případy.

Výsledky byly později rozšířeny o Maria-Florina Balcan, Avrim Blum a Yishay Mansour. Ukázali, že:^[2]

• S neomezeným počtem jednotek na položku dosahuje náhodná jednotlivá cena očekávaného výnosu v rámci logaritmického faktoru celkového sociálního zabezpečení, a to i pro agenty s Všeobecné oceňovací funkce (ani monotónní). Zejména u jednoho agenta je výnos minimálně 4 log (2m) maximálního blahobytu (kde m je počet typů položek) a pro n agenti, je to minimálně O (log (n) + protokol (m)) maximálního blahobytu.
• S omezenou dodávkou, pro subadditivní ocenění, náhodná jednotlivá cena dosahuje výnosů s faktorem 2^{O (√ (log n loglog n))} z celkového počtu sociální péče.
• Dolní mez ukazující posloupnost subaditiv (a sudých zlomkově subaditivní ) agenti, u nichž má jednotlivá cena přibližný poměr 2^{Ω (log1/4n)}
• V případě více jednotek, pokud žádný kupující nevyžaduje více než 1-ε zlomek položek, náhodná jednotlivá cena dosáhne příjmu v rámci O (log n) faktor maximálního sociálního zabezpečení.

Od té doby byl problém studován v různých variantách různými papíry.

Srovnání se souvisejícími problémy

• v alokace položek bez závisti, peněžní platby nejsou povoleny.

• V harmonie pronájmu problém, peněžní platby jsou povoleny, ale všechny objekty by měly být přiděleny (a každý agent by měl dostat přesně jeden objekt).

• A Walrasianská rovnováha je jako cena bez závisti, s dalším požadavkem, že musí být přiděleny všechny objekty s kladnou cenou (všechny nepřidělené objekty musí mít nulovou cenu).

Reference