CS代考 Lecture 1: Introduction – cscodehelp代写 – INTERVIEW&CODEHELP

Lecture 1: Introduction

Auctions

Motivating example: Interactive gig economy
The gig economy (via platforms such as Uber, Amazon Turk, AirBnB…) gives providers of a service flexibility, often at the expense of income security
If multiple providers could service a customer, this could just be decided by the platform or presented as a one-off choice by the customer based on ratings
But a more flexible system will allow interaction between customer and providers to come to the best agreement on price and other factors of importance
The platform will also want to profit…

Slide ‹#› out of 54

Today
Introduction
Auctions for allocation of a single item
English auctions
Dutch auctions
First price sealed bid auctions
Vickrey auctions
Combinatorial auctions
Vickrey-Clarke-Groves mechanism

Slide ‹#› out of 54

Auctions
Auctions are used to allocate scarce resources that are desired by more than one agent.

Examples: selling a painting; selling the right to sell services that use part of the electromagnetic spectrum; selling processing cycles on your PC.

If a resource isn’t scarce, or is desired by only one agent, there’s no problem allocating it.

Auctions aim to allocate resources efficiently, in the sense of allocating them to those that value them the most.

Slide ‹#› out of 54

Structure of an auction
An auctioneer aims to allocate a good to one of the bidders.

The auctioneer wants to maximise the selling price. It attempts to do this through the design of an appropriate auction.

Bidders want to minimise the price at which the good is auctioned. They attempt to do this by using an appropriate strategy.

Slide ‹#› out of 54

Valuation of goods: public
Goods can have private, public/common or correlated value.

Public/common value: The good has the same value to all bidders given that they have perfect knowledge of the item (e.g. a jar of coins). But bidders may have different information about the value of the good (e.g. the estimate of the coins in the jar).

Credit: TradingAcademy.com

Slide ‹#› out of 54

Valuation of goods: private
Goods can have private, public/common or correlated value.

Private value: Bidders have their own valuation of the item (e.g. an antique watch with sentimental value).

Credit: Kayla Kandzorra, flickr

Slide ‹#› out of 54

Valuation of goods: correlated
Goods can have private, public/common or correlated value.

Correlated value: Bidders’ valuations depend partly on private factors and partly on other agents’ valuations of it (e.g. buying a house – your valuation depends on how much you want to live there, but is likely influenced also by how much you can sell it for in the future).

Credit: Photocapy, flickr

Slide ‹#› out of 54

Valuation of goods

Credit: ebay.co.uk

Slide ‹#› out of 54

Auction by visibility
We can categorise auctions according to who can see the bids.

Open cry: the bids are common knowledge to all bidders.

Sealed bid: bidders are not able to determine the value of the bids of other agents.

Slide ‹#› out of 54

Auction by bidding mechanism
We can categorise auctions according to the bidding mechanism.

Ascending: bidding starts at a low price and increases with each successive bid.

Descending: bidding starts at a high price and decreases in each successive round.

One shot: a single round of bidding.

Slide ‹#› out of 54

Auctions by winner determination
We can categorise auctions according to the winner determination mechanism.

First price: agent that bid the highest wins the good and pays the amount of the highest bid.

Second price: agent that bid the highest wins the good and pays the amount of the second highest bid.

Slide ‹#› out of 54

English auctions
For allocation of a single item.
First price, open cry, ascending.
Auctioneer sets a starting price and agents can announce bids that are higher than previous bid.
Rule of when the auction can close can vary: at a set deadline, after a time period when no new bids are made.

Credit: An Tu/European Pressphoto Agency

Slide ‹#› out of 54

What is the dominant strategy for a bidder?

Slide ‹#› out of 54

English auctions

Agent should bid b because it’s lower than their true valuation of the good.

Slide ‹#› out of 54

English auctions
No incentive for the agent to bid higher than their true valuation. If the agent places the next bid and wins the auction they would lose b – v.

Slide ‹#› out of 54

English auctions
Successively bid the smallest amount allowed above the current bid until the bid price reaches your true valuation.
Some English auctions have a set increment amount. Here it is b – p.
Even though the agent would be willing to pay v – p more than the current price, they don’t want to pay as much as the next bid.

