Project Details
Funding Scheme : General Research Fund
Project Number : 17202121
Project Title(English) : Distributed Protocols for Allocation and Selection Problems among Self-Serving Agents: Fairness, Security, Communication Efficiency 
Project Title(Chinese) : 自利性代理分配與選擇問題的分佈式協議:公平性、安全性與通訊效率 
Principal Investigator(English) : Dr Chan, Hubert Tsz Hong 
Principal Investigator(Chinese) : 陳子康 
Department : Department of Computer Science
Institution : The University of Hong Kong
Co - Investigator(s) :
Panel : Engineering
Subject Area : Computing Science & Information Technology
Exercise Year : 2021 / 22
Fund Approved : 838,393
Project Status : On-going
Completion Date : 14-6-2025
Abstract as per original application
This project will investigate distributed protocols that securely realize mechanisms for various allocation and selection problems among self-serving agents. In blockchain applications, an assignment protocol enables fair distribution of goods or chores among agents without any trusted central authority, and a selection protocol lets investors with conflicting interests decide which combination of crowdfunding projects to sponsor. In the literature, deterministic notions of fairness have been considered, but sometimes randomness is necessary. For instance, in the lottery problem, which is a special case of both assignment and selection problems, one prize is given to exactly one agent. The only reasonable mechanism is to select one agent uniformly at random as the winner. However, without a trusted authority, the agents themselves are responsible for generating the randomness in a distributed protocol. Unfortunately, standard cryptographic approaches such as secure multi-party computation require a majority of the agents to be honest, which is not a realistic assumption, because every agent might deviate from the protocol to increase its utility. Nevertheless, the lottery problem can be solved by the tournament tree protocol, which employs a commitment scheme based on standard assumptions such as one-way functions. Even though one cannot prove security in the strongest sense that the winner is unbiased, the tournament tree satisfies some game theoretic notions of security. For example, an honest agent following the protocol will be guaranteed at least the same probability of winning, even if all other agents conspire against it. Moreover, agents forming a coalition also cannot increase their combined chance of winning. Inspired by this framework, we will extend the game theoretic notions of security to protocols solving more general assignment and selection problems. However, unlike the lottery problem in which all agents have the same preference, it is known that the more complicated problem structure implies some impossibility results. For instance, even with a trusted authority, there is no mechanism for a general assignment problem that can achieve all the following properties simultaneously: truthfulness, Pareto optimality, equal treatment. Hence, even formulating the right security notions for protocols realizing the mechanisms for such problems is a challenging task. Finally, to have practical impacts, our protocols will also achieve communication efficiency. Since our preliminary work shows that the tournament tree protocol has optimal round complexity under some security requirement, we will explore approximate notions of security, and design protocols that have desirable tradeoffs between security and communication efficiency.
Research Outcome
Layman's Summary of
Completion Report:
Not yet submitted