Gewinnstrategie im Spiel der Drillinge

8

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:

ab012303/800013/41/2021131
Zunächst hat jedes Triplett Potential 3/8 , so dass die Potentialsumme 3|T|/8 .

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)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.

Erel Segal-Halevi
quelle
1
Es ist ziemlich unwahrscheinlich, dass es eine einfache Strategie gibt, wie es bei den meisten Spielen der Fall ist, bei denen das Stehlen von Strategien beweist, dass der erste Spieler immer gewinnen kann.
Domotorp
Ich stimme domtorp zu. Ich vermute, dass "das Element mit der höchsten Anzahl von Vorkommen nehmen" die richtige grundlegende Heuristik ist, obwohl die Anzahl der Vorkommen nicht genau das Richtige ist, um gezählt zu werden. Argumente, die Strategie stehlen, bedeuten normalerweise, dass Sie, wenn Sie einer bestimmten Heuristik folgen, immer defensiv spielen können, wenn Sie herausgefordert werden, und am Ende gewinnen. Es geht darum herauszufinden, wie und wann man defensiv spielt.
Stella Biderman
Um die vorherigen Kommentatoren zu ergänzen, wäre es sehr interessant, wenn ein Spiel dieser Art (mit Strategie-Diebstahl in einem anderen natürlichen Rahmen als "Ich schneide dich wählen") als PSPACE-vollständig erwiesen wäre (mit zum Beispiel → ein Gewinn zuerst Bewegen Sie sich als PSPACE abgeschlossen). T
Dmytro Taranovsky

Antworten:

3

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.


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:

Denser Induced SubgraphG=(V,E)TripletsGV(E×{0,1})eEuv(u,v,(e,0))(u,v,(e,1))vV(v,v,v)

TripletsVEE×{0,1}11V4

|V|V

VAVB(v,v,v)4|V|/2+2|E[VA]|+(|E||E[VA]||E[VB]|)E[S]S


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/n)1/2GVVnu,vV(u,v)En1/4G

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 1)rr1r

rrΩ(n1/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.

Yonatan N.
quelle
Die Reduktion ist sehr cool. Können Sie einen Hinweis auf diese Vermutung "The Planted Dense Subgraph" geben?
Erel Segal-Halevi
Die Vermutung ist mehrmals unter leicht unterschiedlichen Geschmacksrichtungen aufgetreten , einschließlich cc.gatech.edu/~klai9/FinalThesis.pdf (Vermutung 2), users.cs.duke.edu/~rongge/derivatives_ics.pdf (Densest Subgraph Assumption). , proceedings.mlr.press/v40/Hajek15.pdf (PC - Hypothese), math.ias.edu/files/ABW10_STOC.pdf (DUE Annahme), core.ac.uk/download/pdf/62922882.pdf (gepflanzt Dense Subgraph Vermutung) unter anderem. Die Endergebnisse sind ähnlich genug, dass die obige Konstruktion fast keine Modifikation benötigt, um an den gewählten Geschmack angepasst zu werden.
Yonatan N
3|T|/83|T|/8|T|/2
Nicht aus dem Kopf, aber ich werde sehen, ob ich über das Wochenende noch etwas darüber nachdenken kann. Nettes 3/8 Argument!
Yonatan N