Slide ‹#› out of 54

English auctions
How much can the auctioneer expect to make from an English auction?
The winner pays minimally above the second highest valuation.
The larger the difference between the highest and second highest bidder valuations the more the auctioneer will miss out on.
If there’s not much competition, the auctioneer shouldn’t use an English auction, unless the auctioneer is willing to be dishonest…

Slide ‹#› out of 54

Shill bids
A shill bid is a bid placed by the auctioneer, or by agents in collusion with the auctioneer, with the aim of increasing the price paid by the winner.

Shill bids can also be used to get bidders above the reserve price of the good (the minimum price the auctioneer will sell the item).

Slide ‹#› out of 54

Dutch auctions
For allocation of a single item.
First price, open cry, descending.
Auctioneer sets a high price and then incrementally lowers the price until an agent bids equal to the current asking price.
Used to sell items quickly (e.g. tulip auctions in Netherlands).

Credit: , flickr

Slide ‹#› out of 54

What is the dominant strategy for a bidder?

Slide ‹#› out of 54

Dutch auctions
No incentive for the agent to bid higher than their true valuation. If the agent places the next bid they would lose b – v.

Slide ‹#› out of 54

Dutch auctions
It might be beneficial for an agent to wait for a price lower than their true valuation.
But rarely does an agent know u and so waiting risks another agent winning.
How long an agent waits depends on their risk attitude.

Slide ‹#› out of 54

Risk attitudes
You have the choice of taking £100, or you can flip a coin. If the coin is heads then you take £200 instead, if the coin is tails then you get nothing. The expected utility of the two options is equal (assuming you value £200 twice as much as your value £100).

Risk averse agents prefer a “sure thing”. They will take the £100.
Risk seeking agents prefer to take a gamble. They will flip the coin.
Risk neutral agents are indifferent. They have no preference over taking £100 or flipping.

Slide ‹#› out of 54

Dutch auctions
If bidders are risk averse, can expect more revenue from a Dutch auction than an English auction.

If bidders are risk seeking, can expect more revenue from an English auction than a Dutch auction.

How much can the auctioneer expect to make from a Dutch auction?

Slide ‹#› out of 54

First-price sealed bid auctions
For allocation of a single item.
First price, sealed bit, one shot.
Bidders submit a private bid to the auctioneer. There are no subsequent rounds. The agent with the highest bid wins and pays the price they bid.

What is the dominant strategy for a bidder?

Slide ‹#› out of 54

First-price sealed bid auctions
Like Dutch auction, it might be beneficial for an agent to bid for a price lower than their true valuation.
But rarely does an agent know u and so bidding less than your true valuation risks another agent winning.
How much less than their true valuation an agent bids depends on their risk attitude.
Strategically isomorphic to Dutch auction.

Slide ‹#› out of 54

First-price sealed bid auctions

How much can the auctioneer expect to make from a first-price sealed bid auction?
Same as in Dutch auction.

Slide ‹#› out of 54

Vickrey auctions
For allocation of a single item.
Second price, sealed bid, one shot.
Bidders submit a private bid to the auctioneer. There are no subsequent rounds. The agent with the highest bid wins and pays the price of the second highest bid.

What is the dominant strategy for a bidder?

Should you bid more, less or the same as your true valuation?

Slide ‹#› out of 54

Vickrey auctions
Suppose you bid more then your true valuation. In this case, you may be more likely to be awarded the good, but if the second highest bid is above your valuation then you make a loss.
Suppose you bid less than your true valuation. In this case, you stand less chance of winning than if you bid your true valuation. And if you do win, the amount you pay will not have been affected (you will still pay the price of the second highest bid).
There is no benefit to do anything other than bid your true valuation!
The winner will pay the second highest valuation – similar revenue to the English auction.

Slide ‹#› out of 54

Vickrey auctions
An agent who accurately knows v and p can place an anti-social bid to make the highest bidder pay more.
If the agent with the highest valuation does not bid, then the anti-social bidder will have to pay more than their valuation – anti-social bidding is risky!
However, a dishonest auctioneer can place an anti-social bid after they have read all other bids without any risk…

Slide ‹#› out of 54

