Gewinnstrategie im Spiel der Drillinge

Das Spiel der Drillinge wird durch eine endliche Menge von Elementen $X$ und eine endliche Mehrfachmenge $T$ die Tripletts von Elementen enthält. Zwei Spieler wählen abwechselnd Elemente aus $X$ bis alle Elemente aufgenommen sind. Dann ist die Punktzahl jedes Spielers die Anzahl der Drillinge von $T$ in denen er mindestens 2 Elemente hat.

Ein Standardargument, das Strategie stiehlt, zeigt, dass der erste Spieler immer mindestens $|T|/2$ punkten kann T | / 2 . Nehmen wir im Widerspruch an, dass es falsch ist. Dann kann der zweite Spieler mehr als $|T|/2$ erzielen T | / 2 . Aber dann kann der erste Spieler, der die Gewinnstrategie des zweiten Spielers kopiert, mehr als $|T|/2$ Punkte erzielen T | / 2 auch. Dies ist ein Widerspruch, da die Summe der Punkte $|T|$.

FRAGE: Was ist eine explizite Strategie für den ersten Spieler, der eine Punktzahl von mindestens $|T|/2$ ?

BEARBEITEN: Hier ist eine explizite Strategie für den ersten Spieler, der mindestens $3|T|/8$ erhält T | / 8 . Ordnen Sie jedem Triplett in $T$ ein potentielles $P(a,b)$ basierend auf der Anzahl seiner Elemente, die der (erste, zweite) Spieler genommen hat:

Die Strategie von Spieler 1 lautet: Wählen Sie ein Element aus, das die potenzielle Summe maximiert. Angenommen, das Element ist $x$ und das als nächstes von Spieler 2 ausgewählte Element ist $y$ . Ich behaupte, dass die Potentialsumme nach diesen beiden Zügen schwach zunimmt:

• Das Potential eines Tripletts, das weder $x$ noch $y$ enthält, ändert sich nicht.
• Das Potential eines Tripletts, das sowohl $x$ als auch $y$ ändert sich von $P(a,b)$ zu $P(a+1,b+1)$ , das immer mindestens genauso groß ist.
• Das Potential eines Tripletts, das $x$ und nicht $y$ steigt um $P(a+1,b)-P(a,b)$ ;
• Das Potential eines Tripletts, das $y$ und nicht $x$ nimmt um $P(a,b)-P(a,b+1)$ ; Es ist leicht in der Tabelle zu überprüfen, dass $P(a,b)-P(a,b+1)\leq P(a+1,b)-P(a,b)$ (Die Abnahme, wenn Sie nach rechts gehen, ist höchstens die Zunahme, wenn Sie nach unten gehen).

Insgesamt erhöht sich die Potentialsumme um die Summe von $P(a+1,b)-P(a,b)$ über alle Tripletts, die $x$ enthalten , und verringert sich um (höchstens) die Summe von $P(a+1,b)-P(a,b)$ über alle Tripletts, die $y$ enthalten . Durch die Wahl von $x$ ist die erste Summe schwach größer. Die Potentialsumme steigt also schwach an.

Die endgültige Potentialsumme beträgt also mindestens $3|T|/8$ . Am Ende hat ein Triplett das Potenzial $1$ ( $0$ ), wenn es von Spieler 1 (2) gewonnen wird, sodass die endgültige Potenzialsumme der Punktzahl von Spieler 1 entspricht.

Dies ist kein vollständiger Beweis, aber hier ist eine Rechtfertigung dafür, warum bekannte Vermutungen implizieren, dass das Spiel möglicherweise rechenintensiv zu lösen ist. Ich werde nämlich argumentieren, dass es wahrscheinlich schon schwierig ist, den richtigen ersten Schritt zu finden.

$\textrm{Denser Induced Subgraph}$

Zwei Spieler, A und B, wählen abwechselnd Scheitelpunkte in einem gemeinsamen Diagramm G aus. Scheitelpunkte können nur einmal ausgewählt werden. Wenn keine Eckpunkte mehr ausgewählt werden müssen, werden die durch die Auswahl jedes Spielers induzierten Untergraphen verglichen. Der Spieler mit der größeren Anzahl induzierter Kanten wird zum Gewinner erklärt.

Proof-Gliederung:

$\textrm{Denser Induced Subgraph}$$G = (V,E)$$\textrm{Triplets}$$G$$V \cup (E \times \{0,1\})$$e \in E$$u$$v$$(u, v, (e, 0))$$(u, v, (e, 1))$$v \in V$$(v,v,v)$

$\mathrm{Triplets}$$V$$E$$E \times \{0,1\}$$1$$1$$V$$4$

$|V|$$V$

$V_A$$V_B$$(v,v,v)$$4|V|/2 + 2|E[V_A]| + (|E| - |E[V_A]| - |E[V_B]|)$$E[S]$$S$$\square$

In diesem Sinne können wir auf einige Arbeiten in der Literatur zur Erkennung dichter Teilgraphen zurückgreifen. Es gibt eine Menge relevanter Arbeiten, auf die man sich berufen kann, aber zur Vereinfachung der Analyse werde ich mich auf eine bestimmte Vermutung über die Schwierigkeit berufen, dichte Zufallsgraphen in spärlichen Zufallsgraphen zu finden (ich glaube, dass diese Abhängigkeit beseitigt werden kann mit nur ein wenig mehr Nachdenken, aber dies ist kein formaler Beweis).

$G = (V,E)$$G(n, 1/\sqrt{n})$$1/2$$G$$V'$$V$$\sqrt{n}$$u,v$$V'$$(u,v)$$E$$n^{-1/4}$$G$

$51\%$

Angenommen, das Diagramm wurde erweitert und es gibt eine ungewöhnlich dichte Komponente. Da kein Poly-Time-Algorithmus das Vorhandensein dieses dichten Teilgraphen zuverlässig erfassen kann, kann er auch keinen Scheitelpunkt aus dieser dichten Komponente zuverlässig abtasten (z. B. aufgrund der Selbstreduzierbarkeit). Da (aus Sicht von Spieler A) ein zufälliger Scheitelpunkt aus einem reinen Erdos-Renyi-Diagramm ausgewählt wird, spielt es daher keine Rolle, welchen Scheitelpunkt A auswählt (bis zu einer kleinen Änderung seiner Punktzahl, die letztendlich keine Rolle spielt ¹⁾$r$$r-1$$r$

$r$$r$$\Omega(n^{1/4})$

^$O(1)$

Obwohl das Spiel für Spieler A sehr schwach gelöst ist, ist es daher unwahrscheinlich, dass es rechnerisch machbar ist, dass A auch nur den ersten Zug der Gewinnstrategie ausspielt.

Ein Ansatz, der auf der Härte des "normalen" dichtesten Teilgraphenproblems basiert, sollte auch hier nicht schwer zu erreichen sein, und das Zusammensetzen der Reduktion mit einem Ergebnis der Härte der Annäherung kann wahrscheinlich verwendet werden, um eine Art von Härte zu erhalten, die auf allgemeineren Vermutungen basiert ( zB ETH). Ich bin mir nicht sicher, wie schwierig es sein kann, auf NP-Härte (oder darüber hinaus) aufzusteigen.