decisions regarding spring 24 6319, books, topics, homeworks, projects, quizzes steiglitz: Snipers, Shills, and Sharks: eBay and Human Behavior - free download on syllabus matousek/gartner: LP - free download on syllabus shoham/leyton-brown: MAS - free download on syllabus manlove: - free download on syllabus winning ways: available through library von Stengel: Game Theory Basics, what ideas to rip-off?!?!?!?!?!?!? <<<<<<<<<<<<<< 1. Mex rule and impartial games 3. Cournot duopoly 5. expected utility 9. best-response diagrams, Lemke-Howson 12. Distinctions between correlated, coarse correlated, and ?????? Paul Klemperer, Auctions: Theory and Practice, chapters available for download from UTA library, has exercises ***** <<<< improve facility location examples <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< Nash bargaining? reasonable examples/exercises? xxxxxxxxxxxx Topics: Linear programming - add two weeks of concepts? how might Bichler book (or polyhedralCombinatorics.pdf or Gartner/Matousek) fit in? <<<<<<<<<<<<<<<<<<<<< Spectrum/combinatorial auctions - compress coverage (new Roughgarden book case study, chapter 24 along with pnas.201701997.pdf?) POA - any way to condense? ML - any way to condense or leave out? Complexity and Lemke/Howson - something less superficial (fortnow "The Status of the P versus NP Problem" paper?) fair division - do cakecutting-divisible/bankruptcy after matching-indivisible (rent division) social choice - are voting rules critical?????????????? facility location games - "unify" the many versions (Vetta?, chap 19 and 15.4.2 of Nisan, netsurv.jackson.pdf) <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< correlated equilibria need to come across as much simpler than Nash equilibria (H. P. Young chapter) tatonnement (Walrasian auction) convergence, N 6.1.2?????? fixed points (as context) equilibrium selection? doing more with the collected papers!!!!!!!! cluster for purposes of group projects?!?!?!? REVIEW THESE!!!!!!!!!!!!!!!!!! Game Theory Concepts Potential Games Facility Location Nisan 17/18/19, vetta papers <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< Equilibria Two-Person Zero-Sum Two-Person Bimatrix (in exponential time) <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< KP, p. 96 problem 4.12 MAS, p. 91 Linear Complementarity Problem (LCP), p. 93 Lemke-Howson, p. 94 Degeneracy, p. 96 footnote Searching the space of supports, p. 101 (support-enumeration method) <<<<<<< Does this require C code or is glpsol sufficient? Issues are creating supports and testing conditional dominance <<<<<<<<<<<< gambit-enumpoly on command line with -H option TGS: feasibility program for "test given supports", p. 102 Conditionally strictly dominated action, p. 103 (also see ~/6319/PAPERS-OTHER/simplesearchnashGEB.pdf, sections 4 & 5 and journal version ~/Downloads/porterNudelmanShoham.pdf) Figure 4.6: The SEM algorithm N chapters 3, Algorithm 3.4 - Equilibria by support enumeration Complexity Linear Programming POA Mechanism Design Voting/Politics Auctions VCG Combinatorial/Spectrum All-Pay Sponsored Search Preference Fair Division Matching Adaptive Decision Making Other getting students more confident "early on" with VCG "charging externality" (Steiglitz?) <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< Courses to borrow from: Conitzer, duke - spring 22, used multiagent systems book https://courses.cs.duke.edu/spring22/compsci323d/ tardos, cornell - spring 20, used Roughgarden and others https://www.cs.cornell.edu/courses/cs6840/2020sp/ fu, UBC - winter 16 https://www.fuhuthu.com/CPSC536F2016/index.htm roth, penn - spring 21 https://www.cis.upenn.edu/~aaroth/courses/agtS21.html Books? KP - definite keep, N - cheap to keep, R (or his notes from web) Would lighten up POA(?) Approximately (Near-) Optimal Auctions: Prophet inequality, Bulow-Klemperer (OK to leave out or make aside) Adaptive decision making (R 16/17/18, KP 18, N 4) (OK to leave out or make aside) Complexity of equilibria (R 19/20, N 2/3/19.3.4) Also use Shoham and Leyton-Brown http://www.masfoundations.org/download.html Matousek and Gartner, "Understanding and Using Linear Programming", online UTA library (zero-sum in section 8.1) Readings from Steiglitz (move to textbooks section of syllabus? No) Hans Peters, Game Theory: A Multi-Leveled Approach is available for download through UTA library . . . H.P. Young, chapter 3 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< Student deliverables: <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< For 2024 - 5319 give them 2022 and 2023 homework solutions, then have several (3-6) quizzes. GTA ISSUE!?!?!?!?!?!? 6319, 20% of grade for project. exams/quizzes (how many?????????? format, e.g. open notes?) - just open-book final!!!!!!!!!!!!!!!!!!!! homeworks (reuse 2022/2023 HWs with additional problems thrown in? Really need LP problems!!!!!!!!!!!!!!!!!!!!!) <<<<<<<<<< 1. Linear programming, Gambit, max matching (Konig's lemma), equilibria, optimal baskets of goods, new - potential games, best-response, correlated, coarse correlated 2. Equilibria, location game, POA, new - makespan scheduling, smooth games 3. Preference matching, bankruptcy/fair division, new - social choice (notes 3.C), auctions 4. Wallet game, allocation for downward sloping valuations, VCG payments MST, opt. fixed prices for digital good, new - VCG for shortest path, VCG for sponsored search, RSRE New homework involving more on combinatorial auctions (Lehmann? Nisan multi-unit auction?), convergence/learning 5. Lowest/highest envy-free price vector, fair division of rent, new - spliddit (not regularly available) anything with SAT/ASP? XXXXXXXXXXXX programs?????? 6319 - projects and/or presentations, groups?, involve 5319 students? topics??????? <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< • 5 students for 6319, 20 students for 5319 (01/08/24) • Designate eligible (recent? after 2018?) "primary source" papers, others must be approved • Connections to lecture material/readings • Expectations for presentation (e.g. example, take-home problem, 20 minutes) • topics - eBay/california, matching, utility, redistricting, Jeopardy, mastermind/wordle (Bonnet & Viennot; JACM 63 (5)), multi-player CE, evol. stable strategies, equilibrium selection?, sprouts?, goofspiel, kuhn poker, extensive form? • Two proposal submission dates - first: March 4 (Monday), second: March 25 (Monday) <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< • Grading: Topic 10% (1-2 page narrative including motivation, likely examples/diagrams, 1-3 primary references) Revised Topic 15% Presentation 75% 20-25 minutes (materials 60%, oral skills 20%, questions/future of topic 20%) potential games (which ones?) in LP <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< Selfish routing (Braess, Pigou as instances) have unique equilibrium flows Atomic Selfish routing (?????????????????? as instances) have non-unique equilibrium flows glpk.pdf - GNU Linear Programming Kit, appendix D: Stand-alone LP/MIP Solver gmpl.pdf - Modeling Language GNU MathProg, appendix D: Solving models with glpsol generalize corrEq.mod and coarseCorrEq.mod linear programming to arbitrary number of players? <<<<<<<<<<<<<<<<<<<<<<<<< Just do symmetric players?????????????????? Diet plan (Gale) Transportation (Gale) Flow (Matousek) Production to meet demand at minimum cost (Gale) Maximize income from resources (Gale) Two-person games - (Gale) chaps 6, 7 Colonel Blotto (Matousek) two-person zero-sum game duality farkas lemma simplex khachiyan? karmarkar? exp. time solution to two-person general-sum using LP corr. eq. (graphical games, too?) stable matching equilibrium prices winner determination problem knapsack integer programs rounding assignment problem competitive equilibria Exposure to: 1. Game Theory concepts. 15% 2. Price-of-Anarchy concepts. 15% 3. Mechanism Design. 50% 4. Adaptive Decision Making. 10% 5. Complexity Issues for Equilibria. 10% Issues with notes: 0. Motivation (new)??????????????????????????? 1. Game Theory Concepts Linear Programming: p. 6 LP, Appendix A of KP; Appendix A of Bichler <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< Motivating correlated equilibria? Implementation of optimal baskets of goods with maxflow? (and LP???) Extensive form ???????????????<<<<<<<<<<<<<<<<<<<<<<<<<< 2. POA Getting across the four equilibria - pure, mixed, correlated, coarse correlated Getting across potential games - especially facility location games <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< Coherency of smooth games??????? 3. Mechanism Design (1)Social Choice - Condorcet, axiomatics, voting rules, negative results????????????? VCG etc. Knapsack auctions??? Individually Rational/Risk Aversion??? Distributional results for auctions (2)Multi-unit auctions - Nisan survey (3.F - notes 3 part 2, more homework problems from this, especially knapsack?????????????????????) Bidding languages??? Applications of VCG "Lovely, but Lonely" Revenue Maximization/Optimal Auctions (3)General VCG Combinatorial Auctions (Nisan, chapter 11) 2016 spectrum auction Matching Markets - envy-free prices, rent division 4. Adaptive Decision Making <<<<<<<<<<<<<<<<<<<<< strengthen <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< Best-Response Dynamics No-Regret Dynamics Online Decision Making Multiplicative Weights (CLRS 33.2???) Swap Regret 5. Complexity of Equilibria Four Positive Results PLS-Completeness PNE of Congestion Games MNE of Bimatrix Games - PPAD-Completeness