Winner’s curse
Consider an English auction: when an auction is over, should the winner feel happy that they won the auction for less than or equal to their valuation? Or should they be concerned that no on else valued the good so highly? This phenomenon is the winner’s curse.
It is especially problematic in auctions of goods that have a significant common value component.

Exercise
Does the winner of a Dutch auction suffer from the winner’s curse (and if so, why)?
Does the winner of a Vickrey auction suffer from the winner’s curse (and if so, why)?

Slide ‹#› out of 54

Collusions
None of the four auction types is immune to collusion; all the bidders can form a coalition (the grand coalition) and agree to buy the item for a low price from the auctioneer. The coalition can then sell the item for a higher price and split the profit between themselves.

Hiding the bids made by agents, and keeping the winner a secret, discourages collusion.

Consider a first-price sealed bid auction. The true value of the good is £1000. Bidders agree that all will bid £10 except bidder A who will bid £15. After the auction, the bidders will resell the good and split the profit they make. Why might this be risky for the colluders?

Slide ‹#› out of 54

Combinatorial auctions
Combinatorial auctions are auctions in which multiple goods are auctions simultaneously.
We have many goods, some may be identical, some may be different.
Agents have preference over different bundles of goods.

Slide ‹#› out of 54

Mobile phone bandwidth auction
In 2000, UK government held an auction to sell licences to mobile phone service providers. It was a combinatorial auction with multiple frequencies and geographical locations. The auction mechanism was designed by two game theorists: Binmore and Klemperer. The total revenue was £22.5 billion.
This was at the peak of “dot com” boom, with massive speculative investment in communications technology.
“there was a great deal of caterwauling as telecom executives sought to blame … game theorists who supposedly made them pay more for their licences than they were worth. But who but an idiot would bid more for something than they thought it was worth?” [Binmore, 2007]

Slide ‹#› out of 54

Combinatorial auction formalisation
is the set of items to be auctioned.

is the set of bidders.

Each bidder has a valuation function so that for every bundle of goods , the value indicates how much would be worth to .

Slide ‹#› out of 54

Free disposal and normalised value functions
The property of free disposal holds for if agent is never worse off having more goods.
implies

A valuation function is said to be normalised if agent gets no value for the empty allocation.

Slide ‹#› out of 54

Substitutability and complementarity
Items can be substitutes for one another. A valuation function exhibits substitutability if and only if there exists two bundles where such that

Items can be complementary to one another. A valuation function exhibits complementarity if and only if there exists two bundles where such that

In multiple single item auctions, an agent with a valuation that exhibits complementarity may bid aggressively for a set of items, hoping they win the whole bundle. If it loses the auction for one item in the bundle, then they may have paid too much for other items in the bundle. This is known as the exposure problem.

Slide ‹#› out of 54

Combinatorial auctions
An outcome is an allocation of goods to agents.
such that and
for all we have

The auctioneer wants to find the allocation that maximises social welfare. We define a function that gives the social welfare of an allocation in terms of the values obtained by the agents. (Note, there are agents, is the bundle allocated to agent , is agent ’s valuation function.)
,

But, the auctioneer doesn’t have access to the private valuations of agents….

Slide ‹#› out of 54

First attempt combinatorial auction mechanism
Every agent simultaneously declares a valuation function (it is possible that ).
The mechanism identifies the allocation that maximises , and this is the allocation that’s made.

Two big challenges!
Representational complexity: a recent bandwidth auction had 1122 licences for auction, so a table defining a valuation function for this would require entries – vastly larger than number of atomic particles in universe!
Computational complexity: winner determination is NP-hard even under quite restrictive assumptions.

Slide ‹#› out of 54

Bidding language
We want to find a succinct bidding language that will allow bidders to sufficiently express their valuations.
An atomic bid is a pair where and is the price the bidder is willing to pay for the item.
A bundle satisfies an atomic bid if (assuming free disposal).
An atomic bid defines a valuation function such that: if satisfies ,
otherwise.

There are many valuation functions that atomic bids on their own cannot express. To create more interesting bids we can combine atomic bids with logical connectives.

Slide ‹#› out of 54

Composite bids
Using the XOR connective, we can specify a number of atomic separate bids, but will only pay for at most one of them to be satisfied. If an allocation satisfies a number of atomic bids, the bidder pays the price which is higher.

