Raţionalitate şi echitate in situaţii cooperative (I)

Postarea numãrul 100 pe acest blog trebuie sã fie una „festivã” 🙂 Vreau prin urmare sã iau pentru moment o pauzã de la „politicale” de orice fel şi sã incep sã vã povestesc despre un rezultat matematic obţinut in ultimul an, impreunã cu prietenul Cosmin Bonchiş. Sunt destul de mândru de el, e o lucrare din cele bune pe care le-am scris (din pãcate preprint-ul de vreo 33 de pagini nu e public incã – il puteţi avea dacã mi-l cereţi in privat).

Scenariul de la care am plecat[1] e urmãtorul :

  • n jucãtori vor sã impartã costurile atingerii unui obiectiv comun. Un exemplu e cumpãrarea de pizza in comun 🙂 Unele pizzerii (de exemplu aceasta) oferã avantaje de genul „cumperi 5 pizza, primeşti 10” 🙂 E mai avantajos atunci sã te asociezi.
  • asocierea creazã o nouã problemã: dat fiind cã agenţii nu cumpãrã neapãrat acelaşi numãr de pizze (unul vrea una, altul poate douã :)), cum distribuim costurile intre agenţi ?

Exemplul cumva frivol de mai sus e modelat matematic de ceea ce in teoria jocurilor se numeşte un joc cooperativ, mai precis un joc cooperativ concav. Dincolo de cumpãrarea de pizza, el intervine in multe situaţii „practice”, de exemplu in teoria informaţiei in reţele distribuite, stabilirea preţurilor serviciilor de internet atât la utilizatorul final cât şi intre provideri  (ISP), probleme de mediu, de asigurãri, sisteme multi-agent in informaticã, ştiinţe politice (de exemplu la probleme legate de Uniunea Europeanã) …. in fine, lista e mult mai lungã.

Matematic un joc cooperativ e dat de:

    • o mulţime N de agenţi.
    • o funcţie de cost c definitã pe mulţimea pãrţilor lui N, c:\mathcal{P}(N)\rightarrow [0,\infty) cu c(\emptyset)=0. Intuitiv c(S) e costul total pe care il plãtesc agenţii din mulţimea S dacã se asociazã.

Faptul cã jocul e concav inseamnã urmãtorul lucru: costul marginal al unui agent care se alãturã unei coaliţii scade pe mãsurã ce coaliţia se lãrgeşte (mai spunem şi cã funcţia c este submodularã).
In simboluri:

S\subseteq T implicã c(S\cup \{x\})-c(S)\geq c(T\cup \{x\})-c(T).

O condiţie echivalentã este urmãtoarea: pentru toate mulţimile de agenţi A,B\subseteq N, c(A\cup B)+c(A\cap B)\leq c(A)+c(B).

Cum modelez o alocare a costurilor pe jucãtori ? Evident, cu un vector x=(x_{i})_{i\in V}. Costurile sunt nenegative: x_{i}\geq 0. Mai trebuie sã adaug o condiţie de raţionalitate, fãrã de care coaliţia nu s-ar forma (sau n-ar rezista): costurile trebuie impãrţite de aşa manierã incât niciun agent sau subcoaliţie de agenţi nu plãtesc mai mult decât ar plãti dacã ar fi pe cont propriu – alfel n-ar mai fi interesaţi sã fie membri ai marii coaliţii. In simboluri:

\forall (S\subseteq V): \sum_{i\in S} x_{i}\leq c(S).

Pe de altã parte costul total trebuie impãrţit intre toţi agenţii:

\sum_{i\in N} x_{i}=c(N).

Alocãrile cu aceste proprietãţi formeazã nucleul (eng. core) jocului. Voi folosi in postarea aceasta traducerea nucleu deşi mai corect ar fi miez, şi existã un concept inrudit cu core-ul numit in englezã nucleolus. Am ales sã ignor aici, pentru simplitate, aceste lucruri.

Nucleul s-ar putea sã nu conţinã niciun vector. Insã pentru jocurile concave acest lucru nu se intâmplã: rezultatul, unul simplu dar elegant, ii aparţine  matematicianului/economistului Lloyd Shapley, şi poate fi inţeles foarte uşor: sã considerãm o ordonare a jucãtorilor datã de o permutare arbitrarã \sigma=(\sigma(1),\sigma(2),\ldots, \sigma(n)). Sã considerãm alocarea care alocã la pasul i costul c(\{\sigma(1),\ldots, \sigma(i)\})-c(\{\sigma(1),\ldots, \sigma(i-1)\}) agentului cu index \sigma(i).

LEMÃ: Dacã funcţia cost c este submodularã atunci alocarea x_{\sigma} definitã ca mai sus este un element al nucleului jocului.

Demonstraţie:

Fie S\subseteq N o mulţime de agenţi. Vom demonstra relaţia necesarã prin inducţie dupã cardinalul lui S.

