Әділ бөлу: Тортты қанағаттандыра бөлу процесі

Кіріспе

Ресурстарды әділ бөлу процесі

Қызғанышсыз тортты кесу – әділ тортты бөлудің бір түрі. Бұл – әртүрлі ресурсты ("торт") бөлу, ол қызғанышсыздық критерийін қанағаттандырады, яғни әрбір серіктес өзіне бөлген үлестің, жеке бағалауынша, басқа үлестерден кем емес деп санайды. Егер екі серіктес болса, мәселе оңай шешіледі және көне заманда "бөліп ал және таңда" протоколы арқылы шешілген. Егер үш немесе одан көп серіктес болса, мәселе әлдеқайда қиынға айналады. Мәселенің екі негізгі түрі зерттелді:
Қосылған бөліктер, мысалы, егер торт бір өлшемді аралық болса, онда әр серіктес бір ішкі аралықты алуы керек. Егер серіктестер болса, тек кесімдер қажет. Жалпы бөліктер, мысалы, егер торт бір өлшемді аралық болса, онда әр серіктес біріккен, бөлек ішкі аралықтар жиынтығын алуы мүмкін.

Қысқаша тарихы

Қазіргі заманғы әділ торт кесу мәселесі 1940 жылдары басталды. Алғашқы әділдік критерийі пропорционалды бөлу болды, және көп ұзамай n серіктес үшін процедура табылды. Қызғаныш еркіндігінің күшті критерийін 1950 жылдары Джордж Гамов пен Марвин Стерн торт кесу мәселесіне енгізді. 1960 жылы үш серіктес және жалпы бөлшектерге арналған процедура табылды. Үш серіктес және біріктірілген бөлшектерге арналған процедура тек 1980 жылы табылды. Төрт немесе одан да көп серіктестер үшін қызғанышсыз бөлу 1990 жылдарға дейін шешілмеген мәселе болып келді, содан кейін жалпы бөлшектер үшін үш процедура және біріктірілген бөлшектер үшін бір процедура жарияланды. Бұл процедуралардың барлығы шексіз – олар алдын ала шектелмеген қадамдар санын қажет етуі мүмкін. Біріктірілген бөлшектер үшін тіпті шексіз қадамдар қажет болуы мүмкін. 2000 жылдары қызғаныш еркіндігінің орындалу уақытының күрделілігінің екі төменгі шегі жарияланды. Жалпы бөлшектер үшін төменгі шек Ω(n2) құрайды. Біріктірілген бөлшектер үшін төменгі шек – шексіз, яғни үш немесе одан да көп серіктестер үшін шекті протокол жоқ. 2010 жылдары бірнеше жуықтау процедуралары мен ерекше жағдайларға арналған процедуралар жарияланды. Жалпы бөлшектер үшін шектелген уақыт процедуралары бар ма деген сұрақ ұзақ уақыт бойы шешілмей келді. 2016 жылы мәселе шешілді. Харис Азиз бен Саймон Маккензи ең көп дегенде s немесе t сұранысты қажет ететін дискретті қызғаныш еркіндігі протоколын ұсынды. Төменгі шек пен процедура арасында әлі де үлкен айырма бар. 2024 жылдың ақпанына қарай қызғаныш еркіндігінің нақты орындалу уақытының күрделілігі әлі белгісіз. Біріктірілген бөлшектер жағдайында, нәтиже торттың толығымен бөлінуін талап етеді. Егер бұл талап әр серіктес пропорционалдық құнды (өз бағалауынша торттың жалпы құнының кемінде 1/n бөлігін) алады деген талаппен ауыстырылса, онда үш серіктес үшін шектелген процедура белгілі, бірақ төрт немесе одан да көп серіктес үшін шектелген уақыт процедуралары бар ма деген мәселе әлі де ашық болып қала береді.

Modern research into the fair cake cutting problem started in the 1940s. The first fairness criterion studied was proportional division, and a procedure for n partners was soon found. The stronger criterion of envy freeness was introduced into the cake cutting problem by George Gamow and Marvin Stern in 1950s. A procedure for three partners and general pieces was found in 1960. A procedure for three partners and connected pieces was found only in 1980. Envy free division for four or more partners had been an open problem until the 1990s, when three procedures for general pieces and a procedure for connected pieces were published. All these procedures are unbounded they may require a number of steps which is not bounded in advance. The procedure for connected pieces may even require an infinite number of steps. Two lower bounds on the run time complexity of envy freeness were published in the 2000s. For general pieces, the lower bound is Ω(n2). For connected pieces the lower bound is infinity – there is provably no finite protocol for three or more partners. In the 2010s, several approximation procedures and procedures for special cases were published. The question whether bounded time procedures exist for the case of general pieces had remained open for a long time. The problem was finally solved in 2016. Haris Aziz and Simon Mackenzie presented a discrete envy free protocol that requires at most or queries. There is still a very large gap between the lower bound and the procedure. As of Feb 2024, the exact run time complexity of envy freeness is still unknown. For the case of connected pieces, it was noted that the hardness result assumes that the entire cake must be divided. If this requirement is replaced by the weaker requirement that every partner receives a proportional value (at least 1/n of the total cake value according to their own valuation), then a bounded procedure for three partners is known, but it has remained an open problem whether there exist bounded time procedures for four or more partners.

