Introduction to algorithmic aspect of auction theory

50 %
50 %
Information about Introduction to algorithmic aspect of auction theory

Published on May 10, 2014

Author: cytang


Introduction to Algorithmic Aspect of Auction Theory 2010-01-08 Abner Huang 1 CSBB Lab, Dept. of CS, NTHU.

Outline • Connections between Computer Science and Economics • Algorithmic Game Theory • Algorithmic Mechanism Design 2

Herbert Alexander Simon • Herbert Alexander Simon (June 15, 1916– February 9, 2001) was an American political scientist, economist, and psychologist. • Notable awards – Turing Award 1975 – Nobel Prize in Economics 1978 3

Thomas Crombie Schelling Thomas Crombie Schelling (born 14 April 1921) was awarded the 2005 Nobel Memorial Prize in Economic Sciences (shared with Robert Aumann) for "having enhanced our understanding of conflict and cooperation through game-theory analysis." 4

Micromotives and macrobehavior • Schelling analyzed apartheid with cellular automata, which is invented by John von Neumann and is well-studied by computer scientists. 5

Market Equilibrium-- Arrow-Debreu model 6

Market Equilibrium • Starting in the 60’s, economists have attempted to use the Arrow-Debreu model and the general equilibrium theory to realistically model actual economies, with the goal of evaluating alternate policy options. – Scarf’s algorithm, – Homotopy methods, – Global Newton’s method 7

Market Equilibrium • There are several algorithmic results in the last 6 years, i.e., PTAS, FPTAS, and polynomial time algorithm based on diophantine approximation and ellipsoid algorithm. • Fisher’s Model with Linear Utility Functions is in P. • Arrow-Debreu’s Model with Linear Utility Functions is in P. 8


Outline • Connections between Computer Science and Economics • Algorithmic Game Theory • Algorithmic Mechanism Design 10


Traffic Flow Problem 12

13 Braess’s Paradox Initial Network: s t x 1 ½ x1 ½ ½ ½ Cost = 1.5

14 Braess’s Paradox Initial Network: Augmented Network: s t x 1 ½ x1 ½ ½ ½ Cost = 1.5 Cost = 2 s t x 1 x1 0

15 Braess’s Paradox Initial Network: Augmented Network: All traffic incurs more cost! [Braess 68] • also has physical analogs [Cohen/Horowitz 91] s t x 1 ½ x1 ½ ½ ½ Cost = 1.5 Cost = 2 s t x 1 x1 0

16 Inefficiency of Nash Flows Note: selfish routing does not minimize average delay (observed informally by [Pigou 1920]) • Cost of equilibrium flow = 1•1 + 0•1 = 1 • Cost of optimal (min-cost) flow = ½•½ +½•1 = ¾ s t x 1 0 1 ½ ½

17 Performance Guarantees Good news: in theoretical CS, have lots of techniques for measuring inefficiency. • motivated by NP-completeness, real-time algorithms, etc. Definition: approximation ratio (w.r.t. some objective function): optimal obj fn value protagonists's obj fn value the closer to 1 the better Price of anarchy := equilibrium/OPT ratio

Market Equilibrium • Fisher’s model 18

Market Equilibrium 19






Arrow-Debreu model An Auction-Based Algorithm Garg et al. proposed an auction-based PTAS for the linear case of the Arrow-Debreu model. 25

Remarks 26

Outline • Connections between Computer Science and Economics • Algorithmic Game Theory • Algorithmic Mechanism Design 27

Algorithmic mechanism design • Algorithmic mechanism design (AMD) lies at the intersection of economic game theory and computer science. • Noam Nisan and Amir Ronen, from the Hebrew University of Jerusalem, first coined "Algorithmic mechanism design" Games and Economic Behavior (35): 166–196. 28

Algorithmic mechanism design • It typically employs the analytic tools of theoretical computer science, such as worst case analysis and approximation ratios, in contrast to classical mechanism design in economics which often makes distributional assumptions about the agents. • It also considers computational constraints to be of central importance: mechanisms that cannot be efficiently implemented in polynomial time are not considered to be viable solutions to a mechanism design problem 29

30 Worst-Case Time Complexity n=1000 ,Time cost for different computer time Time 1 1000 steps/s Time 2 2000 steps/s Time 3 4000 steps/s Time 4 8000 steps/s log2n 0.010 0.005 0.003 0.001 n 1 0.5 0.25 0.125 nlog2n 10 5 2.5 1.25 n1.5 32 16 8 4 n2 1,000 500 250 125 n3 1,000,000 500,000 250,000 125,000 1.1n 1039 1039 1038 1038

P vs. NP-Hard • P = the set of problems which can be solved in polynomial time ,e.g., – 50*n0.2,3*n+2000, 0.01*n+19861234, 0.001*n80 – Finding maximum of a set of integers is in P. (linear time in fact.) • EXP = the set of problems which can be solved in exponential time. • NP-Hard = the set of problems which might be able to be solved in polynomial time (at least). 31

