Անարխիայի գինը աճուրդներում

**Անարխիայի գինը** (**PoA**) խաղերի տեսության և մեխանիզմների նախագծման հասկացություն է, որը չափում է, թե ինչպես է համակարգի սոցիալական բարեկեցությունը քայքայվում դրա գործակալների եսասիրական վարքագծի պատճառով։ Այն լայնորեն ուսումնասիրվել է տարբեր համատեքստերում, մասնավորապես՝ աճուրդներում։

Աճուրդում կան մեկ կամ մի քանի իրեր և մեկ կամ մի քանի գործակալներ, որոնք տարբեր գնահատականներ են տալիս իրերին։ Ապրանքները պետք է բաժանվեն գործակալների միջև։ Ցանկալի է, որ *սոցիալական բարեկեցությունը* ՝ բոլոր գործակալների արժեքների գումարը, լինի որքան հնարավոր է բարձր։

Սոցիալական բարեկեցությունը մաքսիմալացնելու մոտեցումներից մեկը ճշմարտացի մեխանիզմի մշակումն է։ Նման մեխանիզմում յուրաքանչյուր գործակալ խրախուսվում է հաղորդել իր իրական գնահատականները կետերի վերաբերյալ։ Այնուհետև աճուրդավարը կարող է հաշվարկել և իրականացնել այնպիսի բաշխում, որը մեծացնում է արժեքների գումարը։ Նման մեխանիզմի օրինակ է VCG աճուրդը։

Սակայն գործնականում միշտ չէ, որ հնարավոր է կիրառել ճշմարիտ մեխանիզմներ։ Օրինակ՝ VCG մեխանիզմը կարող է չափազանց բարդ լինել մասնակիցների համար հասկանալի լինելու համար, աճուրդավարի համար կարող է չափազանց երկար ժամանակ պահանջվել հաշվարկների համար և կարող է ունենալ այլ թերություններ: Գործնականում հաճախ օգտագործվում են ոչ ճշմարտացի մեխանիզմներ, և հետաքրքիր է հաշվարկել, թե որքան սոցիալական բարեկեցություն է կորսվում այս ոչ ճշմարտացիության պատճառով։

Հաճախ ենթադրվում է, որ ոչ ճշմարիտ աճուրդի ժամանակ մասնակիցները խաղում են հավասարակշռության ռազմավարություն, ինչպիսին է Նեշի հավասարակշռությունը։ **Աճուրդի անարխիայի գինը** սահմանվում է որպես օպտիմալ սոցիալական բարեկեցության և *ամենավատ* հավասարակշռության մեջ գտնվող սոցիալական բարեկեցության միջև հարաբերակցությունը՝

PoA = \frac{\max_{s \in Allocations} Welf(s)}{\min_{s \in EquilibriumAllocations} Welf(s)}

Առնչվող հասկացություն է **կայունության գինը** (**ԿԳԳ**), որը չափում է օպտիմալ սոցիալական բարեկեցության և *լավագույն* հավասարակշռության մեջ գտնվող սոցիալական բարեկեցության միջև եղած հարաբերակցությունը։

PoS = \frac{\max_{s \in Allocations} Welf(s)}{\max_{s \in EquilibriumAllocations} Welf(s)}

Ակնհայտ է 1\leq PoS \leq PoA \leq \infty:

Երբ կա ամբողջական տեղեկատվություն (յուրաքանչյուր գործակալ գիտի մյուս բոլոր գործակալների գնահատականները), ընդհանուր հավասարակշռության տեսակը Նեշի հավասարակշռությունն է՝ կա՛մ մաքուր, կա՛մ խառը։ Երբ կա թերի տեղեկատվություն, ընդհանուր հավասարակշռության տեսակը Բեյս-Նեշի հավասարակշռությունն է։ Վերջին դեպքում սովորական է խոսել *անարխիայի բայեսյան գնի* կամ BPoA-ի մասին։

## Մեկ ապրանքի աճուրդներ
Մեկ ապրանքի առաջին գնով աճուրդի ժամանակ Նեշի հավասարակշռությունը միշտ արդյունավետ է, ուստի PoA-ն և PoS-ը 1 են։

