Preface
CS Research can be considered as system research. Furthermore, we derive problems from system. A problem can be computational and un-computational, and we only talk about computational problems. A computational problem can be polynomial and non-polynomial. For polynomial problems, we can directly design algorithmic mechanism. For non-polynomial problems, we should consider how hard they are. Even for np-hard problems, we may have approximation algorithm.
Game Theory: indivisuals + rules = Outcomes.
Social law auctions
social law: restrictions on the actions of the agents.
problem specification:
- given: a Kripke Structure (or other), a property (specified as a logic formula).
- to find out: a social law that change the system to satisfy the property.
When the agent is rational, and their types are private, it becomes a mechanism design problem.
MD for Social Networks
How to maxmize the influence when nodes are self-interested agents.
How information is diffused in a social network.
How to reliably obtain parameters such as weight and threshold.
Network Flow Auctions
Question: How to find out the minimal cost flow in the strategic cases.
Challenge: each edge can sell parts of its capacity. in the prior-free case it falls into an unknown domain.
Multicast Mechanism Design
Question: how to find out the optimal muticast tree in the strategic case.
It reduces to finding out a Steiner tree in strategic case.
Cellular Traffic Offlaoding
Question: the base station how to optimally offload its traffic to some existing alternative wireless networks.
Chanllenge and Opptunities: how to measure the value of a purchase.