AGT/E Grad Schools

I was asked which CS departments are recommended for getting your graduate degree in Algorithmic Game Theory (/Economics).  This sounds like an excellent question to leave for commenters on my blog, but let me start with some of the obvious answers:

The three top CS departments are all excellent for AGT as well: Berkeley has the patriarch of the field, as well as an AGT-active networking group (Scott Shenker), and a whole related school of Information.  MIT has Costis and, from the crypto side, Silvio (who in recent years has been forwarding a hostile takeover of mechanism design by crypto), as well as a network GT  group, and the fantastic close-by microsoft reserach center.  Stanford has Tim and, on the AI-ish side, Yoav, as well as strong AGT-friendly economists (Paul Milgrom, Ilya Segal), and close proximity to Silicon Valley  and in particular to the excellent AGT reserach groups of Microsoft and of Google.

Other noteworthy places include:

1. The very strong group in Cornell (Including Eva Tardos, Jon and Bobby Kleinberg, Joe Halpern and, from the crypto side, Rafael Pass).
2. The EEconomiCS group in Northwestern (Lance Fortnow, Nicole Immorlica, Jason Hartline) with strong support from the business school (including Ehud Kalai, the unofficial AGT godfather within GT, and Rakesh Vohra, a major communication hub between Econ/GT, OR, and TCS).
3. Liverpool has a strong Economics and Computation group.
4. Israel has unusual presence in AGT, including Tel-Aviv, the Technion, and my own CS department at the Hebrew University (Jeff Rosenschein, Daniel Lehmann) with a strong supporting center for the study of rationality (including AGT reserachers Liad Blumrosen and Michal Feldman as well as many AGT-close economists, game-theorists, and mathematicians like Sergiou Hart, Gil Kalai, and Abraham Neyman).

So let me stop with this incomplete list, and ask readers for more suggestions.

Advertisement

Read Full Post »

Wikipedia course assignments

I have been teaching the course Topics on the  border of CS and economics with Michal Feldman in the fall semester.   One of the course assignments was to write a Wikipedia entry on a topic of the students’ choice that is related to the course.  This was the first time that any of us tried this, so we left this assignment pretty open and only made sure that the class’s choice was injective and more or less in range.  We were not aware at the time that there are suggested ways on how to organize such a thing, e.g. this entry in English or this one in Hebrew (we allowed both English and Hebrew entries, and most students chose the latter.)

We saw various reasons why this assignment is a good idea: First, we figured that having the “world” reading your work is an added incentive to write well. (This is especially so given the fact that, due to the terrible budget cuts in Israeli universities in the last few years, we had no TA.) Second, we wanted to ensure that the effort that students put into their assignment is not wasted but rather put to a good use.  Third, there was the idea of doing a public service.  Fourth, there was a somewhat vague notion of immersion in the main motivator of the course: what goes on the Internet.

As the course has ended, we compiled a list of the entries written for the course.  I would say that the experiment has ended with mixed results: the quality of entries varies.  Some of them are really good, others are OK — a reasonable start and hopefully will be improved, but some are quite badly written (in various senses: format, writing style, and even technical content.) It seems that adding incentives for what is usually done by volunteering (i.e. giving course credit for writing an entry that is usually done voluntarily) introduces problems.  While normally Wikipedia writers only do so when they want to and are able to do a god job, here we incentivized people to do so even if they could not do a good job or did not want to put enough effort into doing so.  (This is somewhat similar to the observation that paying for blood donation reduces the willingness to do so.)  I can’t really tell if the students that did a really bad job are incapable of doing significantly better or just didn’t put enough effort into it.

Michal and me now feel somewhat responsible for doing some harm to the (mostly Hebrew language) Wikipedia.  We are not really able to go over all the entries ourselves and “fix” them (again, no TA, and many dozens of entries.) We are making small changes here and there as well as adding a few comments in discussion pages, but this is small in magnitude, and doesn’t help much for the worst entries, so we have decided to hire a TA/RA for a while to “clean after this course”.

One of the interesting new entries was the Algorithmic Game Theory entry in the English Wikipedia.  It turns out that there was no such entry previously, despite a call to write one by the “committee to improve Wikipedia’s arguably-somewhat-sketchy coverage of theoretical computer science” over a year ago, which mentioned AGT together with a list of other desired entries, many of which still remain unwritten.   (Looking at the history page of AGT, it seems that an entry for AGT was previously written, but the entry was not appropriate and focused on Algorithmic Mechanism Design and so was “moved” there about two years ago.)

