In the Internet era, ecommerce has grown and flourished. Auctions, as special markets with restrict rules, play an important role in ecommerce. How to design auction mechanisms with desired economic properties, for example, those that are efficient both allocatively and computationally, is a major issue in ecommerce research. Traditionally auctions are viewed as games and analytic methods from game theory have been successfully applied to some kinds of auctions, like Vickrey auctions. The high complexity of the dynamics of some other auction types, especially double-sided auctions, however makes it difficult to go further in this direction. I, with my colleague in the Agents Lab, CUNY, seek experimental approaches to the problem of auction mechanism design and aim to solve the problem in an automated way.
More specifically, we run agent-supported simulations to analyze markets, and particularly the competition between markets and the dynamics of traders moving between them. We designed the TAC Market Design Competition (CAT) in collaboration with Universities of Liverpool and Southampton and I led the effort of building JCAT, the open-source platform for running CAT games. CAT games model the scenario that is similar to the competition between stock exchanges and provide a solid testbed for research. Indeed, we introduced a grey-box approach to automated mechanism design in the domain of CAT games that combines reinforcement learning and evolutionary computation. We were able to acquire auction mechanisms that can beat entries into the 2007 and 2008 CAT Competitions.
Distributed computing, especially agent-based computing, becomes more and more pervasive as the Internet penetrates to penetrate into every aspect of our everyday lives. It is so because it is often natural and convenient to view a computational system as a collection of multiple interacting agents, and this paradigm grasps the very nature of what such a system tries to model in the real world. However, the agent-based paradigm has its own difficulties, in particular those in solving the following two problems:
A major tool for multi-agent system designers has been game theory (GT). GT provides a framework for studying strategic, interacting individuals and solution concepts---usually various equilibria---with the assumption of the rationality of individuals. GT thus helps to compare the outcomes of an interaction mechanism to the optimal ones in theory, but it does not give a dynamic model that explains how to reach optimal outcomes, nor presents much guidance on how to maximize global outcomes when some agents in the system are not as rational as presumed.
Auction mechanisms are an ideal candidate to provide this missing model. The effectiveness of auction mechanisms in the real world and the similarity between an auction and a multi-agent system---both involving multiple self-interested individuals and concerning certain global outcomes---have led to various market-based approaches to multi-agent coordination and resource allocation problems in cluster and grid computing environments. Collaborating with Peking University, and with support from the Microsoft SQL Server China R&D Center, I proposed a market-based approach to query load balancing in very large database systems in cloud computing environments. My work on automated mechanism design is expected to be helpful in solving problems in this practical domain.
Petri Nets have been a popular technique for describing concurrent and parallel systems since they were introduced by C. A. Petri in 1962. They can be used to intuitively describe the dynamic properties of concurrent systems and the restriction for the allocation of system resources. Petri Nets also feature a graphical interface that is easy to represent and understand. Classical Petri Nets, however, are so simple that even the model of a small system needs a considerable number of states and transitions, resulting in a so-called 'state explosion'. People have been working to improve the representation capabilities of Petri Nets and have already introduced a variety of high-level Petri Nets and simplification methods, but the results are far from inspiring.
With the popularization of Object Oriented (OO) theory over the 1980s, the Petri Net community appealed to OO concepts in that object orientation features abstraction, encapsulation, and inheritance, which may help to build layered Petri Net models instead of 'flat' ones.
Based on OPNets by Yang Kyu Lee and Sung Joo Park, we designed an object-oriented Petri Net language, or OOPN. The supporting tool of OOPN, OOPN-IDE, had been developed to model, simulate, and implement concurrent software systems in an integrated environment. OOPN-IDE is Java-based and includes around 40,000 lines of source code. What makes it different from other Petri Net tools are: 1) collaborative concurrent development support, and 2) Petri Net structure as the framework embedded in the automatically generated application source code. Since OOPN models may be seamlessly embedded in the target system, simulation is actually equivalent to debugging or execution of the real system, which can help to reduce the gap between system specification and real application. Below is a screen snapshot of OOPN-IDE:
Until now, OOPN and OOPN-IDE have been applied to the development of real-time operating systems, agent systems, grid computations, and cluster computations.
All the above is boring? Take a look at the nice classical Petri Net model for the dinning philosopher problem below: