Biased positional game

A biased positional game[1][2]: 27–42  is a variant of a positional game. Like most positional games, it is described by a set of positions/points/elements () and a family of subsets (), which are usually called the winning-sets. It is played by two players who take turns picking elements until all elements are taken. While in the standard game each player picks one element per turn, in the biased game each player takes a different number of elements.

More formally, for every two positive integers p and q, a (p:q)-positional game is a game in which the first player picks p elements per turn and the second player picks q elements per turn.

The main question of interest regarding biased positional games is what is their threshold bias - what is the bias in which the winning-power switches from one player to the other player.

Example

As an example, consider the triangle game. In this game, the elements are all edges of a complete graph on n vertices, and the winning-sets are all triangles (=cliques on 3 vertices). Suppose we play it as a Maker-Breaker game, i.e., the goal of Maker (the first player) is to take a triangle and the goal of Breaker (the second player) is to prevent Maker from taking a triangle. Using a simple case-analysis, it can be proved that Maker has a winning strategy whenever n is at least 6. Therefore, it is interesting to ask whether this advantaged can be biased by letting Breaker pick more than 1 element per turn.

Indeed, it is possible to prove that:[1]

  • For every , Maker wins the (1:q) triangle game on n vertices.
  • For every , Breaker wins the (1:q) triangle game on n vertices.

A winning condition for Breaker

In an unbiased Maker-Breaker game, the Erdos-Selfridge theorem gives a winning condition for Breaker. This condition can be generalized to biased games as follows:[3] [2]: 30–32 

  • If , then Breaker has a winning-strategy in the (p:q) game when playing first.
  • If , then Breaker has a winning-strategy in the (p:q) game even when playing second.

The strategy uses a potential function which generalized the function of Erdos-Selfridge. The potential of a (non-broken) winning-set E with |E| untaken elements is defined as . If Maker wins the game then there exists a set E with |E|=0, so its potential is 1; therefore, to prove that Breaker wins, it is sufficient to prove that the final potential-sum is less than 1. Indeed, by assumption, the potential-sum at Breaker's first turn is less than 1; and if Breaker always picks an element that maximizes the potential-drop, it is possible to show that the potential-sum always weakly decreases.

When each winning-set has elements, for some fixed k, Breaker's winning condition simplifies to: (when playing first) or (when playing second). This condition is tight: there are k-uniform set-families with sets where Maker wins.[4]

A winning condition for Maker

In an unbiased Maker-Breaker game, a theorem by Beck gives a winning condition for Maker. It uses the pair-degree of the hypergraph - denoted by . This condition can be generalized to biased games as follows:[3]

If , then Maker has a winning-strategy in the (p:q) game when playing first.

A winning condition for Avoider

In a biased Avoider-Enforcer game, the following conditions guarantee that Avoider has a winning strategy:[2]: 47–49 

  • If , then Avoider wins the (p:q) game when playing first, under both the strict and the monotonic ruleset. This is almost tight: there is an infinite family of (p:q) games in which this expression is slightly larger than 1 and Enforcer wins.[5] In particular, in the unbiased game the condition becomes . If the graph is k-uniform, the condition becomes . It is remarkable that this condition does not depend on q at all.
  • If each winning-set has at most k elements, and , then Avoider wins (p:q) game when playing first.[6]

See also

References

  1. ^ a b Chvátal, V.; Erdös, P. (1978). "Biased Positional Games". Annals of Discrete Mathematics. 2 (C): 221–229. doi:10.1016/S0167-5060(08)70335-2. ISSN 0167-5060.
  2. ^ a b c Hefetz, Dan; Krivelevich, Michael; Stojaković, Miloš; Szabó, Tibor (2014). Positional Games. Oberwolfach Seminars. Vol. 44. Basel: Birkhäuser Verlag GmbH. ISBN 978-3-0348-0824-8.
  3. ^ a b Beck, J. (1982). "Remarks on positional games. I". Acta Mathematica Academiae Scientiarum Hungaricae. 40 (1–2): 65–71. doi:10.1007/bf01897304. ISSN 0001-5954.
  4. ^ Sundberg, Eric Lars (2013-05-02). "Extremal Hypergraphs for the Biased Erdős-Selfridge Theorem". The Electronic Journal of Combinatorics. 20 (1). doi:10.37236/2394. ISSN 1077-8926.
  5. ^ Hefetz, Dan; Krivelevich, Michael; Szabó, Tibor (2007-07-01). "Avoider--Enforcer games". Journal of Combinatorial Theory, Series A. 114 (5): 840–853. doi:10.1016/j.jcta.2006.10.001. ISSN 0097-3165.
  6. ^ Bednarska-Bzdęga, Małgorzata (2014-01-12). "Avoider-Forcer Games on Hypergraphs with Small Rank". The Electronic Journal of Combinatorics. 21 (1): 1–2. doi:10.37236/3095. ISSN 1077-8926.

