NSF Award for Negotiation Networks Research

Fri, 08 Aug 2008 09:30:57 EST

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.

Marriage Problem

Wed, 30 Apr 2008 09:26:05 EST

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.

Trading Houses

Mon, 28 Apr 2008 12:39:33 EST

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!

My Programming Languages History

Fri, 25 Apr 2008 11:35:03 EST

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:

  1. BASIC - Freshman year in high school I took a summer class on Basic programming using the old Tandy PET (I also had the Atari 2600 basic programming cartridge, but it kinda sucked). Next year, my new Apple IIe had basic built in. I should also mention that back then it was common for high schools to teach Basic programming, Power Point and Excel did not yet exist.
  2. 6052 Assembly language - Of course, I wanted to write games and the only way to get any kind of animation in the Apple IIe was to progran in assembly.
  3. APL - I only worked with this extremely strange language for two weeks.
  4. Pascal - Somehow I got a hold of a copy of a Pascal compiler for the Apple IIe. I was surprised to learn that you could write programs without line numbers and GOTO/jmp statements.
  5. Scheme - I used it in my freshman year at college. Scheme is the simplest language I have seen. It is beautiful.
  6. CLU - In college we had to do our software projects using CLU. It is a pre-cursor to object-oriented languages.
  7. Emacs Lisp - I learned it for a summer job. This rss feed will be turned into HTML automatically by an Emacs Lisp function I wrote.
  8. C - Learned it for an OS class in graduate school.
  9. Lisp - thesis work.
  10. Tcl/tk - thesis work.
  11. C++ - thesis work.
  12. Java - I wanted to write some applets, for fun.
Those are just the major programming languages I encountered while still a student (pre 1998), I also learned bits and pieces of countless scripting languages (awk, sed, bash) or special purpose languages (latex, um-prs, sql). The point is, my experience is not uncommon. A good computer scientist or software engineer will learn at least one new language every year or so. After a while, one notices how they are all not that different but how each one teaches us something about the way we think, the way we solve problems. Writing software is about how we think, and how we translate these thoughts to meet the capabilities of the machine at our fingertips.

Thus, there is no need to get too hung up on which programming language you should learn first. If you choose software as a career, you will likely learn over 100 languages over your lifetime. I can only imagine what we will be using 10 years from today!

If you also have fun writing programs then maybe you would like to try to solve some of my programming questions.

Fast Bidding in a Distributed Combinatorial Auction

Sat, 09 Feb 2008 11:32:42 EST

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

Check it out, approximation mechanism let ut achieve 1000-fold speedups at only a small cost in utility.

A NetLogo Introduction

Wed, 09 Jan 2008 14:35:11 EST

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.

The Internet, Growth, and Students

Mon, 19 Nov 2007 20:56:43 EST

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:

Nasdaq vs. Number of Internet Hosts vs. Number of Websites

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!

Web Applications Class

Wed, 31 Oct 2007 11:12:32 EST

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.

Combinatorial Auction Model

Tue, 23 Oct 2007 08:04:01 EST

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.

Iterated Equiresistance Model

Wed, 17 Oct 2007 12:49:46 EST

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.

Pareto Learning Model

Wed, 10 Oct 2007 13:32:27 EST

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.

New Version of Textbook

Fri, 24 Aug 2007 13:28:37 EST

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.

Multiagent Class this Fall

Fri, 17 Aug 2007 13:22:46 EST

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.

PhD Graduation Pictures

Mon, 13 Aug 2007 10:51:46 EST

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.

Jiang Receives PhD

Thu, 02 Aug 2007 14:50:02 EST

The other Phd graduate this summer is Hong Jiang and her thesis is

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.

Multiagent Systems Class This Fall

Thu, 02 Aug 2007 09:02:07 EST

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.

Goradia Receives PhD

Thu, 02 Aug 2007 08:27:01 EST

We have two new PhD graduates this summer. One of them is Hrishikesh Goradia who has successfully defended his PhD thesis:

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.

Supply Chains, Terrorists Attacks, and Agent-Based Modeling

Tue, 27 Mar 2007 20:39:33 EST

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.

A Quick Video

Fri, 16 Feb 2007 12:49:03 EST

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.

Three New Papers for AAMAS

Fri, 02 Feb 2007 10:22:34 EST

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.

Textbook on Multiagent Systems

Fri, 22 Dec 2006 15:59:14 EST

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.

New NetLogo Models

Thu, 07 Dec 2006 09:01:35 EST

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.

B2B Workflows and Characteristc Form Games

Thu, 30 Nov 2006 15:45:28 EST

Hrishi will be presenting a paper this weekend on his work on workflow automation using multiagent systems. The paper is:

Research Summary Slides

Tue, 05 Sep 2006 15:03:16 EST

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.

Research Opportunities for Undergraduates or Graduates

