We will kick off this semester's series with the first gathering at HKU. Date, time and venue are indicated below. We will have two speakers Xiaotie Deng and Ka-Wong Chong and the information about the talks is attached below.
Date Oct 9 (Friday) Time 3 pm - 4 pm Ka-Wong CHONG 4 pm - 4:30 pm Break 4:30 - 5:30 pm Xiaotie DENG Venue Lecture theatre P4 Chong Yuet Ming Physics Building University of Hong Kong
In reality, social and economic systems often involve in participating agents with different objectives. Mathematical models analyzing such systems often allow these agents to make decisions in their best interests as long as they abide by the rules and the decision making process of the system. Arguably, Nash Equilibrium is the most influential solution concept that requires that none can gain advantage by deviating from the solution on its own. Here all the agents are treated as equal. The concept of the Stackelberg solution, however, considers agents with asymmetrical power in the system. One agent, the leader, fixes its decision variables first and the rest make their decisions with the value of variables controlled by the leader fixed. For an optimization model with linear objective functions of agents subject to linear constraints, Jeroslow showed that the computational difficulty of the agents grows as their positions in the hierarchy go up. For the same model, Deng and Papadimitriou showed that, with two levels, the complexity of the leader remains the same if other agents reach a Nash equilibrium that is optimal for the leader. In practical sense, this may imply that reducing levels in a hierarchical structure may improve the efficiency of the organization. Even though the specific results on computational complexity depend very much on the model that is considered, there are evidence that the derived theory is quite robust.
On the parallel random access machine model (PRAM), it has been known for many years that minimum spanning trees (MST) can be found in O(logn) time on the CRCW PRAM model, the most powerful model in the PRAM family. For the exclusive write model (i.e., CREW and EREW PRAMs), O(log2 n) time algorithms for the MST problems were developed two decades ago. For a while, it was believed that exclusive write models cannot overcome the O(log2 n) time bound. In the last few years, the time bound has been improved significantly to O(log1.5 n) and then further to O(logn loglogn). Meanwhile, randomized O(logn) time algorithm on the EREW PRAM was also discovered. In this talk, a new approach to finding MST on PRAM will be presented. This approach gives a deterministic algorithm that runs in O(logn) time using n+m EREW PRAM, settling a long-standing open problem in the literature.