北美代写,美国作业代写,网课代修,Assignment代写-100%原创(^3) E.g., not dictatorial rules, rules for which there is a candidate that cant possibly win, randomized rules, etc. Also, approval cannot be one of the rules because it is not based on rankings. If you use Cup, Cup only satisfies a criterion if it satisfies it for every way of pairing the candidates.

```
Alice
```

```
Bob
```

```
Carol Daniel
```

```
Eva
```

```
Frank
```

```
Figure 1: Externas proximity graph.
```

```
Suppose we receive the following bids:
```

```
Alice
```

```
Bob
```

```
Carol Daniel
```

```
Eva
```

```
Frank
```

```
4
```

```
4
```

北美代写,美国作业代写,网课代修,Assignment代写-100%原创(^25) 5 4 Figure 2: Graph with bids. The number next to an agent is that agents bid. Suppose we have three rackets for sale. One valid (but not optimal) allo- cation would be to give rackets to Carol, Daniel, and Eva. Carol would get a (reported) utility of 2, Daniel would get 10 (25, because two of Daniels neighbors have rackets), and Eva 5, for a total of 17. 2a. (12 points)Give the optimal allocation, as well as the VCG (Clarke) payment for each agent. 2b. (13 points)In general (general graphs, bids, numbers of rackets), is the problem of finding the optimal allocation solvable in polynomial time, or NP-hard? (Hint: think about theCliqueproblem (which is almost the same as theIndependent Setproblem).) One year has passed, and we have returned to Externa. Everyones rackets have broken (we are not in the business of selling high-quality rackets here) and they need new ones. However, the people in the town were not entirely happy with our previous system. Specifically, it turned out that each agent only ever played with (at most) a single other agent, so that multiplying the value by the number of neighbors with rackets really made no sense. Also, agents have realized that they would receive different utilities for playing with different agents. In the new system, we must not only decide on who receives rackets, but (for the agents who win rackets) we must also decide on the pairing, i.e.,who plays with whom. Each agent can be paired with at most one other agent. Each agentisubmits a valuevijfor every one of her neighborsj; agentireceivesvij if she is paired withj(and both win rackets), and 0 otherwise. Suppose we receive the following bids:

```
Alice
```

```
Bob
```

```
Carol Daniel
```

```
Frank
```

(^12) 4 3 2 1 4 Eva 5 5 6 1 5 Figure 3: Graph with bids. Each number is the value that the closer agent on the edge has for playing with the further agent on the edge. Suppose we have four rackets for sale. One valid (but not optimal) outcome would be to pair Alice and Bob, and Daniel and Eva (and give them all rackets), for a total utility of 4 + 1 + 1 + 6 = 12. 2c. (12 points)Give the optimal outcome (pairing and allocation), as well as the VCG (Clarke) payment for each agent. 2d. (13 points)In general (general graphs, bids, numbers of rackets), is the problem of finding the optimal outcome solvable in polynomial time, or NP- hard? (Hint: think about theMaximum-Weighted-Matchingproblem. Keep in mind that the number of rackets is limited, though.)