Makerere University Faculty of Computing and I.T.

First Makerere Workshop on Social Systems and Computation

Summary

Top researchers from Northwestern University (Chicago), University of British Columbia (Vancouver) and Makerere (Kampala) are teaming up to offer a workshop on cutting-edge methods for computational modeling of social systems, algorithm design, and machine learning. The sessions will take place between 3rd and 10th December 2010, and there is no cost for attendance; however, registration is mandatory. Attendance is limited to academic staff working at an East African university; students doing research in related areas may also be given special permission to attend if space permits. Participants will have the opportunity to publish papers in official, reviewed workshop proceedings at a later date. A certificate of completion will be provided to participants who attend at least two thirds of workshop sessions.

Overview

Traditionally, computer science has viewed data as coming from either an adversarial source or from nature itself, giving rise to worst-case and average-case design and analysis of optimization algorithms.  In recent years with the advent of modern technologies like the Internet, it has become increasingly apparent that neither of these assumptions reflects reality.  Data is neither adversarial nor average, but rather inputs to algorithms are constructed by a diverse set of self-interested agents in an economy, all aiming to maximize their own happiness.  Thus the raw data is often not available to an algorithm designer, but must be solicited from the agents--that is, the designer faces an economic constraint.  The primary goal of this workshop is to explore the implications of this observation.  We will study the performance of algorithms in the presence of utility-maximizing agents and ask whether alternate designs might create incentives for agents to act more optimally.  Simultaneously, we will look at other more traditional optimization problems such as approximation and learning and techniques to solve them, pointing out that these may often be leveraged to solve issues in the economic setting. 

Related Research Areas  Computer Science Theory; Artificial Intelligence; Economics; Business

Format and registration

The workshop will consist of seven 3-hour lectures, plus meal/breakout sessions for informal research discussion. Spaces are strictly limited, and attendees must pre-register. We will aim to select topics and session times that are best for our participants. To register, and to indicate your preferences for topics and dates, please complete the survey at http://www.surveymonkey.com/s/WWGMKZG.  

Schedule

The workshop will consist of the following sessions. All sessions will take place at the Faculty of Computing and IT, Makerere University.

Friday, Dec 3, 10 AM - 1 PM
Mobile Computing Lab, Block B, FCIT
Bayesian Methods and Probabilistic Inference
Bayesian methods are commonly used for recognising patterns and making predictions in the fields of medicine, economics, finance and engineering, powering all manner of applications from fingerprint recognition to spam filters to robotic self-driving cars. This session will show how principles of probability can be used when making inferences from large datasets, covering issues such as prior knowledge and hyperpriors, the construction of "belief networks", and nonparametric methods such as Gaussian processes. Several applications will be demonstrated.
Monday, Dec 6, 10 AM - 1 PM
E-learning Lab, Level 2, Block A, FCIT
Introduction to Game Theory
Game theory is the mathematical study of interaction among independent, self-interested agents. It has been applied to disciplines as diverse as economics, political science, biology, psychology, linguistics and computer science. This tutorial will introduce what has become the dominant branch of game theory, called noncooperative game theory, and will specifically describe normal-form games, a canonical representation in this discipline. The tutorial will be motivated by the question: "In a strategic interaction, what joint outcomes make sense?"
Monday, Dec 6, 2.30 PM - 5.30 PM
E-learning Lab, Level 2, Block A, FCIT
Introduction to Mechanism Design and Auctions
How can we design socially desirable protocols for making decisions in settings where participants cannot be relied upon to behave honestly or cooperatively? This question is answered by the field of Mechanism Design. The tutorial will describe the core principles behind this theory, and explain the famous "Vickrey-Clarke-Groves" mechanism, an ingenious technique for selecting globally-utility-maximizing outcomes even among selfish agents. It will also describe Auction Theory, the most famous application of mechanism design. Auctions are mechanisms that decide who should receive a scarce resource, and that impose payments upon some or all participants, based on agents' "bids"; they form the basis of markets all around the world.
Tuesday, Dec 7, 10 AM - 1 PM
E-learning Lab, Level 2, Block A, FCIT
Social Networks
Social networks describe the structure of interpersonal relationships and have many alarmingly predictable properties.  While most people have just a few friends, most social networks have at least a few very popular people.  Furthermore, most people are closely linked to every other person so that a message (or an idea or a disease) can spread rapidly throughout the network.  Finally, social networks tend to be fairly clustered --.e., if two people share a common friend it is quite likely that they are also friends.  This module will discuss the typical structures of social networks, models that explain these structures, and the impact of these structures on activities in the social network such as message routing or the adoption of new technologies.
Wednesday, Dec 8, 10 AM - 1 PM
E-learning Lab, Level 2, Block A, FCIT
Causal Structure from Data
Until a few decades ago, it was thought to be impossible to learn causes and effects from purely observational data without doing experiments. Sometimes, however, it is impossible to do experiments (e.g. in some branches of genetics), or experiments may be costly or unethical (e.g. situations in climate change or medicine), so the emergence of computational methods for distinguishing causes, effects and confounding variables is likely to have wide implications. Some principles are now understood for learning the causal structure between different variables, and this session will explain the most successful current approaches, their possibilities and their limitations.
Thursday, Dec 9, 10 AM - 1 PM
Venue to be announced
Internet Search and Monetization
The internet is one of the most fundamental and important applications of computer science.  Central to its existence are search engines which enable us to find content on the web.  This module focuses on the algorithms like PageRank that these search engines use to help us find webpages. It also studies how these engines make money through advertising. 
Friday, Dec 10, 10 AM - 1 PM
E-learning Lab, Level 2, Block A, FCIT
Approximation Algorithms
In the field of algorithms, many tasks turn out to be computationally difficult.  That is, the time to complete the task is fundamentally large compared to the size of the problem.  For example, consider the problem of finding the optimal way to visit 10 cities, visiting each exactly once.  To minimize travel time, one could test all possible travel schedules, but for 10 cities there are already 3.5M of them!  Unfortunately, there is not a significantly quicker way to find the optimal solution.  However, one can find an approximately optimal solution quickly.  That is, with just a few things to check, one can design a schedule that takes at most 50% more time than the optimal one.  In this module we showcase a few general techniques for computing approximate solutions to hard problems, including the use of randomization and linear programming.   

Speaker Bios

Nicole Immorlica  is an assistant professor in the Economics Group of Northwestern University's EECS department in Chicago, IL, USA.  She joined Northwestern in Fall 2008 after postdoctoral positions at Microsoft Research in Seattle, Washington, USA and Centruum voor Wiskunde en Informatica (CWI) in Amsterdam, The Netherlands.  She received her Ph.D. from MIT in Boston, MA, USA, in 2005 under the joint supervision of Erik Demaine and David Karger.  Her main research area is algorithmic game theory where she investigates economic and social implications of modern technologies including social networks, advertising auctions, and online auction design.

Kevin Leyton-Brown is an associate professor in computer science at the University of British Columbia, Vancouver, Canada.  He received a B.Sc. from McMaster University (1998), and an M.Sc. and PhD from Stanford University (2001; 2003). Much of his work is at the intersection of computer science and microeconomics, addressing computational problems in economic contexts and incentive issues in multiagent systems. He also studies the application of machine learning to the automated design and analysis of algorithms for solving hard computational problems. 

John Quinn is a Senior Lecturer in Computer Science at Makerere University. He received a BA in Computer Science from the University of Cambridge (2000) and a PhD from the University of Edinburgh (2007). He coordinates the Machine Learning Group at Makerere, and his research interests are in pattern recognition and computer vision, particularly applied to developing world problems.




Back to group homepage