My (preliminary) conclusion: I would do it again, but next time, only with a smaller class size and with a devoted TA.

Read Full Post »

AGT summer school in Shanghai

A summer school on Algorithmic Game Theory will take place on July 4–15, 2010 at Fudan University in Shanghai.  Co-located with Expo 2010 with its expected 70M visitors.

Read Full Post »

Grading a game theory course

A few days ago I re-heard the story of how the game-theory course in the Technion was graded. I’ve heard versions where the professor was Ran Smorodinsky and other versions with Dov Monderer, but I haven’t checked out what “really” happened. (Anyone with the real facts is welcome to send in a comment…) Here is the story.

In the last day of class, the Professor gathered all the students and made the following offer: He wants to have an average grade of X (say 80) in the course with a standard deviation of Y (say 15). If all students agree upon everybody’s grades in a way that conforms to these constraints, then this is how they will be graded, and the exam will be canceled. Otherwise, the scheduled exam will take place as usual and will determine the grades. The professor then left the class and let the students try to reach a joint decision.

Some versions of the story continue thus: the best student in class immediately got up; said that she will not accept anything less than 100; and immediately left the room too.

Read Full Post »

The Computational Complexity of Pure Nash

Perhaps the first complexity question regarding equilibria that a Computer Scientist can ask is how difficult — computationally — is it to find a pure Nash equilibrium of a given game, or report that none exists.

In the simple setting, the -player game is given by it’s utility functions, each of them given as a table of size of numbers (where we assume for simplicity that each player has a strategy space of size .)  By going over all possible possible strategy profiles and checking for each of them whether some player can gain by deviating we get an efficient algorithm.  (Easy exercise: The running time of this algorithm is — improve it to linear in the input size, i.e to .)

This, however, is not the end of the story.  In many cases, we really have a “very large” game, and we would like to find an equilibrium in time which is significantly sub-linear in the size of the game’s utility tables.   How can we even talk about getting sub-linear time algorithms?  We need to read the input — don’t we?  There are two standard ways in Computer Science to talk about this question.  The concrete complexity approach assumes that the utility tables are given by some of “black box” which can answer queries of a certain type (e.g. given a strategy profile , can return the value of as a single atomic operation).  The set of queries that the black box supports will of course determine what can be done efficiently in this model.  The Turing-Machine complexity approach will consider concise representations of the utility functions, whose length is significantly less than the full size of the tables, and expect the algorithm to find an answer in time that is polynomial in the size of the concise input.  This of course gives different algorithmic problems for different concise representations.

In the rest of this post I will present the basic study of the complexity of finding a pure Nash equilibrium in these models (for general games as well as some special cases.)   These basics are often overlooked as they are shadowed by the meaty PLS-completeness results and PPAD-completeness results, but I prefer  talking about the basics even though these contains no “significant” proofs.

Black Box Complexity

In the variant here we assume that we get “black boxes”, one for each player, that can answer utility queries: given a strategy profile return .  Another variant we can consider would also allow asking best-reply queries: given a strategy profile of the others , return the best-reply of player .  (Where we would need to specify how ties are handled.)  We will concentrate on cases where is not too large and we allow the running time to be polynomial in , even though in some cases we could think about running in time which is logarithmic in — the length needed to represent a strategy of a player. In these situations, as a best-reply query can easily be simulated by utility queries to all possible values of , adding a best-reply query doesn’t significantly change the power of the model.  (One can imagine even more queries to ask from the black-box, and the ultimate in this direction would be t allow asking any question about , but only about a single for each query.  This model turns out to be equivalent to the communication complexity model.)

We will consider not only general games, but also two sub-classes of games that are known to always have a pure-Nash equilibrium: Dominance-solvable games (those where iterated elimination of strictly dominated strategies leaves a single strategy profile), and Potential Games.  For motivation it is best to start with a “good” algorithm, that finds a pure Nash equilibrium in all Dominance-solvable games:

1. Let be an arbitrary initial strategy profile
2. Repeat times
   1. For all players do
      1. best reply of to .

The total running time of this algorithm is operations (which include utility queries to the black box, where each best-reply calculation is implemented via utility queries.)  The interesting fact is that this algorithm always ends with a pure Nash equilibrium — as long as the game is dominance-solvable.  (Idea of easy proof: a strategy that was eliminated in the ‘th step of the strategy elimination process can never be used after iterations of the outer loop of this algorithm.)  What is remarkable about this running time is that it is exponentially smaller than the “input size”, as each black box contains numbers in it.