Երկրորդ գնի աճուրդում գոյություն ունի Նեշի հավասարակշռություն, որտեղ գործակալները ճշմարիտ են հաշվետվություն ներկայացնում։ Այն արդյունավետ է, ուստի PoS-ը 1 է։ Սակայն, PoA-ն անսահմանափակ է։ Օրինակ,ենթադրենք, որ կան երկու խաղացողներ. Ալիսը գնահատում է իրը որպես *a*, իսկ Բոբը՝ որպես *b*, որտեղ *a* > *b*:

Գոյություն ունի «լավ» Նեշի հավասարակշռություն, որի դեպքում Ալիսը առաջարկում է *a*, իսկ Բոբը՝ *b*։ Ալիսը ստանում է ապրանքը և վճարում *b-ն*։ Սոցիալական բարեկեցությունը *a* է, որը օպտիմալ է։

Սակայն գոյություն ունի նաև «վատ» Նեշի հավասարակշռություն, որտեղ Ալիսը 0 է առաջարկում, իսկ Բոբը՝ *+1*։ Բոբը ստանում է ապրանքը և ոչինչ չի վճարում։ Սա հավասարակշռություն է, քանի որ Ալիսը չի ցանկանում Բոբին գերագնահատել։ Սոցիալական բարեկեցությունը *b* է։ Հետևաբար, PoA-ն *a* / *b* է, որը սահմանափակ չէ։

Այս արդյունքը թվում է չափազանց հոռետեսական.

* Նախ, երկրորդ գնային աճուրդի դեպքում յուրաքանչյուր գործակալի համար թույլ գերիշխող ռազմավարություն է հայտնել իր իրական գնահատականը։ Եթե ենթադրենք, որ գործակալները հետևում են իրենց գերիշխող ռազմավարություններին, ապա PoA-ն 1 է։
* Ավելին, յուրաքանչյուր գործակալի համար գերիշխող ռազմավարություն է հայտնել իր իրական գնահատականից բարձր ցանկացած արժեք։

Հետևաբար, սովորական է վերլուծել PoA-ն **՝ գերառաջարկներ չներկայացնելու** ենթադրության հիման վրա, ոչ մի գործակալ իր իրական գնահատականից բարձր առաջարկ չի անում։ Այս ենթադրության համաձայն, մեկ ապրանքի աճուրդի PoA-ն 1 է։

## Զուգահեռ աճուրդներ
Զուգահեռ (միաժամանակյա) աճուրդում, m ապրանքները վաճառվում են միևնույն ժամանակ նույն խմբին n մասնակիցներ։ Ի տարբերություն համակցված աճուրդի, որտեղ գործակալները կարող են գներ ներկայացնել ապրանքների փաթեթների համար, այստեղ գործակալները կարող են գներ ներկայացնել միայն առանձին ապրանքների համար՝ անկախ մյուսներից։ Այսինքն՝ գործակալի ռազմավարությունը գների վեկտոր է, մեկ գին՝ մեկ տարրի համար։ PoA-ն կախված է գնորդների գնահատման տեսակից և յուրաքանչյուր առանձին իրի համար օգտագործվող աճուրդի տեսակից։

