Algorithmic Game Theory seminar Introduction lecture ..Before we start Degree, background in game theory I expect the seminar to be a fun place, where we meet and talk Cool papers

Some of them are non trivial, most (all?) are interesting ?So whats algorithmic game theory Game theory A set of agents (people) who are in a situation of conflict Each agent has its own goals Assumption agents are rational + common knowledge of rationality

What will happen? Prediction Algorithmic game theory Using ideas from CS in game theory Mechanism design and market design Ad auctions, spectrum auctions, Doctors match Optimization when the players hold the input Divide the rent of an apartment between friends, when each friend gets a different room

Sell items in an auction Markets Examples Routing Advertisements Social

Administration Each student will tell the class about a single paper Coming to class is mandatory you are allowed to skip up to two classes (note that there will be ) And if you dont come to enough lessons Main evaluation criteria how much I think you understand the paper you presented Will also care about how good was the presentation

Textbook: Algorithmic Game Theory by Nisan, Roughgarden, Tardos, and Vazirani Office hours right before class do come by Choosing papers The main point of the seminar is for you to talk about papers There is a list of papers in my webpage: cs.biu.ac.il/~avinatan The order of talks is according to the list Note: there are more papers than students, so its not possible to know dates yet, but I will post a calendar once I know

which papers were chosen Please send me an email by next week, asking for three papers (first second and third priority) Please start preparing in advance: papers take time Games Each player selects a strategy Given the vector of strategies, each player gets a payoff

A game is summarized by the payoff matrix: Columns / Rows R1 R2 R3 C1

1 /4 -1 / 6 2/7 C2 4 /3 3 / -2

3 /4 Same idea for more than two players Basic notions in game theory Mixed strategy: A player specifies whats the probability that she chooses each row Dominant strategy No matter what everyone else does, this is the best thing for me to do Nash equilibrium: A profile of strategies (one

for each player). If no one else changes their decision, its better for me not to change Example - Chicken Weve circled the (pure) Nash equilibria no pure Nash equilibrium 0,0

1-,1 1,1- 1,1- 0,0 1-,1 1-,1

1,1- 0,0 But players can randomize Real life auctions Set of bidders bid for an item At every stage there is a tentative price Everyone who wants can raise the price,

offering a new one Increments can be fixed before hand, or flexible 13 Model Each bidder i has a valuation function vi which takes a subset of the objects, and says how much the bidder wants this subset In the simple case of a single item vi is just how much the bidder

values the item Bidder i will pay a price pi. The utility (happiness) of bidder i is denoted ui, with ui(xi) = vi(xi) - pi where bidder i received a set xi Auctioneer does not know the bidders valuation function! 14 15

Sealed bid auctions Each player gives a single sealed bid Sealed, in the sense that the bid of one player does not depend on the bids of other players The auctioneer opens all the bids, decides who wins and how much they pay Efficient Non-interactive Easy to analyze 16

Second price auction Winner is highest bidder Price is the second highest bid This is what you really get in the ascending auction 17 Second price auction Theorem: Bidding your true valuation is a dominant

strategy in second price auctions Proof: If you bid your value and didnt win: Any other bid which doesnt win is just as good. If you bid enough to win, you will pay more than what you now bid (since you didnt won) so you will have negative utility If you won: any other winning bid will give you the same price. If you decrease your bid and not win you will loose utility 18

First price auctions Highest bidder gets the item, pays her bid Bidding your value is no longer dominant Suppose there are two players, one with value 1 and one with value 2 There is a (pure) Nash equilibrium, in which everyone gives the second highest value, except the person who want the item the most, who adds another 19

VCG auction Suppose we can find the optimal solution if we had all the inputs from the players Lemma 1: If each player i gets paid then the mechanism is truthful Lemma 2: The mechanism remains truthful even if player i pays an additional hi(v-i). where hi(v-i) is any function which is does not depend on the bid of player i. 20

Making money The easiest way to think of VCG is set hi(v-i) = 0. But then the auctioneer has to pay each player a lot of money We want the payments to be such that Players dont loose from the auction The auctioneer does not pay money to any player Use

21 Clarkes payment The rule ( ) ( h = ( ) )

satisfies: No player looses from participating in the auction The auctioneer never pays a player Meaning: player i is charged the damage that he caused to the world 22

Example of VCG - trade A seller has an object, values it for vs Buyer values it for vb We want them to trade if vb > vs Doing this by VCG, means that the mechanism charges vs from the buyer, and pays vb to the seller, loosing money 23 ?Questions

Lets talk about the papers Prisoners Dilemma