Distributed artificial intelligence • Mainstreams in DAI research included the following: – Parallel problem solving: mainly deals with how classic AI concepts can be modified, so that multiprocessor systems and clusters of computers can be used to speed up calculation. – Distributed problem solving (DPS): the concept of agent, autonomous entities that can communicate with each other, was developed to serve as an abstraction for developing DPS systems. – Multi-Agent Based Simulation (MABS): a branch of DAI that builds the foundation for simulations that need to analyze not only phenomena at macro level but also at micro level, as it is in many social simulation scenarios. 32

Multi-Agent Based Simulation • Too crowded or too desolate in PUB? 33

Applications of Algorithmic mechanism design • Load balancing: The aggregate power of all computers on the Internet is huge. In a “dream world” this aggregate power will be optimally allocated online among all connected processors. One could imagine CPU-intensive jobs automatically migrating to CPU-servers, caching automatically done by computers with free disk space, etc. Access to data, communication lines and even physical attachments (such as printers) could all be allocated across the Internet. tightly linked systems, and is addressed, in various forms and with varying 34

Applications of Algorithmic mechanism design • Routing: When one computer wishes to send information to another, the data usually gets routed through various intermediate routers. So far this has been done voluntarily, probably due to the low marginal cost of forwarding a packet. However, when communication of larger amounts of data becomes common (e.g. video), and bandwidth needs to be reserved under various quality of service (QoS) protocols, this altruistic behavior of the routers may no longer hold. If so, we will have to design protocols specifically taking the routers’ self-interest into account. 35

36 Ticket Allocation Game Project lead (Ticket Allocator) (rational and intelligent) Maintenance Engineers (rational and intelligent) effort, time

37 Resource Allocation in Grid Computing

38 ? Incentive Compatible Broadcast in Ad hoc Wireless Networks

39 Tier 1 Tier 2 Tier 3 Tier 1: UU Net, Sprint, AT&T, Genuity Tier 2: Regional/National ISPs Tier 3: Residential/Company ISP Internet Routing

VGC mechanism 40

Example: Shortest Path Goal: route packets along the lowest-cost path from S to T.

Example: Shortest Path • Each edge is an agent • People want to send messages to other people

Winner Determination Problem • Winner Determination Problem – Agents want to bid some goods with all-or-nothing style, and will report their private values. • Maximum Independent Set Problem – Given undirected graph G = (V,E), MIS is to find a maximum independent set X ⊆ V in G. A subset of vertices Y ⊆ V is independent if ∀u, v ∈ Y, (u, v) not in E 43

Maximum Independent Set Problem

• Theorem Winner determination (WD) problem is NP-hard. 45

In general, we can’t approximate VCG-based mechanisms • Inapproximability for VCG-Based Combinatorial Auctions – By Dave Buchfuhrer et al. To appear in the proceedings of SODA 10. 46

Can we cope with it? • In general, it is hardly possible. • Some ways: – Solve some special cases. – Approximate some special cases. – Change problem formulations. 47

The Task Allocation Problem

The Task Allocation Problem • The MinWork Mechanism The idea is to minimize the total work done. This is no very good solution since our agents are able to work in parallel. – Each task is allocated to the agent who is capable of doing it in a minimal amount of time. – Each agent is given payment equal to the time of the second best agent for every task:

The Task Allocation Problem • Theorem: MinWork is a truthful n- approximation mechanism. • Proof:

The Task Allocation Problem • Proof (continue): MinWork belongs to the VGC family (⇒ is truthful)

VGC mechanism • An output function of a VGC mechanism is required to maximize the objective function. In many cases (e.g. combinatorial auctions (Harstad, Rothkopf and Pekec (1995))), this makes the mechanism computationally intractable. Replacing the optimal algorithm with a non-optimal approximation usually leads to untruthful mechanisms 52

VGC mechanism • Thus, a VGC mechanism essentially provides a solution for any utilitarian problem (except for the possible problem that there might be dominant strategies other than truth-telling). utilitarian problems (Green and Laffont (It is known that (under mild assumptions) VGC mechanisms are the only truthful implementations for utilitarian problems (Green and Laffont (1977)).for 1977)). 53

Thank You 54


Online Matching for Adwords Auctions

Add a comment

Related presentations

How organisms adapt and survive in different environment.

Aplicación de ANOVA de una vía, modelo efectos fijos, en el problema de una empres...

Teori pemetaan

Teori pemetaan

November 10, 2014

learning how to mapping

Libros: Dra. Elisa Bertha Velázquez Rodríguez

Materi pelatihan gis

Materi pelatihan gis

November 10, 2014

learning GIS

In this talk we describe how the Fourth Paradigm for Data-Intensive Research is pr...