Can such an efficient algorithm — whose running time is polynomial in and — be found for other games?  For potential games?  Maybe even this algorithm — just repeated best-replying — will do the trick?  It is not difficult to see for general games repeated-best replying may loop infinitely even if some pure Nash equilibrium exists.  For potential games, almost by definition, every sequence of best-replies will indeed terminate with a pure Nash equilibrium.  (In fact, ordinal potential games are exactly those games where every sequence of better-replies terminates.)  But how long can this take?  Unfortunately, exponential time.  (Exercise: find an exact potential game with players each having two strategies, where starting from some strategy profile , every sequence of best-replies requires exponential time to reach a Nash equilibrium.)

So, can there be another efficient algorithm for general games or for potential games?  A simple observation is that in a potential game where the potential function has polynomial-sized range, any best-reply sequence will terminate withing this polynomial number of steps.  Can this be generalized even further?  One can formally prove a negative answer — a lower bound.  One of the simplest formalisms for this is using an “adversary argument”: instead of first choosing a game and then letting the algorithm access the utility functions via the black boxes, the adversary will make-up the game as he goes along.  Each time the hypothetical algorithm makes a query to the black-box, the adversary will answer it in some way that he thinks will be least helpful to the algorithm — making sure that for as long as possible the algorithm does not have sufficient information as to provide an answer.  The idea about this technique is that if the adversary can pull this off — i.e. keep answering in a consistent way such that a single answer is still not guaranteed — then there must be some fixed game for which the hypothetical algorithm was not able to produce a correct answer in time — exactly the game that is still consistent with the adversary’s answers.

For the case of general games it is easy to provide such an adversary.  Let the adversary fix in his mind some game without any pure Nash equilibrium. (For concreteness, say, 2 players playing matching pennies, and another players not caring at all, but still having two strategies each.  This gives a game with strategy profiles, whose structure is just many multiple copies of the 2×2 game of matching pennies.)  Whenever the algorithm makes a query, the adversary will just answer with the value of the fixed game.  Clearly the algorithm can never find a pure Nash equilibrium since none exists.  The point is that the algorithm cannot decide that no Nash equilibrium exists before making at least queries.  If even a single strategy profile was not queried, then it could be that at that strategy profile all players get high utility (where “high” is anything higher than any value in the original game) and thus it is a Nash equilibrium.

For the case of potential games the adversary must be somewhat more clever.  We will consider an player game where each player has two strategies and thus the space of strategy profiles is the -dimensional Boolean hypercube. Our adversary will produce an exact potential game, as will be evident by the fact that all players will have exactly the same utility at each strategy profile.  In such cases a pure Nash equilibrium is simply a local maximum of this utility function.  Let us start with the basic idea, that does not quite do the job: At the ‘th query of the algorithm, , the adversary will answer .  The idea is that the algorithm cannot find any Nash equilibrium this way since a strategy profile can be declared to be such only if all of its neighbors (in the Boolean hypercube — corresponding to the possible deviations by a single player) were already queried to have a lower utility than the vertex itself.  Since the adversary keeps answering with increasing values, the only way that this can happen is if the algorithm first “closes up” a strategy profile (vertex in the hypercube) by first asking all of its neighbors and only then the enclosed vertex.  So to fix it, we’ll improve the adversary: when asked a query , the adversary will look at the set of un-accessed vertices of the hypercube and see whether any vertices are left disconnected from the “rest of the hypercube”.  Specifically, let us call a vertex “compromised” if its connected component (after removing all queries from the hypercube) has size strictly less than (half the hypercube).  What our adversary will do is go over all newly compromised vertices, fixing their values in an order that increases from the farthest away from to itself.  This way a vertex is never assigned a value after all of its neighbors have, and thus no vertex can be guaranteed to be a Nash equilibrium until all vertices of the hypercube are either queried or compromised.  The only question is how many queries does this take?  Let be the set of queries and be the set of all vertices compromised by , how large does have to be for the union to be at least half of the whole hypercube?  Combinatorially, must contain all of ‘s neighbors in the hypercube.  This leads us to ask for smallest possible size of the set of neighbors of a set of vertices in the hypercube — known as the isoperimetric problem for the Boolean hypercube.  This question is completely solved (see chapter 16 of Bollobas), and in particular it is known that for any subset of at most half of the hypercube, the size of the set of its neighbors is at least fraction of original set’s  size.  This means that , which implies that — an exponential lower bound for the worst case running time of any algorithm that finds a pure Nash equilibrium for all potential games.  An immediate corollary is that there may be best-reply paths of this exponential length.

