On the afternoon of November 8th at 2:30 pm, Professor Gao Yang from the school invited Associate Professor Zhao Dengji from ShanghaiTech University to give a lecture titled "Incentives for Early Arrival in Cooperative Games".
Abstract:
We study cooperative games where players join sequentially, and the value generated by those who have joined at any point must be irrevocably divided among these players. We introduce two desiderata for the value division mechanism: that the players should have incentives to join as early as possible, and that the division should be considered fair. For the latter, we require that each player’s expected share in the mechanism should equal her Shapley value if the players’ arrival order is uniformly at random.
When the value generation function is submodular, allocating the marginal value to the player satisfies these properties. This is no longer true for more general functions. Our main technical contribution is a complete characterization of 0-1 value games for which desired mechanisms exist. We show that a natural mechanism, Rewarding First Critical Player (RFC), is complete, in that a 0-1 value function admits a mechanism with the properties above if and only if RFC satisfies them; we analytically characterize all such value functions. Moreover, we give an algorithm that decomposes, in an online fashion, any value function into 0-1 value functions, on each of which RFC can be run. In this way, we design an extension of RFC for general monotone games, and the properties are proved to be maintained.
Reported by:
Zhao Dengji joined the School of Information at ShanghaiTech University in 2017 as a tenure track assistant professor/doctoral supervisor/researcher, and was promoted to permanent associate professor in 2023. He is the Director of the Robotics Center at the School of Information Science and Technology, Executive Committee Member of the CCF Artificial Intelligence and Pattern Recognition Professional Committee and Computational Economics Professional Group, Secretary General of the CCF Multi Intelligent System Integration Group, Vice Chairman of CCF YOCSEF Shanghai, and Senior Member of CCF/IEEE. He obtained dual doctoral degrees in computer science from the University of Western Sydney in Australia and the University of Toulouse in France in 2012, dual master's degrees in computer science from Dresden University of Technology in Germany and Madrid Institute of Technology in Spain in 2009, and a first-class honours bachelor's degree in computer science from Macau University of Science and Technology in 2006. Before joining the University of Science and Technology, as a postdoctoral fellow, he successively studied under Professor Makoto Yokoo, the first AAAI Fellow in Asia, and Professor Nick Jennings, the first Royal Professor in the computer field in the UK and the current president of Loughborough University.
