Social Networks § So the topology of a social network has a big influence on the extent of distortions and on other heavily studied applications such as: • The spread of computer viruses. [...] Example: Optimal Solution: 2 The 𝜌-Illusion Elimination Problem § This problem is essentially a distance measures how far H is from a graph that does not suffer from misinformation? § More generally, consider a bi-coloured graph H where at least a 𝜌-fraction of the vertices are blue. [...] Now we can derive analogues of the Fundamental Welfare Theorems for the case of Combinatorial Markets… The Welfare Theorems § For combinatorial markets we have seen that equilibria need not exist. [...] If there the linear program relaxation is integral then there is a Walrasian equilibrium for the corresponding allocation. [...] § So the existence of an equilibrium corresponds to the integrality of an LP.
- Pages
- 47
- Published in
- Canada
Table of Contents
- Thoughts for the Day 2
- Majority Illusion 4
- Social Networks 6
- The Illusion Elimination Problem 7
- The -Illusion Elimination 8
- Problem 8
- Our Results 9
- 0 1 9
- 3 1 9
- 2 2 9
- 3 1 9
- Eliminating 11
- Illusion 11
- An Integer Program 12
- A Linear Program 13
- Integral Linear Programs 14
- A Digression on Integer Programming 17
- The Welfare Theorems 18
- Markets with 19
- Indivisible 19
- Goods 19
- Demand Bundles 20
- A Walrasian Equilibrium 21
- Unfortunately Walrasian equilibria need not exist in Combinatorial Markets 22
- A Simple Example 23
- And if they exist what can we say about them 25
- An IP Formulation 26
- An LP Relaxation 27
- The Dual LP 29
- Now we can derive analogues of the Fundamental Welfare Theorems for the case of Combinatorial Markets 30
- The Welfare Theorems 31
- A Characterization 32
- Theorem 32
- A Digression on Computational Complexity 33
- The Revenue Maximization Problem 34
- Why Prices 35
- Algorithms 35
- Back to Illusion Elimination 36
- Another Linear Program 37
- Step 1 38
- Step 2 39
- Step 3 40
- A New Set of Constraints 41
- Step 4 43
- A Polytime Algorithm 44
- The Hardness 45
- Result 45
- 0 1 45
- 3 1 45
- 2 2 45
- 3 1 45
