I have posted a list of MS thesis and undergraduate projects that I am interested in working on. If you are an undergraduate or graduate student interested in doing some research please check them out.
I am honored to have just received
NSF award 0829580 to continue my research into negotiation
networks. The total award is for $234K over the next 3 years. This
research is under the Theoretical Foundations program, and the
Scientific Foundations of the Internet's Next Generation (SING)
sub-topic.
We hope that our research will lay
the scientific foundations for the Internet's next generation of
protocols and deployment strategies. The project summary of the
proposal explains our goals:
We propose to develop automated negotiation protocols for autonomous agents in negotiation networks, which we define as a type of bargaining problem where every agent must negotiate with a fixed set of other agents in order to arrive at a unique deal. Negotiation networks are, in effect, a natural re-formulation of a winner determination in combinatorial auctions problem as a negotiation problem. They thereby distribute the costly winner determination computation among the agents and avoid the need for unnecessary exchange of currency or trusting of third parties.
Intellectual merit: Since the problem of negotiation networks combines features of characteristic form games and bargaining games from game theory, combinatorial auctions and distributed mechanism design from Economics, network exchange theory from Sociology, and distributed algorithm design from computer science, its solution should be a significant contribution to all these fields. While several parts of the proposed problem have been studied in the various disciplines, we will bring these disparate parts within one framework and provide solutions for this very important problem. Our approach is fresh in that we focus on algorithmic solutions for the dynamic, distributed problem of resource allocation among self-interested parties, in contrast with game theory and Economics' solutions which are typically steady-state axiomatic solutions. Success in this research is potentially transformative as it will provide the foundation for the engineering of protocols and efficient algorithms for distributed resource allocation, which is a pervasive problem in our ever-growing highly-interconnected society.
Broader impacts: The negotiation networks problem is not only significant from a research perspective, it also has some very immediate applications. One such application is the multiagent enactment of workflows for the growing SOAP and REST-based (Web Services) service Internet where complex tasks are dynamically and automatically bid for and allocated among arbitrarily large number of agents. Such systems would revolutionize just-in-time manufacturing and purchasing practices by automating not only the paperwork but also the allocation of resources and contract negotiation. Another near-term application lies in the development of incentive-compatible routing mechanism for the new Internet which would provide the proper incentives for companies to deploy more bandwidth and to make their existing bandwidth available to others without having to worry about freeloaders. Further down the road, negotiation networks could even eliminate the need for predefined workflows and lead to much more efficient and dynamic allocation of resources in our economy. These adaptive supply chains would be resilient to local failures and attacks as they dynamically re-negotiate deals in response to environmental changes. In fact, with slight modifications these distributed resource allocation algorithms could be used to coordinate first-responders in an emergency situation, to program distributed environmental sensor networks, and to instruct automated robotic swarms.
In the marriage problem we have an equal number of men and women who
we want to pair up (it is presumed they are all heterosexual). Each
one has an ordered list of their prefered mates. The goal is to find
the set of marriages such that no two people would rather get divorced
and marry each other. That is, not two prefer each other over their
assigned mates.
This problem can be solved with a simple algorithm where all the men
propose to the women. Then, each woman with more than one proposal
rejects all but her most preferred which she temporarily
accepts. The bachelors then repeat the process by asking their most
favorite woman who has not rejected them. The process continues until
all women have a partner. I have a NetLogo implementation
of the marriage problem that illustrates this process.
It is interesting to notice that while the women are the ones that get to
turn down the men, the men do overwhelmingly better than the women. I
mentioned this to my wife and she said that is why she proposed to
me. Of course, in the end it is always the women who propose to us.
Imagine that all students are assigned dorm rooms in some ad-hoc
way. After each one has a room, two students might find that they both
prefer the room the other one has, thus they could switch rooms and
both be happier. Similarly, three students (A,B, and C) might find
that A prefer's B's room, B prefers C's room, and C prefers A's
room. These three students might also trade rooms in a cycle. This can
go on for even larger cycles. But, how do we find these
cycles?
A very simple algorithm, proposed back in the seventies, is to have
each agent point to its most preferred choice. If the resulting graph
has any loops (it will) then all the agents in the loops exchange
rooms and drop out of the game. The remaining agents then point to
their most preferred room and we repeat the process until there are no
more agents left.
I have implemented a simple demonstration of this top
trading cycle algorithm using a simple distributed cycle detection
protocol. Its fun to watch!
As faculty members in Computer Science and Engineering we often
discuss the pros and cons of languages and which ones we should
teach. The Tiobe
software index shows us how the popularity of certain languages
ebbs and flows. I think it is clear that it does not really matter
which specific language you learn first or second, what matters is that
you learn how to think clearly. And that you learn how to learn new
languages.
As a demonstration, I thought I'd take a trip back memory lane and
list the languages I learned (and forgotten) while still in
school:
Walmart needs stuff moved from point A to B, for many A's
and Bs. Also, these deliveries have other possible requirements: one
might need a refigerated truck, one might be a night drop off, one
might be a rush order, etc. Similarly, trucking companies have complex
requirements about where and when they can deliver. Put these millions
of orders together and you have a complex resource allocation
problem. If you are willing to have everyone send their requirements
to a centralized auctioneer then, maybe, you can solve this
problem.
However, what it you don't want to trust, or can't afford to pay a
centralized auctioneer? We are studying automated incentive-compabile
negotiation protocols for distributed resource allocations. I know
this is a mouthfull but all it is saying is that we are developing
algorithms that automated agents can use to negotiate with each other
and solve these type of problems. Think of it as moving all buy/sell
transaction to the web (we are nearly there) and then using software
to decide who to buy what from and at what price. We can show that
this will lead to more efficient solutions, that is, everybody
wins.
Anyway, our latest paper detailing our efforts is
Distributed allocation and multiagent coordination problems can be solved through combinatorial auctions (CAs). However, most of the existing winner determination algorithms (WDAs) for CAs are centralized. The PAUSE auction is one of a few efforts to release the auctioneer from having to do all the work. The pausebid bidding algorithm generates myopically-optimal bids for agents in a PAUSE auction but its running time is exponential on the number of bids. We present new approximate bidding algorithms that not only run in linear time but also increase the utility of the bidders as result of small decrement in revenue.
Check it out, approximation mechanism let ut achieve 1000-fold speedups at only a small cost in utility.
I will be speaking tomorrow Thursday January 10 6:30pm at the Columbia Linux User's Group about NetLogo. It will be an informal introduction. I will try to show why it is a great language for both learning to program and for building simulations that can be used to engage students in active learning of other subjects: such as physics, chemistry, economics, sociology, etc. The meeting is open to all.
Today I gave a 1-hour talk to our freshmen on the history an future of the Internet. Obviously an impossible task but I did my best. I hope I conveyed to them the endless possibiblities that the Internet has opened up.
In preparation for this talk I have been asking our students: how much do you think the .com bubble affected the growth of the Internet? The general belief is overwhelmingly clear. Students believe the bubble had a large impact on the Internet growth. Of course, this is completely wrong. Check out my chart:
The bubble had absolutely no impact on the growth of the Internet which continues to grow exponentially, doubling every three years. The number of websites is doubling at least every two years. The implications of these facts are mindboggling! But, the general public, even our students, still seems to feel that software is done. Oh well, it just means more money for those of us who can program!
I will once again be offering the web applications class. This semester I will also go more in depth into ruby on rails (maybe a have a problem set on it) as well as developing web applications that use other sites' backends, such as building a facebook app or building an app. for the new OpenSocial protocol. Fun for all! I say.
One can visualize a combinatorial auction (with OR bids only) as a graph with two types of nodes: bids and items. Each bid node is labelled with the price of the bid and connected to all the items it is over. This is the visualization I have implemented in my combinatorial auction NetLogo model. It implements the branch-and-bounds algorithm on the branch-on-bids tree as found in my textbook.
A couple of years ago I built this simple NetLogo model that implements the iterated equiresistance algorithm in randomly generated exchange networks, as used by network exchange theory in Sociology. It now looks kinda dated and needs to be cleaned up but I thought I'd post it nonetheless. I'm using it in class as a demo.
I have posted a new netlogo model on pareto learning which implements the algorithms from this paper. This is a quick and dirty implementation for an in class demo. As nearly always happens when I do these, I found a slight problem in the paper. They specify two different ways in which the agents choose an action. Namely, first they say that the agents choose actions stochastically based on their expected utilities, then they say that they choose their best action and with probability epsilon choose a random action. After implementing both strategies it became clear that the second one is the one they actually used. Clearly, this was just a problem of the prose being a bit confusing (at least, for me).
It is also interesting to note how such a small change in the action choice method can have such large effects on the system's behavior. Because of this I have to say that the results from this model are not stable, thus they are not of deep significance.
I have released a new version of my Fundamentals of Multiagent Systems textbook. I incorporated suggestions from several other people who have used it in their classes as well as comments from students. I will be using this version in my multiagent systems class this fall.
I also hope to develop more NetLogo models to illustrate the various algorithms as well as add more algorithms to the book. I think it really could use more example problems along with their implemented solutions. Anyway, thanks to everyone who has contributed! Expect to see a new version by the beginning of next year.
Yes, I will be teaching multiagent systems (782) this Fall, once again. For the first time it will be an Apogee class which means there will be incriminating video of me saying things I shouldn't have. The class time is set for MW 2:00--3:15pm, but the room is to be determined. The class webpage is now up and you can now register for it.
The PhD hooding ceremony was this weekend. Hrishi, Hong and Karthik took pictures, some of which I have shamelessly borrowed and placed on my own flickr set for all to see.
The other Phd graduate this summer is Hong Jiang and her thesis is
To date, most research on multiagent systems has focused on rational utilitymaximizing agents. However, theories show that emotions have a strong effect on human~s physical states, motivations, beliefs, and desires. The details have not been explicated clearly so far. In artificial intelligence, emotions have begun to receive more attention, but mostly in human-robot/computer interaction. The research on applying emotions to agents~ decision-making is still very limited. Can agents be intelligent without emotions? We believe that, whether for humanlike or non-human-like agents, the effect of emotions on decision-making cannot be ignored, since agents with high emotional quotients (EQs) can be built to have better performance in complex dynamic environments than purely rational agents. This research focuses on the effects of emotions on decision-making. Taking into account the incompleteness of emotion theories and emotional differences among individuals, I describe EBDI, a common architecture for emotional agents, which specifies a separate emotion mechanism within an agent, instead of trying to model emotion mechanisms to reflect the reasoning process specifically, like most researchers have done. It reflects the practical reasoning process, and one can select and apply part of an emotion theory into the architecture as needed. Sample agents in Tileworld are presented and the results show that an EBDI agent can have better performance than traditional BDI agents. To apply EBDI in negotiation, a plug-in is designed, which modifies the OCC model, a standard model for emotion synthesis, to generate emotions. Considering the possibility of incorporating emotions into negotiation, I generate EWOD (EmotionalWorth- Oriented Domain), which requires numerical emotions. Thus, a mapping from 22 OCC emotions to 3-dimension numerical PAD emotions is given. Finally, I describe how PAD emotions affect the negotiation strategy and provide an evaluation which shows that it can be used to implement emotional agents that mimic human emotions during negotiation. Thus we can design high EQ agents for negotiation according to specific design purposes. Since negotiation is used widely in many different domains, this research, based on a general process of negotiation, can also be widely applied to other areas.
Congratulations are also in order for Hong. Her research is highly innovative, crossing boundaries between computer science, cognitive science, and Sociology. She has shown how simulated emotions can be incorporated into negotiating agents for the betterment of the whole agent society, as well as how agents can be made to behave like normal irrational humans. Check our her extensive list of papers. She will be joining the faculty at Benedict College.
I will be teaching 782: Introduction to Multiagent Systems this Fall. The class does not yet appear on the registrar's website but it will soon, I am told. So, if you want to learn a lot about applied game theory, applied Economics, distributed algorithms, and how to put these together to make next-generation multiagent systems then save a spot. We will be using my textbook Fundamentals of Multiagent Systems, a new version of which should appear by the time classes start.
We have two new PhD graduates this summer. One of them is Hrishikesh Goradia who has successfully defended his PhD thesis:
Distributed software systems are a norm in today~s computing environment. These systems typically comprise of many autonomous components that interact with each other and negotiate to accomplish joint tasks. Today, we can integrate potentially disparate components such that they act coherently by coordinating their actions via message exchanges. Once this integration issue is resolved, the next big challenge in computing is the automation of the negotiation process between the various system components. In this dissertation, we address this automated negotiation problem in environments where there is a conflict of interest among the system components. We present our negotiation model - a negotiation network - where a software system is a network of agents representing individual components in the system. We analyze the software system as a characteristic form game, one of many concepts in this dissertation borrowed from game theory. The agents in our model preserve the selfinterest of the components they represent (their owners), and make decisions that maximize the expected utilities of their owners. These agents accomplish joint tasks by forming coalitions. We show that the problem of computing the optimal solution, where the utilities of all agents are maximized, is hyper-exponential in complexity. We present an approximate algorithm for this hard problem, and evaluate it empirically. The simulation results show that our algorithm has many desirable properties - it is distributed, efficient, stable, scalable, and simple. Our algorithm produces the optimal (social welfare maximizing) solution for 96% of cases, generates maximal global revenue for 97% of cases, converges to 90% of the best found allocation after only 10 rounds of negotiation, and finds a core-stable solution for revenue distribution among the agents for cases with nonempty core. Finally, to ensure stability for all cases, we present a sliding-window algorithm that computes the nucleolus-stable solution under all situations.
Congratulations are in order for Hrishi! His thesis presents some highly innovative algorithms for automated negotiation, a topic that I expect will see many applications in the near future as semantic we technologies come of age and automated service orchestration becomes the norm in business processes. Go read it! I also want to point out that Hrishi's research contributions go far beyond his thesis; many of Hrishi's publications did not even make it into his thesis. He has accepted a position in the computer science department at Western Carolina University. We wish him well.
I have recently been doing some work on supply chains and, more generally, agent-based modeling in general. There is a certain art to making an agent-based model that is complex enough to capture the problem you are trying to model but still simple enough to remain manageable. Languages like NetLogo are excellent in that they eliminate nearly all extraneous code and one is left with something that almost (OK, maybe I'm being generous) looks like pseudo-code. Nearly all the code relates directly to the problem.
Still, its lots of fun.
On that note, I have posted a NetLogo model on supply chain survivability. The model itself is interesting in that I had to implement Dijistra's to calculate the minimal path between every pair of nodes. This was needed to later calculate the graph's clustering coefficient and the characteristic path length—two measures of a graph's connectivity, the smaller they are the closer everyone is to everyone else (thus, the shorter it takes to get items to the customers). Also note that the model generates small-world graphs (using preferential attachment) as well as random graphs. This model is the basis of some work we are doing. Anyone out there interested in this kind of stuff, let me know.
Below is a very quick video showing wht EBDI architecture of Hong Jiang in action. Unfortunately, it comes our fuzzy since google video reduces the resolution and it will probably not make much sense unless you read her paper on EBDI.
We had three papers accepted to this year's Autonomous Agents and Multiagent Systems Conference. The first one will get a full presentation and the other two will be presented as posters.
Benito builds on my previous effort to design a bidding algorithm for the PAUSE auction by providing a much faster bidding algorithm. The PAUSE auction is a combinatorial auction in which the bidders themselves solve the winner determination problem in order to win. They do so because that is the only way to win! Thus, the auction provides a simple way to distribute the computation among the agents. Our algorithms implement the myopically-optimal strategy for the agents in such an auction which is to calculate a new winning bidsest but only if in that bidset they would get more utility than they get from the currently winning bidset. In other words, if I don't get any more utility from a new bidset then I won't bother to calculate one (of course, some else might think differently.
Hrishikesh's attacks a problem similar to the one solved by the PAUSE auction but in this case it is the goods (items for sale) which negotiate to find the best allocation. This maps better to service-oriented architecture scenarios where various service providers are trying to sell their services but the buyers only want bundles. For example, you might only want a shipping service if you can also buy the book you want, both for less than $10. We present an algorithm based on Equal Excess theory which is an old solution concept to the negotiation problem (aka characteristic form game).
Hong is studying the problem of how to incorporate established emotional models from psychology into autonomous agents, namely BDI agents. This paper presents a first try at an architecture that will blend these two. The goal is to develop agents that behave like humans—with all the irrationality that that implies. We speculate that as agents start to take over more of our tasks, such as buying/bargaining with others, that users will be angry if their agents do not behave like they would, even if such a behaviors would be deemed irrational by a standard utility-maximizing model.
I have made my current, very preliminary, version of the textbook on multiagent systems available for anyone to download and comment upon. I am calling it Fundamentals of Multiagent Systems: with NetLogo Examples for now.
This semester's multiagent systems' class, while small, has led to the development of a lot of interesting and fun NetLogo models. I have posted a few of them in my MAS Netlogo page. The Sodoku puzzle using distributed breakout is especially fun.
Hrishi will be presenting a paper this weekend on his work on workflow automation using multiagent systems. The paper is:
I have posted a copy of my slides for this Friday's Seven Minute Madness (2:30pm in 300 Main Street, B213). They provide a pithy summary of what we are doing now.
I have a couple of programming projects which are a great way to get started learning about multiagent systems and would look great in your resume. Note that these are not paid positions, but you could get credit for them as a directed study if you want. Graduate students might also be interested as a way to get a flavor of what we do.