Network Traffic and Auctions
The dominant strategy is a second-price auction.
What is bidding one's own true value?
This occurs when the number of elements in S exceeds the number of elements in it's neighbor set N(S)
What is a constricted set?
This step occurs after running the hub update rule and the authority update rule after k number of steps.
What is normalization (sum up all the values and divide by this sum)?
This rule is used to compute the probability of an event by multiplying the marginal probabilities of all the states of the world by each conditional probability that the event occurs in that particular state of the world.
What is the law of total probability?
The number of random edges is proportional to this in a small-worlds network for some value of q.
What is the distance between the two nodes raised to the power of negative q?
These two auctions are functionally equivalent where they start at a highest price and lower the price until at most one person accepts the price.
What are descending price auctions (Dutch auctions) and first-price auctions?
A bargaining solution is said to be this if each node is receiving their outside option plus half of the surplus.
What is the Nash bargaining solution?
This procedure consists of shrinking each page's PageRank by some factor and equally redistributing the total amount "evaporated" among all nodes in the network.
What is scaled PageRank?
This occurs then a particular decision (i.e. accept/reject) exceeds the other decision by at least two in a sequential decision making process.
What is an information cascade?
What is a cluster density?
This is the expected amount of money a seller will receive from an auction.
What is seller's revenue?
An exchange between two nodes such that no non-exchanging nodes can incentivize an exchanging node to deviate and switch bargaining partners.
What is stability?
This occurs when updating the PageRank do not result in any changes to any node's PageRank.
What are equilibrium PageRank values?
This is the formula to use to solve for P(A|B) when you are given P(B|A), P(A), and P(B).
What is Baye's rule?
P(A|B) = P(A)xP(B|A)/P(B)
This is k (the number of new people met by each node in a new wave) multiplied by p (the probability of infecting a particular node).
What is R0?
This paradox describes a situation where adding an edge in a network traffic diagram that has a 0 travel time results in a worst Nash equilibrium travel time.
What is Braess' paradox?
A network exchange graph is said to be this when every node that is participating in an exchange is exchanging at a Nash bargaining solution.
What is balanced?
The seller prefers this auction mechanism in a sponsored search market for advertising slots since it maximizes seller's revenue.
What is a generalized second-price auction?
What is c = 1 + 1/(1 - p)?
This is the threshold value for deciding when to adopt a new behavior, if the behavior can be modeled as a coordination game where the payoff for coordinating on the old action is a and the payoff for coordinating on the new action is b.
What is q >= b/(b+a)?
The capacity (or weights) of a selection of edges such that if you were to remove those edges from the network flow diagram, the resulting graph would have two components.
What is a cut?
What is not balanced?
An item in a VCG auction will always be sold at this price.
What is 0?
The resulting distribution from a preferential attachment (rich-gets-richer) model when p is set to 1.
What is the normal distribution?
This is the process in which a starter node S send a package to target node t and only knows where they lie on the grid and their own random edges. Node S doesn't know where the random edges are in the network.
What is decentralized search?