Din submodularitate (cu A=\{\sigma(1),\ldots, \sigma(i-1)\}, B=\{\sigma(i)\} rezultã imediat faptul cã x_{\sigma(i)}\leq c(\{\sigma(i)\}), stabilind adevãrul lemei când |S|=1.

Sã presupunem acum cã S este o mulţime de cardinal cel puţin 2, pe care o descompunem in S=T\cup \{j\}, unde j este elementul cu cel mai mare index, j=\sigma(i), din toate elementele lui S.

Avem x_{j}=c(\{\sigma(1),\sigma(2),\ldots, \sigma(i)\})-c(\{\sigma(1),\sigma(2),\ldots, \sigma(i-1)\}) \leq c(T\cup \{j\})-c(T) (din submodularitatea lui c şi faptul cã T\subseteq \{\sigma(1),\sigma(2),\ldots, \sigma(i-1)\}. Aplicând acum ipoteza de inducţie lui T deducem x_{j}\leq c(S)-\sum_{i\in T}x_{i}, adicã ce trebuia sã demonstrãm. \Box

ECHITATE IN ALOCAREA COSTURILOR: VALOAREA SHAPLEY.

Lema de mai sus ne oferã n! puncte in nucleu[2]. De fapt putem observa cã orice combinaţie liniarã de aceste puncte este in nucleu[3]. Se pune problema cum alegem punctul cel mai fair din toate aceste alocãri posibile intre jucãtori ? Alocarea pur egalitarã s-ar putea sã nu fie in nucleu şi, oricum, nu e ceea ce cãutãm: când comanzi pizza 🙂 dacã primul agent vrea 2 pizze iar al doilea doar una, nu e fair sã plãteascã egal. Aceeaşi problemã o are, pe de altã parte, şi alocarea proporţionalã: in exemplul cu Pizzeria Dopo Poco de mai sus :), primul agent poate primi douã pizze plãtind doar una, şi nu-i convine asocierea cu al doilea dacã va fi pus sã plateascã dublu faţã de agentul 2 (adicã 4/3 din costul unei pizze)[4]

O soluţie de compromis este urmãtoarea: unui agent ii alocãm media payoff-urilor obţinute cu schema de mai sus, unde media e luatã dupã toate permutãrile \sigma \in S_{n}.

Acest lucru ne garanteazã faptul cã alocarea rezultatã este, in cazul jocurilor concave cel puţin, in nucleu. Ea poartã numele de alocarea (valoarea) Shapley a jocului nostru cooperativ, şi e cea mai utilizatã soluţie pentru jocuri cooperative. Ea este şi echitabilã intr-un anumit sens, axiomatic (pe care nu vreau sã il discut aici). Totuşi utilizarea valorii Shapley nu e lipsitã de probleme.

CUM CALCULÃM VALOAREA SHAPLEY ?

V-aţi dat seama poate: media din definiţia valorii Shapley presupune o sumã cu n! termeni. Acest lucru e imposibil de realizat practic.

Deşi existã metode mai inteligente de calcul (exact sau aproximativ) a valorii Shapley, limitãrile de mai sus sunt intr-un anumit sens insurmontabile: Deng şi Papadimitriou au arãtat cã problema de a calcula exact indexul Shapley este completã pentru clasa de complexitate \#P. Intr-un anumit sens acest lucru o face probabil „mai dificilã” decât problemele NP-complete.

Aceasta nu e singura problemã a valorii Shapley. Despre asta (şi rezultatele mele cu Cosmin) intr-un episod viitor 🙂

NOTE:

[1][INAPOI] Mint cumva, cum se intâmplã de multe ori originea problemei a fost cu totul alta. Totul a inceput cumva in joacã, drept o generalizare care unificã douã rezultate existente pe care i-am propus-o ca exerciţiu lui Cosmin in vara lui 2010, la un prânz la Grãdina Bãnãţeana 🙂 Generalizarea s-a dovedit mult mai complicatã/interesantã decât mã aşteptam. Şi mi-am dat seama abia mai pe urmã cã de fapt ne ocupãm cu jocuri cooperative 🙂

[2][INAPOI] Prin urmare conceptul de nucleu nu determinã in general o unicã „cea mai bunã” soluţie.

[3][INAPOI] De fapt in cazul jocurilor concave ştim mai mult: nucleul este un poliedru cu toate colţurile in punctele de tip (x_{\sigma}). Altfel spus toate punctele din nucleu sunt combinaţii liniare de puncte de tip (x_{\sigma}).

[4][INAPOI] Presupunem (nu ştiu dacã este adevãrat) faptul cã Dopo Poco iţi poate livra trei pizze in loc de patru, dar nu va accepta niciodatã plata (sau livrarea) unei pizza şi jumãtate, de exemplu 🙂

Anunțuri
Acest articol a fost publicat în Uncategorized. Pune un semn de carte cu legătura permanentă.

Lasă un răspuns

Completează mai jos detaliile tale sau dă clic pe un icon pentru a te autentifica:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare / Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare / Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare / Schimbă )

Fotografie Google+

Comentezi folosind contul tău Google+. Dezautentificare / Schimbă )

Conectare la %s