Rahul Vaze
Abstract
An online truthful budgeted matching problem is considered for a bipartite graph, where the right vertices are available ahead of time, and individual left vertices arrive sequentially. On arrival of a left vertex, its edge utilities (or weights) to all the right vertices and a corresponding cost (or bid) are revealed. If a left vertex is matched to any of the right vertices, then it has to be paid at least as much as its cost. The problem is to match each left vertex instantaneously and irrevocably to any one of the right vertices, if at all, to find the maximum weight matching that is truthful, under a payment budget constraint. Truthfulness condition requires that no left vertex has any incentive of misreporting its cost. Assuming that the vertices arrive in an uniformly random order (secretary model) with arbitrary utilities, a truthful algorithm is proposed that is 24ß- competitive (where ß is the ratio of the maximum and the minimum utility) and satisfies the payment budget constraint. Direct applications of this problem include crowdsourcing auctions, and matching wireless users to cooperative relays in device-to-device enabled cellular network.
- Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. A knapsack secretary problem with applications. In Approximation, randomization, and combinatorial optimization. Algorithms and techniques, pages 16--28. Springer, 2007. Google Scholar
Digital Library
- Roger B Myerson. Optimal auction design. Mathematics of operations research, 6(1):58--73, 1981. Google ScholarDigital Library
- Y. Singer. Budget feasible mechanisms. In Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on, pages 765--774, Oct 2010. Google ScholarDigital Library
- Gagan Goel, Afshin Nikzad, and Adish Singla. Matching workers expertise with tasks: Incentives in heterogeneous crowdsourcing markets. In NIPS Workshop on Crowdsourcing, 2013.Google Scholar
- Yaron Singer and Manas Mittal. Pricing mechanisms for crowdsourcing markets. In Proceedings of the 22Nd International Conference on World Wide Web, WWW '13, pages 1157--1166, Republic and Canton of Geneva, Switzerland, 2013. International World Wide Web Conferences Steering Committee. Google ScholarDigital Library
- Dejun Yang, Guoliang Xue, Xi Fang, and Jian Tang. Crowdsourcing to smartphones: incentive mechanism design for mobile phone sensing. In Proceedings of the 18th annual international conference on Mobile computing and networking, pages 173--184. ACM, 2012. Google ScholarDigital Library
- Ashwin Subramanian, G Sai Kanth, Sharayu Moharir, and Rahul Vaze. Online incentive mechanism design for smartphone crowd-sourcing. In Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt), 2015 13th International Symposium on, pages 403--410. IEEE, 2015.Google Scholar
- Nitish Korula and Martin Pál. Algorithms for secretary problems on graphs and hypergraphs. In Automata, Languages and Programming, pages 508--520. Springer, 2009. Google ScholarDigital Library
Recommendations
Online vertex-weighted bipartite matching and single-bid budgeted allocations
SODA '11: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithmsWe study the following vertex-weighted online bipartite matching problem: G(U, V, E) is a bipartite graph. The vertices in U have weights and are known ahead of time, while the vertices in V arrive online in an arbitrary order and have to be matched ...
Prior-free auctions for budgeted agents
EC '13: Proceedings of the fourteenth ACM conference on Electronic commerceWe consider prior-free auctions for revenue and welfare maximization when agents have a common budget. The abstract environments we consider are ones where there is a downward-closed and symmetric feasibility constraint on the probabilities of service ...
Prior-free auctions for budgeted agents
EC '13: Proceedings of the fourteenth ACM conference on Electronic commerceWe consider prior-free auctions for revenue and welfare maximization when agents have a common budget. The abstract environments we consider are ones where there is a downward-closed and symmetric feasibility constraint on the probabilities of service ...
Comments