Turing-Machine complexity

We now move to the alternative way of accessing a “large” game, that of representing it concisely.  Clearly not every game has such a concise representation, but can we at least find and equilibrium efficiently for those that do?  Also, different representations may require different complexities — which concise representation should we consider?  The first one we will look at is the general representation of a black box by the code of a procedure, equivalently by a description of Turing machine. However,  we only want to consider TMs that run efficiently, e.g. in polynomial time, or alternatively count the running time of the TM as part of the input size.  The usual formalism for giving such a TM as input, is the equivalent requirement of a Boolean circuit that computes the black-box queries, and this will be our first concise representation:

Input: boolean circuits, each computing a function , where the input of each circuit is the index of each player’s strategy and  the output of each circuit is interpreted as a -bit long integer specifying the utility.

Output (Decision version): does this game have a pure Nash equilibrium?

We would expect the running time to be polynomial in the input size: , and the total size of the circuits.  As before let us concentrate on cases where is not too large (i.e. also polynomial in these parameters).

So what is the complexity of this problem?  Generally speaking, the state of complexity theory is such that we get essentially no algorithmically-useful information from the circuit representation.  Thus, we would expect a polynomial time algorithm to exist for this generic representation only if such existed in the black-box model — which is doesn’t.  In this world we can easily prove an NP-completeness result.

Theorem: Existence of a pure Nash equilibrium in a game given by boolean circuits (as above) is NP-complete.

Proof: Containment in NP is by guessing the equilibrium point, and then verifying it by checking all possible deviations for every player.  (This is the only place where we used being small, otherwise the problem seems to be -complete).  To prove NP-hardness we will provide a reduction from 3-SAT (I lost the reference for this reduction).  All players will have two strategies: 0 and 1.  For each variable we will have a player whose utility function is a constant 0.  For each clause we will have an additional player whose utility function gives him 1 if his strategy is the OR of its literals.  We will then have two additional “top” players whose utilities are as follows: if all clause players play 1, then both of these players get utility 1 whatever they play; otherwise, these players play “matching pennies” between themselves.  Note that in a pure Nash equilibrium, the variable players can play anything, the clause players must faithfully compute the clause values, and then the two “top” players can be in equilibrium if and only if all clause values are 1.

The next succinct representation we consider is one that aims to take advantage of the fact that in many games while there are many players, each player’s utility only depends on the strategies of a few others and not on everyone’s strategies.  In such cases, we can represent  the utility of each player as a full table of only the relevant players’ strategies.  In such games an important structure is obtained by looking at the graph  (or digraph) specifying for each two players whether the utility of one depends on  the strategy played by the other.  So here is the equilibrium problem using this “graphical games” succinct representation:

Input: A graph and for each vertex in it, a table , where is the degree of vertex , and the table specifies the utility of player as a function of his strategy as well as those of his neighbors.

Output (Decision version): does this game have a pure Nash equilibrium?

We would expect the running time to be polynomial in the the total size of the tables, i.e polynomial in and in , where .

However just a tiny variation of the NP-completeness proof above shows that this problem in NP-complete too.  The only players in the reduction above who had degree more than 3 are the two top players who were “computing” the “AND” of all the clauses.  To get a reduction where all players have degree at most 3, we will add an additional player for each clause who will compute the “and” of this clause with all preceding ones.  This will be done by giving him utility 1 if his strategy is indeed the “and” of the original clause-player of his clause and the new-clause-player of the preceding clause (and 0 otherwise).  Now the two “top” players will just need to depend on the new-clause-player of the last clause as they did before (either always wining or playing matching pennies).  Thus we get:

Theorem: Existence of a pure Nash equilibrium in graphical games (as above) is NP-complete.

A nice exercise is to exhibit a polynomial time algorithm for the special case that when the graph is in fact a tree.

