Update cookies preferences

E-book: Economics and Computation: An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division

Edited by , Illustrated by
Other books in subject:
  • Format - PDF+DRM
  • Price: 92,01 €*
  • * the price is final i.e. no additional discount will apply
  • Add to basket
  • Add to Wishlist
  • This ebook is for personal use only. E-Books are non-refundable.
Economics and Computation: An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair DivisionLarger Image
Other books in subject:

DRM restrictions

  • Copying (copy/paste):

    not allowed

  • Printing:

    not allowed

  • Usage:

    Digital Rights Management (DRM)
    The publisher has supplied this book in encrypted form, which means that you need to install free software in order to unlock and read it.  To read this e-book you have to create Adobe ID More info here. Ebook can be read and downloaded up to 6 devices (single user with the same Adobe ID).

    Required software
    To read this ebook on a mobile device (phone or tablet) you'll need to install this free app: PocketBook Reader (iOS / Android)

    To download and read this eBook on a PC or Mac you need Adobe Digital Editions (This is a free app specially developed for eBooks. It's not the same as Adobe Reader, which you probably already have on your computer.)

    You can't read this ebook with Amazon Kindle

This textbook connects three vibrant areas at the interface between economics and computer science: algorithmic game theory, computational social choice, and fair division. It thus offers an interdisciplinary treatment of collective decision making from an economic and computational perspective. Part I introduces to algorithmic game theory, focusing on both noncooperative and cooperative game theory. Part II introduces to computational social choice, focusing on both preference aggregation (voting) and judgment aggregation. Part III introduces to fair division, focusing on the division of both a single divisible resource ("cake-cutting") and multiple indivisible and unshareable resources ("multiagent resource allocation"). In all these parts, much weight is given to the algorithmic and complexity-theoretic aspects of problems arising in these areas, and the interconnections between the three parts are of central interest.

Foreword v
Matthew O. Jackson
Yoav Shoham
Preface by the Editor vi
Contributors xiii
1 Playing, Voting, and Dividing
1(40)
J. Rothe
1.1 Playing
3(2)
1.1.1 Noncooperative Game Theory
3(1)
1.1.2 Cooperative Game Theory
4(1)
1.2 Voting
5(4)
1.2.1 Preference Aggregation by Voting
5(3)
1.2.2 Manipulative Actions in Single-Peaked Societies
8(1)
1.2.3 Judgment Aggregation
8(1)
1.3 Dividing
9(7)
1.3.1 Cake-cutting: Fair Division of Divisible Goods
9(1)
1.3.2 Fair Division of Indivisible Goods
10(1)
1.3.3 A Brief Digression to Single-Item Auctions
11(5)
1.4 Some Literature Pointers
16(1)
1.5 A Brief Digression to Computational Complexity
17(24)
1.5.1 Some Foundations of Complexity Theory
17(6)
1.5.2 The Satisfiability Problem of Propositional Logic
23(10)
1.5.3 A Brief Compendium of Complexity Classes
33(8)
Part I Playing Successfully
2 Noncooperative Game Theory
41(94)
P. Faliszewski
I. Rothe
J. Rothe
2.1 Foundations
42(18)
2.1.1 Normal Form, Dominant Strategies, and Equilibria
43(7)
2.1.2 Further Two-Player Games
50(10)
2.2 Nash Equilibria in Mixed Strategies
60(21)
2.2.1 Definition and Application to Two-Player Games
60(9)
2.2.2 Existence of Nash Equilibria in Mixed Strategies
69(12)
2.3 Checkmate: Trees for Games with Perfect Information
81(19)
2.3.1 Sequential Two-Player Games
81(13)
2.3.2 Equilibria in Game Trees
94(6)
2.4 Full House: Games with Incomplete Information
100(19)
2.4.1 The Monty Hall Problem
101(6)
2.4.2 Analysis of a Simple Poker Variant
107(12)
2.5 How Hard Is It to Find a Nash Equilibrium?
119(16)
2.5.1 Nash Equilibria in Zero-Sum Games
119(3)
2.5.2 Nash Equilibria in General Normal Form Games
122(13)
3 Cooperative Game Theory
135(62)
E. Elkind
J. Rothe
3.1 Foundations
136(15)
3.1.1 Cooperative Games with Transferable Utility
137(3)
3.1.2 Stability Concepts for Cooperative Games
140(9)
3.1.3 Convex Games
149(2)
3.2 Simple Games
151(17)
3.2.1 The Core of a Simple Game
152(1)
3.2.2 Counting and Representing Simple Games
152(1)
3.2.3 Weighted Voting Games
153(4)
3.2.4 Dimensionality
157(2)
3.2.5 Power Indices
159(1)
3.2.6 The Shapley--Shubik Index and the Shapley Value
160(6)
3.2.7 The Banzhaf Indices
166(2)
3.3 Complexity of Problems for Succinctly Representable Games
168(29)
3.3.1 Games on Graphs
169(6)
3.3.2 Weighted Voting Games
175(8)
3.3.3 Hedonic Games
183(14)
Part II Voting and Judging
4 Preference Aggregation by Voting
197(130)
D. Baumeister
J. Rothe
4.1 Some Basic Voting Systems
198(30)
4.1.1 Scoring Protocols
199(3)
4.1.2 Voting Systems Based on Pairwise Comparisons
202(11)
4.1.3 Approval Voting and Range Voting
213(2)
4.1.4 Voting Systems Proceeding in Stages
215(6)
4.1.5 Hybrid Voting Systems
221(6)
4.1.6 Overview of Some Fundamental Voting Systems
227(1)
4.2 Properties of Voting Systems and Impossibility Theorems
228(23)
4.2.1 The Condorcet and the Majority Criterion
229(2)
4.2.2 Nondictatorship, Pareto Consistency, and Consistency
231(4)
4.2.3 Independence of Irrelevant Alternatives
235(2)
4.2.4 Resoluteness and Citizens' Sovereignty
237(1)
4.2.5 Strategy-Proofness and Independence of Clones
238(2)
4.2.6 Anonymity, Neutrality, and Monotonicity
240(4)
4.2.7 Homogeneity, Participation, and Twins Welcome
244(5)
4.2.8 Overview of Properties of Voting Systems
249(2)
4.3 Complexity of Voting Problems
251(76)
4.3.1 Winner Determination
253(7)
4.3.2 Possible and Necessary Winners
260(9)
4.3.3 Manipulation
269(22)
4.3.4 Control
291(26)
4.3.5 Bribery
317(10)
5 The Complexity of Manipulative Actions in Single-Peaked Societies
327(34)
E. Hemaspaandra
L.A. Hemaspaandra
J. Rothe
5.1 Single-Peaked Electorates
331(3)
5.2 Control of Single-Peaked Electorates
334(10)
5.3 Manipulation of Single-Peaked Electorates
344(7)
5.4 Bribery of Single-Peaked Electorates
351(2)
5.5 Do Nearly Single-Peaked Electorates Restore Intractability?
353(8)
5.5.1 K-Maverick-Single-Peakedness
355(1)
5.5.2 Swoon-Single-Peakedness
356(5)
6 Judgment Aggregation
361(34)
D. Baumeister
G. Erdelyi
J. Rothe
6.1 Foundations
365(2)
6.2 Judgment Aggregation Procedures and Their Properties
367(7)
6.2.1 Some Specific Judgment Aggregation Procedures
368(3)
6.2.2 Properties, Impossibility Results, and Characterizations
371(3)
6.3 Complexity of Judgment Aggregation Problems
374(17)
6.3.1 Winner Determination in Judgment Aggregation
375(1)
6.3.2 Safety of the Agenda
376(1)
6.3.3 Manipulation in Judgment Aggregation
376(7)
6.3.4 Bribery in Judgment Aggregation
383(4)
6.3.5 Control in Judgment Aggregation
387(4)
6.4 Concluding Remarks
391(4)
Part III Fair Division
7 Cake-Cutting: Fair Division of Divisible Goods
395(98)
C. Lindner
J. Rothe
7.1 How to Have a Great Party with only a Single Cake
395(1)
7.2 Basics
396(5)
7.3 Valuation Criteria
401(15)
7.3.1 Fairness
401(9)
7.3.2 Efficiency
410(1)
7.3.3 Manipulability
411(4)
7.3.4 Runtime
415(1)
7.4 Cake-Cutting Protocols
416(77)
7.4.1 Two Envy-Free Protocols for Two Players
417(6)
7.4.2 Proportional Protocols for n Players
423(22)
7.4.3 Super-Proportional Protocols for n Players
445(5)
7.4.4 A Royal Wedding: Dividing into Unequal Shares
450(2)
7.4.5 Envy-Free Protocols for Three and Four Players
452(9)
7.4.6 Oversalted Cream Cake: Dirty-Work Protocols
461(5)
7.4.7 Avoiding Crumbs: Minimizing the Number of Cuts
466(19)
7.4.8 Degree of Guaranteed Envy-Freeness
485(4)
7.4.9 Overview of Some Cake-Cutting Protocols
489(4)
8 Fair Division of Indivisible Goods
493(58)
J. Lang
J. Rothe
8.1 Introduction
493(2)
8.2 Definition and Classification of Allocation Problems
495(5)
8.2.1 Allocation Problems
495(1)
8.2.2 Classification of Allocation Problems
496(4)
8.3 Preference Elicitation and Compact Representation
500(8)
8.3.1 Ordinal Preference Languages
502(2)
8.3.2 Cardinal Preference Languages
504(4)
8.4 Criteria for Allocations
508(10)
8.4.1 Ordinal Criteria
509(2)
8.4.2 Cardinal Criteria
511(7)
8.5 Computing Allocations: Centralized Mechanisms
518(20)
8.5.1 Centralized Fair Division with Ordinal Preferences
519(3)
8.5.2 Centralized Fair Division with Cardinal Preferences without Money
522(10)
8.5.3 Centralized Fair Division with Cardinal Preferences and Money
532(6)
8.6 Decentralized Allocation Protocols
538(9)
8.6.1 The Descending Demand Protocols
539(2)
8.6.2 The Picking Sequences Protocols
541(2)
8.6.3 Contested Pile-Based Protocols: Undercut
543(3)
8.6.4 Protocols Based on Local Exchanges
546(1)
8.7 Further Issues
547(4)
8.7.1 Strategy-Proofness
547(1)
8.7.2 Matching
548(1)
8.7.3 Private Endowments
549(1)
8.7.4 Randomized Fair Division
549(2)
References 551(30)
List of Figures 581(4)
List of Tables 585(2)
Index 587
Dorothea Baumeister from Heinrich-Heine-Universität Düsseldorf, Germany, has coauthored Chapter 4 on preference aggregation by voting and Chapter 6 on judgment aggregation.

Edith Elkind from University of Oxford, UK, has coauthored Chapter 3 on cooperative game theory.

Gábor Erdélyi from University of Siegen, Germany, has coauthored Chapter 6 on judgment aggregation.

Piotr Faliszewski from AGH University of Science and Technology in Kraków, Poland, has coauthored Chapter 2 on noncooperative game theory.

Edith Hemaspaandra from Rochester Institute of Technology, USA, has coauthored Chapter 5 on the complexity of manipulative actions in single-peaked societies.

Lane A. Hemaspaandra from University of Rochester, USA, also has coauthored Chapter 5 on the complexity of manipulative actions in single-peaked societies.

Jérôme Lang from CNRS-LAMSADE, Université Paris-Dauphine, France, has coauthored Chapter 8 on fair division of indivisible goods.

Claudia Lindner from University of Manchester, UK, has coauthored Chapter 7 on cake-cutting: fair division of divisible goods.

Irene Rothe from Bonn-Rhein-Sieg University of Applied Sciences, Germany, has coauthored Chapter 2 on noncooperative game theory.

Jörg Rothe from Heinrich-Heine-Universität Düsseldorf, Germany, has written introductory Chapter 1 and has coauthored Chapters 28.
More information about ebooks More information about ebooks
Permanent link: https://www.kriso.ee/db/97836624790492e.html
Keywords: