CPS 296.1: Computational Microeconomics: Game Theory, Social Choice, and Mechanism DesignWhat is Economics?An economic pictureAfter trade (a more efficient outcome)Some distinctions in economicsWhat is Computer Science?Resource allocation as a computational problemEconomic mechanismsWhat is game theory?What is game theory…Penalty kick exampleGame playing & AIQuestions and problems in (computational) game theoryWhat is social choice?Voting over outcomesCombinatorial auctionsKidney exchangeProblems in computational social chocieWhat is mechanism design?Mechanism design…Example: (single-item) auctionsWhich auction generates more revenue?Slide 23Many uses of linear programming, mixed integer (linear) programming in this courseSponsored searchPrediction marketsFinancial securitiesHow to incentivize a weather forecasterWhy should economists care about computer science?Why should economists care about computer science…Why should computer scientists care about economics?CPS 296.1:Computational Microeconomics: Game Theory, Social Choice, and Mechanism DesignInstructor: Vincent Conitzer (Assistant Professor of Computer Science & Economics)[email protected] web page: http://www.cs.duke.edu/courses/fall09/cps296.1What is Economics?•“Economics is the social science that studies the production, distribution, and consumption of goods and services.” [Wikipedia, Aug. 2009]•Some key concepts:–Economic agents or players (individuals, households, firms, …)–Agents’ current endowments of goods, money, skills, …–Possible outcomes ((re)allocations of resources, tasks, …)–Agents’ preferences or utility functions over outcomes–Agents’ beliefs (over other agents’ utility functions, endowments, production possibilities, …)–Agents’ possible decisions/actions–Mechanism that maps decisions/actions to outcomesAn economic picture$ 600$ 800$ 200v( ) = 400v( ) = 200) = 200v(v( ) = 100v( ) = 400After trade (a more efficient outcome)$ 400$ 1100$ 100v( ) = 400v( ) = 200) = 200v(v( ) = 100v( ) = 400… but how do we get here?Auctions? Exchanges? Unstructured trade?Some distinctions in economics•Descriptive vs. normative economics–Descriptive: •seeks only to describe real-world economic phenomena•does not care if this is in any sense the “right” outcome–Normative:•studies how people “should” behave, what the “right” or “best” outcome is•Microeconomics vs. macroeconomics–Microeconomics: analyzes decisions at the level of individual agents •deciding which goods to produce/consume, setting prices, …•“bottom-up” approach–Macroeconomics: analyzes “the sum” of economic activity•interest rates, inflation, growth, unemployment, government spending, taxation, …•“big picture”What is Computer Science?•“Computer science (or computing science) is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems” [Wikipedia, Aug. 2009]•A computational problem is given by a function f mapping inputs to outputs–For integer x, let f(x) = 0 if x is prime, 1 otherwise–For an initial allocation of resources x, let f(x) be the (re)allocation that maximizes the sum of utilities•An algorithm is a fully specified procedure for computing f–E.g. sieve of Eratosthenes–A correct algorithm always returns the right answer–An efficient algorithm returns the answer fast•Computer science is also concerned with building larger artifacts out of these building blocks (e.g., personal computers, the Internet, the Web, search engines, spreadsheets, artificial intelligence, …)Resource allocation as a computational problem$ 800$ 400v( ) = $400v( ) = $600v( ) = $500v( ) = $400$ 750$ 450inputoutputHere, gains from trade ($300) are divided evenly(not essential)Economic mechanisms$ 800$ 400v( ) = $400v( ) = $600v( ) = $500v( ) = $400$ 800$ 400“true” inputresult$ 800v() = $500v( ) = $501agents’ bids$ 400v() = $451v( ) = $450agent 1’s bidding algorithmagent 2’s bidding algorithmexchange mechanism(algorithm)Exchange mechanism designer does not have direct access to agents’ private informationAgents will selfishly respond to incentivesWhat is game theory?•“Game theory is a branch of applied mathematics that is used in the social sciences, most notably in economics, as well as in biology, engineering, political science, international relations, computer science, and philosophy. Game theory attempts to mathematically capture behavior in strategic situations, in which an individual's success in making choices depends on the choices of others.” [Wikipedia, Aug. 2009]What is game theory…•Game theory studies settings where multiple parties (agents) each have–different preferences (utility functions),–different actions that they can take•Each agent’s utility (potentially) depends on all agents’ actions–What is optimal for one agent depends on what other agents do•Very circular!•Game theory studies how agents can rationally form beliefs over what other agents will do, and (hence) how agents should act–Useful for acting as well as predicting behavior of othersPenalty kick exampleprobability .7probability .3probability .6probability .4probability 1Is this a “rational” outcome? If not, what is?actionactionGame playing & AIperfect information games: no uncertainty about the state of the game (e.g. tic-tac-toe, chess, Go)imperfect information games: uncertainty about the state of the game (e.g. poker)1 gets King 1 gets Jackbet betstay staycall fold call fold call fold call fold“nature”player 1player 1player 2 player 2whiteblack blackQa1-a8 Qa1-f6Kf8-f7 Kf8-g7 Kf8-g8 Kf8-e8black wins white wins draw draw2 1 1 1 -2 -11 1•Optimal play: value of each node = value of optimal child for current player (backward induction, minimax)•For chess and Go, tree is too large–Use other techniques (heuristics, limited-depth search, alpha-beta, …)•Top computer programs (arguably) better than humans in chess, not yet in Go•Player 2 cannot distinguish nodes connected by dotted lines–Backward induction fails; need more sophisticated game-theoretic techniques for optimal play•Small poker variants can be solved optimally•Humans still better than top computer programs at full-scale poker (at least most versions)•Top computer (heads-up) poker players are based on techniques for game theoryQuestions and
View Full Document
Unlocking...