Read other articles:

Jakow Zak pada 1937 Yakov Izrailevich Zak (Ukrainian: Яків Ізраїлович Закcode: uk is deprecated ), (Rusia: Яков Израилевич Закcode: ru is deprecated ), Jiakov Israilevič Sak; Odessa, 20 November [K.J.: 7 November] 1913 – Moskwa, 28 Juni 1976) adalah seorang pianis dan guru Uni Soviet berdarah Yahudi. Lahir di Odessa, Zak belajar piano di Konservatorium Odessa di bawah bimbingan Maria Starkhova, mengambil kelas tentang harmoni khusus dengan Mykola Vilinsky,...

 

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (يوليو 2019) مؤشر لي كه كيانج نسبة إلى رئيس الوزراء الصيني لي كيه كيانج، هو مؤشر بديل لقياس النمو الاقتصادي. وفقًا لبرقيات لوزارة الخارجية الأمريكية المسربة عبر منصة ويك�...

 

Epping Forest in 2008 Electricity wires cut through the forest at Coed Plas-y-Nant (Clwydian Range AONB), Ruthin, Wales The United Kingdom,[Notes 1] being in the British Isles, is ideal for tree growth, thanks to its mild winters, plentiful rainfall, fertile soil and hill-sheltered topography. In the absence of people, much of Great Britain would be covered with mature oaks, except for Scotland. Although conditions for forestry are good, trees face threats from fungi, parasites and p...

Artikel ini memerlukan pemutakhiran informasi. Harap perbarui artikel dengan menambahkan informasi terbaru yang tersedia. Surabaya adalah sebuah kota sekaligus ibu kota atau pusat pemerintahan provinsi Jawa Timur dan kota terbesar kedua di Indonesia. Kota ini juga merupakan salah satu kota tertua di Asia Tenggara dan merupakan kota terbesar pada zaman Hindia Belanda. Kota ini adalah tempat bagi banyak bangunan tinggi. Kota ini saat ini sedang melalui tahap mengubah langit-langitnya dalam pros...

 

US gubernatorial election 1875 Kentucky gubernatorial election ← 1871 August 2, 1875 1879 →   Nominee James B. McCreary John Marshall Harlan Party Democratic Republican Popular vote 126,976 90,795 Percentage 58.31% 41.69% County resultsMcCreary:      50–60%      60–70%      70–80%      80–90%      >90%Harlan:    ...

 

Historic house in Herefordshire, England The Chase Hotel, Ross-on-Wye in 2008 The Chase in Ross-on-Wye in Herefordshire is a house of historical significance. It was built in 1818 by an attorney and was a private residence of several notable people until it was sold in 1927. After that time it was converted to a hotel and was used for this purpose until September 2019. As a hotel, it had accommodation and restaurant facilities and catered for special events, particularly weddings. In January ...

