Topics: Linear programming - add two weeks? use gnu GLPK? 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 social choice - are voting rules critical?????????????? facility location games - "unify" the many versions (Vetta?, chap 19 of Nisan)) correlated equilibria need to come across as much simpler than Nash equilibria 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?!?!?!? Game Theory Potential Games Facility Location Equilibria Two-Person Zero-Sum Complexity POA Mechanism Design Voting/Politics Auctions VCG Combinatorial/Spectrum All-Pay Sponsored Search Preference Fair Division Adaptive Decision Making Other getting students more confident "early on" with VCG (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) Student deliverables: exams/quizzes (how many?????????? format, e.g. open notes?) - just open-book final!!!!!!!!!!!!!!!!!!!! <<<<<<<<<<<<<<< homeworks (reuse 2022 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?), convergence/learning 5. Lowest/highest envy-free price vector, fair division of rent, new - spliddit anything with SAT/ASP? programs?????? 6319 - projects and/or presentations, groups?, involve 5319 students? topics??????? <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< • Designate eligible (recent? after 2018?) "primary source" papers, others must be approved • Connections to lecture material • Expectations for presentation (e.g. example, take-home problem, 20 minutes) LP examples with GLPK <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< glpk.pdf - GNU Linear Programming Kit, appendix D: Stand-alone LP/MIP Solver gmpl.pdf - Modeling Language GNU MathProg, appendix D: Solving models with glpsolrm diet.out 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 1. Exposure to Game Theory concepts. 15% 2. Exposure to Price-of-Anarchy concepts. 15% 3. Exposure to Mechanism Design. 50% 4. Exposure to Adaptive Decision Making. 10% 5. Exposure to 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 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 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