Abstrakt. Vi studerar den avund gratis prissättning problem som en säljare som vill maximera intäkterna genom att sätta priser för buntar av objekt. I enlighet med standardanvändning [9] [10] definierar vi en tilldelning/prissättning för att vara avundsfri om ingen agent vill ersätta hennes tilldelning (och prissättning) med en annan agents. Om det finns ett obegränsat utbud av objekt och agenter är enkelsinnade så visar vi att hitta intäkter maximerande avund gratis tilldelning / prissättning kan lösas i polynom tid genom att minska det till en instans av viktade oberoende satt på en perfekt graf. Vi betraktar också en generalisering av avundsfriheten. Vi definierar en tilldelning/prissättning som multiavundsfri om ingen agent vill ersätta hennes tilldelning med en union av tilldelningar av vissa andra agenter och hennes pris med summan av deras priser. Vi visar att även om en sådan tilldelning/prissättning kan approximeras av O(log m + log n) faktor [3], är det coNP - svårt att avgöra om en given tilldelning / pris är multi avundsjuka gratis. Vi visar också att intäktsmaximering multi avund gratis tilldelning / prissättning är APX hårt. En intressant begränsad version av undergruppen prissättning problem är när alla objekt är intervaller av en linje segment och alla förfrågningar är en sammanhängande uppsättning objekt längs linjen. Motivet här är att man kan tänka på agenterna som förare på en motorväg när varje produkt är motorvägssegment (eller gäster i ett hotell -föremål översätts till datum). I denna miljö, avgöra om en given tilldelning / pris är multi avundsjuka gratis är polynom tid. Om motorvägen har begränsat kapacitet då en inkomst maximerar avund gratis tilldelning / prissättning kan beräknas i polynom tid och vi ger också en FPTAS för intäkterna maximera multi avund gratis tilldelning / prissättning.
Fiat m.fl. REF övervägde en förlängning av avundsfriheten där ingen agent avundas någon undergrupp av andra medel.
Envy, Multi Envy, and Revenue Maximization
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}