Now let us move to the special case of exact potential games.  The problem specification (input and output) is exactly as defined above where the utility functions are given as Boolean circuits, except that we are guaranteed that the utility functions are those of an exact potential game.  (This condition may not be easy to verify in general, but our algorithm may take it as an assumption.)   We know that a pure equilibrium is exactly a local maximum of the potential function.  This potential function is uniquely defined, up to an additive constant, by the given utility functions: once the value of the potential function is known for some profile, , we can change, in turn each to an arbitrary and the difference is completely specified by .  Thus the potential function is defined by   .  We see that the problem of finding a pure Nash equilibrium for potential games is equivalent to that of finding a local maximum of a given Boolean circuit, where “locality” is given by switching the values of one of the sets of bits in our problem definition. (Proof: the expression above is efficiently computable and thus our problem is no harder, and on the other hand a special case of our problem is where all ‘s are identical in which case our problem is equivalent to finding a local maximum.)

Now let us say a few words about the complexity of this local-maximum problem.  First, syntactically speaking we have an “NP search problem”: on input (the utility functions) the task is to find some solution (strategy profile) that satisfies ( is a local maximum of ), where is computable in polynomial time.  The general class of such search problems is termed FNP,  and in our case we are talking about problems with a guarantee that such a always exists, a subclass termed TFNP.  Now, semantically, there are various other problems that have a similar flavor of finding a local maximum (or minimum), and this class of problems, a subset of TFNP, was termed PLS (polynomial local search).  Some examples of such problems come from attempting to formalize what various local-improvement search heuristics obtain: suppose that you attempt finding a short traveling salesman route by gradually trying to switch the locations of pairs of cities along the route.  What do you get?  How long will this take?  The general class of problems in PLS is defined as those having polynomial-time computable procedures specifying a neighborhood relation and a quality score over solutions where the problem is to define a solution which is a local minimum (or maximum).  By these definitions, our problem is in this class PLS, and in fact the generic nature of our problem makes it PLS-complete.  So what does this PLS-completeness mean?  It means that the complexity of our problem is similar to the hardest problems in this class which seem to have intermediate difficulty between P and NP.  We do not know a polynomial time algorithm for them (and such an algorithm will require significantly new techniques since it doesn’t “relativize”), nor or they likely to be NP-complete (since that would also imply NP=coNP).

A special case of potential games is that of network congestion games.  In these we are given a (directed) graph, with pairs of vertices in it and, for each edge , a sequence of costs: .  This is a succinct representation of a congestion game: player ‘s set of strategies is the set of paths in the graph from to , and the cost (negative utility) of a player is the sum of over all edges in his path, where is the number of players whose strategy (path) contains the edge .  Network congestion games are exact potential games, and have a pure Nash equilibrium.  Finding such an equilibrium turns out to be PLS-complete too, although this requires a complicated reduction.

Read Full Post »

Outsourcing and CS education

The academic year has started today at the Hebrew University and I couldn’t help wondering what all our CS graduates will be doing ten or twenty years after graduation.  With the amazing rise of technology and science in much of the third developing world, their world-wide competition will be tough.  Will their software engineering jobs be outsourced too?   The current situation does not seem at equilibrium:

Read Full Post »

Supremum and mathematical education

My nephew just started his undergraduate degree in Math at the Technion.  When his grandfather, a high-powered engineer (whom I sometimes turn to for solving a differential equation that I need solved) , asked him what they learned in their very first calculus lesson, the answer was “supremum“.  The grandfather was mystified, claiming that “supremum” was not part of the math curriculum at all when he got his engineering degree half a century ago (also in the Technion, it turns out.)  While this can hardly be literally true, it does highlight the difference between the “abstract” approach to math and the “applied approach” which he got as an engineer.  From an abstract point of view, it makes much sense to start  with the notion of supremum, the ubiquitous existence of which essentially defines the real numbers, while I suppose that a more applied approach will hardly emphasize such abstract technical hurdles.  When I studied math at the Hebrew university, we spent an enormous amount of time on such abstract notions up to the point of ending the first year with hardly any practical abilities of figuring out a simple Integral but having a pretty good grasp of properties of zero-measure (yes, first year).

In my department, we have an on-going debate about the type of math that our CS students should get.  Traditionally, we have followed the extremely abstract tradition of our math department which emphasizes the basics rather than applications (even in the “differential equations” course, students rarely solve them, but more often prove existence and such).   In the last decade or so there has been a push in my department to shift some focus to “useful” math too (like being able to actually use singular value decomposition or Fourier transform, as needed in computer vision, learning theory, and other engineering-leaning disciplines).  I’m on the loosing side of this battle and am against this shift away from the “non-useful” fundamentals.   The truth is that most computer scientists will rarely need to use any piece of “useful” math.  What they will constantly need to use is “mathematical maturity”: being comfortable with formal definitions and statements, being able to tell when a proof is correct, knowing when and how to apply a theorem, and so on.

