Combinatorial fairness property in division of goods

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

A game played on binary matrices (22-dimension coin-turning game)

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

Modern advances in combinatorial game theory

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

Infinite positions in 3D chomp

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

Graph connectivity related game

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

Nash Equilibrium in general graphical game

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

Study of Hex on the Torus

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