Таяулаулар мен ішінара шешімдер

Соңғы азайту протоколының қайта кіретін түрі шектелген уақыт ішінде қызғанышсыз бөлуге жуықтап есептеуді (аппроксимация) табады. Нақтырақ айтқанда, кез келген тұрақты үшін , ол әрбір серіктің құндылығы ең үлкен құндылықтан кем емес , уақытында бөлуді қамтамасыз етеді. Егер барлық құндылық өлшемдері кесімді сызықтық болса, онда құндылық функцияларының өрнектелуінің мөлшеріне қатысты полиномдық алгоритм бар. Сұраулар саны , мұндағы – құндылық тығыздығы функцияларының туындыларындағы үзілістер саны.

Қаттылық нәтижесі

n адамға арналған әрбір қызғанышсыз процедурада кем дегенде Ω(n²) сұраныс қажет, бұл Robertson–Webb сұраныс моделінде белгіленген. Дәлел алгоритмнің әр серіктес туралы қанша ақпаратқа ие екенін мұқият талдауға негізделген. А. А. Тортты [0,1] бір өлшемді аралық деп есептейік, және әр серіктес үшін торттың құндылығы 1-ге нормаланған. Әр қадамда алгоритм белгілі бір серіктестен [0,1] аралығында орналасқан белгілі бір аралықты бағалауды немесе аралықты белгілі бір мәнмен көрсетуді сұрайды. Екі жағдайда да алгоритм тек сұрауда немесе жауапта аталған соңғы нүктелері бар аралықтар туралы ақпарат жинайды. Осы нүктелерді «белгі» деп атайық. Бастапқыда i-нің жалғыз белгілері 0 және 1 болады, себебі алгоритм i серіктесі туралы білетін жалғыз нәрсе – vi([0,1]) = 1. Егер алгоритм i серіктесінен [0.2,1] аралығын бағалауды сұраса, онда жауаптан кейін i-нің белгілері {0, 0.2, 1} болады. Алгоритм vi([0,0.2])-ді есептей алады, бірақ 0.2-ден өзгеше соңғы нүктесі бар кез келген аралықтың құндылығын есептей алмайды. Әр сұраныста белгілердің саны екіге артық көбеймейді. Атап айтқанда, [0,0.2] аралығының құндылығы толығымен 0-ге немесе толығымен 0.2-ге жақын орналасуы мүмкін, немесе олардың арасында кез келген жерде шоғырлануы мүмкін. Б. I серіктестің екі тікелей белгісінің арасындағы аралық i серіктестің «белгілік аралығы» деп аталады. Алгоритм i серіктесіне торттың бір бөлігін бөлуді шешкенде, ол i үшін жалпы құндылығы i-нің кез келген белгілік аралығының құндылығынан кем болмаған бір бөлігін бөлуі керек. Дәлел қайшылыққа қарай жасалады: i үшін i-ге бөлінген құндылықтан артық белгілі бір J аралығы бар деп есептейік. Басқа серіктес, мысалы j, міндетті түрде J аралығының бір бөлігін алады. А тармағына сәйкес, J аралығының барлық құндылығы j серіктесіне бөлінген үлес ішінде шоғырлануы мүмкін. Осылайша, i, j-ге қызғанышпен қарайды, ал бөліс қызғанышсыз болмайды. С. Барлық серіктестер барлық сұраныстарға олардың құндылық өлшемі біркелкі (яғни аралықтың құндылығы оның ұзындығына тең) деп жауап береді дейік. B тармағына сәйкес, алгоритм i-ге тек оның i-нің барлық белгілік аралықтарынан ұзын болса ғана бір бөлігін бере алады. Кем дегенде n/2 серіктеске ең көп дегенде 2/n ұзындығы бар аралық беріледі; демек, олардың барлық белгілік аралықтары ең көп дегенде 2/n ұзындығында болуы керек; демек, олардың кем дегенде n/2 белгілік аралықтары болуы керек; демек, олардың кем дегенде n/2 белгісі болуы керек. D. I серіктес жауап берген әр сұранысқа ең көп дегенде екі жаңа нүкте кіреді, сондықтан i-нің белгілерінің санын ең көп дегенде 2 есеге арттырады. Сондықтан, C тармағында сипатталған жағдайда, алгоритм n/2 серіктестің әрқайсысына кем дегенде n/4 сұраныс қоюы керек. Сұраныстардың жалпы саны кем дегенде n²/8 = Ω(n²) болады.

