隨著資通訊技術的快速演進，許多嶄新的應用領域相繼出現，順應此一趨勢所相
應而生的應用系統往往非常的龐大。隨著系統規模的成長，一個重要的發展趨勢
就是，互助合作的傾向與需求愈來愈明確。在此，我們將此類需要集體努力，才
足以共同完成目標之應用服務統稱為群組服務(group services)。在本論文中所探
討之群組服務納入群組參與者數量之上下限制條件，並且允許每個參與者參加至
多一定值群組之情況。為使群組服務更加完備，群組條件中的利益模型也是一必
需考量之重要因素。為此，我們提出兩種不同型態之群組服務: 利益一致群組服務
與等級一致群組服務。深入探討其對應之指派問題，希望透過對於參與者之妥善
分派，最大化系統獲得的總體利益。

在利益一致群組服務之指派議題(簡稱PAP) 中，每個參與者參與同一群組
將產生相同的利益。我們首先針對參與者僅允許加入至多一個群組之特例，設計
兩種演算法以因應不同效率需求之應用。其中，啟發式演算法能夠提供一1/2 近
似解結果。另一方面，我們則以分支搜尋的方式，並藉由我們所發現之最佳解重
要特性妥善避免不必要的分支情況有效率地找出問題之最佳解。我們更進一步延
伸上述技術，使其能夠解決每個參與者參加至多一定值群組之情況。

為探討更貼近實務應用之群組服務，本論文進一步提出等級一致群組服務之
指派議題(簡稱RCAP)。此一利益模型，允許每個參與者參與同一群組將產生不
同的利益，然而需要遵守等級一致的特性。為此，我們仍先探究參與者僅允許加
入一個群組之特例情況。我們提出以分配向量的角度來處理，並且設計出一有效
機制能夠找出一分配向量之最佳指派。以此機制為基礎，我們發展出1/2 近似解
演算法及分支搜尋最佳解演算法。在找出最佳解之機制上，我們發展一最佳分配
向量之組成型態以作為分支搜尋演算法之重要基礎並且提出許多新穎的裁減策
略。然而，當此問題允許每個參與者參與至多一定值群組之情況時，前述技術並
沒有辦法被妥善地延用。儘管如此，透過先前研究成效作為基礎，本論文針對此
一研究議題，提供我們所發現之重要特性，預期可以對於相關演算策略之設計產
生助益。

With the advancement of information and communication technologies, several novel application areas are constantly being developed. The derivative application systems based on this conspicuous trend are usually large-scale. With the increase of the system scale, a significant trend might be anticipated, i.e., the phenomenon of mutual aid among users will become more evident. In this dissertation, we denote the services that require summoning a collection of patrons to cooperatively fulfill a task or mission as ”group services”.
The group services studied in this dissertation incorporate the lower and upper bound constraints of the participation number of each group into the group requirement. Moreover, we discuss a case where each patron is allowed to join at most one group, and a more complicated case, where each patron is allowed to join no more than a given number of groups. To facilitate group services, the profit model among the group services is also a significant factor that should be considered. We propose two kinds of group services differentiated according to their profit models: profit-consistent group services, and rank-consistent
group services. This dissertation subsequently focuses on designing efficient
mechanisms to deal with patron assignment issues for these two group services. Specifically, we intend to appropriately assign patrons to groups to best benefit the grouping system.

In the patron assignment problem for profit-consistent group services (called PAP), the yielded profit is consistent for any patron assigned to the same group. We focus on the special case in which each patron can only join one group at most. To solve this problem, we propose two approaches in response to different efficiency requirements. One aims at providing a heuristic algorithm with an approximation factor of 1/2. The other approach aims to determine an optimal solution using a branch and bound technique in an efficient manner. To achieve efficiency, we introduce a theorem that captures a useful property of an optimal assignment. Moreover, we successfully extend the above methods to solve the general problem in which each patron is allowed to join no more than a given number of groups.

To provide a general profit model for group services, we focus on the patron assignment problem for rank-consistent group services (called RCAP). The relaxed profit model yields distinct profits on the same group but the profits should follow the rank-consistent property among different groups. We address the special case in which each patron can only join at most one group at first. Following, we introduce the technique of allocation vectors and design a generic procedure to obtain the optimal physical assignment under a given allocation vector. The above technique lays the foundation to develop an 1/2-approximation algorithm and a branch and bound algorithm for seeking the optimal solution. More importantly, the branch and bound algorithm is featured by employing a specific pattern of optimal allocation vector and several newly proposed pruning strategies. Unfortunately, the proposed techniques cannot be directly extended for solving the general case of RCAP in which each patron can join no more than a given number of groups. However, based on the above research effort, we provide some novel ideas that might be useful in establishing a strategy for solving this challenging problem.