2007 Fort Worth mayoral election ← 2005 May 12, 2007[1] 2009 → Turnout6.93%[1]   Candidate Mike Moncrief Louis McBee Party Nonpartisan Nonpartisan Popular vote 16,424 3,138 Percentage 80.17% 15.32% Mayor before election Mike Moncrief Democratic Elected Mayor Mike Moncrief Democratic Elections in Texas Federal government Presidential elections 1848 1852 1856 1860 1872 1876 1880 1884 1888 1892 1896 1900 1904 1908 1912 1916 1920 1924 1928 1932 193...

 

  提示:此条目页的主题不是中國—瑞士關係。   關於中華民國與「瑞」字國家的外交關係,詳見中瑞關係 (消歧義)。 中華民國—瑞士關係 中華民國 瑞士 代表機構駐瑞士台北文化經濟代表團瑞士商務辦事處代表代表 黃偉峰 大使[註 1][4]處長 陶方婭[5]Mrs. Claudia Fontana Tobiassen 中華民國—瑞士關係(德語:Schweizerische–republik china Beziehungen、法�...

 

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (ديسمبر 2018) كأس ملك إسبانيا 2017–18البلد إسبانياالفرق83البطلبرشلونةالوصيفإشبيليةالمباريات الملعوبة107الأهداف المسجل�...

قائمة الحكومات التركية (بالتركية: Türkiye Hükümetleri Listesi) وهي قائمة بجميع الوزارات التي حكمت في تركيا بعد انتهاء الدولة العثمانية وتأسيس الجمهورية التركية فتبدأ منذ أول حكومة بتاريخ 1923 إلى الآن.[1] القائمة الرقم رئيس الوزراء فترة العهدة التصويت الأحزاب 1 عصمت إينونو 1 نوفمبر 1...

 

Second ArmySecond Army's Shoulder Sleeve InsigniaActiveOctober 1918 – April 1919October 1933 – January 1966 July 1983 – July 1995 March 2014 – April 2017Allegiance United StatesBranch United States ArmyTypeField armyPart ofRegular ArmyMotto(s)Tout PréparéEngagementsWorld War ICommandersNotablecommandersWilliam SimpsonLeonard T. GerowEdward H. BrooksGeorge Windle Read, Jr.InsigniaSecond Army's distinctive unit insigniaFlagSecond Army's SSI Prior to 1950sMilitary unit ...

 

US GDP gap since 1975[1] US potential (light) and actual (bold) GDP estimates from the Congressional Budget Office in January 2009. The difference between the two represents the GDP gap.[2] IMF estimates of the 2009 output gaps as % of GDP by country The GDP gap or the output gap is the difference between actual GDP or actual output and potential GDP, in an attempt to identify the current economic position over the business cycle. The measure of output gap is largely used...

Viktor RöthlinNazionalità Svizzera Altezza174 cm Peso57 kg Atletica leggera SpecialitàMaratona Record 5000 m 13'4028 (1999) 10000 m 28'2253 (2000) Mezza maratona 1h02'16 (2006) Maratona 2h07'23 (2008) CarrieraNazionale 2000-2014 Svizzera Palmarès Competizione Ori Argenti Bronzi Mondiali 0 0 1 Europei 1 1 0 Vedi maggiori dettagli  Modifica dati su Wikidata · Manuale Viktor Röthlin (Kerns, 14 ottobre 1974) è un ex maratoneta svizzero. Indice 1 Palmarès 2 Altre competizion...

 

جواز سفر أردنيالغلاف الأمامي للجواز السفر الأردنيمعلومات عامةنوع المستند جواز سفرالبلد الأردنالغرض السفر خارج الاردنصادر عن  الأردنمتطلبات الاستحقاق الجنسية الأردنيةالانتهاء خمسة سنوات او حسب نوع الجوازتعديل - تعديل مصدري - تعديل ويكي بيانات جواز السفر الأردني هو ال...

 

German businessman (1933–2023) Heinz DürrDürr in 2013Born(1933-07-16)16 July 1933Stuttgart, GermanyDied27 November 2023(2023-11-27) (aged 90)OccupationBusiness executiveOrganizationsDürr AGAEGDeutsche Bahn Heinz Dürr (16 July 1933 – 27 November 2023) was a German businessman. He was a major shareholder in the Dürr AG, founded in Stuttgart in 1895. Dürr was chairman of the board of AEG from 1980 to 1990, and from 1991 to 1994 he served as executive board chairman of Deutsche Bun...

Pour les articles homonymes, voir L3. Carro Armato L3 Une L3 cc (à gauche) et une L3/35 (à droite) capturées devant Bardia en Libye en 1941. Caractéristiques de service Service 1933-1947 environ Utilisateurs Italie Brésil Bulgarie République de Chine État indépendant de Croatie Hongrie Espagne nationalisteAutres (voir texte) Conflits Seconde guerre italo-éthiopienne, Guerre d'Espagne, guerre sino-japonaise, Guerre slovaquo-hongroise, Invasion italienne de l'Albanie, Seconde Guerre m...

 

Jean IIRaja SiprusBerkuasa29 Juni 1432 - 28 Juli 1458PendahuluYanusPenerusCharlotteKelahiran16 Mei 1418Kematian28 Juli 1458PasanganAmadea Palaiologina dari Montferrat Eilene PalaiologinaKeturunanCharlotte dari Lusignan Jacques II dari SiprusWangsaPoitiers-LusignanAyahYanus dari SiprusIbuCharlotte, Ratu Siprus Jean II atau III dari Siprus (16 Mei 1418 – 28 Juli 1458) merupakan seorang Raja Siprus dan Armenia dan juga bergelar Raja Yerusalem dari tahun 1432 sampai 1458. Ia sebelumnya bergelar...

 

Statistics of Indian states in terms of Poverty Poverty rate map of India by prevalence in 2022, among its states and union territories States and union territories of India ordered by Area Population GDP (per capita) Abbreviations Access to safe drinking water Availability of toilets Capitals Child nutrition Crime rate Ease of doing business Electricity penetration Exports Fertility rate Forest cover Highest point HDI Home ownership Household size Human trafficking Infant mortality rate Inst...

Gaelic football competition 1937–38 National Football LeagueLeague detailsDates24 October 1937 – 3 July 1938League championsWinnersMayo (5th win)CaptainPaddy MoclairLeague runners-upRunners-upWexfordCaptainPeter Hayes← 1936–37 1938–39 → The 1937–38 National Football League was the 11th staging of the National Football League (NFL), an annual Gaelic football tournament for the Gaelic Athletic Association county teams of Ireland. Mayo successfully defended its league title...

 

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。(このテンプレートの使い方)出典検索?: Dancing Fantasy – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2019年4月) この記事の主題はウィキペディアにおける音楽�...