Aus Wikiludia

Inhaltsverzeichnis

1 Modellierung
- 1.1 vom Treffen(Jörn)
- 1.2 Mechanism Design / Social Choice (Flo)

Modellierung

Momentan haben wir 2 Ansätze, die es wohl zu vereinen gilt - den vom Treffen und einen der zumindest schon mal nach Mechanism Design kriterien gebaut ist. In jedem Fall sollten wir an der Modellierung da noch was tun.

vom Treffen(Jörn)

Modellkomponenten:

Zentrale Instanz(en): ein oder mehrere (jeweils zuständig für einen Cluster) Verwaltungsserver, die durch wechselnde Peers realisiert werden (rollierend); Schlagwort "cluster representatives"
Diskrete Zeitlinie $T = \mathbb{N}$ bzw. $T = \{0,1, \ldots, t\}$
Individueen bzw. Spielermenge $M=\{1,2, \ldots, n\}$
Zustände $Z = {C, S}$ , d.h. ein Peer kann in Runde t genau eine Rolle "Client" oder "Server" annehmen
Auswahlfunktion zur Rollen- bzw. Zustandsauswahl je Runde: $z: M \times T \rightarrow Z$
Historien (Zeitindex unten wie üblich): $h^{i}(t) = (h_{1}^i, h_{2}^i, \ldots, h_{t}^i) \in H(t):=(h^1(t), \ldots, h^n(t)), i=1,\ldots,n, \quad t \in T$
Reputationsfunktion bzw. -statistik: $r: H \rightarrow [0,1]^n$ bzw. $r_i: h_i \rightarrow [0,1]$ für Individuum i
Aktionsmenge (vgl. gemischte Strategie): $A = {c, d}$ (cooperate, defect)
Wahrscheinlichkeit der Interaktion mit Individuum j, in Abhängigkeit der Reputation (aktuell im Zeitpunkt t):

  ; hier

Strategiefunktion des Individuums (wahlweise):
- fest (vgl. evolutorisches Spiel), d.h. die Strategie des Individuums ist in dessen Genen kodiert: konstante Funktion $s_i: \rightarrow [0,1], s_i(x) = const.$
- variabel, d.h. z.B. abhängig von eigener (i) und/oder der Reputation des Kommunikationspartners (j) zum aktuellen Zeitpunkt: $s_i(t): (h^i(t), h^j(t)) \rightarrow [0,1], s_i(\cdot,\cdot) \in [0,1], t \in T$
Nutzenfunktion des Basisspiels: Payoff-Matrix, d.h. $u_i(a_i,a_j) = x_i,\quad a_i, a_j \in A, x_i \in \mathbb{R}$ ; hier: $u (c, c) = (7, - 1), u (c, d) = u (d, c) = u (d, d) = (0,0)$

Nutzenfunktion des Gesamtspiels bzgl. Individuum i: $u_i(t) := \sum_{\tau=0}^t u_i(a_i^{\tau}, a_x^{\tau}) \quad a_i^{\tau}, a_x^{\tau} \in A, x \in M$

Mögliche Erweiterungen:

Strategieerweiterungen:
- Request file erst in Runde $t+k, \quad k>0$
Private history und subjektive Reputationseinschätzung des Individuums i bzgl. der anderen.
Bandbreite einschränken (im Moment gar nicht modelliert)

Mechanism Design / Social Choice (Flo)

Überlegungen:

Was ist das Ziel des Systems?

Das Sharing zu maximieren, also: Viele Sachen sharen mit viel Bandbreite. D.h. insbesondere zunächst:

Für einen genehmigten Download möglichst viel Bandbreite zur Verfügung zu stellen. Es wird zunächst nun ein Mechanismus entworfen der eben genau einen Download regelt.

In wiefern kann der Mechanismus die subjektiven Wertvorstellungen der Agenten antizipieren?

Prinzipiell diese speziell gar nicht, da es sich um rein individuelle, teils auch in der nicht-rationellen Psyche, zumindest aber in einer dem Mechanismus nicht bekannten Information begründete Wertvorstellungen handelt. Ein Agent möchte eben gewisse Daten downloaden, andere eventuell nicht.

Das einzige, das der Mechanismus annehmen kann ist, dass ein Agent prinzipiell filesharing nutzen will - sonst wäre er nicht am System beteiligt.

Daher wird der Nutzen über Downloadmöglichkeiten geregelt und der Mechanismus nimmt an, daß mehr Downloadmöglichkeit auch einen Nutzengewinn für den Agenten bedeutet.

sollte das nicht gelten, so gibt es 2 Fälle:

Es wird angenommen, daß ein Agent der gerade nichts downloaden will und der mit seinem Kontostand zufrieden ist, nicht am System teilnimmt, bis sich dieser Zustand wieder ändert.

Ein Agent der downloaden will, aber einen Kontostand hat der hoch genug ist, wird bei rationalem Handeln seinen Upload sperren. Ein Eingreifen hier ist in diesem Fall vom (diesem) Mechanismus nicht möglich, da er dem Agenten keine Anreize bieten kann. Außerhalb des Mechanismus kann hier jedoch eingegriffen werden um die Häufigkeit dieses Falls zu verringern (Verfall des Downloadguthabens etc.).

Modellierung

