Algorithmic Mechanism Design Tutorial

Document Sample
Algorithmic Mechanism Design Tutorial Powered By Docstoc
					        Algorithmic Mechanism Design Tutorial
                              Brendan Lucier
                       (Recorded by Geoﬀrey Peddle)
                                  Nov. 16, 2010

1     Introduction
We are going to consider algorithm design from a game theoretic viewpoint.
What changes is that now agents, with vested interests, hold some of the values
that are important to the outcome. We want to develop algorithms that are
resilient to the possibility that agents will lie in order to manipulate the outcome
for their own beneﬁt. Most of todays discussion is based on the paper “Truthful
Mechanisms for One-Parameter Agents” by Aaron Archer and Eva Tardos.

2     Makespan problem
Consider the related machine makespan minimization problem.
Deﬁnition. Given n jobs with processing times {p1 , p2 , · · · , pn } and m ma-
chines with speeds {s1 , s2 , · · · , sm } we want to assign the jobs to machines to
minimize the maximum ﬁnish time.
    Recall that the load on machine j is Lj = i∈Ij pi where we are summing
over the jobs Ij assigned to machine j. The makespan is Cmax = maxj Lj /sj .
    The game theoretic twist: Machines are rational agents. If machine j runs
a load Lj it incurs a cost (negative value) of Lj /sj . To minimize this cost
machines want to minimize the load that they are assigned. The machine speed
is private information and they will lie to reduce their load and thus their cost.
    We need to convince machines to reveal their true speed, not under report
their speed to avoid work. This will allow us to solve our makespan problem.
The idea is to pay machines for their time so they will no longer have an incentive
to lie.
Deﬁnition. A mechanism takes bids (i.e. declared speeds) and returns an as-
signment of jobs plus payments to the machines P1 , P2 , · · · , Pm .
    The utility of machine j is Pj − Lj /sj or the payment - load / true speed.
    We will write {b1 , b2 , · · · , bm } for declared speed (bids) and uj (b) for the
utility of machine j resulting from bids b where b represents the set of bids by

all machines. Note that the utility of machine j also implicitly depends on sj ,
its true speed.
    We write b−j for the bids of all machines excluding machine j.
Deﬁnition. A mechanism is truthful if the utility of a machine is maximized by
telling the truth. That is ∀j, ∀sj , ∀b−j and ∀bj its the case that uj (sj ; b−j ) ≥ uj (bj ; b−j ).

   Assume that each agent only cares about maximizing its own utility so it
won’t lie unless it will directly beneﬁt. Each agent’s utility is only a function of
what jobs that agent gets assigned.

Deﬁnition. Let Lj (bj ; b−j ) be the load assigned to machine j by an algorithm
for our makespan problem. Then that algorithm is monotone if Lj (bj ; b−j ) is a
monotone non-decreasing function (∀j, ∀b−j ).

   Another way of saying this is that the allocation to machine j is non-
decreasing as the declared speed increases.

Theorem 1. Given an algorithm A, there exists a payment scheme that makes
A truthful if and only if A is monotone.

   The problem of designing a truthful mechanism therefore reduces to design-
ing a monotone algorithm. Intuitively it would seem easy to come up with
monotone algorithms but this is often not the case.

2.1     Non-monotone algorithm
Recall the greedy longest-processing-time algorithm: order the jobs from longest
to shortest processing time and then greedily assign each to the least-loaded
machine. This algorithm is a 2-approximation, but it is not monotone. Consider
an example with 3 tasks and 2 machines.
   Let the tasks be p1 = 2 and p2 = p3 = 1 +
   Let the machine speeds be s1 = 1 and s2 = 1 −
   Our greedy algorithm assigns: p1 → s1 , p2 → s2 and p2 → s2 resulting in
loads L1 = 2 and L2 = 2(1 + )
   But if we increase the speed of machine 2 to s2 = (1 + ) then its load de-
creases from 2(1 + ) to 2. So this algorithm is not monotone.