Exercise
Give the valuations of all possible bundles of goods from set {a, b, c, d} (i.e. give the full valuation function) for the XOR bid

Slide ‹#› out of 54

XOR bids clearly allow us to express more complex valuation functions. In fact, XOR bids can represent any valuation function, but in the worst case it takes an exponential number of atomic bids.

Slide ‹#› out of 54

Feasible winner determination
Given a set of bids, the complexity of finding the allocation that maximises social welfare is NP-hard — the winner determination problem is an example of a combinatorial optimisation problem, which are notoriously hard.
There are two approaches for attempting to solve the winner determination problem efficiently:
Use techniques which are optimal (always find the best allocation) but which are efficient in specific cases.
Accept approximate solutions that are not optimal (time constraint, distance constraint, heuristic, etc.).

Slide ‹#› out of 54

Constrained bid winner determination
Optimal techniques for winner determination on constrained problems include:
Limiting the size of an atomic bid to a constant. We might enforce that an atomic bid can include a maximum of two items.
Ensure bids are on contiguous goods (if the goods are not ordered we can apply some arbitrary ordering to them).

These constraints on the bids reduce the complexity of the winner determination problem.

Slide ‹#› out of 54

Heuristic winner determination
Heuristic techniques for winner determination include the greedy approach.
A greedy allocation starts by trying to find the largest bid we can satisfy, and then the next largest, and so on until all goods have been allocated.
The greedy allocation is fast to compute, but it may not find the optimal solution.

Slide ‹#› out of 54

Exercise
We have two agents and three goods .

Which allocation of goods maximises social welfare?

Which allocation of goods is made using the greedy allocation?

Slide ‹#› out of 54

Manipulation of combinatorial auctions
Even with a sufficient bidding language and an efficient solution for the winner determination problem, we still face the issue that bidders may try to strategically manipulate the auction.
We would like a mechanism in which if every agent acts rationally then they will bid their true valuation.

We have seen this in the Vickrey Auction. We can use a generalisation of the Vickrey auction to ensure truth telling is the dominant strategy in combinatorial auctions.
The generalisation is known as the Vickrey-Clarke-Groves mechanism (VCG mechanism).
Just like in the Vickrey auctions, truth telling is the dominant strategy for the VCG mechanism.

Slide ‹#› out of 54

Vickrey-Clarke-Groves mechanism
Each agent simultaneously declares their valuation function .
The mechanism computes the allocation which maximises social utility, according to the valuation functions declared in step 1.
The goods are allocated according to .
Each agent pays the amount to the mechanism, where is computed as follows.
Let denote the allocation that would have been chosen at step 2 had agent declared (in step 1) the valuation for all and every other agent apart from had declared the same valuation as the did in step 1.
Then .

Social welfare without
Total value to other agents

Slide ‹#› out of 54

Exercise
1. Each agent simultaneously declares their valuation function .
2. The mechanism computes the allocation which maximises social utility, according to the valuation functions declared in step 1.
3. The goods are allocated according to .
4. Each agent pays to the mechanism, where is computed as follows.
– Let denote the allocation that would have been chosen at step 2 had agent declared (in step 1) the valuation for all and every other agent apart from had declared the same valuation as the did in step 1.

Suppose we have two goods and and two agents who can each obtain at most one item. The agents declare the following true valuation functions:

What allocation of goods is made?
How much does each agent pay to the mechanism?
What utility does each agent get?
Can agent improve its utility by lying and declaring valuation ? Hint: think about the possible cases.

Slide ‹#› out of 54

Summary
Auctions are a way of allocating resources, individually or in bundles, to agents based on how much they value those resources
The design of an auction mechanism can influence whether it achieves maximum social welfare, whether it is open to manipulation, the potential benefit to the auctioneer depending on the risk profile of bidders, and whether the bidders can be satisfied that they have paid a reasonable price
For complex combinatorial auctions, we may realistically use heuristics to determine a good allocation due to the complexity of finding the best allocation

Slide ‹#› out of 54

/docProps/thumbnail.jpeg

CS代考 Lecture 1: Introduction – cscodehelp代写

Published by admin

Leave a Reply Cancel reply