Hier wird der Mechanismus $M = {Σ, g, p 1,..., p n}$ betrachtet, der einen einzelnen, von einer Zentralinstanz (Unterschied zum bisherigen Modell!) genehmigten Download der Datei $\tilde{d} \in D$ (mit D als Menge der Dateien) optimiert, indem Anzahl der Uploader und deren Bandbreite maximiert werden.

Typ

Ein Agent hat in jeder Zeiteinheit einen Typ $t_i =(d_i, b_i) \in T = \mathbb{P}(D) \times R^+$ , wobei D die Menge der filesharingrelevanten Dateien eines Agenten ist und die für den Upload verfügbare Bandbreite als reelle Zahl modelliert wird.

Beachte: Der Typ stellt die maximalen Möglichkeiten eines Agenten dar. Wie er handelt folgt im nächsten Punkt.

Strategie

ist hier "direct revealing", d.h. $\Sigma = T, \hat{t_i}: T \times \Sigma^{n-1}\rightarrow\Sigma$ . Ein Agent gibt seinen Typ an. Hier kann er jedoch einen Typ angeben der weniger Dateien oder eine geringere Bandbreite hat.

Ergebnis

Von welchen Peers die Datei heruntergeladen wird.

Der Ergebnisraum O hat folgende Gestalt

$O = \{ o \in [0,1]^n : (\forall j \in \{1, ...,n \}: I_{d_j}(\tilde{d}) = 0 \Rightarrow o_j = 0) \wedge \sum_{j=1}^{n}o_j =1\}$

wobei $o = (o 1,..., o n)$ und $I_{d_j}$ die Indikatorfunktion ist, die angibt, ob Agent j die gewünschte Datei hat oder nicht.

Im Klartext: jedem vorhandenen/angegebenen Typ eines jeweiligen Agenten wird eine Zahl zwischen 0 und 1 zugeordnet. Hat der Typ das File nicht, so ist dies Null. Die Summe all dieser Zahlen ist 1. Der Ergebnisraum beschreibt, wieviel Prozent der Datei von welchem Agenten heruntergeladen werden.

Social Choice Function

Wählt $o \in O$ so, dass die Gesamtbandbreite maximal wird (und die Übertragungszeit somit minimal wird).

Also gilt für $f: T^n \rightarrow O; f(t) = \left(\frac{I_{d_i}(\tilde d) \cdot b_i}{\sum_{j=1}^n I_{d_j}(\tilde d) \cdot b_j}\right)_{i \in \{1, ...,n\} }$

Im Klartext: Jeder Agent bekommt seinen prozentualen Anteil an der verfügbaren Gesamtbandbreite zugewiesen.

Ergebnisfunktion

Sie soll der Social Choice Function so nahe wie möglich kommen, hat jedoch im Gegensatz zur SCF nur Zugriff auf die Strategien, nicht auf die Typen.

D.h.: $g: \Sigma^n \rightarrow O; g(t) = \left(\frac{I_{\hat{d}_i}(\tilde d) \cdot\hat{b}_i}{\sum_{j=1}^n I_{\hat{d}_j}(\tilde d) \cdot\hat{b}_j}\right)_{i \in \{1, ...,n\} }$

Nutzenfunktion, Value, Payment

Upload per se bringt keinen Nutzen, d.h. für die individuelle value $v_i: O \times T \rightarrow \mathbb{R};$ gilt $v_i \left(o,t_i\right) \le 0$

Damit teilgenommen wird muß für die individuelle Nutzenfunktion $u_i: O \times \mathbb{R} \times T \rightarrow \mathbb{R};$ gilt $u_i \left(o,p_i,t_i\right) \ge 0$

hieraus folgt bei quasilinearer Nutzenfunktion $u_i \left(o,p_i,t_i\right) = v_i \left(o,t_i\right)+p_i$ direkt für das individuelle payment $p i$ , daß $p_i \ge - v_i \left(o,t_i\right)$

Es sollte klar ersichtlich sein, daß das payment sich aus Sicht des Mechanismus, der den wahren Typ der Agenten nicht kenn nur nach den Strategien richten kann, also $p_i: \Sigma^n \rightarrow \mathbb{R}$

Wahl des Payments und Wirksamkeit des Mechanismus

Wählen wir einfach $p_i = - v_i \left(o,t_i\right)$ , so gibt es keinen Anreiz einen falschen Typ anzugeben. Jedoch auch keinen den richtigen anzugeben. Da wir davon ausgehen können, daß eine falsche Typangabe bezüglich höherer Bandbreite als verfügbar oder nicht verfügbarer Dateien ausgeschlossen werden kann (sei es technisch oder sei es mit drakonischen Strafen in der Paymentfunktion), werden im Zweifel nur kleinere Werte angegeben. Will man Angabe des richtigen Typs erzwingen und nicht nur Angabe des falschen Typs unrentabel machen, so muß man eben die payment Funktion so wählen, dass mit $p_i(\hat{t})= I_{\hat{d}_i} \cdot \tilde{p}_i(\hat{b}_i), \hat{t} \in \Sigma^n$ gilt, daß $\frac{d\tilde{p}_i}{d\hat{b}_i} >1$ , da so mit zunehmender Bandbreite zunehmend Gewinn gemacht wird.