Thursday, January 28, 2016

RIP Marvin Minsky



Some sad news: Turning award winner and "father of AI" Marvin Minsky has passed away. NYT has an obituary piece on him

Sunday, January 17, 2016

Sunday, December 20, 2015

OpenAI: a non-profit artificial intelligence research company

Elon Musk, Peter Thiel and Reid Hoffman with the support of prominent tech companies such as Amazon and InfoSys are starting a 'non-profit artificial intelligence research company' called OpenAI.  The venture has been covered by NYT.


[Hat tip to Serge Gaspers]



Sunday, December 6, 2015

Illegal Organ Market in Pakistan

A new pieces on the illegal organ market in Pakistan: http://tribune.com.pk/story/1002596/spare-organs/

A case for starting a centralised clearing market where no money is involved?

Thursday, October 29, 2015

New Game Theory Centre: HSE International Laboratory for Game Theory and Decision-Making

Herve Moulin discusses the new HSE International Laboratory for Game Theory and Decision-Making that has been launched in St. Petersburg:

http://www.hse.ru/en/news/research/156770482.html

Friday, September 4, 2015

A new cake cutting protocol



Cake cutting is a playful metaphor for an abstract mathematical setting that models fair division and conflict resolution. The settings concerns agents having different valuations over subsets of a single divisible resource (the cake) which is represented by an interval between 0 and 1. It is assumed the cake is infinitely divisible and agents' valuation of the union of two disjoint cake pieces is simply the sum of the valuations of the pieces. The field of cake cutting has been explored by mathematicians, computer scientists, economists, and political scientists. At least two prominent books have been written on the subject. 


Books on cake cutting




The most central problem in cake cutting is to query the agents about their valuations of sub-intervals and use these answers to efficiently identify an envy-free allocation in which no agent prefers another agent's allocation. The solution to this problem has long been known for the case of two agents in the shape of the Divide and Choose protocol. In this protocol, the first agent is asked to  divide the cake into two equally preferred pieces and then asks the other agent to pick the piece he prefers. The first agent is not envious as long as he obediently and truthfully divides the cake into two equally preferred pieces. The second agent is certainly not envious because he chose one of the two pieces first. The protocol has been known since Biblical times (Book of Genesis (Chapter 13)):  Abraham divides the land of Canaan and Lot chooses first. The protocol also features in Greek mythology with Greek gods Prometheus and Zeus dividing meat using the same protocol.


abraham.jpg
Abraham and Lot divided land using the Divide and Choose protocol

zeus-statue-mount-olympus.jpg
Divide and Choose protocol is also mentioned in Greek mythology (Hesiod's Theogeny)









In recent times, the protocol has been enshrined in the Convention of the Law of the Sea.


united-nations-convention-on-the-law-of-the-sea-unclos-1-638.jpg
Divide and Choose protocol us used in the Convention of the Law of the Sea

In 1960’s, the Divide and Choose protocol was generalized to the case where three instead of two agents are dividing the cake. The protocol is known as the Selfridge-Conway protocol after its inventors John Selfridge and John Conway who discovered it independently. It is considered one of the most elegant algorithms in the field of fair division. In a recent biography of polymath Conway, it is reported that then when he discovered the protocol for three agents, "he sat down at his orange typewriter and pecked out a letter to Martin Gardner."


John Selfridge




John Conway

Since the Conway-Selfridge protocol, a protocol for four or more agents has eluded researchers. In 1995, political scientist Steven Brams and mathematician Alan Taylor made a breakthrough by proposing the first envy-free protocol for any number of agents. Although the protocol terminates in finite time, it had one drawback: it is not bounded even for four agents. In other words, the number of queries required to identify an envy-free allocation can be arbitrarily large for certain valuations functions. 

Steven Brams
Alan Taylor



Since the discovery of the Brams-Taylor protocol, it has been an open problem to devise a bounded envy-free cake-cutting protocol even for four agents. In a recent report coauthored with Simon Mackenzie, we have come up with a protocol that requires a bounded number of queries as well cuts of the cake. At a very high level, the protocol is based on two main ideas. One is the idea of dominance: an agent i dominates another agent j with respect to a partially allocated envy-free allocation, if i is not envious of j even if j gets the remaining unallocated cake. This idea of dominance is also known as irrevocable advantage in the literature. The other idea we use is that of permutation: agent's allocations are permuted or exchanged. This may case some some agents to be less happy than before but the permutation is done in a careful way so as to not cause envy. Such permutations are done to identify partial envy-free allocations with more structure than make it easier to identify complete envy-free allocation. 

You are welcome to read the report from arxiv.