Tutorials
Monday, May 17th, 8:30am - 5:30pm


Tutorials Schedule
8:30am - 9:00am Conference Registration

9:00am - 12:30pm
Break 10:30-11am

 Morning Tutorial I - Market Clearing Algorithms (Tuomas Sandholm)

Morning Tutorial II - E-Commerce Applications of Semantic Web Services (Benjamin Grosof)
Note: Attendees will choose either Tutorial I or Tutorial II
12:30pm-2:00pm Box LUNCH (provided to Tutorial registrants)

2:00pm - 5:30pm
Break 3:30-4:00pm

 Afternoon Tutorial - The Price of Anarchy (Christos Papadimitriou and Tim Roughgarden)

Morning Tutorial I

Market Clearing Algorithms

Tuomas Sandholm
Associate Professor
Computer Science Department
Carnegie Mellon University

Markets are important mechanisms for allocating goods, services, tasks, and resources among multiple agents, be they human or software. The market clearing problem is that of deciding how to allocate the items among the agents. The last four years have witnessed a leap of improvement in market clearing algorithms both for traditional market designs and entirely new market designs enabled by advanced clearing technology. This tutorial covers the computational implications of different market designs and presents algorithms for clearing markets optimally and approximately. Auctions (one seller, multiple buyers), reverse auctions (one buyer, multiple sellers), and exchanges (multiple buyers and multiple sellers) are covered. Both theoretical and experimental results are presented. Multi-item and multi-unit markets will be a key focus. Computational implications of different classes of side constraints will be presented. Bid types covered include price-quantity bids, different shapes of supply/demand curves, and package bids. Methods for selective incremental preference elicitation for combinatorial markets are presented, with which the market can be cleared optimally using only a small portion of the agents' preferences as input.

A basic understanding of algorithms, search, and NP-completeness is helpful. No background on markets is assumed.

Tuomas Sandholm is associate professor in the Computer Science Department at Carnegie Mellon University. He received the Ph.D. and M.S. degrees in computer science from the University of Massachusetts at Amherst in 1996 and 1994. He earned an M.S. (B.S. included) with distinction in Industrial Engineering and Management Science from the Helsinki University of Technology, Finland, in 1991. He has 13 years of experience building electronic marketplaces, and several of his systems have been fielded. He has published over 160 papers, and received the inaugural ACM Autonomous Agents Research Award, the NSF Career award, the Sloan Fellowship, and the IJCAI Computers and Thought award.



Morning Tutorial II

E-Commerce Applications of Semantic Web Services
Benjamin Grosof, MIT
http://ebusiness.mit.edu/bgrosof

The Internet is currently undergoing a radical change to a major next generation of Web technology based on XML and knowledge bases, which will enable much broader and deeper kinds of automatic interactions between enterprises/applications, especially in B2B. What is this new wave of technology? What are the implications for e-commerce? What is all the excitement in industry and research worlds really about -- what are "the Semantic Web", "Web Services", and their convergence "Semantic Web Services" (SWS)? What are the e-commerce application areas of SWS? This tutorial will provide an introduction, exploring techniques, applications, and challenges, and including emerging standards and strategy considerations. Techniques covered also include rules combined with ontologies and databases. Applications covered in detail include e-contracting, financial knowledge integration, and trust/security/privacy.


º Who Should Attend This Tutorial:

The major platform for e-commerce is the Web. This tutorial is about the e-commerce implications of the next major generation of the Web itself -- Semantic Web Services, which brings together the two major thrusts in Web standards and technology (Semantic Web and Web Services). There are a number of exciting research issues; most e-commerce researchers are not yet up to speed in this area, and this half-day tutorial will help them get there. The tutorial is suitable for most of the EC-04 audience; within that, especially those researching EC infrastructure or applications that rely heavily on the Web as a platform.

Prerequisites: none.

Helpful but not required:
º High-level Outline of Tutorial:

1. Intro
     a. Overview and get acquainted
     b. B2B & XML
2. Semantic Web Services: concepts, technologies, standards
     a. Semantic Web, Web Services, and their convergence
     b. Rules and RuleML
     c. Combining Rules with Ontologies
3. Application Scenarios in depth:
     a. E-Contracting including business policies
     b. Financial Knowledge Integration including ontology translations
     c. Authorization and Trust including privacy, multi-agent delegation
4. Windup and Discussion
     a. Prospective Early Adopter areas for SWS in EC


Benjamin Grosof is Douglas Drane Assistant Professor in Information Technology (IT) at MIT Sloan School of Management. His research is to create and study knowledge-based IT for e-commerce applications. He focuses especially on the technologies, business applications, and strategies for Semantic Web Services (SWS), the convergence of Web Services and Semantic Web. SWS is the next major generation of the Web, in which e-services and business communication become more knowledge-based and agent-based. The pioneer of inter-operable XML business rules, he co-leads the RuleML emerging industry standards effort. His research also includes several application areas for rule-based SWS in business process automation: e-contracting, which he has pioneered; financial information and reporting; and business policies, e.g, for trust and security. He is Principal Investigator and Rules co-lead in the DARPA Agent Markup Language (DAML) program, and a core participant in the newly formed Semantic Web Services Initiative that is creating emerging SWS standards. He interacts extensively with industry, including to do consulting in areas related to his research and standards activities.

He joined MIT Sloan in July 2000. Previously, he was a senior research scientist, in software, at IBM T.J. Watson Research Center (12 years there), where most recently he conceived and led IBM CommonRules and co-led its application piloting for rule-based XML agent contracting in EECOMS, a $29Million NIST industry consortium project on manufacturing supply chain management. His notable technical contributions also include fundamental advances in rule-based intelligent agents, conflict handling for rules, rule-based security authorization, and integration of rules with machine learning. He is author of over 45 refereed publications, two major industry software releases, and a patent. His background includes two years in software startups, PhD in Computer Science (specialty AI) from Stanford University, and a BA in Applied Mathematics from Harvard University.



Afternoon Tutorial

The Price of Anarchy
Christos Papadimitriou and Tim Roughgarden

The ``price of anarchy''---the worst-case ratio between the social objective function value of an equilibrium and that of a social optimum---is an increasingly popular measure of the inefficiency of equilibria in noncooperative games. In this tutorial, we will survey several mathematical techniques for bounding the price of anarchy, along with the applications to which they have been successfully applied.

Tim Roughgarden received his BS and MS degrees from Stanford University in 1997 and 1998, and his PhD in from Cornell University in 2002. He is currently an NSF Postdoctoral Fellow at UC Berkeley, and will join Stanford's computer science faculty in the fall of 2004. Dr. Roughgarden's research interests lie on the interface of combinatorial optimization and game theory. For his PhD work, he received SIGACT's Danny Lewin Best Student Paper Award, the Mathematical Programming Society's Tucker Prize, INFORM's Optimization Prize for Young Researchers, and an honorable mention for the ACM Doctoral Dissertation Award.

Christos H. Papadimitriou is C. Lester Hogan Professor of Computer Science at UC Berkeley. Before Berkeley he taught at Harvard, MIT, Athens Polytechnic, Stanford, and UCSD. He has written four textbooks and over 200 articles on algorithms, complexity, and their applications to optimization, databases, AI, economics, and the Internet. His novel Turing (a novel about computation), MIT Press, was published in the fall of 2003. He holds a PhD from Princeton, and honorary doctorates from ETH (Zurich) and the University of Macedonia (Thessaloniki). He is a member of the American Academy of Arts and Sciences and of the National Academy of Engineering, and a fellow of the ACM.