**Դեպք 1. ենթամոդուլային գնորդներ, երկրորդ գնի աճուրդներ, ամբողջական տեղեկատվություն**`

* Գոյություն ունի մաքուր Նեշի հավասարակշռություն՝ օպտիմալ սոցիալական բարեկեցությամբ։ Հետևաբար, PoS-ը 1 է։
* Հնարավոր է բազմանդամային ժամանակում հաշվարկել մաքուր Նեշի հավասարակշռություն, որտեղ սոցիալական բարեկեցությունը օպտիմալի առնվազն կեսն է։ Հետևաբար, «պոլինոմային ժամանակի կայունության» գինը առավելագույնը 2 է։
* PoA-ն անսահմանափակ է, ինչպես արդեն ցույց է տրված վերևում բերված մեկ կետի օրինակում։ Սակայն, *ուժեղ՝ առանց գերառաջարկների* ենթադրության դեպքում (ցանկացած փաթեթի ցանկացած գնորդի առաջարկների գումարը առավելագույնը այդ փաթեթի արժեքն է գնորդի համար), PoA-ն առավելագույնը 2 է։ Վերջին արդյունքը ճիշտ է նաև այն դեպքում, երբ գնորդների գնահատականները մասնակիորեն են ենթագումարային։

**Դեպք 2՝ մասնակիորեն ենթաադիմիտիվ գնորդներ, 2-րդ գնի աճուրդ, թերի տեղեկատվություն**։ Ենթադրելով *ուժեղ-առանց գերառաջարկի*, ցանկացած (խառը) Բեյս-Նեշի հավասարակշռություն սպասում է օպտիմալ բարեկեցության առնվազն կեսին, հետևաբար, BPoA-ն առավելագույնը 2 է։ Այս արդյունքը կախված չէ գործակալների ընդհանուր պրիորալից։

**Դեպք 3. ենթաադիտիվ գնորդներ, երկրորդ գնի աճուրդներ**: *Հզոր՝ առանց գերառաջարկի* ենթադրության՝

* Լրիվ տեղեկատվության դեպքում, յուրաքանչյուր մաքուր Նեշի հավասարակշռության բարեկեցությունը օպտիմալից առնվազն 1/2 է, ուստի PoA-ն առավելագույնը 2 է։
* Անավարտ տեղեկատվության դեպքում գոյություն ունեն Բեյս-Նեշի հավասարակշռություններ, որտեղ բարեկեցությունը *փոքր է օպտիմալի 1/2-ից*, ուստի BPoA-ն մեծ է 2-ից։
* BPoA-ն առավելագույնն է 2\log{m}, որտեղ m իրերի քանակն է։ Այս երաշխիքը վավեր է նաև կոպիտ կորելացված հավասարակշռության համար, հետևաբար՝ խառը Նեշի հավասարակշռության և կորելացված հավասարակշռության հատուկ դեպքերի համար։
* PoA-ի վերը նշված երկու վերին սահմաններն էլ նրբորեն նվազում են, երբ թուլացվում են ենթաադդիտիվության և գերառաջարկների բացակայության ենթադրությունները։ Օրինակ՝ եթե ենթադրենք, որ յուրաքանչյուր խաղացող գերագնահատում է առավելագույնը որոշակի հաստատուն գործակցով, ապա PoA-ն աճում է առավելագույնը մեկ հաստատուն գործակցով։

**Դեպք 4. Ընդհանուր (մոնոտոն) գնորդներ, [[Առաջին գնի փակ գնով աճուրդ|առաջին գնի աճուրդներ]], ամբողջական տեղեկատվություն**`

* Խաղի մաքուր Նեշի հավասարակշռությունների բազմությունը հենց շուկայի Վալրասի հավասարակշռություններն են (գնային հավասարակշռություններ):
* Քանի որ նման հավասարակշռությունները սոցիալապես օպտիմալ են (ըստ առաջին բարեկեցության թեորեմի ), մաքուր Նեշի հավասարակշռությունների PoA-ն 1 է։ Դժբախտաբար, նման հավասարակշռություններ կարող են գոյություն չունենալ։
* Խառը Նեշի հավասարակշռություն միշտ գոյություն ունի (ճիշտ հավասարության կանոն ընտրելիս): Սակայն, դա պարտադիր չէ, որ սոցիալապես օպտիմալ լինի։ PoA-ն կարող է լինել այնքան բարձր, որքան՝ \Omega(\sqrt{m}), և նույնիսկ PoS-ը կարող է լինել այնքան բարձր, որքան \Omega(\sqrt{m}/\log{m})։
** Այս արդյունքը տարածվում է նաև երկրորդ գնի աճուրդների վրա, նույնիսկ *թույլ՝ առանց գերառաջարկների* ենթադրությամբ։
* PoA-ն առավելագույնն է O(m)։
* Երբ բոլոր գնահատականները ենթագումարային են, PoA-ն առավելագույնը O(\log{m})։
* Երբ բոլոր գնահատականները \beta - մասնակիորեն ենթաադմիատիվ, PoA-ն առավելագույնը 2 \beta (մասնավորապես, XOS գնորդների համար PoA-ն առավելագույնը 2 է):
* Վերջին երեք սահմանները վերաբերում են նաև կոպիտ փոխկապակցված հավասարակշռություններին. դրանք չեն պահանջում «գերագնահատման բացակայություն» ենթադրություն։

