Վիկրեյ-Քլարկ-Գրովզ

**Վիկրեյ-Քլարկ-Գրովզ (ՎՔԳ) աճուրդը** բազմաթիվ իրերի փակ գնանշումներով աճուրդի տեսակ է: Առաջարկողները ներկայացնում են առաջարկներ, որոնք ներկայացնում են ապրանքների համար իրենց գնահատականները՝ առանց իմանալու մյուս առաջարկողների առաջարկները։ Աճուրդի համակարգը իրերը բաշխում է սոցիալապես օպտիմալ ձևով, այն յուրաքանչյուր անհատից գանձում է մյուս մասնակիցներին պատճառված վնասը։ Այն խթան է տալիս գնորդներին ներկայացնել իրենց իրական գնահատականները ՝ ապահովելով, որ յուրաքանչյուր գնորդի համար օպտիմալ ռազմավարությունը իրերի իրական գնահատականները ներկայացնելն է։ Այն կարող է խաթարվել գնորդների գաղտնի համաձայնությամբ, և մասնավորապես՝ որոշ դեպքերում՝ մեկ գնորդի կողմից տարբեր անուններով մի քանի առաջարկներ ներկայացնելով։ Սա Վիկրեյի աճուրդի ընդհանրացում է բազմաթիվ իրերի համար։

Աճուրդը անվանակոչվել է Ուիլյամ Վիկրեյի, Էդվարդ Հ. Քլարկի, և Թեոդոր Գրովզի անունով՝ իրենց հոդվածների համար, որոնք հաջորդաբար ընդհանրացրել են գաղափարը։

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

## Ինտուիտիվ նկարագրություն
Դիտարկենք աճուրդ, որտեղ վաճառվում են նույնական ապրանքների մի շարք։ Մասնակիցները կարող են մասնակցել աճուրդին՝ հայտարարելով Ն ապրանքներ ստանալու համար վճարելու պատրաստ առավելագույն գինը։ Յուրաքանչյուր գնորդին թույլատրվում է հայտարարել մեկից ավելի առաջարկ, քանի որ նրա մեկ միավորի համար վճարելու պատրաստակամությունը կարող է տարբեր լինել՝ կախված ստացված միավորների ընդհանուր քանակից։ Մասնակիցները չեն կարող տեսնել այլ մարդկանց առաջարկները որևէ պահի, քանի որ դրանք կնքված են (տեսանելի են միայն աճուրդի համակարգին): Բոլոր առաջարկները ներկայացնելուց հետո աճուրդը համարվում է փակված։

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

Մյուս մասնակիցներին պատճառված այս սահմանային վնասը (այսինքն՝ հաջողված առաջարկ ներկայացրած յուրաքանչյուր անհատի կողմից վճարված վերջնական գինը) կարող է հաշվարկվել հետևյալ կերպ՝ (աճուրդի առաջարկների գումար՝ առաջարկների լավագույն համակցությունից *՝ բացառությամբ դիտարկվող մասնակցի*) − (ինչ առաջարկներ են ներկայացրել մյուս *հաղթող* մասնակիցները առաջարկների ներկայիս (լավագույն) համակցությունում): Եթե երկրորդ լավագույն համակցության գնային առաջարկների գումարը նույնն է, ինչ լավագույն համակցությանըը, ապա գնորդների կողմից վճարվող գինը կլինի նույնը, ինչ նրանց սկզբնական գնային առաջարկը։ Մնացած բոլոր դեպքերում գնորդների կողմից վճարվող գինը կլինի ավելի ցածր։

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

## Պաշտոնական նկարագրություն
### Նշագրություն
Աճուրդի հանված իրերի ցանկացած հավաքածուի համար M = \{t_1,\ldots,t_m\} և ցանկացած գնորդների խումբ N = \{b_1,\ldots,b_n\}, թող V^M_N տվյալ առաջարկների համակցության համար ՎՔԳ աճուրդի սոցիալական արժեքն է։ Այսինքն՝ որքանով է յուրաքանչյուր մարդ գնահատում իր հենց նոր շահած իրերը՝ գումարած բոլորի համար։ Իրի արժեքը զրո է, եթե նրանք չեն հաղթում։ Առաջարկողի համար b_i և կետ t_j, թող առաջարկողի առաջարկը ապրանքի համար լինի v_{i}(t_{j})։  Նշումը A \setminus B նշանակում է A-ի տարրերի բազմություն, որոնք B-ի տարրեր չեն։

