CS SEMINAR

Axiomatic Analysis of Mechanisms for Online Fair Division

Speaker
Toby Walsh
Scientia Professor of Artificial Intelligence
University of New South Wales


02 Jun 2017 Friday, 11:00 AM to 12:30 PM

Video Conference Room, COM1-02-13

Abstract:

We consider fair division problems in which items arrive online and are allocated immediately to agents. In general, we may have no information about future items or, indeed, even if there are any more items. We propose several new mechanisms for this online setting. Many existing mechanisms for regular (offline) fair division can no longer be applied to the online setting as they assume the items being allocated are available at every time point. We then study axiomatic properties of these online mechanisms. We define an online version of strategy-proofness which reflects the fact that agents have less incentive to misreport when the future is uncertain and they must commit to actions now. We identify the class of online mechanisms which are strategy-proof, as well as the classes guaranteed to return allocations which are Pareto efficient, or envy free. We also identify mechanisms and settings in which combinations of Pareto efficiency, envy-freeness and strategy-proofness can be guaranteed. Finally, we report a simple but powerful impossibility result particular to this online setting. In offline fair division, mechanisms can return allocations that are always Pareto efficient and envy-free ex ante. In online fair division, we prove that this is impossible. Online fair division requires you to choose one or the other.


Biodata:

Toby Walsh is a leading researcher in Artificial Intelligence. He was recently named in the inaugural Knowledge Nation 100, the one hundred "rock stars" of Australia's digital revolution. He is Guest Professor at TU Berlin, Scientia Professor of Artificial Intelligence at UNSW and leads the Algorithmic Decision Theory group at Data61, Australia's Centre of Excellence for ICT Research. He has been elected a fellow of the Australian Academy of Science, and has won the prestigious Humboldt research award as well as the 2016 NSW Premier's Prize for Excellence in Engineering and ICT. He has previously held research positions in England, Scotland, France, Germany, Italy, Ireland and Sweden.

He regularly appears in the media talking about the impact of AI and robotics. In the last year, he has appeared in TV and the radio on the ABC, BBC, Channel 7, Channel 9, Channel 10, CCTV, DW, NPR, RT, SBS, and VOA, as well as on numerous local radio stations. He also writes frequently for print and online media. His work has appeared in the New Scientist, American Scientist, Le Scienze, Cosmos and The Best Writing in Mathematics (Princeton University Press). His twitter account has been voted one of the top ten to follow to keep abreast of developments in AI. He often gives talks at public and trade events like CeBIT, the World Knowledge Forum, TEDx, The Next Big Thing Summit, and PauseFest. He has played a key role at the UN and elsewhere on the campaign to ban lethal autonomous weapons (aka "killer robots").