**Դեպք 5. Ընդհանուր գնորդներ, երկրորդ գնի աճուրդներ, ամբողջական տեղեկատվություն**: Ընդհանուր գնահատումների դեպքում (որոնք կարող են ունենալ լրացումներ) ուժեղ՝ առանց գերառաջարկի առաջարկելու ենթադրությունը չափազանց ուժեղ է, քանի որ այն թույլ չի տալիս գնորդներին բարձր արժեքներ առաջարկել լրացնող ապրանքների փաթեթների համար։ Օրինակ, եթե գնորդի գնահատականը մեկ զույգ կոշիկի համար կազմում է 100 դոլար, բայց յուրաքանչյուր կոշիկի համար՝ 1 դոլար, ապա ուժեղ՝ ոչ գերարժեքավոր առաջարկի ենթադրությունը թույլ չի տալիս նրան յուրաքանչյուր կոշիկի համար առաջարկել 1 դոլարից ավելի առաջարկ, ուստի նա զույգը շահելու քիչ հնարավորություն ունի։ Հետևաբար, այն փոխարինվում է *թույլ՝ առանց գերառաջարկի* ենթադրության, ինչը նշանակում է, որ գերառաջարկի բացակայության պայմանը գործում է միայն այն փաթեթի համար, որը գործակալը վերջապես հաղթում է (այսինքն՝ գնորդի առաջարկների գումարը իրեն հատկացված փաթեթին առավելագույնը կազմում է նրա արժեքը այս կոնկրետ փաթեթի համար): Այս թույլ՝ առանց գերառաջարկի ենթադրության համաձայն՝

* Խաղի մաքուր Նեշի հավասարակշռությունների բազմությունը հենց շուկայի *պայմանական գնային հավասարակշռություններն* են։
* Քանի որ նման հավասարակշռությունները կիսով չափ սոցիալապես օպտիմալ են (հասնում են առավելագույն սոցիալական բարեկեցության առնվազն կեսին), մաքուր Նեշի հավասարակշռությունների PoA-ն առավելագույնը 2 է։ Դժբախտաբար, նման հավասարակշռություններ կարող են գոյություն չունենալ։

**Դեպք 6. Ընդհանուր գնորդներ, առաջին գնի աճուրդներ, թերի տեղեկատվություն** Ցանկացած ընդհանուր նախորդի համար՝

* BPoA-ն առավելագույնն է O(m n):
* Երբ բոլոր գնահատականները \beta -կոտորակային ենթաադիտիվ, BPoA-ն առավելագույնը 4 \beta (մասնավորապես, XOS գնորդների համար BPoA-ն առավելագույնը 2 է, իսկ ենթաադիտիվ գնորդների համար՝ O(\log m))։

**Դեպք 7. Ենթադիմացող գնորդներ, թերի տեղեկատվություն**՝

* Երբ ապրանքները վաճառվում են առաջին գնով աճուրդներում, BPoA-ն առավելագույնը 2 է։
* Երբ ապրանքները վաճառվում են երկրորդ գնի աճուրդներում, BPoA-ն առավելագույնը 4 է։ Սա ճիշտ է թե՛ ուժեղ՝ առանց գերառաջարկների ենթադրության դեպքում (ցանկացած փաթեթի ցանկացած գնորդի առաջարկների գումարը առավելագույնը այդ փաթեթի արժեքն է գնորդի համար), թե՛ *թույլ՝ առանց գերառաջարկների* ենթադրության դեպքում (ցանկացած գնորդի հաղթական առաջարկների սպասվող գումարը առավելագույնը այդ գնորդի հաղթական արժեքն է):

## Հաջորդական աճուրդներ
Հաջորդական աճուրդում, m իրերը վաճառվում են հաջորդական աճուրդներում՝ մեկը մյուսի հետևից։ Ընդհանուր հավասարակշռության տեսակը մաքուր ռազմավարություններում ենթախաղի կատարյալ հավասարակշռությունն է (SPEPS): Երբ գնորդներն ունեն ամբողջական տեղեկատվություն (այսինքն՝ նրանք նախապես գիտեն աճուրդների հաջորդականությունը), և յուրաքանչյուր փուլում վաճառվում է մեկ ապրանք, SPEPS-ը միշտ գոյություն ունի

Այս SPEPS-ի PoA-ն կախված է հայտատուների օգտակար գործառույթներից և յուրաքանչյուր առանձին կետի համար օգտագործվող աճուրդի տեսակից։