2.2     Monotone algorithm
After much work people have a monotone PTAS solution that is very complex.
Instead of looking at this we are going to look at a randomized 3-approximation
that is truthful in expectation (i.e. agents maximize their expected utility by
declaring truthfully). Note that with random algorithms the deﬁnition of mono-
tonicity changes slightly but has the same form. Now Lj (bj ; b−j ) becomes the
expected load. Our random monotone greedy algorithm for a 3-approximation
is algorithm 1.
    We will now describe steps 2-4 in more detail, starting with step 2.

 Algorithm 1:             Input:   declared speeds s1 , s2 , · · · , sm and job times
 p 1 , p 2 , · · · , pn
 1   Sort input so s1 ≥ s2 ≥ · · · ≥ sm and p1 ≥ p2 ≥ · · · ≥ pn .
 2   Compute a lower bound T on the optimal makespan.
 3   Greedily make a fractional assignment with makespan T.
 4   Round to an integral assignment with makespan ≤ 3T .

Deﬁnition. A fractional assignment is valid for makespan T if whenever job j
is partially assigned to machine i, pj /si ≤ T .

   This is saying that if job j was the only job on machine i, then it would
complete in less time than T. Now we give the algorithm that will attempt to
do a fractional assignment with makespan T.

 Algorithm 2: Fractional assignments
 1   i ← 1;
 2   L1 , L2 , · · · , Lm ← 0;
 3   for j = 1, · · · , n do
 4        Compute what fraction of job j to put on machine i.
 5        if Li + pj ≤ T × si then
 6            pj assigned to machine i
 7            Li ← Li + pj
 8        end
 9        else
10            place fraction of pj onto machine i such that
              Li + pj × f raction = T × si
11            place the rest of the job on machine i+1.
12            i ← i + 1 (switch to machine i + 1)
13        end
14   end

    Details: Step 3
    Note: this greedy algorithm creates a fractional assignment. Is this assign-
ment valid? Write i(j) for the slowest machine onto which job pj ﬁts (in time
T ). Then we ﬁnd a valid assignment if job j is placed on or before machine i(j)
for all j. So, if the greedy algorithm creats a valid assignment where job j is
placed on machine i, we must have
                                                   j            i
                              T ≥ max{pj /si ,          pk /         sl }.
                                                  k=1          l=1

Since every job must be placed on some machine, the above equation must hold

for some i, for every j. So it must be that
                                                 j            i
                     T ≥ max min max{pj /si ,         pk /         sl }.
                           j    i
                                                k=1          l=1

Call the right-hand side of the above inequality TL.B. ; this will be our lower
bound for step 2.
    One can show that the greedy algorithm does actually ﬁnd a valid assignment
when T = TL.B. .
    Lemma: There exists a fractional assignment meeting lower bound T.
    Details: Step 4.
    Our rounding is as follows. If some fraction α of job pj is on machine i then
assign pj to machine i with probability α. Note that the expected load will be
equal to the fractional load with this assignment so it is enough to show that
the fractional load is monotone.
    Claim: Fractional loads are monotone.
    Suppose that machine i lowers its declared speed from si to si = si /α, α > 1.
           ´                                              ´
    Let TL.B. be the new lower bound with declared si and TL.B. be the lower
bound with declared si .
               ´                   ´
    Note: TL.B. ≥ TL.B. and TL.B. ≤ α × TL.B.
    If machine i that we are considering is the slowest then it was allocated the
remainder when all other machines had ﬁnished with time TL.B. . Since TL.B.      ´
is at least as large as TL.B. this left over portion will only get smaller when bid
changes from si to si .
    Otherwise if machine is not the slowest then the load will change from TL.B. ×
        ´      ´         ´     ´       ´
si to TL.B. × si . But TL.B. × si = TL.B. × si /α ≤ TL.B. × si so the load decreases.
    We conclude that our algorithm is monotone, so we could implement this
algorithm and calculate payments so that no machine would have an incentive
to lie about its speed.


Shared By: