About project

Research Experience for Undergraduates (REU) is a special program by DIMACS, Rutgers University, which helps students to start their own research. It covers projects from math and theoretical computer science to machine learning and bioinformatics.

Students from Charles University have participated this project since 1999. Group leader of this year is Gaurav Kucheriya . Other participants from Czech Republic are: Tomáš Čížek , Barbora Dohnalová , Guillermo Gamboa , Jiří Kalvoda , Kyrylo Karlov , Vova Kuznietsov , Josef Matějka , Jakub Petr and Ondřej Sladký .

Division game

This project is under supervision of and Bhargav Narayanan . I collaborate with Tomáš Čížek , Vova Kuznietsov and Ondřej Sladký . The main goal of the project is to find a winning strategy in a game called Division game.

Introduction

There are 2N gold coins sitting on a table, of different weights. Alice and Bob know all the weights, and they are going to split these coins up between themselves so they each get N coins. The way they will do so is as follows. Alice first picks a coin on the table, say x, Bob chooses who gets to keep x (him or Alice). Then Bob picks another coin y on the table, now Alice chooses who gets to keep y, and so on back and forth, until one player has N coins, at which point all the remaining coins go to the other player. Each player wants to maximise the sum of the weights of the coins that they get. It seems to be true, but we don’t yet know how to prove, that Bob is always better off than Alice in this game!

Progress of research

Week 1

We started thinking about our problem. At first, we solved some trivial examples. We played various games manually and we were thinking about general behavior of the problem.

Week 2

We defined rank and we tried to describe the problem using ordering. We made a lot of conjenctures, but most of them failed after we had finished a solver. After a day of the lost hope, we came up with a conjencture that wasn't instantly disprooved via solver. We also prooved a theorem about values of coins. Since that moment, we could thinking just about distinct games with positive integer values. We also tried to find upper bounds for games, but all estimations were both true but useless, either useful but false.

Week 3

We prooved our conjencture for a = 2. It was trivial, but we were too much focused on general proof and we didn't think about that problem trivially. We discovered two different branches research. Ondra Sladký tried prove a conjencture by two-step induction. This leads to proof of case where a = 3. I tried study a base structure of distinct games. This leads to a interesting problem in a lattice theory. However it seems that it isn't a way how to prove our conjecture.

Week 4

We continued in proof of case a = 3. We had to deal with a lot of mistakes in algebraic manipulations. We formulated and proved lemma about estimating games by given subset of coins. We finally proved treshold lemma and pumping lemma.

Week 5

Proof of case a = 3 is mostly finished. Unfortunately, it seems that we cannot generalize this technique. Bhargav sent us his notes to his proof of case a = 3. It looks like similar mess full of estimations. I started to think about lattice from week 3. I found some literature that can be helpful in our problem. General (n,n,C) game lattice (denoted like L(n, n)) is finite young lattice, so it has very nice properties. L(1,n) is just linear order. We can get better estimations using finding downsets in lattices.

Week 6

We made a great deal of progress in lattices. Using a structure we call a cut, we are able to do computer proving. We are using a lot of tools like linear programming and SAT solvers. We can make a proof for n = 5 with this method. We also read Bhargav's notes. He did similar things as we did, but he has a bit better bounds and a bit less messy proof of case a = 3. We also fixed something we called Alice's massacre, which says that most of Alice's strategies immidiately leads to that she will lose by induction. There are only 2 valid strategies left.

Week 7

We found out, that we cannot prove division game using massacre, so we came up with a conjecture which says treshold is changing only by one if game is played optimally. We extended massacre to cover changing a treshold, but we got stuck on that now Alice still has 128 valid strategies.

Week 8

We decided to no longer continue in massacre and we focused on special types of games. We found a proof that Bob will always win a game with two and three types coins. We were thinking again about games with doubled coins. Earlier, we had a disproof to our conjecture that Alice can always draw this game for 14 coins. However, I was was trying to understand what is going on in this case and I find out that there is probably problem with our solver. I guess caching isn't going well since there are too much coins. We didn't have to explore this more, because we ran out of time and we had to make our final presentation and return home right after that.

Photos

Photos from my journey across the US.

REU photos

Support

This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 823748.