Ստորև բերված առաջին հինգ արդյունքները վերաբերում են ամբողջական տեղեկատվություն ունեցող գործակալներին (բոլոր գործակալները գիտեն մնացած բոլոր գործակալների գնահատականները)։

**Դեպք 1. Նույնական իրեր, երկու գնորդ, երկրորդ գնի աճուրդներ**՝

* Երբ առնվազն մեկ գնորդ ունի գոգավոր գնահատման ֆունկցիա (նվազող եկամուտներ), PoA-ն առավելագույնը 1/(1-e) \approx 1.58։
* Թվային արդյունքները ցույց են տալիս, որ երբ կան բազմաթիվ գոգավոր գնահատման ֆունկցիաներով առաջարկողներ, արդյունավետության կորուստը նվազում է օգտատերերի թվի աճին զուգընթաց։

**Դեպք 2. հավելյալ գնորդներ** 

* Երկրորդ գնի աճուրդների դեպքում PoA-ն անսահմանափակ է. SPEPS-ում բարեկեցությունը կարող է կամայականորեն փոքր լինել։

**Դեպք 3. միավոր պահանջարկով գնորդներ**՝

* Առաջին գնով աճուրդների դեպքում PoA-ն առավելագույնը 2 է. SPEPS-ում բարեկեցությունը միշտ առավելագույնի առնվազն կեսն է (եթե թույլատրվում են խառը ռազմավարություններ, PoA-ն առավելագույնը 4 է):
* Երկրորդ գնի աճուրդների դեպքում PoA-ն կրկին անսահմանափակ է։

Այս արդյունքները զարմանալի են և ընդգծում են յուրաքանչյուր փուլում առաջին գնի աճուրդ (երկրորդ գնի աճուրդի փոխարեն) օգտագործելու նախագծային որոշման կարևորությունը։

**Դեպք 4. ենթամոդուլային գնորդներ**(նշենք, որ հավելյալ և միավորային պահանջարկը ենթամոդուլայինի հատուկ դեպքեր են):

* Ե՛վ առաջին, և՛ երկրորդ գնի աճուրդների դեպքում PoA-ն անսահմանափակ է, նույնիսկ երբ կան միայն չորս մասնակից։ Ինտուիցիան այն է, որ բարձր գին առաջարկող կողմը կարող է նախընտրել թույլ տալ, որ ցածր գին առաջարկող կողմը հաղթի՝ ապագա փուլերում իր հնարավոր մրցակցությունը նվազեցնելու համար։

**Դեպք 5. ադիտիվ+UD**։ Ենթադրենք, որ որոշ գնորդներ ունեն լրացուցիչ գնահատականներ, մինչդեռ մյուսներն ունեն միավորի պահանջարկի գնահատականներ։ Առաջին գնով աճուրդների հաջորդականության դեպքում PoA-ն կարող է լինել առնվազն՝ \min(n,m), որտեղ *m-ը* ապրանքների քանակն է, իսկ *n-* ը՝ առաջարկողների քանակը։ Ավելին, անարդյունավետ հավասարակշռությունները շարունակվում են նույնիսկ թույլ գերիշխող ռազմավարությունների կրկնվող վերացման դեպքում։ Սա ենթադրում է գծային անարդյունավետություն բազմաթիվ բնական միջավայրերի համար, ներառյալ՝

* գնորդներ՝ համախառն փոխարինող գնահատականներով,
* կարողունակ գնահատականներ,
* բյուջեի լրացուցիչ գնահատումներ,
* լրացուցիչ գնահատումներ՝ վճարումների վրա խիստ բյուջետային սահմանափակումներով։

**Դեպք 6. միավորային պահանջարկով գնորդներ, թերի տեղեկատվություն, 1-ին գնի աճուրդներ**։ BPoA-ն առավելագույնը 3 է։

## Առնչվող թեմաներ
Աճուրդներում PoA-ի վերաբերյալ ուսումնասիրությունները հնարավորություն են տվել պատկերացում կազմել այլ միջավայրերի մասին, որոնք կապված չեն աճուրդների հետ, ինչպիսիք են ցանցային ձևավորման խաղերը։

## Ամփոփիչ աղյուսակ
[Մասնակի աղյուսակ - պարունակում է միայն զուգահեռ աճուրդներ - պետք է լրացվի]

## Ծանոթագրություններ

Կատեգորիա:Խաղերի տեսություն