### Հանձնարարություն
Առաջարկող b_i ում առաջարկը ապրանքի համար t_j «գերարժեք» է, այսինքն՝ v_{i}(t_{j}), շահում է իրը, բայց վճարում է V^{M}_{N \setminus \{b_i\}}-V^{M \setminus \{t_j\}}_{N \setminus \{b_i\}}, որը նրանց հաղթանակի սոցիալական արժեքն է, որը կրում են մնացած գործակալները։

### Բացատրություն
Իրոք, գնորդների խումբը, բացի b_i է N \setminus \{b_i\}։ Երբ կետը t_j հասանելի է, նրանք կարող են ստանալ բարեկեցություն V^{M}_{N \setminus \{b_i\}}. Ապրանքի շահումը b_i կրճատում է մատչելի իրերի հավաքածուն M \setminus \{t_j\}, ուստի հասանելի բարեկեցությունն այժմ V^{M \setminus \{t_j\}}_{N \setminus \{b_i\}}։ Հետևաբար, բարեկեցության երկու մակարդակների միջև տարբերությունը մնացած մասնակիցների կրած հասանելի բարեկեցության կորուստն է, ինչպես կանխատեսվում էր՝ հաղթողի **դեպքում**։ b_i ստացա ապրանքը t_j։ Այս քանակը կախված է մնացած գործակալների առաջարկներից և գործակալին անհայտ է b_i։

### Հաղթողի օգտակարությունը
*Հաղթող մասնակիցը, որի առաջարկը համապատասխանում է իրական արժեքին <math>A</math> իրի համար <math>t_j</math>, <math>v_{i}(t_{j})=A,</math> ստանում է առավելագույն օգտակարություն <math>A - \left(V^{M}_{N \setminus \{b_i\}}-V^{M \setminus \{t_j\}}_{N \setminus \{b_i\}}\right).</math>։*

## Օրինակներ
### Երկու ապրանք, երեք մասնակից
Ենթադրենք, որ աճուրդի են հանվում երկու խնձոր՝ երեք գնորդների միջև։

* Առաջարկող Ա-ն ուզում է մեկ խնձոր և պատրաստ է վճարել 5 դոլար այդ խնձորի համար։
* Առաջարկող B-ն ուզում է մեկ խնձոր և պատրաստ է վճարել 2 դոլար դրա համար։
* Առաջարկող C-ն ուզում է երկու խնձոր և պատրաստ է վճարել 6 դոլար երկուսն էլ ունենալու համար, բայց չի հետաքրքրված գնել միայն մեկը՝ առանց մյուսի։

Նախ, աճուրդի արդյունքը որոշվում է գների մաքսիմալացմամբ. խնձորները գնում են առաջարկող A-ին և առաջարկող B-ին, քանի որ նրանց համակցված առաջարկը՝ $5 + $2 = $7, ավելի մեծ է, քան առաջարկող C-ի կողմից երկու խնձորի համար առաջարկված առաջարկը, որը պատրաստ է վճարել ընդամենը $6: Այսպիսով, աճուրդից հետո A գնորդի կողմից ստացված արժեքը կազմում է $5, B գնորդի կողմից՝ $2, իսկ C գնորդի կողմից՝ $0 (քանի որ C գնորդը ոչինչ չի ստանում): Նկատի ունեցեք, որ հաղթողների որոշումը, ըստ էության, պարկի խնդիր է։

Հաջորդը, վճարումները որոշելու բանաձևը տալիս է.