Read Full Post »

RoboZZle and the Essence of Algorithms

The essence of algorithms is that of combining simple operations as to solve complex problems.  Key is that everything should be completely well defined: the available simple operations, how they may be combined, the complex problem, and the correctness of your solution.  Elegance is bridging a large semantic gap: the simpler and fewer the operations and the farther from them the problem seems to be, the more we are impressed.  The simpler the solutions turn out to be, the more we are impressed.

I have just been introduced to a web site that gets as close to this essence as anything that I’ve seen: RoboZZle.  The problems are given by mazes, where the goal to pick all “stars” on the maze.  You must instruct a “robot” to do so, using very few commands: turn left or right, go forward, call a subroutine, do one of the above conditioned on the color of the square that you are on, or change the color of the square that you are on.  That’s it.  Programs must be very short, usually around half a dozen commands, and are entered, debugged, and run very easily graphically.  Amazingly, this is enough for a multitude of interesting challenges, ranging from ones that are easy for kids, to ones that baffle me (despite the solution being of length 5).

These puzzles give you the main intellectual ingredients of algorithms and programming: not only using loops and conditionals but also abstraction (defining subroutines) and recursion.  Check it out or, better, have your kids do so.

Read Full Post »

Back to School

I have finished my 2-year sabbatical/leave-of-absence at Google Tel-Aviv and am returning full time to the School of CSE and the Center of Rationality at the Hebrew University of Jerusalem.   This year I am teaching three courses, of which two are on Algorithmic Game Theory, jointly with Michal Feldman:

1. In the first semester — that starts in two weeks — Michal and me are teaching a course titled (somewhat arbitrarily) “Topics on the border of computation and economics” which will focus mostly on (1) hardness of reaching equilibrium and (2) inefficiency of equilibrium, i.e. basically parts I & III of the AGT book.  Some of the non-standard choices we are making are to take a deliberately wide view of the types of equilibrium studied (including correlated equilibrium, various notions of coalition-proof, sink-equilibria), and to focus on pure strategies for the first part of the course (these suffice to demonstrate clearly several issues: convergence and its speed (PLS), price of anarchy and stability, strong equilibrium, congestion/potential games, network creation games.)
2. In the second semester, Michal and me are teaching a course titled (again, arbitrarily) Computational topics in game theory, this one devoted to algorithmic mechanism design and electronic auctions, i.e. basically part II of the AGT book.
3. I am also teaching in the second semester a highly applied undergraduate course titled From Nand to Tetris which is based on a book The elements of computing systems that I wrote with Shimon Schocken.  The idea is to have the students build, in a single semester, a complete working computer, starting with the lowest hardware levels (a Nand gate), going through a CPU, an assembler, a virtual machine, a compiler, a (wannabe)-OS, and ending with a working application (such as Tetris).  The point is that everything is actually constructed by the students (hardware that is simulated using a hardware description language, and software that actually runs).

Read Full Post »

New Penn Program in Market and Social Systems Engineering

Penn just announced a new undergraduate program in “market and social systems engineering”:

The University of Pennsylvania has launched a first-of-its-kind program that will prepare undergraduate students to shape the technologies that underpin Web search, keyword auctions, electronic commerce, social and financial networks and the novel and unanticipated markets and social systems of the years ahead.

<snip>

The intellectual core of the program will encompass network science, algorithmic game theory and other disciplines relevant to engineers and scientists as they consider human incentives and behavior in developing modern technological systems.

<snip>

Based within Penn’s School of Engineering and Applied Science, the program will enroll students in the fall of 2011.

<snip>

Penn Engineering will hire new faculty for the program, in addition to calling on the strengths of Penn’s current faculty across Penn Engineering, the School of Arts and Sciences and the Wharton School.

<snip>

Traditional programs don’t prepare students to design systems that take into account the goals and incentives of the people who use them,” said Michael Kearns, professor in the Department of Computer and Information Science in Penn’s School of Engineering and Applied Science and the program’s founding faculty director. “We haven’t asked engineering students to take a course in game theory to understand how incentives work or in sociology to understand human behavior. There is now enough science out there on the intersection of these topics to design undergraduate courses.”

Read Full Post »