Every envy free procedure for n people requires at least Ω(n2) queries in the Robertson–Webb query model. The proof relies on a careful analysis of the amount of information the algorithm has on each partner. A. Assume that the cake is the 1 dimensional interval [0,1], and that the value of the entire cake for each of the partners is normalized 1. In each step, the algorithm asks a certain partner either to evaluate a certain interval contained in [0,1], or to mark an interval with a specified value. In both cases, the algorithm gathers information only about intervals whose end points were mentioned in the query or in the reply. Let's call these endpoints landmarks. Initially the only landmarks of i are 0 and 1 since the only thing the algorithm knows about partner i is that vi([0,1])=1. If the algorithm asks partner i to evaluate the interval [0.2,1], then after the reply the landmarks of i are {0,0.2,1}. The algorithm can calculate vi([0,0.2]), but not the value of any interval whose endpoint is different than 0.2. The number of landmarks increases by at most 2 in each query. In particular, the value of the interval [0,0.2] might be concentrated entirely near 0, or entirely near 0.2, or anywhere in between. B. An interval between two consecutive landmarks of partner i is called a landmark interval of partner i, When the algorithm decides to allocate a piece of cake to partner i, it must allocate a piece whose total value for i is at least as large as any landmark interval of i. The proof is by contradiction: suppose there is a certain landmark interval J whose value for i is more than the value actually allocated to i. Some other partner, say j, will necessarily receive some part of the landmark interval J. By paragraph A, it is possible that all the value of interval J is concentrated inside the share allocated to partner j. Thus, i envies j and the division is not envy free. C. Suppose all partners answer all queries as if their value measure is uniform (i. e. the value of an interval is equal to its length). By paragraph B, the algorithm may assign a piece to partner i, only if it is longer than all landmark intervals of i. At least n/2 partners must receive an interval with a length of at most 2/n; hence all their landmark intervals must have a length of at most 2/n; hence they must have at least n/2 landmark intervals; hence they must have at least n/2 landmarks. D. Each query answered by partner i involves at most two new endpoints, so it increases the number of landmarks of i by at most 2. Hence, in the case described by paragraph C, the algorithm must ask each of n/2 partners, at least n/4 queries. The total number of queries is thus at least n2/8 = Ω(n2).

Әр түрлі құқықтармен көзқарастан азат бөлім

Қызғанышсыз критерийдің жалпылама түрі – әр серіктестің әртүрлі үлеске құқығы бар екендігі. Яғни, әр серіктес i үшін олар алуға тиіс торттың үлесін көрсететін wᵢ салмағы болады (барлық wᵢ салмақтарының қосындысы 1-ге тең). Сонда салмақталған қызғанышсыз бөлу келесідей анықталады. Кез келген агенттің i үшін құндылық өлшемі Vi және кез келген басқа агент j үшін: Яғни, әр серіктес өзінің үлесі, өзінің құқығына қатысты, басқа серіктестің құқығына қатысты кез келген басқа үлестен кем емес деп санайды. Егер барлық салмақтар бірдей болса (және 1/n-ге тең болса), бұл анықтама қызғанышсыздықтың стандартты анықтамасына дейін тосып қалады. Егер бөліктер үзіліссіз болса, салмақталған қызғанышсыз бөлу әрқашан болады және оны кез келген салмақтар жиынтығы үшін Робертсон-Уэбб протоколы арқылы табуға болады. Зенг шамамен салмақталған қызғанышсыз бөлуге арналған балама алгоритм ұсынды, ол азырақ кесулерді қажет етеді. Бірақ егер бөліктер байланысты болуы керек болса, салмақталған қызғанышсыз бөлу мүмкін болмауы мүмкін. Мұны мынадан көруге болады: кез келген салмақталған қызғанышсыз бөлу сол салмақ векторымен салмақталған пропорционалды бөлумен бірдей болады; яғни, кез келген агент i үшін құндылық өлшемімен Vi: Белгілі болғандай, байланысты бөліктермен салмақталған пропорционалды бөлу болмауы мүмкін: мысалы, әртүрлі құқықтармен пропорционалды тортты кесуді қараңыз. Сондай-ақ, салмақталған қызғанышсыз бөлудің балама анықтамасы бар, онда салмақтар агенттерге емес, бөліктерге тағайындалады. Бұл анықтама бойынша салмақталған қызғанышсыз бөлу келесі жағдайларда болады (әр жағдай алдыңғысын жалпылайды): Қосымша құндылық функциялары, 1 өлшемді торт (интервал) және бөліктер байланысты интервалдар болуы керек. Қосымша мән функциялары, көп өлшемді симплекстік торт және бөліктер симплекстер болуы керек. Дәлелдемеде Спернер теоремасы, ККМ леммасы, Гейлдің жабу леммасы және Кай Фанның сәйкес келу нүктелері туралы леммасы қолданылады.

"Жақсы" тортты бөлу

Кейбір жағдайларда бөлінетін "кек" теріс мәнге ие болуы мүмкін. Мысалы, бұл шөп шабуға тиіс жер немесе тазалауға тиіс қараусыз жер болуы мүмкін. Онда "кек" "гетерогенді жақсы" емес, "гетерогенді жаман" болып саналады. Кейбір қанағатсыздықсыз бөлу процедураларын жаман "кек" үшін бейімдеуге болады, бірақ бейімделу көбінесе оңай болмайды. Толығырақ ақпаратты қанағатсыздықсыз үй шаруаларын бөлу бөлімінен қараңыз.