Given n agents, and m items where vi(g)≥0 is the value of item g for agent i, does there always exist a partition A1,…,An of the m items into n sets s.t. for all i,j∈{1,…,n}: ∑g∈Aivi(g)≥(∑g∈Ajvi(g))−(min Where if A_j is empty, the min is taken as 0. In essence this is a fairness property where … Read more
Let r≥1 be a natural number. I am interested in the following (two-player, impartial, perfect-information) game: The state of the game is an n×n matrix with coefficients in F2 (we can imagine it as an n×n array of coins that can show either tails=0 or heads=1). A move consists of adding a matrix of rank … Read more
I’m going to take part in teaching a course in combinatorial game theory in the best of ONAG’s spirit. I was wondering if there are interesting post-ONAG results that are worth mentioning in (a later part) of this course. In particular, I’m interested in results about: classification of “cyclic” partisan games (the ones that are … Read more
In the second edition of the book “On Numbers and Games” by Conway there is a theorem 88 (p. 194) on comparison of sums of ↑x games. It contains a weird statement: … (If X is a sum of ↑x‘s, then) The game X+∗ is positive if and only if X+↑On is positive, where On … Read more
I’ve recently come back to investigating ordinal chomp. See A winning move for the first player in 3×3×ω Ordinal Chomp for a definition. I made a new discovery, that the position (ωω1ωω1200) is a losing position, first by a computer search, then by a proof showing that all possible moves from this position are winning … Read more
I was considering the following game on an undirected unweighted graph G=(V,E) (not necessarily simple). Two players, Police and Runaway, take moves in turn. Police can cut an arbitrary subset of edges in a single move and Runaway can move from a current vertex to an adjacent vertex (cutting an edge means that corresponding vertices … Read more
Any one has any ideas about how to compute the Nash Equilibrium in general graphical game? Especially, when the graph structure is not a tree. Answer You might look at this: Bhat, Navin AR, and Kevin Leyton-Brown. “Computing Nash equilibria of action-graph games.” In Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence, pp. … Read more
Hex is usually played on a parallelogram shaped board. What if you play it on a Torus? One thing I notice is that the idea of connecting opposite sides doesn’t make much sense anymore, since a torus has no sides. What you can do is assign the players target “loops”, where two loops are considered … Read more
I have read about Sprague Grundy Theorem and understand the proof of its correctness. However, I am unable to see the motivation behind the definitions. How do Sprague and Grundy know that they should define the Grundy number in that manner? Why is it the case that xoring the Grundy numbers together work? I don’t … Read more
Closed. This question is off-topic. It is not currently accepting answers. Want to improve this question? Update the question so it’s on-topic for MathOverflow. Closed 4 years ago. Improve this question Quoridor is a board game in which the objective is to move a piece across to the other side. A player can put up … Read more