[1] M. Hyodo, T. Matsuo, and T. Ito, “An optimal coalition formation algorithm for electronic group
buying,” in Proceedings of the 2003 SICE Annual Conference, vol. 3, pp. 3402–3407, 2003.
[2] T. Lu and C. E. Boutilier, “Matching models for preference-sensitive group purchasing,” in Proceedings
of the 13th ACM Conference on Electronic Commerce, pp. 723–740, 2012.
[3] G. Raravi, A. Mondal, R. Thangaraj, and A. Singh, “Mobiherd: Towards enabling cost-effective and
scalable mobile group buying,” in Proceedings of the 17th IEEE International Conference on Mobile
Data Management (MDM), vol. 1, pp. 28–33, 2016.
[4] K. S. Anand and R. Aron, “Group buying on the web: A comparison of price-discovery mechanisms,”
Management Science, vol. 49, no. 11, p. 1546–1562, 2003.
[5] L. Boongasame, “Survey on buyer coalition mechanisms,” Applied Mathematical Sciences, vol. 7,
no. 5, pp. 229–236, 2013.
[6] “Amazon mechanical turk.” https://www.mturk.com/.
[7] D. Zhang, L. Wang, H. Xiong, and B. Guo, “4w1h in mobile crowd sensing,” IEEE Communication
Magazine, vol. 52, no. 8, pp. 42–48, 2014.
[8] B. Pan, Y. Zheng, D. Wilkie, and C. Shahabi, “Crowd sensing of traffic anomalies based on human
mobility and social media,” in Proceedings of the 2013 ACM SIGSPATIAL International Conference
on Advances in Geographic Information Systems, pp. 344–353, 2013.
[9] C. J. Ho and J. W. Vaughan, “Online task assignment in crowdsourcing markets,” in Proceedings of
the 26th Conference on Artificial Intelligence(AAAI), July 2012.
[10] Y. Wang, W. Hu, Y. Wu, and G. Cao, “Smartphoto: a resource-aware crowdsourcing approach for image
sensing with smartphones,” in Proceedings of the 2014 ACM international symposium on Mobile
ad hoc networking and computing(MobiHoc), pp. 113–122, 2014.
[11] S. Assadi, J. Hsu, and S. Jabbari, “Online assignment of heterogeneous tasks in crowdsourcing markets,”
in Proceedings of the AAAI Conference on Human Computation and Crowdsourcing(HCOMP),
2015.
[12] C. J. Ho, S. Jabbari, and J. W. Vaughan, “Adaptive task assignment for crowdsourced classification,”
in Proceedings of the 30th International Conference on Machine Learning, 2013.
[13] J. Bragg, A. Kolobov, Mausam, and D. S. Weld, “Parallel task routing for crowdsourcing,” in Proceedings
of the AAAI Conference on Human Computation and Crowdsourcing(HCOMP), 2014.
[14] L. T. Thanh, S. Stein, A. Rogers, and N. R. Jennings, “Efficient crowdsourcing of unknown experts
using bounded multi-armed bandits,” Artificial Intelligence Journal, no. 214, pp. 89–111, 2014.
[15] P. Cheng, X. Lian, L. Chen, J. Han, and J. Zhao, “Task assignment on multi-skill oriented spatial
crowdsourcing,” IEEE Transactions on Knowledge and Data Engineering, vol. 28, pp. 2201–2215,
Apr 2016.
[16] G. T. Ross and R. M. Soland, “A branch and bound algorithm for the generalized assignment problem,”
Mathematical Programming, vol. 8, no. 1, pp. 91–103, 1975.
[17] A. Darmann, E. Elkind, S. Kurz, J. Lang, J. Schauer, and G. Woeginger, “Group activity selection
problem,” in Proceedings of the 8th international conference on Internet and Network Economics,
pp. 156–169, 2012.
[18] A. Darmann, “Group activity selection from ordinal preferences,” in Proceedings of the 2015 International
Conference on Algorithmic DecisionTheory, vol. 1, pp. 35–51, 2015.
[19] A. Darmann, E. Elkind, S. Kurz, J. Lang, J. Schauer, and G. Woeginger, “Group activity selection
problem with approval preferences,” International Journal of Game Theory, 2017.
[20] L. Zhou and P. Tokekar, “Task allocation for wireless sensor network using logic gate-based evolutionary
algorithm,” in Proceedings of the 31st AAAI Conference on Artificial Intelligence, pp. 565–571,
2017.
[21] M. P. Johnson, H. Rowaihy, D. Pizzocaro, A. Bar-Noy, S. Chalmers, T. F. L. Porta, and A. Preece,
“Sensor-mission assignment in constrained environments,” IEEE Transactions on Parallel and Distributed
Systems, vol. 21, pp. 1692–1705, Nov 2010.
[22] A. A. Ferjani, N. Liouane, and I. Kacem, “Task allocation for wireless sensor network using logic
gate-based evolutionary algorithm,” in Proceedings of the 2016 International Conference on Control,
Decision and Information Technologies (CoDIT), pp. 654–658, 2016.
[23] M. Zhao, Y. Zuo, Y. Y. Fang, and M. D. Li, “Sensor assignment method based on time-varying measurement
variance for tracking multi-targets,” in Proceedings of the 2016 Chinese Control and Decision
Conference (CCDC), pp. 3368–3372, 2016.
[24] M. Sghaier, S. Hammadi, H. Zgaya, and C. Tahon, “An optimized dynamic carpooling system based on
communicating agents operating over a distributed architecture,” in Proceedings of 2011 International
Conference on Intelligent Systems Design and Applications (ISDA),, pp. 124–129, 2011.
[25] L. Knapen, D. Keren, A.-U.-H. Yasar, S. Cho, T. Bellemans, D. Janssens, and G. Wets, “Estimating
scalability issues while finding an optimal assignment for carpooling,” Procedia Computer Science,
vol. 19, no. Supplement C, pp. 372 – 379, 2013.
[26] X. Qi, L. Wang, and X. Wang, “Optimization of carpooling based on complete subgraphs,” in Proceedings
of the 35th Chinese Control Conference (CCC), pp. 9294–9299, 2016.
[27] I. Jang, H. S. Shin, and A. Tsourdos, “A game-theoretical approach to heterogeneous multi-robot task
assignment problem with minimum workload requirements,” in Proceedings of the 2017 Workshop on
Research, Education and Development of Unmanned Aerial Systems, pp. 156–161, 2017.