Xian Qiu — Improved Taxation Rate for Bin Packing Games
| Time: | Wednesday, March 16, 2011 |
| Location: | Room 101, Citadel |
A cooperative bin packing game is an N-person game, where the player set N consists of k bins of capacity 1 each and n items of sizes a1,...,an. The value of a coalition of players is defined to be the maximum total size of items in the coalition that can be packed into the bins of the coalition. We present an alternative proof to the non-emptiness of 1/3-core for all bin packing games and show how to improve this bound 1/3 (slightly). We conjecture that the true best possible value is 1/7.