* Ա հայտատուի համար. A-ից պահանջվող շահման համար վճարումը որոշվում է հետևյալ կերպ. Նախ, աճուրդում, որը բացառում է հայտատու Ա-ին, սոցիալական ապահովության առավելագույն արդյունքը երկու խնձորն էլ կհատկացնի հայտատու C-ին $6 ընդհանուր սոցիալական արժեքով: Այնուհետև, սկզբնական աճուրդի ընդհանուր սոցիալական արժեքը՝ առանց Ա-ի արժեքի, հաշվարկվում է որպես $7 − $5 = $2: Ի վերջո, հանեք երկրորդ արժեքը առաջին արժեքից: Այսպիսով, A-ից պահանջվող վճարը կազմում է $6 − $2 = $4:
* Բ հայտատուի համար. Վերոնշյալի նման, աճուրդի լավագույն արդյունքը, որը բացառում է հայտատու B-ին, երկու խնձորներն էլ հատկացնում է C հայտատուին $6-ով: Բնօրինակ աճուրդի ընդհանուր սոցիալական արժեքը հանած B-ի բաժինը կազմում է $5: Այսպիսով, B-ից պահանջվող վճարը կազմում է $6 − $5 = $1:
* Վերջապես, C հայտատուի վճարումը (($5 + $2) − ($5 + $2)) = $0 է:

Աճուրդից հետո A-ն 1 դոլարով ավելի լավ վիճակում է, քան նախկինում (վճարելով 4 դոլար՝ 5 դոլար օգտակարություն ստանալու համար), B-ն 1 դոլարով ավելի լավ վիճակում է, քան նախկինում (վճարելով 1 դոլար՝ 2 դոլար օգտակարություն ստանալու համար), իսկ C-ն չեզոք է (ոչինչ չի շահել):

### Երկու առաջարկող
Ենթադրենք, որ կան երկու հայտատուներ, 𝑏1 և 𝑏2, երկու հատ,𝑡1 և 𝑡2, և յուրաքանչյուր հայտատուին թույլատրվում է ձեռք բերել մեկ ապրանք: Մենք թույլ ենք տալիս 𝑣𝑖,𝑗

լինել հայտատու 𝑏𝑖ապրանքի գնահատումը 𝑡𝑗. Ենթադրենք 𝑣1,1=10𝑣1,2=5, 𝑣2, 1=5, և𝑣2, 2=3. Մենք տեսնում ենք, որ երկուսն էլ𝑏1 և 𝑏2 նախընտրում է ստանալ ապրանքը 𝑡1

,սակայն սոցիալապես օպտիմալ հանձնարարականը տալիս է կետ 𝑡1 հայտատուին 𝑏1  (այսպես, դրանց ձեռք բերված արժեքն է 10) և կետը 𝑡2 հայտատուին 𝑏2 (այսպես, դրանց ձեռք բերված արժեքն է 3) Այսպիսով, ձեռք բերված ընդհանուր արժեքն է 13, որը օպտիմալ է։

Եթե անձը b_2 աճուրդին չէին մասնակցում, անձ b_1 դեռ կհանձնարարվեր t_1, և, հետևաբար, անձը b_1 ավելին ոչինչ չի կարող շահել։ Ներկայիս արդյունքն է՝ 10, հետևաբար b_2 գանձվում է 10-10=0։

Եթե անձը b_1 աճուրդին չէին մասնակցում, t_1 կհանձնարարվեր b_2 և կունենար գնահատական 5։ Ընթացիկ արդյունքը 3 է, հետևաբար b_1 գանձվում է 5-3=2;

### Օրինակ #3
Դիտարկենք աճուրդը n տներ դեպի n առաջարկներ ներկայացնողներ, որոնցից յուրաքանչյուրը պետք է ստանա մեկական տուն։ \tilde v_{ij}, ներկայացնում է արժեքի խաղացողին i ունի տան համար j . Հնարավոր արդյունքները բնութագրվում են երկկողմանի համապատասխանություններով, որոնք զուգակցում են տները մարդկանց հետ։ Եթե մենք գիտենք արժեքները, ապա սոցիալական բարեկեցության մաքսիմալացումը հանգեցնում է առավելագույն կշռի երկմասն համապատասխանության հաշվարկին։