Sat, 19 Aug 2006 09:22:41 EST

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.

  1. I am writing a multiagent systems' textbook which includes a lot of sample programs written in NetLogo. I already have a some programs but I need a bunch more. If you are interested in writing some, let me know. NetLogo is easy to learn and tons of fun to use. It is an agent-based modeling language that can be used in a surprinsingly large set of domain areas such as physics, economics, sociology, chemistry, biology, and many others.
  2. I am interested in developing an Ajax social bookmarking application for academic publications, like citeulike but with support for ontologies and automated recommendations.
  3. I am also interested in developing an Ajax system for distributed combinatorial auctions using some of the algorithms we have developed--available from my list of publications.

Pausebid Poster

Fri, 30 Jun 2006 10:05:21 EST

I have finished my pausebid poster for the workshop. I found out that it is not easy to explain how an algorithm works on a poster! It seems there is no substitute for staring and thinking about it, drawing all kinds of pictures to get a feel for how it works. Also, in related news, Benito is already working on a faster version of the algorithm which is coming along really well.

Summer 2006 Papers: AAAI

Thu, 11 May 2006 10:00:00 EST

Hong and I managed to get papers admitted to AAAI workshops. We will be presenting them at the conference in Boston. They are

Spring 2006 Papers

Sat, 15 Apr 2006 07:42:00 EST

We have a revised version of Murali's paper, who we are sorry to say left us for a high-paying job at Microsoft, and a new paper on emotional agents.
Also, we have new models in our MAS NetLogo models page and our MAS Reading Group has been very busy this Spring, drop by if you are interested.

Summer 2005 Papers

Tue, 06 Sep 2005 15:37:00 EST

The following papers were published by members of the MDL during the summer of 2005. All of the current member also got a chance to attend the Fourth Americas School on Agents and Multiagent Systems which, they tell me, was a lot of fun.

Dissertation on Workflow and Agents

Fri, 14 Jan 2005 10:08:00 EST

Paul Buhler has recently received his PhD. I am making his dissertaion available here. Paul is now a faculty member at the College of Charleston.

Workflow and Multiagent Paper

Thu, 20 May 2004 07:26:00 EST

We will be presenting the following paper this summer.

New Paper on Teaching (and Learning) Multiagent Systems

Thu, 13 May 2004 07:44:00 EST

I will be presenting the following paper this summer. The paper is a nice summary of our experiences in the last five years as well as my peculiar views on the future of our field.

Workflow Paper on IEEE Internet Computing

Fri, 16 Jan 2004 12:35:00 EST

We just had a paper published on using multiagent systems to implement distributed workflow.

Building Agents using Components

Mon, 01 Dec 2003 14:02:00 EST

Hrishikesh Goradia has finished his Master's thesis on building agents using behavior components. This thesis lead to the development of SoccerBeans. The thesis itself is:

Semantic Web Thesis Available

Tue, 18 Nov 2003 11:25:00 EST

Andy Finkbeiner has successfully defended his M.S. thesis. You can get a copy of it:

MAS Reading Group Now For Credit

Thu, 11 Sep 2003 08:49:00 EST

The MAS reading group can now (Fall 2003) be taken for one unit of pass/fail credit. To get the credit sign up for CSCE 797 Section 20. You will, of course, need to attend and lead discussion once. As always, you do not have to sign up to attend.

A Semantic Web Prototype

Mon, 21 Jul 2003 12:28:00 EST

Kapil Rajendra Dukle has successfully defended his MS thesis which implemented a prototype query-answering service for the semantic web. The system combines a scrapper, a DAML ontology, Jess, and some domain knowledge about football in order to answer questions about NFL players. You can read his thesis.

BPEL4WS meets Multiagent Systems

Thu, 10 Jul 2003 08:33:00 EST

Paul has published our first journal paper on our ongoing research into the merging of workflow technologies with multiagent systems.

Agents and Beans

Thu, 10 Jul 2003 08:31:00 EST

Next week, Hrishikesh will be presenting his paper (below) at the ABSE workshop in Melbourne, Australia. Drop by! ;-)

Adaptive Workflow

Fri, 20 Jun 2003 10:46:00 EST

Paul will be presenting a paper on adaptive workflow enactment using agents at the Web Services conference. The paper is:

AAMAS Conference

Fri, 16 May 2003 06:54:00 EST

Both Taraka and Sharad had their papers accepted as poster presentations for the Autonomous Agents and Multiagent Systems Conference, they are: I will be presenting a paper on the Trust workshop. The paper is We also have some other papers accepted elsewhere. I will be posting those once we have them in their final version.

New Publication On Agent Behaviors

Fri, 15 Nov 2002 15:47:00 EST

It is:

New Papers

Thu, 14 Nov 2002 23:15:00 EST

We have three new papers which have been submitted for review, they are: If you want a copy of any one of them just send me an email.