Chess Match Ends in a 3 3 Draw CS 416 Artificial Intelligence Lecture 8 Adversarial Search Assignment 1 Adversarial Search Problems involving Multiple agents Competitive environments Agents have conflicting goals Also called games Since the dawn of time Oldest game theory problem Oldest known written fair division problem T Hill GaTech A man dies owing 100 200 and 300 zuz to each of three claimants A B and C respectively Modern bankruptcy provides shares of the estate proportional to their indiviual claims no matter what size of the estate Written in the Talmud 2nd Century If the estate is only 100 zuz Each claimant receives equal shares If the estate is 200 zuz A receives 50 B and C receive 75 even though their claims are not equal Why A receives 1 6 B receives 2 6 C receives 3 6 Page 1 Unexplained until 1984 Game Theory Aumann and Maschler Israeli Mathematicians Studied by mathematicians economists finance In AI we limit games to Realistically when you die people could come out of the woodwork saying you owe them money Some could coalesce into deceptive groups How can we reduce the incentives rewards of forming such groups Minimize largest dissatisfaction among all possible coalitions Truly many similar solutions to this problem see http www math gatech edu hill publications cv dir madevice pdf deterministic turn taking two player zero sum perfect information Page 2
View Full Document
Unlocking...