Եթե մենք չգիտենք արժեքները, ապա փոխարենը մենք առաջարկում ենք առաջարկներ \tilde b_{ij}, հարցնելով յուրաքանչյուր խաղացողի i որքան են նրանք ցանկանում առաջարկել տան համար j։ Սահմանել b_i(a) = \tilde b_{ik} եթե առաջարկող i տուն է ստանում k համապատասխանության մեջ a։ Հիմա հաշվարկեք a^*, առավելագույն քաշի երկկողմանի համապատասխանեցում առաջարկների նկատմամբ, և հաշվարկել։

: p_i = \left[ \max_{a \in A} \sum_{j \neq i} b_j(a) \right] - \sum_{j \neq i} b_j(a^*) .

Առաջին անդամը մեկ այլ առավելագույն քաշի երկմասն համընկնում է, իսկ երկրորդ անդամը կարող է հեշտությամբ հաշվարկվել հետևյալից՝ a^*։

## Արդարացի առաջարկի օպտիմալությունը
Հետևյալը ապացույց է այն բանի, որ աճուրդի հանված իրերի համար իրական գնահատականներ տալը օպտիմալ է։

Յուրաքանչյուր առաջարկողի համար b_i, թող v_i լինել նրանց իրական գնահատականը որևէ իրի նկատմամբ t_i, և ենթադրենք (առանց ընդհանրության խախտման), որ b_i հաղթանակներ t_i իրենց իրական գնահատականները ներկայացնելուց հետո։ Այնուհետև ցանցային կոմունալ ծառայությունը U_i ձեռք բերված b_i տրվում է շահած իրի իրենց սեփական գնահատականից՝ հանած վճարած գինը։

: 
\begin{align}
U_i &= v_i-\left(V^{M}_{N \setminus \{b_i\}}-V^{M \setminus \{t_i\}}_{N \setminus \{b_i\}}\right) \\
&=\sum_{j}v_j-\sum_{j\neq i}v_j+V^{M\setminus \{t_i\}}_{N\setminus \{b_i\}}-V^M_{N\setminus\{b_i\}} \\
&=\sum_j v_j-V^{M\setminus \{t_i\}}_{N\setminus \{b_i\}}+V^{M\setminus \{t_i\}}_{N\setminus \{b_i\}}-V^M_{N\setminus\{b_i\}} \\
&=\sum_j v_j-V^M_{N\setminus\{b_i\}.}
\end{align}


Ինչպես V^M_{N\setminus\{b_i\}} անկախ է v_i, մեխանիզմը հետապնդում է զուտ օգտակարության մաքսիմալացումը՝ կորպորատիվ համախառն օգտակարության մաքսիմալացման հետ մեկտեղ։ \sum_j v_j հայտարարված առաջարկի համար v_i։

Ավելի պարզ դարձնելու համար եկեք ներկայացնենք տարբերությունը U_i - U_j = \left[v_i + V^{M \setminus \{t_i\}}_{N \setminus \{b_i\}}\right] - \left[v_j + V^{M \setminus \{t_j\}}_{N \setminus \{b_i\}}\right]  ցանցային կոմունալ ծառայությունների միջև U_i -ի b_i արդար առաջարկի ներքո v_i ստացված իր t_i և ցանցային օգտակարություն U_j առաջարկողի b_i անարդարացի առաջարկների ներքո v'_i ապրանքի համար t_i ստացված իր t_j իրական օգտակարության վրա v_j։

\left[v_j + V^{M \setminus \{t_j\}}_{N \setminus \{b_i\}}\right]  ոչ ճշմարիտ առաջարկների միջոցով ստացված կորպորատիվ համախառն օգտակարությունն է։ Բայց բաշխումը, որը նշանակում է t_j դեպի b_i տարբերվում է բաշխման նշանակումից t_i դեպի b_i որը ստանում է առավելագույն (իրական) համախառն կորպորատիվ օգտակարությունը։ Հետևաբար \left[v_i + V^{M \setminus \{t_i\}}_{N \setminus \{b_i\}}\right] - \left[v_j + V^{M \setminus \{t_j\}}_{N \setminus \{b_i\}}\right]\geq 0  և U_i\geq U_j քեդ։

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

Կատեգորիա:Էլեկտրոնային առևտուր
Կատեգորիա:Խաղերի տեսություն
Կատեգորիա:Միկրոէկոնոմիկա
Կատեգորիա:Տնտեսություն